《数据结构（C语言版）》教案

作者：21工作室 | 发布时间：2020-12-09 19:43:49 收藏本文下载本文

2011 至2012 学年第一学期教案课程名称数据结构使用教材《数据结构（C语言版）》

教学时数56课程性质必修

任课班级（人数）信管（53人）

信息系（部）

信管教研室任课教师山东科技大学泰山科技学院课时授课计划 2011-2012学年第二学期第1周授课日期 2月 20 日星期1 月日星期月日星期月日星期月日星期班级信管10-1 基本课题第1章绪论 1.1-1.2 教学目的与要求：

1.了解数据结构的基本概念 2.理解常用术语教学重点：

数据结构的基本概念和术语教学难点：

数据元素之间的四种结构关系作业及参考书：

1、什么是数据结构？《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：自我介绍——开课——引入——展开——举例——小结——作业一、自我介绍和课程介绍约8min 课时：64 二、引入约2min 由问题的提出引入三、讲课进程设计 1.1 什么是数据结构 1.1.1、数据结构与其它的关系约15min 数据结构 +算法 =程序程序设计: 为计算机处理问题编制一组指令集算法: 处理问题的策略数据结构: 问题的数学模型 1.1.2、当今计算机应用的特点：

约25min l)所处理的数据量大且具有一定的关系；

2)对其操作不再是单纯的数值计算，而更多地是需要对其进行组织、管理和检索。

举例说明：

1)学生成绩表 2)井安棋对弈 3)交通管理结论计算机的操作对象的关系更加复杂，操作形式不再是单纯的数值计算，而更多地是对这些具有一定关系的数据进行组织管理；

我们将此称为非数值性处理。要使计算机能够更有效地进行这些非数值性处理，就必须弄清楚这些操作对象的特点，在计算机中的表示方式以及各个操作的具体实现手段。

1.2 基本概念和术语 1.1.1、数据与数据结构约20min 数据：是对客观事物的符号表示。

所有能被输入到计算机中，且能被计算机处理的符号的集合。是计算机操作的对象的总称。是计算机处理的信息的某种特定的符号表示形式。

数据元素：是数据（集合）中的一个“个体”，是数据结构中讨论的基本单位。

数据对象：是性质相同的数据元素的集合，是数据的一个子集。

数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。这种集合称为结构。

数据的逻辑结构可归结为以下四类: 种类特征示例集合元素间为松散的关系线性结构元素间为严格的一对一关系如上面的成绩表中各元素树形结构元素间为严格的一对多关系图状结构（或网状结构）

元素间为多对多关系数据结构的形式定义为:数据结构是一个二元组数据的存储结构：——逻辑结构在存储器中的映像数据元素的映象方法：计算机中存储信息的最小单位：位，8位为一字节，两个字节为一字，字节、字或更多的二进制位可称为位串。在逻辑描述中，把位串称为元素或结点。

关系的映象方法：顺序映象链式映象 1.2.2、数据类型约5min 数据类型是一个值的集合和定义在此集合上的一组操作的总称。

1.2.3、抽象数据类型约20min 是指一个数学模型以及定义在此数学模型上的一组操作。

关键：使用它的人可以只关心它的逻辑特征，不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。

抽象数据类型表示法：

三元组表示：（D，S，P）

其中D是数据对象，S是D上的关系集，P是对D的基本操作集。

书中的定义格式：

ADT 抽象数据类型名{

数据对象：<数据对象的定义>

数据关系：<数据关系的定义>

基本操作：<基本操作的定义>

}ADT 抽象数据类型名 ADT 有两个重要特征: 数据抽象数据封装四、本次课小结：

约3min 1.熟悉各名词 2.术语的含义 3.掌握基本概念五、作业约2min 2、什么是数据结构？课时授课计划 2011-2012学年第二学期第1周授课日期 2月 24日星期5 月日星期月日星期月日星期月日星期班级信管10-1 基本课题抽象数据类型的表示与实现算法和算法分析教学目的与要求：

类C语言的各种句型及算法描述的规范教学重点：

类C语言的各种句型及算法描述的规范教学难点：

类C语言的各种句型及算法描述的规范作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：复习——引入——展开——举例——小结——作业一、复习：

约5min 1、数据结构的基本概念 2、一些基本术语二、引入约2min 由程序设计过程遇到的问题引入三、讲课进程设计 1.3抽象数据类型的表示与实现 1.3.1基本操作：

约15min AssignComplex(&Z, v1, v2)操作结果：构造复数 Z,其实部和虚部分别被赋以参数 v1 和 v2 的值。

DestroyComplex(&Z)操作结果：复数Z被销毁。

GetReal(Z, &realPart)初始条件：复数已存在。

操作结果：用realPart返回复数Z的实部值。

GetImag(Z, &ImagPart)初始条件：复数已存在。

操作结果：用ImagPart返回复数Z的虚部值。

Add(z1,z2, &sum)初始条件：z1, z2是复数。

操作结果：用sum返回两个复数z1, z2 的和值。

1.3.2对本书所采用的类C语言作简要说明约18min 1.预定义常量及类型 2、数据结构的存储结构typedef 3、算法描述为以下的函数形式：

4.在算法描述中可以使用的赋值语句形式有：

5.在算法描述中可以使用的选择结构语句形式有：

6.在算法描述中可以使用的循环结构语句形式有：

7.在描述算法中可以使用的结束语句形式有：

8.在算法描述中可以使用的输入输出语句形式有：

9.在算法描述中使用的注释格式为：

10.在算法描述中可以使用的扩展函数有：

11.逻辑运算约定 1.4算法和算法分析 1.4.1、算法约10min 算法是为了解决某类问题而规定的一个有限长的操作序列。一个算法必须满足以下五个重要特性：

1．有穷性 2．确定性 3．可行性 4．有输入 5．有输出 1.4.2、算法设计的原则约10min 设计算法时，通常应考虑达到以下目标：

1．正确性2.可读性3．健壮性4．高效率与低存储量需求 1.4.3、算法效率的衡量方法和准则约20min 通常有两种衡量算法效率的方法事后统计法缺点：1．必须执行程序 2．其它因素掩盖算法本质事前分析估算法和算法执行时间相关的因素：1．算法选用的策略2．问题的规模3．编写程序的语言4．编译程序产生的机器代码的质量5．计算机执行指令的速度算法 = 控制结构 + 原操作（固有数据类型的操作）

一个算法的执行时间大致上等于其所有语句执行时间的总和，对于语句的执行时间是指该条语句的执行次数和执行一次所需时间的乘积。

在计算时间复杂度时所采用的记号“O”是数学符号，其严格的数学定义是：若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数c和n0，使得当n>=n0时都满足0=

1.执行一条读写或赋值语句用O(1)时间2、依次执行一系列语句所用时间用和准则 3、判断语句的耗时主要是执行语句所用的时间，检验条件还需O(1)4、循环语句的运行时间为多次叠代中执行循环体以及检验循环条件的耗时，常用乘法准则若算法的两个部分的时间复杂度为T1(n)=o(f(n))和T2(n)=o(g(n))则大“O”下的：

