课程编号15101102数据结构教学大纲

1、 课程编号15101102数据结构教学大纲ata Structure 一、课程基本信息课程编号15101102适用专业教育技术学、信息工程总学时数51实验学时18课程类别学科基础课教 研 室网络与计算机课程学分3上机学时课程性质必修课编 写 人黄海军讲授学时36课外学时8开课学期3编写时间2006年7月周学时数3见习学时二、课程教学目标数据结构在计算机科学中是一门综合性的专业基础课。目前在我国，数据结构不仅仅是计算机专业的教学计划中的核心课程之一，而且是其它非计算机专业的主要选修课程之一，作为教育技术学专业和和信息工程专业，也需要较强的计算机专业知识，数据结构对于后续专业课程的学习非常重要。三

2、、教学基本要求本课程系统地介绍数据结构的基本概念、操作及典型应用例子。通过课堂教学、课外练习和上机实习，使学生了解不同数据结构的特性，学会数据组织的方法，能根据所研究的具体问题的要求选择适当的数据结构、存储结构和相应的算法，并初步掌握算法的时间复杂度和空间复杂压的基本分析方法以及良好的程序设计技能，为后续课程的学习和科研工作的参与打下扎实的基础。 1、熟练掌握：要求学生能够全面、深入理解和熟练掌握所学内容，并能够用其知识分析、设计和解答相关的应用问题。 2、掌握：要求学生能够较好地理解和掌握，并且能够做简单的分析。 3、了解：要求学生能够一般地了解的所学内容。考核方法：本课采用平时10%+实验

3、20%+闭卷30%，为考核成绩，百分制。四、本课程的先导课程本课程的先导课程为高级语言程序设计课程，同时为数据库原理与应用、面向对象程序设计等后续专业课程的学习打下基础。五、教学方法与手段1、以课堂讲授为主，适应增加一些课堂讨论。2、采用多媒体教学手段进行教学。3、理论教学与上机教学相结合，提高学生的动手实践能力。六、考核方式与成绩评定办法本课程成绩为平时、上机、期末三部分组成，其中平时占，上机占，期末占。如果上机采用抽考形式，则可作如下调整：平时占，上机占，期末占，具体评定办法见本课程的考试大纲。七、使用教材及参考书目【使用教材】1、严蔚敏、吴伟民 编著，C语言版数据结构，清华大学出版社 2

