《数据结构与算法》教学大纲

1、 数据结构与算法教学大纲前言数据结构与算法课程是计算机相关专业高等教育的专业基础课程。是计算机程序设计的重要理论技术基础，它对理论和实践的要求都相当高，且内容较多。作为数学与计算科学学院信息与计算专业的必修课，基本内容以计算机系的专业技术基础课-数据结构的内容为主，根据信息专业的特点，在内容和难度上有所取舍。学习本课程所讨论的知识内容和提倡的技术方法和思路，无论对进一步学习计算机领域的其他课程，还是对从事软件工程的开发，都有着不可替代的作用。本课程设置的目的是：要培养学生的数据抽象能力，学会分析研究计算机加工的数据结构的特性，以便为信息的加工和处理选择适当的逻辑结构、存储结构及实现应用的适当算

2、法，并掌握分析算法的时间和空间复杂度的技术。学习本课程的要求是：通过本课程的学习，要求学生了解数据结构及其分类、数据结构与算法的密切关系；熟悉各种基本数据结构及其操作，学会根据实际问题要求来选择数据结构；掌握设计算法的基本步骤和算法分析方法；掌握数据结构在排序和查找等常用算法中的应用。先修课程要求：计算机基础、C语言、离散数学本课程计划总学时90学时，4学分，其中理论54学时，实验课36学时。选用教材：1严蔚敏、吴伟民编著，数据结构（C语言版），清华大学出版社，1999年2严蔚敏、吴伟民编著，数据结构题集，清华大学出版社教学手段：多媒体教学考核方法：考试教学进程安排表周次周学时教学主要内容教学

3、环节备注13第一章绪论2.1线性表的类型定义讲课232.2线性表的顺序存储结构讲课332.3线性表的链式表示和实现讲课433.1栈3.2栈的应用举例讲课533.4队列习题讲课习题课63第四章串5.1数组的定义5.2数组的顺序表示和实现讲课735.3矩阵的压缩存储5.4广义表的定义6.1树的定义和基本术语6.2二叉树讲课836.3遍历二叉树和线索二叉树讲课936.4树和森林6.6哈夫曼树及其应用讲课1037.1图的定义和术语7.2图的存储结构讲课1137.3图的遍历7.4图的连通性问题讲课1237.5有向图五环图及其应用习题讲课习题课1339.1静态查找表9.2动态查找表讲课1439.3哈希表讲

4、课15310.1概述10.2插入排序10.3快速排序讲课16310.4选择排序10.5归并排序10.7各种排序方法综合比较讲课173习题习题课183复习讨论第一章绪论一、学习目的本章主要介绍了数据结构的一些基本概念和算法分析的一般方法。具体包括数据、数据元素、数据的逻辑结构、物理结构、算法等和类C语言的书写规范。通过本章的学习，使学生领会数据、数据元素和数据的概念及气相互关系，掌握数据结构的逻辑结构、存储结构的联系与区别，了解算法时间复杂度和空间复杂度的分析。掌握类C语言的书写要求。本章计划理论2学时。二、课程内容1.1-1.2数据结构的基本概念和术语数据、数据结构、数据的物理结构、数据的逻辑

5、结构、数据类型、抽象数据类型1.3抽象数据类型的表示与实现类C语言的书写规范与应用1.4算法描述和算法分析算法算法设计的要求算法效率的度量时间复杂度分析、语句频度算法的存储空间的要求三、重点、难点提示和教学手段重点难点：数据结构相关的基本概念尤其是数据的逻辑结构、存储结构和算法之间的关系；抽象数据类型的定义、表示和实现；计算语句频度和估算算法时间复杂度。教学手段讲授四、思考与练习习题集1.1，1.2，1.3，1.8，1.9，1.10第二章 线性表一、学习目的通过本章的学习，要求学生掌握线性表的逻辑结构特性及这种关系在计算机中的不同表示形式。熟练掌握顺序存储的线性表和单链表的算法设计及其程序实现

