《数据结构(A)》课程教学大纲
（Data Structures）
课程编号：80L129Q 适用专业：计算机专业 开课单位： 计算机学院
课时数：
56+24
课程学分数：4 课程类别：本科
课程性质： 学位
授课方式： 讲授
考试方式：笔试+课程实验
一、课程的性质和目的
本课程系统地介绍各种常用的数据结构，分别讨论线性表、栈、队列、字符串、数组、广义表、树、二叉树以及图等基本的数据结构及其应用，还介绍了排序、查找的各种实现算法，并着重从时间上进行定性或定量的分析和比较。要求学生掌握各种数据结构的逻辑关系、存储表示及运算操作，并初步掌握算法的时间分析和空间分析技术，提高分析问题和解决问题的能力。
二、课程教学内容
第一章 绪论 (3学时) 教学内容：数据结构的基本概念；算法设计；时间和空间复杂度。 要求学生掌握：
1相关的基本概念； 2算法五大要素；
3计算语句频度和估算算法时间复杂度的方法。 教学重点及难点：估算算法时间复杂度的方法。
第二章
线性表 (5学时) 教学内容：线性表的逻辑结构；线性表的存储结构及操作的实现；一元多项式的表示。要求学生掌握：
1线性表的逻辑结构； 2线性表的存储结构；
3线性表在顺序结构和链式结构上实现基本操作的方法；
4从时间和空间复杂度的角度比较线性表两种存储结构的不同特点及其适用场合。 教学重点及难点：链式结构上实现基本操作的方法。
第三章
栈和队列 (4学时) 教学内容：栈的定义、表示及实现； 表达式求值； 栈与递归过程；
队列的定义、表示及实现。
要求学生掌握：
1 栈和队列的特点；
2在两种存储结构上栈的基本操作的实现； 3循环队列和链队列的基本运算； 4递归算法执行过程中栈状态的变化过程。
教学重点及难点：栈的基本操作的实现；循环队列和链队列的基本运算。
第四章
串 (4学时) 教学内容：串的逻辑结构，存储结构；
串操作的实现(重点难点BF和KMP算法) ，串的应用(略讲)。
要求学生掌握：
1串的七种基本运算的定义，利用这些基本运算来实现串的其它各种运算的方法；
2在顺序存储结构上实现串的各种操作的方法；
3 KMP算法，熟悉NEXT函数和改进NEXT函数的定义和计算； 4串名的存储映象和在堆存储结构实现串操作的方法。
教学重点及难点：KMP算法，手工计算NEXT函数和改进NEXT函数的值。
第五章 数组和广义表 (4学时) 教学内容：数组的存储结构；稀疏矩阵的表示及操作的实现；
广义表的定义和存储结构；广义表的递归算法。
要求学生掌握：
1数组在以行序为主的存储结构中的地址计算方法； 2矩阵实现压缩存储时的下标变换；
3理解稀疏矩阵的两种存储方式的特点和适用范围，领会以三元组表示稀疏矩阵时进行运算采用的处理方法；
4广义表的定义及其存储结构，学会广义表的表头，表尾分析方法； 5学习编制广义表的递归算法。
教学重点及难点：矩阵实现压缩存储时的下标变换；广义表的存储结构。
第六章 树和二叉树 (8学时) 教学内容：树的基本概念；二叉树的性质和存储结构；遍历二叉树和线索二叉树；
树的存储结构和遍历；哈夫曼树及其应用。
要求学生掌握：
1二叉树的结构特点；
2二叉树的各种存储结构的特点及适用范围； 3按各种次序遍历二叉树的递归和非递归算法；
4二叉树的线索化，在中序线索树上找给定结点的前驱和后继的方法； 5树的各种存储结构及其特点； 6编写树的各种运算的算法；
7建立最优二叉树和哈夫曼编码的方法。
教学重点及难点：按各种次序遍历二叉树的递归和非递归算法。
第七章
图 (6学时) 教学内容：图的基本概念；图的存储结构；图的遍历；最小生成树；
最短路径；拓扑排序和关键路径。
要求学生掌握：
1熟悉图的各种存储结构，了解实际问题与采用何种存储结构和算法有密切联系； 2遍历图的递归算法； 3应用图的遍历算法求各种简单路径问题，比如，最小生成树﹑最短路径﹑拓扑排序﹑关键路径等。
教学重点及难点：图的各种存储结构，图的遍历算法，构造最小生成树的算法。
第八章
动态存储管理 （不讲）
第九章 查找 (8学时) 教学内容：静态查找表(顺序表,有序表,索引顺序表)；
动态查找表(二叉排序树,平衡二叉树,B_树和B+树)的建立和查找； 哈希表的建立，查找及分析。
要求学生掌握：
1顺序查找，折半查找和索引查找的方法，并能灵活应用； 2二叉排序树的构造方法； 3二叉平衡树的旋转平衡方法；
4 B_树，B+树和键树的特点以及它们的建立过程； 5哈希表的构造方法；
6按定义计算各种查找方法在等概率情况下查找成功时和失败时的平均查找长度，理解哈希表在查找不成功时的平均查找长度的计算方法。
教学重点：各种查找方法，哈希表的构造方法及平均查找长度的计算。 教学难点：二叉平衡树的旋转平衡方法。
第十章 内部排序 (7学时) 教学内容：插入排序；交换排序(起泡排序,快速排序)；
选择排序(简单选择、树形选择、堆)；归并排序；基数排序。
要求学生掌握：
1各种排序方法的特点并能灵活应用； 2各种方法的排序过程；
3各种排序方法的时间复杂度分析。
教学重点及难点：各种排序方法的特点及时间复杂度的分析。
第十一章 外部排序 (1学时) 教学内容：外排的基本方法
要求学生掌握：
1外部排序的两个过程；
2外排过程中所需进行外存读/写次数的计算方法。
教学重点及难点：外排过程中所需进行外存读/写次数的计算方法。
第十二章 机动
习题课（6学时） 上机实验（24学时）
实验内容（附后）
三、课程教学的基本要求
（一） 课堂讲授：（56学时） 1． 教学方法：课堂讲授 2． 教学手段：电子教案
（二） 教学环境：多媒体教室
（三） 课堂练习、作业、自学
（四） 考试（笔试占70分，上机实验占20分，平时作业占10分）
四、本课程与其它课程的联系与分工
先修课程: 计算机导论、C语言
后继课程：操作系统、数据库、编译原理、软件工程等
五、建议教材与教学参考书 1.严蔚敏等，《数据结构》（C语言版）清华大学出版社 2.严蔚敏等，《数据结构题集》（C语言版）清华大学出版社