求和准则为 T1(n)+ T2(n)=O(max(f(n),g(n))乘法准则为 T1(n)* T2(n)=O((f(n)*g(n))1.4.4、算法的存储空间需求约10min 算法的空间复杂度定义为: S(n)= O(g(n))表示随着问题规模 n 的增大，算法运行所需存储量的增长率与 g(n)的增长率相同。

算法的存储量包括: 1．输入数据所占空间2．程序本身所占空间3．辅助变量所占空间四、小结：

约5min 1.理解算法五个要素的确切含义。

2.掌握计算语句频度和估算算法时间复杂度的方法。

五、作业约5min 1、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0).通常算法的输入和输出可采用下列两种方式之一：

•（1）通过参数表中的参数显式传递；

（2）通过全局变量隐式传递。

• 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。

课时授课计划 2011-2012学年第二学期第2周授课日期 2月 27 日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题线性表的类型定义线性表的顺序表示和实现教学目的与要求：

1、掌握线性表的概念和类型定义 2、掌握线性表的顺序表示和实现方法教学重点：

线性表的类型定义线性表的顺序表示和实现方法教学难点：

线性表的类型定义线性表的顺序存储的实现方法作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：复习——引入——展开——举例——小结一、引入约3min 由顺序的算法引入二、讲课进程设计 2．1线性表的类型定义 12.1.1线性表的定义约27min 线性表是由n（n≥0）个类型相同的数据元素组成的有限序列。

抽象数据类型线性表的定义如下：

ADT List { 数据对象 D＝{ ai | ai ∈ElemSet, i=1,2,...,n, n≥0 } {称 n 为线性表的表长;称 n=0 时的线性表为空表。} 数据关系 R1＝{ |ai-1 ,ai∈D, i=2,...,n } 基本操作：

结构初始化操作：

InitList(&L)操作结果：构造一个空的线性表L。结构销毁操作：

DestroyList(&L)初始条件：线性表 L 已存在。操作结果：销毁线性表 L。

引用型操作 ListEmpty(L)（线性表判空）

ListLength(L)（求线性表的长度）

PriorElem(L, cur_e, &pre_e)（求数据元素的前驱）

NextElem(L, cur_e, &next_e)（求数据元素的后继）

GetElem(L, i, &e)（求线性表中某个数据元素）

LocateElem(L, e, compare())（定位函数）

ListTraverse(L, visit())（遍历线性表）

加工型操作 ClearList(&L)（线性表置空）

PutElem(&L, i, &e)（改变数据元素的值）

ListInsert(&L, i, e)（插入数据元素）

ListDelete(&L, i, &e)（删除数据元素）

2.1.2举例约10min 两个线性表合并LA和LB 2.2 线性表的顺序表示和实现 2.2.1顺序映象约15min——以 x 的存储位置和 y 的存储位置之间某种关系表示逻辑关系。

最简单的一种顺序映象方法是：

令y的存储位置和x的存储位置相邻。线性表的基本操作在顺序表中的实现 InitList(&L)// 结构初始化 LocateElem(L, e, compare())// 查找 ListInsert(&L, i, e)// 插入元素 ListDelete(&L, i)// 删除元素 2.1.1、线性表操作约20min ListInsert(&L, i, e)的实现：

首先分析插入元素时，线性表的逻辑结构发生什么变化？线性表操作 ListDelete(&L, i, &e)的实现：

首先分析：

删除元素时，线性表的逻辑结构发生什么变化？线性表类型的实现 2.1.2、线性表顺序存储结构的特点：

约20min 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。

暴露的问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；

(2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；

(3)线性表的容量难以扩充。

三、小结约5min 1.了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。

2.熟练掌握这两类存储结构的描述方法，以及线性表的各种基本操作的实现。

课时授课计划 2011-2012学年第二学期第2周授课日期 3月 3 日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题线性表的链式表示和实现一元多项式的表示及相加教学目的与要求：

1、掌握线性链表、单链表、静态链表的概念、表示及实现方法。

2、掌握循环链表的概念 3、掌握双向链表的表示与实现教学重点：

1、线性链表之单链表的表示及实现方法。

2、双向链表的表示与实现教学难点：

1、线性链表 2、双向链表的存储表示作业及参考书：

写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：复习——引入——展开——举例——小结——作业一、复习

约5min 复习线性表有的概念二、引入

约2min 由线性表的表示不方便引入三、讲课进程设计 2.3 线性表的链式表示和实现线性表顺序存储结构的特点：

约10min 它是一种简单、方便的存储方式。它要求线性表的数据元素依次存放在连续的存储单元中，从而利用数据元素的存储顺序表示相应的逻辑顺序，这种存储方式属于静态存储形式。

暴露的问题(1)在做插入或删除元素的操作时，会产生大量的数据元素移动；

(2)对于长度变化较大的线性表，要一次性地分配足够的存储空间，但这些空间常常又得不到充分的利用；

(3)线性表的容量难以扩充。

2.3.1、单链表

约10min 用一组地址任意的存储单元存放线性表中的数据元素（这组存储单元可以是连续的也可以是不连续的）。

2.3.2、结点和单链表的 C 语言描述

约10min 2.3.3、单链表操作的实现

约13min 因此生成链表的过程是一个结点“逐个插入”的过程。

操作步骤：

1、建立一个“空表”；

2、输入数据元素an，建立结点并插入；

3、输入数据元素an-1，建立结点并插入；

4、依次类推，直至输入a1为止。

2.3.4、其它形式的链表

约5min 1.循环链表2.双向链表 2.3.5、有序表类型

约5min 2.4一元多项式的表示 2.4.1一元多项式

约20min 在计算机中，可以用一个线性表来表示: P =(p0, p1, …，pn)抽象数据类型一元多项式的定义如下：

ADT Polynomial { 数据对象：D＝{ ai| ai∈TermSet,i=1,2,...,m, m≥0 TermSet 中的每个元素包含一个表示系数的实数和表示指数的整数 } 数据关系：R1＝{ |ai-1 ,ai∈D, i=2,...,n 且ai-1中的指数值＜ai中的指数值 } 基本操作：

CreatPolyn(&P, m)操作结果：输入 m 项的系数和指数，建立一元多项式 P。

DestroyPolyn(&P)初始条件：一元多项式 P 已存在。

操作结果：销毁一元多项式 P。

PrintPolyn(&P)初始条件：一元多项式 P 已存在。

操作结果：打印输出一元多项式 P。

PolynLength(P)初始条件：一元多项式 P 已存在。

操作结果：返回一元多项式 P 中的项数。

AddPolyn(&Pa, &Pb)初始条件：一元多项式 Pa 和 Pb 已存在。

操作结果：完成多项式相加运算，即：

Pa = Pa＋Pb，并销毁一元多项式 Pb。

SubtractPolyn(&Pa, &Pb)… … } ADT Polynomial 2.4.2一元多项式的实现：

约10min typedef OrderedLinkList polynomial;// 用带表头结点的有序链表表示多项式四、小结约5min 1.能够从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。

五、本章作业：

约5min 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。

本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。

课时授课计划 2011-2012学年第一学期第3周授课日期 9月22日五星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题栈栈的应用举例教学目的与要求：

1、栈的数据类型定义 2、栈的顺序存储与实现 3、掌握栈的应用方法，理解栈的重要作用教学重点：

1、栈的顺序存储表示与实现方法 2、利用栈实现行编辑、利用栈实现表达式求值教学难点：

1、栈的定义 2、利用栈实现表达式求值作业及参考书：

1、栈定义的应用 2、栈的特点《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约10min 1.什么是线性结构？ 2.以餐馆中一叠一叠的盘子的使用为例，引出栈的特点。

二、讲课进程设计 3.1 栈的类型定义 3.1.1、栈、栈顶(top)、栈底(bottom)的定义约10min 3.1.2栈的类型定义约10min 3.2 栈的应用举例例一、数制转换

约10min 十进制数N和其他d进制数的转换是计算机实现计算的基本问题，个简单算法基于下列原理：

N =(N div d)×d + N mod d(其中：div为整除运算，mod为求余运算)例二、括号匹配的检验

约10min 检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。

三种情况对应到栈的操作即为：

1．和栈顶的左括弧不相匹配；

2．栈中并没有左括弧等在哪里；

3．栈中还有左括弧没有等到和它相匹配的右括弧。

例三、行编辑程序问题

约10min 在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。

合理的作法是：设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区,并假设“#”为退格符，“@”为退行符。

例四、迷宫求解

约10min 假设以栈S记录“当前路径”，则栈顶中存放的是“当前路径上最后一个通道块”。

“纳入路径”的操作即为“当前位置入栈；

“从当前路径上删除前一通道块”的操作即为“出栈“。

例五、表达式求值

约10min 任何一个表达式都是由操作数(operand)、运算符(operator)和界限符(delimiter)组成。

例六、实现递归

约10min 递归函数的实现一个递归函数的运行过程类似于多个函数的嵌套调用，差别仅在于“调用函数和被调用函数是同一个函数”。为了保证“每一层的递归调用”都是对“本层”的数据进行操作，在执行递归函数的过程中需要一个“递归工作栈”。

三、小结约5min 1.掌握栈和队列类型的特点，并能在相应的应用问题中正确选用它们。

2.熟练掌握栈类型的两种实现方法，特别应注意栈满和栈空的条件以及它们的描述方法。

四、作业

约5min 1、4个元素a1，a2，a3和a4依次通过一个栈，在a4进栈前，栈的状态，则不可能的出栈序是（）

(A)a4，a3，a2，a1(B)a3，a2，a4，a1(C)a3，a1，a4，a2(D)a3，a4，a2，a1 2、栈的特点是（）。

课时授课计划 2011-2012学年第一学期第3周授课日期 9月27日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题队列教学目的与要求：

1.熟练掌握循环队列和链队列的基本操作实现算法。

2.理解递归算法执行过程中栈的状态变化过程。

教学重点：

1．链队的表示与实现教学难点：.1。链队的表示与实现作业及参考书：

1．栈与队列的比较 2．读程序段《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 在日常生活中，为了维持正常的社会秩序而出现的常见现象是什么？是“排队“。在计算机程序中，模拟排队的数据结构是“队列“。

二、讲课进程设计 3.4 队列 1队列的定义约10min 2队列的抽象类型定义

约15min 3.队列的基本操作：

约20min InitQueue(&Q)操作结果：构造一个空队列Q。

DestroyQueue(&Q)初始条件：队列Q已存在。

操作结果：队列Q被销毁，不再存在。

QueueEmpty(Q)初始条件:队列Q已存在。

操作结果:若Q为空队列,则返回TRUE，否则返回FALSE。

QueueLength(Q)初始条件:队列Q已存在。

操作结果:返回Q的元素个数，即队列的长度。

GetHead(Q, &e)初始条件：Q为非空队列。

操作结果：用e返回Q的队头元素。

ClearQueue(&Q)初始条件：队列Q已存在。

操作结果：将Q清为空队列。

EnQueue(&Q, e)初始条件:队列Q已存在。

操作结果:插入元素e为Q的新的队尾元素。

DeQueue(&Q, &e)初始条件：Q为非空队列。

操作结果：删除Q的队头元素，并用e返回其值。

QueueTravers(Q, visit())队列类型的实现 4.链队列——链式映象

约15min 5.循环队列——顺序映象

约20 min 队列在程序设计中的一个典型应用例子是作业排队问题。

三、小结约5min 1.熟练掌握循环队列和链队列的基本操作实现算法，特别注意队满和队空的描述方法。

2.理解递归算法执行过程中栈的状态变化过程。

四、作业

约10min 1、线性表、栈和队列都是（）结构,可以在线性表的（）位置插入和删除元素，对于栈只能在（）插入和删除元素，对于队列只能在（）插入元素和（）删除元素。

2、指出下述程序段的功能是什么?(1)void Demo1(SeqStack *S){

int i;arr[64];n=0;

while(StackEmpty(S))arr[n++]=Pop(S);

for(i=0, i< n;i++)Push(S, arr[i]);

} //Demo1 课时授课计划 2011-2012学年第一学期第4周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题

实验二栈和队列的总结复习教学目的与要求：

1、深入了解栈和队列的特征，以便在实际问题背景下灵活运用它们；

2、巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

教学重点：

巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

教学难点：

巩固这两种结构的构造方法，接触较复杂问题的递归算法设计。

作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

课堂类型：

教学过程：

停车场管理 [问题描述]

设停车场内只有一个的停放n辆汽车的狭长通道，且只有一个大门可供汽车进出。汽车在停车场内按车辆到达时间的先后顺序，依次由北向南排列（大门在最南端，最先到达的第一辆车停放在车场的最北端），若车场内已停满n辆汽车，则后来的汽车只能在门外的便道上等候，一旦有车开走，则排在便道上的第一辆车即可开入；

当停车场内某辆车要离开时，在它之后开入的车辆必须先退出车场为它让路，待该辆车开出大门外，其它车辆再按原次序进入车场，每辆停放在车场的车在它离开停车场时必须按它停留的时间长短交纳费用。试为停车场编制按上述要求进行管理的模拟程序。

[测试数据]

设n=2,输入数据为：（‘A’，1，5），（‘A’，2，10），（‘D’，1，15），（‘A’，3，20），（‘A’，4，25），（‘A’，5，30），（‘D’，2，35），（‘D’，4，40），（‘E’，0，0）。其中，‘A’表示到达；

‘D’表示离去，‘E’表示输入结束。

[基本要求]

以栈模拟停车场，以队列模拟车场外的便道，按照从终端读入的输入数据序列进行模拟管理。每一组输入数据包括三个数据项：汽车“到达”或“离去”信息、汽车牌照号码及到达或离去的时刻，对每一组输入数据进行操作后的输出数据为：若是车辆到达，则输出汽车在停车场内或便道上的停车位置；

若是车离去；

则输出汽车在停车场内停留的时间和应交纳的费用（在便道上停留的时间不收费）。栈以顺序结构实现，队列以链表实现。

[实现提示]

需另设一个栈，临时停放为给要离去的汽车让路而从停车场退出来的汽车，也用顺序存储结构实现。输入数据按到达或离去的时刻有序。栈中每个元素表示一辆汽车，包含两个数据项：汽车的牌照号码和进入停车场的时刻。

[选作内容]

（1）

两个栈共享空间，思考应开辟数组的空间是多少？

（2）

汽车可有不同种类，则它们的占地面积不同，收费标准也不同，如1辆客车和1.5辆小汽车的占地面积相同，1辆十轮卡车占地面积相当于3辆小汽车的占地面积。

（3）

汽车可以直接从便道上开走，此时派在它前面的汽车要先开走让路，然后再依次排到队尾。

（4）

停放在便道上的汽车也收费，收费标准比停放在停车场的车低，请思考如何修改结构以满足这种要求。

课时授课计划 2011-2012学年第一学期第4周授课日期 10月8日日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题串教学目的与要求：

1、熟悉串七种基本操作的定义，并能利用这些基本操作实现传的其他各种操作的方法。

2、熟悉掌握在串的定长顺序存储结构上实现串的各种操作的方法。

3、掌握串的堆存储结构以及在其上实现串的各种操作的基本方法。

教学重点：

1、串七种基本操作的定义 2、串的定长顺序存储 3、串的堆存储结构教学难点：

1、串七种基本操作的定义 2、串的堆存储结构作业及参考书：

对串的操作的应用《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 计算机上的非数值处理的对象基本上都是字符串数据。

二、讲课进程设计 4.1串的抽象数据类型的定义 1.定义

约10min

串、串长、空串、子串、主串、位置、相等、空格串 2.串的抽象数据类型的定义约10min StrAssign(&T, chars)StrCopy(&T, S)DestroyString(&S)StrEmpty(S)StrCompare(S,T)StrLength(S)Concat(&T,S1,S2)SubString(&Sub,S,pos,len)Index(S,T,pos)Replace(&S,T,V)StrInsert(&S, pos, T)StrDelete(&S, pos, len)ClearString(&S)4.2 串的表示和实现 4.2.1、串的定长顺序存储表示

约15min 1.串联接2.求子串 4.2.2、串的堆分配存储表示约20min 通常，C语言中提供的串类型就是以这种存储方式实现的。系统利用函数malloc()和free()进行串值空间的动态管理，为每一个新产生的串分配一个存储区，称串值共享的存储空间为“堆”。

4.2.3、串的块链存储表示

约10min 也可用链表来存储串值，由于串的数据元素是一个字符，它只有 8 位二进制数，因此用链表存储时，通常一个结点中存放的不是一个字符，而是一个子串。

4.4串操作应用举例 4.4.1文本编辑约20min 可用于文本编辑的程序很多，功能强弱差别很大，但基本操作是一致的：都包括串的查找，插入和删除等基本操作。

对用户来讲，一个文本（文件）可以包括若干页，每页包括若干行，每行包括若干文字。

对文本编辑程序来讲，可把整个文本看成一个长字符串，称文本串，页是文本串的子串，行又是页的子串。为简化程序复杂程度，可简单地把文本分成若干行。

三、小结约5min 1.熟悉串的七种基本操作的定义，并能利用这些基本操作来实现串的其它各种操作的方法。

2.熟练掌握在串的定长顺序存储结构上实现串的各种操作的方法。

3.了解串的堆存储结构以及在其上实现串操作的基本方法。

4.了解串操作的应用方法和特点。

四、作业约5min 假设有如下的串说明：

char s1[30]=“Stocktom,CA“, s2[30]=“March 5 1999”, s3[30], *p;(1)在执行下列语句后，s3的值是什么?

strcopy(s3,s1);concat(s3,“,“);concat(s3,s2);(2)调用函数strcompare(s1,s2)的返回值是什么?(3)调用函数strcompare(&s1[5],“ton“)的返回值是什么?(4)调用函数strlength(concat(s1,s2))的返回值是什么? 课时授课计划 2011-2012学年第一学期第5周授课日期 10月11日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题数组教学目的与要求：

1、掌握数组的定义 2、掌握数组的顺序表示方法教学重点：

1、数组的定义 2、数组的顺序表示方法教学难点：

数组的顺序表示方法作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结一、引入约5min 由前几章讨论的线性结构中的数据元素都是非结构的原子类型引入数组。

二、讲课进程设计 5.1 数组的类型定义抽象数据类型定义 约5min ADT Array { 数据对象：

数据关系：

} ADT Array 二维数组的定义: 约10min 数据对象: D = {aij | 0≤i≤b1-1, 0 ≤j≤b2-1} 数据关系: R = { ROW, COL } ROW = {| 0≤i≤b1-2, 0≤j≤b2-1} COL = {| 0≤i≤b1-1, 0≤ j≤b2-2} 基本操作：

约10min InitArray(&A, n,bound1,...,boundn)DestroyArray(&A)Value(A, &e, index1,..., indexn)Assign(&A, e, index1,..., indexn)5.2 数组的顺序表示和实现类型特点: 约10min 1)只有引用型操作，没有加工型操作；

2)数组是多维的结构，而存储空间是一个一维的结构。

有两种顺序映象的方式: 约10min 1)以行序为主序(低下标优先)；

2)以列序为主序(高下标优先)。

5.3 矩阵的压缩存储 5.3.1特殊矩阵 a.对称矩阵

约15min 定义压缩存储方式 b.三角矩阵约15min 定义压缩存储方式 c.对角矩阵

约20min 定义压缩存储方式三、小结 1、数组的特殊性 2、数组的存储 3、特殊矩阵的存储课时授课计划 2011-2012学年第二学期第5周授课日期 3月23日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题稀疏矩阵广义表教学目的与要求：

1、掌握稀疏矩阵的定义，三元组表示 2、掌握广义表的定义，它的链接存储结构教学重点：

1、三元组表示 2、广义表的存储结构教学难点：

1、三元组表示法 2、定义作业及参考书：

1、画出给出的广义表的两种存储结构 2、求广义表的运算 3、在对象矩阵中求下标变换公式《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 由特殊矩阵引入二、讲课进程设计 5.3.2稀疏矩阵 1、定义约5min 两类稀疏矩阵：1)特殊矩阵2)随机稀疏矩阵 2、随机稀疏矩阵的压缩存储方法: 1、三元组顺序表约20min 2、行逻辑联接的顺序表约20min 3、十字链表约10min 5.4 广义表广义表的定义

约20min 1、广义表：

表头：非空广义表的第一个元素α1 表尾：其余元素（α2，…，αn）组成的表。

2、广义表的抽象数据类型定义3、广义表的操作：

5.5广义表的的存储结构由于广义表中的数据元素可以具有不同的结构．因此，采用链式存储结构表示广义表。每个数据元素可用一个结点表示。

1、广义表的头尾链表存储表示约10min typedef enum{ATOM, LIST}ElemTag;typedef struct GLNode{ ElemTag tag;union{ AtomType atom;struct {struct GLNode *hp , *tp;}ptr };}*GList;三、小结约5min 1.了解数组的两种存储表示方法，并掌握数组在以行为主的存储结构中的地址计算方法。2.掌握对特殊矩阵进行压缩存储时的下标变换公式。3.了解稀疏矩阵的两类压缩存储方法的特点和适用范围，领会以三元组表示稀疏矩阵时进行矩阵运算采用的处理方法。4、掌握广义表的结构特点及其存储表示方法，读者可根据自己的习惯熟练掌握任意一种结构的链表，学会对非空广义表进行分解的两种分析方法：即可将一个非空广义表分解为表头和表尾两部分或者分解为n个子表。

