数据结构Ⅱ教学大纲

1、数据结构（n）教学大纲编写人：董凯宁编写时间：2005年10月30日课程基本信息课程名称：数据结构（H）DataStructure（II）课程号：40128830课程类别：专业课学时：48学分：3二、教学目的及要求数据结构概论，从抽象数据类型的角度讨论线性表、栈、队列，串、数组、广义表，树、二叉树和图等基本类型的数据结构及其应用，抽象数据类型的常用表示方法，操作系统和编译程序中涉及的动态存储管理的基本技术，查找、内部排序，外部排序，置换-选择排序，文件的概念，文件结构，索引顺序存取方法。三、教学内容第1章绪论（共3学时）1.1 什么是数据结构（0.5学时）教学内容：由数学方程无法描述的非数值计

2、算问题引出数据结构表、图、树的3种实例，阐述数据结构的概念，数据结构的内涵和特点，数据结构所处的学科地位，数据结构的学科背景、起源、发展和现状；要求学生掌握数据结构的概念，能辨别数学模型中数学方程和表、图、树等数据结构的区别。1.2 基本概念和术语（1学时）教学内容：阐述本课使用的一些基本概念，包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构、逻辑结构、物理结构、存储结构、位、元素、结点、数据域、顺序映像、非顺序映像、顺序存储结构、链式存储结构、指针、虚拟存储结构、数据类型、原子类型、结构类型、抽象数据类型、固定聚合类型、可变聚合类型、多形数据

3、类型；要求学生掌握包括数据、数据元素、数据项、数据对象、数据结构、集合、结构、线性结构、树形结构、图状结构、网状结构等在内的所有基本概念。1.3 抽象数据类型的表示与实现（0.5学时）教学内容：阐述在C语言中，抽象数据类型的常用表示方法，包括预定义常量和类型、数据结构的表示用类型定义（typedef）描述、函数表示法、各种赋值语句、选择语句、结束语句、输入和输出语句、基本函数、逻辑运算约定；要求学生了解抽象数据类型的描述语言、构成方法，掌握抽象数据类型的类C语言11种表示方法。1.4 算法与算法分析（1学时）1.4.1 算法教学内容：阐述算法的定义，算法的5个重要特征：有穷性、确定性、可行性、

4、输入、输出；要求学生掌握算法的定义，理解算法的5个重要特征。1.4.2 算法设计要求教学内容：阐述好算法设计的4个要求一一即正确性、可读性、强壮性和效率与低存储量需求；要求学生理解好算法设计的4个要求。1.4.3 算法效率的度量教学内容：阐述算法效率的2种度量方法：事前统计的方法和事后分析估算的方法，时间复杂度的概念，频度的概念；要求学生掌握时间复杂度的概念，频度的概念。1.4.4 算法的存储空间需求教学内容：阐述空间复杂度的概念，空间复杂度的表示法，算法原地工作的概念；要求学生掌握空间复杂度的概念，了解算法原地工作的概念。第2章线性表（共4学时）4.1 线性表的类型定义（0.5学时）教学内容

5、：阐述线性结构的特点，线性表的抽象数据类型定义，数据项、记录、文件的定义，实例说明线性表的插入、删除、归并等操作方式，并对算法做相应的分析；要求学生掌握线性表的概念和抽象数据类型定义。4.2 线性表的顺序表示和实现（重点）（1.5学时）教学内容：阐述线性表的顺序表示的概念，顺序映像的方式，顺序映像的随机存取特性，实例描述线性表在顺序存储表示时进行插入、删除、合并操作的几种算法；要求学生掌握线性表的顺序表示的概念和顺序映像的方式，理解线性表在顺序存储结构时的插入、删除、合并等操作方法。4.3 线性表的链式表示和实现（重点）（1.5学时）4.3.1 线性链表教学内容：阐述线性链表的概念、构成方式，

