《数据结构》教学大纲

1、数据结构教学大纲一、课程基本信息中文名称数据结构英文名称Data Structure适用专业计算机科学与技术/信息管理与信息系统/信息工程先修课程C程序设计课程类别专业本科学科基础课程修读性质必修学分/学时3.5学分/51学时（实践学时:17）考核方式考试二、教学目标本课程是为计算机科学与技术、信息管理与信息系统、信息工程的本科生开设的学科基础课程之一，学习本课程能使学生掌握数据在计算机中的表示、存储和处理。为以后学习编译程序、操作系统、数据库系统打下基础。掌握常用的数据结构及内在的逻辑关系，计算机软件设计中的算法知识。提高软件设计和编程技能。学会初步对不同的存储结构和相应算法的对比，有一定的

2、算法改进能力。三、教学内容及基本要求第一章 绪论（理论学时：3学时/实践学时：1学时）（一）教学目标1.了解数据结构的发展和地位；2.了解各种算法描述方法和算法设计的基本要求；3.理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；4.掌握对算法的评价标准和算法效率的度量方法；（二）重点、难点重点：理解数据结构、逻辑结构、存储结构和抽象数据类型的基本概念；掌握对算法的评价标准和算法效率的度量方法；难点：算法的评价标准和算法效率的度量方法。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.什么是数据结构2.基本概念和术语3.抽象数据类型的表示和实现4.算法和算法分析（1）算

3、法（2）算法设计要求（3）算法效率的度量（4）算法的存储空间需求第二章 线性表（理论学时：8学时/实践学时：3学时）（一）教学目标1.理解线性表的概念、逻辑结构特性以及两种存储结构特性，针对实际应用能从时间和空间复杂度的角度选用适当的存储结构；2.熟练掌握线性表的顺序存储结构及其各种基本运算；3.熟练掌握线性表的链式存储结构（单链表、循环链表、双向链表）及其各种基本运算，能在实际应用中选用适当的链表结构；（二）重点、难点重点：线性表的概念、逻辑结构特性以及两种存储结构特性，线性表顺序存储实现中的创建、查找、插入和删除等基本操作及相关算法，线性表链式存储实现中单链表、循环链表和双向链表的创建、查

4、找、插入和删除等基本操作及相关算法。难点：线性表顺序和链式存储实现中的某些操作及相关算法。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.线性表的类型定义2.线性表的顺序表示和实现3.线性表的链式表示和实现（1）线性链表（2）循环链表（3）双向链表第三章 栈和队列（理论学时：5学时/实践学时：2学时）（一）教学目标1.掌握栈和队列的定义、表示、实现和应用；2.掌握栈的顺序存储结构和链式存储结构以及相应操作的实现；3.了解递归的概念和递归过程的实现；4.掌握队列的顺序存储结构（循环队列）和链式存储结构的实现；（二）重点、难点重点：栈和队列的定义、表示、实现和应用；栈的顺序存储结

5、构和链式存储结构以及相应操作的实现；队列的顺序存储结构（循环队列）的实现；难点：栈和队列的顺序存储结构和链式存储结构以及相应操作的实现。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.栈（1）抽象数据类型栈的定义（2）栈的表示和实现2.栈的应用举例（1）数值转换（2）括号匹配的检验（3）行编辑程序（4）迷宫求解（5）表达式求值3.队列（1）抽象数据类型队列的定义（2）链队列-队列的链式表示和实现（3）循环队列-队列的顺序表示和实现第四章 串（理论学时：2学时）（一）教学目标1.掌握串的基本概念、顺序和链式存储结构；2.掌握串的各种基本运算；3.掌握顺序存储结构上串的各种操作，

6、了解串的应用；（二）重点、难点重点：串的基本概念、顺序和链式存储结构及各种基本运算；难点：串的各种基本运算。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.串类型定义2.串的表示和实现（1）定长顺序存储表示（2）堆分配存储表示（3）串的块链存储表示第五章 数组和广义表（理论学时：3学时/实践学时：2学时）（一）教学目标1.掌握数组的顺序存储和特殊矩阵的压缩存储。2.了解广义表的概念和存储结构。（二）重点、难点重点：数组的存储表示方法，顺序存储数组时数据元素之间的地址关系，特殊矩阵的压缩存储方法，稀疏矩阵的压缩存储方法，广义表的定义、性质和存储结构。难点：特殊矩阵和压缩矩阵的存

7、储表示（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.数组的定义2.数组的顺序表示和实现3.矩阵的压缩存储（1）特殊矩阵（2）稀疏矩阵4.广义表的定义5.广义表的存储结构第六章 树和二叉树（理论学时：9学时/实践学时：3学时）（一）教学目标1.熟练掌握二叉树的定义、性质、各种存储结构的特点及适用范围；2.熟练掌握二叉树的各种遍历算法；3.理解线索二叉树的概念、存储结构及线索化算法；4理解树的基本概念及其存储结构；掌握树和森林与二叉树间的转换，掌握树和森林的遍历算法； 5.掌握哈夫曼树的概念、存储结构；建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算；（二）重点、难点重点：二

