“数据结构”课程教学大纲

数据结构教学大纲和安排

第一部分 大纲说明

一、课程的性质和任务

“数据结构”是计算机科学与技术专业本科生的一门必修课程。本课程介绍如何组织各种数据在计算机中的存储、传递和转换。内容包括：数组、链接表、栈和队列、递归、树与森林、图、堆与优先级队列、集合与搜索结构、排序、索引与散列结构等。课程采用面向对象的观点讨论数据结构技术，并以兼有面向过程和面向对象双重特色的C++语言作为算法的描述工具，强化数据结构基本知识和面向对象程序设计基本能力的双基训练。为后续计算机专业课程的学习打下坚实的基础。

二、先修课要求

C语言程序、离散数学。

三、课程的教学基本要求

1、掌握重要数据结构的概念、使用方法及实现技术；

2、学会做简单的算法分析，包括算法的时间代价和空间代价。

四、教学方法

授课为主，结合作业和答疑，进行必要的上机实验。

五、课程教学要求的层次

1、熟练掌握：要求学生能够全面、深入理解和熟练掌握所学内容，并能够用其知识分析、设计和解答相关的应用问题。

2、掌握：要求学生能够较好地理解和掌握，并且能够做简单的分析。 3、了解：要求学生能够一般地了解的所学内容。

第二部分 授课计划初步方案

一、学时分配

课程教学总学时数为 80学时，4学分，其中讲授学时60，实验20

教 学 内 容 讲授学时 实验学时 2学时 2学时 2学时 2学时 4学时 2学时 4学时 2学时 一、数据结构基本概念及算法分析 6学时 二、数组 4学时 三、链表 4学时 四、栈和队列 4学时 五、递归 4学时 六、树与森林 10学时 七、集合与搜索 6学时 八、图 8学时 九、排序 8学时 十、索引与散列结构 6学时

二、教学环节

1、教学 本课程是计算机专业基础课，内容多且带有一定的抽象性，学习起来有一定难度。为保证教学效果，主要内容用课堂讲授的方式完成。使学生能够很快掌握课程的主要知识和解决问题的方法。

2、作业和答疑

本课程教学过程中，作业和答疑是必不可少的教学环节。 3、研究形学习和上机操作

研究形学习和上机操作是获取知识的重要手段。教师讲课只是起到抛砖引玉的作用，关键还在于学生的研究形学习和上机操作。为达到研究形学习的效果，除读懂教科书中所讲内容外，还需大量阅读其他参考资料和做题。其目的是要通过阅读、做题弄懂、加深对概念的理解，提高程序设计，解决问题的能力。为此，安排一定的实验上机学时。要求学生珍惜实验机时，真正做到学有所获。

学生在上机做实验前，应事先将程序、调试数据、上机操作顺序准备好，并提前使用这些调试数据人工执行过。目的是提高上机的效率和成功率，严禁抄袭

２

或拷贝他人的成果，自觉培养科学、严谨的作风。

除学校提供的时间外，要求课外学生利用自己可能拥有的计算机条件，完成更多的练习，不通过大量的实践，能力和知识水平得不到有效得提高。

4、考试

考试是对学生掌握知识水平的检验。要求考试内容紧扣大纲要求，既要能够检验学生的掌握情况，又要体现水平。学生的本课程成绩按平时作业满分20分，期末考试满分80分分配，合计计算。

第三部分 教学内容和教学要求

一、数据结构基本概念及简单的算法分析 6学时

1、教学内容： 什么是数据结构

抽象数据类型及面向对象概念：数据类型；数据抽象与抽象数据类型；面向对象的概念；用于描述数据结构的语言

数据结构的抽象层次 算法定义

性能分析与度量：算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法；渐进的空间复杂度

C＋＋面向对象编程

面向对象、C＋＋的类、C＋＋的输出输入、模板。 2、教学要求：

了解：什么是数据、数据对象、数据元素、数据结构、数据的逻辑结构与物理结构、逻辑结构与物理结构间的关系