6、结点、数据域、指针域、指针、链、链表、头指针、头结点和静态链表的概念，线性链的表示法，实例算法说明单链表的插入、删除、合并操作处理算法，静态链表的算法；要求学生掌握线性有序链表的概念、与之相关的名词概念，理解单链表的插入、删除、合并操作算法过程。4.3.2 循环链表教学内容：阐述循环链表的概念，循环链表的操作特点；要求学生掌握循环链表的概念。4.3.3 双向链表教学内容：阐述双向链表的概念和特点，双向链表的抽象数据类型定义，双向链表的几种操作算法；要求学生掌握双向链表的概念，理解双向链表的抽象数据类型定义，理解双向链表的操作算法。4.4 一元多项式的表示及相加（0.5学时）教学内容：阐述存储高

7、次一元多项式的线性表可以采用每个元素包含2个数据项的方法，利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算；要求学生掌握利用线性链表的基本操作来实现一元多项式的定义、相加和相乘运算。第3章栈和队列（共4学时）7.1 栈（0.5学时）7.1.1 抽象数据类型栈的定义教学内容：阐述栈、栈顶、栈底、后进先出等概念，栈的抽象数据定义；要求学生掌握栈及栈的相关概念，理解栈的抽象数据定义。7.1.2 栈的表示和实现教学内容：阐述栈的2种存储表示法：顺序栈和链栈的定义，顺序栈的模块说明；要求学生掌握顺序栈的定义。7.2 栈的应用举例（1学时）7.2.1 数制转换教学内容：阐述应用栈结构的后进先出

8、特性，进行十进制N和其它d进制数的转换算法；要求学生理解应用栈结构的数制转换算法。7.2.2 括号匹配的检验教学内容：阐述应用栈结构的后进先出特性，进行圆括号和方括号书写格式是否正确的检查算法；要求学生理解应用栈结构的括号匹配检验算法。7.2.3 行编辑程序教学内容：阐述应用栈结构的文本行编辑算法；要求学生理解应用栈结构的文本行编辑算法。7.2.4 迷宫求解教学内容：阐述应用栈结构的迷宫求解算法，即求出迷宫中从入口到出口的所有路径；要求学生理解应用栈结构的迷宫求解算法。7.2.5 表达式求值教学内容：阐述应用栈结构进行表达式求值的算符优先法，算符优先法中的算符优先关系，要求学生理解应用栈结构进

9、行表达式求值的算符优先法。7.3 栈与递归的实现（0.75学时）教学内容：阐述递归的概念、递归问题的特性，栈在n阶Hanoi塔问题等典型递归问题中的应用；要求学生理解栈在n阶Hanoi塔递归算法中的应用。7.4 区红（重点）（1.5学时）7.4.1 抽象数据类型队列的定义教学内容：阐述队列、FIFO的概念，队列的特性，队列的抽象数据定义，双端队列的概念；要求学生掌握队列的概念，理解队列的特性，队列的抽象数据定义，双端队列的概念。7.4.2 链队列一队列的链式表示和实现教学内容：阐述链队列的概念，链队列类型的模块说明，队列链式表示的基本操作函数；要求学生掌握链队列的概念，理解链队列类型的模块说明

10、，队列链式表示的基本操作函数。7.4.3 循环队列一队列的顺序表示和实现教学内容：阐述循环队列的概念，循环队列类型的模块说明，队列循环表示的基本操作函数；要求学生掌握循环队列的概念，理解循环队列类型的模块说明，队列循环表示的基本操作函数。3.4离散事件模拟（0.25学时）教学内容：阐述使用有序链表和队列这两种数据类型做离散事件模拟的算法；要求学生理解包含有序链表和队列的事件模拟程序。第4章串（共3学时）10.1 用类型的定义（0.5学时）教学内容：阐述用产生的背景，用的概念，用长度、空用、子用、主用、位置、空格用等概念，用的抽象数据类型定义，用的基本操作集概念；要求学生掌握用及相关的概念，理解

11、用的抽象数据类型定义。10.2 -的表示和实现（重点）（1.5学时）10.2.1 定长顺序存储表示教学内容：阐述用在机内的定长顺序表示，在这种存储结构表示时如何实现用的连接操作和子用操作；要求学生掌握用的定长顺序存储表示，理解在定长顺序存储结构表示时实现用的连接操作和子用操作的方法。10.2.2 堆分配存储表示教学内容：阐述用的堆分配存储表示，在这种存储结构表示时如何实现用的插入操作；要求学生掌握用的堆分配存储表示，理解在堆分配存储结构表示时实现用的插入操作10.2.3 用的块链存储表示教学内容：阐述用的块链存储表示；要求学生掌握用的块链存储表示。10.3 用的模式匹配算法（0.75学时）10

