《数据结构》教学大纲
来源：
发布时间：
2006-5-29 16:56:06
点击：
（一）课程性质与任务
数据结构是计算机及应用专业中一门重要的专业基础课程，在计算机软件的各个领域中均会使用到数据结构的有关知识。当用计算机来解决实际问题时，就要涉及到数据的表示及数据的处理，而数据表示及数据处理正是数据结构课程的主要研究对象，通过这两方面内容的学习，为后续课程，特别是软件方面的课程打开厚实的基础。因此，数据结构课程在计算机应用专业中具有举足轻重的作用。
本课程的任务是：在基础方面，要求学员掌握常用数据结构的基本概念及其不同的实现方法；在技能方面，通过系统学习能够在不同存储结构上实现不同的运算，并对算法设计的方式和技巧有所体会。总言之，使应用者较全面的掌握各种常用的数据结构，提高运用数据结构解决实际问题的能力。
（二）与其它课程的关系
学习本课程必须具备高级语言程序设计（如C语言）的基础知识与基本技能。它的后续课程为操作系统、数据库原理等。
数据结构中存储结构及基本运算的实现需要程序设计的基本知识和编程的经验及能力，本课程的大部分实例均是用C语言实现的，故要求较熟练地掌握C语言。
（三）教材与参考书
教材：《数据结构》经济科学出版社，2000年，黄刘生主编
参考书：《数据结构》第二版，中国科学技术大学出版社，2000年，黄刘生、唐策善编
《数据结构》第二版，清华大学出版社，1992年，严蔚敏、吴伟民编
《数据结构》，高等教育出版社，1987年，许卓群等编
（四）课程要求
第1章 概论
介绍数据结构中常用的基本概念和术语以及学习数据结构的意义，要求了解各种基本概念和术语，掌握算法描述和分析的方法。了解数据结构的逻辑结构、存储结构及数据的运算三方面的要领及相互关系。算法复杂度的分析方法。
1.数据、数据元素、数据项、数据结构等基本概念。数据结构的逻辑结构、存储结构及数据运算的含义及其相互关系。数据的两大类逻辑结构和四种常用的存储表示方法。
2.数据结构在各种软件系统中所起的作用。选择合适的数据是解决应用问题的关键步骤。
3.算法、算法的时间复杂度和空间复杂度、最坏的和平均的时间复杂度等概念。算法的时间复杂度不仅仅依赖于问题的规模，也取决于输入实例的初始状态。算法描述和算法分析的方法，对于一般算法能分析出时间复杂度。
第2章 线性表
介绍线性表的逻辑结构和各种存储表示方法，以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。要求在熟悉这些内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存诸结构设计出相应的有效算法，解决与线性表相关的实际问题。熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析，能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。
1.线性表的逻辑结构特征，线性表上定义的基本运算，并能利用基本运算构造出较复杂的运算。
2.顺序表的含义及特点，即顺序表如何反映线性表中元素之间的逻辑关系。顺序表上的插入删除操作及其平均时间性能分析。利用顺序表设计算法解决简单的应用问题。
3.链表如何表示线性表中元素之间的逻辑关系。链表中头指针和头结点的使用。单链表、双链表、循环链表链接方式上的区别。单链表上实现的建表、查找、插入和删除等基本算法，并分析其时间复杂度。循环链表上尾指针取代头指针的作用，以及单循环链表上的算法与单链表上相应算法的异同点。双链表的定义及其相关的算法。利用链表设计算法解决简单的应用问题。
4.顺序表和链表的主要优缺点。针对线性表上所需要执行的主要操作，知道选择顺序表还是链表作为其存储结构才能取得较优的时空性能。
第3章 栈和队列
介绍栈和队列的逻辑结构定义及在两种存储结构上如何实现栈和队列的基本运算。要求在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。掌握栈和队列在两种存储结构上实现的基本运算，循环队列中对边界条件的处理。
1.栈的逻辑结构特点，栈与线性表的异同。顺序栈和链栈上实现的进栈、退栈等基本算法。栈的"上溢"和"下溢"的概念及其判别条件。利用栈设计算法解决简单的应用问题。
2.队列的逻辑结构特点，队列与线性表的异同。顺序队列（主要是循环队列）和链队列上实现的入队、出队等基本算法。队列的"上溢"和"下溢"的概念及其判别条件。使用数组实现的循环队列取代普通的顺序队列的原因。循环队列中对边界条件的处理方法。利用队列设计算法解决简单的应用问题。
3.栈和队列的特点，什么样的情况下能够使用栈或队列。
第4章 串
介绍串的逻辑结构、存储结构及其串上的基本运算，C语言及其它高级语言均已具备了较强的串处理功能，掌握串上实现的模式匹配算法。
1.串的有关概念及基本运算。串与线性表的关系。
2.串的两种存储表示。串上实现的模式匹配算法及其时间性能分析。使用C语言提供的串操作函数构造与串相关的算法解决简单的应用问题。
第5章 多维数组和广义表
介绍多维数组的逻辑结构特征及其存储方式，特殊矩阵和稀疏矩阵的压缩存储方法及广义表的概念，要求学员熟悉这些内容。熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算，稀疏矩阵的压缩存储表示下实现的算法。
1.多维数组的逻辑结构特征。多维数组的顺序存储结构及地址计算方式。数组是一种随机存取结构的原因。
2.特殊矩阵和稀疏矩阵的概念。特殊矩阵和压缩存储时的下标变换方法。稀疏矩阵的三元组表表示方法及有关算法。
3.广义表的有关概念及其与线性表的关系。广义表的括号表示和图形表示之间的转换。求给定的非空广义表的表头和表尾运算。
第6章 树
介绍二叉树的定义、性质、存储结构、遍历、线索化、树的定义、存储结构、遍历、树和森林与二叉树的转换，哈夫曼树及哈夫曼编码等内容。要求在熟悉这些内容的基础上，掌握二叉树的遍历算法及其有关应用，使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。
1.树的逻辑结构特征。树的不同表示方法。树的常用术语及含义。
2.二叉树的递归定义及树与二叉树的差别。二叉树的性质，了解相应的证明方法。二叉树的两种存储方法、特点及适用范围。
3.二叉树的三种遍历算法，理解其执行过程。确定三种遍历所得到的相应的结点访问序列。以遍历算法为基础，设计有关算法解决简单的应用问题。
4.二叉树线索化的目的及实质。在中序线索树中查找给定结点的中序前趋和中序后继的方法。查找给定结点的前趋和后序后继并非有效的原因。
5.树和森林与二叉树之间的转换方法。树的各种存储结构及其特点。树的两种遍历方法。
6.最优二叉树和最优前缀码的概念及特点。哈夫曼算法的思想。根据给定的叶结点及其权值构造出相应的最优二叉树。根据最优二叉树构造对应的哈夫曼编码。
第7章 图
介绍图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法，要求学员在熟悉这些内容的基础上，掌握在图的两种存储结构上实现的遍历算法。图的应用算法：求最小生成树，求最短路径以及拓扑排序，只要求学员掌握这些算法的基本思想及时间性能。
1.图的逻辑结构特征。图的常用术语及含义。
2.邻接矩阵和邻接表这两种存储结构的特点及适用范围。根据应用问题的特点和要求选择合适的存储结构。
3.连通图及非连通图的深度优先搜索和广度优先搜索两种遍历算法，其执行过程以及时间分析。
4.生成树的最小生成树的概念。对遍历给定的图，画出深度优先和广度优先生成树或生成森林。Prim和Kruskal算法的基本思想、时间性能及这两种算法各自的特点。要求对给定的连通图，根据Prim和Kruskal算法构造出最小生成树。
5.最短路径的含义。求单源最短路径的Dijkstra算法的基本思想和时间性能。对于给定的有向图，根据Dijkstra算法画出求单源最短路径的过程示意图。
6.拓扑排序的基本思想和步骤。拓扑排序不成功的原因。对给定的有向图，若拓扑序列存在，则要求写出一个或多个拓扑序列。
第8章 排序
介绍五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。要求在熟悉这些内容的基础上，掌握快速排序、堆排序、归并排序和基数排序的基本思想及排序过程，以及这四个排序算法的实现。
1.排序在数据处理中的重要性。排序方法的"稳定"性含义。排序方法的分类及算法好坏的评判标准。
2.直接插入排序中的基本思想和算法实现，以及在最好、最坏和平均情况下的时间性能分析。直接插入排序中哨兵的作用。针对给定的输入实例，要能写出直接插入排序的排序过程。
3.冒泡排序的基本思想。快速排序的基本思想和算法实现，以及在最坏和平均情况下的时间性能分析，了解算法的稳定性。基准元素（划分元）对划分是否平衡的影响。针对给定的输入实例，能写出快速排序的排序过程。
4.堆、小根椎 、大根堆、堆顶等有关概念和定义。堆性质及堆与完全二叉树的关系。直接选择排序和堆排序的基本思想和算法实现，以及时间性能分析。针对给定的输入实例，写出堆排序的排序过程。
5.归并排序的基本思想和算法实现，以及时间性能分析。针对给定的输入实例，能写出归并排序的排序过程。
6.箱排序和基数排序的基本思想和算法实现，以及时间性能分析。针对给定的输入实例，能写出箱排序和基数排序的排序过程。分配排序与其它几类排序的区别。
7.通过对被排序的记录数目、记录信息量的大小、关键字的结构及初始状态、稳定性要求、辅助空间的大小、各种时间性能等方面的比较掌握各种排序的优缺点。根据实际问题的特点和要求选择合适的排序方法。
第9章 查找
介绍线性表、树和散列表的查找方法、算法实现以及各种查找方法的时间性能（平均查找长度）分析。要求学员在熟悉这些内容的基础上，掌握顺序查找、二分查找，二叉查找树上查找以及散列表上查找的基本思想和算法实现。二叉查找树的删除算法及B-树上的插入和删除算法。
1.查找在数据处理中的重要性。查找算法效率的评判标准。
2.顺序查找、二分查找、分块查找的基本思想、算法实现和查找效率分析。顺序查找中哨兵的作用。二分查找对存储结构及关键字的要求。通过比较线性表上三种查找方法的优缺点，能根据实际问题的要求和特点，选择出合适的查找方法。
3.二叉查找树和B-树的定义和特点以及用途。二叉查找树的插入、删除、建树和查找算法及时间性能。建立一棵二叉查找树的过程实质上是对输入实例的排序过程，输入实例对所建立的二叉查找树形态的影响。B-树的插入、删除及查找方法的基本思想，查找效率。
4.散列表、散列函数、散列地址和装填因子等有关概念。散列函数的选取原则及产生冲突的原因。几种常用的散列函数构造方法。两类解决冲突的方法及其优缺点。产生"堆积"现象的原因。采用线性控测法和拉链法解决冲突时，散列表的建表方法、查找过程以及算法实现和时间分析。散列表和其它表的本质区别。
第10章 文件
介绍存储在外存上的数据结构（即文件）的有关概念、各种文件的特点、组织方法及查询和更新操作，要求对这些内容做一般性的了解。
1.文件的有关概念。文件的逻辑结构及其操作。文件的存储结构（组织方式）分类。评价文件组织效率的标准。
2.顺序文件的特点及外存种类的适应性。顺序文件上各种查找方法的基本思想及对外存种类的要求。
3.索引文件的组织方式和特点。索引文件的查询和更新操作的基本思想。
4.索引顺序文件是最常用的一种文件组织方式的原因。两种最常用的索引顺序文件（ISAM文件和VSAM文件）的组织方式和特点。在ISAM文件和VSAM文件上查询和更新操作的基本思想。
5.散列文件的组织方式和特点。散列文件的查询和更新操作的基本思想。
6.多关键字文件与其它文件的区别。多重表文件和倒排文件的组织方式和特点。多重表文件和倒排文件上查询及更新操作的基本思想。