6、结构上实现的基本操作，熟练掌握线性表在链式存储结构上基本操作的实现。掌握循环链表和双向循环链表的基本操作。能够从时间和空间的角度结合比较线性表两种存储结构的不同特点及在不同的应用中选择合适存储形式。计划理论7学时。二、课程内容2.1线性表的类型定义2.2线性表的顺序存储结构顺序表顺序表上的基本运算2.3线性表的链式表示和实现线性链表循环链表双向链表三、重点、难点提示和教学手段重点难点提示：线性表这种抽象数据结构的定义及其逻辑上的特点；顺序表上插入、删除和定位运算的实现；单链表的结构特点及其类型说明；头指针和头结点的作用；定位、删除、插入运算在单链表上的实现；循环链表和双链表的结构特点，尤其是链

7、表定义及其操作。顺序表和链表的比较和在不同应用环境下的选择是教学难点。讲课辅以算法演示，另加实验。四、思考与练习2.2，2.3，2.4，2.5，2.6，2.7，2.8，2.9，2.10，2.13，2.13，2.17，2.19，2.20，2.21，2.24，2.25，2.26，2.31第三章 栈和队列一、学习目的本章主要介绍了两种常用的操作受限的线性表，内容包括这两种线性表的定义和在两种存储结构上操作的实现。通过本章学习要求理解栈和队列的定义，掌握栈和队列在两种存储结构中的基本操作的实现。能够在简单的应用中，为数据选择合适的逻辑结构和存储结构，并实现要求的操作。计划理论6学时。二、课程内容3.1

8、栈抽象数据类型栈的定义和基本操作栈的顺序存储结构栈的链式存储结构3.2栈的应用举例数制转换括号匹配迷宫求解表达式求值3.3栈与递归（选讲）3.4队列抽象数据类型队列的定义链队列队列的链式表示和实现循环队列队列的顺序表示和实现三、重点、难点提示和教学手段重点难点：栈上的基本运算；栈的顺序存储结构及运算实现；栈的链式存储结构；入栈、出栈等运算在链栈上的实现；队列上的基本运算；队列的顺序存储结构及其上的运算实现；队列的链式存储结构；入队、出队等运算在链式队列上的实现是本章教学的重点。顺序栈的溢出判断条件，循环队列的队空、队满判断条件；循环队列上的插入和删除操作，为实际的应用选择合适的数据结构是本章的

9、难点。讲课加实验。四、思考与练习题集3.1，3.3，3.4，3.7，3.19，3.28，3.29第四章 串一、学习目的通过本章学习，要求学生掌握串类型的抽象数据类型定义和有关基本概念，理解串的模式匹配思想，了解串的表示和实现和串的模式匹配算法。计划理论2学时。二、课程内容4.1串的定义4.2串的表示和实现定长顺序存储堆分配存储表示串的块链存储表示4.4串的应用举例三、重点、难点提示和教学手段重点和难点：串的表示和实现，熟练掌握串的定长顺序表示和实现串的基本操作。串的堆存储是本章的难点。讲授。四、思考与练习题集4.3，4.4，4.9第五章 数组和广义表一、学习目的通过本章学习了解数组的定义和表示

10、方式，掌握特殊矩阵和压缩矩阵的压缩存储方法；理解广义表的逻辑结构。本章计划2学时二、课程内容5.1数组的定义5.2数组的顺序表示和实现5.3矩阵的压缩存储5.3.1特殊矩阵5.3.2稀疏矩阵5.4广义表的定义三、重点、难点提示和教学手段重点和难点：数组在以行为主的存储结构中的地址计算方法，广义表的逻辑结构。特殊矩阵的压缩存储时的下标变换公式是其难点。讲课辅以算法演示。四、思考与练习题集5.1，5.6，5.7，5.8，5.10，5.13，5.21第六章 树和二叉树一、学习目的通过本章的学习要求，要求学生掌握以下内容：树的定义、性质、存储结构；熟练掌握二叉树的遍历，哈夫曼树的构造和编码方法；了解二

11、叉树的线索化，树与森林的转化和树的应用。能够运用二叉树的遍历解决相关的应用问题。计划理论学时8学时。二、课程内容6.1树的定义和基本术语树的定义基本操作6.2二叉树二叉树的定义和基本操作二叉树的性质普通二叉树、完全二叉树、满二叉树二叉树的存储结构6.3遍历二叉树和线索二叉树遍历二叉树先序遍历二叉树、中序遍历二叉树、后序遍历二叉树线索二叉树中序线索化二叉树6.4树和森林树的存储结构森林与二叉树的转换树和森林的遍历6.6哈夫曼树及其应用最优二叉树的定义哈夫曼树的构造和哈夫曼编码二、重点、难点提示和教学手段重点和难点：本章是本课程的教学重点。其中二叉树的定义、逻辑特点及其五种基本形态；二叉树的五个性

