《数据结构》课程教学大纲

一、课程名称

1、中文名称：数据结构

2、英文名称：Data Structure

二、学时

总学时72学时，其中讲授54学时，实验18学时

三、开课学期

第3学期

四、课程考核要求

考试（期终考试成绩中卷面成绩占70%，实践环节成绩占30%）

五、课程概述

《数据结构》是计算机学科的一门专业基础课。通过该课程的学习使学生掌握数据结构的基本概念、基本原理和基本方法；掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析；能够运用数据结构基本原理和方法进行问题的分析与求解。

六、适用专业

计算机科学与技术专业（物联网工程方向）

七、课程教学要求和学时分配

第l章 绪论

（一）课程内容

1、数据结构的课程体系

2、基本概念和术语

3、算法和算法分析

（二）基本要求

掌握数据结构、存储结构和数据类型的基本概念及相关术语；理解算法要素的确切含义；掌握算法设计的基本要求以及分析算法的时间与空间复杂度的方法。

（三）重点难点

重点是数据与数据元素，抽象数据类型表示法，类C语言语法，渐近时间复杂度的意义、作用以及计算方法。难点是数据元素间的四种结构关系，抽象数据类型表示法，渐近时间复杂度的意义。

（四）建议学时 2学时

第2章 线性表

（－）课程内容

1、线性表的定义

2、线性表的顺序表示和实现

3、线性表的链式表示和实现

4、线性表的应用

（二）基本要求

掌握线性表的逻辑结构特性；掌握线性表的顺序存储结构和链式存储结构的描述方法及其结构特点；熟练掌握线性表在顺序存储结构和链式存储结构的结构上进行相关的查找、插入、删除等操作的算法，并且能够从时间和空间复杂度的角度综合比较两种存储结构的不同特点。

（三）重点难点

重点是线性表的定义，线性表的顺序表示和实现方法，线性链表的单链表表示及实现方法。定位结点、删除结点、插入结点操作在单链表上的实现，循环链表、双链表的结构特点，循环链表、双链表上删除与插入操作的实现。难点是线性链表的概念，线性表的顺序表示和实现方法，线性表与线性结构的联系与区别，链表与链式结构的联系与区别，指针操作，一元多项式的相加算法。

（四）建议学时 8学时

第3章 栈和队列

（－）课程内容

1、栈的定义、表示和实现

2、栈的应用举例

3、栈与递归的实现

4、队列的定义、表示与实现

5、队列的应用举例

（二）基本要求

掌握栈和队列的结构特性和描述方法；熟练掌握出栈和入栈的基本操作，以及循环队列和链队列的出队列和入队列的基本操作实现算法；熟悉栈和队列的一些典型应用实例。

（三）重点难点

重点是栈和队列的基本概念、基本算法，栈的顺序存储表示与实现方法，利用栈实现行编辑，利用栈实现表达式求值，链队列的表示与实现。难点是栈和队列的应用算法，顺序栈的溢出判断条件。

（四）建议学时 6学时

第4章 串

（－）课程内容

1、串类型的定义

2、串的表示和实现

3、串的模式匹配算法

4、串操作应用举例

（二）基本要求

掌握串的结构特性以及串的基本操作；掌握针对字符串进行操作的常用算法；熟练运用字符串处理函数。

（三）重点难点

重点是串的定义，串的表示和实现，串的模式匹配算法。难点是串的表示和实现，串的模式匹配算法。

（四）建议学时 2学时

第5章 数组与广义表

（－）课程内容

1、数组的定义

2、数组的顺序表示

3、矩阵的压缩存储

4、广义表的定义及存储结构

（二）基本要求

掌握一维数组以及多维数组的存储和表示方法；掌握对特殊矩阵进行压缩存储时的下标变换公式；了解稀疏矩阵的三元组压缩存储表示方法及适用范围；掌握稀疏矩阵的三元组表示方法及矩阵转置算法；了解广义表的定义、存储结构和基本运算。

（三）重点难点

重点是数组的定义，数组的顺序表示方法，广义表的操作及意义，矩阵的压缩存储。难点是广义表存储结构。

