《数据结构》教学大纲

1、数据结构（Data Structure）课程代码：2131034学分：4学时：64（其中：课程教学学时：48，实验学时：16）先修课程：计算机科学与技术专业导论、程序设计基础适用专业：计算机科学与技术教材：数据结构（C语言版），严蔚敏，吴伟民编著，清华大学出版社，2016年7月第 1 版第45次印刷开课学院：计算机与软件学院一、课程性质与课程目标（一）课程性质数据结构是高等工科院校计算机类相关专业的一门重要学科基础必修课。本课程主要研究各种数据的抽象表示、实现方法、算法的设计过程以及算法的分析，是计算机软件设计的重要理论和实践基础课程。（二）课程目标课程目标包括知识目标和能力目标，具体如下：课

2、程目标1：使学生掌握数据结构的基本概念和基本理论，熟悉合理组织数据的基本方法，培养学生解决计算机领域复杂工程问题所需专业基础知识，为本专业后续课程的学习以及进一步的软件开发打下良好的理论基础；课程目标2：能够运用计算思维分析问题和解决问题，针对计算机领域复杂工程问题，分析并抽象出涉及的数据元素以及它们内在的逻辑关系；课程目标3：能够综合运用数据结构的基本理论和设计方法，针对计算机领域复杂工程问题研究和设计可行的解决方案，并能对解决方案进行分析和论证。（三）课程目标与专业毕业要求指标点的对应关系本课程支撑专业培养计划中的毕业要求指标点1.2、2.2和3.2。毕业要求指标点1.2：具备扎实的计算机

3、工程基础知识，了解通过计算机解决复杂工程问题的基本方法，并遵循复杂系统开发的工程化基本要求；毕业要求指标点2.2：应用计算机领域专业知识，能够根据给出的实际工程案例，运用草稿、图表、流程表等工程方法发现问题、提出问题及分析问题；毕业要求指标点3.2：能够合理地组织数据，有效地存储和处理数据，正确地进行算法设计、分析和评价。课程目标毕业要求指标点课程目标1课程目标2课程目标3毕业要求1.2毕业要求2.2毕业要求3.2二、课程内容及教学要求本课程教学内容包括：线性表、栈和队列、数组、树和二叉树、图等常见的数据结构，讨论各种典型查找算法、内部排序算法以及算法分析的基本方法。本课程基本要求是：从数据的

4、逻辑结构、存储结构和运算三个方面理解并掌握线性表、栈、队列、数组、树和图等常用的数据结构；了解在各种常用的数据结构上实现的排序和查找运算；对算法的时间和空间复杂度有一定的分析能力；针对常见的应用问题，能选择合适的数据结构及设计有效的算法解决问题。第1章绪论教学内容1. 数据结构的定义；2. 基本概念和术语（数据、数据元素、数据项、数据对象、数据结构）；3. 抽象数据类型的表示与实现（ADT的三要素）；4.算法和算法分析（算法的定义及其五个特性；算法评价的标准；算法效率的度量）。（二）教学要求1.了解数据结构的三个方面：逻辑结构、存储结构、运算；2. 理解抽象数据类型的概念；3. 理解算法的概念

5、和特性；4. 掌握算法的描述方法；5. 了解算法分析的内容；6. 掌握算法时间复杂度的分析方法。（三）重点与难点1. 重点数据结构三方面含义、算法的伪码描述方法、简单算法的时间复杂度分析。2. 难点算法的伪码描述、算法的时间复杂度分析。第2章线性表（一）教学内容线性表的定义、相关概念（前驱、后继、表长、位序、空表等）、线性表的抽象数据结构类型定义；线性表的顺序表示和运算实现；顺序表的插入和删除操作的实现方法；线性链表的有关概念：头结点、结点、数据域、指针域、指针（链）；线性链表的存储结构、插入和删除操作的实现方法及其时间复杂度分析；循环链表的存储结构以及插入和删除操作的实现方法及其时间复杂度分