12、.3.1 求子用位置的定位函数教学内容：阐述定位操作、匹配、模式匹配、模式用等概念，求子用位置的定位函数；要求学生掌握模式匹配的概念，熟悉求子用位置的定位函数。10.3.2 模式匹配的一种改进算法教学内容：阐述克努特-莫里斯-普拉特（KMP模式匹配算法；要求学生熟悉KMP奠式匹配算法。10.4 用操作应用举例（0.25学时）10.4.1 文本编辑教学内容：阐述文本编辑是修改字符数据的形式或格式，在文本编辑中使用用操作；要求学生理解文本编辑中用的用法。10.4.2 建立词索引表教学内容：阐述使用用建立词索引表的方法，词索引表插入的实现算法；要求学生理解建立词索引表中用的用法。第5章数组和广义表（

13、共5学时）数组的定义（0.5学时）教学内容：阐述抽象数据类型数组的定义；要求学生掌握抽象数据类型数组的定义。数组的顺序表示和实现（重点）（1.5学时）教学内容：阐述数组的顺序存储结构，以列序为主序的二维数组存储方式，以行序为主序的二维数组存储方式，n维数组的数据元素存储位置的计算；要求学生掌握数组的顺序表示法。矩阵的压缩存储（重点）（1.5学时）特殊矩阵教学内容：阐述矩阵、压缩存储、特殊矩阵的概念，特殊矩阵的压缩存储算法；要求学生掌握压缩存储、特殊矩阵的概念，熟悉特殊矩阵的压缩存储算法。稀疏矩阵教学内容：阐述稀疏矩阵的概念，稀疏矩阵的压缩存储算法，两个稀疏矩阵相乘的算法；要求学生掌握稀疏矩阵的

14、压缩存储算法。广义表的定义（0.5学时）教学内容：阐述抽象数据类型广义表的定义，列表的3个重要结论；要求学生掌握抽象数据类型广义表的定义。广义表的存储结构（0.5学时）教学内容：阐述广义表的链式存储结构，广义表的头尾链表存储表示；要求学生熟悉广义表的存储结构。m元多项式的表示（0.25学时）教学内容：阐述广义表的m元多项式表示，m元多项式的存储结构示意图；要求学生了解广义表的m元多项式表示。广义表的递归算法（0.25学时）求广义表的深度教学内容：阐述利用分治法进行递归算法设计，求广义表的深度算法；要求学生了解广义表的递归算法。复制广义表教学内容：阐述复制广义表算法；要求学生了解复制广义表的递归

15、算法。建立广义表的存储结构教学内容：阐述建立广义表的存储结构的2种分析方法；要求学生了解建立广义表的存储结构的2种方法。第6章树和二叉树（共6学时）树的定义和基本术语（0.5学时）教学内容：阐述树型结构的背景，树、子树、结点、叶子、终端结点、分支结点、双亲、孩子、深度、有序树、无序树、森林抽象数据类型树的定义，树的4种表示法;要求学生掌握树的概念，树结构中结点、叶子、深度等术语的概念。二叉树（重点）（1学时）二叉树的定义教学内容：阐述抽象数据类型二叉树的定义；要求学生掌握抽象数据类型二叉树的定义。二叉树的性质教学内容：阐述二叉树的5个重要性质；要求学生掌握二叉树的5个重要性质。二叉树的存储结构

16、教学内容：阐述二叉树的顺序存储结构，二叉树的链式存储结构；要求学生掌握二叉树的顺序存储结构，二叉树的链式存储结构。遍.历树和线索二叉树（重点）（1学时）遍历二叉树教学内容：阐述遍历和遍历二叉树的概念，先序遍历二叉树的操作定义，中序遍历二叉树的操作定义，后序遍历二叉树的操作定义，先序遍历二叉树基本操作的递归算法在二叉链表上的实现；要求学生掌握遍历和遍历二叉树的概念，熟悉序遍历二叉树基本操作的递归算法在二叉链表上的实现。线索二叉树教学内容：阐述线索链表、线索、线索二叉树、线索化的概念，线索二叉树及其存储结构，后序后继线索二叉树；要求学生掌握线索、线索二叉树的概念，熟悉中序线索二叉树，中序线索链表。