了解：什么是数据类型、抽象数据类型、数据抽象和信息隐蔽原则。了解什么是面向对象

了解：算法的定义、算法的特性、算法的时间代价、算法的空间代价 掌握：用C++语言描述算法的方法，能够使用C++语言编写程序

二、数组

4学时

1、教学内容：

作为抽象数据类型的数组：数组的定义和初始化；作为抽象数据类型的数组；数组的顺序存储方式

３

顺序表：顺序表的定义和特点；顺序表的类定义；顺序表的查找、插入和删除；使用顺序表的事例

字符串：字符串的抽象数据类型；字符串操作的实现；字符串的模式匹配 2、教学要求：

了解：线性表的逻辑结构特性，以及线性表的两种存储实现方式

了解：作为抽象数据类型的数组的定义，数组的按行顺序存储与按列顺序存储

熟练掌握：顺序表的定义与实现，包括搜索、插入、删除算法的实现及其平均比较次数的计算，掌握应用顺序表作为集合的简单操作

了解：稀疏矩阵的定义及其数组实现 熟练掌握：字符串的定义及实现 三、链表

4学时

1、教学内容：

单链表：单链表的结构；单链表的类定义；单链表中的插入与删除；带表头结点的单链表；用模板定义的单链表类；静态链表

循环链表：循环链表的类定义；用循环链表解约瑟夫问题； 多项式及其相加：多项式的类定义；多项式的加法 双向链表

2、教学要求：

了解：链表与数组一样，是一种实现级结构。有动态链表和静态链表之分 了解：链表有单链表、循环单链表、双向链表之分 了解：单链表的结构、特点

掌握：单链表的类定义、构造函数、单链表的插入与删除算法 了解：带表头结点的单链表的优点和类定义及相应操作的实现 熟练掌握：用模板定义的单链表类

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

掌握：双向链表的特点，双向链表的类定义及相关操作的实现，用双向链表解决问题的方法。

４

四、栈和队列

4学时

1、教学内容：

栈：栈的抽象数据类型；栈的顺序存储表示；栈的链接存储表示 表达式求值：中缀表达式求值；中缀表示到后缀表示的转换

队列 ：队列的抽象数据类型；队列的顺序存储表示；队列的链接存储表示；队列的应用举例

优先级队列：优先级队列的定义；优先级队列的存储表示 2、教学要求：

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

了解：在表达式计算时栈是如何使用的，重点了解用后缀表示计算表达式及中缀表示改后缀表示的方法和算法思路

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

掌握：优先级队列的定义、特性和优先级队列的抽象数据类型，优先级队列的插入与删除算法

五、递归

4学时

1、教学内容：

递归的概念：递归问题的求解

递归过程与递归工作栈：单向递归和尾递归的迭代实现；一般递归问题利用栈实现非递归解法

广义表：广义表的概念；广义表的表示及操作；广义表存储结构的实现；广义表的访问算法；广义表的递归算法

2、教学要求：

掌握：递归的概念。包括什么是递归，有那些种类的递归，递归问题的递归求解方法

掌握：递归过程的机制与利用递归工作栈实现递归的方法

了解：迷宫问题的递归求解思路及如何利用栈实现迷宫问题的非递归解法 掌握：利用递归解决问题的分治法和回溯法 掌握：广义表的定义及其实现方法 掌握：广义表的递归算法

５

六、树与森林

10学时

1、教学内容：

树和森林的概念：树的定义；树的术语；树的抽象数据类型

二叉树：二叉树的定义；二叉树的性质；二叉树的抽象数据类型 二叉树的表示：顺序表示；二叉链表表示

遍历二叉树：中序遍历；前序遍历；后序遍历；应用二叉树遍历的事例；二叉树的计数

线索化二叉树：线索；中序线索化二叉树

堆：堆的定义；堆的建立；堆的插入与删除；堆的调整算法

树与森林：树的存储表示；森林与二叉树的转换；遍历树；遍历森林 霍夫曼树：路径长度；霍夫曼树；霍夫曼编码 2、教学要求：