6、析。（二）教学要求 1. 理解线性表的基本概念，线性表有关的术语，线性表的特性；2. 熟悉线性表的抽象数据类型定义；3. 掌握线性表的顺序存储表示及实现；4. 掌握线性表的链接存储表示及实现；5. 了解线性表的应用。（三）重点与难点1.重点熟练掌握顺序表和单链表上的各种基本算法及相关的时间复杂度分析。2.难点双向循环链表的插入、删除以及算法时间复杂度的分析。第3章栈和队列教学内容1. 栈的有关概念：栈、栈顶、栈底、空栈的定义；2. 栈的“后进先出”特点；3. 栈的抽象数据类型定义；4. 栈的表示和实现：顺序栈和链栈；5. 栈的应用举例：数制转换、括号匹配的检验、表达式求值（应用栈实现表达式求值

7、的过程）；6. 队列的定义及有关概念，队列的“先进先出”特点，队列的抽象数据类型定义；7. 链队列队列的链式表示和实现；8. 循环队列队列的顺序表示和实现：循环队列的存储结构，循环队列的插入和删除操作实现。（二）教学要求1. 理解栈的基本概念，栈有关的术语，栈的特性；2. 熟悉栈的抽象数据类型定义；3. 掌握栈的顺序存储表示及实现和栈的链接存储表示及实现；4. 掌握栈的应用；5. 理解队列的基本概念，队列有关的术语，队列的特性；6.熟悉队列的抽象数据类型定义；7.掌握队列的顺序存储表示及实现和队列的链接存储表示及实现；8.了解队列的应用（三）重点与难点1.重点顺序栈及其运算的实现、栈的简单应用

8、、循环队列的插入和删除实现。2.难点循环队列的概念以及循环队列的插入和删除实现。第4章字符串（一）教学内容1. 串的定义，串长、空串、子串、主串、位置、相等、空格串等概念。常用串运算，串的抽象数据类型定义；2. 串的表示和实现；（1）定长顺序存储表示（2）堆分配存储表示（3）串的块链存储表示3. 串的模式匹配算法。（二）教学要求1. 理解串的基本概念，串有关的术语，串的特性；2. 熟悉串的抽象数据类型定义；3. 掌握串的存储表示及实现；4. 理解串的模式匹配运算；5. 掌握朴素的模式匹配算法。（三）重点与难点1.重点串的常用运算含义、串的顺序存储表示。2.难点串的模式匹配运算。第5章数组和广义

9、表（一）教学内容1. 数组的抽象数据结构类型定义；2. 一维数组的顺序存储表示，二维数组的顺序存储表示：以行序存储和以列序存储；数组中存储元素和修改元素值的操作；3. 矩阵的压缩存储：对称矩阵的压缩存储；稀疏矩阵的抽象数据类型定义，稀疏因子的定义，稀疏矩阵压缩存储的实现方法：三元组顺序表；十字链表。（二）教学要求1. 理解数组的定义，数组的顺序表示和实现；2. 了解对称矩阵、三角矩阵、稀疏矩阵的压缩存储；3. 了解广义表的定义，广义表的链式存储结构。（三）重点与难点1.重点数组的存储表示、对称矩阵和稀疏矩阵的压缩存储。2.难点稀疏矩阵的压缩存储。第6章树和二叉树（一）教学内容树的抽象数据类型定

10、义。结点、结点的度、叶子（终端结点）、分支结点（非终端结点）、树的度、双亲、孩子、兄弟、祖先、子孙、深度、有序树、无序树和森林等术语的定义；二叉树的抽象数据类型定义；二叉树的5个性质；满二叉树和完全二叉树的概念；二叉树的存储结构：顺序存储结构、链式存储结构；遍历二叉树：先序遍历、中序遍历、后序遍历的概念及递归算法；树的存储结构：双亲表示法、孩子表示法、孩子兄弟表示法；森林与二叉树的转换；赫夫曼树及其应用：路径长度、树的路径长度、树的带权路径长度、最优二叉树（赫夫曼树）的定义；赫夫曼编码算法。（二）教学要求1. 理解树的基本概念，树有关的术语，树的特性；2. 熟悉树的抽象数据类型定义；3. 熟悉

