一、课程名称：《数据结构》

二、学分：4

三、先修课程：《C语言程序设计》、《离散数学》

四、课程的性质、目的和任务：

《数据结构》课程是网络教育考试的一门必修的专业基础课。这门课程的主要特点是实践性很强,不仅要学习基本理论知识,更要注重上机实践,通过上机实践验证算法的正确性,掌握和巩固所学理论知识。设立本门课程的目的是通过学习，使学生学会分析研究计算机加工的数据结构的特性，以便为应用涉及的数据选择适当的逻辑结构、存储结构及相应的算法，并初步了解对算法的时间分析和空间分析技术。另一方面，通过对本课程算法设计和上机实践的训练，还应培养学生的数据抽象能力和程序设计的能力，为后续课程，特别是软件课程打下坚实的知识基础。要求学生掌握各种常用数据结构的逻辑结构，存储结构及有关操作的算法。

五、课程的教学基本要求及主要内容：

第一章  绪论

一、学习要求

通过本章的学习，要求学生了解数据结构中常用的基本概念和术语以及学习数据结构的意义，了解该课程的基本框架。

本章要了解各种基本概念和术语，了解抽象数据类型的表示与实现，掌握算法描述和分析的方法。本章重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系，难点是算法复杂度的分析方法。

二、课程内容

1、教学内容：

（1）数据结构基本概念
     数据、数据元素、数据对象、数据结构和数据类型等概念
（2）算法及算法分析
     性能分析与度量：算法的性能标准；空间复杂度度量；时间复杂度度量
2、教学要求：
（1）了解数据、数据对象、数据元素、数据类型、数据结构、数据的逻辑结构与物理结构概念及逻辑结构与物理结构间的关系

（2）了解算法的定义、算法的特性、算法的时间代价、算法的空间代价
（3）掌握计算语句频度和估算算法时间复杂度的方法

第二章  线性表

一、学习要求

通过本章的学习，要求学生在熟悉内容的基础上，能够针对具体应用问题的要求和性质，选择合适的存储结构设计出相应的有效算法，解决与线性表相关的实际问题。

本章要了解线性表的逻辑结构及各种存储表示方法以及定义在逻辑结构上的各种基本运算及其在存储结构上如何实现这些基本运算。重点掌握顺序表和单链表上实现的各种基本算法及相关时间性能分析，难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的实际问题。

二、课程内容

1、教学内容：
（1） 线性表的定义和性质及基本运算；
（2） 线性表的顺序存储结构
（3） 线性表的链式存储结构
2、教学要求：
（1） 了解线性表的逻辑结构特性，以及线性表的两种存储实现方式
（2） 熟练掌握两种存储结构的描述方法。链表是本章的重点和难点。
（3） 熟练掌握顺序表的定义与实现，包括查找、插入、删除算法的实现；
（4） 熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构；
（5） 能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

三、实践（上机）环节内容和基本要求

1、实验目的

（1）掌握用Turbo C 2.0上机实现线性链表的基本方法；

（2）掌握线性表的基本操作：建表、插入、删除、输出等运算在链式存储结构上的实现。

2、实验内容

（1）编写一生成线性表的函数，线性表的元素从键盘读取，用链式存储结构存储；

（2）编写一在线性表中插入一元素的函数；

（3）编写一在线性表中删除一元素的函数；

（4）编写一输出线性表的函数；

（5）编写主函数，调用以上各函数，以便能观察出原线性表以及作了插入或删除后线性表的屏幕输出。

第三章  栈和队列

一、学习要求

通过本章的学习，要求学生在掌握栈和队列的特点的基础上，懂得在什么样的情况下能够使用栈或队列。

本章要了解栈和队列的逻辑结构定义，重点掌握在两种存储结构上如何实现栈和队列的基本运算。难点是循环队列中对边界条件的处理。

二、课程内容

1、教学内容：
（1） 栈和队列的定义及特点；
（2） 栈的顺序存储表示和链接存储表示；
（3） 队列的顺序存储表示；队列的链接存储表示；
（4） 栈和队列的应用举例。
2、教学要求：
（1）掌握栈和队列的定义、特性，并能正确应用它们解决实际问题；
（2）熟练掌握栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件；
（3）熟练掌握队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况

三、实践（上机）环节内容和基本要求

1、实验目的

（1） 掌握用Turbo C 2.0上机实现栈的基本方法；