8、叉树的定义、结构特点和性质，二叉树的设计和实现，二叉树存储结构的特点，先序、中序、后序遍历的递归和非递归算法，二叉树的线索化过程，最优二叉树的特性及建立最优二叉树和构造哈夫曼编码的方法。树和森林与二叉树间的转换。难点：二叉树遍历的非递归算法，二叉树的线索化算法。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.树的定义和基本术语2.二叉树（1）二叉树的定义（2）二叉树的性质（3）二叉树的存储结构3.遍历二叉树和线索二叉树（1）遍历二叉树（2）线索二叉树4.树和森林（1）树的存储结构（2）森林与二叉树的转换（3）树和森林的遍历5.赫夫曼树及其应用（1）最优二叉树（赫夫曼树）（2）

9、赫夫曼编码第七章 图（理论学时：9学时/实践学时：2学时）（一）教学目标1.理解图的基本概念，掌握图的邻接矩阵和邻接表的存储结构；2.熟练掌握图的深度优先和广度优先遍历算法；3. 掌握构造最小生成树的方法及其算法；4.掌握求拓扑排序和关键路径的方法，理解其算法；5.理解带权最短路径的概念，掌握用Dijkstra方法求最短路径的算法； （二）重点、难点重点：图的定义、术语、结构特点和性质，图的邻接矩阵、邻接表的存储结构及其构造方法，图的深度优先搜索和广度优先搜索算法，构造连通图的最小生成树算法，有向无环图的拓扑排序算法、关键路径的算法，最短路径求解中的Dijkstra算法和Floyed算法。难点

10、：图的存储结构及图的各种应用的算法。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.图的定义和术语2.图的存储结构（1）数组表示法（2）邻接表（3）十字链表（4）邻接多重表3.图的遍历（1）深度优先搜索（2）广度优先搜索4.图的连通性问题（1）无向图的连通分量和生成树（2）最小生成树5.有向无环图及其应用（1）拓扑排序（2）关键路径6.最短路径（1）从某个源点到其余各顶点的最短路径（2）每一对顶点之间的最短路径第九章 查找（理论学时：6学时/实践学时：2学时）（一）教学目标1.理解查找及其算法的时间复杂度，静态查找表的概念；2.熟练掌握顺序查找、折半查找和分块查找算法，能对其

11、性能进行分析；3.掌握二叉排序树查找算法；理解二叉平衡树，B树的概念；4.理解哈希表的含义；掌握哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法；（二）重点、难点重点：顺序查找、折半查找和分块查找算法，哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法；难点：哈希函数的构造方法，哈希表的建立和查找以及处理冲突的基本方法，各种查找算法的性能进行分析。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.静态查找表（1）顺序表的查找（2）有序表的查找（3）索引顺序表的查找2.动态查找表（1）二叉排序树和平衡二叉树（2）B-树和B+树3.哈希表（1）什么是哈希表（2

12、）哈希函数的构造方法（3）处理冲突的方法（4）哈希表的查找及其分析第十章 内部排序（理论学时：6学时/实践学时：2学时）（一）教学目标1.了解内部排序的概念；2.掌握插入类排序的算法，直接插入排序、希尔排序；3. 掌握交换类排序的算法，冒泡排序、快速排序；4. 掌握选择类排序的算法，简单选择排序、堆排序；5.了解归并排序、基数排序的算法；6.掌握各种排序方法的特点，能够对各种排序算法进行评价，并能加以灵活应用；（二）重点、难点重点：插入类排序的算法，直接插入排序、希尔排序； 掌握交换类排序的算法，冒泡排序、快速排序，掌握选择类排序的算法，简单选择排序、堆排序；难点：各种排序方法的特点，能够对各

13、种排序算法进行评价，并能加以灵活应用。（三）教学方法多媒体课件辅助教学，理论和实践结合（四）教学内容1.概述2.插入排序（1）直接插入排序（2）其他插入排序（3）希尔排序3.快速排序4.选择排序（1）简单选择排序（2）树形选择排序（3）堆排序5.归并排序6.基数排序（1）多关键字的排序（2）链式基数排序7.各种内部排序方法的比较讨论四、考核形式及成绩评定（一）考核形式：期末考试为闭卷考试，考试范围和要求应符合本教学大纲对各章教学内容的基本要求。（二）成绩评定：课程考核由平时作业及听课情况和期末考试成绩两部分组成，分别占课程总成绩的30%和70%。五、教材与参考书教 材：严蔚敏.数据结构（C语言）.（第三版）.北京：清华大学出版社，2007参考书：