四、课后作业及习题约5min 1、画出下面广义表的两种存储结构图示：((((a), b)),(((), d),(e, f)))2、求下列广义表运算的结果：

（1）GetHEAD[((a,b),(c,d))];（2）GetTAIL[((a,b),(c,d))];（3）GetTAIL[HEAD[((a,b),(c,d))]];（4）GetHEAD[TAIL[HEAD[((a,b),(c,d))]]];（5）GetTAIL[HEAD[TAIL[((a,b),(c,d))]]];3、设有三对角矩阵An×n ,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得B[k]= aij，求：（1）用i,j表示k的下标变换公式；

（2）用k表示i,j的下标变换公式。

课时授课计划 2011-2012学年第一学期第6周授课日期 10月20日五星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题树的定义和基本术语二叉树教学目的与要求：

1、掌握树、二叉树的基本概念和术语，二叉树的性质 2、掌握二叉树的两种存储结构教学重点：

1、二叉树的性质和定义 2、链式存储结构教学难点：

1、二叉树的性质 2、链式存储二叉树的基本操作作业及参考书：

1、一棵度为2的树与二叉树的区别 2、3个结点的树与3个结点的二叉树《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 由前几章的线性结构带来的问题引出非线性结构。

二、讲课进程设计第6章树和二叉树 6.1树的定义和基本术语 1、树的定义约10min 树是包含n个结点的有限集合(n>0)Tree=(D,R)其中，D是具有相同性质的数据元素的集合，若D中只有一个元素，则R为空集，否则R是D上某个二元关系H的集合，H是如下描述的二元关系：

（1）

在D中存在唯一一个称为根的元素r0,它在关系H下无前驱；

（2）

除结点r0外,K中每个结点对于关系H来说，都有且只有一个前驱。

（3）结点r0外的任何结点rR，都存在一个结点序列r0,r1,…,rs,H(1<=i<=s),这样一个结点序列称为根到结点r的路径。

树的例子：家族，机构等 2、树的抽象数据类型的定义约5min ADT Tree 数据对象 D：

数据关系 R：

基本操作 P：

InitTree(&T);DestroyTree(&T);CreateTree(&T,definition);ClearTree(&T);…… 3、树的术语约10min 结点：数据元素和指向子树的分枝；

终端结点（叶子），分枝结点子女：结点的子树的根称为结点的子女，该结点称为子女的双亲；

层次：根为第一层，根的子女为第二层，以此类推深度：树中结点的最大层次称为树的深度（或高度）

度：结点的分枝数目树的度：树中结点的最大度兄弟：同一双亲的子女互称兄弟，其父母为兄弟的结点互称堂兄祖先：结点的祖先是从根到该结点所经分支上的所有结点子孙：以某结点为根的子树中的任一结点都称为该结点的子孙。

有序树：结点的子树从左到右有顺序，否则，称为无序树森林树的不相交集合，除去根结点后的子树集合就是森林 RF={|i=1,2,…,m,m>0} 6.2二叉树 6.2.1二叉树的类型定义约15min 二叉树是另一种树型结构，它的特点是每个结点至多只有二棵子树（即二叉树中不存在度大于2的结点),并且,二叉树的子树有左右之分,其次序不能任意颠倒。二叉树或为空树，或是由一个根结点加上两棵分别称为左子树和右子树的、互不交的二叉树组成。(树的度最大为2)二叉树的主要基本操作：

查找类 Root(T);Value(T, e);Parent(T, e);LeftChild(T, e);RightChild(T, e);LeftSibling(T, e);RightSibling(T, e);BiTreeEmpty(T);BiTreeDepth(T);PreOrderTraverse(T, Visit());InOrderTraverse(T, Visit());PostOrderTraverse(T, Visit());LevelOrderTraverse(T, Visit());插入类 InitBiTree(&T);Assign(T, &e, value);CreateBiTree(&T, definition);InsertChild(T, p, LR, c);删除类 ClearBiTree(&T);DestroyBiTree(&T);DeleteChild(T, p, LR);6.2.2二叉树的性质约20min 性质1：

在二叉树的第i 层上至多有2i-1 个结点。

(i≥1)性质 2 ：深度为 k 的二叉树上至多含 2k-1个结点（k≥1）。

性质 3 ：对任何一棵二叉树，若它含有n0 个叶子结点（0度结点）、n2 个度为 2的结点，则必存在关系式：n0 = n2+1。

两类特殊的二叉树：

满二叉树：指的是深度为k且含有2k-1个结点的二叉树。

完全二叉树：树中所含的 n 个结点和满二叉树中编号为 1 至 n 的结点一一对应。（编号的规则为，由上到下，从左到右。）

性质 4 ：具有 n 个结点的完全二叉树的深度为 ëlog2nû +1。

性质 5 ：若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：（1）如i=1，则序号为i的结点是根结点，无双亲结点；

如i>1，则序号为i的结点的双亲结点序号为。（2）如2×i>n，则序号为i的结点无左孩子；

如2×i≤n，则序号为i的结点的左孩子结点的序号为2×i。（3）如2×i＋1>n，则序号为i的结点无右孩子；

如2×i＋1≤n，则序号为i的结点的右孩子结点的序号为2×i＋1 6.2.3 二叉树的存储结构约25min 1、二叉树的顺序存储表示 2、二叉树的链式存储表示 1).二叉链表 2)．三叉链表 3)．双亲链表 4)．线索链表三、小结约5min 1、树、二叉树的定义 2、二叉树的性质 3、存储结构四、作业约5min 1.一棵度为2的树与一棵二叉树有何区别？ 2.试分别画出具有3个结点的二叉树和3 个结点的二叉树的所有不同形态。

课时授课计划 2011-2012学年第一学期第7周授课日期 10月25日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题遍历二叉树和线索二叉树教学目的与要求：

1.遍历二叉树是二叉树各种操作的基础。掌握各种遍历策略的递归算法，灵活运用遍历算法实现二叉树的其它操作。

2.理解二叉树线索化的实质.熟练掌握二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

教学重点：

1.遍历二叉树是二叉树各种操作的基础。

2．各种遍历策略的递归算法，运用遍历算法实现二叉树的其它操作。

教学难点：

各种遍历策略的递归算法，运用遍历算法实现二叉树的其它操作。

二叉树的线索化过程以及在中序线索化树上找给定结点的前驱和后继的方法。

作业及参考书：

写出所给二叉树的前、中、后序的序列《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约3min 由二叉树的结构引出对每个结点的遍历。

二、讲课进程设计 6.3遍历二叉树和线索二叉树 6.3.1二叉树的遍历一、问题的提出约7min 顺着某一条搜索路径巡访二叉树中的结点，使得每个结点均被访问一次，而且仅被访问一次。（将树线性化）

对“二叉树”而言，可以有三条搜索路径：

Ø 1．先上后下的按层次遍历；

Ø 2．先左（子树）后右（子树）的遍历；

Ø 3．先右（子树）后左（子树）的遍历。

二、先左后右的遍历算法约10min 先（根）序的遍历算法若二叉树为空树，则空操作；

否则（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树。

中（根）序的遍历算法若二叉树为空树，则空操作；

否则（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树。

后（根）序的遍历算法若二叉树为空树，则空操作；

否则（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点。

三、算法的递归描述约10min 总结：无论先序、中序、后序遍历二叉树，遍历时的搜索路线是相同的：从根结点出发，逆时针延二叉树外缘移动对每个结点均途径三次。

先序遍历：第一次经过结点时访问。

中序遍历：第二次经过结点时访问。

后序遍历：第三次经过结点时访问。

四、中序遍历算法的非递归描述约10min 五、遍历算法的应用举例约30min 1、统计二叉树中叶子结点的个数(先序遍历)先序(或中序或后序)遍历二叉树，在遍历过程中查找叶子结点，并计数。由此，需在遍历算法中增添一个“计数” 的参数，并将算法中“访问结点”的操作改为：若是叶子，则计数器增1。

2、求二叉树的深度(后序遍历)算法基本思想: 首先分析二叉树的深度和它的左、右子树深度之间的关系。

3、复制二叉树(后序遍历)其基本操作为：生成一个结点。

4、建立二叉树的存储结构 p 不同的定义方法相应有不同的存储结构的建立算法按给定的表达式建相应二叉树由先缀表示式建树由原表达式建树我们已经知道二叉树结构和它的某个遍历序列不存在一一对应的关系，但若已知一个二叉树的前序序列和中序序列，却一定可以惟一确定一个二叉树的结构。

6.3.2线索二叉树约20min • 何谓线索二叉树？ • 遍历二叉树的结果是，求得结点的一个线性序列。

• 如何保存这种在遍历过程中得到的信息？ • 最简单的方法是在每个结点上增加二个指针域：fwd和bkwd用来指示此结点在遍历中的前驱和后继结点。

• 线索链表的遍历算法 • 由于在线索链表中添加了遍历中得到的“前驱”和“后继”的信息，从而简化了遍历的算法。

• 如何建立线索链表？结索化的实质是将二叉链表中的空指针改为指向前驱或后继的线索，而前驱或后继的信息只有在遍历时才能得到，因此线索化的过程即为在遍历的过程中修改空指针的过程。为了记下遍历过程中访问结点的先后关系，附设一个指针pre始终指向刚刚访问过的结点，若指针p指向当前访问的结点，则pre指向它的前驱。由此在中序遍历过程中修改结点的左、右指针域，以保存当前访问结点的“前驱”和“后继”信息。遍历过程中，附设指针pre, 并始终保持指针pre指向当前访问的、指针p所指结点的前驱。

三、小结约7min 1、遍历的总结 2、线索化的总结四、作业 1、对所给出的二叉树写出前、中、后序的遍历序列。

课时授课计划 2011-2012学年第一学期第7周授课日期 11月1日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题树和森林教学目的与要求：

1．熟悉树的各种存储结构及其特点，掌握树、森林与二叉树的转换方法。

2．学会编写实现树的各种操作的算法。

教学重点：

1、树、森林与二叉树的转换方法 2．学会编写实现树的各种操作的算法。

教学难点：

1、树、森林与二叉树的转换方法 2．学会编写实现树的各种操作的算法。

作业及参考书：

树和森林的转换《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 由前面树、二叉树的回顾引入二、讲课进程设计 6.4树和森林 6·4·1 树的存储结构约25min 1、双亲表示法以一组连续的存储空间存放树的结点，每个结点中附设一个指针指示其双亲结点在这连续的存储空间中的位置（下标，这种结构属静态链表）,可形式表示如下：

typrdef struct tnode { datatype data;int parent;}tree[n] 2、孩子表示法用多重链表表示。有两种方法：同构：按最大度的结点设置各结点结构，即一个数据域和d个指针域，这容易造成空间浪费；

异构：结点有几棵子树设几个指针，这样操作困难。可将其子女链在一个单链表中。其形式描述如下：

typrdef struct tagnode /* 表结点 */ { int child;struct tagnode *next;}node, *link;typedef struct /* 头结点 */ {datatype data;link headptr;}headnode;typedef headnode childlink[maxnode];/* 表头数组 */ 带双亲的孩子链表表示法：

typedef struct /* 头结点 */ {datatype data;int parent;link headptr;}headnode1;3、孩子兄弟表示法该方法又称二叉树表示法，或二叉链表表示法，即以二叉链表作存储结构，结点的两个链域分别指向该结点的第一个孩子和下一个兄弟，分别命名为fch和nsib。可形式描述如下：

typedef struct treenode {datatype data;struct treenode *fch,*nsib;}treenode ,*tree;树的这种表示本质上是二叉树的二叉链表表示。由于二叉树和树这种存储结构的一致性，从而导致树和二叉树可以相互转换。

6·4·2 森林与二叉树的相互转换约30min 1、森林转为二叉树树（树林）转换成二叉树时结果是唯一的。其转换可以递归的描述如下：若树（树林）为空，则二叉树为空；

否则，树（树林）中第一棵树的根是二叉树的根，第一棵树除去根结点后的子树林是二叉树的左子树，树林中除去第一棵树后的树林形成二叉树的右子树。

形象的说转换过程可用下面的“三步曲”来说明：

三步曲：

连线切线旋转连线：

将兄弟结点连接起来切线：

保留双亲到第一个子女的连线，将双亲到其它子女的连线切掉。

旋转：

以根为轴，平面向下顺时针方向旋转450。

2、二叉树转为树林二叉树转换成树（树林）时结果也是唯一的。

其转换可以递归的描述，若二叉树为空，则树（树林）为空；

否则，二叉树的根是树（树林）中第一棵树的根，二叉树的左子树构成树（树林）中第一棵树除去根结点后的子树林，二叉树的右子树构成树林中除去第一棵树后的树林。

形象的说是上面三步曲的逆。

6·4·3 树和森林的遍历约30min 树的遍历方法也可分为“宽度优先法”和“深度优先法”两类。前者指从（根）第一层开始，由上到下，从左往右逐个结点的遍历；

后者又可分为先根次序和后根次序。

（1）

先根次序的遍历（相当于对其相应的二叉树的先序遍历）

若树（森林）为空，则空操作，否则：

·访问左面第一棵树的根；

·按先根次序从左到右遍历此根下的子树；

·按先根次序从左到右遍历除第一棵树外的树（森林）。

（2）

后根次序的遍历（相当于对其相应的二叉树的中序遍历）

若树（森林）为空，则空操作，否则：

·按后根次序从左到右遍历最左面的树下的子树；

·访问最左面树的根；

·按后根次序从左到右遍历除第一棵树外的树（森林）；

三、小结约7min 1、树的存储 2、树与森林之间的转换 3、树和森林的遍历四、作业约3min 1、完成由树和森的转换课时授课计划 2011-2012学年第一学期第8周授课日期 11月3日五星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题哈夫曼树教学目的与要求：