（2） 掌握栈的基本操作：栈的初始化、入栈、出栈、栈的判空等运算在顺序存储结构上的实现。

2、实验内容

写一个算法，借助栈将一个带头结点的单链表倒置。

要求：利用栈的特征，先沿着链表从头至尾扫描一遍，将链表的每个结点的data域的值依次进栈，然后再沿着链表从头至尾扫描一遍，同时栈中元素依次出栈，并填入到链表的每个结点的data域中。

第四章  串

一、学习要求

通过本章的学习，要求学生熟悉串的逻辑结构、存储结构以及串上的基本运算。

本章要了解串的逻辑结构和存储结构。重点掌握串上的基本运算。

二、课程内容

1、教学内容：
（1） 串的概念；
（2） 串的存储结构；
（3） 串的运算。
2、教学要求：
（1） 理解串的基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法；
（2） 熟练掌握在串的顺序存储结构上实现串的各种操作的方法；
（3） 了解串操作的应用方法和特点。

第五章  数组和广义表

一、学习要求

通过本章的学习，要求学生熟悉多维数组的逻辑结构特征及其存储方式，特殊矩阵的压缩存储方法及广义表的概念。

本章要了解数组和稀疏矩阵的存储表示方法，掌握广义表的结构特点及其存储表示。重点掌握多维数组的存储方式，矩阵的压缩存储方式及广义表的定义及其求表头和表尾的运算，难点是稀疏矩阵的压缩存储表示下实现的算法。

二、课程内容

1、教学内容：
（1） 数组的定义和顺序存储方式；
（2） 特殊矩阵的压缩存储；
（3） 稀疏矩阵
（4） 广义表的概念、表示及基本操作；广义表存储结构的实现。

2、教学要求：
（1） 了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法；
（2） 掌握对特殊矩阵进行压缩存储时的下标变换公式；
（3） 了解稀疏矩阵的两种压缩存储方法的特点和适用范围，理解以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法；
（4） 掌握广义表的结构特点及其存储表示方法，会对非空广义表进行分解。

第六章  树和二叉树

一、学习要求

通过本章的学习，要求学生熟悉二叉树的定义、性质、存储结构、遍历、线索化，树的定义、存储结构、遍历树和森林的转换，哈夫曼树和哈夫曼编码等内容。

本章重点掌握二叉树的遍历算法及其有关应用，难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。

二、课程内容

1、教学内容：
（1） 树和森林的概念（树的定义、树的术语、性质及运算）；
（2） 二叉树的定义、性质及运算；
（3） 二叉树的存储结构（顺序、链式表示）；
（4） 遍历二叉树
（5） 树的存储结构；树、森林与二叉树的转换；遍历树；遍历森林
（6） 哈夫曼树、哈夫曼编码。

2、教学要求：
（1）了解树和森林的概念。包括树的定义、树的术语和性质；
（2）熟练掌握二叉树的结构特性，熟悉二叉树的各种存储结构的特点及适用范围；
（3）熟练掌握二叉树的遍历方法及遍历算法；
（4）熟悉树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法；
（5）掌握建立哈夫曼树和哈夫曼编码的方法及带权路径长度的计算。

三、实践（上机）环节内容和基本要求

1、实验目的

（1） 掌握用Turbo C 2.0上机实现树的基本方法；

（2） 掌握二叉树的基本操作：建立二叉树、二叉树的遍历等运算在链式存储结构上的实现。

2、实验内容

生成如下二叉树，并得出先序遍历结果：

第七章  图

一、学习要求

通过本章的学习，要求学生掌握图的基本概念、两种常用的存储结构、两种遍历算法以及图的应用算法。

本章重点掌握在图的两种的存储结构上实现的遍历算法。难点是图的应用算法：求最小生成树，求最短路径以及拓扑排序，只要求学生掌握这些算法的基本思想。

二、课程内容

1、教学内容：
（1）图的基本概念
（2）图的存储结构（邻接矩阵、邻接表及有向图十字邻接表）；
（3）图的遍历（深度优先搜索、广度优先搜索）；
（4）最小生成树（kruskul算法、prim算法）；
（5）最短路径（dijkstra算法、floyd算法）;
（6）AOV网络与拓扑排序；
（7）AOE网络与关键路径。
2、教学要求：
（1）理解图的基本概念，熟悉图的各种存储结构及其构造算法；
（2）熟练掌握图的两种搜索路径的遍历；
（3）掌握构造最小生成树的方法，并理解算法；
（4）理解用Dijkstra方法求解单源最短路径问题；
（5）掌握求活动网络的拓扑排序的方法，并理解算法；
（6）掌握求解关键路径的方法。

