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

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

Data Structure

执笔人： 编写日期：

一、课程基本信息

1. 课程编号：

2. 课程性质/类别： 必修课 / 专业主干课

3. 学时/学分： 48 学时（另实验16学时） / 4 学分

4. 适用专业：计算机科学与技术、软件工程、网络工程、信息管理与信息系统等专业

二、课程教学目标及学生应达到的能力

数据结构课程是计算机相关专业的专业基础课、必修课程，主要介绍用计算机解决一系列问题特别是非数值信息处理问题时所用的各种组织数据的方法、存储数据结构的方法以及在各种结构上执行操作的算法。通过本课程的学习，要求学生掌握各种数据结构的特点、存储表示、运算方法以及在计算机科学中最基本的应用，培养、训练学生选用合适的数据结构和编写质量高、风格好的应用程序的能力，培养学生分析问题、解决问题的能力，并为后续课程的学习打下良好的理论基础和实践基础。

三、课程教学内容与基本要求

（一）绪论（ 3 学时） 1．主要内容：

（1）介绍什么是数据结构；

（2）基本概念和术语: 数据、数据元素、数据对象，以及数据结构的定义、逻辑结构、物理结构（理解）数据类型、抽象数据类型；

（3）抽象数据类型的表示与实现；

（4）算法和算法分析: 算法的概念、算法设计的要求以及算法效率的度量。

2．基本要求

（1）了解学习数据结构的重要性；

（2）掌握数据结构的定义及相关概念和术语；

（3）了解抽象数据类型的定义、表示与实现方法；

（4）理解算法的概念、特点并掌握度量其效率的基本方法。

3．自学内容：

类C语言的书写规范。

（二）线性表（ 6 学时） 1．主要内容：

（1）线性表的抽象数据类型定义和相关概念：数据项、记录、文件等；

（2）线性表顺序存储表示和基本操作的实现；

（3）线性表的链式存储表示和基本操作的实现；

（4）稀疏多项式的抽象数据类型定义、表示和加法的实现。

2．基本要求

（1）掌握线性表的定义和特点；

（2）熟练掌握线性表的顺序存储表示和插入、删除、查找等实现算法；

（3）熟练掌握单链表、循环链表、双向链表三种链表的表示，以及单链表的查找、插入、删除、创建等实现算法。

3．自学内容： 静态链表。

（三）栈和队列（ 5 学时）

1．主要内容：

（1）栈和队列的结构特性和抽象数据类型定义；

（2）栈和队列的顺序存储表示和实现；

（3）栈和队列的链式存储表示和实现；

（4）栈和队列在程序设计中的应用。

2．基本要求

（1）掌握栈和队列两种抽象数据类型的特点；

（2）掌握栈的两种存储表示和实现，特别注意栈满栈空的条件；

（3）掌握队列的两种存储表示和实现，特别注意队满队空的条件；

（4）了解递归算法与栈的关系。

3．自学内容： 链栈，离散事件模拟

（四）串（ 3 学时） 1．主要内容：

（1）串的抽象数据类型定义；

（2）串的表示和实现: 定长顺序存储结构和堆分配存储结构；

（3）串的各种基本操作的实现及其应用；

（4）串的模式匹配操作。

2．基本要求

（1）熟悉串的一些基本操作的定义，并能利用基本操作实现串的其它操作；

（2）掌握串的定长顺序存储结构以及基本操作的实现；

（3）掌握串的堆分配存储结构以及基本操作的实现；

（4）掌握串的简单模式匹配算法，理解KMP算法。

3．自学内容： 串操作的应用实例。

（五）数组和广义表（ 4 学时） 1．主要内容：

（1）数组的抽象数据类型定义及其顺序表示和实现；

（2）特殊矩阵和稀疏矩阵的压缩存储；

（3）广义表的抽象数据类型定义和存储结构。 2．基本要求

（1）了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；