1、掌握哈夫曼树的构造方法 2、掌握哈夫曼编码 3、带权路径的计算 4、了解最优树的特性教学重点：

1、哈夫曼树的构造 2、掌握建立最优树和哈夫曼编码的方法。

教学难点：

1、建立最优树和哈夫曼编码的方法 2、带权路径的计算作业及参考书：

1、构造一棵哈夫曼树并且计算其权值《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 由最优树概念的提出引入哈夫曼树二、讲课进程设计 6·6 哈夫曼树及其应用 6·6·1 最优二叉树（哈夫曼树----带权路径长度最短的树）

1、哈夫曼树的基本概念

约20min（1）

路径从树中一个结点到另一个结点之间的分支。

（2）

路径长度路径上的分支数目称为路径长度。

（3）

树的路径长度从树根到每一结点的路径长度之和，称为树的路径长度，完全二叉树是路径长度最短的二叉树。

（4）

结点的带权路径长度从该结点到树根之间的路径长度和结点上权的乘积。

（5）

树的带权路径长度树中所有叶子结点的带权路径长度之和，通常记为WPL=wili，（6）

哈夫曼树（最优二叉树）带权路径长度之和最小的二叉树称为哈夫曼树（最优二叉树）

（7）

哈夫曼编码在哈夫曼树上，左分枝为0，右分枝为1，从根结点开始，直到叶子结点所组成的编码序列，称为叶子结点的哈夫曼编码。

2、哈夫曼树在判定问题中的应用约15min 将百分制转为五级记分制的例子。说明哈夫曼树判定次数最少的树（即带权路径长度最短、最节省计算时间。）

3、如何构造哈夫曼树约20min（1）

根据给定的n个权值{w1,w2,…,wn}，构成n棵二叉树的集合F={T1,T2,…,Tn}，每棵二叉树Ti只有根结点。在F中选两棵根结点权值最小的树作为左右子树，构造一棵二叉树，新二叉树根结点的权值等于其左右子树根结点权值之和。

（2）

在F中删除这两棵子树，同时将新得到的二叉树加入F中。

（3）

重复（2）和（3），直到F中只剩一棵树（即哈夫曼树）为止。

举例说明这一过程：

应该说明，哈夫曼树的形态不是唯一的，但对具有一组权值的各哈夫曼树的WPL是唯一的。

6·6·2 哈夫曼编码 1、哈夫曼编码提出的背景约10min(1)如何使电报编码变短，非前缀编码出现二义性。(2)用二叉树可以构造前缀编码。(3)由哈夫曼树得到最优编码。

2、构造哈夫曼树和哈夫曼编码的算法约20min 前缀编码：任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀。

如A B C D 四个字符的使用率由高到低，编码为A---0 B---10 C---110 D---111 利用赫夫曼树可以构造一种不等长的二进制编码，并且构造所得的赫夫曼编码是一种最优前缀编码，即使所传电文的总长度最短。哈夫曼编码算法的实现：由于哈夫曼树中没有度为1的结点，则一棵有n个叶子的哈夫曼树共有2×n－1个结点，可以用一个大小为2×n－1 的一维数组存放哈夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成一个静态三叉链表。

三、小结约5min 1、构造哈夫曼树2、哈夫曼编码四、作业约5min 1、求由带权9、1、3、5、6的5个叶子节点生成的哈夫曼树的带权路径长度。

2、设哈夫曼树的叶节点数为n0，则它的节点总数为多少？课时授课计划 2011-2012学年第一学期第8周授课日期 10月27日五星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题树与二叉树复习习题课教学目的与要求：

1．熟悉二叉树结点的结构和对二叉树的基本操作。

2．掌握对二叉树每一种操作的具体实现。

3．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

教学重点：

1．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

教学难点：

1、利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

课堂类型：

总结复习教学过程：

提出问题――对问题提示――完成问题――检查二叉树基本操作复习目的 4．熟悉二叉树结点的结构和对二叉树的基本操作。

5．掌握对二叉树每一种操作的具体实现。

6．学会利用递归方法编写对二叉树这种递归数据结构进行处理的算法。

复习内容该程序的功能是实现二叉树结点的类型定义和对二叉树的基本操作。该程序包括二叉树结构类型以及每一种操作的具体的函数定义和主函数。

/* 定义DataType为char类型 */ typedef char DataType;/* 二叉树的结点类型 */ typedef struct BitNode {DataType data;struct BitNode *lchild,*rchild;}BitNode,*BitTree;/* 初始化二叉树，即把树根指针置空 */ void BinTreeInit(BitTree *BT)/* 按先序次序建立一个二叉树*/ void BinTreeCreat(BitTree *BT)/* 检查二叉树是否为空 */ int BinTreeEmpty(BitTree *BT)/* 按任一种遍历次序（包括按先序、中序、后序、按层次）输出二叉树中的所有结点 */ void BinTraverse(BitTree *BT)/* 求二叉树的深度 */ int BinTreeDepth(BitTree BT)/* 求二叉树中所有结点数 */ int BinTreeCount(BitTree BT)/* 清除二叉树，使之变为空树 */ void BinTreeClear(BitTree * 课时授课计划 2011-2012学年第一学期第11周授课日期 11月8日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题图的定义和术语图的存储结构教学目的与要求：

1、掌握图的定义及常用术语 2、掌握图的二种存储表示法教学重点：

1、图的常用术语 2、图的数组表示及邻接表表示法教学难点：

1、图的常用术语 2、邻接表表示法作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 由各城市之间的通信引出图二、讲课进程设计第七章图对图进行概述约5min 图是一种比线性表和树都复杂的数据结构。在图结构中，结点之间的关系是任意的，图中任意两个元素之间都可能有关系。图的应用非常广泛。

7.1图的定义和术语 1、图的定义

约5min 图是一种数据结构，其形式化定义可写为 Graph=(V,R)其中，V={x|xdatatype} R={VR} VR={|P(x,y)(x,yV)} 在图中，数据元素常称为顶点，V是顶点的有穷集合；

R是边（弧）的有穷集合。

2、抽象数据类型图的定义约5min ADT Graph {数据对象V：

数据关系R：

基本操作P：

}ADT Graph 3、图的术语概念约15min(1)有向图、无向图弧：;边(x,y)。

(2)有（无）向完全图稀疏图稠密图子图无向完全图：n个顶点n(n-1)/2条边；

有向完全图：n个顶点n(n-1)条弧；

(3)权、网和边（弧）相关的数叫权，带权的图称网。

(4)邻接、邻接点无向图：一条边连起来的两个顶点，互称邻接点；

有向图：若从顶点x到顶点y有一条弧，则说顶点x邻接到顶点y，而顶点y邻接自顶点x。

(5)度、出度、入度无向图中和顶点相关的边(e)的个数叫顶点的度。e= 有向图中从顶点出发的弧的个数叫该顶点的出度，入到该顶点的弧的个数叫该顶点的入度。TD(v)=ID(v)+OD(v)(6)路径、路径长度、回路(环)、简单路径(7)连通、连通图、连通分量无向图顶点v1到顶点v2有路径，则说v1和v2连通。若任意两个顶点都连通，则说该图是连通的。连通分量是无向图中的极大连通子图。

(8)强连通图、强连通分量(9)生成树、有向树、生成森林一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，但只有足以构成一棵树的n-1条边。

若有向图中只有一个顶点的入度为0，其余顶点的入度均为1，则该有向图称为有向树。有向图的生成森林由若干棵有向树组成，含有图的全部顶点，但只有足以构成若干棵不相交的有向树的弧。

7·2 图的存储结构 7·2·1 图的顺序存储结构----数组表示法约20min 1、数组表示法用两个数组分别表示数据元素的（顶点）的信息和边（弧）的信息若顶点只有编号信息，边（弧）只是有无，则可用下面的邻接矩阵来表示。

2、邻接矩阵的定义有n个顶点的图G=(V,{VR})的邻接矩阵为n阶方阵，其定义为：

0 若（vi,vj）或VR 3、无向图邻接矩阵的性质（1）

无向图的邻接矩阵是对称矩阵；

（2）

顶点vi的度是邻接矩阵中第i行（或第i列）的元素(1)之和。

4、有向图邻接矩阵的性质（1）

有向图的邻接矩阵不一定是对称矩阵；

（2）

顶点vi的出度是邻接矩阵中第i行元素之和，入度是邻接矩阵中第i列的元素之和 5、网的邻接矩阵将邻接矩阵中的0、1换成权值，就是网的邻接矩阵。

6、邻接矩阵的优缺点容易实现图的前4个操作。容易判定顶点间有无边（弧），容易计算顶点的度（出度、入度）；

缺点是所占空间只和顶点个数有关，和边数无关，在边数较少时，空间浪费较大。

7、建立邻接矩阵的算法 7·2·2 图的邻接表表示法约15min 邻接矩阵在稀疏图时空间浪费较大，为了克服这一缺点，可采用邻接表表示法。

1、邻接表的结点结构 2、邻接表是顶点的向量结构和边（弧）的单链表结构每个顶点结点包括两个域，将n个顶点放在一个向量中（称为顺序存储的结点表）；

一个顶点的所有邻接点链接成单链表，该顶点在向量中有一个指针域指向其第一个邻接点。

3、邻接表的优缺点容易实现图的前4个操作；

空间较省；

无向图容易求各顶点的度；

边表中结点个数是边的两倍；

有向图容易求顶点的出度；

若求顶点的入度则不容易，要遍历整个表。为了求顶点的入度，有时可设逆邻接表（指向某顶点的邻接点链接成单链表）

4、建立邻接表的算法 7·2·3 图的十字链表表示法约15min 在有向图的邻接表表示法中，查每个顶点的出度非常容易，但查顶点的入度就要遍历整个邻接表。解决的办法是建立逆邻接表，但这成了两个表，也不方便。本节介绍有向图的另一种表示方法，即十字链表表示法 7·2·4 图的邻接多重表表示法约10min 这是无向图的另一种表示方法。因为在邻接表中，每条边需要两个边结点，在以边为主处理图时，需判断此边是否处理过，增加了复杂性。图的邻接多重表中每个边只有一个结点三、小结约5min 1、图的基本概念及术语 2、图的两种存储结构之间的比较课时授课计划 2011-2012学年第一学期第11周授课日期 11月15日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题图的遍历图的连通性问题教学目的与要求：

1、掌握图的深度优先遍历的方法及算法 2、掌握广度优先遍历的方法及算法 3、掌握最小生成树教学重点：

1、深度优先遍历 2、最小生成树教学难点：

1、深度优先遍历 2、最小生成树作业及参考书：

1、图的基本概念 2、生成树 3、最小生成树《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 复习图的存储结构，引出图的遍历二、讲课进程设计 7.3 图的遍历 7.3.1、深度优先搜索遍历图约20min 连通图的深度优先搜索遍历从图中某个顶点V0 出发，访问此顶点，然后依次从V0的各个未被访问的邻接点出发深度优先搜索遍历图，直至图中所有和V0有路径相通的顶点都被访问到。

7.3.2、广度优先搜索遍历图约15min 对连通图，从起始点V到其余各顶点必定存在路径。从图中的某个顶点V0出发，并在访问此顶点之后依次访问V0的所有未被访问过的邻接点，之后按这些顶点被访问的先后次序依次访问它们的邻接点，直至图中所有和V0有路径相通的顶点都被访问到。若此时图中尚有顶点未被访问，则另选图中一个未曾被访问的顶点作起始点，重复上述过程，直至图中所有顶点都被访问到为止。

7.3.3、遍历应用举例约10min 1、求两个顶点之间的一条路径长度最短的路径 7.4图的连通问题 7.4.1无向图的连通分量和生成树

约15min 1、在对图遍历时，对于连通图，从任一个顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访问序列恰为各连通分量中的顶点集。

2、生成树对于连通图，调用DFS或BFS所经过的边的集合和图的全部顶点构成了图的极小连通子图，即连通图的一棵生成树。

3、生成森林对于非连通图，每个连通分量的顶点集和所经过的边一起构成若干棵生成树，这些连通图的生成树构成非连通图的生成森林。

7.4.3最小生成树约25min 普里姆(Prim)算法的基本思想:取图中任意一个顶点 v 作为生成树的根，之后往生成树上添加新的顶点 w。在添加的顶点 w 和已经在生成树上的顶点v 之间必定存在一条边，并且该边的权值在所有连通顶点 v 和 w 之间的边中取值最小。之后继续往生成树上添加顶点，直至生成树上含有 n-1 个顶点为止。

克鲁斯卡尔算法的基本思想：考虑问题的出发点: 为使生成树上边的权值之和达到最小，则应使生成树中每一条边的权值尽可能的小。

三、小结约5min 1、深度优先搜索遍历图 2、最小生成树四、作业约5min 1、已知如右图所示的有向图，请给出该图的（1）每个顶点的入/出度；

（2）邻接矩阵；

（3）逆邻接表；

（4）强连通分量；

2、画出以顶点v1为初始源点遍历图所示的有向图所得到的DFS 和BFS生成森林。

3、对图（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。课时授课计划 2011-2012学年第一学期第12周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题拓扑排序最短路径教学目的与要求：

1、掌握拓扑排序 2、掌握迪杰斯特算法教学重点：

1、拓扑排序 2、最短路径教学难点：

拓扑排序作业及参考书：

7.1已知如右图所示的有向图，请给出该图的（1）每个顶点的入/出度；

（2）邻接矩阵；

（3）逆邻接表；

（4）强连通分量；

7.2画出以顶点v1为初始源点遍历图（下图）所示的有向图所得到的DFS 和BFS生成森林。

7.3对图（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。7.4已知如图所示的AOE网，试求：每个事件的最早发生时间和最晚发生时间；

每个活动的最早开始时间和最晚开始时间；

给出关键路径。

7.5 试基于图的深度优先策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i!=j)。

注意：算法中涉及的图的基本操作必须在此存储结构上实现。