（四）建议学时 4学时

第6章 树和二叉树

（－）课程内容

1、树的定义和基本术语

2、二叉树定义、性质和存储结构

3、遍历二叉树和线索二叉树

4、树的存储结构

5、森林与二叉树的转换

6、树和森林的遍历

7、哈夫曼树及其应用

（二）基本要求

掌握树的基本定义及其相关术语的含义；熟练掌握二叉树的结构特性，了解相应的证明方法；熟悉三种遍历二叉树的递归算法；掌握二叉树线索化的实质及线索化的过程；掌握树、森林与二叉树的转换及其各自遍历的对应关系；掌握哈夫曼编码的原理及实现方法。

（三）重点难点

重点是二叉树的定义和逻辑特点，二叉树的基本运算，二叉树的链式存储结构的组织方式，二叉树的三种遍历方法及其算法，一般树转化为二叉树的方法，哈夫曼树及哈夫曼编码，哈夫曼编码的应用。难点是二叉树的递归定义，二叉树链式存储结构的组织方式，三种遍历的区别，哈夫曼编码。

（四）建议学时 10学时

第7章 图

（－）课程内容

1、图的定义和术语

2、图的存储结构

3、图的遍历

4、图的连通性问题

5、有向无环图及其应用

6、最短路径

（二）基本要求

掌握图的定义和术语；掌握图的两种存储结构和两种遍历策略；熟悉图的最小生成树的生成方法；掌握拓扑排序、关键路径的算法思想；掌握网络顶点之间的最短距离的计算思想。

（三）重点难点

重点是图的定义、术语及其含义，各种图的邻接矩阵表示方法，图的按深度优先搜索遍历方法和按广度优先搜索遍历方法，生成树和最小生成树的概念，Prim算法，拓扑序列和拓扑排序的概念和算法思想，关键路径的算法思想，最短路径的算法思想。难点是图的两种存储结构，关键路径、最短路径算法。

（四）建议学时 10学时

第8章 查找

（－）课程内容

1、查找的基本概念

2、顺序查找法

3、折半查找法

4、二叉排序树的构造和查找

5、平衡二叉树的定义及维护平衡的方法

6、B树及其基本操作、B+树的基本概念

7、散列（Hash）表

8、查找算法的分析及应用

（二）基本要求

掌握顺序表和有序表的查找方法；掌握查找效率的计算方法；熟练掌握二叉排序树的构造和查找方法；理解平衡二叉树的维护平衡的方法；掌握B树及其基本操作、B+树的基本概念；掌握散列函数构造方法及冲突解决方案。

（三）重点难点

重点是查找的基本概念，顺序查找、折半查找、二叉排序树的定义和查找算法，二叉平衡树的概念，B树及其基本操作、B+树的基本概念，散列表的基本思想，各种散列表的组织、解决冲突的方法。难点是二叉排序树上的插入和删除算法，平衡树、B树的建立，平衡二叉树的旋转平衡算法，散列表上的有关算法。

（四）建议学时 6学时

第9章 排序

（一）课程内容

1、排序的基本概念

2、插入排序

3、快速排序

4、选择排序

5、归并排序

6、基数排序

7、外部排序

8、各种排序方法的比较

9、排序算法的应用

（二）基本要求

掌握排序的定义和各种排序方法的基本思想及其特点；理解各种排序方法的排序过程及其依据的原则；掌握快速排序和堆排序等方法；能够进行各种排序方法的时间复杂性分析。

（三）重点难点

重点是排序的基本概念，直接插入排序、快速排序、选择排序、 归并排序 、基数排序、最佳归并树的思想和算法。难点是快速排序算法，堆排序算法。

（四）建议学时 6学时

八、教材主要参考资料

1、《数据结构（C语言版）》，严蔚敏等，清华大学出版社

2、《数据结构教程》（第3版），李春葆等，清华大学出版社

3、《数据结构与算法》，Sartaj Sahni著，汪诗林等译，机械工业出版社

4、《数据结构题集》，严蔚敏等，清华大学出版社

5、《数据结构习题与解析》，李春葆，清华大学出版社