数据结构课程教学大纲
Data Structure
学时数: 64 适用专业: 电子信息工程、电气自动化
学分数: 4.0 执笔人: 朱荣
编写日期:2017年1月课程代码：08241006
一、课程的性质和目的
本课程属于计算机电子类相关专业的重要专业基础课，系统地介绍了线性表、栈、队列、字符串、数组、树、二叉树、图、查找表等几种数据结构的基本概念，操作及其典型应用的例子。

通过本门课程的学习，使学生了解数据对象的特性，数据组织的基本方法，并初步具备分析和解决现实世界问题在计算机中如何表示和处理的能力以及培养良好的程序设计技能，为后续课程的学习和科研工作的参与打下良好的基础。

二、课程教学环节的基本要求
课堂讲授：本课程要求使用多媒体教室授课，特殊情况可在机房中采用交互式边讲边练的方式授课。

可采用教师讲授、课堂讨论、习题课等进行课堂教学。

作业方面：每章布置3～6道习题以巩固教学；安排4～6个上机实验使理论与实际相结合。

作业批改方式可采用抽改，并在课堂上（或辅导时）安排习题评讲。

考试环节：闭卷形式。

内容包括选择题，问答题，填空题，算法设计题等。

三、课程的教学内容和学时分配
第一章绪论（4学时）
教学内容：
数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义；抽象数据类型的定义、表示和实现方法；描述算法的类C语言；算法设计的基本要求以及从时间和空间角度分析算法的方法。

教学要求：
1．理解各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构之间的关系。

分清哪些是逻辑结构的性质，哪些是存储结构的性质。

2．了解抽象数据类型的定义、表示和实现方法。

3．理解类C语言的书写规范，特别要注意值调用和指针调用的区别，输入、输出的方式以及错误处理方式。

4．理解算法五个要素的确切含义
5．掌握计算语句频度和估算算法时间复杂度的方法。

重点：算法和算法分析。

难点：从时间和空间角度分析算法的方法。

第二章线性表（6学时）
教学内容：
线性表的逻辑结构定义、抽象数据类型定义和各种存储结构的描述方法；在线性表的两类存储结构（顺序的和链式的）上实现基本操作；稀疏多项式的抽象数据类型定义、表示和加法的实现。

教学要求：
1．了解线性表的逻辑结构特性：顺序存储结构和链式存储结构。

2．熟练掌握这两类存储结构的描述方法。

3．熟练掌握线性表在顺序存储结构上实现基本操作：查找、插入和删除的算法。

4．熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。

了解静态链表，能够加深对链表本质的理解。

5．能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

重点：线性表的顺序表示和实现；线性表的链式表示和实现。

难点：顺序和链式表示的实现。

第三章栈和队列（6学时）
教学内容：
栈和队列的结构特性；在两种存储结构上如何实现栈和队列的基本操作以及栈和队列在程序设计中的应用。

教学要求：
1．掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。

2．熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。

3．熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。

重点：栈和队列的表示和实现算法。

难点：栈满和栈空的条件以及它们的描述方法；循环队列的队满和队空的描述方法。

第四章串（4学时）
教学内容
串的数据类型定义；串的三种存储表示：定长顺序存储结构、块链存储结构和堆分配存储结构；串的各种基本操作的实现。

教学要求：
1．理解串的基本操作的定义，并能利用这些基本操作实现串的其他各种操作的方法。

2．熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。

3．掌握串的堆存储结构以及在其上实现串操作的基本方法。

重点：串的堆存储结构以及在其上实现串操作的基本方法。

难点：串的堆存储结构以及在其上实现串操作的基本方法。

第五章数组（2学时）
教学内容：
数组的类型定义和表示方式；特殊矩阵和稀疏矩阵的压缩存储方法及运算的实现。

教学要求：
1．了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。

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

3．了解稀疏矩阵的两种压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。

重点：对特殊矩阵进行压缩存储时的下标变换公式。

难点：对特殊矩阵进行压缩存储时的下标变换公式。