17、树和森林（1学时）树的存储结构教学内容：阐述树的3种常用的链表存储结构，即双亲表示法、二叉树表示法、孩子表示法；要求学生掌握树的3种常用的链表存储结构。森林与二叉树的转换教学内容：阐述森林与二叉树的转换，森林转换成二叉树的定义，二叉树转换成森林的定义；要求学生掌握森林转换成二叉树的定义，二叉树转换成森林的定义。树和森林的遍历教学内容：阐述森林的2种遍历方法：先序遍历森林、中序遍历森林；要求学生了解森林的2种遍历方法。树与等价问题（0.25学时）教学内容：阐述等价关系和等价类的定义，等价问题，确定等价类的算法，划分等价类需对集合进行的3种操作；要求学生理解等价关系和等价类的定义，了解双亲表示法做

18、存储结构时查找函数和归并操作的实现算法。赫夫曼树及其应用（重点）（1学时）最优二叉树教学内容：阐述最优二叉树的概念，构造赫夫曼树的算法；要求学生掌握最优二叉树的概念，构造赫夫曼树的算法。赫夫曼编码教学内容：阐述赫夫曼编码的定义，赫夫曼和赫夫曼编码的存储表示；要求学生掌握赫夫曼编码的定义，赫夫曼和赫夫曼编码的存储表示。回溯法与树的遍历（1学时）教学内容：阐述回溯法的定义，遍历状态树的算法；要求学生理解回溯法的定义和遍历状态树的算法。树的计数（0.25学时）教学内容：阐述二叉树相似和等价的概念，二叉树的计数问题定义，由前序和中序序列构造一棵二叉树的过程；要求学生熟悉二叉树相似和等价的概念，二叉树的

19、计数问题定义。第7章图（共5学时）图的定义和术语（1学时）教学内容：阐述图的概念，抽象数据类型图的定义，顶点、弧、有向图、无向图、完全图、有向完全图、稀疏图、稠密图、权、网、子图、邻接点、入度、出度、路径、回路、简单路径、连通、连通图、连通分量、强连通图、生成树、生成森林等概念；要求学生掌握图以及与图有关名词的定义、掌握抽象数据类型图的定义。图的存储结构（重点）（1学时）数组表示法教学内容：阐述图的多重链表，图的数组表示法，网及其邻接矩阵；要求学生掌握图的多重链表，熟悉图的数组表示法。邻接表教学内容：阐述图的链式存储结构邻接表、逆邻接表；要求学生掌握图的链式存储结构邻接表。十字链表教学内容：阐

20、述有向图的链式存储结构十字链表；要求学生掌握有向图的链式存储结构十字链表。邻接多重表教学内容：阐述无向图的链式存储结构邻接多重表；要求学生掌握无向图的链式存储结构邻接多重表。图的遍历（重点）（1学时）深度优先搜索教学内容：阐述图的遍历概念，遍历图的路径深度优先搜索；要求学生掌握深度优先搜索过程。广度优先搜索教学内容：阐述遍历图的路径广度优先搜索；要求学生掌握广度优先搜索过程。图的连通问题（1学时）无向图的连通分量和生成树教学内容：阐述利用遍历图的算法求解连通和非连通无向图的连通性问题，无向图的连通分量和生成树的构成方式；要求学生熟悉无向图的连通分量和生成树的构成方式。有向图的强连通分量教学内容

21、：阐述求解有向图的强连通分量的步骤；要求学生熟悉求解有向图的强连通分量的步骤。最小生成树教学内容：阐述最小生成树问题的概念，构造最小生成树的普里姆算法、克鲁斯卡尔算法；要求学生熟悉构造最小生成树的普里姆算法。关节点和重连通分量教学内容：阐述关节点、重连通图和重连通分量的概念，由深度优先生成树得出2类关节点的特性；要求学生熟悉关节点、重连通图和重连通分量的概念，了解2类关节点的特性。有向无环图及其应用（0.5学时）拓扑排序教学内容：阐述有向无环DAG图的定义，在描述表达式时与二叉树的区别，拓扑排序、偏序、全序、拓扑有序的概念，拓扑排序的算法；要求学生掌握有向无环DAGS的定义，熟悉拓扑排序、偏序