11、树的抽象数据类型定义；4. 理解二叉树的基本概念，二叉树有关的术语，二叉树的特性；5. 熟悉二叉树的抽象数据类型定义；6. 掌握二叉树的顺序与链接存储表示；7. 掌握二叉树的遍历运算及实现；8. 了解线索二叉树；9掌握赫夫曼（Huffman）树及其应用；10. 了解森林与二叉树的转换；11. 了解树和森林的遍历。（三）重点与难点1.重点二叉树的存储表示、二叉树的遍历算法、赫夫曼算法、赫夫曼编码。2.难点赫夫曼算法、赫夫曼编码。第7章图（一）教学内容1. 基本概念及术语：顶点、弧（弧头、弧尾）、有向图、无向图、完全图、网、子图、度（出度、入度）、路径、回路（环）、简单回路、连通图（强连通图）、连

12、通分量（强连通分量）等；2. 图的存储结构：数组表示法（邻接矩阵）；邻接表；3. 图的遍历：深度优先、广度优先；4. 图的连通性问题：最小生成树的定义；构造最小生成树的算法（Prim算法和Kruskal算法）。5. 有向无环图及其应用：拓扑排序、关键路径；6. 最短路径：从某个源点到其余各顶点的最短路径（Dijkstra算法）。（二）教学要求1. 理解图的基本概念，图有关的术语，图的特性；2. 熟悉图的抽象数据类型定义；3. 掌握图的邻接矩阵、邻接表存储表示；4. 掌握图的深度优先遍历、广度优先遍历算法；5. 掌握以下图的基本应用及其复杂度分析：最小（代价）生成树、最短路径、拓扑排序、关键路径

13、。（三）重点与难点1.重点图的存储表示、图的遍历算法、最小生成树算法、关键路径算法。2.难点最小生成树算法，最短路径算法。第8章查找（一）教学内容1. 顺序查找的过程、算法以及性能分析；平均查找长度的定义；2. 有序表的折半查找过程、算法以及性能分析；3. 索引顺序表的查找过程、算法以及性能分析；4. 二叉排序树的定义及查找过程；二叉排序树的插入和删除；二叉排序树的查找分析；平衡二叉树（AVL树）、平衡因子的定义及平衡二叉树的构造过程；平衡树查找的分析；5. B-树的定义；6. 哈希表：基本概念：哈希（Hash）函数、冲突、同义词、哈希表、散列、哈希地址（散列地址）等；哈希函数的构造要求、除留

14、余数法；处理冲突的方法：开放地址法、链地址法；哈希表的查找及其分析。（二）教学要求1. 理解查找的定义及相关概念；2. 掌握静态查找表：顺序表的查找，有序表的查找，索引顺序表的查找；3. 掌握动态查找表：二叉排序树，平衡二叉树；4. 了解B-树；5.掌握哈希表及其查找。（三）重点与难点1.重点顺序查找、折半查找、二叉排序树及其建立、二叉排序树查找、AVL树建立过程分析、AVL树的查找及ASL分析、哈希表的建立、哈希表查找及ASL分析。2.难点AVL树建立过程。第9章内部排序（一）教学内容1. 排序的定义；排序方法的时间和空间特性、稳定性；2. 插入排序：直接插入排序、希尔排序；3. 快速排序；

15、4. 选择排序：堆排序；5. 归并排序；6. 各种内部排序方法的比较。（二）教学要求1. 理解排序的定义及相关概念；2. 掌握常用的排序方法：直接插入排序，二分法插入排序，直接选择排序，冒泡排序，希尔排序，快速排序，堆排序，归并排序，基数排序；3. 理解各类内部排序方法的特点：时间复杂度，空间复杂度，稳定性。（三）重点与难点1.重点希尔排序、快速排序、堆排序和归并排序。2.难点快速排序、堆排序以及各类内部排序方法的比较。三、本课程开设的实验项目编号实验项目名称学时类型要求支撑的课程目标1线性表的存储表示及实现2验证性必做课程目标12栈的应用(数制转换及回文判断)2验证性必做课程目标13串的应用