7.6 试利用栈的基本操作编写，按深度优先搜索策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Craph看成是一种抽象的数据类型《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 由城市之间的通信引入二、讲课进程设计 7.5有向无环图及其应用有向无环图的基础约10min 1、有向无环图的定义无环的有向图叫有向无环图，简称DAG图。

2、用DAG图描述带公共子式的表达式((a+b)*(b*(c+d))+(c+d)*e)*((c+d)*e)3、有向图中是否有环的检查 4、有向无环图的应用有向无环图是描述工程或系统的进行过程的有效工具。一是工程能否顺利进行，二是估算工程完成所需的最短时间，这就是拓扑排序和关键路径问题。

7·5·1 拓扑排序约20min 1、拓扑排序的基本概念（1）

AOV网顶点表示活动，弧表示活动间的优先关系的有向图，叫顶点表示活动的网（Activity On Vertex Network）。

（2）拓扑序列将AOV网上的所以顶点排成一个线性序列，且该序列满足若在AOV网中，顶点vi到vj有一条路径，则在该线性序列中vi必在vj的前面。这样的序列称为拓扑序列。

（3）

拓扑排序对AOV网构造拓扑序列的操作叫拓扑排序。

（4）在AOV网中不应有环，否则就会自己以自己为先决条件；

若AOV网代表一个工程，则AOV网的一个拓扑序列就是一个工程顺利完成的可行方案。

2、拓扑排序的方法 1）从图中选择一个入度为0的顶点输出；

2）从图中删除该顶点及源自该顶点的所有弧；

3）

重复以上两步，直至全部顶点都输出，拓扑排序顺利完成。否则，若剩有入度非0的顶点，说明图中有环，拓扑排序不能进行。

3、拓扑排序算法在邻接表的顶点向量中，向量的每个元素再增加一个入度域，存放各顶点的入度值。输出该顶点，删除源自该顶点的弧就是将该顶点的邻接点的入度减1。实际实现时，可设一个栈，存放入度为0的顶点，退栈就是输出顶点，当邻接点的入度域减1减到0时，就将其入栈，拓扑排序完成时，栈应为空。

4、拓扑排序算法的分析 O（n+e）

7·5·2 关键路径约25min 1、AOE网用顶点表示事件，弧表示活动，弧上的权值表示活动持续的时间的有向图叫AOE（Activity On Edge Network）网。AOE网常用于估算工程完成时间。

2、AOE网研究的问题 1)完成整个工程至少需要多少时间；

2)哪些活动是影响工程的关键。

1956年，美国杜邦公司提出关键路径法，并于1957年首先用于1000万美圆化工厂建设，工期比原计划缩短了4个月。杜邦公司在采用关键路径法的一年中，节省了100万美圆。

3、关键路径的几个术语（1）

关键路径从源点到汇点的路径长度最长的路径叫关键路径。

（2）

活动开始的最早时间e(i)（3）

活动开始的最晚时间l(i)定义e(i)=l(i)的活动叫关键活动。

（4）

事件开始的最早时间ve(i)（5）

事件开始的最晚时间vl(i)4、求关键路径的算法(1)输入e条弧，建立AOE网的存储结构。

(2)从源点v1出发，令ve(1)=0,求 ve(j)2<=j<=n。

(3)从汇点vn出发，令vl(n)=ve(n),求 vl(i)1<=i<=n-1。

(4)根据各顶点的ve和vl值，求每条弧s（活动）的最早开始时间e(s)和最晚开始时间l(s)，其中e(s)=l(s)的为关键活动。

求关键路径是在拓扑排序的前提下进行的，不能进行拓扑排序，自然也不能求关键路径。

5、求关键路径的算法分析（1）

求关键路径必须在拓扑排序的前提下进行，有环图不能求关键路径；

（2）

只有缩短关键活动的工期才有可能缩短工期；

（3）

若一个关键活动不在所有的关键路径上，减少它并不能减少工期；

（4）

只有在不改变关键路径的前提下，缩短关键活动才能缩短整个工期。

7.6最短路径网络中的常见问题：两点间是否有通路，哪条路径最短。本书讨论两类问题：一类是从一个顶点到其它顶点间的最短路径，另一类是任意两顶点间的最短路径。这都是有向图的应用。

7·6·1 从某个源点到其它各顶点间的最短路径约10min 这里路径指两顶点间的通路，路径的长度指所有经过的边的总长。“最短路径”的问题指当两个顶点间通路多于一条时，如何找出边长总和为最短的那条。Dijkstra提出按路径长度递增的次序求最短路径的方法。

1、Dijkstra 求最短路径的基本思想把顶点分成两组，第一组是已确定最短路径的结点的集合，第二组是尚未确定最短路径的结点的集合。按路径长度递增的次序逐个把第二组的顶点放到第一组中。设求从v1到其它各顶点间的最短路径,则在任意时刻，从v1到第一组各顶点间的最短路径都不大于从v1到第二组各顶点间的最短路径。

2、Dijkstra 求最短路径的步骤设图以邻接矩阵arcs存储，矩阵中各元素的值为各边的权值。顶点间无边时其对应权值用无穷大表示。

3、Dijkstra 求最短路径的实例模拟 4、Dijkstra 求最短路径的算法 5、Dijkstra 求最短路径的算法分析对于n个顶点的图，求一个顶点到其余顶点的最短路径，循环n-1次，加上修改最短路径的循环，是二层循环，故时间复杂度为O(n2)。若只求从源点到某一顶点间的最短路径，和求到其余顶点间的最短路径相同，时间复杂度也是O(n2)。

6·4·2 每一对顶点间的最短路径约20min 对于n个顶点的图，求每一对顶点间的最短路径，方法有二：一是按Dijkstra算法，求每一个顶点到其它各顶点间的最短路径，即是在上面基础上，再加一层循环，时间复杂度是O(n3)，另一种方法是弗洛伊德（floyd）提出来的，时间复杂度也是O(n3)，但形式上简单。

1、弗洛伊德（floyd）算法的基本思想设求顶点vi到vj间的最短路径，若vi到vj有弧，则弧上的权值是一条路径，但未必是最短路径，要经过n-1次测试。首先将顶点v1加入，即看(vi,v1),(v1,vj)是否有路径，且比(vi,vj)低，如是，则用后两段路径代替，并称这是vi到vj中间顶点序号不大于1的最短路径。再将顶点v2加入，得到vi到vj中间顶点序号不大于2的最短路径。如此下去，直到vn加入，得到vi到vj中间顶点序号不大于n的最短路径，算法结束。

2、弗洛伊德（floyd）算法的实例模拟 4、弗洛伊德（floyd）算法三、小结约3min 1、拓扑排序 2、最短路径四、作业及习题约8min 7.1已知如右图所示的有向图，请给出该图的（1）每个顶点的入/出度；

（2）邻接矩阵；

（3）逆邻接表；

（4）强连通分量；

7.2画出以顶点v1为初始源点遍历图（下图）所示的有向图所得到的DFS 和BFS生成森林。

7.3对图（下图）所示的连通图，请分别用Prim和Kruskal算法构造其最小生成树。7.4已知如图所示的AOE网，试求：每个事件的最早发生时间和最晚发生时间；

每个活动的最早开始时间和最晚开始时间；

给出关键路径。

7.5 试基于图的深度优先策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径（i!=j)。

注意：算法中涉及的图的基本操作必须在此存储结构上实现。

7.6 试利用栈的基本操作编写，按深度优先搜索策略遍历一个强连通图的非递归形式的算法。算法中不规定具体的存储结构，而将图Craph看成是一种抽象的数据类型课时授课计划 2011-2012学年第一学期第12周授课日期 11月17日五星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题图总结复习教学目的与要求：

1、掌握图的各种存储结构。

教学重点：

要熟练掌握邻接矩阵和邻接表存储结构教学难点：

要熟练掌握邻接矩阵和邻接表存储结构作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

课堂类型：

教学过程：提出问题――对问题提示――完成问题――检查图的基本操作复习目的 1．掌握图的各种存储结构，特别要熟练掌握邻接矩阵和邻接表存储结构。

2．遍历是图各种应用的算法的基础，要熟练掌握图的深度优先遍历和广度优先遍历算法，复习栈和队列的应用。

复习内容程序1 /* 定义邻接矩阵类型 */ typedef int adjmatrix[n+1][n+1];/* 建立图的邻接矩阵 */ void CreatMatrix(adjmatrix GA)/* 从初始点v出发深度优先遍历邻接矩阵GA表示的图 */ void DfsMatrix(adjmatrix GA,int v)/*从初始点v出发广度优先遍历邻接矩阵GA表示的图*/ void BfsMatrix(adjmatrix GA,int v)程序2 /* 邻接表的结点类型 */ typedef struct arc {int adjvex;struct arc *next;}ArcNode;typedef struct VexNode {int vertex;ArcNode *firstarc;}VerNode;typedef VerNode AdjList[MAXNODE];/* 建立图的邻接表 */ void CreatAdjlist(AdjList GL)/* 从初始点v出发深度优先遍历邻接表GL表示的图 */ void DfsAdjlist(AdjList GL,int v)/*从初始点v出发广度优先遍历邻接表GL表示的图*/ void BfsAdjlist(AdjList GL,int v)课时授课计划 2011-2012学年第一学期第13周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题静态查找表动态查找表（上）

教学目的与要求：

1、熟练掌握顺序表和有序表的查找方法。

2、熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系。

3、熟练掌握二叉排序树的构造和查找方法。

4、掌握二叉平衡树的维护平衡方法。

教学重点：

1、查找的基本概念2、折半查找3、二叉排序树的实现4、平衡二叉树教学难点：

1、顺序查找的性能分析 2、折半查找 3、构造二叉排序树、平衡二叉树作业及参考书：

1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：

(1)查找不成功，即表中无关键字等于给定值K的记录；

(2)查找成功，即表中有关键字等于给定值K的记录。

2.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。

3.画出对长度为10的有序表进行折半查找的判定树，并求其等该率时查找成功的平均查找长度。

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约3min 由日常生活中遇到的如找电话、查找一个学生的信息引入。

二、讲课进程设计第九章查找基本定义约5min 1、查找的定义查找其关键字等于给定值的操作。

2、关键字的概念关键字是数据元素（或记录）中某个数据项的值，可以标识一个记录，若能唯一标识，则称为主关键字，否则，称为次关键字。

3、查找的结果若查到其关键字等于给定值的记录，则称“查找成功”，否则，称“查找失败”。

4、查找算法效率的度量（1）平均查找长度ASL：在查找其关键字等于给定值的过程中，需要和给定值进行比较的关键字个数的期望值称为查找成功时的平均查找长度。

（2）所需的辅助存储空间 9.1 静态查找表 9·1·1 顺序查找约12min 1、顺序查找的定义用待查关键字和线性表中各结点的关键字逐个比较，直到找到关键字值相等的结点，即查找成功；

或查完全表，而未找到关键字相等的结点，即为查找失败。

2、顺序查找的算法 3、顺序查找算法的时间复杂度平均查找长度ASL: 查找成功 ==(1)查找失败 n+1(2)设查找成功的概率为p,查找成功的概率为q=(1-p),则平均比较次数为：

E(n)=p.+q.(n+1)= p.+(1-p).(n+1)=(n+1).(1-);若成功和失败的概率各占50%,平均性能。

若查找各结点的概率不等，应将查找概率高的结点放在前边，以提高查找效率。

9·2·2 有序表的查找（二分查找）

约20min 1、二分法查找的基本概念若顺序表中元素已按关键字有序排列，查找时不必顺序查找，而是用待查关键字与中间位置的元素的关键字比较，若相等，则查找成功；

若待查关键字小，则在由中间位置分开的左子表中查找，否则，在右子表中进行。如此下去，直至查找成功或查找失败。

2、二分法查找的算法 3、二分法查找的时间复杂度二分法查找的过程可用二叉树来描述，中间结点是二叉树的根，左子表相当于左子树，右子表相当于右子树，由此得到的二叉树便为描述二分法查找的判定树。二分法查找的过程是走了一条从根结点到叶子结点的过程，不论查找成功与失败，查找长度均不超过树的高度，其平均性能为h= élog2(n+1)ù。

4、二分法查找的优缺点优点：查找速度快；

但表必须有序。

缺点：频繁插入和删除不方便。

二分法查找适于表中元素很少变化而查找频繁的情况；

顺序表查找适于查找少而表中元素频繁变化的情况。

9·2·3 索引顺序表的查找（分块查找）约15min 分块查找综合了顺序查找和二分法查找的优点，既有动态结构，又适于快速查找。

1、分块查找的基本思想将待查找文件等长的分为若干个子文件（最后一个子文件长度可能小）。子文件内的元素无序，但子文件之间有序，即第一个子文件的最高关键字小于第二个子文件的最高关键字，第二个子文件的最高关键字小于第三个子文件的最高关键字，依次类推。再建立一个索引表（文件），文件中的每个元素含有各子文件的最高关键字和各子文件中第一个元素的地址（下标），索引文件按关键字有序。

查找时，对索引表可以顺序查找或二分法查找，在块内只能顺序查找。

2、分块查找的平均长度设待查找文件有n个记录，平均分成b块，每块有s个记录。若只考虑查找成功的概率，且在块内和索引表中均用顺序查找，则平均查找长度为：

E(n)=Eb+Ew=+=(s2+2s+n)/(2s)若s=，则平均查找长度取最小值：+1 若对索引表采用二分法查找，则平均查找长度为：

E(n)=Eb+Ew=élog2(b+1)ù+ 3、几种查找方法的比较 9·2 动态查找表适应元素结点的动态插入与删除。

9·2·1 二叉排序树 1、什么叫二叉排序树约10min（1）

二叉排序树的定义二叉排序树或为一棵空树，或为具有如下性质的二叉树：

· 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值；

· 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值；

· 它的左右子树也分别是二叉排序树。

（2）

二叉排序树的建立实例设关键字序列k=(k1,k2,…,km)(m>0)，则建立二叉排序树的步骤如下：

· 令关键字k1为二叉排序树的根；

·若k1>k2，则k2做k1左子树的根结点，否则做k1右子树的根结点；

在子树中继续子树的根比较重复前面的操作；

· 对序列中的其它关键字递归使用上面步骤。