22、、全序、拓扑有序的概念。关键路径教学内容：阐述AOEW,关键路径的算法；要求学生熟悉AOE网的概念，了解关键路径的算法。最短路径（0.5学时）从某个源点到其余各顶点的最短路径教学内容：阐述源点、终点的概念，分析带权有向图中从某个源点到其余各顶点的最短路径问题，讲解针对此问题的用C语言描述的迪杰斯特拉算法；要求学生了解从某个源点到其余各顶点的最短路径问题，了解迪杰斯特拉算法。每一对顶点之间的最短路径教学内容：分析带权有向图中每一对顶点之间的最短路径问题，讲解针对此问题的弗洛伊德算法；要求学生了解带权有向图中每一对顶点之间的最短路径问题，了解弗洛伊德算法。第8章动态存储管理（共3学时）概述（0.2

23、5学时）教学内容：阐述动态存储管理的基本问题是系统如何应用户提出的请求分配内存；要求学生理解动态存储管理的基本问题。可利用空间表及分配方法（0.25学时）教学内容：阐述使用可利用空间表进行动态存储分配的方法，可利用空间表的3种不同的结构形式，即系统运行期间所有用户请求分配的存储量大小相同、存储量有若干种规格、分配给用户的内存块的大小不固定可以随请求而变，空间表中空闲块的3种分配策略，即首次拟合法、最佳拟合法、最差拟合法；要求学生了解使用可利用空间表进行动态存储分配的方法的方法。边界标识法（1学时）可利用空间表的结构教学内容：阐述边界标识法的定义，可利用空间表的结构；要求学生了解边界标识法的定义

24、，可利用空间表的结构。分配算法教学内容：阐述可利用空间表的分配算法；要求学生了解可利用空间表的分配算法。回收算法教学内容：阐述可利用空间表的回收算法；要求学生了解可利用空间表的回收算法。伙伴系统（1学时）可利用空间表的结构教学内容：阐述动态存储管理方法伙伴系统，伙伴关系下的可利用空间表的结构；要求学生了解动态存储管理方法伙伴系统、伙伴关系下的可利用空间表的结构。分配算法教学内容：阐述可利用空间表的分配算法；要求学生了解可利用空间表的分配算法。回收算法教学内容：阐述伙伴关系下回收算法；要求学生了解伙伴关系下回收算法。无用单元收集（0.25学时）教学内容：阐述无用单元的概念，无用单元收集的2条途径

25、，即收集访问计数器、收集无用单元，3种标志算法，即递归算法、非递归算法、利用表结点本身的指针域标记遍历路径的算法；要求学生建立无用单元收集的概念。存储紧缩（0.25学时）教学内容：阐述存储紧缩的概念，2种回收紧缩的方式；要求学生了解存储紧缩的概念和2种回收紧缩的方式。第9章查找（共4学时）静态查找表（重点）（1.5学时）顺序表的查找教学内容：阐述查找表的概念，动态查找表、关键字、查找的概念，抽象数据类型静态查找表的定义，顺序表的查找实现；要求学生掌握查找表的概念，动态查找表、关键字、查找的概念，顺序表的查找实现。有序表的查找教学内容：阐述有序表的折半查找实现，查找操作的性能分析，折半查找的性能

26、分析；要求学生掌握有序表的折半查找实现。静态树表的查找教学内容：阐述静态树表的查找，静态最优查找树的概念；要求学生掌握静态最优查找树的概念。索引顺序表的查找教学内容：阐述索引顺序表的分块查找算法；要求学生了解索引顺序表的分块查找算法。动态查找表（重点）（1学时）二叉排序树和平衡二叉树教学内容：阐述动态查找表的特点，抽象数据类型动态查找表的定义，二叉排序树的概念，二叉排序树的查找过程，二叉排序树的插入和删除，平衡二叉树（AVD的概念，平衡树的生成过程，二叉排序树的平衡旋转图例；要求学生掌握抽象数据类型动态查找表的定义，二叉排序树的概念，二叉排序树的查找过程，平衡二叉树（AVD的概念。B树和B+树