了解：树和森林的概念。包括树的定义、树的术语、树的抽象数据类型 掌握：二叉树的概念、性质及二叉树的表示 熟练掌握：二叉树的遍历方法

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

熟练掌握：堆的定义，堆的建立、堆的插入与删除、堆的向上和向下调整等算法以及用来实现优先级队列的方法

掌握：树与森林的实现，重点在用二叉树实现 掌握：森林与二叉树的转换；树的遍历算法

掌握：二叉树的计数方法及从二叉树遍历结果得到二叉树的方法

掌握：霍夫曼树的实现方法、构造霍夫曼编码的方法及带权路径长度的计算

七、集合与搜索 6学时

1、教学内容：

集合及其表示：集合基本概念；以集合为基础的抽象数据类型；用位向量实现集合抽象据类型；

用有序链表实现集合的抽象数据类型。 并查集：并查集的定义；并查集的实现。

简单的搜索结构：搜索的概念；静态搜索结构；顺序搜索；基于有序顺序表的顺序搜索和折半搜索。

二叉搜索树：二叉搜索树的定义；二叉搜索树上的搜索；二叉搜索树的插入；二叉搜索树的删除。

AVL树：AVL树定义；平衡化旋转；AVL树的插入和删除；AVL树高度。 2、教学要求：

６

掌握：集合的基本概念及其表示方法，包括位数组及有序链表的表示及其相关操作的实现算法。

掌握：利用并查集实现集合的方法。

熟练掌握：静态搜索表的顺序搜索和折半搜索算法及其性能分析方法。

熟练掌握：二叉搜索树的表示、搜索、插入、删除算法及其性能分析方法。 掌握：AVL树的平衡化旋转、构造、插入、删除时的调整方法及其性能分析。

八、图 8学时

1、教学内容：

图的基本概念：图的基本概念；图的抽象数据类型。 图的存储表示：邻接矩阵；邻接表；邻接多重表。

图的遍历与连通性：深度优先搜索；广度优先搜索；连通分量；关节点与重连通分量。

最小生成树：kruskul算法；prim算法。 单源最短路径问题：dijkstra算法。

活动网络：AOV网络与拓扑排序；AOE网络与关键路径。 2、教学要求：

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

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

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

理解：求解关节点及构造重连通图的方法(不要求算法)。

掌握：构造最小生成树的Prim算法和Kruskal算法，要求理解算法。 理解：如何用Dijkstra方法求解单源最短路径问题。 熟练掌握：活动网络的拓扑排序算法。 掌握：求解关键路径的方法。

九、排序 8学时

1、教学内容：

插入排序：直接插入排序；折半插入排序；链表插入排序；希尔排序。 交换排序：起泡排序；快速排序。

７

选择排序：直接选择排序；锦标赛排序；堆排序。

归并排序：归并；迭代的归并排序算法；递归的链表归并排序 基数排序：多关键码排序；链式基数排序

外排序：外排序的基本过程；k路平衡归并；初始归并段的生成；最佳归并树。 2、教学要求：

掌握：排序的基本概念和性能分析方法。

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

了解：基数排序方法及其性能分析方法。

掌握：多路平衡归并等外排序方法及败者树构造方法。 掌握：生成初始归并段及败者树构造方法。 掌握：最佳归并树的建立方法。

十、索引与散列结构 6学时

1、教学内容：

静态索引结构：线性索引；倒排索引；m路静态查找树。

动态索引结构：动态的m路查找树；B树的定义；B树的插入；B树的删除；B+树。

散列：散列表与散列方法；散列函数；处理溢出的闭散列方法；处理溢出的开散列方法；散列表分析。 2、教学要求：

熟练掌握：静态索引结构，包括线性索引、倒排索引、静态索引树的搜索和构造方法。

熟练掌握：动态索引结构，包括B树、B+树的搜索和构造方法。 熟练掌握：散列法，包括散列函数的构造、解决冲突的方法。

８