16、（串的联接和模式匹配）2验证性必做课程目标14二叉树的遍历2验证性必做课程目标1，25赫夫曼树及其应用2设计性必做课程目标1，2，36图的建立与遍历2验证性必做课程目标1，27顺序查找与二分法查找的实现与比较2验证性必做课程目标2，38快速排序算法2验证性必做课程目标2，3实验1：线性表的存储表示及实现1. 实验目的及要求1）掌握线性表的顺序存储表示及实现；2）掌握线性表的链接存储表示及实现；3）理解线性表的逻辑结构和两种存储结构；4）能够应用线性表解决实际问题，并能分析其时间复杂度。2. 实验主要内容1）自行建立两个有序的顺序表，然后将其合并成一个新的有序表；2）自行建立两个有序的单链表，然

17、后将其合并成一个新的有序单链表；3）分别分析有序的顺序表合并和有序的单链表合并的算法时间复杂度。3. 重难点有序单链表的创建与合并，合并算法复杂度的分析。实验2：栈的应用1. 实验目的及要求1) 了解栈的定义及特点；2）掌握顺序栈的实现；3）掌握栈的简单应用。2. 实验主要内容1）建立能够存放十进制整数的顺序栈空栈；2）利用栈的特性完成数制转换（十进制数转成二进制数、八进制数和十六进制数）；3）建立能够存放字符的顺序栈空栈；4）利用栈的特性对输入的字符串完成是否为回文的判断；5）分别对上述两个算法完成算法时间复杂度的分析。3. 重难点利用栈的特性对输入的字符串完成是否为回文的判断。实验3：串的

18、应用（字符串的联接和字符串的模式匹配）1. 实验目的及要求1) 了解串的三种存储结构；2）掌握串的定长顺序存储结构；3）掌握串的简单模式匹配算法并分析该算法的时间复杂度。2. 实验主要内容1）采用定长顺序存储结构存储两个长度不超过255的字符串；2）将上述两个字符串联接起来作为主串S；3）采用定长顺序存储结构存储一个长度不超过255的字符串作为模式子串T；4）采用简单模式匹配算法，对主串S，从它的第pos个字符起和模式串T比较，如果模式串中的每个字符都和主串S中的字符序列匹配成功，则返回主串的pos；5）分别对上述两个算法（串的联接和串的模式匹配）完成算法时间复杂度的分析。3. 重难点定长顺序

19、存储的两个串联接时的各种情况分析；匹配不成功时主串应回溯到的位置分析。实验4：二叉树的遍历1. 实验目的及要求1) 了解二叉树的定义和递归的思想；2）掌握二叉树的链式存储结构：二叉链表；3）掌握二叉树的5个基本性质；4）掌握建立二叉树的基本算法；5）掌握二叉树的三种遍历算法。2. 实验主要内容1）对给定的二叉树补足空结点（度为1的结点只需补1个空结点；度为0的结点需要补2个结点；度为2的结点不需要补空结点）；2）对补充过空结点的二叉树进行先序遍历（空结点用#表示）；3）根据先序遍历的结果，递归建立二叉树；4）分别用递归和非递归的算法中序遍历该二叉树，输出中序遍历的结果（不包含空结点）；5）分别

20、对上述算法完成算法时间复杂度的分析。3. 重难点根据先序遍历的结果，递归建立二叉树。实验5：赫夫曼树及其应用1. 实验目的及要求1) 了解最优二叉树的定义及特点；2）掌握赫夫曼树的构造过程；3）掌握赫夫曼编码。2. 实验主要内容1）根据输入的一串电文字符，分别统计各个字符在电文中出现的频率；2）根据各个字符在电文中出现的频率建立赫夫曼树；3）为赫夫曼树上的每个叶子结点实现赫夫曼编码，并输出该编码；4）对Huffman编码生成的代码串进行译码，输出电文字符串。3. 重难点建立赫夫曼树，求每个字符的赫夫曼编码。实验6：图的建立与遍历1. 实验目的及要求1) 理解并掌握图的逻辑结构和物理结构邻接矩阵

