《数据结构》课程教学大纲
课程名称：数据结构
课程编号：112052
课程性质：职业能力必修课
先修课程：C语言程序设计
并修课程：无
参考资料：
1.郭福顺, 廖明宏, 李莲治. 数据结构与算法基础. 大连：大连理工大学出版社. 2000年6月
2.李益明, 邓文华. 数据结构(C语言版). 北京：电子工业出版社. 2003年
3.孙凌, 李丹. 数据结构. 北京：人民邮电出版社. 2003年
课 时：64（理论46 实验16 机动2）
周 学 时：4
总 学 分：4
适用专业：计算机应用技术、计算机系统维护
知识结构：理论知识（60%）+实践能力（40%）
成绩分配：
总成绩（100%）＝平时成绩（15%）＋实验成绩（35%）+期末成绩（50%）
期末成绩（50%）＝笔试
教学目标：
本课程以理论和实际应用相结合，通过本课程的学习，了解数据结构的内容，理解线性结构、树结构及图结构的逻辑结构及其最适合的应用领域；掌握线性结构、树结构的应用及查找、排序算法的实现。本课程的基本要求如下：
1.了解数据结构的基本概念及术语
2.掌握线性表的顺序表示和实现
3.掌握线性表的链式表示和实现
4.掌握栈、队列的表示及应用
5.掌握数组的表示及实现
6.了解树的基本概念，掌握树的表示及应用
7.了解图的结构、遍历及应用领域
8.理解查找算法的机理，掌握查找算法的应用
9.理解排序算法的机理，掌握排序算法的实现
附表一：
理论教学课时分配
序号 |
内 容 |
理论课时 |
1 |
绪论 |
2 |
2 |
线性表 |
8 |
3 |
栈和队列 |
4 |
4 |
数组 |
2 |
5 |
树和二叉树 |
10 |
6 |
图 |
10 |
7 |
查找 |
4 |
8 |
内部排序 |
6 |
9 |
机动学时 |
2 |
合计 |
|
48 |
附表二：
实践教学课时分配
序号 |
内 容 |
实验课时 |
1 |
线性表 |
2 |
2 |
栈和队列 |
4 |
3 |
树和二叉树 |
2 |
4 |
图 |
4 |
5 |
查找 |
2 |
6 |
内部排序 |
2 |
合计 |
|
16 |
第一章、绪论
（一）教学目的： 了解数据结构的基本概念和术语；理解抽象数据类型的表示与实现；领会算法及算法分析的基本方法及意义。
（二）教学重点： 数据结构的基本概念和术语；抽象数据类型；算法及算法分析。
（三）教学难点： 抽象数据类型，算法及算法分析。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.什么是数据结构、数据、数据类型及与此有关的概念
2.什么是算法及算法的重要特性
3.算法的分析方式
4.算法的分析手段
（六）学时分配： 2学时。
第二章、线性表
（一）教学目的： 理解线性表的特点及实质，掌握线性表的应用。
（二）教学重点： 线性表的结构及操作方法。
（三）教学难点： 线性表的应用。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.线性表的定义及逻辑结构
2.对线性表常用的基本操作
3.线性表的顺序存储结构及部分操作的实现和性能分析
4.线性表的链序存储结构及部分操作的实现和性能分析
5.静态链表的算法特点
6.循环链表和双向链表的特点
（六）学时分配： 8学时。
第三章、栈和队列
（一）教学目的： 了解栈和队列的操作特点，掌握栈和队列的应用。
（二）教学重点： 栈和队列的表示和实现。
（三）教学难点： 栈和队列的应用。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.栈的定义及性质
2.栈的表示及实现
3.栈的应用
4.队列的定义及性质
5.队列的链式存储结构
6.队列的顺序存储结构----循环队列
（六）学时分配： 4学时。
第四章、数组
（一）教学目的： 掌握数据的顺序表示和实现；理解矩阵的压缩存储。
（二）教学重点： 数组的实现。
（三）教学难点： 矩阵的压缩存储。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.数组的定义
2.数组的顺序表示和实现
3.矩阵的压缩存储
（六）学时分配： 2学时。
第五章、树和二叉树
（一）教学目的： 了解树的定义和基本术语；理解二叉树定义、性质、存储结构；掌握二叉树操作及应用。
（二）教学重点： 二叉树的操作及应用。
（三）教学难点： 二叉树的操作及应用。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.树的结构定义和基本操作
2.二叉树的定义及性质
3.二叉树的存储结构
4.遍历二叉树和线索二叉树
5.树和森林定义及二叉树的关系
6.哈夫曼树及其应用
（六）学时分配： 10学时。
第六章、图
（一）教学目的： 理解图的定义和术语，掌握图的存储结构、图的遍历，了解最短路径问题。
（二）教学重点： 图的术语及图存储结构。
（三）教学难点： 图的存储结构、图的遍历。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.图的定义和术语
2.图的存储结构
3.图的遍历
4.图的连通性
5.有向无环图及其应用
6.最短路径问题
（六）学时分配： 10学时。
第七章、查找
（一）教学目的： 了解查找的概念和术语，掌握常见的查找算法。
（二）教学重点： 查找算法原理。
（三）教学难点： 查找算法的应用。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.基本概念和术语
2.静态查找表
3.动态查找表
4.哈希表
（六）学时分配： 4学时。
第八章、内部排序
（一）教学目的： 领会各种排序算法的机制，掌握排序算法编码。
（二）教学重点： 插入、交换、选择、归并四种排序算法的原理及应用。
（三）教学难点： 插入、交换、选择、归并四种排序算法的原理及应用。
（四）讲授方式： 讲授、演示。
（五）教学内容：
1.概念及术语
2.插入排序
3.交换排序-----快速排序
4.选择排序
5.归并排序
（六）学时分配： 6学时。
实验一、线性表
（一）实验目的：
1．掌握顺序存储结构的特点。
2．掌握顺序存储结构的常见算法。
（二）实验内容：
1．建立顺序表(可利用随机产生的数据)，建立递增顺序表(可利用随机产生的数据)。
2．实现该顺序表的遍历。
3．在顺序表中查找某一元素，若找到则返回该元素的序号。
4．在顺序表的指定位置插入元素。
5．删除顺序表中的指定元素。
6．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。
7．输入整型元素序列利用有序表插入算法建立一个有序表。
8．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。
9．编写一个主函数,调试上述算法。
（三）实验学时：2学时。
（四）实验分阶：
基础：能完成顺序表的建立操作
提高：能完成算法6并调试出程序
实验二、栈和队列
（一）实验目的：
1．掌握栈、队列的思想及其存储实现。
2．掌握栈、队列的常见算法的程序实现。
（二）实验内容：
1．采用链式存储实现栈的初始化、入栈、出栈操作。
2．采用顺序存储实现栈的初始化、入栈、出栈操作。
3．采用链式存储实现队列的初始化、入队、出队操作。
4．在主函数中设计一个简单的菜单，分别测试上述算法。
（三）实验学时：2学时。
（四）实验分阶：
基础：能完成栈和队列的建立操作
提高：能完成各种存储结构的操作并调试出程序
实验三、树和二叉树（一）
（一）实验目的：
1．掌握二叉树的存储实现。
2．理解并掌握二叉树的创建与遍历过程。
（二）实验内容：
1．输入字符序列，先序建立二叉链表。
2．中序遍历二叉树：非递归算法。
3．后序遍历二叉树：非递归算法。
4．求二叉树的高度 。
5．求二叉树的叶子个数。
（三）实验学时：2学时
（四）实验分阶：
基础：能完成二叉树的建立操作
提高：能完成二叉树的基本操作并调试出程序
实验四、树和二叉树（二）
（一）实验目的：
1.掌握二叉树的常用算法的程序实现。
（二）教学内容：
1.递归算法实现二叉树的先序、中序、后序遍历。
2.利用二叉树实现某一序列元素的排序。
3.借助链表实现二叉树的层次遍历。
（三）实验学时：2学时
（四）实验分阶：
基础：能完成二叉树的建立操作
提高：能完成二叉树的先序、中序、后序遍历并调试出程序
实验五、图
（一）实验目的：
1．掌握图的存储思想及其存储实现。
2．掌握图的深度、广度优先遍历算法思想及其程序实现。
3．掌握图的常见应用算法的思想及其程序实现。
（二）实验内容：
1．键盘输入数据，建立一个有向图的邻接表。
2．输出该邻接表。
3．在有向图的邻接表的基础上计算各顶点的度，并输出。
4．以有向图的邻接表为基础实现输出它的拓扑排序序列。
5．采用邻接表存储实现无向图的广度优先遍历。
6．在主函数中设计一个简单的菜单，分别调试上述算法。
（三）实验学时：4学时。
（四）实验分阶：
基础：键盘输入数据，建立一个有向图的邻接表并输出该邻接表。
提高：采用邻接表存储实现无向图的广度优先遍历。在主函数中设计一个简单的菜单，分别调试上述算法
实验六、查找
（一）实验目的：
1．掌握折半查找算法的思想及程序实现。
（二）实验内容：
1.利用实验一建立有序表，采用折半查找实现某一已知的关键字的查找。
（三）实验学时：2学时。
（四）实验分阶：
基础：能建立有序表并能理解折半查找方法
提高：实现折半查找程序
实验七、内部排序
（一）实验目的：
1、掌握常见的排序算法的思想及其适用条件。
2、掌握常见的排序算法的程序实现。
（二）实验内容：
输入一组关键字序列分别实现下列排序：
1. 实现简单选择排序。
2. 实现直接插入排序。
3．实现快速排序算法。
4．在主函数中设计一个简单的菜单，分别测试上述算法。
5．大作业：采用几组不同数据测试算法1—算法4的比较次数和移动次数。
（三）实验学时：2学时。
（四）实验分阶：
基础：完成一到两种排序方法
提高：在主函数中设计一个简单的菜单，分别测试上述算法。并采用几组不同数据测试算法1—算法4的比较次数和移动次数。