例如，给定关键字序列: k=(45,12,53,3,37,100,24,61,90,78)（3）

中序（对称序）遍历二叉排序树所的结点序列是有序序列对二叉排序树进行中序遍历，其遍历序列是一个有序序列，这是由二叉排序树的定义决定的。

（4）

二叉排序树中结点的插入在二叉排序树中插入结点，只要保证插入结点后的二叉排序树仍然是二叉排序树就行了，插入的结点都是叶子结点，其结果是唯一的。

（5）

二叉排序树中结点的删除在二叉排序树中删除结点，删除结点后的二叉排序树仍然是二叉排序树，但其结果不是唯一的。而且，当一个结点被删除后，再将其立即插入，所得二叉排序树与结点删除前得二叉排序树一般来说形态不等。

2、最佳二叉排序树约10min（1）

最佳二叉排序树的定义有n个结点的二叉树，共有n!个不同的二叉排序树，其中，平均查找（检索）长度最短的那棵二叉排序树叫最佳二叉排序树。

（2）

扩充的二叉排序树将二叉树中度为1和0的结点，都补充上虚结点，使每个结点（除虚结点外）的度均为2，这样的二叉树称为扩充的二叉排序树。设所加虚结点的个数为N，原有结点（称为内部结点）个数为n，由于这时的二叉树无度为1的结点，根据二叉树的性质3，则下式成立：

N=n+1 若定义外部路径长度是扩充的二叉树的根到每个外部结点的路径长度之和，用E表示。内部路径长度是指从扩充的二叉树的根到每个内部结点的路径长度之和，用I表示，则下式成立：

E=I+2n 可用数学归纳法证明如下：

当n=1时，I=0，E=2，等式成立；

设有n个内部结点时，下式成立 En= In+2n（1）

考虑n+1个结点的扩充二叉树，当删去一个内部结点时，若此结点的路径长度为K，则有 In=In+1-K(2)而这时的外部路径长度减少了两个路径长度为K+1的外部结点，增加了一个路径长度为K的内部结点。即 En=En+1-2(K+1)+K(3)由以上三式，有 En+1= En+2(K+1)-K =(In+2n)+K+2 =((In+1-K)+2n)+K+2 =In+1+2(n+1)证毕。

（3）

二叉排序树的检索效率E（n）<=1+4logn（4）

如何构造最佳二叉排序树首先将关键字排序，将所得有序表构造静态查找的判定树，所得二叉树即为最佳二叉排序树。判定树是唯一的，但按着最佳二叉排序树的定义，最佳二叉排序树是不唯一的。

3、平衡二叉树(AVL树)约10min 二叉排序树在最差情况下成为单枝树，检索效率等同顺序表。最佳二叉排序树难于构造，因此提出一种称为平衡二叉树的二叉排序树，它的检索效率界于最佳二叉排序树和一般二叉排序树之间，要求树中任一结点的左右子树的高度差都不大于1。四种旋转：LL，RR，LR，RL 三、小结约3min 1、顺序存储2、动态存储四、作业约2min 1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：

(1)查找不成功，即表中无关键字等于给定值K的记录；

(2)查找成功，即表中有关键字等于给定值K的记录。

2.设有序表为(a,b,c,e,f,g,i,j,k,p,q),请分别画出对给定值b,g和n进行折半查找的过程。

课时授课计划 2011-2012学年第一学期第13周授课日期 12月6日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题B树哈希表教学目的与要求：

1、B－树的建树，查找 2、哈希表的构造 3、查找时间教学重点：

1、B－树的构造，查找 2、哈希表的构造教学难点：

1、B－树构造 2、哈希表的构造作业及参考书：

1、B－树构造 2、哈希表的构造《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约3min 由前面所讲的动态存储引入B－树和哈希表。

二、讲课进程设计 9.2.2 B-树和B+树

约25min 1．B-树的定义B-树是一种平衡的多路查找树：

2．查找过程：从根结点出发，沿指针搜索结点和在结点内进行顺序（或折半）查找两个过程交叉进行。

3．插入在查找不成功之后，需进行插入。显然，关键字插入的位置必定在最下层的非叶结点。

4．删除和插入的考虑相反，首先必须找到待删关键字所在结点，并且要求删除之后,结点中关键字的个数不能小于ém/2ù-1，否则，要从其左(或右)兄弟结点“借调”关键字，若其左和右兄弟结点均无关键字可借(结点中只有最少量的关键字)，则必须进行结点的“合并”。

5．查找性能的分析在B-树中进行查找时，其查找时间主要花费在搜索结点（访问外存）上，即主要取决于B-树的深度。

结论：

在含 N 个关键字的 B-树上进行一次查找，需访问的结点个数不超过logém/2ù((N+1)/2)+1 9·3 哈希表 9·3·1 什么是哈希表约12min 1、散列函数的提出从前讲的检索，都是用待检索的关键字和各记录的关键字比较，若相等，则检索成功，否则，继续比较。我们希望找到一个函数，对关键字进行计算，把函数值解释为记录的存储地址，这就是散列检索。所用的函数就叫散列函数。用散列法存储的线性表叫散列表。查找时也用同样方法计算地址，到相应单元去找记录。若找到，则查找成功；

若该单元无记录，则查找失败；

若该单元有记录，但不是所找，要继续查找。这种方法也称关键字-地址转换法。

2、散列检索的术语（1）

碰撞（冲突）：两个关键字不同，但其散列函数值相同，即key1<>key2，f(key1)=f(key2)。冲突是不可避免的，举标识符的例子。1939年 davenport的“生日悖论”。

（2）

同义词：发生碰撞（冲突）的关键字称为同义词。

（3）

负载因子：定义为a=（散列表中结点的数目）/（散列表的长度）a一般取0.6~0.9（4）

采用散列表着重考虑两个问题：选择一个好的散列函数；

选择一种解决碰撞（冲突）的方法。

3、对散列表较详细的叙述根据设定的散列函数h(key)和处理冲突的方法，将一组关键字映象到一个有限的连续的地址集（区间）上，并以关键字在地址集中的“象”作为记录在表中的存储位置，这种表称为散列表，这一映象过程叫散列（或哈希造表），所得存储地址称散列地址或哈希地址。

9·3·2 哈希函数的构造方法

约20min 1、数字选择法分析关键字的各位，去掉分布不均匀的位，留下均匀的位作为地址。

2、平方取中法一个数平方后，结果的中间几位和数的各位都有关系，可以取中间几位作为地址。

3、折叠法关键字位数较多，分布均匀，用折叠法。折叠法又分为移位折叠和间界折叠。

4、除余法关键字除以p的余数作为地址：h(key)=key mod p 通常p取小于散列表长的最大素数。

5、基数转换法将一个小基数的数看作大基数的数，再转换为小基数的数。

6、随机数法 H(key)=random(key)9·3·3 处理冲突的方法约20min 处理冲突的方法分两大类：拉链法和开放地址法。

1、拉链法拉链法的基本思想是，散列表（向量）的每个元素由两个域组成，一个域存放关键字，另一个域是一个地址指针，指向该关键字的同义词，若无同义词，该域为空。

（1）

建立分离的同义词子表的方法：象从前动态建立单链表一样，将同义词建成单链表。例如，关键字序列为283,255,377,407,384,801,803,203,659,491,775,519,611,99，设向量空间为0—18，散列函数为h(key)=key mod 19。

其检索（查找）方法是，先计算关键字地址，若该地址处无关键字，则检索失败；

若该地址正是要找的关键字，则检索成功；

若该地址有关键字，但不是所找的关键字，则顺链查找，直到检索成功或链为空时失败。

(2)建立结合的同义词子表的方法：

该方法不另动态开辟空间建立单链表，而是利用散列表向量空间，当遇到同义词时，要在向量空间中从后向前找尚未占用的空间，将同义词放入其中，并从关键字地址（下标）往该同义词处拉上链（静态链表）。这种方法易产生堆积（聚集），即同义词和非同义词争夺同一散列地址。解决方法用两遍处理：第一遍只插入同义词子表表头的关键字，第2遍插入其它关键字。

2、开放地址法开放地址法处理冲突的基本思想是：当发生冲突时，使用某种方法在散列表中形成一个探查序列，沿着此探查序列逐个单元的查找，直到找到给定的关键字或碰到一个开放的地址（即该单元为空）为止。若插入时碰到开放地址，则插入其中；

若查找时碰到开放地址，则查找失败。

（1）

开放定址法 Hi=(H(key)+di)mod m(i=1,2,…,m-1)其中，H(key)为散列函数，m为散列表长度，di为增量序列，有以下三种取法：

· di=1,2,…,m-1, 称为线性探查再散列，其探查单元序列为：d+1,d+2,…,m-1,0,…,d-1。

· di=12,-12,22,-22,32,…,+(-)k2,(k<=m/2),称为二次探查再散列。

· di=伪随机数序列，称伪随机探查再散列。

（2）

双散列函数探查法就是当一个散列函数计算散列地址发生冲突时，使用第二个散列函数进行计算。设两个散列函数h1和h2，以关键字为自变量，设m为素数，可以取 h1(key)=key mod m且h2(key)=key mod(m-2)+1或h2(key)=[key/m] mod(m-2)+1 若h1(key)=d发生碰撞，双散列函数的探查序列为：

(d+h2(key))mod m,(d+2h2(key))mod m,(d+3h2(key))mod m 双散列函数的探查法的检索过程，与其造表类似。

9·3·4 散列表的查找及分析约12min 三、小结约3min 1、B－树2、哈希表四、作业约6min 1．由序列（24，56，42，86，70，61）构造2-3树 2．已知散列函数为H(K)=K mod 12,健值序列为25，37，52，43，84，99，120，15，26，11，70，82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度课时授课计划 2011-2012学年第一学期第14周授课日期 6月13日三星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题排序的概念插入排序快速排序教学目的与要求：

1.了解排序的定义和各种排序方法的特点。熟悉各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序和计数排序等五类。

2.掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。

3．理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

教学重点：

熟悉不同种方法的排序过程及其依据的原则教学难点：

熟悉不同种方法的排序过程及其依据的原则作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约5min 由现实生活中遇到的问题引入排序的作用，从而引入排序。

二、讲课进程设计第十章内部排序 10·1 基本概念约15min 1、排序的定义：在排序中结点（数据元素）称为“记录”，记录的集合称为“文件”，内存中的文件也常称为“线性表”。

2、排序的分类内部排序和外部排序内部排序可以分为5大类：插入排序、选择排序、交换排序、分配排序和归并排序。

3、稳定排序和不稳定排序若待排序文件中有关键字相等的记录，排序后，其前后相对次序与排序前未发生变化，这种排序称为“稳定”排序，否则是“不稳定”排序。稳定排序与不稳定排序表示所用的排序方法，并不说明哪种方法好与差。

4、排序中记录的存储方式顺序存储结构静态链表地址排序 5、排序算法的评价（1）

算法执行时所需要的时间最好情况，最差情况，平均情况算法执行时所需要的附加空间如无特别说明，本书排序指记录关键字按递增排序，以数组作为待排序记录文件的存储结构。

10·2 插入排序 10·2·1 直接插入排序约10min 1、直接插入排序的基本思想：

先假定第一个记录是有序序列，然后，从第二个记录开始，依次将记录插入到前边有序的序列中，直至全部记录序列有序。为了避免总要查询文件尾，特设“监视哨”。

2、直接插入排序的实例模拟 3、直接插入排序的算法 4、直接插入排序的算法复杂度空间复杂度：只占一个单元（r[0]）;时间复杂度：

（1）最佳情况：待排序文件已经有序，这时对每个关键字只进行一次比较，总共进行=n-1次比较，记录移动次数=2(n-1)。

（2）最差情况：待排序文件完全逆序，这时对第i（2<=i<=n）个记录要和前i-1次比较，总的比较次数为=(n+2)*(n-1)/2，记录移动次数达最大值==(n+4)*(n-1)/2（2）

平均情况平均比较次数和平均移动次数均约为n2/4。

10·2·2 希尔(shell)排序约20min 又称缩小增量排序，是shell在1959年提出的。

1、基本思想当待排序记录较少和待排序记录基本有序时，直接插入排序的效率较高。基于这种思想，希尔提出将待排序记录分为d组，相距d的记录放在一组，进行直接插入排序。

2、Shell 排序的分组选择有人认为，di都取成奇数好，有人认为di之间互质为好。di系列要选没有除1以外的公因子。

3、排序实例 4、Shell 排序算法 5、Shell 排序的算法复杂度 10·3 快速排序 10·3·1 起泡排序约15min 1、起泡排序的基本思想起泡排序也称冒泡排序，若待排序记录为R1，R2，…，Rn，其对应关键字为K1，K2，…，K n，则起泡排序作法如下：

（1）

K1和K2，若逆序（K1>K2）,则交换之，然后比较K2和K3，……，直至Kn-1和Kn，这时最大关键字到了最后（第n个位置），这叫一趟起泡排序，进行了n-1次比较。

（2）

重复（1），但只比较到第n-1个元素（关键字），称第二趟比较。

（3）

共进行n-1趟比较，完成整个排序。

2、起泡排序实例模拟 3、起泡排序的算法 4、起泡排序算法的时间复杂度起泡排序的比较次数和记录的初始顺序有关。在正序时，比较次数为n-1，交换次数为0；

逆序时，比较次数和交换次数均为：

=（n-1）

移动次数为n(n-1)，存储开销为一个记录空间，供交换用。

10·3·2 快速排序约25min 1、快速排序的基本概念以第一个记录为“枢轴”，查询记录序列，确定“枢轴“的位置。枢轴将待排序文件分成两部分：枢轴左面的记录的关键字都不大于它的关键字，而枢轴右面的记录的关键字都不小于它的关键字。对枢轴的左右两部分继续实施这一过程，直至全部文件有序。

2、快速排序的实例模拟 3、快速排序的算法 4、快速排序的时间复杂度比较次数大约为nlog2n,交换次数大约为nlog2n/6，移动次数小于等于nlog2n。若待排序文件有序（无论正序逆序），快速排序退化成起泡排序=（n-1）≈n2/2。存储开销为栈的深度，不超过log2n。