21、、邻接表；2）以邻接表为存储结构，掌握无向图的基本操作和实现方法；3）掌握图的深度优先遍历和广度优先遍历算法；4）能够对上述算法进行时间复杂度分析。2. 实验主要内容1）以邻接表为存储结构，根据输入的顶点数、边数、顶点信息、边的权值等信息构造一个无向图G；2）深度优先遍历图G，将从键盘输入的顶点作为起始点，输出深度优先遍历的顶点序列；3）广度优先遍历图G，将从键盘输入的顶点作为起始点，输出广度优先遍历的顶点序列；4）分别对深度优先遍历和广度优先遍历两个算法完成算法时间复杂度的分析；3. 重难点用邻接表的存储结构完成图的构造。实验7：顺序查找与二分法查找的实现与比较1. 实验目的及要求1）掌握顺

22、序查找的过程、算法以及性能分析；2）了解平均查找长度的定义，掌握平均查找长度的计算方法；3）掌握二分法查找的过程、算法以及性能分析。2. 实验主要内容1）采用顺序表结构存放查找数据，关键字类型为整型；2）采用哨兵法完成顺序查找，计算平均查找长度；3）对上述顺序表中的数据进行排序；4）利用二分查找法完成查找，计算平均查找长度；5）分别对上述两个算法完成算法时间复杂度的分析，对比二者的查找效率。3. 重难点计算二分法查找的平均查找长度。实验8：快速排序算法1. 实验目的及要求1）理解内部排序的定义及相关概念；2）掌握常用的排序算法快速排序的实现；3）掌握排序算法的时间复杂度分析过程以及稳定性分析。

23、2. 实验主要内容1）建立能够存放n个十进制整数的顺序表；2）随机选定其中一个元素作为枢轴；3）根据枢轴，进行一趟快速排序，将原数列划分成两个待排序序列；4）分别递归对两个子序列进行快速排序；5）对快速排序算法完成算法时间复杂度和稳定性分析；3. 重难点快速排序的思想和算法时间复杂度分析。注：本课程为专业课，授课对象为大二学生，实验类型主要包括验证性和设计性实验，均需要提交实验报告，实验报告主要包括实验目的、实验内容、预习内容、实验步骤、算法的时间复杂度分析以及总结。实验评价内容和评分细则参见附录1。四、学时分配及教学方法章教学形式及学时分配主要教学方法支撑的课程目标课堂教学实验上机课程实践小

24、计第一章绪论44讲授、案例、演示课程目标1， 2第二章线性表628讲授、案例、自学、实验课程目标1， 2第三章栈和队列628讲授、对比、自学、讨论、实验课程目标1， 2， 3第四章串224讲授、演示、自学、实验课程目标1， 2第五章数组22讲授、自学课程目标1， 2第六章树和二叉树8412讲授、案例、演示、讨论、自学、实验课程目标1， 2， 3第七章图8210讲授、案例、演示、讨论、自学、实验课程目标1， 2， 3第八章查找628讲授、案例、演示、实验课程目标1， 2， 3第九章内部排序628讲授、案例、演示、实验课程目标1， 2， 3合计481664注：1.课程实践学时按相关专业培养计划列入表格； 2.主要教学方法包括讲授法、讨论法、演示法、研究型教学方法（基于问题、项目、案例等教学方法）等。五、课程考核 1. 课程考核方式包括期末考试、平时作业和实验情况考核。考核形式考核要求考核权重备注平时作业及阶段测试课后完成1015个习题，主要考核学生对每节课知识点的复习、理解和掌握度，计算全部作业的平均成绩再按15%计入总成绩；可让学生查阅资料，了解本课程相关技术发展情况，自主学习并完成。15%根据平时作业得分取平均值或结