《数据结构》课程教学大纲

一、课程基本情况
开课单位：计算机与信息工程系 课程编码：Z060106
适用专业：高职高专计算机类各专业 修课方式：必修
总 学 时： 64～76学时 考核方式：考试
教 材：陈雁.《数据结构》. 高等教育出版社. 2002年
教学参考书：严尉敏 .《数据结构》. 清华大学出版社. 2003年
苏德富 .《数据结构》. 重庆大学出版社. 2002年
二、课程的性质、任务和目的
《数据结构》是介于数学、硬件及软件三者之间的一门核心课程，它不仅是一般程序设计，尤其是非数值性程序设计的基础，而且是设计实现编译程序、操作系统、数据库系统、大型应用程序及其它系统程序的重要基础。所以《数据结构》从课程性质上讲是一门专业基础课。
本课程的目的和任务就是训练学生对计算机加工的数据对象进行分析的能力，选择适当的数据结构、存贮结构及相应算法的能力，并且能够创造性地进行算法设计和程序设计，使所设计的程序结构清楚，正确易读，并上机调试通过。
三、课程的主要内容与学时分配
(一) 主要内容
1．数据结构概述 2学时
1.1 数据结构研究的对象----数据、数据之间的关系
1.2 实际问题抽象成数学模型----线性结构、层次结构、网状结构
1.3 数据结构中使用的基本术语----数据、数据元素、数据项、数据对象、数据结构、存储结构
1.4 数据结构的发展及它的地位----为什么要学习数据结构
1.5 算法描述的语言及对算法分析的方法----算法、算法特征、时间复杂度，空间复杂度的分析
2．线性表 12 学时（6+2+4 ）
2.1 顺序表的定义----存储原理、运算（查找、插入、删除）
2.2 链式存储结构、运算----存储原理、运算（查找、插入、删除）
2.3 循环链、双向链
3．栈和队列 8学时（6+2）
3.1 栈的逻辑结构、栈的基本运算
3.2 队列的基本运算、循环队列
3.3 栈与队的应用
4．数组 6学时(4+*2)
4.1 数组的概念
4.2 特殊矩阵、稀疏矩阵的存储方法
5．串 2学时
5.l 串的定义及基本运算
5.2 串的存贮结构
5.3 串的基本运算的实现——模式匹配（KMP）
6．树 12学时（6+2+4）
6.1 树的概念
6.2 二叉树的概念
6.3 二叉树的存储结构
6.4 树的遍历
6.5 线索树——
6.6 树的存储结构
6.7 树、二叉树和森林之间的转换
6.8 哈夫曼树（Huffman）算法及其应用（哈夫曼编码）
7．图 12学时（8+2+2）
7.1 图的定义，术语
7.2 图的存贮结构——顺序链式存储
7.3 图的遍历
7.4 最小生成树
7.5 拓扑排序
7.6 最短路径
7.7 关键路径
8．检索 10学时（6+2+2）
8.1 顺序检索、有序检索、分块检索、散列表的检索
8.2 二叉排序树
8.3 平衡二叉排序树
* 8.4 B_树
9．排序 8学时（6+2+2）
9.1 插入排序
9.2 快速排序
9.3 选择排序
9.4 堆排序
9.5 归并排序
9.6 基数排序
9.7 内部排序方法的比较
9.8 外部排序简介
*10．文件 2学时
10.l 顺序文件
10.2 索引文件
10.3 直接存取文件
10.4 多关键字文件
(二) 学时分配
序号
章 节
课 时 分 配
理论课
习题课
实验课
其它
共计
1
数据结构概述
2
d
d
2
2
线性结构表
6
2
4
12
3
栈、队列
6
d
2
8
4
数组
4
d
*2
6
5
串
2
d
d
2
6
树
6
*2
2+*2
12
7
图
8
*2
2
12
8
查找
6
*2
2
10
9
排序
6
*2
2
10
10
文件
2
d
d
2
合 计
48
10
18
d
76
四、课程教学基本要求及重点
1．数据结构概述：了解数据结构研究的对象、数据结构的发展及地位，掌握实际问题抽象成数学模型的概念、数据结构中使用的基本术语和算法描述的语言及算法分析的方法。具体为：
学会分析数据结构研究的对象 ----数据、数据之间的关系；
会将实际问题抽象成数学模型 ----线性结构、层次结构、网状结构；
掌握数据结构中使用的基本术语 ----数据、数据元素、数据项、数据对象、数据结构、存储结构；
了解数据结构的发展及它的地位 ----为什么要学习数据结构；
掌握算法描述的语言及对算法分析的方法 ----算法、算法特征、时间复杂度，空间复杂度的分析。
重点：概念、算法分析的方法。
难点：算法分析的方法。
2．线性结构
熟练掌握顺序表的定义、向量 (或一维数组)的存储、插入、删除元素等运算。
掌握链式表的建立、插入、删除元素等运算。
熟悉链表的连接，多项式的加、减运算等操作。
熟悉循环链、双向链的操作。
重点：概念、基本运算实现方法。
难点：应用。
3．栈、队列
掌握栈的定义，顺序栈存储结构和链式栈存储结构的建立、基本操作（运算）。
熟悉栈在计算表达式中的应用、栈与递归过程。
掌握循环队列的操作和实现，应用。
熟悉队列的定义，顺序队列（循环队列）存储结构和链式队列存储结构的建立、基本操作（运算）。
熟悉队列的应用。
重点：概念、栈和队列基本运算实现方法。
难点：栈和队列的应用。
4．数组
掌握数组的定义、数组的顺序表示和实现；
掌握特殊矩阵： 三角矩阵、对称矩阵及稀疏矩阵的定义、存储方法，地址计算式；
熟悉稀疏矩阵的十字链表存储方法；
熟悉特殊矩阵的一些算法。
重点：概念、存储方法，地址计算式；
难点：应用。
5．串
掌握串的定义及基本运算；
掌握串的存贮结构；
掌握串基本运算的实现；
熟悉串的基本运算的实现 ----模式匹配（KMP）。
重点：串的定义及基本运算。
6．树
熟练掌握树的概念、二叉树的概念、二叉树的性质、完全二叉树、满二叉树的概念和特点；
掌握二叉树的存储结构（顺序存储和链式存储）；
掌握二叉树的遍历算法（使用栈的遍历）前序、中序和后序；
掌握线索树的概念，线索方法；
掌握树的存储结构、树、二叉树和森林之间的转换、哈夫曼树（ Huffman）算法及其应用（哈夫曼编码）。
重点：二叉树的概念、二叉树的性质、完全二叉树、满二叉树的概念和特点；二叉树的遍历。
难点：遍历过程、线索树的线索方法。
7．图
熟练掌握图的定义，术语、图的存贮结构、图的两种遍历方法；
掌握最小生成树的 Kruskal和Prim两种生成过程，掌握Prim算法。
掌握拓扑排序、最短路径、关键路径的算法思想。
重点：图的定义，术语、图的存贮结构、图的两种遍历方法；
难点：拓扑排序、最短路径、关键路径的算法思想。
8．排序
熟练掌握插入排序、快速排序、选择排序、堆排序、归并排序和基数排序的思想、算法、时间和空间复杂度；
会对各种内部排序方法进行时间和空间复杂度的比较；
熟悉外部排序方法。
重点：插入排序、快速排序、选择排序、堆排序、归并排序和基数排序的思想、算法、时间和空间复杂度分析。
难点：各排序方法的使用情况和比较。
9．检索
熟练掌握顺序检索、二分检索、分块检索、散列表的检索的方法；掌握顺序检索中监视哨的作用。
掌握散列的基本思想、处理冲突常用的方法；掌握用除余法构造散列函数的方法、掌握用开放地址法（重点：线性探测再散列）和拉链处理冲突的方法；
掌握二叉排序树、平衡二叉排序树的概念；掌握二叉排序树、熟悉平衡二叉排序树构造方法。
熟悉 B_树的概念。
重点：各种检索的思想、算法、时间和空间复杂度分析。
难点：二叉排序树构造机删除方法、平衡二叉排序树构造方法。
10．文件
熟悉顺序文件、索引文件、直接存取文件和多关键字文件的概念。
五、实验课时分配表
序号
实 验 项 目
课时
备注
1
线性表的顺序存储结构基本运算实现
2
2
线性表的链式存储结构基本运算实现
2
3
栈与队列基本运算实现
2
综合实验
4
*稀疏矩阵的运算实现
2
5
二叉树的建立与基本运算实现
2
6
*二叉树中求树高度等运算实现
2
综合实验
7
图基本运算实现
2
8
排序
2
9
检索
2
合 计
18
主要仪器设备附表
序 号
名称
数量（台套）
备 注
1
计算机
每人一台（ 80台套）
TC集成环境
六、大纲说明及教学方法建议
1．在教学内容的组织上应从静态，半静态到动态等，体现出由易到难，循序渐近的教学原则，使学生入门容易，并用实验加深和巩固学生所学的知识。
2．在讲解中，需要把数据结构的说明与某种现有程序设计语言实现数据结构加以区别，并且应该集中描述数据结构的功能。
3．除了对每种结构应用算法的讲解外，还应讨论资源即时间和空间的利用，应使学生能对这些因素进行分析。
4．注重培养学生使用数据结构编写实际应用中的问题，提高学生综合素质。
5．对带有“*”的章节可根据实际情况处理。