5、快速排序对最差情况的改进为防止最差情况的出现，一般采取“三者取中”法来确定枢轴。即在第一个记录和最后一个记录，以及中间位置的记录中，选取值为中间的那个来作枢轴，这样就能防止最差情况的出现。

三、小结约5min 1、插入排序2、快速排序四、作业约5min 1、以关键码序列（503，087，061，908，170，897，275，653，426）为例，手工执行一下排序算法，写出每一趟排序结束时的关键码状态：

1）直接插入排序 2）希尔排序（增量d[1]=5）；

3）快速排序：

课时授课计划 2011-2012学年第一学期第14周授课日期 12月15日五星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题选择排序归并排序基数排序各种内部排序方法的比较讨论教学目的与要求：

2.掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。

3．理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。

教学重点：

1、选择排序2、归并排序 3、基数排序教学难点：

1、堆排序作业及参考书：

各种排序的应用《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业一、引入约3min 由前面两种排序引入后面的排序二、讲课进程设计 10.4 选择排序 10．4．1 直接选择排序约15min 1、直接选择排序的基本思想设待排序文件有n个记录，第一趟进行n-1次比较，选出关键字最小的记录，和第一个记录交换。第二趟进行n-2次比较，选出关键字次小记录，和第二个记录交换，……，如此下去，进行n-1趟，直至待排序文件全部有序。

2、直接选择排序的实例演示 3、直接选择排序的算法 4、直接选择排序算法的复杂度直接选择排序的比较次数和记录的初始顺序无关。其比较次数为：

=（n-1）

交换次数为不超过(n-1)次。当文件初始正序时，不发生交换；

当初始文件逆序时，发生（n-1）次交换，移动次数为3(n-1)。

10·4·2 树形选择排序约7min 1、树形选择排序的基本概念树形排序的步骤：

（1）

将n个待排序关键字两两比较，得到n/2个较小关键字，保留下来；

（2）

再把n/2个关键字两两比较，得到n/4个较小关键字，再保留之；

（3）

反复进行上述操作，直至得到最小关键字（树根）。

(4)将最小关键字输出，且将其原来位置改为极大数，与此位置相关部分重新（向树根方向）进行比较，选出次小关键字，保留结果。如此下去，直至全部排序完成。

该方法比直接选择排序速度上有很大提高，其缺点有：

（1）

需要另开储存空间保存排序结果；

（2）

n个待排序关键字，需要额外的（n-1）个内部结点（包括根结点），增加了内存开销。

（3）

将最小关键字改为极大数，再与兄弟结点比较属于多余。

2、树形选择排序的算法复杂度树形选择排序在第一次选最小值时比较n-1次，以后每选一个次小值要比较log2n次，故总的比较次数为(n-1)+(n-1)log2n=nlog2n。结点的移动次数不超过比较次数。故总的开销为O（nlog2n）。

10．4．3 堆排序约20min 1、堆的定义堆是一个含有n个关键字{k1,k2,…,kn}的序列，且具有如下特性：

ki<=k2i 且 ki<=k2i+1(1<=i<=n/2)(1)或 ki>=k2i 且 ki>=k2i+1(1<=i<=n/2)(2)ki>=k2i 满足式（1）的称为极小化堆，或极小堆，或小堆，满足式（2）的称为极大化堆，或极大堆，或大堆。本节以极小化堆为例子进行讲解。

堆与完全二叉树的关系：堆是n个元素（关键字）的序列，满足完全二叉树顺序存储中结点间的关系（双亲与子女序号间的关系）。

2、堆排序的基本问题既然堆顶元素（关键字）是最小元素，所以它是排序序列的最小元素，输出后，将其它元素再调整成堆，新的堆顶元素是排序序列的第二个元素。如此下去，通过堆，可将一个无序序列变为一个有序序列。因此，堆排序的基本问题是：如何建堆如何调堆 3、如何调堆将最后一个元素和堆顶元素交换（相当将堆顶元素输出）后，这时，从堆顶到倒数第二元素，除堆顶元素外，其余元素均符合堆的定义。下面采用筛选法，把包括堆顶元素在内的所有元素调成堆。

4、如何建堆具有n个结点的完全二叉树，其叶子结点被认为符合堆的定义，其最后一个非终端结点的编号是n/2，若从该结点开始，直到根结点，依次调用上面的筛选法，则可完成堆的建立。具体算法放在下面堆排序算法中。

5、堆排序算法 6、堆排序算法分析时间复杂度为O（nlogn），只需要一个记录大小供交换用的辅助存储空间。

10·5 归并排序约10min 1、归并排序的基本思想设待排序文件有n个记录，开始首先假定这n个记录都是有序的（这是自然的，一个记录当然自己有序）。然后进行归并，将相邻的有序子文件合并成一个较大子文件，如此下去，直至整个文件有序。对于二路归并来说，第一次长1的有序子文件两两归并得到长为2的éù个有序子文件，再两两归并得到长为4的éù个有序子文件，如此下去，直至得到长为n的有序文件。

2、二路归并排序的算法 3、二路归并排序的时间复杂度第i趟排序后，有序子文件长度为2i，具有n个记录的文件排序，必须做「log2nù趟归并，每趟所花时间为O（n），故二路归并排序的时间复杂度为O（nlog2n），所需空间为O（n）。

3·7 各种排序方法的比较 10·6 基数排序 10·6·1 多关键字的排序约8 min 1、分配排序的实例（1）

扑克牌的排序扑克牌有花色和面值（点数）。规定花色高于面值。在花色中规定梅花>方块>红心>黑桃；

在面值中2<3<4<…<10

方法1：先按花色分成4堆，每堆内按面值从小到大排序，最后按花色顺序收集起来。这种方法叫最高位（MSD）优先法。

方法2：先按面值分成13堆，将13堆从小到大排序，再按花色分成4堆，最后按花色顺序收集起来。这种方法叫最低位（LSD）优先法。

（2）

卡片的排序卡片按日期（年月日）建立，然后以建立日期为关键字进行排序。

方法1：先按年份分堆，同年的卡片按月份分堆，同月的卡片按日分堆，最后顺序收集这些卡片。这种方法叫最高位（MSD）优先法。

方法2：先按日分堆并收集，再按月份分堆并收集，最后按年分堆并收集。这种方法叫最低位（LSD）优先法。

2、分配排序的方法最高位（MSD）优先法是按最高位分成若干子集，子集再分成子集，在各子集中排序，最后收集；

最低位（LSD）优先法是从最低位开始到最高位结束，进行若干次分配和收集。

当关键字为一个字段时，亦可使用分配排序方法。如000---999。

10·6·2 链式基数排序约15min 将最低位优先法用于单关键字的情况。

1、基数排序的基本思想 n个记录的关键字进行排序，每个关键字看成是一个d元组：

ki=(ki1, ki2,..., kid)其中 c0<=kij <=cr-1(1<=i<=n, 1<=j<=d)排序时先按kid 的值，从小到大将记录分到r（称为基数）个盒子中，再依次收集；

然后按kid-1的值再这样作。直至按ki1分配和收集序列为止，排序结束。

在关键字为数字时，r=10, 0<=ci<=9，1<=i<=d；

在关键字为字母时 r=26, ’A’<=ci<=’Z’, 1<=i<=d。

2、基数排序的实例模拟 3、基数排序的算法 10.7 各种排序方法的综合比较约12min 1、时间性能平均的时间性能/ 当待排记录序列按关键字顺序有序时 /简单选择排序、堆排序和归并排序的时间性能不随记录序列中关键字的分布而改变。

2、空间性能指的是排序过程中所需的辅助空间大小 1)所有的简单排序方法(包括：直接插入、起泡和简单选择)和堆排序的空间复杂度为O(1)；

2).快速排序为O(logn)，为递归程序执行过程中，栈所需的辅助空间；

3).归并排序所需辅助空间最多，其空间复杂度为 O(n);4.)链式基数排序需附设队列首尾指针，则空间复杂度为 O(rd)。

3、排序方法的稳定性能 1).稳定的排序方法指的是，对于两个关键字相等的记录，它们在序列中的相对位置，在排序之前和经过排序之后，没有改变。

2).当对多关键字的记录序列进行LSD方法排序时，必须采用稳定的排序方法。

3).对于不稳定的排序方法，只要能举出一个实例说明即可。

4).快速排序、堆排序和希尔排序是不稳定的排序方法。

4、关于“排序方法的时间复杂度的下限” 三、小结约7min 1、对各种排序方法进行总结 2、本章讨论的各种排序方法，除基数排序外，其它方法都是基于“比较关键字”进行排序的排序方法。

四、作业约3min 10.1以关键码序列（503，087，061，908，170，897，275，653，426）为例，手工执行一下排序算法，写出每一趟排序结束时的关键码状态：

1）堆排序：

2）归并排序；

3）基数排序；

10.2将编写教科书10.2.2节中所述链表插入排序的算法。

10.3 2路归并排序的另一策略是，先对待排序序列扫描一遍，找出并划分为若干个最大有序子列，将这些子列作为初始归并段。试写出一算法在链表结构上实现这一策略。

课时授课计划 2011-2012学年第一学期第15周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题排序和查找算法辅导（上）

教学目的与要求：

进一步掌握各种排序和查找的方法教学重点：

掌握其方法教学难点：

选择不同的排序和查找方法作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：给出问题――学生思考――学生解答――对问题讲解一、讲课进程设计排序和查找算法辅导以下各题，先让学生做，看学生做的情况再讲解。

1.（约8min）设L为单链表的头结点地址，其数据结点的数据都是正整数且无相同的，试设计利用直接插入的原则把该链表整理成数据递增的有序单链表的算法。

2.（约8min）二路插人排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注:向量d可视为循环表），其原则为，先将r[l]赋给d[1]，再从r[2]记录开始分二路插入。编写实现二路插入转序算法 3.（约8min）有N个记录存储在带头结点的双向链表中，现用双向起泡排序法对其按上升序进行排序，请写出这种排序的算法。

（注：双向起泡排序即相临两趟排序方向相反起泡）

4、（约8min）设有一个数组中存放了一个无序的关键序列K1、K2、……..、Kn。现要求将Kn放在将元素排序后的正确位置上，试编写实现该功能的算法，要求比较关键字的次数不超过n。

5．（约8min）设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红,白,蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后，重新安排时对每粒砾石的颜色只能看一次，并且只允许交换操作来调整砾石的位置 6．（约12min）设文件（R1，R2，……，Rn）是一个堆，Rn+1是任意一个结点，试设计一个算法，该算法把Rn+1添加到堆中，并使添加后形成的文件仍是一个堆，要求算法的时间复杂性为O(log2n)。

课时授课计划 2011-2012学年第一学期第15周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题排序和查找算法辅导（下）

教学目的与要求：

进一步掌握各种排序和查找的方法教学重点：

掌握其方法教学难点：

选择不同的排序和查找方法作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：给出问题――学生思考――学生解答――对问题讲解一、讲课进程设计 7．（约10min）数据结构DEAP的定义如下：DEAP是一棵完全二叉树，它或者是一棵空树，或者满足下列特性：（1）树根不包含元素．（2）其左子树是一小堆（MINHEAP），其右子树是一大堆（MAXHEAP）．（3）若右子树非空，设ｉ是左子树的任一结点，ｊ是右子树中与ｉ相应的结点．若这样的ｊ结点不存在，则取ｊ为右子树中与ｉ的父结点相应的结点；

结点ｉ的关键字总是小于或等于结点ｊ的关键字值．一个DEAP的例子如右图所示，与结点１５相对应的结点为２０，与结点１９对应的结点为２５．（1）

给出在该DEAP中插入结点４后的结果．（2）

写出在DEAP中插入新结点的算法．（3）

用C或PASCAL语言编写实现上述算法得程序． 8.(约6min)给出折半查找的递归算法，并给出算法时间复杂度性分析 9、(约7min)设记录R1,R2,…,Rn按关键字值从小到大顺序存贮在数组r[1..n]中,在r[n+1]出设立一个监督哨,其关键字值为+∞;试写一查找给定关键字k 的算法;并画出此查找过程的判定树,求出在等概率情况下查找成功时的平均查找长度.10、(约7min)二叉排序树采用二叉链表存储。写一个算法，删除节点值是X的结点。要求删除该结点后此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。

11、(约10min)在二叉排序树的结构中，有些数据元素值可能是相同的，设计一个算法实现按递增有序打印结点的数据域，要求相同的数据元素仅输出一个，算法还应能报出最后被滤掉，而未输出的数据元素个数，对如图所示的二叉排序树，输出为：10，12，13，15，18，21，27，35，42．滤掉3个元素。

12．(约10min)知输入关键字序列为（１００，９０，１２０，６０，７８，３５，４２，３１，１５）址区向为０~１１。设计一个哈希表函数把上述关键字散到０~１１中，画出散列表（冲突用线性探测法）；

写出查找算法，计算在等概率情况下查找长度。课时授课计划 2011-2012学年第一学期第16周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题复习1～5章教学目的与要求：

1、对数据结构中的基本概念做更深的理解 2、掌握线性表的用法 3、栈和队列的作用 4、串的应用 5、数组的应用教学重点：

各章的知识点教学难点：

作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：给出内容提要、学习重点、例题解析讲课进程设计第一章绪论约10min 一、内容提要 1 数据结构研究的内容。2 基本概念：数据、数据元素、数据对象、数据结构、数据类型、抽象数据类型、多形数据类型。3 算法的定义及五个特征。4 算法描述：类PASCAL语言。5 算法设计要求。6 算法分析。二、学习重点 1 数据结构的“三要素”：逻辑结构、物理（存储）结构及在这种结构上所定义的操作（运算）

。2 抽象数据类型的定义、表示和实现方法。3 类PASCAL书写规范，过程（函数）中值参和变参的差别，过程调用规则。4 用计算语句频度来估算算法的时间复杂度。三、例题解析 1 写出以下各语句执行次数（左边括号内数字为语句序号）第二章线性表约25min 一、内容提要 1．线性表是元素间约束力最强的一类数据结构。