27、教学内容：阐述B树的卞S念，B树查找分析，B树的插入和删除，B+M的概念；要求学生掌握抽象数据类型动态查找表的定义，二叉排序树的概念，二叉排序树的查找过程，平衡二叉树（AVD的概念，B树的才吃念，B树查找分析，B+W的概念。键树教学内容：阐述数字查找树的概念，数字查找树的2种存储结构，在双链树中查找记录的操作算法，Trie树的查找算法；要求学生掌握数字查找树的概念，了解键树的2种存储结构，了解Trie树的查找算法。哈希表（重点）（1.5学时）什么是哈希表教学内容：阐述哈希表、哈希函数的概念；要求学生掌握哈希表、哈希函数的概念。哈希函数的构造方法教学内容：阐述哈希函数的6种构造方法：即直接定址法

28、、数字分析法、平方取中法、折叠法、除留余数法和随机数法；要求学生熟悉哈希函数的6种构造方法，即直接定址法、数字分析法、平方取中法、折叠法、除留余数法和随机数法。处理冲突的方法教学内容：阐述哈希造表处理冲突的4种方法，即开放地址法、再哈希法、链地址法和建立一个公共溢出区；要求学生哈希造表处理冲突的4种方法，即开放地址法、冉哈希法、链地址法和建立一个公共溢出区。哈希表的查找及其分析教学内容：阐述以开放定址等方法处理冲突的哈希表的查找算法，哈希表查找的分析；要求学生熟悉以开放定址等方法处理冲突的哈希表的查找算法。第10章内部排序（共6学时）概述（0.5学时）教学内容：阐述排序的概念，内部排序和外部排

29、序的概念；要求学生建立排序的概念。插入排序（重点）（1.5学时）直接插入排序教学内容：阐述直接插入排序的概念，直接插入排序的算法；要求学生掌握直接插入排序的改建，了解直接插入排序的算法。其它插入排序教学内容：阐述折半插入排序的概念和算法，2-路插入排序的概念和算法；要求学生了解折半插入排序的概念和算法，2-路插入排序的概念和算法。希尔排序教学内容：阐述希尔排序的概念和算法，缩小增量排序的序列特点；要求学生了解希尔排序的概念和算法，了解缩小增量排序的序列特点。快速排序（1学时）教学内容：阐述起泡排序的概念和算法，快速排序的概念和算法；要求学生掌握起泡排序的概念和算法，了解快速排序的概念和算法。选

30、择排序（重点）（1.5学时）简单排序选择教学内容：阐述选择排序的的基本思想，简单选择排序算法；要求学生掌握选择排序的的基本思想，了解简单选择排序算法。树形选择排序教学内容：阐述树形选择排序示例；要求学生了解树形选择排序。堆排序教学内容：阐述堆排序的概念，堆的定义，堆排序的算法；要求学生了解堆排序的概念，堆的定义，堆排序的算法。归并排序（0.5学时）教学内容：阐述归并排序的概念和算法；要求学生了解归并排序的概念和算法。基数排序（0.5学时）多关键字排序教学内容：阐述基数排序的概念，多关键字排序问题；要求学生了解基数排序的概念，多关键字排序问题。链式基数排序教学内容：阐述链式基数排序方法；要求学生了解链式基数排序方法。各种内部排序方法的比较讨论（0.5学时）教学内容：阐述各种内部排序方法的优劣；要求学生了解各种内部排序方法的优劣。第11章外部排序（共2学时）外存信息的存取（0.5学时）教学内容：阐述磁带信息的存取方式，磁盘信息的存取方法；要求学生了解磁带信息的存取方式，磁盘信息的存取方法。外部排序的方法（0.75学时）教学内容：阐述2路平衡归并的外部排序法；令学生了解2路平衡归并的外部排序法。多路平衡归并的实现（0.25学时）教学内容：描述多路平衡归并的败者树图；要求学生了解多路平衡归并的败者树图。置换选择排序（0.25学时