（2）掌握对特殊矩阵进行压缩存储时的下标变换公式；

（3）熟悉稀疏矩阵的三元组顺序表存储结构下的一般转置和快速转置算法；了解十字链表等存储结构；

（4）掌握广义表的结构特点、取表头表尾操作，及其存储表示方法。

3．自学内容：

采用十字链表存储结构创建稀疏矩阵。

（六）树和二叉树（ 10 学时） 1．主要内容：

（1）树的抽象数据类型定义和基本术语；

（2）二叉树的抽象数据类型定义、性质和存储结构；

（3）二叉树的遍历；

（4）线索二叉树的定义、遍历及线索化二叉树；

（5）树的存储结构、树和森林的遍历以及与二叉树的转换； （6）Huffman树及其应用。 2．基本要求

（1）掌握树型结构的特点和基本术语；

（2）熟练掌握二叉树的性质，了解相应的证明方法；

（3）了解二叉树的顺序存储结构和链式存储结构，熟练掌握二叉链表存储结构；

（4）熟练掌握二叉树三种遍历的递归算法和中序遍历非递归算法，能灵活运用遍历算法实现二叉树的其他操作；

（5）熟练掌握二叉树的线索化过程，以及在中序线索二叉树上找结点的前驱与后继的方法；

（6）熟悉树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法；

（7）了解Huffman树的特性，掌握建立Huffman树和Huffman编码的方法。

3．自学内容：

先序、后序遍历二叉树非递归算法，层次遍历二叉树算法。

（七）图（ 9 学时） 1．主要内容：

（1）图的定义和术语；

（2）图的四种存储结构：数组表示法（邻接矩阵）、邻接表、十字链表和邻接多重表；

（3）图的两种遍历策略：深度优先遍历和广度优先遍历；

（4）图的连通性和最小生成树；

（5）有向无环图及其应用：拓扑排序和关键路径；

（6）最短路径问题。

2．基本要求

（1）熟悉图的定义和术语；

（2）了解图的存储结构，熟练掌握数组表示法（邻接矩阵）和邻接表存储表示；

（3）熟练掌握图的深度优先遍历和广度优先遍历算法；

（4）掌握无向连通带权图的最小生成树求解算法；

（5）了解有向无环图、AOV网、AOE网及其在实际中的应用，熟悉拓扑排序算法和关键路径算法；

（6）熟悉两种最短路径问题求解算法。 3．自学内容：

树的先根遍历算法与图的深度优先遍历算法比较； 树的层次遍历算法与图的广度优先遍历算法比较。

（八）查找（ 4 学时） 1．主要内容：

（1）查找的基本概念和相关术语；

（2）静态查找表：顺序查找、折半查找和索引顺序表查找；

（3）动态查找表：二叉排序树的查找、插入和删除；

（4）哈希表。

2．基本要求

（1）了解查找的作用，熟悉相关术语；

（2）熟练掌握顺序查找、折半查找和索引顺序表查找；

（3）熟练掌握二叉排序树的特性、构造和查找方法；

（4）熟练掌握哈希表的构造方法，特别是哈希函数和处理冲突方法的选取；

（5）通过分析等概率下的平均查找长度来衡量各种查找方法的效率。

3．自学内容： 平衡二叉树。

（九）内部排序（ 4 学时） 1．主要内容：

（1）排序的基本概念和相关术语；

（2）插入排序：直接插入排序、折半插入排序和希尔排序；

（3）交换排序：起泡排序和快速排序；

（4）选择排序：简单选择排序和堆排序；

（5）归并排序：二路归并排序；

（6）基数排序：链式基数排序；

（7）各种内部排序方法的比较讨论。

2．基本要求

（1）了解排序作用，熟悉相关术语；

（2）掌握多种排序的基本思想、算法特点和排序过程，分析它们的时间复杂度、空间复杂度和稳定性。

3．自学内容：