2．线性表的逻辑结构定义，对线性表定义的操作。3．线性表的存储结构：顺序存储结构和链式存储结构。4．线性表的操作在两种存储结构中的实现。5．一元多项式的线性表表示方法，及高次（稀疏）多项式的抽象数据类型定义、表示和加法的实现。二、学习重点 1．线性表的逻辑结构，指线性表的数据元素间存在着线性关系。在顺序存储结构中，元素存储的先后位置反映出这种线性关系，而在链式存储结构中，是靠指针来反映这种关系的。2．顺序存储结构用向量（一维数组）表示，给定下标，可以存取相应元素，属于随机存取的存储结构。3．尽管“只要知道某结点的指针就可以存取该元素”，但因链表的存取都需要从头指针开始，顺链而行，故链表不属于随机存取结构。4．链表是本章学习的重点和难点。要理解头结点，首元结点和元素结点的差别。理解头结点是为了在插入、删除等操作时，为了算法的统一而设立的（若无头结点，则在第一元素前插入元素或删除第一元素时，链表的头指针总在变化）。掌握通过画出结点图来进行链表的生成、插入、删除、遍历等操作。5．链表操作中应注意不要使链意外“断开”。因此，若在某结点前插入一个元素，或删除某元素，必须知道该元素的前驱结点的指针。6．从时间和空间复杂度的角度综合比较线性表在顺序和链式两种存储结构下的特点。7．静态链表是又一重点和难点。应和链表进行比较、理解。三、例题解析１．设线性表以顺序存储结构存于a(1..n)中，试编写算法将该线性表就地逆置。

２．编写在单链表上进行排序的算法 3．设两个非递减有序的线性表各有m和n个元素（m>0,n>0）,分别存于一维数组a和b中，且a 的存储空间足够大。试编写算法将两线性表合并成一线性表，结果仍是非递减有序，要求算法的时间复杂度是o(m+n)。

第三章栈和队列约30min 一、内容提要 1．从数据结构角度讲，栈和队列也是线性表，其操作是线性表操作的子集，属操作受限的线性表。但从数据类型的角度看，它们是和线性表大不相同的重要抽象数据类型。2．栈的定义及操作。栈是只准在一端进行插入和删除操作的线性表，该端称为栈的顶端。3．栈的顺序和链式存储结构，及在这两种结构下实现栈的操作。4．栈的应用：表达式求值，递归过程及消除递归。5．队列的定义及操作，队列的删除在一端（尾），而插入则在队列的另一端（头）。因此在两种存储结构中，都需要队头和队尾两个指针。6．链队列空的条件是首尾指针相等，而循环队列满的条件的判定，则有队尾加1等于队头和设标记两种方法。二、学习重点 1．栈和队列操作在两种存储结构下的实现。2．中缀表达式转成前缀、后缀表达式并求值。3．用递归解决的问题：定义是递归的，数据结构是递归的，及问题的解法是递归的，掌握典型问题的算法。

4．链队列删除时为空的处理（令队尾指针指向队头）。特别是仅设尾指针的循环链队列的各种操作的实现。5．循环队列队空定义为队头指针等于队尾指针，队满则可用一个单元（教材中所示）

及设标记办法（下面例题）。这里特别注意取模运算。6．在后续章节中要注意栈和队列的应用，如串中心对称的判定，二叉树遍历的递归和非递归算法，图的深度优先遍历等都用到栈，而树的层次遍历、图的宽度优先遍历等则用到队列。

三、例题解析 1．两栈共享一向量空间，编写入栈和出栈算法。

2．将中缀表达式转换成后缀表达式，并进行表达式求值。

3、用设标记来判定循环队列满，编写入队和出队的算法。

第四章串约10min 一、内容提要 1、是数据元素为字符的线性表，串的定义及操作。2、的基本操作，编制算法求串的其它操作。3、的存储结构，因串是数据元素为字符的线性表，所以存在“结点大小“的问题。静态和动态（块链结构，堆结构）存储的优缺点。

4、朴素模式匹配算法及改进（KMP）算法。二、学习重点 1、串的基本操作，编写串的其他操作（如index,replace等）。2、在串的模式匹配中，求匹配串的nextval 函数值。3、尽管朴素的模式匹配的时间复杂度是O(m*n), KMP算法是O(m+n),但在一般情况下，前者实际执行时间近似O(m+n),因此至今仍被采用。4、KMP算法仅在主串与模式串存在许多“部分匹配”时才显得比前者块的多，其主要优点是主串不回嗍。5、串操作在存储结构下的实现。

三、例题解析 1、利用串的如下基本运算create(s),assign(s,t),length(s),substr(s,start,len),concat(s1,s2),编写操作replace的算法 2 设目标为 t=’abcaabbabcabaacbacba’,模式串 p=’abcabaa’;(1)计算P的NEXTVAL函数值；

(2)不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程；

第五章数组和广义表约25min 一、内容提要 1，数组的逻辑结构定义及存储，2，稀疏矩阵（含特殊矩阵）的存储及运算。3，广义表的定以及存储。4，广义表运算的递归算法。

二、学习重点 1，数组（主要是二维）在以行序为主的存储中的地址计算方法。2，特殊矩阵在压缩存储时的下标变换。3，稀疏矩阵的三元组表存储结构及矩阵移植的算法。4，稀疏矩阵的十字链表存储方法及十字链表生成算法。5，广义表的HEAD和TAIL 运算。6，给定广义表画出其存储结构。7，从广义表的递归算法，掌握如何编写递归算法。

三、例题解析 1、字符串二维数组A[0..8,1..10]，每个元素由6个字符组成，每个字符占一个存储单元，则（1）存放A需要多少个字节？（2）A的第8列和第5行共占多少字节？(3)按行序存储时，A[8,5]和按列存储时哪个元素时的地址相同？ 2求下列广义表操作结果：(1)HEAD(TAIL(HEAD(((a,b),(c,d))))(2)TAIL(HEAD(TAIL(((a,b),(c,d))))【解答】（1）b(2)(d)3.广义表的HEAD和TAIL操作，写出如上题的表达式，把原子banana从下列广义表中分离出来。

（1）（apple,(pear),((banana)),(((orange)))）;（2）

L2=(apple,(pear,(banana),orange));课时授课计划 2011-2012学年第一学期第16周授课日期月日星期月日星期月日星期月日星期月日星期班级信管10-1 基本课题复习6～10章教学目的与要求：

1、树的基本知识 2、图的基本知识 3、查找的应用 4、排序的选择教学重点：

各章的重点教学难点：

作业及参考书：

《数据结构算法实现及解析》/高一凡编著教具：

多媒体板书课堂类型：

讲授教学过程：引入——展开——举例——小结——作业讲课进程设计第六章树和二叉树约25min 一、内容提要 1、树是复杂的非线性数据结构，树，二叉树的递归定义，基本概念，术语。2、二叉树的性质，存储结构。3、二叉树的遍历算法（递归，非递归）。4、线索二叉树5、树的存储结构，树、森林的遍历及和二叉树的相互转换。6、二叉树的应用：表达式求值、判定问题及哈夫曼树和哈夫曼编码。二、学习重点（本章内容是本课程的重点）

1、二叉树性质及证明方法，并能把这种方法推广到K叉树。2、二叉树遍历的递归算法，本书中介绍了三种（先、中、后序）方法，另三种也应会用。前序和中序的非递归遍历。遍历是基础，由此导出许多实用的算法，如求二叉树的高度、各结点的层次数、度为0、1、2的结点数，二叉树的相似、全等、复制等等的算法。3、由二叉树的遍历的前序和中序序列或后序和中序序列可以唯一构造一棵二叉树，手工模拟及编写算法。由前序和后序序列不能唯一确定一棵二叉树。4、二叉树线索化的实质是建立结点在相应序列中的前驱和后继之间的直接联系。在何序（前、中、后）下进行何种（全、前驱、后继）线索化，并求某结点相应的前驱和后继。5、完全二叉树的性质，顺序存储结构和二叉树链表存储结构的相互转换。6、树的双亲表示法和孩子兄弟表示法间的相互转换。7、树、森林和二叉树间的相互转换（“连线”、“切线”和“旋转”）。8、哈夫曼树的定义、构造及求哈夫曼编码。三、例题及分析 1.在二叉树中查找其数据域为 x的结点。如存在，返回该结点指针，否则返回空指针。

２．设二叉树采用二叉链表作为存储结构，试编写算法求二叉树的结点数。

３．打印二叉树中结点x（假定存在）的所有祖先结点。

第七章图约25min 一、内容提要 1．图的定义，概念、术语及基本操作。

2．图的存储结构。3．图的遍历。4．图的应用（连通分量，最小生成树，拓扑排序，关键路经，最短路经）。二、学习重点图是应用最广泛的一种数据结构，本章是这门课程的重点。

1 基本概念中，连通分量，生成树，邻接点是重点。2 图是复杂的数据结构，也有顺序和链式两种存储结构：数组表示法（重点是邻接距阵）和邻接表。这两种存储结构对有向图和无向图均适用。十字链表是有向图的另一种表示，将有向图的邻接表和逆邻接表合一。邻接多重表是无向图邻接表的改进，将边结点的数量减少一半（正好等于边的数量）。3 图的遍历是图的各种算法的基础，应熟练掌握图的深度、广度优先遍历，手工模拟图的遍历中栈和队列指针状态的变化。4 在（强）连通图中，主过程一次调用深（宽）度优先遍历过程（dfs/bfs），即可遍历完全部顶点，故可以用此方法求出连通分量的个数，并能画出遍历中形成的深（宽）度优先生成树。5连通图的最小生成树不是唯一的，但最小生成树边上的权值之和是唯一的。

应熟练掌握prim和kruscal算法，特别是手工分步模拟生成树的生成过程。6 拓扑排序是在有向图上对入度（先后）为零的顶点的一种排序，结果不唯一。关键路经是在拓扑有序的前提下求出来的，从源点到汇点的最长路径。应能掌握这两种算法，并熟练手工模拟。理解“减少关键活动时间能缩短工期”，是指该活动为所有关键路径所共有，且减少到尚未改变关键路经的前提下才有效。7 从单源点到其他顶点，以及各个顶点间的最短路经问题，掌握算法，并熟练手工模拟。三、例题解析 1、用邻接多重表实现图的各种运算。

2、编写对图的深度优先非递归遍历算法。

第九章查找约25min 一、内容提要 1、本章介绍的查找表是称为集合的数据结构。是元素间约束力最差的数据结构：元素间的关系是元素仅共在同一个集合中。

2、查找表的操作：查找，检索，插入，删除，成员关系判断。

3、静态查找表：顺序表，有序表，静态树表，索引顺序表。

4、动态查找表：二叉排序树，平衡二叉树，B-树，B+树，键树。

5、哈希表。

二、学习重点 1、查找表是称为集合的数据结构。因元素间关系非常松散，其操作需借助其它数据结构来实现。本章列举了三种方法（静态查找表，动态查找表，哈希表）实现查找表的运算。2、顺序表因引设置了监视哨使查找效率大大提高。有序表的平均查找长度不超过树的深度，其判定树是唯一的。索引顺序查找综合了上述二者的优点，既能较快速的查找，又能适应动态变化的要求。3、二叉排序树的形态取决于元素的输入顺序。按中序遍历可得到结点的有序序列，应熟练掌握其建立、查找，插入和删除算法。4、最佳二叉排序树是平均查找长度最短的二叉排序树，平衡二叉树是介于最佳和一般间的折中，应熟练掌握手工绘制平衡二叉树。5、键树中每个结点是关键字的一个字符，该树是有序树（同层兄弟间从左到右递增，最小是结束符号$）。6、哈希表是查找表（集合）的又一表示方法，根据选定的哈希函数和处理冲突的方法，将关键字映像到哈希表中。冲突是不可避免的。7、哈希表中关键字的查找只能用哈希函数来计算，不能顺序、折半查找。元素删除也只能作标记，不能物理的删除。三、例题解析 1．设二叉排序树中元素均为整数，试编写算法从大到小输出各元素值。

2．编写在二叉排序树上插入结点s的算法。

3．编写在索引顺序表中查找数据k的算法。

4．已知一个含有100个记录的表，关键字是中国人名的拼音。请给出此表的一个哈希表设计方案。要求在等概率情况下查找成功的平均查找长度不超过3。

第十章内部排序约25min 一、内容提要 1、排序的定义，排序可以看作是线性表的一种操作2、排序的分类，稳定排序与不稳定排序的定义。3、插入排序（对分插入、二路插入、表插入、希尔插入排序）。4、交换排序（冒泡排序、快速排序）。5、选择排序（简单选择排序、树形选择排序、堆排序）。6、归并排序、基数排序。二、学习要点 1．各种排序所基于的基本思想。2．在“最好”和“最差”情况下，排序性能的分析，是否是稳定排序的结论。3．插入排序基于假定待排序文件第一个记录有序，然后从第二个记录起，依次插入到已排好序的有序子文件中，直到整个文件有序。从减少比较次数和移动次数进行了各种改进，产生了折半、二路、表插入、希尔等一系列插入排序。4．交换排序基于相邻记录比较，若逆序则进行交换。冒泡排序和快速排序是交换排序的例子，快速排序是目前最快的内部排序法。应采用“三者取中”法防止其性能退化。5．简单选择排序、树形选择排序、堆排序是选择排序的例子。堆排序较为重要，其最差性能比快速排序的最差性能好（Ologn）6．归并排序、基数排序及时间复杂度O(n2)的排序为稳定排序，而希尔排序、快速排序、堆排序等时间性能好的排序方法，包括简单选择排序，是不稳定排序。7．对每种排序方法的学习，应掌握其本质（排序所基于的思想），并能举一反三。二、例题解析 1．设待排序文件有n(n>0)个记录，试编写算法，不经全部排序，将第j(0

2．已知（k1,k2,┄,kp）是堆，试编写算法将（k1,k2,┄,k[p],k[p+1]）调整为堆。算法复杂度为O(logn).3.编写归并排序的非递归排序算法。

数据结构课程设计运动会分数统计（C语言版）