12、质；二叉树上的基本运算；二叉树的链式存储结构及其类型说明；二叉树的顺序存储结构及其类型说明；二叉树的三种遍历方法及在此基础上的应用；哈夫曼树和哈夫曼编码是本章的教学重点。二叉树的递归定义；二叉树链式存储结构和组织形式；三种遍历的主要区别是教学难点。讲课辅以算法演示，另加实验。四、思考与练习6.1，6.4，6.14，6.19，6.21，6.22，6.23，6.26，6.27，6.33，6.43，6.63第七章图一、学习目的通过学习本章要求学生掌握以下内容：理解图的基本概念和术语；掌握图的两种存储结构方法；掌握图的两种遍历的算法思想、步骤，并能列出在两种存储结构上按上述两种遍历算法得到的序列；理解

13、最小生成树的概念，能够运用普里姆或库鲁索方法生成图的最小生成树；领会拓扑排序、最短路径的思想，能够列出一个图的拓扑排序序列。本章是本课程的又一个教学的重点和难点章节。计划理论学时9学时。二、课程内容7.1图的定义和术语7.2图的存储结构数组表示邻接表7.3图的遍历深度优先遍历广度优先遍历7.4图的连通性问题无向图的连通分量和生成树最小生成树7.5有向图五环图及其应用拓扑排序最短路径三、重点、难点提示和教学手段重点和难点：理解图的定义、术语与含义；掌握各种图的邻接矩阵表示法及其类型说明；理解并掌握图的两种遍历方法；领会生成树和最小生成树的概念，并能够选用一种方法得到图的最小生成树；强化拓扑有序的

14、概念，可以根据相应的算法和步骤得到图的拓扑排序序列；了解关键路径的思想和最短路径的思想。图的术语的理解和区分；图的两种存储结构的不同点及其应用场合是教学的难点。讲课辅以算法演示，另加实验。三、思考与练习习题集：7.1，7.7，7.6，7.11第九章 查找一、学习目的通过本章的学习，要求掌握静态查找表的查找算法和实现，掌握二叉排序树的查找、插入算法及其实现；掌握哈希表的构造方法；深刻理解哈希表与其他结构表的实质性的差别。了解三类函数和处理冲突的方法，能够对各种查找方法，根据定义在等概率下的平均查找长度。本章是本课程的重点。计划理论8学时.二、课程内容9.1静态查找表顺序表查找有序表的查找静态树表

15、的查找索引顺序表的查找9.2动态查找表二叉排序树的查找、插入、删除平衡二叉树、B树、B树的思想9.3哈希表哈希表的概念哈希表的构造方法处理冲突的方法哈希表的查找及其分析三、重点、难点提示和教学手段重点和难点：查找表的基本概念及查找原理，查找运算在静态表有序表上的实现，动态查找表的概念，二叉排序树的定义和二叉排序树的查找算法和基本思想；哈希表的概念和散列的思想；简单的构造哈希表的方法和解决冲突的方式；平均查找长度的概念和计算是本章的教学重点。二叉排序树上的插入和删除；构造散列表中的冲突的处理方式是本章的教学难点。讲课辅以算法演示，另加实验。四、思考与练习题集：9.9，9.19，9.21，9.25

16、，9.26，9.31第十章 内部排序一、学习目的本章主要是介绍常用的内部排序方法的基本思想、排序过程、算法实现、时间和空间性能的分析以及各种排序方法的比较和选择。通过本章的学习要求理解各种内部排序方法，插入排序、交换排序、选择排序、归并排序和基数排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。在每种排序方法中，重点掌握先进的高效方法。本章是本课程的重点和难点章节。计划理论8学时。二、课程内容10.1概述10.2插入排序直接插入排序希尔排序10.3快速排序10.4选择排序简单选择排序树刑选择排序堆排序10.5归并排序10.7各种排序方法综合比较三、重点、难点提示和教学手段重点和难点：排序基本概念及稳定排序和非稳定排序的区别；各种排序方法的基本