课程编号:13091140140

课程名称（中文）:数据结构

课程名称（英文）:Data Structrue

开课单位:信息技术学院

学分:4 总学时:72

理论学时:54 实验学时:18

先开课程:C语言程序设计、离散数学

授课对象:计算机科学与技术专业、软件工程

考核方式:考试

一、课程的教学目标与任务

《数据结构》在计算机科学中是一门综合性的专业主干课，它是介于数学、计算机硬件、计算机软件三者之间的一门核心课程，而且是操作系统、数据库系统及其它系统程序的大型应用程序设计的基础，同时又直接为从事各类计算机应用的技术人员提供了必要的基本知识和解决实际问题的多种方法。

通过对本课程的教学，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步掌握算法的时间分析和空间分析的技术。培养学生的数据抽象能力，为今后学习面向对象程序设计打下坚实的基础。

二、课程内容及基本要求

（一）绪论（2学时）

1.基本要求:

（1）理解什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。

（2）了解什么是数据类型、抽象数据类型。

（3）理解算法的定义、算法的特性。

（4）掌握算法的时间代价、算法的空间代价。

2.重点、难点

（1）重点:数据类型、数据结构、算法时间复杂度。

（2）难点:算法的时间复杂度与空间复杂度。

（二） 线性表（8学时）

1.基本要求:

（1）理解线性表的逻辑结构特性，以及线性表的两种存储实现方式。

（2）熟练掌握顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算。

（3）了解链表有单链表、循环单链表、双向链表之分。

（4）掌握单链表的结构、特点。

（5）熟练掌握单链表的类定义、构造函数、单链表的插入与删除算法及其平均比较次数的计算。

（6）熟练掌握带表头结点的单链表的优点和类定义及相应操作的实现。

（7）了解循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法。

（8）了解双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。

（9）掌握顺序表和单链表的比较。

2.重点、难点

（1）重点:线性表的表示与实现。

（2）难点:顺序表和单链表的插入与删除操作实现。

3.说明

本章思考题

（1）给出顺序表建表算法。

（2）给出链表建表算法。

（三） 栈和队列 （4学时）

1.基本要求:

（1）熟练掌握栈的定义、特性和栈的抽象数据类型，栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件。

（2）熟练掌握队列的定义、特性和队列的抽象数据类型，队列的顺序表示、链表表示以及相应操作的实现，特别是循环队列中队头与队尾指针的变化情况。

（3）掌握栈和队列的的应用。

2.教学的重点和难点

（1）重点:栈的表示和实现；队列的表示和实现。

（2）难点:循环队列。

3.说明

本章思考题

（1）递归算法执行过程中的状态变化过程。

（2）分别给出解决循环队列队满和队空条件一致的三种方法实现入队和出队的操作。

（四）串（4学时）

1.基本要求:

了解串的定义，串的表示和实现；熟练掌握串的操作的定义。

（1）串的定义。

（2）串的表示和实现。

2.重点、难点

（1）重点:串的操作的定义。

（2）难点:串的表示和实现。

3.说明

本章思考题

三种串表示的优缺点。

（五） 数组和广义表 （4学时）

1.基本要求:

（1）掌握数组的两种存储表示方法。

（2）掌握矩阵的压缩存储。

（3）掌握稀疏矩阵的定义及其数组实现。

（4）了解广义表的定义。

2.重点、难点

（1）重点:矩阵的压缩存储。

（2）难点:特殊矩阵，广义表的存储。

3.说明

本章思考题:矩阵的各种压缩存储实现。

（六） 树和二叉树 （10学时）

1.基本要求:

（1）理解树和森林的概念。包括树的定义、树的术语、树的抽象数据类型。

（2）掌握二叉树的概念、性质及二叉树的表示。

（3）熟练掌握二叉树的遍历方法。

（4）掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。

（5）掌握树与森林的实现，重点在用二叉树实现。

（6）掌握森林与二叉树的转换；树的遍历算法。

（7）了解二叉树的计数方法及从二叉树遍历结果得到二叉树的方法。

（8）掌握赫夫曼树的实现方法、构造赫夫曼编码的方法及带权路径长度的计算。

2.重点、难点

重点:二叉树，赫夫曼树。

难点:二叉树的基本性质，线索二叉树，赫夫曼树。

3.说明

本章思考题

（1）赫夫曼树编码的优点。

（2）给出现实生活中树型结构的例子。

（七） 图 （10学时）

1.基本要求:

（1）理解图的基本概念和图的抽象数据类型。

（2）掌握图的3种存储表示:邻接矩阵、邻接表和邻接多重表。对于前两种，要求掌握典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法。

（3）熟练掌握图的两种遍历算法与求解连通性问题的方法。包括深度优先搜索和广度优先搜索算法、求连通分量的方法(不要求具体算法实现)。

（4）掌握构造最小生成树的Prim算法和Kruskal算法，要求理解具体算法实现。

（5）掌握活动网络的拓扑排序算法。

（6）理解求解关键路径的方法。

（7）理解如何用Dijkstra方法求解单源最短路径问题(不要求具体算法实现)。

2.重点、难点

（1）重点:图的遍历及应用。

（2）难点:关键路径及最短路径。

3.说明

（1）判断图的连通性可用几种算法实现。

（2）给出现实生活中图型结构的例子。

（九） 查找（6学时）

1.基本要求:

（1）了解查找表的定义、分类和各类的特点。

（2）掌握顺序查找和二分查找的思想和算法。

（3）理解二叉排序树的概念和有关运算的实现方法。

（4）掌握哈希表、哈希函数的构造方法、以及处理冲突的方法。

（5）掌握哈希存储和哈希查找的基本思想及有关方法、算法。

2.重点、难点

（1）重点:二叉排序树，哈希表的构造和查找。

（2）难点:AVL树的调整，B树。

3.说明

本章思考题:比较各种查找算法。

（十） 内部排序（6学时）

1.基本要求:

（1）掌握:排序的基本概念和性能分析方法。

（2）掌握:插入排序、交换排序、选择排序、归并排序等内排序的方法及其性能分析方法。

2.重点、难点

（1）重点:各种排序算法实现。

（2）难点:各排序性能分析以及适用面。

3.说明

本章思考题:比较各种排序算法。