二路插入排序、表插入排序和树形选择排序。 四、教学安排建议 1. 作业练习

完成每章的教学后进行布置习题，使用教材配套的《数据结构题集（C语言版）》。尽量选择基础的并且加注了标记的题，应注重于精，而不要求多。要求积极独立完成所布置的习题，建议安排至少六次。

2. 案例分析

可参考选择以下一些案例：（1）学生通讯录管理系统，（2）表达式求值问题（3）交通咨询系统，等。 3. 专题研讨

可参考选择以下一些：（1）最小生成树问题（2）航班信息查询与检索系统，（3）内部排序算法比较，等。 4. 实验安排

为了达到理论与实际应用的结合，让学生能将所学知识应用于实际问题的求解中，培养学生的实际动手能力，从而加深对概念及所学知识的理解，灵活、牢固掌握教材内容，提高程序设计及解决实际问题的能力，实验环节的安排非常重要。

建议实验安排为八次，共16学时，分别如下：

实验1 线性表的顺序存储结构的实现(2学时)

实验2 线性表的链式存储结构的实现(2学时)

实验3 栈的算法实现(2学时)

实验4 队列的算法实现 (2学时)

实验5 串类型及操作(2学时)

实验6 二叉树的建立与遍历(2学时)

实验7 图的建立与遍历(2学时)

实验8 查找与排序(2学时)

注：教师可根据教学实际情况（如：学生情况及学时情况等），适当调整实践教学内容及学时分配。 五、课程考核

1. 考核形式及成绩评定办法

本课程考核形式为：平时成绩占40%，期末考试成绩占60%。其中平时成绩的结构分包括：课堂表现10%、平时作业10%和实验20%，期末考试为闭卷笔试考试：120分钟，卷面分满分100分。期末考试成绩低于50分者，本课程成绩按不及格论处。

2. 本课程考核的基本要求

课堂表现10%：包括课堂考勤和课堂提问，如果缺课课时达到本课程教学时数的1/3，则取消考试资格。

平时作业10%：根据上交次数及完成情况进行评定。 实验20%：根据各次实验完成情况及实验报告成绩进行评定。

期末考试60%：本课程的期末考试考核内容主要包括线性表、栈与队列、串、数组与广义表、树与二叉树、图、查找和内部排序。其中，线性表、二叉树、图、查找和内部排序内容为考核的重点。 六、本课程与其它课程的先行后续关系

先行课程：《高级程序设计语言》、《离散数学》

后续课程：《操作系统》、《编译原理》、《数据库理论》、《算法分析与设计》等

七、建议教材及教学参考书

1. 教材：

严蔚敏，吴伟民编著，《数据结构（C语言版）》，清华大学出版，2012.5

严蔚敏，吴伟民编著，《数据结构题集（C语言版）》，清华大学出版，2012.5

2.参考书：

[1] 许卓群，张乃孝，杨冬青，唐世渭，《数据结构》，高等教育出版社，2004.

[2] 徐孝凯，《数据结构简明教程》，清华大学出版社，1995

[3] 陈文博，朱青，《数据结构与算法》，机械工业出版社，1996

[4] 李云清，杨庆红，揭安全编著，《数据结构》（C语言版），人民邮电出版社，2007.

[5] 杨秀金主编，《数据结构》，西安电子科技大学出版社，2002.

[6] 李廉治，姜文清，郭福顺，《数据结构》，大连理工大学出版社，1989

[7] Aho A V, Hopcroft J E, Ullman J D. Data Structures and Algorithms. Addison-Wesley Publishing Company,Inc.,1983

[8] Baron R J, Shapiro L G. Data Structures and their Implementation. Van Nostrand Reinhold Company, 1980

[9] Esakov J, Weiss T. Data Structures: An Advanced Approach Using C. Prentice-Hall, Inc.,1989

[10] [美]S巴斯《计算机算法：设计和分析引论》朱洪等译，复旦大学出版社，1985