4、006年2、严蔚敏、吴伟民 编著，C语言版数据结构题集，清华大学出版社 【参考书目】1、张乃孝 编著，C语言版算法与数据结构，高等教育出版2、Robert .Kruse, C.L.Tondo, Bruce Leung,Data Structures & program design in C2nd Edition, 清华大学出版社影印3、李春堡等编，数据结构习题与解析，清华大学出版社2000.1 4、蔡子经、施伯乐等编，数据结构教程，复旦大学出版社 1994 12八、课程结构和学时分配章节章节名称讲授学时辅导学时课外学时作业(数量）备注第一章绪论24第二章线性表6224第三章栈和队列4224第

5、四章串24第五章数组与广义表224第六章树和二叉树8228第七章图6226第八章查找22第九章排序424机动（4）共计36812九、教学内容第一章绪论（学时）【教学目标】、了解：什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系。、了解：什么是数据类型、抽象数据类型、数据结构的逻辑结构、存储结构和数据运算三方面的概念及相互关系。、了解：算法的定义、算法的特性、算法的时间代复杂度、算法的空间复杂度。、熟练掌握：用C语言描述算法的方法，能够使用C语言编写程序。【重点难点】 重点是了解数据结构的逻辑结构、存储结构及数据的运算三方面的概念及相互关系。 难点是

6、算法复杂度的分析方法【教学内容】第一节什么是数据结构 第二节基本概念和术语。第三节抽象数据类型的表示与实现第四节算法和算法分析量一、算法. 二、算法设计的要求 三、算法效率的度量四、算法的存储空间需求第二章线性表（学时）【教学目标】、了解：顺序表的含义及特征。、了解：单链表的结构、特点。带表头结点的单链表的优点和类定义及相应操作的实现。、了解：链表动态链表和静态链表之分。链表有单链表、循环单链表、双向链表之分。、了解：循环链表的特点，循环链表的类定义，以及用循环链表解决问题的方法。、熟练掌握：顺序表和单链表的插入和删除算法。、熟练掌握：顺序表和单链表上实现的各种基本算法及相关的时间性能分析，解

7、决简单应用的问题。【重点难点】 重点是熟练掌握顺序表和单链表上实现的各种基本算法及相关的时间性能分析。 难点是能够使用本章所学到的基本知识设计有效算法解决与线性表相关的应用问题。【教学内容】第一节 顺序表的类型定义第二节 线性表的顺序表示和实现第二节线性表的链式表示和实现一、线性链表. 二、循环链表 三、双向链表*第三节一元多项式的表示及其相加（选讲）第三章栈和队列（学时）【教学目标】、熟练掌握：栈的定义、特性和栈的抽象数据类型，栈的顺序表示、链表表示以及相应操作的实现。特别注意栈空和栈满的条件。、了解：迷宫问题的递归求解思路及如何利用栈实现迷宫问题的非递归解法。、熟练掌握：队列的定义、特性和

8、队列的抽象数据类型，队列的顺序表示、链表表示以及相应操作的实现。特别是循环队列中队头与队尾指针的变化情况。【重点难点】 重点是掌握栈和队列在两种存储结构上实现的基本运算。 难点是循环队列中对边界条件的处理。【教学内容】第一节栈一、栈的抽象数据类型的定义. 二、栈的表示和实现 第二节栈的应用举例一、数制转换. 二、括号匹配的检验 三、行编辑程序四、迷宫求解五、表达式求解*第三节栈与递归的实现(选讲)第四节队列一、抽象数据类型的定义. 二、链队列 三、循环队列*第五节离散事件模拟(选讲)第四章串（学时）【教学目标】、了解：串类型的定义。、了解：串的存储表示。、掌握：串的逻辑结构、存储结构。、掌握：

9、串的基本算法。【重点难点】 重点是掌握串上实现的模式匹配算法。 难点是掌握串上实现的模式匹配算法。【教学内容】第一节串的类型定义第二节串的表示和实现一、定长顺序存储表示. 二、堆分配存储表示 三、串的块存储表示*第三节串的模式匹配算法（选讲）一、求子串位置的定位函数 二、模式匹配的一种改进算法 第五章数组和广义表（学时）【教学目标】、作为抽象数据类型的数组的定义，数组的按行顺序存储与按列顺序存储。、了解：数组的定义，数组的顺序表示和实现、了解：稀疏矩阵的定义及其数组实现。、了解：广义表的定义及其实现方法。、掌握：多维数组的存储方式、矩阵的压缩存储方式。、掌握：广义表的定义及其求表头和表尾的运算

10、。、掌握：稀疏矩阵的压缩存储表示下实现的算法。【重点难点】 重点是熟悉多维数组的存储方式、矩阵的压缩存储方式、广义表的定义及其求表头和表尾的运算。 难点是稀疏矩阵的压缩存储表示下实现的算法。【教学内容】第一节数组的定义第二节数组的顺序表示和实现第三节矩阵的压缩存储一、特殊矩阵 二、稀疏矩阵第四节广义表第五节广义表的存储结构*第六节m元多项式的表示(选讲)*第七节广义表的递归算法（选讲）一、求广义表的深度. 二、复制广义表 三、建立广义表的存储结构第六章树和二叉树（学时）【教学目标】、了解：树和森林的概念。包括树的定义、树的术语、树的抽象数据类型。、掌握：二叉树的概念、性质及二叉树的表示。、熟练

11、掌握：二叉树的遍历方法。、掌握：线索化二叉树的特性及寻找某结点的前驱和后继的方法。、掌握：树与森林的实现，重点在用二叉树实现。、掌握：森林与二叉树的转换；树的遍历算法。、掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法。、掌握：赫夫曼树的实现方法、构造赫夫曼编码的方法及带权路径长度的计算。 【重点难点】 重点是掌握二叉树的遍历算法及其有关应用。 难点是使用本章所学到的有关知识设计出有效算法，解决与树或二叉树相关的应用问题。【教学内容】第一节树的定义和基本术语第二节二叉树一、二叉树的定义 二、二叉树的性质 三、二叉树的存储结构第三节遍历二叉树和线索二叉树一、遍历二叉树. 二、线索二叉树

12、第四节树和森林一、树的存储结构. 二、森林与二叉树的转换 三、树和森林的遍历*第五节树与等价问题(选讲)第六节赫夫曼树及其应用一、最优二叉树（赫夫曼树） 二、赫夫曼编码 *第七节回溯与树的遍历(选讲)*第八节树的计数 第七章图（学时）【教学目标】、理解：图的基本概念和图的抽象数据类型。、掌握：图的3种存储表示：邻接矩阵、邻接表和邻接多重表。对于前两种，要求掌握典型操作，如构造、求根、找第一个邻接顶点、找下一个邻接顶点等操作的实现算法。、熟练掌握：图的两种遍历算法与求解连通性问题的方法。包括深度优先搜索和广度优先搜索算法、求连通分量的方法(不要求算法)。、掌握：构造最小生成树的Prim算法和Kr

13、uskal算法，要求理解算法。、理解：如何用Dijkstra方法求解单源最短路径问题(不要求算法)。、熟练掌握：活动网络的拓扑排序算法。、掌握：求解关键路径的方法。【重点难点】 重点是图的数组和邻接表存储方法，以及图的深度优先和广度优先搜索算法，了解图的有关应用问题及算法。 难点是使用本章所学到的有关知识设计出有效算法，解决与图相关的应用问题。【教学内容】第一节图的定义和基本术语第二节图的存储结构一、数组表示法. 二、邻接表三、十字链表四、邻接多重表第三节图的遍历一、深度优先搜索 二、广度优先搜索第四节图的连通性问题一、无向图的连图分量 *二、有向图的连通分量(选讲) 三、最小生成树*四、关节

14、点与重连通分量(选讲)第五节 有向无环图及其应用一、拓扑排序 二、关键路径第六节 最短路径一、从某个源点到其余各顶点的最短路径 二、每一对顶点之间的最短路径第九章查找（学时）【教学目标】、了解：AVL树的平衡化旋转、构造、插入、删除时的调整方法及其性能分析。、了解：哈希表的定义。、熟练掌握：静态查找表的顺序搜索和折半搜索算法及其性能分析方法。、掌握：二叉排序树的表示、搜索、插入、删除算法及其性能分析方法。、熟练掌握：散列法，包括散列函数的构造、解决冲突的方法。【重点难点】 重点是顺序查找、二分查找，二叉查找树上查找以及哈希表上查找的基本思想和算法实现。 难点是二叉查找树的删除算法及B树上的插入和删除算法，后者可根据学生情况作选讲内容。【教学内容】第一节静态查找表一、顺序表的查找 二、有序表的查找 *三、静态树表的查找(选讲)四、索引顺序表的查找第二节动态查找表一、二叉排序树和平衡二叉树（AVL树）*二、和树(选讲) *三、键树（选讲）第三节哈希表一、什么是哈希表 二、哈希函数的构造方法 三、处理冲突的方法四、哈希表的查找及其分析第十章排序（4学时）【教学目标】、掌握：排序的基本概念和性能分析方法。、