第六章树和二叉树（4学时）
教学内容：
二叉树的定义、性质和存储结构；二叉树的遍历和线索化以及遍历算法的各种描述形式；树和森林的定义、存储结构与二叉树的转换、遍历；树的多种应用。

本章是课程的重点内容之一。

教学要求：
1．熟练掌握二叉树的结构特性，了解相应的证明方法。

2．理解二叉树的各种存储结构的特点及适用范围。

3．熟练掌握各种遍历策略的递归和非递归算法，了解遍历过程中“栈”的作用和状态，并且能灵活运用遍历算法实现二叉树的其他操作。

层次遍历是按另一种搜索策略进行的遍历。

4．理解二叉树线索化的实质，熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

5．理解树的各种存储结构及其特点，掌握树和森林与二叉树的转换方法。

6．学会编写实现树的各种操作的算法。

7．了解最优树的特性，掌握建立最优树和哈夫曼编码的方法。

重点：二叉树的各种存储结构；遍历算法实现二叉树；建立哈夫曼树和编码的方法。

难点：二叉树的线索化过程；建立哈夫曼树的方法。

第七章图（2学时）
教学内容：
图的定义和术语；图的四种存储结构：数组表示法、邻接表、十字链表和邻接多重表；图的两种遍历策略：深度优先搜索和广度优先搜索；图的连通性：连通分量和最小生成树；拓扑排序和关键路径；两类求最短路径问题的解法。

教学要求：
1．理解图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。

2．熟练掌握图的两种搜索路径的遍历：遍历的逻辑定义、深度．优先搜索的两种形式（递归和非递归）和广度优先搜索的算法。

重点：图的四种存储结构；最小生成树；拓扑排序和关键路径。

难点：图的两种遍历策略；关键路径；
第八章查找（6学时）
教学内容：
讨论查找表（包括静态查找表和动态查找表）的各种实现方法：顺序表、有序表和哈希表；关于衡量查找表的主要操作—查找的查找效率和平均查找长度的讨论。

教学要求：
1．熟练掌握顺序表和有序表的查找方法。

2．熟练掌握二叉排序树的构造和查找方法。

3．掌握二叉平衡树的维护平衡方法。

4．熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构的表的实质性的差别。

重点：顺序查找；二叉排序树的构造和查找方法。

难点：二叉平衡树的维护平衡方法。

第九章内部排序（6学时）
教学内容：
概述；插入排序；交换排序(起泡排序，快速排序)；选择排序(简单选择，树形选择，堆)；归并排序；基数排序。

教学要求：
1．深刻理解排序的定义和各种排序方法的特点并能加以灵活应用。

2．了解各种方法的排序过程及其依据的原则。

3．掌握各种排序方法的时间复杂度的分析方法。

4．理解排序方法“稳定”或“不稳定”的过程及其适用场合。

5．了解“表排序”和“地址排序”的过程及其适用场合。

6．希尔排序、快速排序、堆排序、归并排序等高效方法是本章的学习重点和难点。

重点：希尔排序、快速排序、堆排序、归并排序等排序过程；各种排序方法的时间复杂度的分析方法。

难点：各种排序方法的时间复杂度的分析方法。

排序方法“稳定”或“不稳定”的过程及其适用场合。

四、实验项目与内容提要
五、本课程和其它课程的联系与分工
数据结构是一门核心专业基础课，与本专业其它专业课联系紧密，一方面它需要离散数学、线性代数、高级程序设计语言、计算机组成原理等为基础，另一方面，它为后继课程：算法设计、操作系统、数据库原理、编译原理、软件工程等提供理论及实践基础。

五、建议教材和教学参考书
建议教材:
［1］严蔚敏．《数据结构》（C语言版）．清华大学出版社.
［2］殷人昆．《数据结构》（C语言描述）．清华大学出版社.
［3］李春葆.《数据结构教程》（C语言版）．清华大学出版社.
教学参考书:
［1］严蔚敏．《数据结构题集》．清华大学出版社.
［2］刘大有．《数据结构》（C语言版）．高等教育出版社.
［3］William Ford．William Topp．《Data Structure with C++》．清华大学出版社.。