三、实践（上机）环节内容和基本要求

1、实验目的

（1） 掌握用Turbo C 2.0上机实现图的基本方法；

（2） 掌握图的广度和深度优先搜索遍历算法

二、实验内容

分别编写BFS、DFS算法

第八章  查找

一、学习要求

通过本章的学习，要求学生掌握静态查找表、动态查找表、哈希表的查找方法、算法实现以及各种查找方法的时间性能分析。

本章重点掌握顺序查找、折半查找，二叉排序树查找以及哈希表查找的基本思想和算法实现。难点是二叉排序树的构造和查找算法。

二、课程内容

一、教学内容：
1、 线性表的查找；
2、 树表查找；
3、 哈希表查找。

二、教学要求：
1、熟练掌握顺序表和有序表的查找算法及其性能分析方法；
2、熟练掌握二叉排序树的构造和查找算法及其性能分析方法；
3、理解AVL树的维护平衡方法；
4、 理解B_树、B+的特点、查找及构造方法；
5、 熟练掌握哈希函数的构造及解决冲突的方法。

三、实践（上机）环节内容和基本要求

1、实验目的

掌握用Turbo C 2.0上机实现二叉排序树的基本方法；

2、实验内容

从一棵二叉排序树上删除一结点之后仍须保持为一棵二叉排序树。

第九章  排序

一、学习要求

通过本章的学习，要求学生了解五类内部排序方法的基本思想、排序过程、算法实现、时间和空间性能分析以及各种排序方法的比较和选择。

本章重点掌握快速排序、堆排序、归并排序和基数排序的基本思想和排序过程，难点是这四个排序算法的实现。

二、课程内容

1、教学内容：
（1）插入排序（直接插入排序、折半插入排序、希尔排序）；
（2）交换排序（起泡排序、快速排序）；
（3）选择排序（直接选择排序、堆排序）；
（4）归并排序；
（5）基数排序；
2、教学要求：
（1）掌握排序的基本概念和各种排序方法的特点，并能加以灵活应用；
（2）掌握插入排序、交换排序、选择排序、归并排序的方法及其性能分析方法；
（3）了解基数排序方法及其性能分析方法。

三、实践（上机）环节内容和基本要求

1、实验目的

掌握用Turbo C 2.0上机实现各种排序算法；

二、实验内容

分别编写直接插入、冒泡、直接选择、快速、堆等排序算法。比较各种排序算法的运行速度。

建议用菜单组织以上操作。

第十章  文件

一、学习要求

通过本章的学习，要求学生了解存储在外存上的数据结构（即文件）的有关概念、各种文件的特点、组织方法及查询和更新操作，要求对这些内容做一般性的了解。

二、课程内容

1、教学内容：

（1）    文件的基本概念

（2）    顺序文件，索引文件

（3）    ISAM文件和VSAM文件

（4）    直接存储文件，多关键字文件。

2、教学要求：

了解各种文件的组织方式和操作方法。

Ⅴ 教材内容自学安排：

       （以下列出内容的章节知识点序号以教材为准，与光盘课件无关）

一、        第二章第4节内容：一元多项式的表示及相加。

二、        第三章第3节的内容：栈与递归的实现

三、第三章第5节的内容：离散事件模拟

四、第四章第3节和第4节的内容：串的模式匹配算法和串操作应用举例。

五、第五章第6节和第7节的内容：m元多项式的表示和广义表的递归算法。

六、第六章第7节、第8节的内容：

6．5 树与等价问题

6．7 回溯法与树的遍历

6．8 树的计数

七、第七章第7.4节7.4.2和7.4.4的内容：

7.4.2 有向图的强连通分量

7.4.4 关节点和重连通分量

八、第八章的内容：动态存储管理

九、第九章第9.1.3和9.2.3的内容：

9.1.3 静态树表的查找

9.2.3 键树

十、第十一章的内容：外部排序

六、考试方式：闭卷笔试

七、使用教材：《数据结构（C语言版）》；严蔚敏编；清华大学出版社出版。