文档内容
淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
第一章：绪论
课程：数据结构
课题：第一章 1.1—1.4小节（共4个课时）
1.1 什么是数据结构
1.2 基本概念和术语
1.3 抽象数据类型的表现与实现
1.4 算法和算法分析
目的要求：理解数据、数据元素、数据项的概念；掌握逻辑结构和存储结构的关系；理解算法的基本概念；学
会分析算法的时间复杂性和空间复杂性。
新课重点、难点：数据、数据元素、数据项、时间复杂性和空间复杂性
教学方法：课堂讲解、例题演示，课件演示
教学内容及过程：
……………………………第1-2课时……………………………
计算机的应用不再局限于科学计算，更多地用于控制，管理，数据处理等非数值计算的处理工作。计算机
加工处理的对象：数值，字符，表格，图形声音，图象等具有一定结构的数据。进行程序设计时必须分析待处
理的对象的特性及各对象之间存在的关系———产生背景。
1.1 什么是数据结构
计算机解题步骤：建立数学模型——设计解此数学模型的算法——编制程序——进行测试调整——解答。
其中建立数学模型的实质：找出操作对象之间的关系。
例1. 图书馆书目检索 ——对应线性关系
例2. 博奕树 ——对应树型关系
例3. 交叉路口交通灯管理 ——对应图状结构。
数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象及它们之间的关系和操作等的学科。
（地位）
1.2 数据结构的基本概念和术语
1. 数据（Data）
数据是描述客观事物的数值、字符以及能输入机器且能被处理的各种符号集合。换句话说，数据是对客观
事物采用计算机能够识别、存储和处理的形式所进行的描述；是计算机加工处理的对象。包括数值、字符、声
音、图象等。
2. 数据元素（Data Element）
数据元素是组成数据的基本单位, 是数据集合的个体，在计算机中通常作为一个逻辑整体进行考虑和处理。
一个数据元素可由若干个数据项组成（Data Item）。
3. 数据对象（Data Object）
数据对象是性质相同的数据元素的集合，是数据的一个子集。例如：整数数据对象是集合N={0， ±1， ±
2， …}，字母字符数据对象是集合C={′A′，′B′，…，′Z′}，表1-1所示的学籍表也可看作一个数据对
象。由此可看出，不论数据元素集合是无限集（如整数集）、有限集（如字符集），还是由多个数据项组成的复
合数据元素（如学籍表），只要性质相同， 都是同一个数据对象。
综上1~3所述，再分析数据概念：
1淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
4. 结构（Data Structure）
数据元素相互之间的关系称为结构（ Structure ），有四种基本结构。
(1) 集合结构：结构中的数据元素之间除了同属于一个集合的关系外，无任何其它关系。
(2) 线性结构：结构中的数据元素之间存在着一对一的线性关系。
(3) 树形结构：结构中的数据元素之间存在着一对多的层次关系。
(4) 图状结构或网状结构：结构中的数据元素之间存在着多对多的任意关系。
线性结构——线性表、栈、队、字符串、数组、广义表
非线性结构——树、 图
数据结构的形式定义：
数据结构是一个二元组 Data_structure=(D,S) 。其中：D为数据结构的有限集，S是D上关系的有限集。
例：复数结构Complex=(C,R)
其中：C为含两个实数的集合{c1,c2}；
R={P}， P是集合C上的一种关系，
P={}，为有序偶，c1表示复数的实部，c2表示复数的虚部。
存储结构
存储结构（又称物理结构）是逻辑结构在计算机中的存储映象，是逻辑结构在计算机中的实现，它包括数
据元素的表示和关系的表示。
形式化描述：D要存入机器中，建立一从D的数据元素到存储空间M单元的映象S，D→M， 即对于每一个
d，d∈D, 都有唯一的m∈M，使S（D）=m, 同时这个映象必须明显或隐含地体现关系R。
逻辑结构与存储结构的关系为：存储结构是逻辑关系的映象与元素本身的映象。逻辑结构是数据结构的抽
象，存储结构是数据结构的实现，两者综合起来建立了数据元素之间的结构关系。
顺序映象 （顺序存储结构）顺序结构用元素在存储器中的相对位置表示数据
元素之间的逻辑关系。
非顺序映象（非顺序存储结构）非顺序映像借助指示元素存储地址的指针表示元
素之间的逻辑关系。
一维数组来描述顺序存储结构，用指针来描述链式存储结构。
运算的集合
数据结构的内容可归纳为三个部分：逻辑结构、存储结构和运算集合。按某种逻辑关系组织起来的一批数
据，按一定的映象方式把它存放在计算机的存储器中，并在这些数据上定义了一个运算的集合， 就叫做数据
2淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
结构。
数据类型(Data Type)
数据类型是一组性质相同的值集合以及定义在这个值集合上的一组操作的总称。数据类型中定义了两个集
合，即该类型的取值范围，以及该类型中可允许使用的一组运算。例如高级语言中的数据类型就是已经实现的
数据结构的实例。 从这个意义上讲，数据类型是高级语言中允许的变量种类， 是程序语言中已经实现的数据
结构（即程序中允许出现的数据形式）。在高级语言中，整型类型可能的取值范围是-32768~+32767， 可用的
运算符集合为加、 减、 乘、 除、 取模（如C语言中+， -， *， /， %）。
抽象数据类型
１） 数据的抽象
计算机中使用的是二进制数，汇编语言中则可给出各种数据的十进制表示，如98.65、 9.6E3等, 它们是
二进制数据的抽象; 使用者在编程时可以直接使用, 不必考虑实现细节。在高级语言中，则给出更高一级的数
据抽象，出现了数据类型， 如整型、 实型、字符型等。到抽象数据类型出现，可以进一步定义更高级的数据
抽象，如各种表、队、栈、树、图、窗口、管理器等，这种数据抽象的层次为设计者提供了更有利的手段，使
得设计者可以从抽象的概念出发，从整体考虑，然后自顶向下、逐步展开，最后得到所需结果。可以这样看，
高级语言中提供整型、实型、字符、记录、文件、指针等多种数据类型，可以利用这些类型构造出像栈、队列、
树、图等复杂的抽象数据类型。
２） 抽象数据类型 (Abstract Data Type)
抽象数据类型（简称ADT）是指基于一类逻辑关系的数据类型以及定义在这个类型之上的一组操作。抽象
数据类型的定义取决于客观存在的一组逻辑特性，而与其在计算机内如何表示和实现无关，即不论其内部结构
如何变化，只要它的数学特性不变，都不影响其外部使用。从某种意义上讲，抽象数据类型和数据类型实质上
是一个概念。整数类型就是一个简单的抽象数据类型实例。“抽象”的意义在于教学特性的抽象。一个ADT定
义了一个数据对象，数据对象中各元素间的结构关系，以及一组处理数据的操作。ADT 通常是指由用户定义且
用以表示应用问题的数据模型，通常由基本的数据类型组成，并包括一组相关服务操作。
抽象数据类型是近年来计算机科学中提出的最重要的概念之一，它集中体现了程序设计中一些最基本的原则：
分解、抽象和信息隐藏。
一个抽象数据类型确定了一个模型，但将模型的实现细节隐藏起来；它定义了一组运算，但将运算的实现
过程隐藏起来。
数学模型→抽象数据类型→数据结构，恰好反应了信息结构转换的三个重要阶段，而在这个转换过程中，数据
结构是基础，抽象数据类型是中枢。
一个线性表的抽象数据类型的描述如下：
ADT Linear -list
数据元素 所有ai属于同一数据对象，i=1，2，…，n, n≥0；
逻辑结构 所有数据元素ai（i=1，2，…，n-1）存在次序关系，ai无前趋，an无后继；
操作 设L为Linear-list:
Initial(L): 初始化空线性表;
Length(L): 求线性表的表长;
Get(L, i): 取线性表的第i个元素；
Insert(L, i, b): 在线性表的第i个位置插入元素b；
Delete(L, i): 删除线性表的第i个元素。
３） 抽象数据类型实现
第一种情况： 传统的面向过程的程序设计。
第二种情况： “包”、 “模型”的设计方法。
第三种情况： 面向对象的程序设计（Object Oriented Programming，简称OOP）。
４） ADT的定义
ADT的定义格式不唯一, 我们采用下述格式定义一个ADT:
3淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
ADT 抽象数据类型名{
数据对象: <数据对象的定义>
数据关系: <结构关系的定义>
基本操作: <基本操作的定义>
}ADT 抽象数据类型名
其中数据对象和结构关系的定义采用数学符号和自然语言描述, 而基本操作的定义格式为:
操作名称 (参数表)
初始条件: <初始条件描述>
操作结果: <操作结果描述>
关于参数传递
参数表中的参数有两种：第一种参数只为操作提供待处理数据, 又称值参；第二种参数既能为操作提供待
处理数据, 又能返回操作结果，也称变量参数。操作前提描述了操作执行之前数据结构和参数应满足的条件, 操
作结果描述操作执行之后, 数据结构的变化状况和应返回结果。ADT可用现有计算机语言中已有的数据类型,
即固有数据类型来表示和实现。不同语言的表示和实现方法不尽相同，如ADT中“返回结果的参数”， PASCAL
语言用“变参” 实现, C++语言通过“引用型参数”实现, 而C语言用“指针参数”实现。
用标准C语言表示和实现ADT描述时，主要包括以下两个方面:
(1) 通过结构体将int、 float等固有类型组合到一起, 构成一个结构类型, 再用typedef为该类型或该
类型指针重新起一个名字。
(2) 用C语言函数实现各操作。
基本操作主要有以下几种：
(1) 插入： 在数据结构中的指定位置上增添新的数据元素；
(2) 删除： 删去数据结构中某个指定数据元素；
(3) 更新：改变数据结构中某个元素的值， 在概念上等价于删除和插入操作的组合；
(4) 查找：在数据结构中寻找满足某个特定要求的数据元素（的位置和值)；
(5) 排序：（在线性结构中）重新安排数据元素之间的逻辑顺序关系，使数据元素按值由小到大或由大到小
的次序排列。
结构化的开发方法与面向对象的开发方法的不同点，结构化的开发方法是面向过程的开发方法，首先着眼
于系统要实现的功能。从系统的输入和输出出发， 分析系统要实现的功能，用自顶向下、逐步细化的方式建立
系统的功能结构和相应的程序模块结构。一旦程序功能需要修改， 就会涉及多个模块，修改量大，易于出错，
并会引起程序的退化。
作业1：
1：理解和掌握几个重要的基本概念：数据结构；抽象数据类型等；
2：理解和运用四种逻辑结构；并进行合理的划分。
……………………………第3-4课时……………………………
1．3 抽象数据类型的表示和实现
(1) 预定义常量和类型。
本书中用到以下常量符号，如True、False、MAXSIZE等，约定用如下宏定义预先定义： ＃ define
TRUE 1
＃ define FALSE 0
＃ define MAXSIZE 100
＃ define OK 1
＃ define ERROR 0
(2) 本书中所有的算法都以如下的函数形式加以表示， 其中的结构类型使用前面已有的定义。
4淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
［数据类型］ 函数名（［形式参数及说明］）
{ 内部数据说明；
执行语句组；
} /*函数名*/
函数的定义主要由函数名和函数体组成，函数体用花括号“{”和“}”括起来。函数中用方括号括起来的
部分如“［形式参数］”为可选项， 函数名之后的圆括号不可省略。
(3) 赋值语句。
1、简单赋值;
（1）〈变量名〉=〈表达式〉，它表示将表达式的值赋给左边的变量；
（2）〈变量〉++， 它表示变量加1后赋值给变量；
（3）〈变量〉--， 它表示变量减1后赋值给变量。
2、串联赋值#;
〈变量1〉=〈变量2〉=〈变量3〉=…=〈变量k〉=〈表达式〉；
3、成组赋值#;
（〈变量1〉，〈变量2〉，〈变量3〉， …, 〈变量k〉)=（〈表达式1〉，〈表达式2〉，〈表达式3〉， …, 〈表
达式k〉）；
〈数组名1〉［下标1］［下标2］=〈数组名2〉［下标1］［下标2］；
4、条件赋值;
〈变量名〉=〈条件表达式〉？〈表达式1〉: 〈表达式2〉；
(4) 条件选择语句。
if （〈表达式〉） 语句；
if （〈表达式〉） 语句1；
else 语句2；
(5) 循环语句。
1、for 语句
for (<表达式1>； <表达式2>； <表达式3>）
{循环体语句； }
首先计算表达式1的值， 然后求表达式2的值，若结果非零（即为真）则执行循环体语句，最后对表达式
3运算，如此循环， 直到表达式2的值为零（即不成立为假）时为止。
2、while 语句
while (<条件表达式>）
{循环体语句；}
while循环首先计算条件表达式的值，若条件表达式的值非零（即条件成立），则执行循环体语句，然后再
次计算条件表达式的值， 重复执行，直到条件表达式的值为零（即为假）时退出循环， 执行该循环之后的语
句。
3、do-while 语句
do { 循环体语句
}while (<条件表达式>）
该循环语句首先执行循环体语句, 然后计算条件表达式的值， 若条件表达式成立，则再次执行循环体，再计
算条件表达式的值，直到条件表达式的值为零，即条件不成立时结束循环。 (6) 输入、 输出语句。
输入语句： 用函数scanf实现； 特别当数据为单个字符时， 用getchar函数实现；当数据为字符串时，
用gets函数实现。
输出语句：用printf函数实现；当要输出单个字符时，用putchar函数实现；当数据为字符串时，用puts
函数实现。
其中输入输出函数中的类型部分不做严格要求， 淡化表述。
5淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
(7) 其它一些语句。
① return <表达式>或return： 用于函数结束。
② break语句： 可用在循环语句或case语句中结束循环过程或跳出情况语句。
③ continue语句： 可用在循环语句中结束本次循环过程， 进入下一次循环过程。 ④ exit
语句： 表示出现异常情况时， 控制退出函数。
(8) 注释形式。
/*字符串*/ 、//
注释句的作用是增强算法的可阅读性，在算法描述中要求在函数首部加上对算法功能的必要注释描述。加
注释说明时如果没有涉及到的参量一定是多余的，而涉及到的内容应当作为参量，这实际上是程序设计中的一
个素质要求， 希望多加注意。
(9) 一些基本的函数， 例如：
max函数： 用于求一个或几个表达式中的最大值；min函数： 用于求一个或几个表达式中的最小值；abs
函数： 用于求表达式的绝对值；eof函数： 用于判定文件是否结束； eoln函数： 用于判断文本行是否结束。
ADT举例：
对于一个复数 z=x+yi
ADT complex{
数据对象 D={c1,c2|c1,c2R}
数据关系 R1＝{}
基本操作:
add(z1,z2,sum)；
subTracf(z1,z2,difference)；
Get_re (z) ；
Get_im(z)；
}ADT complex；
1.4 算 法
1. 算法（Algorithm）的定义
Algorithm is a finite set of rules which gives a sequence of operation for solving a specific
type of problem. (算法是规则的有限集合， 是为解决特定问题而规定的一系列操作。) 是指令的有限序列，
其中每一条指令表示一个或多个操作。
2. 算法的特性
(1) 有穷性：有限步骤之内正常结束， 不能形成无穷循环。
(2) 确定性：算法中的每一个步骤必须有确定含义， 无二义性。
(3)可行性：原则上能精确进行， 操作可通过已实现的基本运算执行有限次而完成。
(4)输入：有多个或0个输入。
(5)输出： 至少有一个或多个输出。
在算法的五大特性中， 最基本的是有限性、 确定性和可行性。
3. 算法设计的要求
１） 算法的正确性
(1) 所设计的程序没有语法错误；
(2) 所设计的程序对于几组输入数据能够得出满足要求的结果；
(3) 所设计的程序对于精心选择的典型、 苛刻而带有刁难性的几组输入数据能够得到满足要求的结果。
(4) 程序对于一切合法的输入数据都能产生满足要求的结果。
例如： 要求n个数的最大值问题， 给出示意算法如下：
max=0;
6淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
for（i=1； i<=n; i++）
{ scanf(″%f″, x); if (x>max) max=x; }
2） 可读性
3） 健壮性
4） 高效率和低存储量
算法、 语言和程序的关系
(1) 算法： 描述了数据对象的元素之间的关系（包括数据逻辑关系、 存储关系描述）。
(2) 描述算法的工具：算法可用自然语言、框图或高级程序设计语言进行描述。 自然语言简单但易于产生
二义，框图直观但不擅长表达数据的组织结构， 而高级程序语言则较为准确但又比较严谨。
(3) 程序是算法在计算机中的实现（与所用计算机及所用语言有关）。
设计实现算法过程的步骤
找出与求解有关的数据元素之间的关系（建立结构关系）。
确定在某一数据对象上所施加的运算。
考虑数据元素的存储表示。
选择描述算法的语言。
设计实现求解的算法， 并用程序语言加以描述。
对算法作性能评价
1. 性能评价
对问题规模和该算法在运行时所占的空间S与所耗费的时间T给出一个数量关系的评价。问题规模N对不
同的问题其含义不同，对矩阵是阶数， 对多项式运算是多项式项数，对图是顶点个数，对集合运算是集合中的
元素个数。
2. 有关数量关系的计算
数量关系评价体现在时间——算法编程后在机器中所耗费的时间。
数量关系评价体现在空间——算法编程后在机器中所占的存储量。
1） 关于算法执行时间
一个算法的执行时间大致上等于其所有语句执行时间的总和， 对于语句的执行时间是指该条语句的执行次
数和执行一次所需时间的乘积。
2） 语句频度
语句频度是指该语句在一个算法中重复执行的次数。 例1-1 两个n×n阶矩阵相乘。
3） 算法的时间复杂度
原操作是指从算法中选取一种对所研究问题是基本运算的操作，用随着问题规模增加的函数来表征, 以此
作为时间量度。
而对于算法分析，我们关心的是算法中语句总的执行次数T(n)是关于问题规模n的函数，进而分析T(n)
随n的变化情况并确定T(n)的数量级（Order of Magnitude）。在这里， 我们用“O”来表示数量级，这样我
们可以给出算法的时间复杂度概念。 所谓算法的时间复杂度， 即是算法的时间量度，记作：
T(n)=O(f(n))
它表示随问题规模n的增大，算法的执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，
简称时间复杂度。
7淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
一般情况下， 随n的增大，T(n)的增长较慢的算法为最优的算法。 例如： 在下列三段程序段中，给出原
操作x=x+1的时间复杂度分析。
（1） x=x+1 ； 其时间复杂度为O(1)， 我们称之为常量阶；
（2） for (i=1; i<= n; i++) x=x+1; 其时间复杂度为O(n)， 我们称之为线性阶；
（3） for (i=1; i<= n; i++)
for (j=1; j<= n; j++) x=x+1;
其时间复杂度为O(n 2), 我们称之为平方阶。此外算法还能呈现的时间复杂度有对数阶O(log2n), 指
数阶O(2n)等。
4） 数据结构中常用的时间复杂度频率计数
数据结构中常用的时间复杂度频率计数有7个：
O(1) 常数型 O(n)线性型 O(n2)平方型 O(n3)立方型
O(2n)指数型 O(log2n)对数型 O(nlog2n)二维型
按时间复杂度由小到大递增排列成表1-3（当n充分大时）。
不同数量级的时间复杂度的形状如图1.6所示， 表1-3与图1.6是同一问题的不同表示形式。一般情况下，随
n的增大，T(n)增长较慢的算法为最优的算法。从中我们应该选择使用多项式阶O(nk)的算法， 而避免使用指
数阶的算法。
例如： 下列程序段：
for (i=1; i< n; i++)
for (j=i; j<= n; j++) x++;
有一个二重循环， 语句x++的执行频度为： n+(n-1)+(n-2)+…+3+2+1 =n(n+1)/2
而该语句执行次数关于n的增长率为n2, 即时间复杂度为O(n2)。
5） 最坏时间复杂度
算法中基本操作重复执行的次数还随问题的输入数据集的不同而不同。
6） 算法的空间复杂度（略）
作业2：
1:图1.5、P13：算法的5个特征；
2:P15：两段程序的语句的频度的分析
本章教学总结：
8淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
第二章：线性表
课程：数据结构
课题：第二章 2.1—2.4小节（共6个课时）
2.1 线性表的类型定义
2.2 线性表的顺序表示和实现
2.3 线性表的链式表示和实现
2.4 一元多项式的表示及相加
目的要求：理解线性表的定义和特点；掌握顺序表和链表的特点，掌握在这两种存储结构上各种基本运算的实
现算法以及效率的分析，并学习在这两种存储结构上进行算法设计的方法；以达到利用基本算法进行较复杂算
法设计的目的。
新课重点、难点：线性表、 顺序表、链表
教学方法：课堂讲解、例题演示，课件演示
教学内容及过程：
……………………………第1-2课时……………………………
线性结构的特点：
在数据元素的非空有限集中，
• 存在唯一的一个被称为“第一个”的数据元素；
• 存在唯一的一个被称为“最后一个”的数据元素；
• 除第一个元素之外，集合中的每个元素均只有一个前驱；
• 除最后一个元素之外，集合中的每个元素均只有一个后继。
2.1 线性表的类型定义
2.1.1 线性表的逻辑结构
例如： 英文字母表(A, B, …, Z)就是一个简单的线性表，表中的每一个英文字母是一个数据元素， 每个
元素之间存在唯一的顺序关系，如在英文字母表字母B的前面是字母A， 而字母B的后面是字母C。 在较为复
杂的线性表中，数据元素(data elements ) 可由若干数据项组成，如学生成绩表中，每个学生及其各科成绩
是一个数据元素，它由学号、姓名、各科成绩及平均成绩等数据项(item) 组成，常被称为一个记录(record) ，
含有大量记录的线性表称为文件(file)。数据对象（data object）是性质相同的数据元素集合。
表2-1 车辆登记表
线性表(Linear List)是由n (n≥0)个类型相同的数据元素a1, a2, …， an组成的有限序列，记作（a1,
a2, …，ai-1，ai，ai+1， …，an）。这里的数据元素ai(1≤i≤n)只是一个抽象的符号，其具体含义在不同
情况下可以不同，它既可以是原子类型，也可以是结构类型但同一线性表中的数据元素必须属于同一数据对象。
此外，线性表中相邻数据元素之间存在着序偶关系，即对于非空的线性表（a1,a2,…，ai-1,ai,ai+1, …,
9淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
an）， 表中ai-1 领先于ai，称ai-1 是ai的直接前驱，而称ai是 ai-1的直接后继。除了第一个元素a1外，
每个元素ai有且仅有一个被称为其直接前驱的结点ai-1，除了最后一个元素an外，每个元素ai有且仅有一
个被称为其直接后继的结点ai+1。 线性表中元素的个数n被定义为线性表的长度，n=0时称为空表。
线性表的特点可概括如下：
同一性：线性表由同类数据元素组成，每一个ai必须属于同一数据对象。
有穷性：线性表由有限个数据元素组成， 表长度就是表中数据元素的个数。
有序性：线性表中表中相邻数据元素之间存在着序偶关系。
由此可看出，线性表是一种最简单的数据结构，因为数据元素之间是由一前驱一后继的直观有序的关系确
定；线性表又是一种最常见的数据结构，因为矩阵、数组、字符串、堆栈、 队列等都符合线性条件。
2.1.2 线性表的抽象数据类型定义
ADT List{
数据元素： D={ai| ai∈ElemSet, i=1, 2, …，n, n≥0 ， ElemSet为某一数据对象}
关系：Ｓ＝｛ | ai, ai+1∈D，i=1, 2, …, n-1｝
基本操作：
（1） InitList（&L）
初始条件： L为未初始化线性表。
操作结果： 将L初始化为空表。
（2） DestroyList(&L)
初始条件： 线性表L已存在。
操作结果： 将L销毁。
（3） ClearList(&L)
初始条件： 线性表L已存在 。
操作结果： 将表L置为空表。
（4） ListEmpty（L）
初始条件： 线性表L已存在。
操作结果： 如果L为空表则返回真， 否则返回假。
（5） ListLength（L）
初始条件： 线性表L已存在。
操作结果： 如果L为空表则返回0， 否则返回表中的元素个数。
（6） LocateElem(L, e,compare())
初始条件： 表L已存在， compare()是数据元素判定函数。
操作结果： 返回L中第1个与e满足关系compare() 的数据元素的位序，如果不存在，返回值为0。
（7） GetElem(L, i,&e)
初始条件： 表L存在， 且1≤i≤ListLength（L）。
操作结果： 用e返回线性表L中第i个元素的值。
（8） ListInsert (&L, i, e)
初始条件：表L已存在，1≤i≤ListLength(L)+1。
操作结果：在L中第i个位置之前插入新的数据元素e，L的长度加1。
（9） ListDelete (&L, i, &e)
初始条件： 表L已存在且非空， 1≤i≤ListLength(L)。
操作结果： 删除L的第i个数据元素， 并用e返回其值， L的长度减1。
} ADT List
例2—1
Void union (List &La, List Lb){
La_len= ListLength (La); Lb_len= ListLength (Lb);
10淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
For (i=1;i<= Lb_len;i++){
GetElem (Lb,i,e);
If(!LocateElem(La,e,equal)) ListInsert(La,++ La_len,e);
}
}
O(Listlength(LA)* Listlength(LB))
例2—2
Void MergeList(List La,List Lb,List &Lc){
InitList(Lc);
i=j=1;k=0;
La_len=ListLength(La);Lb_len=ListLength (Lb);
While((i<=La_Len)&&(j<=Lb_len)){
GetElem(La,i,ai); GetElem(Lb,j,bj);
if(ai<= bj) {ListInsert(Lc,++k, ai); ++i;}
else { ListInsert(Lc,++k, bj); ++j}
}
while (i<=La_len) {GetElem(La, i++, ai);
ListInsert(Lc, ++k, ai);
}
while (j<=Lb_len) {GetElem(Lb, j++, bj);
ListInsert(Lc, ++k, bj);
}
}
2.2 线性表的顺序表示和实现
2.2.1 线性表的顺序存储结构
线性表的顺序存储是指用一组地址连续的存储单元依次存储线性表中的各个元素，使得线性表中在逻辑结
构上相邻的数据元素存储在相邻的物理存储单元中，即通过数据元素物理存储的相邻关系来反映数据元素之间
逻辑上的相邻关系。 采用顺序存储结构的线性表通常称为顺序表。
假设线性表中有n个元素，每个元素占k个单元，第一个元素的地址为loc(a1)，则可以通过如下公式计
算出第i个元素的地址loc(ai)：
loc(ai) =loc(a1)+(i-1)×k
其中loc(a1)称为基地址。
它是一种随机存取的数据结构。
顺序存储结构可以借助于高级程序设计语言中的一堆数组来表示，一维数组的下标与元素在线性表中的序
11淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
号相对应(C语言中下标等于序号减1）。线性表的顺序存储结构可用C语言定义如下：
#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
typedef struct
{
ElemType *elem; /* 线性表占用的数组空间 */
int length；
int listsize;
} SeqList；
2.2.2 线性表顺序存储结构上的基本运算
1. 初始化操作
Status IniList_Sq(SqList &L){
L.elem=(ElemType*)malloc(LIST_INIT_SIZE*sizeof(ElemType));
If(!L.elem) exit(OVERFLOW);
L.length=0;
L.listsize=LIST_INIT_SIZE;
Return OK;
}
2. 插入操作
在这种结构中容易实现随机存取第i个数据元素，C语言中数组的下标从0开始，所以ai应在L.elem[i-1]
中存取。
线性表的插入运算是指在表的第i(1≤i≤n+1)个位置之前插入一个新元素e，使长度为n的线性表 (e1，…，
ei-1，ei，…，en) 变成长度为n+1的线性表（e1，…, ei-1，e，ei，…，en）。
用顺序表作为线性表的存储结构时，由于结点的物理顺序必须和结点的逻辑顺序保持一致，因此我们必须
将原表中位置n，n-1，…，i上的结点，依次后移到位置n+1，n，…，i+1上，空出第i个位置，然后在该位
置上插入新结点e。当i=n+1时， 是指在线性表的末尾插入结点，所以无需移动结点，直接将e插入表的末尾
即可。
例如：已知线性表 (4, 9, 15, 28, 30, 30, 42, 51, 62)， 需在第4个元素之前插入一个元素“21”，则需
要将第9个位置到第4个位置的元素依次后移一个位置，然后将“21”插入到第4个位置，如图2.3所示。请
注意区分元素的序号和数组的下标。
图2.3 顺序表中插入元素
Status ListInsert_sq(sqList &L, int i, ElemType e){
If(i<1||i>L.length+1) return ERROR;
If(L.length>=L.listsize){
newbase=(ElemType*)realloc(L.listsize+LISTINCREMENT)*sizeof(ElemType));
If(!newbase)exit(OVERFLOW);
L.elem=newbase;
L.listsize+=LISTINCREMENT;
}
q=&(L.elem[i-1]);
12淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
for(p=&(L.elem[L.length-1]));p>=q;--p)*(p+1)=*p;
*q=e;
++L.length;
return OK；
}
插入元素时，时间主要耗费在移动元素上。移动个数取决于插入位置。
3. 删除操作
线性表的删除运算是指将表的第i(1≤i≤n)个元素删去，使长度为n的线性表(e1，…,ei-1，ei，ei+1，…，
en)变成长度为n-1的线性表(e1，…, ei-1， ei+1，…，en)。删除第i个元素（1≤i≤n〉时需将从第i+1
至第n（共n-i）个元素依次向前移动一个位置。
例如：线性表(4, 9, 15, 21, 28, 30, 30, 42, 51, 62)删除第5个元素， 则需将第6个元素到第10个
元素依次向前移动一个位置，如图2.4所示。
图2.4 顺序表中删除元素
算法描述：
Status ListDelete_Sq(sqList &L,int i,ElemType &e){
If( (i<1) || (i>L.length) ) return ERROR;
P=&(L.elem[i-1]);
e=*p;
q=L.elem+L.length-1;
For(++p; p<=q; ++p) *(p-1)=*p;
--L.Length;
return OK;
}
在顺序表中插入或删除一个数据元素时，其时间主要耗费在移动数据元素上。对于插入算法而言，设Pi
为在第i个元素之前插入元素的概率，并假设在任何位置上插入的概率相等，即Pi=1/(n+1), i=1, 2, …，
n+1。设Eins为在长度为n的表中插入一元素所需移动元素的平均次数， 则
同理，设Qi为删除第i个元素的概率，并假设在任何位置上删除的概率相等，即Qi=1/n, i=1,2, …，
n。删除一个元素所需移动元素的平均次数Edel为
4.在顺序表中查找元素的算法：
int LocatElem_Sq(SqList L,ElemType e, Status(*compare)(ElemType, ElemType))
{
i=1;
p=L.elem;
While (i<=L.length && !(*compare)(*p++,e)) ++i;
13淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
If (i<=L.length) return i;
else return 0;
}
5. 有两个顺序表LA和LB，其元素均为非递减有序排列， 编写一个算法，将它们合并成一个顺序表LC， 要求
LC也是非递减有序排列。例如LA=(2, 2, 3), LB=(1, 3, 3, 4), 则LC=(1, 2, 2, 3, 3, 3, 4)。
算法思想：设表LC是一个空表，为使LC也是非递减有序排列，可设两个指针i、 j分别指向表LA和LB中的
元素， 若LA.elem［i］>LB.elem［j］， 则当前先将LB.elem［j］插入到表LC中; 若LA.elem［i］≤LB.elem
［j］，则当前先将LA.elem［i］插入到表LC中，如此进行下去，直到其中一个表被扫描完毕，然后再将未扫
描完的表中剩余的所有元素放到表LC中
Void MergeList_Sq(SqList La, SqList Lb, SqList &Lc )
{
Pa=La.elem; pb=Lb.elem;
Lc.listsize=Lc.length=La.length+Lb.length;
Pc=Lc.elem=(ElemType*)malloc(Lc.listsize*sizeof(ElemTpe));
If (!Lc.elem) exit (OVERFLOW);
pa_last=La.elem+La.length-1;
pb_last=Lb.elem+Lb.length-1;
While (pa<=pa_last && pb<=pb_last){
If (*pa<=*pb) *pc++=*pa++;
Else *pc++=*pb++;
}
while(pa<=pa_last) *pc++=*pa++;
while(pb<=pb_last) *pc++=*pb++;
}
由上面的讨论可知， 线性表顺序表示的优点是：
(1）无需为表示结点间的逻辑关系而增加额外的存储空间（因为逻辑上相邻的元素其存储的物理位置也是相邻
的）；
(2）可方便地随机存取表中的任一元素。
其缺点是：
插入或删除运算不方便，除表尾的位置外，在表的其它位置上进行插入或删除操作都必须移动大量的结点，
其效率较低。
由于顺序表要求占用连续的存储空间，存储分配只能预先进行静态分配，因此当表长变化较大时，难以确
定合适的存储规模。若按可能达到的最大长度预先分配表空间，则可能造成一部分空间长期闲置而得不到充分
利用；若事先对表长估计不足，则插入操作可能使表长超过预先分配的空间而造成溢出。
作业1：
1：算法2.1、图2.2、算法2.4
2：算法2.5、算法2.6
……………………………第3-4课时……………………………
2.3 线性表的链式表示和实现
2.3.1 单链表
线性表的链式存储：用一组任意的存储单元存放线性表的数据元素（这组存储单元可以连续，也可不连续）。
为表示数据元素之间的逻辑关系，还需有存储一个指示后继的信息——指针。由数据域和指针域构成数据元素
14淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
的存储映象，称为结点（Node）。
单链表包括两个域：数据域用来存储结点的值；指针域用来存储数据元素的直接后继的地址（或位置）。
链表正是通过每个结点的指针域将线性表的n个结点按其逻辑顺序链接在一起。由于链表的每个结点只有一个
指针域，故将这种链表又称为单链表。
由于单链表中每个结点的存储地址是存放在其前趋结点的指针域中的，而第一个结点无前趋，因而应设一
个头指针H指向第一个结点。同时，由于表中最后一个结点没有直接后继，则指定线性表中最后一个结点的指
针域为“空”（NULL）。这样对于整个链表的存取必须从头指针开始。
例如：图2.5所示为线性表（A, B, C, D, E, F, G, H）的单链表存储结构，整个链表的存取需从头指针
开始进行，依次顺着每个结点的指针域找到线性表的各个元素。
图2.5单链表的示例图
图2.6 单链表的逻辑状态
图2.7 带头结点单链表图示
单链表可以由头指针唯一确定。 单链表的存储结构描述如下：
Typedef struct LNode {
ElemType data;
Struct LNode *next;
}LNode ,*Linklist; /* LinkList为结构指针类型*/
假设L是LinkList型的变量，则L是一个结构指针，即单链表的头指针，它指向表中第一个结点（对于带
头结点的单链表，则指向单链表的头结点），若L=NULL（对于带头结点的单链表为L->next=NULL），则表示单链
表为一个空表，其长度为0。若不是空表，则可以通过头指针访问表中结点，找到要访问的所有结点的数据信
息。对于带头结点的单链表L，p=L->next指向表中的第一个结点a1，即p->data=a1，而p->next->data=a2。
其余依此类推。
2.3.2 单链表上的基本运算
1. 建立单链表
15淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图2.8 头插法建立单链表图示
void CreateList_L(Linklist &L, int n){
L=(Linklist) malloc(sizeof(Lnode));
L->next=NULL;
For(i=n; i>0; --i){
p=(Linklist)malloc(sizeof(Lnode));
scanf(& p->data);
p->next=L->next;
L->next=p;
}
}
2） 尾插法建表
图2.9 尾插法建表图示
2. 查找
在单链表中，由于每个结点的存储位置都放在其前一结点的next域中，因而即使知道被访问结点的序号i，
也不能像顺序表那样直接按序号i访问一维数组中的相应元素，实现随机存取，而只能从链表的头指针出发，
顺链域next逐个结点往下搜索，直至搜索到第i个结点为止。
算法描述：设带头结点的单链表的长度为n，要查找表中第i个结点，则需要从单链表的头指针L出发，从头
结点（L->next）开始顺着链域扫描， 用指针p指向当前扫描到的结点, 初值指向头结点，用j做计数器，累
计当前扫描过的结点数（初值为0）， 当j = i 时， 指针p所指的结点就是要找的第i个结点。
查找元素的算法：
Status GetElem_L(Linklist L,int i,ElemType &e){
P=L->next;
j=1;
While (p & jnext;
++j;
}
16淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
if ( !p ║ j>i) return ERROR;
e=p->data;
return ok;
}
3. 单链表插入操作
算法描述：要在带头结点的单链表L中第i个位置插入一个数据元素e，需要首先在单链表中找到第i-1
个结点并由指针pre指示，然后申请一个新的结点并由指针s指示，其数据域的值为e，并修改第i-1个结点
的指针使其指向s，然后使s结点的指针域指向原第i个结点。
插入：s->next=p->next; p->next=s;
图2.10 在单链表第i个结点前插入一个结点的过程
Status ListInsert_L(Linklist &L, int i, ElmeType e ){
p=L;j=0;
While( p && jnext;
++j
}
If( !p ║ j>i-1) return ERROR;
s=(Linklist)malloc(sizeof(LNode));
s->data=e;
s->next=p->next;
p->next=s;
return OK;
}
4. 删除
17淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图2.11 单链表的删除过程
Status ListDelete_L(Linklist &L, int i, Elemtype &e){
p=L;j=0;
While ( p->next && jnext;
++j;
}
if ( !(p->next) ║ j>i-1) return ERROR ;
q = p->next;
p->next=q->next;
e = q->data;
free(q);
return OK;
}
合并单链表：
void mergelist_L(Linklist &La,Linklist &Lb,Linklist &Lc){
pa=La->next; pb=Lb->next;
Lc=pc=La;
While( pa && pb) {
if( pa->data <= pb->data){
pc->next=pa; pc=pa; pa=pa->next;
}
else{
pc->next=pb; pc=pb; pb=pb->next;
}
}
pc->next= pa ? pa : pb;
free(Lb);
}
作业2：
1：图2.5、图2.8、图2.9
2：算法2.8、算法2.9、算法2.10、算法2.11
……………………………第5-6课时……………………………
18淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
2.3.3 循环链表
循环链表(Circular Linked List)是单链表的另一种形式，它是一个首尾相接的链表。其特点是将单链表
最后一个结点的指针域由NULL改为指向头结点或线性表中的第一个结点，就得到了单链形式的循环链表，并称
为循环单链表。类似地，还有多重链的循环链表。 在循环单链表中，表中所有结点都被链在一个环上，多重循
环链表则是将表中的结点链在多个环上。为了使某些操作实现起来方便，在循环单链表中也可设置一个头结点。
这样，空循环链表仅由一个自成循环的头结点表示。
图2.12 带头结点循环单链表
2.3.4 双向链表
循环单链表的出现，虽然能够实现从任一结点出发沿着链能找到其前驱结点，但时间耗费是O(n) 。如果
希望从表中快速确定某一个结点的前驱，另一个解决方法就是在单链表的每个结点里再增加一个指向其前驱的
指针域prior。 这样形成的链表中就有两条方向不同的链，我们可称之为双(向)链表(Double Linked List)。
双链表的结构定义如下
typedef struct DulNode{
ElemType data;
Struct DulNode *prior, *next;
}DulNode,*DuLinklist;
图2.13 双链表的结点结构
由于在双向链表中既有前向链又有后向链，寻找任一个结点的直接前驱结点与直接后继结点变得非常方便。
设指针p指向双链表中某一结点，则有下式成立：
p->prior->next = p = p->next->prior
图2.14 双向循环链表图示
1. 双向链表的前插操作
19淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图2.15 双向链表插入操作
2. 双向链表的删除操作
算法描述：
图2.16 双向链表的删除操作
2.3.5 静态链表
静态链表同样可以借助一维数组来描述：
#define MAXSIZE 1000
typedef struct {
ElemType data;
int cur;
}component,SlinkList[MAXSIZE];
设S为SlinkList型变量，则S[0].cur指示第一个结点在数组中的位置，设i=s[0].cur，则s[i].data
存放线性表的第一个元素，且s[i].cur指示第二个结点在数组中位置。一般情况，若第i个分量表示链表的第
k个结点，则s[i].cur指示第k+1个结点的位置。在静态链表中以整型游标i代替动态指针p，i=s[i].cur类
似于p=p->next。
图2.17 静态链表的插入和删除操作示例
定位函数：
int LocateElem_SL(SlinkList s, ElemType e){
i=s[0].cur;
while( i && s[i].data!=e) i=s[i].cur;
return i;
}
void IniteSpace_SL(SlinkList &space){
20淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
for(i=0; iexpexp，则结点p所指的结点应是“和多项式”中的一项，令指针p后移；若p->exp>q->exp，
则结点q所指的结点应是“和多项式”中的一项，将结点q插入在结点p之前，且令指针q在原来的链表上后
移；
若p->exp=q->exp， 则将两个结点中的系数相加， 当和不为零时修改结点p的系数域， 释放q结点；
若和为零，则和多项式中无此项， 从A中删去p结点， 同时释放p和q结点
作业3：
1：图2.12、图2.14、图2.15、图2.16、图2.17、图2.18
2：算法2.18、算法2.19、算法2.23
本章教学总结：
22淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
第三章：栈和队列
课程：数据结构
课题：第三章 3.1—3.4小节（共6个课时）
3.1 栈
3.2 栈的应有和举例
3.3 栈与递归的实现
3.4 队列
目的要求：理解栈和队列的定义、特点，学习它们的各种组织方式及算法；掌握它们的空和满的判断条件；
并学会它们的简单应用。
新课重点、难点：
教学方法：课堂讲解、例题演示，课件演示
教学内容及过程：
……………………………第1-2课时……………………………
3.1 栈
3.1.1 栈的定义
栈作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表尾进行，通常将表中允许进行
插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示
器指示。同时表的另一端被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈
或入栈，删除操作称为出栈或退栈。
设S=(a1,a2,…,an)表示栈，则a1为栈底元素，an 为栈顶元素。栈是一种后进先出（Last In First Out）的
线性表（简称LIFO结构）。
栈只能对栈顶元素进行插入和删除操作。
ADT Stack{
数据元素：可以是任意类型的数据，但必须属于同一个数据对象。
数据关系：栈中数据元素之间是线性关系。
基本操作：
（1） InitStack(&S)
初始条件：S为未初始化的栈。
操作结果：将S初始化为空栈。
（2） ClearStack(&S)
初始条件：栈S已经存在。
操作结果：将栈S置成空栈。
（3） StackEmpty(S)
23淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
初始条件：栈S已经存在。
操作结果：若S为空栈，则函数值为TRUE，否则FALSE
（4） Push(&S,e)
初始条件：栈S已经存在。
操作结果：在S的顶部插入(亦称压入)元素e；
（5） Pop(&S, &e)
初始条件：栈S已经存在。
操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值。
（6） GetTop(S, &e)
初始条件： 栈S已经存在。
操作结果：取栈S的顶部元素。
与Pop(&S, e)不同之处在于GetTop(S,&e)不改变栈顶的位置。
3.1.2 栈的表示和实现
1. 顺序栈
顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，
同时由于栈的操作的特殊性， 还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的
位置。通常以top=0表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。 栈的顺序存储结构定义
如下：
＃define TRUE 1
＃define FALSE 0
typedef struct {
SElemType * base;
SElemType *top;
int stacksize; //栈可使用的最大容量
} Sqstack;
按初始分配量进行第一次存储分配，base为栈底指针，始终指向栈底。top为栈顶指针，初值指向栈底，
每插入一个元素，top增1；每删除一个元素，top减1，top始终在栈顶元素的下一个位置上。
顺序栈基本操作的实现如下:
(1) 初始化。
Status InitStack (SqStack &S){
S.base=(SElemType *)malloc
(STACK_INIT_SIZE *sizeof(SElemType));
If (! S.base) exit (OVERFLOW);
S.top=S.base;
S.stacksize=STACK_INIT_SIZE;
return OK;
24淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
}
(2) 取栈顶元素
Status GetTop(SqStack S, SElemType &e)
{
if (S.top == S.base) return ERROR;
e= * (S.top-1);
return OK;
}
(3) 入栈。
Status Push(SqStack &S, SElemType e){
if (S.top - S.base>= S.stacksize){
S.base=(SElemType*)realloc(S.base,
(S.stacksize+STACKINCREMENT)*sizeof(SElemType));
if(!S.base) exit(OVERFLOW);
S.top=S.base+S.stacksize;
S.stacksize+=STACKINCREMENT;
}
*S.top++=e; return OK;
}
(4) 出栈
Status Pop(SqStack &S, SelemType &e)
{
If( S.top==S.base) return ERROR;
e=*--S.top;
return OK;
}
在栈的共享技术中最常用的是两个栈的共享技术：它主要利用了栈“栈底位置不变，而栈顶位置动态变化”
的特性。首先为两个栈申请一个共享的一维数组空间S［M］，将两个栈的栈底分别放在一维数组的两端，分别
是0，M-1。 由于两个栈顶动态变化，这样可以形成互补，使得每个栈可用的最大空间与实际使用的需求有关。
由此可见，两栈共享比两个栈分别申请M/2的空间利用率高。
2. 链栈
3.2 栈的应用举例
1. 数制转换
假设要将十进制数N转换为d进制数，一个简单的转换算法是重复下述两步，直到N等于零：
X = N mod d (其中mod为求余运算)
N = N div d (其中div为整除运算)
如(1348)10=(2504)8
25淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
void conversion()
{ InitStack(S);
scanf(“%d”,&N);
while(N)
{ Push(s, N % 8 );
N=N / 8;
}
while( !StackEmpty)
{ Pop(S,e);
printf(“%d”,e);
}
} 算法：3.1
作业1：
1：图3.1、3.2
2：P47：栈基本操作的算法描述、算法3.1
……………………………第3-4课时……………………………
4. 迷宫求解
拓展：填充算法
3.3 栈与递归的实现
26淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
栈非常重要的一个应用是在程序设计语言中用来实现递归。 递归是指在定义自身的同时又出现了对自身的调
用。 如果一个函数在其定义体内直接调用自己，则称其为直接递归函数；如果一个函数经过一系列的中间调用
语句， 通过其它函数间接调用自己，则称其为间接递归函数。
1. 递归特性问题
1) 递归函数
例如， 很多数学函数是递归定义的， 如二阶Fibonacci数列：
递归过程的实现
一个函数调用另一个函数时，在运行被调用函数之前，系统做的工作有：
(1) 保留本层参数与返回地址（将所有的实在参数、 返回地址等信息传递给被调用函数保存）；
(2) 给下层参数赋值（为被调用函数的局部变量分配存储区）；
(3) 将程序转移到被调函数的入口。
而从被调用函数返回调用函数之前，系统也应完成三件工作：
(1) 保存被调函数的计算结果；
(2) 恢复上层参数（释放被调函数的数据区）；
(3) 依照被调函数保存的返回地址， 将控制转移回调用函数。
当多个函数调用时按后调用先返回的原则。
例 求n的阶乘
＃include
lang fac(int n)
{ lang L;
if(!n) L=1;
else L=n*fac(n-1);
return L;
}
int main()
{ int n;
lang L;
scanf(“%d”,&n);
L=fac(n);
printf(“%ld”,L);
}
例3-2：n阶Hanoi塔问题：假设有三个分别命名为X、Y和Z的塔座，在塔座X上插有n个直径大小各不相同、
27淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
依小到大编号为1， 2, …， n的圆盘。现要求将X轴上的n个圆盘移至塔座Z上并仍按同样顺序叠排，圆盘
移动时必须遵循下列原则：
(1) 每次只能移动一个圆盘；
(2) 圆盘可以插在X、 Y和Z中的任何一个塔座上；
(3) 任何时刻都不能将一个较大的圆盘压在较小的圆盘之上。
如何实现移动圆盘的操作呢？当n=1时，问题比较简单，只要将编号为1的圆盘从塔座X直接移动到塔座Z上
即可；当n>1时， 需利用塔座Y作辅助塔座， 若能设法将压在编号为n的圆盘上的n-1个圆盘从塔座X(依照
上述原则)移至塔座Y上， 则可先将编号为n的圆盘从塔座X 移至塔座Z上，然后再将塔座Y上的n-1个圆盘
(依照上述原则)移至塔座Z上。而如何将n-1个圆盘从一个塔座移至另一个塔座问题是一个和原问题具有相同
特征属性的问题，只是问题的规模小个1，因此可以用同样方法求解。由此可得如下算法所示的求解n阶Hanoi
塔问题的函数。
void hanoi(int n,char x,char y,char z) /*将塔座X上按直径由小到大且至上而下编号为1至n的n个圆盘
按规则搬到塔座Z上， Y可用作辅助塔座 */
1 {
2 if(n==1)
3 move(x,1,z); /* 将编号为1的圆盘从X移动Z */
4 else {
5 hanoi(n-1,x,z,y); /* 将X上编号为1至n-1的圆盘移到Y,Z作辅助塔 */
6 move(x,n,z); /* 将编号为n的圆盘从X移到Z */
7 hanoi(n-1,y,x,z); /* 将Y上编号为1至n-1的圆盘移动到Z， X作辅助塔 */
8 }
9 } 算法：3.5
下面给出三个盘子搬动时hanoi(3, A, B, C) 递归调用过程：
hanoi(2,A,C,B):
hanoi(1,A,B,C) move(A->C) 1号搬到C
move(A->B) 2号搬到B
hanoi(1,C,A,B) move(C->B) 1号搬到B
move(A->c) 3号搬到C
hanoi(2,B,A,C):
hanoi(1,B,C,A) move(B->A) 1号搬到A
move(B->c) 2号搬到C
hanoi(1,A,B,C) move(A->C) 1号搬到C
3) 递归问题的优点
通过上面的例子可看出，递归既是强有力的数学方法， 也是程序设计中一个很有用的工具。其特点是
对递归问题描述简捷，结构清晰，程序的正确性容易证明。
4) 递归算法求解问题的要素
递归算法就是算法中有直接或间接调用算法本身的算法。 递归算法的要点如下：
28淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
(1) 问题具有类同自身的子问题的性质， 被定义项在定义中的应用具有更小的尺度。
(2) 被定义项在最小尺度上有直接解。
设计递归算法的方法是：
(1) 寻找方法，将问题化为原问题的子问题求解（例n!=n*(n-1)!）。
(2) 设计递归出口，确定递归终止条件
(例求解n!时，当n=1时，n! =1)。
作业2：
1：图3.7
2：算法3.5、种子填充算法、两种算法求解n!
……………………………第5-6课时……………………………
3.4 队 列
3.4.1 队列的定义
队列 (Queue)是另一种限定性的线性表，它只允许在表的一端插入元素，而在另一端删除元素，所以
队列具有先进先出(Fist In Fist Out， 缩写为FIFO)的特性。在队列中，允许插入的一端叫做队尾(rear)，
允许删除的一端则称为队头(front)。 假设队列为q=(a1，a2，…，an)，那么a1就是队头元素，an则是队尾
元素。队列中的元素是按照a1，a2，…，an的顺序进入的， 退出队列也必须按照同样的次序依次出队，也就
是说，只有在a1，a2，…，an-1都离开队列之后，an才能退出队列。
数据元素：可以是任意类型的数据，但必须属于同一个数据对象。
关系： 队列中数据元素之间是线性关系。
基本操作：
（1） InitQueue(&Q)： 初始化操作。 设置一个空队列。
（2） QueueEmpty(Q)： 判空操作。 若队列为空， 则返回TRUE， 否则返回FALSE。
（3）EnQueue(&Q，e)：进队操作。在队列Q的队尾插入e。
（4） DeQueue(&Q,&e)： 出队操作。使队列Q的队头元素出队， 并用e带回其值。
（5） ClearQueue(&Q)： 队列置空操作。 将队列Q置为空队列。
（6） DestroyQueue(&Q)： 队列销毁操作。 释放队列的空间。
3.4.2 队列的表示和实现
链队列
29淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
链队列可以定义如下：
＃define TRUE 1
＃define FALSE 0
typedef struct Qnode
{ QElemType data;
Struct Qnode *next;
} Qnode, *QueuePtr;
typedef struct
{ QueuePtr front;
QueuePtr rear;
} LinkQueue;
（1） 初始化操作。
Status InitQueue(LinkQueue &Q)
{
Q.front = Q.rear = (Queueptr) malloc(sizeof(Qnode));
if(!Q.front) exit ( OVERFLOW);
Q.front ->next = NULL;
return OK;
}
（2）销毁队列
Status DestroyQueue(LinkQueue &Q)
{ while(Q.front)
{ Q.rear = Q.front->next;
free (Q.front);
Q.front = Q.rear;
}
return OK;
}
（3） 入队操作。
Status EnQueue (LinkQueue &Q, QelemType e)
{ p= (QueuePtr) malloc(sizeof(Qnode));
if (!p) exit ( OVERFLOW);
p->data = e; p->next = NULL;
Q.raer -> next =p;
Q.rear = p;
return OK;
}
（4） 出队操作。
Status DeQueue (LinkQueue &Q, QelemType &e)
{ If ( Qfront == Q.rear) return ERROR;
p=Q.front->next;
e=p->data;
Q.fornt->next =p->next;
If (Q.rear == p) Q.rear = Q.front;
free(p); return OK;
30淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
}
3.4.3：循环队列
图3.12 头、尾指针和队列元素之间的关系
图3.14 循环队列的头尾指针
如何区分队列“空”和“满”
1. 另设一个标志位以区分队列是空还是满；
2. 少用一个元素空间，当队列头指针在队列尾指针的下一个位置上时为“满”。
当Q.front=Q.rear时队空；Q.front+1=Q.rear时队满
循环队列满足条件 (Q.rear+1)%MAXQSIZE== Q.front 队满
循环队列的类型定义：
#define MAXQSIZE 100 /*队列的最大长度*/
typedef struct
{ QElemType *base; /* 队列的元素空间*/
int front; /*头指针指示器*
int rear;
} SqQueue; /*尾指针指示器*/
（1） 初始化操作。
Status InitQueue (SqQueue &Q)
{ Q. base = (QElemType * )
malloc(MAXQSIZE * sizeof (QElemType));
if ( ! Q. base) exit (OVERFLOW);
Q. front = Q. rear = 0;
return OK;
}
（2） 入队操作。
Status EnQueue (SqQueue &Q, QElemType e)
31淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
{ if ((Q. rear+ 1) % MAXQSIZE == Q. front) return ERROR;
Q.base[Q, rear] = e;
Q.rear = (Q. rear + 1) % MAXQSIZE;
return OK;
}
（3） 出队操作。
Status DeQueue (SqQueue &Q, QElemType &e)
{ if (Q. front = = Q. rear) return ERROR;
e = Q. base[Q, front];
Q. front = (Q. front + 1) % MAXQSIZE;
return OK;
}
(4) 求队列长度
int QueueLength (SqQueue Q)
{
return (Q. rear - Q. front + MAXQSIZE) % MAXQSIZE;
}
作业3：
1：图3.8、图3.10、图3.11、图3.14
2：P62：队列的基本操作算法、P64：循环队列的基本操作算法、
本章教学总结：
32淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
第四章：串
课程：数据结构
课题：第四章 4.1—4.4小节（共4个课时）
4.1 串类型的定义
4.2 串的表示和实现
4.3 串的模式匹配算法
4.4 串操作应用举例
目的要求：了解串的概念，掌握串的基本运算，学习串运算在不同存储结构下的实现过程。
新课重点、难点：
教学方法：课堂讲解、例题演示，课件演示
教学内容及过程：
……………………………第1-2课时……………………………
4.1 串的定义
串(String)是零个或多个字符组成的有限序列。 一般记为：
S= ′a1a2...an′ (n≥0)
其中S是串的名字, 用单引号括起来的字符序列是串的值，ai(1≤i≤n)可以是字母、数字或其它字符。n
是串中字符的个数, 称为串的长度，n=0时的串称为空串 (Null String)。
串中任意个连续的字符组成的子序列称为该串的子串。包含子串的串相应地称为主串。通常将字符在串中
的序号称为该字符在串中的位置。子串在主串中的位置则以子串的第一个字符在主串中的位置来表示。
假串A=′China Beijing′, B=′Beijing′, C=′China′, 则它们的长度分别为13、7和5。B和C是A
的子串, B在A中的位置是7, C在A中的位置是1。
当且仅当两个串的值相等时,称这两个串是相等的，即两个串的长度相等, 且每个对应位置的字符都相等时
才相等。
串值必须用一对单引号括起来，但单引号本身不属于串，它的作用只是为了避免与变量名或数的常量混淆
而已。
在各种应用中，空格常常是串的字符集合中的一个元素，因而可以出现在其它字符中间。由一个或多个空
格组成的串‘ ’称为空格串（blank string ,请注意：此处不是空串）。它的长度为串中空格字符的个数。为
了清楚起见，以后我们用符号“Ø”来表示“空串”。串的逻辑结构和线性表极为相似，区别仅在于串的数据对
象约束为字符集。 串的逻辑结构和线性表极为相似，区别仅在于串的数据对象约束为字符集。
串的抽象数据类型定义如下:
ADT String {
数据对象: D={ai| ai ∈CharacterSet, i=1, 2, …, n; n≥0}
数据关系: R={| ai-1, ai ∈D, i=2, …, n; n≥0}
基本操作:
(1) StrAssign（&T,chars）
初始条件：chars是字符串常量。
操作结果：生成一个其值等于chars的串T。
(2) Strcopy（&T,S）
初始条件：串S存在。
操作结果：由串S复制得串T。
(3) StrEmpty（S）
33淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
初始条件：串S存在。
操作结果：若S为空串，则返回TURE，否则返回FALSE
(4) StrCompare（S，T）
初始条件：串S和T存在。
操作结果：若S>T，则返回值>0；若S=T,则返回值＝0；
若S0 )
{ n=StrLength( T) ; m=StrLength( T ); i=pos;
while ( i<＝n-m+1)
{ SubString( Sub, S, I ,m) ;
If ( StrCompare( Sub, T)!=0) ++I;
Else return I;
} // while
} // if
return 0; // S中不存在与T相等的子串
} // Index 算法：4.1
4.2 串的表示和实现
4.2.1 定长顺序存储表示串
类似于线形表的顺序存储结构，用一组地址连续的存储单元存储串值得字符序列。在串的定长顺序存储结
构中，按照予定义的大小，为每个定义的串变量分配一个固定长度的存储区，则可用定长数组如下描述之。
#define MAXSTRLEN 255 // 用户可在255 以内定义最大串长
Typedef unsigned char SString[MAXSTRLEN+1];
//0号单元存放串的长度
串的实际长度可在这预定义长度的范围内随意，超过预定义长度的串值则被舍去，称之为“截断”。对串
长有两种表示方法：一个是如上述定义描述的那样，以下标为0的数组分量存放串的实际长度，如PASCAL语言
中的串类型采用这种表示方法；二是在串值后面加一个不计入串长的结束标记字符，如在C语言中以“\0”表
示串值的终结。此时的串长为隐含值，显然不便于进行某些串操作。
1.串联接Concat(& T , S1, S2)
假设S1，S2和T都是SString 型的串变量，且串T是由串S1联接串S2得到的，即串T的值的前一段和
串S1的值相等，串T的值的后一段和串S2的值相等，则只要进行相应的“串值复制”操作即可，只是需要按
前述约定，对超长部分实施“截断”操作。基于串S1和S2长度的不同情况，串T的产生可能有如下三种情况：
1）S1[0]+S2[0]<=MAXSTRLEN,如图4.10（a）所示，得到的串T是正确的结果：
2）S1[0] < MAXSTRLEN而 S1[0]+S2[0]>MAXSTRLEN,则将串S2的一部分截断，得到的串T只包含串S2的一个
子串，如图4.1（b）所示；
3）S1[0]=MAXSTRLEN，则得到的串T并非联接结果，而和串S1相等。上述算法描述如算法4.2所示。
Status Concat ( SString & T , SString S1 , SString S2 )
{ // 用T返回由S1和S2联接而成的新串。若未截断，则返回 TRUE , 否则FALSE 。
If ( S1 [ 0 ] + S2 [ 0 ] <= MAXSTRLEN )
{ // 未截断
T [ 1 . . S1 [ 0 ] ] = S1 [ 1 . . S1 [ 0 ] ] ;
T [ S1 [ 0 ] + 1 . . S1 [ 0 ] + S2 [ 0 ] ] = S2[1..S2[0]] ;
T [ 0 ] = S1 [ 0 ] + S2 [ 0 ] ; uncut = TRUE ;
}
else if (S1[0] < MAXSTRLEN)
{ // 截断
T [ 1 . . S1 [ 0 ] ] = S1 [ 1 . . S1 [0] ] ;
T [ S1[0] + 1 . . MAXSTRLEN ] = S2[ 1 . . MAXSTRLEN – S1[0] ] ;
T [0] = MAXSTRLEN ; uncut = FALSE ;
}
else
{ // 截取（仅取S1）
35淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
T [ 0 . . MAXSTRLEN ] = S1 [ 0 . . MAXSTRLEN ] ;
Uncut = FALSE;
}
Return uncut ;
} // Concat 算法4.2
2. 求子串SubString ( & Sub , S , pos , len )
求子串的过程即为复制字符串的过程。将串S 中从第Pos 个字符开始长度为 len 的字符序列复制到串Sub
中。显然，本操作不会有需截断的情况，但有可能产生用户给出的参数不符合操作的初始条件，当参数非法时，
返回ERROR。其算法描述如算法4.3所示。
Status SubString ( SString & Sub , SString S , int pos . int len )
{ //用Sub返回串是S 的第pos 个字符起长度为len的字串。
//其中: 1<= pos <= Strlength (S) 0 <= len <= Strlength(S)–pos + 1。
If ( pos < 1 || len < 0 || len > S [ 0 ] – pos + 1 )
return ERROR ;
Sub [ 1 . . len ] = S [ pos . . pos + len – 1 ] ;
Sub [ 0 ] = len ;
return OK ;
} // SubString 算法4.3
SubString(SString & Sub,SString S,int pos，int len)
{ //用 Sub 返回串是 S 的第 pos 个字符起长度为 len 的字串。其中：1<=pos<=Strlength(S)且
0<=len<=Strlength(S)– pos+1。
If(pos<1 || len<0 || len>S[0]–pos+1)
return ERROR ;
Sub[1..len]=S[pos..pos+len–1];
Sub[0]=len;
return OK ;
} // SubString
算法4.3
综上两个操作可见，在顺序存储结构中，实现串操作的原操作为“字符序列的复制”，操作的时间复杂度
基于复制的字符序列的长度。另一操作特点是，如果在操作中出现串值序列的长度超过上界MAXSTRLRN时，约
定用结尾法处理，这种情况不仅在求联接串时可能发生，在串的其他操作中，如插入、置换等也可能发生。克
服这个弊病惟有不限定串长的最大长度，即动态分配串的存储空间。
作业1：
1：
2：
……………………………第3-4课时……………………………
4.2.2堆分配存储表示
这种存储表示的特点是，仍以一组地址连续的存储单元存放串值字符序列，但他们的存储空间是在程序执
行过程中动态分配而得。在C语言中，存在一个称之为“堆”的自由存储区，并由C语言的动态分配函数malloc()
和free() 来管理。利用函数malloc()为每个新产生的串分配一块实际串长所需要的存储空间，若分配成功，
则返回一个指向起始地址的指针，作为串的基址，同时，为了以后处理方便，约定串长也作为存储结果的一部
分。
36淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
Typedef struct
{char * ch ; // 若是非空串，则按串长分配存储区，否则ch为NULL
int length ;// 串长度
}HString ;
（1）串插入操作StrInsert( & S , pos , T )
为串S重新分配大小等于串S和串T长度之和的存储空间，然后进行串值复制 。
Status StrInsert(HString &S, int pos ,HString T )
{//1<=pos<=Strlength(S)+1.在串S的第pos 个字符之前插入串T 。
if ( pos<1pos>S.length+1 ) return ERROR ; / / pos不合法
if ( T. length )
{ // T非空，则重新分配，插入T
if(!(S.ch=(char*)realloc(S.ch,(S.length+T.length)*sizeof(char))))
exit ( OVERFLIW) ;
for (i=S,length–1; i> = pos–1; - - i) // 为插入T而腾出位置
S.ch[ i + T.length ] = S.ch[i ] ;
S.ch[pos–1 ..pos+T.length–2]=T.ch[0 ..T.length–1] ; //插入T
S.length + = T.length ;
}
Return OK ;
} // StrInsert 算法4.4
Status StrAssing( HString & T, char * chars )
{ // 生成一个其值等于串常量 chars 的串 T
If ( T,ch ) free (T,ch) ; // 释放 T原有的空间
For ( I = 0, c = chars ; c ; ++ I, ++ c ) ; // 求 chars 的长度
If( ! I ) {T,ch = NULL ; T.length = 0 ; }
Else {If( !(T ,ch=(char*)malloc(I* sizeof(char ))))
Exit ( OVERFLOW ) ;
T.ch[ 0 . . I – 1 ] = chars [ 0 . . I – 1 ] ;
T. length = I ;
}
Return OK ;
} // StrAssign P76下：算法
Int Strlength ( HString S )
{ //返回S 的元素个数，称为串的长度。
Return S. length ;
} // Strlength
Int StrCompare ( HString S , HString T )
{ // 若 S>T, 则返回值 >0 ；
// 若 S=T ,则返回值 =0 ；
// 若 SS. length || len <0 || len>S.length–pos+1)
Return ERROR ;
If ( Sub .ch ) free ( Sub.ch ) ; // 释放旧空间
If(!len) { Sub.ch = NULL; Sub.length = 0 ; } // 空子串
Else { Sub.ch = ( char * ) malloc( len * sizeof (char ) ) ;
Sub,ch[0 .. len–1]=S[pos–1 . . pos+len–2] ;
Sub.length = len ;
} //完整子串
Return OK ;
} // SubString
4.2.3串的块链存储表示
和线性表的链式存储结构相类似，也可采用链表方式存储串值。由于串结构的特殊性——结构中的每个数
据元素是一个字符，则用链表存储串值时，存在一个“结点大小”的问题，即每个结点可以存放一个字符，也
可以存放多个字符。例如，图4.2（a）是结点大小为1的链表。当结点大小大于4（即，每个结点可以存放四
个字符）的链表，图4.2(b)是结点大小为1的链表。当结点大小大于1时，由于串长不一定是结大小的整数倍，
则链表中的最后一个结点不一定全被串值占满，此时通常补上“#”或其他的非串值字符（通常“#”不属于串
的字符集，是一个特殊的符号）。
为了便于进行串的操作，当以链表存储串值时，除头指针外还可附设一个尾指针指示链表中的最后一个结
点，并给出当前串的长度。称如此定义的串存储结构为块链结构，说明如下：
//====== 串的块链存储表示=======
#define CHUNKSIZE 80 //可由用户定义的大小
38淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
typedef struct Chunk
{ char ch[CHUNKSIZE] ;
struct Chunk * next ;
}Chunk ;
typedef struct
{ Chunk * head , * tail ; // 串的头和尾指针
int curken ; // 串的当前长度
}LString ;
由于在一般情况下，对串进行操作时，只需要从头到尾顺序扫描即可，则对串值不必建立双向链表。设尾
指针的目的是为了便于进行联结操作，但应注意联结时需处理第一个串尾的无效字符。
在链式存储方式中，结点大小的选择和顺序存储方式的格式选择一样都很重要，它直接影响着串处理的效
率。在各种串的处理系统中，所处理的串往往很长或很多。例如，一本书的几百万个字符，情报资料的成千上
万个条目。这要求我们考虑串值的存储密度。存储密度可定义为：
存储密度 = 串值所占的存储位 / 实际分配的存储位
显然，存储密度小（如结点大小为1时），运算处理方便，然而，存储占用量大。如果在串处理过程中需进
行内、外存交换操作过多而影响处理的总效率。应该看到，串的字符集的大小也是一个重要因素。一般地，字
符集小，则字符的机内编码就短，这也影响串值的存储方式的选取。
串值的链式存储结构对某些串操作，如联结操作等有一定方便之处，但总的说来不如另外两种存储结构灵
活，它占用存储量大且操作复杂。此外，串值在链式存储结构时串操作的实现和线性表在链表存储结构中的操
作类似，故在此不作详细讨论。
4.3 串的模式匹配算法
4.3.1 求子串位置的定位函数 Index( S, T ,pos)
子串的定位操作通常称作串的模式匹配（其中T被称为模式串），是各种串处理系统中最重要的操作之一。
在4.1节中曾借用串的其他基本操作给出了定位函数的一种算法。
根据算法4.1的基本思想，采用定长顺序存储结构，可以写出不依赖于其他串操作的匹配算法，如算法4.5
所示。
int Index （SString S, SString T, int pos ）
{ // 返回子串 T 在主串中第 pos 个字符之后的位置。如不存在，则函数值为 0。其中：T 非空，
1<=pos<=Strlength( S )。
i = pos ; j = 1 ;
while ( i<=S[ 0 ] && j<= T[ 0 ] )
{if ( S[i] = = T[j]) { ++ i ; ++ j ;} // 继续比较后续字符
else { i = i – j + 2 ; j = 1 ;} // 指针后退重新开始匹配
}
if ( j> T[ 0 ]) return i - T[ 0 ] ;
else return 0 ;
} // Index 算法：4.5
在算法4.5 的函数过程中，分别利用计数指针 i 和j 指示主串S和模式串T中当前正待比较的字符位置。
算法的基本思想是：从主串S 的第pos个字符起和模式的第一个字符比较之，若相等，则继续逐个比较后续字
符，否则从主串的下一个字符起再重新和模式的字符比较之。依次类推，直至模式T中的每个字符依次个主串
S中的一个连续的字符序列相等，则称匹配成功，函数值为和模式T中第一个字符相等的字符在主串S中的序
号，否则称匹配不成功，函数值为零。在有些情况下，该算法的效率很低。例如: 当模式串为‘00000001 ’，
而主串为:
‘0000000000000000000000000000000000000000000000000001’时。一般情况下，此算法的时间复杂度为
O(n+m)，最坏情况下的时间复杂度为O(n*m) 。
39淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
4.3.2 模式匹配的另一种改进算法
这种改进算法是D.E.Knuth与V.R.Pratt 和J.H.Morris同时发现的，因此人们称它为克努特—莫里斯—
普拉特操作（简称为KMP算法）。此算法可以在O（n+m）的时间数量级上完成串的模式匹配操作。其改进在于：
每当一趟匹配过程中出现字符比较不相等时，不需回溯 i 的指针，而是利用已经得到的“部分匹配”的结果将
模式向右“滑动”尽可能远的一段距离后，继续进行比较。下面先从具体的例子看起。
讨论一般情况。假设主串为‘s1s2……sn’，模式串为‘p1p1…pm’从上例的分析可知，为了实现改进算
法，需要解决下述问题：当匹配过程中产生“分配”（即si!=jm）时，模式串“向右滑动”可行的距离多远，
换句话说，当主串中第 i 个字符与模式中第j个字符“失配”（即比较不等）时，主串中第i 个字符（i 指
针不回溯）应与模式中哪个字符再比较？
假设此时应与模式中第k（k k 满足下列关系式（4-2）
‘P1P1…Pk-1 ’= ‘ Si-k+1Si-k+2……………Si-1’ (4-2)
而已经得到的“部分匹配”的结果是
‘Pj-k+1Pj-k+2…Pj-1 ’= ‘Si-k+1Si-k+2…Si-1 ’ (4-3)
由（4-2）和（4-3）推得下列等式
‘P1p2…Pk-1 ’ = ‘Pj-k+1Pj-k+2…Pj-1 ’ (4-4)
反之，若模式串中存在满足式（4-4）的两个子串，则当匹配过程中，主串中第i个字符与模式中第j个字
符比较不等时，仅需将模式向右滑动至模式中第k个字符和主串中第i个西服对齐，因此，模式中头k-1个字
符的子串‘P1P2…Pk-1’必定与主串中第i个字符之前长度为k-1的子串‘Si-k+1Si-k+2…Si-1’相等，由此，
匹配仅需从模式中第k个字符与主串中第i个字符比较起继续进行。
若令next[j]=k，则next[j]表明当模式中第j个字符与主串中相应字符“失配”时，在模式中需重新和
主串中该字符进行比较的字符的位置。由此可引出模式串的next函数的定义：
由此定义可推出下列模式串的next函数值：
在求得模式的next函数之后，匹配可如下进行：假设以指针i和j分别指示主串和模式中正待比较的字符，
令i的初值为pos,j的初值为1。若在匹配过程中Si=Pj,则i和j分别增1，否则，i不变，而j退到next[j]
的位置再进行比较，若相等，则指针各自增1，否则j再退到下一个next值的位置，依次类推，直至下列两种
可能：
一种可能是j退到某个next值（next[next[…next[j]]]）时字符比较相等，则指针各自增1继续进行匹
配；；另一种是j退到值为零（即模式的第一个字符“失配”），则此时需将模式继续向右滑动一个位置，即从
主串的下一个字符Si+1起和模式重新开始匹配。
KMP算法在形式上个算法极为相似。不同之处仅在于：当匹配过程中产生“失配”时，指针i不变，指针j
需同时增1。即若主串的第i个字符和模式的第1个字符不等，应从主串的第i+1个字符起重新进行匹配。
int Index_KMP (SString S, SString T, int pos )
{ // 利用模式串 T 的 next 函数求 T 在主串 S 中第 pos 个字符之后的位置的 KMP 算法。其中：T 非空，
1<=pos<=StrLength(S)。
i = pos ; j = 1 ;
40淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
while ( i < = S [ 0 ] && j < = T[ 0 ] )
{ if (j==0 || S[i]= = T[j]) { ++ i ; ++ j ; n }
// 继续比较后续字符
else j = next [ j ] ; // 模式串向右移动
}
if ( j > T[ 0 ] ) return i – T [ 0 ] ; // 匹配成功
else return 0 ;
} // Index_KMP 算法：4.6
仿照KMP算法，可得到求next函数值的算法。
void get_next ( SString T , int & next[ ] )
{ // 求模式串T的next函数值并存入数组next。
i = 1 ; next [ 1 ] = 0 ; j = 0 ;
while ( i < T [ 0 ] )
{ if (j==0 ||T[i]==T[j]) {++ i ; ++ j ; next[i] = j ; }
else j = next[j] ;
}//while
} // get_next
算法：4.7
最后，要说明两点：
1）虽然算法4.5的时间复杂O(n*m)，但在一般情况下，其实际的执行时间近似于O(n+m)，因此至今仍被
采用。KMP算法仅当模式与主串之间存在许多“部分匹配”的情况下才显得比算法4.5快的多。但是KMP算法
的最大特点是指示主串的指针不需回溯，整个匹配过程中，对主串仅需从头至尾扫描一遍，这对处理从外设输
入的庞大文件很有效，可以边读入边匹配，而无需回头重读。
2） 前面定义的next函数在某些情况下尚有缺陷。例如模式’aaaab’在和主串‘aaabaaaab’匹配时，
当i= 4 , j = 4时s.ch[4]!=t.ch[4]，由next[j]的指示还需进行i=4、j=3、i=4、j=2、i=4、j=1等三次比
较。实际上，因为模式中第1、2、3个字符和第4个字符都相等，因此不需要再和主串中第4个字符相比较，
而可以将模式一气向右滑动4个字符的位置直接进行i=5，j=1时的字符比较。这就是说，若按上述定义得到
next[j]= k，而模式中 Pj = Pk，则当主串中字符Si和Pj比较不相等时，不需要再和Pk进行比较，而直接和
Pnext[k]进行比较，换句话说，此时的next[j]应和next[k]相同。由此可得计算next函数修正值的算法如算
法4.8所示。此时匹配算法不变。
void get_nextval (SString T , int & nextval [ ] )
{ // 求模式串T的next函数修正值并存入数组nextval 。
i= 1 ; nextval[ 1 ] = 10 ; j= 0 ;
while ( i< T[0] )
{
if ( j= = 0 || T[i] = = T[j] )
{
++i ; ++j ;
if ( T[i] != T[j]) nextval[i] = j ;
else j = nextval[i] = nextval[j] ;
}
else j = mextval [j] ;
}
} // get_nextval 算法：4.8
4.4 串的应用举例：文本编辑
41淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
文本编辑程序是一个面向用户的系统服务程序，广泛应用于原程序、原程序的输入和修改，甚至用于报刊
和书籍的编辑排版以及办公室的公文书信的起草和润色。文本编辑的实质是修改字符书记的形式或格式。虽然
各种文本编辑程序的功能强弱不同，但是其基本操作是一致的，一般都包括串的查找，插入和删除等基本操作。
为了编辑方便，可以用分页符和换行符将文本分为若干页，每页有若干行。我们把文本当作一个字符串，称为
文本串，页是文本串的子串，行是页的子串。
我们采用堆存储结构来存储文本，同时设立页指针、行指针和字符指针，分别指向当前操作的页、行和字
符，同时建立页表和行表存储每一页、每一行的起始位置和长度。 假设有如下源程序：
main ( )
{ float a,b,max ;
scanf (“%f , %f , &a , &b”) ;
if a > b max = a ;
else max = b ;
}
文本编辑程序中设立页指针、行指针和字符指针，分别指示当前财政的页、行和字符。如果在某行内插入
或删除若干字符，则要为该行重新分配存储空间，同时还要修改该行的起始位置。如分配给它的存储空间，则
要为该行重新分配存储空间，同时还要修改行的起始位置。
如果要插入或删除一行，就要涉及行表的插入或删除。若被删除的行是所在页的起始行，则还要修改页表
中相应页的起始行号（修改为下一行的行号）。为了查找方便，行表是按行号递增顺序存储的，因此，对行表进
行的插入或删除运算需移动操作位置以后的全部表项。
页表的维护与行表类似，在此不再赘述。由于访问是以页表和行表作为索引的，所以在作行个页的删除操
作时，可以只对行表和页表作相应的修改，不必删除所设计的字符。这可以节省不少时间。
作业2：
1：P73：串的链接操作；图4.1；
2：算法4.5：串的模式匹配算法、图4.3；
本章教学总结：
42淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
第五章：数组和广义表
课程：数据结构
课题：第五章 5.1—5.6小节（共4个课次）
5.1 数组的定义
5.2 数组的顺序表现和实现
5.3 矩阵的压缩存储
5.4 广义表的定义
5.5 广义表的储存结构
5.6m元多项式的表示
目的要求：领会数组的定义，数组的两种顺序存储结构，并领会几种特殊矩阵和稀疏矩阵的压缩存储方法，了
解广义表的概念和存储结构。
新课重点、难点：
教学方法：课堂讲解、例题演示，课件演示
教学内容及过程：
……………………………第1-2课时……………………………
5.1 数组的定义
数组和广义表可看成是一种特殊的线性表，其特殊在于，表中的数据元素本身也是一种线性表。
数组是我们最熟悉的数据类型，在早期的高级语言中，数组是唯一可供使用的数据类型。由于数组中各元
素具有统一的类型，并且数组元素的下标一般具有固定的上界和下界，因此，数组的处理比其它复杂的结构更
为简单。多维数组是向量的推广。例如，二维数组：可以看成是由个行向量组成的向量，也可以看成是个列向
量组成的向量。
在C语言中，一个二维数组类型可以定义为其分量类型为一维数组类型的一维数组类型，也就是说，
typedef elemtype array2[m][n]; 等价于：
typedef elemtype array1[n];
typedef array1 array2[m];
同理，一个维数组类型可以定义为其数据元素为维数组类型的一维序组类型。数组一旦被定义，它的维数
和维界就不再改变。因此，除了结构的初始化和销毁之外，数组只有存取元素和修改元素值的操作。
43淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图 矩阵Am×n看成n个列向量的线性表
图 矩阵Am×n看成m个行向量的线性表
以上我们以二维数组为例介绍了数组的结构特性，实际上数组是一组有固定个数的元素的集合。也就是说，
一旦定义了数组的维数和每一维的上下限，数组中元素的个数就固定了。 例如二维数组A3×4，它有3行、4
列，即由12个元素组成。由于这个性质，使得对数组的操作不像对线性表的操作那样可以在表中任意一个合法
的位置插入或删除一个元素。对于数组的操作一般只有两类：
(1） 获得特定位置的元素值；
(2） 修改特定位置的元素值。
基本操作：
（1） InitArray(&A, n, bound1, …, boundn)： 若维数n和各维的长度合法，则构造相应的数组A，并
返回TRUE。
（2） DestroyArray（&A）： 销毁数组A。
（3） Value（A，&e,index1, …,indexn）： 若下标合法，则用e返回数组A中由index1, …,indexn
所指定的元素的值。
（4） Assign(&A,e,indexl,…indexn)：若各下标不超界，则将e赋值为所指定的A的元素值，并返回OK。
n维数组中每个元素都受着n个关系的约束，在每个关系中，元素aj1j2…jn(0≤ji≤bi-2)都有一个直接
后继元素。因此，就其单个关系而言，这n个关系仍是线性关系。所有数据元素必须属于同一数据类型。
数组的每个元素都对应于一组下标（j1,j2,…jn）,其中每个下标的取值范围是0≤ji≤bi-1,bi称为第i
维的长度。当n=1时，n维数组就退化为定长的线性表。由此，n维数组是线性表的扩广。
5.2 数组的顺序表示和实现
数组一般不做插入和删除操作，因此采用顺序存储结构。由于存储单元是一维结构，而数组是多维结构，
则用一组连续存储单元存放数组的数据元素就有个次序约定问题。
44淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
数组的顺序存储结构有两种：一种是按行序存储，如高级语言BASIC、 C和PASCAL语言都是以行序为主；
另一种是按列序存储，如高级语言中的FORTRAN语言就是以列序为主显然，二维数组Am×n以行为主的存储序
列为：
a11, a12, …，a1n, a21, a22, …, a2n, …, am1, am2, …, amn
而以列为主的存储序列为：
a11, a21, …，am1，a12, a22, …, am2, …, a1n, a2n, …, amn
假设有一个3×4×2的三维数组A ，共有24个元素，其逻辑结构如图所示。
三维数组元素的标号由三个数字表示，即行、列、纵三个方向。a142表示第1行，第4列，第2纵的元素。
如果对A3×4×2 （下标从1开始）采用以行为主序的方法存放，即行下标变化最慢，纵下标变化最快，则顺
序为：
a111，a112，a121，a122， …，a331，a332，a341，a342
采用以纵为主序的方法存放，即纵下标变化最慢，行下标变化最快，则顺序为：a111，a211，a311，a121，
a221，a321，…，a132，a232，a332，a142，a242，a342
以上的存放规则可推广到多维数组的情况。总之，知道了多维数组的维数，以及每维的上下界，就可以方
便地将多维数组按顺序存储结构存放在计算机中了。同时，根据数组的下标，可以计算出其在存储器中的位置。
因此，数组的顺序存储是一种随机存取的结构。
以二维数组Am×n为例，假设每个元素只占一个存储单元，“以行为主”存放数组，下标从1开始，首元
素a11的地址为Loc［1, 1］，求任意元素aij的地址。aij是排在第i行，第j列，并且前面的第i-1行有n
×（i-1）个元素，第ｉ行第j个元素前面还有ｊ-１个元素。由此得到如下地址计算公式：
Loc［i, j］=Loc［1, 1］+n×(i-1)+(j-1)
根据计算公式，可以方便地求得aij的地址是Loc［i,j］。如果每个元素占size个存储单元，则任意元素aij
的地址计算公式为：
Loc［i, j］=Loc［1, 1］ + (n×(i-1)+j-1)×size
三维数组A（1..r , 1..m , 1..n）可以看成是r个m×n的二维数组， 如图所示。
假定每个元素占一个存储单元，采用以行为主序的方法存放，即行下标r变化最慢， 纵下标n变化最快。
首元素a111的地址为Loc［1, 1, 1］，求任意元素aijk的地址。
显然，ai11的地址为Loc［i, 1, 1］=Loc［1, 1, 1］+(i-1)×m×n， 因为在该元素之前， 有ｉ-１个ｍ
×ｎ的二维数组。由ai11的地址和二维数组的地址计算公式，不难得到三维数组任意元素aijk的地址：
Loc［i, j, k］=Loc［1, 1, 1］+(i-1)×m×n+(j-1)×n+(k-1)
其中1≤i≤ｒ，1≤j≤ｍ， 1≤k≤ｎ。
对于ｎ维数组A(c1∶d1, c2∶d2，…, cn∶dn)，我们只要把上式推广，就可以容易地得到ｎ维数组中任
45淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
意 元 素 aj1j2…jn 的 存 储 地 址 的 计 算 公 式 :
LOC(aj1j2…jn)=LOC(a00…0)+(b2*b3*…*bn*j1+b3*…*bn*j2+…+bn*jn-1+jn)*l
LOC(aj1j2…jn)= LOC(a00…0)+(
= LOC(a00…0)+
其中 cn=L,ci-1=bi*ci
下面是数组的顺序存储表示实现：
//------数组的顺序存储表示―――――
#include
#define MAX_ARRAY_DIM 8
typedef struct
{ ELemType *base;
Int dim;
Int *bounds;
Int *constants;
}Array;
//--------基本操作的函数原型说明――――――
Status InitArray(Array,ElemType &e,…)；
//若维数dim和随后的各维长度合法，则构造相应的数组A，并返回ok;
Status DestroyArray(Array &A);
//销毁数组A
Status Value(Array A,Elemtype &e,…);
//A是n维数组，e为元素变量，随后是n个下标值。
//若下标不超界，则e的赋值为所指定的A的元素值，并返回ok;
Status Assign(Array &A,int dim,…);
//A是n维数组，e为元素变量，随后是n个下标值。
//若下标不超界，则将e的值赋给所指定的A的元素值，并返回ok
5.3 矩阵的压缩存储
压缩存储：为多个值相同的元素只分配一个存储空间，对零元素不分配空间。特殊矩阵：值相同的元素或
零元素在矩阵中的分布有一定的规律。稀疏矩阵：矩阵中元素分布没有规律，但零元素较多。
5.3.1 特殊矩阵
三角矩阵大体分为三类：下三角矩阵、上三角矩阵和对称矩阵。对于一个n阶矩阵A来说，若当ij时，有aij=0，则称此矩阵为上三角矩阵；若矩阵中的所有元素
均满足aij=aji，则称此矩阵为对称矩阵。
对于下三角矩阵的压缩存储，我们只存储下三角的非零元素，对于零元素则不存。我们按“行序为主序”
46淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
进行存储，得到的序列是a11, a21, a22, a31, a32, a33, …, an1, an2, …, ann。由于下三角矩阵的元素
个数为n(n+1)/2，所以可压缩存储到一个大小为n(n+1)/2的一维数组C中，如图所示。
下三角矩阵中元素aij(i>j)在一维数组A中的位置为：Loc［i,j］=Loc［1,1］+前i-1行非零元素个数+第i
行中aij前非零元素个数前i-1行元素个数=1+2+3+4+…+（i-1）=i(i-1)/2，第i行中aij前非零元素个数=j-1，
所以有：
Loc［i, j］=Loc［1, 1］+i(i-1)/2+j-1
同样，对于上三角矩阵，也可以将其压缩存储到一个大小为n(n+1)/2的一维数组C中。其中元素aij(i|1<=i<=n-1}
Col={< aij, ai+1j >|1<=j<=n}
基本操作：
CreateSMatix(&M)
操作结果：创建稀疏矩阵M。
DestroySMatrix(&M)；
初始条件：稀疏矩阵M存在。
操作结果：销毁稀疏矩阵M。
PrintSMatrix(M)
初始条件：稀疏矩阵M存在。
操作结果：输出稀疏矩阵M。
CopySMatrix(M,&T)
初始条件：稀疏矩阵M存在。
操作结果：由稀疏矩阵M复制得到T。
AddSMatrix(M,N,&Q)
初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵的和Q＝M+N。
SubtMatix(M,N,&Q)
初始条件：稀疏矩阵M与N的行数和列数对应相等。
操作结果：求稀疏矩阵差Q＝M-N
MultSMatix(M,N,&Q)
初始条件：稀疏矩阵M的行数和列数对应相等。
操作结果：求稀疏矩阵乘积Q＝M×N
TransposeSMatix(M,&T)
初始条件：稀疏矩阵M存在。
操作结果：求稀疏矩阵M的转置矩阵T。
}ADT SparseMatrix
1: 稀疏矩阵的三元组表表示法
稀疏矩阵的压缩存储：只存储非零元。记录值、行、列位置，即一个三元组（i，j，aij）。用三元组表作
为稀疏矩阵的存储结构。
48淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图 稀疏矩阵的三元组表表示
稀疏矩阵的三元组表表示法虽然节约了存储空间，但比起矩阵正常的存储方式来讲，其实现相同操作要耗
费较多的时间，同时也增加了算法的难度, 即以耗费更多时间为代价来换取空间的节省。三元组表的类型说明
如下：
# define MAXSIZE 12500
typedef struct{
int i, j ;
ElemType e ;
}Triple ;
typedef union{
Triple data[ MAXSIZE+1 ] ;
Int mu, nu, tu ;
}TSMatrix ;
1) 用三元组表实现稀疏矩阵的转置运算
下面首先以稀疏矩阵的转置运算为例，介绍采用三元组表时的实现方法。所谓的矩阵转置，是指变换元素
的位置，把位于（row，col）位置上的元素换到（col，row）位置上，也就是说， 把元素的行列互换。如图所
示的6×7矩阵M，它的转置矩阵就是7×6的矩阵N，并且N（row，col）=M（col， row），其中，1≤row≤7 ，
1≤col≤6。
采用矩阵的正常存储方式时， 实现矩阵转置的经典算法如下：
void TransMatrix（ElementType source［n］［m］, ElementType dest［m］［n］） {/*source和dest分
别为被转置的矩阵和转置以后的矩阵（用二维数组表示）*/
int i, j;
for(i=0; i0时， 该集合满足如下条件：
(1) 其中必有一个称为根（root）的特定结点，它没有直接前驱，但有零个或多个直接后继。
(2) 其余n-1个结点可以划分成m（m≥0）个互不相交的有限集T1，T2，T3，…，Tm，其中Ti又是一棵树，
称为根root的子树。 每棵子树的根结点有且仅有一个直接前驱，但有零个或多个直接后继。
图6.1 树的图示方法
54淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
ADT Tree
数据对象D：一个集合，该集合中的所有元素具有相同的特性。
数据关系R： 若D为空集，则为空树。 若D中仅含有一个数据元素，则R为空集，否则R={H}，H是如下
的二元关系：
(1) 在D中存在唯一的称为根的数据元素root， 它在关系H下没有前驱。
(2)若D-{ root }≠ф，则存在D-{ root }的一个划分D1，D2…Dm ( m>0 ) 对任意j≠k ( 1≤j, k≤m )
有Dj∩Dk=ф,且对任意的i( 1≤i≤m ) 唯一存在数据元素 xi﹥∈H.
(3)对应于D-{ root }的划分，H-{ ,…< root,xm> }有唯一的一个划分H1，H2，…,Hm ( m>0 ),
对任意j≠k ( 1≤j, k≤m )有Hj∩Hk=ф,且对任意i(1≤i≤m ) ,H1是Di上的二元关系，（ Di, { Hi } ）
是一棵符合本定义的树，成为根root的子树。}
树的基本术语
· 结点：包含一个数据元素及若干指向其它结点的分支信息。
· 结点的度：一个结点的子树个数称为此结点的度。
· 叶子结点：度为0的结点，即无后继的结点，也称为终端结点。
· 分支结点：度不为0的结点，也称为非终端结点。
· 孩子结点：一个结点的直接后继称为该结点的孩子结点。在图6.1中， B、C是A的孩子。
· 双亲结点：一个结点的直接前驱称为该结点的双亲结点。在图6.1中，A 是B、C的双亲。
· 兄弟结点：同一双亲结点的孩子结点之间互称兄弟结点。在图6.1中，结点H、I、 J互为兄弟结点。
·堂兄弟：双亲在同一层的结点互为堂兄弟。
·祖先结点：一个结点的祖先结点是指从根结点到该结点的路径上的所有结点。在图6.1中，结点K的祖先
是A、B、E。
·子孙结点：以某结点为根的子树中的任一结点都称为该结点的子孙 。在图6.1中，结点D的子孙是H、I、
J、 M。
·结点的层次：从根结点开始定义，根结点的层次为1，根的直接后继的层次为2，依此类推。
·树的度： 树中所有结点的度的最大值。
·树的高度（深度）： 树中所有结点的层次的最大值。
·有序树：在树T中，如果各子树Ti之间是有先后次序的，则称为有序树。 否则称为无序树 。
·森林： m（m≥0）棵互不相交的树的集合。将一棵非空树的根结点删去，树就变成一个森林；反之，给森
林增加一个统一的根结点，森林就变成一棵树。
6.2 二叉树的定义
6.2.1 二叉树的定义
定义：我们把满足以下两个条件的树形结构叫做二叉树（Binary Tree）：
（1） 每个结点至多只有二棵子树（即度都不大于2）；
（2）二叉树的子树有左右之分，其次序不能任意颠倒。
由此定义可以看出，一个二叉树中的每个结点只能含有0、 1或2个孩子，而且每个孩子有左右之分。我
们把位于左边的孩子叫做左孩子，位于右边的孩子叫做右孩子。
图6.3 给出了二叉树的五种基本形态。
55淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
与树的基本操作类似，二叉树有如下基本操作：
(1) InitBiTree（&T）;
操作结果：构造空二叉树。
(2) DestoryBitree（&T）;
初始条件：二叉树T存在。
操作结果：销毁二叉树T。
(3) GreateBiTree（&T,definition）;
初始条件：definition给出二叉树T的定义。
操作结果：按definition构造二叉树T。
(4) ClearBiTree（&T）;
初始条件：二叉树T存在。
操作结果：将二叉树T清为空树。
(5) BiTreeEmpty（T）;
初始条件：二叉树T存在。
操作结果：若T为空二叉树，则返回TRUE，否则FLASE。
(6) BiTreeDepth（T）;
初始条件：二叉树T存在。
操作结果：返回T的深度。
(7) Root（T）；
初始条件：二叉树T存在。
操作结果：返回T的根。
(8) Value(T,e);
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e的值。
(9) Assign（T，&e,value）;
初始条件：二叉树T存在，e是T中某个结点。
操作结果：结点e赋值为value。
(10) Parent（T，e）；
初始条件：二叉树T存在，e是T中某个结点。
操作节点：返回e的右孩子。若e无左孩子，则返回“空”；
(11) LeftChild（T，e）;
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e的左孩子。若e无左孩子，则返回“空”。
(12) RightChild（T，e）;
初始条件：二叉树T存在，e是T中某个结点。
操作结果：返回e 的右孩子。
6.2.2 二叉树的性质
性质1: 在二叉树的第i层上至多有2i-1个结点(i≥1)。
证明： 用数学归纳法。
归纳基础：当i=1时，整个二叉树只有一根结点，此时
2i-1=20=1，结论成立。
归纳假设：假设i=k时结论成立，即第k层上结点总数最多为2k-1个。 现证明当i=k+1时， 结论成
立：
因为二叉树中每个结点的度最大为2，则第k+1层的结点总数最多为第k层上结点最大数的2倍，即2×
2k-1=2(k+1)-1，故结论成立。
56淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
性质2: 深度为k的二叉树至多有2k-1个结点（k≥1）。
证明：因为深度为k的二叉树，其结点总数的最大值是将二叉树每层上结点的最大值相加，所以深度为k
的二叉树的结点总数至多为
故结论成立。
性质3: 对任意一棵二叉树T，若终端结点数为n0，而其度数为2的结点数为n2，则n0=n2+1 。
证明：设二叉树中结点总数为n， n 1为二叉树中度为1的结点总数。 因为二叉树中所有结点的
度小于等于2，所以有 n=n0+n1+n2
设二叉树中分支数目为B， 因为除根结点外， 每个结点均对应一个进入它的分支，所以有：n=B+1。又因
为二叉树中的分支都是由度为1和度为2的结点发出， 所以分支数目为：B=n1+2n2。整理上述两式可得到：
n=B+1=n1+2n2+1
将n=n0+n1+n2代入上式，得出n0+n1+n2=n1+2n2+1，整理后得n0=n2+1，故结论成立。
满二叉树：
深度为k且有2k-1个结点的二叉树。在满二叉树中，每层结点都是满的，即每层结点都具有最大结点数。
图6.3(a)所示的二叉树，即为一棵满二叉树。满二叉树的顺序表示，即从二叉树的根开始，层间从上到下，层
内从左到右，逐层进行编号（1， 2， …， n）。例如图6.3(a)所示的满二叉树的顺序表示为(1， 2， 3， 4，
5， 6， 7， 8， 9， 10， 11， 12， 13， 14， 15)。
完全二叉树：
深度为k，结点数为n的二叉树，如果其结点1~n的位置序号分别与满二叉树的结点1~n的位置序号一一
对应，则为完全二叉树， 如图6.3(b)所示。
满二叉树必为完全二叉树， 而完全二叉树不一定是满二叉树。
完全二叉树的特点：
⑴叶子只能在层次最大的两层上出现；
⑵对任意一个结点，右分支下的子孙的最大层次为L，则左分支为L或L+1 。
图6.3 满二叉树与完全二叉树
性质4：具有n个结点的完全二叉树的深度为［log2n］+1。
证明：假设n个结点的完全二叉树的深度为k，根据性质2可知，k-1层满二叉树的结点总数为：n1=2k-1-1；
k层满二叉树的结点总数为： n2=2k-1。显然有n11， 则序号为i的结点的双亲结点序号
为［i/2］。
（2） 如2×i>n，则序号为i的结点无左孩子；如2×i≤n，则序号为i的结点的左孩子结点的序号为2
×i。
57淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
（3） 如2×i＋1>n，则序号为i的结点无右孩子；如2×i＋1≤n， 则序号为i的结点的右孩子结点的序
号为2×i＋1。
可以用归纳法证明其中的（2）和（3）：
当i=1时，由完全二叉树的定义知，如果2×i=2≤n，说明二叉树中存在两个或两个以上的结点，所以其
左孩子存在且序号为2； 反之，如果2>n，说明二叉树中不存在序号为2的结点，其左孩子不存在。同理，如
果2×i+1=3≤n， 说明其右孩子存在且序号为3；如果3>n，则二叉树中不存在序号为3的结点， 其右孩子不
存在。
假设对于序号为j(1≤j≤i)的结点，当2×j≤n时，其左孩子存在且序号为2×j，当2×j>n 时，其左
孩子不存在；当2×j+1≤n时， 其右孩子存在且序号为2×j+1，当2×j+1>n时，其右孩子不存在。
当i=j+1时，根据完全二叉树的定义， 若其左孩子存在， 则其左孩子结点的序号一定等于序号为j的结点的
右孩子的序号加1， 即其左孩子结点的序号等于 （2×j+1）+1=2（j+1）=2×i， 且有2×i≤n；如果2×i>n，
则左孩子不存在。 若右孩子结点存在，则其右孩子结点的序号应等于其左孩子结点的序号加1，即右孩子结点
的序号为2×i+1，且有2×i+1≤n；如果2×i+1>n，则右孩子不存在。 故（2）和（3）得证。
由（2）和（3）我们可以很容易证明（1）。
当i=1时， 显然该结点为根结点，无双亲结点。当i>1时，设序号为i的结点的双亲结点的序号为m，如
果序号为i的结点是其双亲结点的左孩子，根据（2）有i=2×m，即 m=i/2; 如果序号为i的结点是其双亲结
点的右孩子，根据（3）有i=2×m+1， 即m=（i-1）/2=i/2-1/2，综合这两种情况，可以得到，当i>1时， 其
双亲结点的序号等于［i/2］。证毕。
6.2.3 二叉树的存储结构
二叉树的结构是非线性的， 每一结点最多可有两个后继。 二叉树的存储结构有两种：
顺序存储结构和链式存储结构。
1： 顺序存储结构
用一组地址连续的存储单元，依次自上而下，自左至右存储完全二叉树上的结点元素，即将完全二叉树上
编号为i 的结点元素存储在数组的第i –1个分量中。
图6.4 二叉树与顺序存储结构
图6.5 单支二叉树与其顺序存储结构
作业1：
1：图6.3二叉树的基本形态；
2：二叉树的五个性质；
……………………………第3-4课时……………………………
58淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
2. 链式存储结构
对于任意的二叉树来说，每个结点只有两个孩子，一个双亲结点。我们可以设计每个结点至少包括三个域：
数据域、 左孩子域和右孩子：
其中，LChild域指向该结点的左孩子，Data域记录该结点的信息，RChild域指向该结点的右孩子。 用C
语言这样声明二叉树的二叉链表结点的结构：
typedef struct BiTNode
{ TElemType data;
struct BiTNode *LChild;
struct BiTNode *RChild;
}BiTNode, *BiTree;
有时，为了便于找到父结点，可以增加一个Parent域， Parent域指向该结点的父结点。 该结点结构如
下：
图6.6 二叉树和二叉链表
若一个二叉树含有n个结点，则它的二叉链表中必含有2n个指针域， 其中必有n＋1个空的链域。此结论
证明如下：
证明：分支数目B=n-1，即非空的链域有n-1个，故空链域有2n-(n-1)=n+1个。
不同的存储结构实现二叉树的操作也不同。如要找某个结点的父结点，在三叉链表中很容易实现；在二叉
链表中则需从根指针出发一一查找。可见，在具体应用中，需要根据二叉树的形态和需要进行的操作来决定二
叉树的存储结构。
6.3 二叉树的遍历与线索化
6.3.1 二叉树的遍历
图6.7 二叉树结点的基本结构
遍历二叉树：按某种搜索路径，使二叉树每个结点均被访问一次，且仅被访问一次。访问的含义很广。遍
59淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
历需寻找某中规律，使二叉树的结点能排列在一个线形队列上 。
我们用L、D、R分别表示遍历左子树、访问根结点、 遍历右子树， 那么对二叉树的遍历顺序就可以有六
种方式：
(1) 访问根，遍历左子树，遍历右子树（记做DLR）。
(2) 访问根，遍历右子树，遍历左子树（记做DRL）。
(3) 遍历左子树，访问根，遍历右子树（记做LDR）。
(4) 遍历左子树，遍历右子树，访问根（记做LRD）。
(5) 遍历右子树，访问根，遍历左子树（记做RDL）。
(6) 遍历右子树，遍历左子树，访问根（记做RLD）。
注意：先序、中序、后序遍历是递归定义的， 即在其子树中亦按上述规律进行遍历。
下面就分别介绍三种遍历方法的递归定义。
· 先序遍历（DLR）操作过程：
若二叉树为空， 则空操作， 否则依次执行如下3个操作：
(1) 访问根结点；
(2) 按先序遍历左子树；
(3) 按先序遍历右子树。
· 中序遍历（LDR）操作过程：
若二叉树为空， 则空操作， 否则依次执行如下3个操作：
(1) 按中序遍历左子树；
(2) 访问根结点；
(3) 按中序遍历右子树。
· 后序遍历（LRD）操作过程：
若二叉树为空， 则空操作， 否则依次执行如下3个操作：
(1) 按后序遍历左子树；
(2) 按后序遍历右子树；
(3) 访问根结点。
对于如图6.8所示的二叉树， 其先序、 中序、 后序遍历的序列如下：
先序遍历： A、 B、 D、 F、 G、 C、 E、 H 。
中序遍历： B、 F、 D、 G、 A、 C、 E、 H 。
后序遍历： F、 G、 D、 B、 H、 E、 C、 A 。
最早提出遍历问题是对存储在计算机中的表达式求值。例如：（a+b*c）-d/e。该表达式用二叉树表示如图
6.9所示。当我们对此二叉树进行先序、中序、后序遍历时，便可获得表达式的前缀、 中缀、 后缀书写形式：
前缀： -+a*bc/de
中缀： a+b*c-d/e
后缀： abc*+de/-
其中中缀形式是算术表达式的通常形式，只是没有括号。 前缀表达式称为波兰表达式。算术表达式的后缀
表达式被称作逆波兰表达式。 在计算机内， 使用后缀表达式易于求值。
60淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图6.9 算术式的二叉树表示
1） 先序遍历
PreOrderTraverse(Bitree T,Status(* Visit) (TelemType e))
{ if ( T )
{ if ( Visit ( T->data ) )
if ( PreOrderTraverse ( T->lchild , Visit ) )
if ( PreOrderTraverse ( T->rchild, Visit ) )
return OK;
return ERROR;
} else return OK;
}
图6.10 中序遍历二叉树的递归过程
基于栈的递归消除：依栈的状态变化，可直接写出相应的非递归算法，栈元素包含两项，递归调用语句编
号（返回地址），指向根结点的指针。若栈顶记录中指针值为空，则应退至上一层，若从左子树返回，应退到指
针所指的根。若是从右子树返回，表明本层的遍历结束，应继续退栈。
Status InOrderTraverse( BiTree T, Status ( * Visit ) ( TelemType e ) )
{ InitStack ( S ); Push ( S, T );
while( !StackEmpty ( S ) )
{ while ( GetTop ( S, p ) && p)
Push ( S, p->lchild );
Pop ( S, p );
if ( !StackEmpty ( S ) )
{ Pop(S, p); if (!Visit(p->data)) return ERROR;
Push ( S, p->rchild );
}// if
}// While
return OK;
}// InOrderTraverse
Status InOrderTraverse ( BiTree T, Status ( *Visit ) ( TelemType e ) )
61淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
{ InitStack ( S ); p=T;
While ( p || !StackEmpty ( S )
{ if ( p ) { Push ( S, p ); p=p->lchild; }
else
{ Pop ( S, p ); if ( !Visit ( p->data ) ) return ERROR;
p=p->rchild; }
} return OK;
}
遍历算法应用
1. 输出二叉树中的结点
遍历算法将走遍二叉树中的每一个结点，故输出二叉树中的结点并无次序要求，因此可用三种遍历中的任
何一种算法完成。
2. 输出二叉树中的叶子结点
输出二叉树中的叶子结点与输出二叉树中的结点相比，它是一个有条件的输出问题，即在遍历过程中走到
每一个结点时需进行测试，看是否有满足叶子结点的条件。
4. 建立二叉链表方式存储的二叉树
给定一棵二叉树，我们可以得到它的遍历序列；反过来，给定一棵二叉树的遍历序列，我们也可以创建相
应的二叉链表。 这里所说的遍历序列是一种“扩展的遍历序列”。在通常的遍历序列中，均忽略空子树，而在
扩展的遍历序列中，必须用特定的元素表示空子树。
A B C Φ Φ D E Φ G Φ Φ F Φ Φ Φ
其中用Φ表示空子树。
6.3.2 线索二叉树
1. 基本概念
二叉树的遍历运算是将二叉树中结点按一定规律线性化的过程。 当以二叉链表作为存储结构时，只能找
到结点的左、右孩子信息， 而不能直接得到结点在遍历序列中的前驱和后继信息。 要得到这些信息可采用以
下两种方法：第一种方法是将二叉树遍历一遍，在遍历过程中便可得到结点的前驱和后继，但这种动态访问浪
费时间；第二种方法是充分利用二叉链表中的空链域， 将遍历过程中结点的前驱、 后继信息保存下来。
我们知道，在有n个结点的二叉链表中共有2n个链域，但只有n-1个有用的非空链域，其余n+1个链域是
空的。我们可以利用剩下的n+1个空链域来存放遍历过程中结点的前驱和后继信息。 现作如下规定：若结点有
左子树，则其LChild域指向其左孩子，否则LChild域指向其前驱结点；若结点有右子树，则其RChild域指向
其右孩子，否则RChild域指向其后继结点。为了区分孩子结点和前驱、后继结点，为结点结构增设两个标志域，
如下所示：
在这种存储结构中，指向前驱和后继结点的指针叫做线索。以这种结构组成的二叉链表作为二叉树的存储
62淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
结构，叫做线索链表。对二叉树以某种次序进行遍历并且加上线索的过程叫做线索化。线索化了的二叉树称为
线索二叉树。
3. 在线索二叉树中找前驱、 后继结点
1）对中序线索树：
找后继 若 rtag=1 则rchild指示后继
若 rtag=0 右子树的最左下结点
找前驱 若 ltag=1 则lchild指示前驱
若 ltag=0 左子树最右下结点为前驱
对后序线索树，找后继，分3种情况
① 若结点x是二叉树的根，则后继为空；
② 若x是双亲的右孩子或是双亲的左孩子且双亲没有右子树，则后继为双亲；
③ 若x是双亲的左孩子，且双亲有右子树，则后继为双亲右子树，第一个遍历的结点。
可见，在后序线索化树上找后继时需知道双亲，即需带标志域的三叉链表作为存储结构。
在中序线索二叉树上遍历二叉树，虽时间复杂度也为O（n ）但常数因子比前面讨论的算法小，且不需要
设栈，若经常找前驱，后继，应采用线索链表做为存储结构。
为方便起见，在二叉链表上添加一个头结点，并令lchild指向二叉树的根rchild指向最后访问的结点。
同样，第一个访问结点的lchild和最后访问结点的rchild指向头结点，双向线索链表。
作业2：
1：对一些特殊样式的二叉树进行顺序存储；
2：对二叉树进行三种遍历操作；
……………………………第5-6课时……………………………
6.4 树和森林
6.4.1 树的存储结构
树的主要存储方法有以下三种：
1. 双亲表示法
这种方法用一组连续的空间来存储树中的结点，在保存每个结点的同时附设一个指示器来指示其双亲结点
63淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
在表中的位置， 其结点的结构如下：
图6.18 树的双亲表示法
双亲表示法的形式说明如下：
#define MAX_TREE_SIZE 100
typedef struct PTNode {
TelemType data;
int parent;
}PTNode;
typedef struct{
PTNode nodes[ MAX_TREE_SIZE ];
int r, n;
}Ptree;
PARENT ( T, x ) 常数量时间;
反复PARENT操作可找到树的根，即ROOT（x ）;求解孩子，需遍历整个链表。
2. 孩子表示法
这种方法通常是把每个结点的孩子结点排列起来，构成一个单链表， 称为孩子链表。n个结点共有n个孩
子链表（叶子结点的孩子链表为空表），而n个结点的数据和n个孩子链表的头指针又组成一个顺序表。
这种存储结构的形式说明如下：
typedef struct CTNode {
int child;
struct CTNode *next;
}*ChildPtr;
typedef struct
{ TelemType data;
ChildPtr firstchild;
}CTBox;
typedef struct
{ CTBox nodes [ MAX_TREE_SIZE ];
int n, r;
}Ctree;
64淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图6.19 树的孩子链表表示法
3. 孩子兄弟表示法
图6.20 树的孩子兄弟表示法
孩子兄弟表示法的类型定义如下：
链表中结点的两个链域分别指向该结点的第一个孩子结点和下一个兄弟结点，分别命名为firstchild域和
nextsibling域
typedef struct CSNode {
ElemType data;
Struct CSNode *firstchild, *nextsibling;
}CSNode, *CSTree;
这种存储结构便于实现树的各种操作，例如：如果要访问结点x的第i个孩子，则只要先从FirstChild
域找到第一个孩子结点，然后沿着这个孩子结点的Nextsibling域连续走i-1步，便可找到x的第i个孩子。
如果在这种结构中为每个结点增设一个Parent域，则同样可以方便地实现查找双亲的操作。
6.4.2 森林与二叉树的转换
1. 树转换为二叉树
图6.22 树到二叉树的转换
将一棵树转换为二叉树的方法是：
(1) 树中所有相邻兄弟之间加一条连线。
(2) 对树中的每个结点，只保留其与第一个孩子结点之间的连线，删去其与其它孩子结点之间的连线。
65淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
(3) 以树的根结点为轴心，将整棵树顺时针旋转一定的角度， 使之结构层次分明。
可以证明，树做这样的转换所构成的二叉树是唯一的。图6.22给出了将图6.21所示的树转换为二叉树的
转换过程示意。
图6.23 树与二叉树的对应
2. 森林转换为二叉树
森林是若干棵树的集合。树可以转换为二叉树， 森林同样也可以转换为二叉树。因此，森林也可以方便地
用孩子兄弟链表表示。森林转换为二叉树的方法如下：
（1） 将森林中的每棵树转换成相应的二叉树。
（2） 第一棵二叉树不动，从第二棵二叉树开始，依次把后一棵二叉树的根结点作为前一棵二叉树根结点的
右孩子， 当所有二叉树连在一起后，所得到的二叉树就是由森林转换得到的二叉树。
图6.24 森林转换为二叉树的过程
如果F= { T1, T2, …, Tm } 是森林，按以下规则转换成一棵二叉树 B= ( root, LB, RB )
（1）若F为空即m=0，则B为空树
（2）若F非空，则B的根root为森林第一棵树的根ROOT（T1）B的左子树LB是从T1中各结点的子树森林
F1= { T11，T12，…，T1m1 }转换成二叉树，其右子树RB是从森林F’={ T2，T3，…，Tm }转换成二叉树。
3. 二叉树还原为树或森林
树和森林都可以转换为二叉树，二者的不同是: 树转换成的二叉树, 其根结点必然无右孩子，而森林转换
后的二叉树，其根结点有右孩子。将一棵二叉树还原为树或森林，具体方法如下：
66淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
（1） 若某结点是其双亲的左孩子，则把该结点的右孩子、 右孩子的右孩子……都与该结点的双亲结点用
线连起来。
（2） 删掉原二叉树中所有双亲结点与右孩子结点的连线。
（3） 整理由（1）、（2）两步所得到的树或森林， 使之结构层次分明。
图6.25 二叉树到森林的转换示例
同样，我们可以用递归的方法描述上述转换过程。
如果B=（ root，LB，RB ）是一棵二叉树，则可按如下规则转换成森林F= { T1, T2, …, Tm }
（1）若B为空，则F为空；
（2）若B为非空，则F中第一棵树T1的根ROOT（T1）即为二叉树B的根root；T1中根结点的子树森林F1
是由B的左子树LB转换成的森林F中除T1之外其余树组成的森林F’={T2，T3，…，Tm}是由B的右子树RB
转换成的森林。
根据这个递归的定义， 我们同样可以写出递归的转换算法。
6.4.3 树的遍历
1. 树的遍历
树的遍历方法主要有以下两种：
1） 先根遍历
若树非空，则遍历方法为：
(1) 访问根结点。
(2) 从左到右， 依次先根遍历根结点的每一棵子树。
例如， 图6.21中树的先根遍历序列为ABECFHGD。
2） 后根遍历
若树非空， 则遍历方法为：
（1） 从左到右， 依次后根遍历根结点的每一棵子树。
（2） 访问根结点。
例如， 图6.21中树的后根遍历序列为EBHFGCDA。
2. 森林的遍历
森林的遍历方法主要有以下三种：
1） 先序遍历
若森林非空， 则遍历方法为：
(1) 访问森林中第一棵树的根结点。
(2) 先序遍历第一棵树的根结点的子树森林。
(3) 先序遍历除去第一棵树之后剩余的树构成的森林。
例如， 图6.24(a)中森林的先序遍历序列为ABCDEFGHIJ。
2） 中序遍历
若森林非空， 则遍历方法为：
67淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
(1) 中序遍历森林中第一棵树的根结点的子树森林。
(2) 访问第一棵树的根结点。
(3) 中序遍历除去第一棵树之后剩余的树构成的森林。
例如， 图6.24(a)中森林的中序遍历序列为BCDAFEHJIG。
3） 后序遍历
若森林非空， 则遍历方法为：
(1) 后序遍历森林中第一棵树的根结点的子树森林。
(2) 后序遍历除去第一棵树之后剩余的树构成的森林。
(3) 访问第一棵树的根结点。
作业3：
1：把树用三种方法存储；
2：把树和森林与二叉树进行相互转换；
3：对树和森林进行遍历；
……………………………第7-8课时……………………………
6.6 赫夫曼树及其应用
6.6.1 最优二叉树
1. 路径和路径长度
路径是指从树中一个结点到另一个结点之间的分支序列，路径长度是指从一个结点到另一个结点所经过的
分支数目。
树的路径长度：从树根到每一个结点的路径长度之和。完全二叉树是路径长度最短的二叉树。
2. 结点的权和带权路径长度
在实际的应用中，人们常常给树的每个结点赋予一个具有某种实际意义的实数，我们称该实数为这个结点
的权。在树形结构中，我们把从树根到某一结点的路径长度与该结点的权的乘积，叫做该结点的带权路径长度
3. 树的带权路径长度
树的带权路径长度为树中所有叶子结点的带权路径长度之和，通常记为：
其中n为叶子结点的个数，wi为第i个叶子结点的权值，li为第i个叶子结点的路径长度。例如，图 6.26
中三棵二叉树的带权路径长度分别为：
WPL(a)=7×2＋5×2＋2×2＋4×2＝36
WPL(b)=4×2＋7×3＋5×3＋2×1＝46
WPL(c)=7×1＋5×2＋2×3＋4×3＝35
假设n个权值{ w1, w2, …, wn }构造一棵有n个叶子结点的二叉树，每个叶子的权值为wi， 则WPL最
小的二叉树叫做最优二叉树 。
68淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图6.26 具有不同带权路径长度的二叉树
问题1: 什么样的二叉树的路径长度PL最小？ 一棵树的路径长度为0， 结点至多只有1个（根）； 路径长
度为1， 结点至多只有2个（两个孩子）； 路径长度为2， 结点至多只有4个； 依此类推，路径长度为k， 结
点至多只有2k个, 所以n个结点二叉树其路径长度至少等于如图6.27所示序列的前n项之和。由图6.27可知，
结点n对应的路径长度为［log2n］，所以前n项之和为：
完全二叉树的路径长度：
(h为树的深度)，所以完全二叉树具有最小路径长度的性质，但不具有唯一性。有些树并不是完全二叉树，
但也可以具有最小路径长度，如图6.28所示。
图6.28 具有相同最小路径长度的不同形态的二叉树
问题2: 什么样的树的带权路径长度最小？ 例如： 给定一个权值序列{2, 3, 4, 7}， 可构造如图6.29所
示的多种二叉树的形态。
69淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图6.29 具有不同带权路径长度的二叉树
4. 赫夫曼树
构造赫夫曼算法的步骤如下：
（1）用给定的n个权值{w1, w2, …, wn}对应的n个结点构成n棵二叉树的森林F={T1, T2, …, Tn}，
其中每一棵二叉树Ti(1≤i≤n)都只有一个权值为wi的根结点，其左、右子树为空。
（2）在森林F中选择两棵根结点权值最小的二叉树，作为一棵新二叉树的左、右子树，标记新二叉树的根
结点权值为其左右子树的根结点权值之和。 （3）从F中删除被选中的那两棵二叉树， 同时把新构成的二
叉树加入到森林F中。
（4）重复（2）、（3）操作， 直到森林中只含有一棵二叉树为止， 此时得到的这棵二叉树就是赫夫曼树。
6.6.2 赫夫曼编码
电报需将传送的文字转换成由二进制的字符组成的字符串，如‘ABACCDA’设A，B，C，D编码分别为00，
01，10，11则‘00010010101100’14位，对方接收时将其译码。在传送电文时，希望总长度尽可能的短，如‘A，
B，C，D’分别编码为0，00，1和01则上述7个字符转换成总长为9位‘000011010’，但是这样的电文无法
译码‘0000’，可有多种译法‘AAAA’ ，‘ABA’或‘BB’，设计时用前缀编码。
前缀编码：任一个字符的编码都不是另一个字符编码的前缀，可利用二叉树设计前缀编码。
设计电文总长最短的前缀编码，设每种字符在电文中出现的次数为Wi，编码长度为Li，有n种字符，电文
总长ΣWiLi ( i=1…n) 。对应二叉树上，若置Wi为叶子结点的权，恰为WPL，即设计赫夫曼树，得到的前缀
编码为赫夫曼编码，赫夫曼树中没有度为1的结点（严格的（正则的）二叉树），一棵有n个叶子结点的赫夫曼
树共有2n-1个结点可以存储在2n-1的一维数组中，另外需知道双亲。
表 6 – 1 指令的使用频率 表 6 – 2 指令的变长编码
70淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
图6.30 构造赫夫曼树示例
表 6 – 3 指令的赫夫曼编码
可以验证，该编码是前缀编码。若一段程序有1000条指令， 其中I1大约有400条，I2大约有300条，
I3大约有150条，I4大约有50条，I5大约有40条，I6大约有30条，I7大约有30条。对于定长编码，该段
程序的总位数大约为3×1000＝3000。采用赫夫曼编码后，该段程序的总位数大约为 1×400＋2×300＋3×150
＋5×（50＋40＋30＋30）＝2200。可见，赫夫曼编码中虽然大部分编码的长度大于定长编码的长度3， 却使
得程序的总位数变小了。可以算出该赫夫曼编码的平均码长为：
71淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
举例：数据传送中的二进制编码。
要传送数据 state, seat, act, tea, cat, set, a,eat，如何使传送的长度最短？首先规定二叉树的
构造为左走0，右走1 ，如图6.31所示。
为了保证长度最短， 先看字符出现的次数， 然后将出现次数当作权， 如图6.32所示。
图6.31 左走0，右走1的二叉树 图6.33 构造赫夫曼树的过程
所以有state 的编码为 00111101101, stat的编码为001111011。
构造满足赫夫曼编码的最短最优性质：
(1) 若di≠dj（字母不同），则对应的树叶不同。 因此前缀码（任一字符的编码都不是另一个字符编码）
不同，一个路径不可能是其它路径的一部分， 所以字母之间可以完全区别。
(2) 将所有字符变成二进制的赫夫曼编码，使带权路径长度最短，相当总的通路长度最短。
若要求传送以上这些编码长度不一的数据，且还要求传送词间互相区分，应如何设计最优编码呢？为保证
传送词间互相区别，则需加入一空白字符出现频率，空白字符^出现为7，再构造赫夫曼树，由此得到的赫夫曼
编码一定满足最短且又互相区分的性质。
6.6.3 赫夫曼编码算法的实现
由于赫夫曼树中没有度为1的结点，则一棵有n个叶子的赫夫曼树共有2n-1个结点，可以用一个大小为
2n-1的一维数组存放赫夫曼树的各个结点。由于每个结点同时还包含其双亲信息和孩子结点的信息，所以构成
一个静态三叉链表。静态三叉链表描述如下：
typedef struct
{ unsigned int weight ; /* 用来存放各个结点的权值*/
unsigned int parent, LChild, RChild ; /*指向双亲、 孩子结点的指针*/
}HTNode, * HuffmanTree; /*动态分配数组， 存储赫夫曼树*/
typedef char * *HuffmanCode ; /*动态分配数组， 存储赫夫曼编码*/
创建赫夫曼树并求赫夫曼编码的算法如下：
void HuffmanCoding(HuffmanTree &ht , HuffmanCode &hc, int * w, int n)
{
/* w存放n个权值, 构造赫夫曼树ht, 并求出赫夫曼编码hc */
if (n<=1) return; // n为叶子结点个数
m=2*n-1; // m为结点个数
ht=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); /*0号单元未使用*/
72淘宝店铺：洋码头东东宝贝
这是一家用心的考试资料店
for(i=1; i<=n; i++) ht[i] ={ w[i], 0, 0, 0}; /*叶子结点初始化*/
for(i=n+1; i<=m; i++) ht[i] ={0, 0, 0, 0}; /*非叶子结点初始化*/
for(i=n+1; i<=m; i++) /*创建非叶子结点, 建赫夫曼树*/
{ select(ht, i-1, s1, s2);
//在ht[1]~ht[i-1]的范围内选择两个parent为0且weight最小的结点，其序号分别赋值给s1、 s2
ht[s1].parent=i; ht[s2].parent=i;
ht[i].LChild=s1; ht[i].RChild=s2;
ht[i].weight=ht[s1].weight+ht[s2].weight;
} /*赫夫曼树建立完毕*/
// 从叶子到根，逆向求每个叶子结点对应的赫夫曼编码hc=(HuffmanCode)malloc((n+1)*sizeof(char*));//
分配n个编码的头指针
cd=(char * )malloc(n * sizeof(char )); // 分配求当前编码的工作空间
cd[n-1]＝’\0’; // 从右向左逐位存放编码， 首先存放编码结束符
for(i=1; i<=n; i++) /*求n个叶子结点对应的赫夫曼编码*/
{ start=n-1; /*初始化编码起始指针*/
for(c=i, f=ht[i].parent; f!=0; c=f, f=ht［f］.parent)
if(ht［f］.LChild==c)
cd［--start］=′0′; /*左分支标0*/
else
cd［--start］=′1′; /*右分支标1*/
hc［i］=(char *)malloc((n-start)*sizeof(char));
strcpy(hc［i］, &cd［start］);
} free(cd);
}
数组ht的前n个分量表示叶子结点，最后一个分量表示根结点。 每个叶子结点对应的编码长度不等，但
最长不超过n。
不用栈不用递归中序遍历赫夫曼树，求赫夫曼编码。从根开始。见P148算法6.13。
作业4：
1：构造哈夫曼树；
2：生成哈夫曼编码；
本章教学总结：
73第七章：图
课程：数据结构
课题：第七章 7.1—7.6小节（共8个课时）
7.1 图的定义和术语
7.2 图的存储结构
7.2.1 数组表示法
7.2.2 邻接表
7.2.3 十字链表
7.2.4 邻接多重表
7.3 图的遍历
7.3.1 深度优先搜索
7.3.2 广度优先搜索
7.4 图的连通性问题
7.4.1 无向图的连通分量和生成树
7.4.3 最小生成树
7.5 有向无环图及其应用
7.5.1 拓扑排序
7.5.2 关键路径
7.6 最短路径
7.6.1 从某个源点到其余各顶点的最短路径
7.6.2 每一对顶点之间的最短路径
目的要求：理解图型结构的概念和术语，掌握图的邻接矩阵和邻接表两种存储形式，理解图的遍历的基本思想，
掌握图的两种遍历的方法和其实现的过程，学会图在最小生成树、拓扑排序、最短路径、关键路径中的应用。
新课重点、难点：
教学方法：课堂讲解、例题演示，课件演示
教学内容及过程：
……………………………第1-2课时……………………………
7.1 图的定义与基本术语
7.1.1 图的定义
图(Graph)是一种网状数据结构， 其形式化定义如下：
Graph=（V，R）
V={x|x∈DataObject}
R={VR}
VR={|P（x， y）∧（x， y∈V）}
DataObject为一个集合，该集合中的所有元素具有相同的特性。V中的数据元素通常称为顶点（vertex），
VR是两个顶点之间关系的集合。P（x，y）表示x和y之间有特定的关联属性P。
若∈VR，则表示从顶点x到顶点y的一条弧（arc），并称x为弧尾（tail）或起始点，称y
为弧头（head）或终端点，此时图中的边是有方向的，称这样的图为有向图。
若∈VR， 必有∈VR，即VR是对称关系，这时以无序对（x， y）来代替两个有序对，表示
x和y之间的一条边（edge），此时的图称为无向图。
74ADT Graph
数据对象V： 一个集合，该集合中的所有元素具有相同的特性。
数据关系R：R={VR}
VR={|P（x，y）∧（x， y∈V）}
基本操作：
（1） CreateGraph（G）： 创建图G。
（2） DestoryGraph（G）： 销毁图G。
（3） LocateVertex（G， v）：确定顶点v在图G中的位置。 若图G中没有顶点v，则函数值为“空”。
（4） GetVertex（G， i）： 取出图G中的第i个顶点的值。 若i大于图G中顶点数，则函数值为“空”。
（5） FirstAdjVertex（G，v）：求图G中顶点v的第一个邻接点。 若v无邻接点或图G中无顶点v，则
函数值为“空”。
（6） NextAdjVertex（G，v，w）：已知w是图G中顶点v的某个邻接点，求顶点v的下一个邻接点（紧跟
在w后面）。 若w是v的最后一个邻接点， 则函数值为“空”。
（7） InsertVertex（G， u）：在图G中增加一个顶点u。
（8） DeleteVertex（G， v）：删除图G的顶点v及与顶点v相关联的弧。
（9） InsertArc（G， v， w）：在图G中增加一条从顶点v到顶点w的弧。
（10） DeleteArc（G， v， w）： 删除图G中从顶点v到顶点w的弧。
（11） TraverseGraph（G）： 按照某种次序， 对图G的每个结点访问一次且仅访问一次。
基本术语
1:完全图、稀疏图与稠密图
我们设n表示图中顶点的个数，用e表示图中边或弧的数目，并且不考虑图中每个顶点到其自身的边或弧。
即若∈VR，则vi≠vj。
对于无向图而言，其边数e的取值范围是0~n（n-1）/2。我们称有n（n-1）/2条边（图中每个顶点和其
余n-1个顶点都有边相连）的无向图为无向完全图。
对于有向图而言，其边数e的取值范围是0~n（n-1）。我们称有n（n-1）条边（图中每个顶点和其余n-1
个顶点都有弧相连）的有向图为有向完全图。
对于有很少条边的图（e∈A， 则称顶点v邻接到顶点v′，顶点v′邻接自顶点v，
或者说弧与顶点v和v′相关联。
4. 度、入度和出度
对于无向图而言，顶点v 的度是指和v相关联边的数目，记作（v）。例如：图7.1中G2中顶点v3的度是
3，v1的度是2；
在有向图中顶点v的度有出度和入度两部分，其中以顶点v为弧头的弧的数目成为该顶点的入度，记作ID
（v），以顶点v为弧尾的弧的数目称为该顶点的出度，记作OD（v）,则顶点v的度为TD（v）=ID（v）+OD（v）。
例如：图G1中顶点v1的入度是ID(v1)=1，出度OD(v1)=2,顶点v1的度TD(v1)=ID(v1)+OD(v1)=3。一般地，
若图G中有n个顶点，e条边或弧，则图中顶点的度与边的关系如下：
5. 权与网
在实际应用中，有时图的边或弧上往往与具有一定意义的数有关，即每一条边都有与它相关的数，称为权，
这些权可以表示从一个顶点到另一个顶点的距离或耗费等信息。我们将这种带权的图叫做带权图或网，如图7.3
所示。
6. 路径与回路
无向图G=（V，{E}）中从顶点v到v′的路径是一个顶点序列vi0， vi1，vi2，…，vin，其中（vij-1，
vij）∈E，1≤j≤n。如果图G是有向图，则路径也是有向的，顶点序列应满足∈A， 1≤j≤n。
路径的长度是指路径上经过的弧或边的数目。在一个路径中，若其第一个顶点和最后一个顶点是相同的，即v=v
′，则称该路径为一个回路或环。若表示路径的顶点序列中的顶点各不相同，则称这样的路径为简单路径。除
了第一个和最后一个顶点外，其余各顶点均不重复出现的回路为简单回路。
767. 连通图
在无向图G=（V，{E}）中，若从vi到vj有路径相通，则称顶点vi与vj是连通的。如果对于图中的任意
两个顶点vi、vj∈V，vi，vj都是连通的，则称该无向图G为连通图。例如：G2就是连通图。无向图中的极大
连通子图称为该无向图的连通分量。在有向图G=（V，{A}）中，若对于每对顶点vi、vj∈V且vi≠vj， 从vi
到vj和vj到vi都有路径，则称该有向图为强连通图。有向图的极大强连通子图称作有向图的强连通分量，如
图7.4所示。
8. 生成树
一个连通图的生成树是一个极小连通子图，它含有图的全部顶点，只有n-1条边（构成树的最小分支树）
若在一棵生成树上添加一条边必定构成一个环。
一棵有n个顶点的生成树有且仅有n-1条边。若n个顶点小于n-1条边，则必为非连通图；多于n-1条边
一定有环，但仅有n-1条边的图不一定生成树。
如果一个有向图恰有一个顶点的入度为0，其余顶点入度为1，则是一棵有向树，一个有向树的生成森林。
由若干棵有向树组成，含有图中全部顶点，但只有足以构成若干棵不相交的有向树的弧。
7.2 图的存储结构
7.2.1 邻接矩阵表示法
图的邻接矩阵表示法（Adjacency Matrix）也称作数组表示法。它采用两个数组来表示图：
77一个是用于存储顶点信息的一维数组；另一个是用于存储图中顶点之间关联关系的二维数组，这个关联关
系数组被称为邻接矩阵。
若图G是一个具有n个顶点的无权图，G的邻接矩阵是具有如下性质的n×n矩阵A：
若图G是一个有n个顶点的网，则它的邻接矩阵是具有如下性质的n×n矩阵A： 例如：图就是一个有向
网N及其邻接矩阵的示例。
78邻接矩阵法的特点如下：
· 存储空间：对于无向图而言， 它的邻接矩阵是对称矩阵（因为若（vi，vj）∈E（G），则（vj，vi）∈
E（G）），因此我们可以采用特殊矩阵的压缩存储法，即只存储其下三角即可，这样，一个具有n个顶点的无向
图G， 它的邻接矩阵需要n（n-1）/2个存储空间即可。但对于有向图而言，其中的弧是有方向的， 即若∈E（G），不一定有∈E（G），因此有向图的邻接矩阵不一定是对称矩阵，对于有向图的邻接矩阵的
存储则需要n2个存储空间。
采用邻接矩阵存储法表示图，很便于实现图的一些基本操作，如实现访问图G中v顶点第一个邻接点的函
数FirstAdjVertex（G，v）可按如下步骤实现：
(1) 首先， 由LocateVertex（G，v）找到v在图中的位置，即v在一维数组vexs中的序号i。
(2) 二维数组arcs中第i行上第一个adj域非零的分量所在的列号j，便是v的第一个邻接点在图G中的
位置。
(3) 取出一维数组vexs［j］中的数据信息，即与顶点v邻接的第一个邻接点的信息。
对于稀疏图而言，不适于用邻接矩阵来存储，因为这样会造成存储空间的浪费。
7.2.2 邻接表表示法
图的邻接矩阵表示法(即图的数组表示法)，虽然有其自身的优点，但对于稀疏图来讲，用邻接矩阵的表示
方法会造成存储空间的很大浪费。邻接表（Adjacency List）表示法实际上是图的一种链式存储结构。它克服
了邻接矩阵的弊病，基本思想是只存有关联的信息，对于图中存在的边信息则存储，而对于不相邻接的顶点则
不保留信息。在邻接表中，对图中的每个顶点建立一个带头结点的边链表，如第i个边链表中的结点则表示依
附于顶点vi的边（若是有向图，则表示以vi为弧尾的弧）。每个边链表的头结点又构成一个表头结点表。这样，
一个n个顶点的图的邻接表表示由表头结点表与边表两部分构成：
(1) 表头结点表：由所有表头结点以顺序结构（向量）的形式存储，以便可以随机访问任一顶点的边链表。
表头结点的结构如图7.8（a）所示。 表头结点由两部分构成，其中数据域（data）用于存储顶点的名或其它
有关信息；链域（firstarc）用于指向链表中第一个顶点（即与顶点vi邻接的第一个邻接点）。
79作业1：
1：图7.3：无向图及其连通分量；
2：图7.5：图的生成树；
……………………………第3-4课时……………………………
■ 存储空间
对于有n个顶点，e条边的无向图而言，若采取邻接表作为存储结构，则需要n个表头结点和2e个表结点。
很显然在边很稀疏（即e 远小于n(n-1)/2时）的情况下，用邻接表存储所需的空间比邻接矩阵所需的空间
(n(n-1)/2)要节省得多。
■无向图的度
在无向图的邻接表中，顶点vi的度恰好就是第i个边链表上结点的个数。
■有向图的度
80在有向图中，第i个边链表上顶点的个数是顶点vi的出度，只需通过表头向量表中找到第i个顶点的边链
表的头指针，实现顺链查找即可。
如要判定任意两个顶点(vi和vj)之间是否有边或弧相连，则需要搜索所有的边链表，这样比较麻烦。
求得第i个顶点的入度，也必须遍历整个邻接表，在所有边链表中查找邻接点域的值为i的结点并计数求
和。由此可见， 对于用邻接表方式存储的有向图，求顶点的入度并不方便， 它需要通过扫描整个邻接表才能
得到结果。
一种解决的方法是逆邻接表法，我们可以对每一顶点vi再建立一个逆邻接表，即对每个顶点vi建立一个
所有以顶点vi为弧头的弧的表，如图7.10所示。
建邻接表时，若输入的顶点信息即为顶点编号，○(n+e)；否则○(n*e)。
在邻接表上容易找任何一个顶点的第一个邻接点和下一个邻接点，但要判定任两个顶点之间是否有边或弧，
需搜索第i个或第j个链表，没有邻接矩阵方便。
7.2.3 十字链表
十字链表弧结点结构图
顶点结点结构图
81在十字链表中既容易找到以Vi为尾的弧，也容易找到以Vi为头的弧，易求入度和出度。建立十字链表的
复杂度同邻接表。
7.2.4 邻接多重表
827.3 图的遍历
从图中某一顶点出发访问图中每一个结点，且每个顶点仅被访问一次----图的遍历 是图的连通性问题，
拓扑排序，求关键路径等的基础。
图的遍历比起树的遍历要复杂得多。由于图中顶点关系是任意的，即图中顶点之间是多对多的关系，图可
能是非连通图，图中还可能有回路存在，因此在访问了某个顶点后，可能沿着某条路径搜索后又回到该顶点上。
为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此我们为图设置
一个访问标志数组visited［n］，用于标示图中每个顶点是否被访问过，它的初始值为0(“假”)，表示顶点均
未被访问；一旦访问过顶点vi，则置访问标志数组中的visited［i］为1(“真”)，以表示该顶点已访问。
837.3.1 深度优先搜索
深度优先搜索（Depth-First Search）是指按照深度方向搜索，它类似于树的先根遍历，是树的先根遍历
的推广。 深度优先搜索连通子图的基本思想是：
（1） 从图中某个顶点v0出发，首先访问v0。
（2） 找出刚访问过的顶点vi的第一个未被访问的邻接点， 然后访问该顶点。以该顶点为新顶点，重复本
步骤，直到当前的顶点没有未被访问的邻接点为止。
（3）返回前一个访问过的且仍有未被访问的邻接点的顶点，找出并访问该顶点的下一个未被访问的邻接点，
然后执行步骤(2)。
采用递归的形式说明，则深度优先搜索连通子图的基本思想可表示为：
（1） 访问出发点v0。
（2） 依次以v0的未被访问的邻接点为出发点， 深度优先搜索图， 直至图中所有与v0有路径相通的顶点
都被访问。
若此时图中还有顶点未被访问，则另选图中一个未被访问的顶点作为起始点，重复上述深度优先搜索过程，
直至图中所有顶点均被访问过为止。
图给出了一个深度优先搜索的过程图示，其中实箭头代表访问方向，虚箭头代表回溯方向，箭头旁边的数
字代表搜索顺序， A为起始顶点。
84图的深度优先搜索过程图示
首先访问A，然后按图中序号对应的顺序进行深度优先搜索。 图中序号对应步骤的解释如下：
（1） 顶点A的未访邻接点有B、E、D， 首先访问A的第一个未访邻接点B；
（2） 顶点B的未访邻接点有C、E，首先访问B的第一个未访邻接点C；
（3） 顶点C的未访邻接点只有F，访问F；
（4） 顶点F没有未访邻接点，回溯到C；
（5） 顶点C已没有未访邻接点，回溯到B；
（6） 顶点B的未访邻接点只剩下E，访问E；
（7） 顶点E的未访邻接点只剩下G，访问G；
（8） 顶点G的未访邻接点有D、H，首先访问G的第一个未访邻接点D；
（9） 顶点D没有未访邻接点， 回溯到G；
（10） 顶点G的未访邻接点只剩下H， 访问H；
（11） 顶点H的未访邻接点只有I， 访问I；
（12） 顶点I没有未访邻接点， 回溯到H；
（13） 顶点H已没有未访邻接点， 回溯到G；
（14） 顶点G已没有未访邻接点， 回溯到E；
（15） 顶点E已没有未访邻接点， 回溯到B；
（16） 顶点B已没有未访邻接点， 回溯到A。
7.3.2 广度优先搜索
广度优先搜索（Breadth-FirstSearch）是指照广度方向搜索，它类似于树的层次遍历，是树的按层次遍
历的推广。广度优先搜索的基本思想是：
（1） 从图中某个顶点v0出发，首先访问v0。
（2） 依次访问v0的各个未被访问的邻接点。
（3） 分别从这些邻接点（端结点）出发，依次访问它们的各个未被访问的邻接点（新的端结点）。访问时
应保证：如果v i和vk为当前端结点，vi在vk之前被访问， 则vi的所有未被访问的邻接点应在vk的所有
未被访问的邻接点之前访问。重复（3）， 直到所有端结点均没有未被访问的邻接点为止。
85图的广度优先搜索过程图示
分析上述算法，图中每个顶点至多入队一次，因此外循环次数为n。当图g采用邻接表方式存储，则当结
点 v 出队后，内循环次数等于结点 v 的度。由于访问所有顶点的邻接点的总的时间复杂度为
O(d0+d1+d2+:+dn-1)=O(e)， 因此图采用邻接表方式存储，广度优先搜索算法的时间复杂度为O(n+e)；当图g
采用邻接矩阵方式存储，由于找每个顶点的邻接点时，内循环次数等于n，因此广度优先搜索算法的时间复杂
度为O(n2)。
作业2：
1：数组表示法表示图； 2：邻接表表示图；
3：十字链表表示图； 4：邻接多重表表示图；
……………………………第5-6课时……………………………
7.4 图的连通性问题
7.4.1 无向图的连通分量
图遍历时，对于连通图，无论是广度优先搜索还是深度优先搜索，仅需要调用一次搜索过程，即从任一个
顶点出发，便可以遍历图中的各个顶点。对于非连通图，则需要多次调用搜索过程，而每次调用得到的顶点访
问序列恰为各连通分量中的顶点集。例图是一个非连通图，按照它的邻接表进行深度优先搜索遍历，三次调用
DFSTraverse过程得到的访问顶点序列为：
设E（G）为连通图G中所有边的集合，则从图中任一顶点出发遍历图时，将E（G）分成两个集合T（G）
和B（G）。T（G）为遍历时的边的集合，B（G）是剩余边的集合。显然，T（G）和G中所有顶点一起构成连通
图G的极小连通子图，且为一棵生成树，分别称为深度优先生成树和广度优先生成树。 P171（a）（b）
对于非连通图，每个连通分量的顶点集和走过的边集一起构成若干生成树，称为生成森林。
867.4.3 最小生成树
应用：如何在最节省经费的前提下建立通信网。
在一个连通网的所有生成树中， 各边的代价之和最小的那棵生成树称为该连通网的最小代价生成树
（Minimum Cost Spanning Tree），简称为最小生成树(MST)。 最小生成树有如下重要性质：
设 N=(V,{E}) 是一连通网，U 是顶点集V的一个非空子集。 若（u, v）是一条具有最小权值的边， 其
中u∈U， v∈V-U， 则存在一棵包含边（u , v）的最小生成树。
我们用反证法来证明这个MST性质：
假设不存在这样一棵包含边（u , v）的最小生成树。 任取一棵最小生成树T，将（u , v）加入T中。根
据树的性质，此时T中必形成一个包含（u,v）的回路， 且回路中必有一条边（u′, v′）的权值大于或等
于（u, v）的权值。 删除（u′, v′），则得到一棵代价小于等于T的生成树T′，且T′为一棵包含边（u ,
v）的最小生成树。 这与假设矛盾， 故该性质得证。
我们可以利用MST性质来生成一个连通网的最小生成树。普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算
法便是利用了这个性质。
1. 普里姆算法
假设N=(V, {E})是连通网，TE为最小生成树中边的集合。
（1） 初始U={u0}(u0∈V), TE=φ；
（2） 在所有u∈U, v∈V-U的边中选一条代价最小的边（u0， v0）并入集合TE，同时将v0并入U；
（3） 重复（2）， 直到U=V为止。
此时，TE中必含有n-1条边，则T=（V，{TE}）为N的最小生成树。
可以看出， 普利姆算法逐步增加U中的顶点， 可称为“加点法”。
为了实现这个算法需要设置一个辅助数组closedge［ ］，以记录从U到V-U具有最小代价的边。对每个顶
点v∈V-U，在辅助数组中存在一个分量closedge［v］，它包括两个域vex和lowcost，其中lowcost存储该边
上的权， 显然有 closedge［v］.lowcost=Min({cost(u, v) | u∈U})
普里姆算法可描述如下：
struct
{
VertexType adjvex;
VRType lowcost;
} closedge［MAX_VERTEX_NUM］; /* 求最小生成树时的辅助数组*/
2. 克鲁斯卡尔算法
87假设N=(V, {E})是连通网，将N中的边按权值从小到大的顺序排列:
(1) 将n个顶点看成n个集合；
(2) 按权值由小到大的顺序选择边，所选边应满足两个顶点不在同一个顶点集合内，将该边放到生成树边
的集合中。同时将该边的两个顶点所在的顶点集合合并；
(3) 重复(2), 直到所有的顶点都在同一个顶点集合内。
可以看出，克鲁斯卡尔算法逐步增加生成树的边， 与普里姆算法相比，可称为“加边法”。
普里姆算法构造最小生成树的过程
普里姆算法各参量的变化
例如，对于图7.18所示的连通网， 将所有的边按权值从小到大的顺序排列为：
权值 1 2 3 4 5 5 5 6 6 6
边(v1,v3) (v4,v6) (v2,v5) (v3,v6) (v1,v4) (v2,v3) (v3,v4) (v1,v2) (v3,v5) (v5,v6)
经过筛选所得到边的顺序为：
(v1,v3) (v4,v6) (v2,v5) (v3,v6) (v2,v3)
在选择第五条边时，因为v1、v4已经在同一集合内，如果选（v1，v4）， 则会形成回路， 所以选（v#-2，
v#-3）。
88设N= (V, {E}), 最小生成树的初态为T=（V, { }）。
（1） 待选的边： (2, 3)->5, (2, 4)->6, (3, 4)->6, (2, 6)->11, (4, 6)->14, (1, 2)->16, (4,
5)->18, (1, 5)->19, (1, 6)->21, (5, 6)->33。
顶点集合状态： {1}， {2}， {3}， {4}， {5}， {6}。
最小生成树的边的集合： { }。
（2) 从待选边中选一条权值最小的边为: (2, 3)->5。
待选的边变为： (2, 4)->6, (3, 4)->6, (2, 6)->11, (4, 6)->14, (1, 2)->16, (4, 5)->18,
(1, 5)->19, (1, 6)->21, (5, 6)->33。
顶点集合状态变为： {1}， {2， 3}， {4}， {5}， {6}。
最小生成树的边的集合： {(2, 3)}。
（3） 从待选边中选一条权值最小的边为: (2, 4)->6。
待选的边变为： (3, 4)->6, (2, 6)->11, (4, 6)->14, (1, 2)->16, (4, 5)->18 , (1, 5)->19,
(1, 6)->21, (5, 6)->33。
顶点集合状态变为： {1}， {2， 3， 4}， {5}， {6}。
最小生成树的边的集合： {(2, 3), (2, 4)}。
（4） 从待选边中选一条权值最小的边为: (3, 4)->6， 由于3、 4在同一个顶点集合{2，3，4}内，故放弃。
重新从待选边中选一条权值最小的边为: (2, 6)->11。
待选的边变为： (4, 6)->14 , (1, 2)->16 , (4, 5)->18 , (1, 5)->19, (1, 6)->21 , (5, 6)->33。
顶点集合状态变为： {1}， {2， 3， 4， 6}， {5}。
最小生成树的边的集合： {(2, 3)， (2, 4), (2, 6)}。
（5） 从待选边中选一条权值最小的边为:(4,6)->14， 由于4、 6在同一个顶点集合{2，3，4，6}内，故放
弃。重新从待选边中选一条权值最小的边为: (1, 2)->16。
待选的边变为： (4, 5)->18 , (1, 5)->19, (1, 6)->21, (5, 6)->33。
顶点集合状态变为： {1， 2， 3，4， 6}，{5}。
最小生成树的边的集合： {(2, 3)， (2, 4), (2, 6)，(1, 2)}。
（6） 从待选边中选一条权值最小的边为: (4, 5)->18。
待选的边变为： (1, 5)->19, (1, 6)->21 , (5, 6)->33。
顶点集合状态变为： {1， 2， 3， 4， 6， 5}。
最小生成树的边的集合： {(2, 3)， (2, 4), (2, 6) ， (1, 2), (4， 5)}。
至此， 所有的顶点都在同一个顶点集合{1，2，3，4，6， 5}里，算法结束。所得最小生成树如图7.20
89所示，其代价为： 5+6+11+16+18=56。
作业3：
1：对图进行普里姆算法操作，求出最小生成树；
2：对图进行克鲁斯卡尔算法操作，求出最小生成树；
……………………………第7-8课时……………………………
7.5 有向无环图的应用
一个无环的有向图称为有向无环图，简称DAG图。
检查一个有向无环图是否存在比无向图复杂，如在无向图中若发现回边（指向已访问过的顶点的边）必存
在环，而对有向图有可能是指向深度优先生成森林中另一棵生成树上顶点的弧。因此判断时，从图上某个顶点
v出发，在dfs（v）结束之前，若出现一条从顶点u到顶点v的回边，说明u是v的子孙，这时必有环。
有向无环图也是描述一项工程或系统的进行过程的有效工具。一个大型工程可分为若干活动（子工程），而
这些子工程之间受一定条件的约束，关心的问题是：该工程能否顺序进行，估算整个工程完成所必须的最短时
间——拓扑排序，关键路径。
7.5.1 拓扑排序（Topological Sort）
用顶点表示活动，用弧表示活动间的优先关系的有向无环图，称为顶点表示活动的网（ActivityOnVertex
90Network），简称为AOV-网。
在有向图G=（V， {E}）中， V中顶点的线性序列（vi1, vi2, vi3 …，vin）称为拓扑序列，序列必须
满足如下条件： 对序列中任意两个顶点vi、vj，在G中有一条从vi到vj的路径，则在序列中vi必排在vj
之前。
例如，图7.21的一个拓扑序列为： C1, C2, C3, C4, C5, C8, C9, C7, C6。
AOV-网的特性如下：
· 若vi为vj的先行活动，vj为vk的先行活动，则vi必为vk的先行活动，即先行关系具有可传递性。
从离散数学的观点来看，若有、 ，则必存在。
显然，在AOV-网中不能存在回路，否则回路中的活动就会互为前驱，从而无法执行。
· AOV-网的拓扑序列不是唯一的。
例如，图7.21的另一个拓扑序列为：C1, C2, C3, C8, C4, C5, C9, C7, C6。
拓扑排序的基本思想为：
（1） 从有向图中选一个无前驱的顶点输出；
（2） 将此顶点和以它为起点的弧删除；
（3） 重复（1）、（2），直到不存在无前驱的顶点；
（4） 若此时输出的顶点数小于有向图中的顶点数，则说明有向图中存在回路，否则输出的顶点的顺序即为
一个拓扑 序列。
例如，对于图7.22所示的AOV-网，执行上述过程可以得到如下拓扑序列：
v1，v6，v4，v3，v2，v5 或 v1，v3，v2，v6，v4，v5
91由于有向图的存储形式的不同， 拓扑排序算法的实现也不同。
1） 基于邻接矩阵表示的存储结构
A为有向图G的邻接矩阵， 则有：
· 找图G中无前驱的顶点——在A中找到值全为0的列；
· 删除以i为起点的所有弧——将矩阵中i对应的行全部置为0。
算法步骤如下：
（1） 取1作为第一新序号；
（2） 找一个未新编号的、 值全为0的列j， 若找到则转（3）； 否则， 若所有的列全部都编过号， 拓
扑排序结束； 若有列未曾被编号， 则该图中有回路；
（3） 输出列号对应的顶点j， 把新序号赋给所找到的列；
（4） 将矩阵中j对应的行全部置为0;
（5） 新序号加1， 转（2）。
2） 基于邻接表的存储结构
入度为零的顶点即为没有前驱的顶点， 我们可以附设一个存放各顶点入度的数组indegree ［ ］，于是有
（1）找G中无前驱的顶点——查找indegree ［i］为零的顶点v#-i；（2）删除以i为起点的所有弧——对链
在顶点i后面的所有邻接顶点k，将对应的indegree［k］ 减1。
为了避免重复检测入度为零的顶点，可以再设置一个辅助栈，若某一顶点的入度减为0，则将它入栈。每
当输出某一入度为0的顶点时，便将它从栈中删除。
7.5.2 关键路径
有向图在工程计划和经营管理中有着广泛的应用。 通常用有向图来表示工程计划时有两种方法：
· 用顶点表示活动， 用有向弧表示活动间的优先关系， 即上节所讨论的AOV-网。
· 用顶点表示事件， 用弧表示活动， 弧的权值表示活动所需要的时间。
我们把用第二种方法构造的有向无环图叫做边表示活动的网（Activity On Edge Network）, 简称AOE-
网。
AOE-网在工程计划和管理中很有用。 在研究实际问题时， 人们通常关心的是：
· 哪些活动是影响工程进度的关键活动？
· 至少需要多长时间能完成整个工程？
在AOE网中存在唯一的、入度为零的顶点，叫做源点；存在唯一的、出度为零的顶点，叫做汇点。从源点
到汇点的最长路径的长度即为完成整个工程任务所需的时间，该路径叫做关键路径。关键路径上的活动叫做关
键活动。这些活动中的任意一项活动未能按期完成，则整个工程的完成时间就要推迟。相反，如果能够加快关
键活动的进度，则整个工程可以提前完成。
图7.29 一个 AOE-网
92· 事件vi的最早发生时间ve(i)：从源点到顶点vi的最长路径的长度，叫做事件vi的最早发生时间。
求ve(i)时可从源点开始， 按拓扑顺序向汇点递推：
ve(0)=0；
ve(i)=Max{ve（k）＋dut（）}
∈T, 1≤i≤n-1;
其中，T为所有以i为头的弧的集合，dut（）表示与弧对应的活动的持续时间。
· 事件vi的最晚发生时间vl(i)： 在保证汇点按其最早
发生时间发生这一前提下，求事件vi的最晚发生时间。
在求出ve(i)的基础上，可从汇点开始， 按逆拓扑顺序向源点递推，求出vl(i)：
vl(n-1)=ve(n-1)；
vl(i)=Min{vl（k）＋dut（）}
∈S, 0≤i≤n-2;
其中，S为所有以i为尾的弧的集合，dut（）表示与弧对应的活动的持续时间。
· 活动ai的最早开始时间e(i) ：如果活动ai对应的弧为，则e(i)等于从源点到顶点j的最长路
径的长度，即：e(i)=ve(j)
· 活动ai的最晚开始时间l(i) ：如果活动ai对应的弧为，其持续时间为dut（）, 则有：
l(i)=vl(k)- dut（），即在保证事件v k的最晚发生时间为vl(k)的前提下，活动ai的最晚开始时间
为l(i)。
· 活动ai的松弛时间（时间余量）：ai的最晚开始时间与ai的最早开始时间之差：{l(i)-e(i)}。
显然， 松弛时间（时间余量）为0的活动为关键活动。
求关键路径的基本步骤如下：
（1） 对图中顶点进行拓扑排序，在排序过程中按拓扑序列求出每个事件的最早发生时间ve(i)；
（2） 按逆拓扑序列求每个事件的最晚发生时间vl(i)；
（3） 求出每个活动ai的最早开始时间e(i)和最晚发生时间l(i)；
（4） 找出e(i)=l(i) 的活动ai， 即为关键活动。
93例如， 对图所示的AOE-网计算关键路径的过程如下:
(1)计算各顶点的最早开始时间：
(2)ve(0)=0
(3)ve(1)=max{ve(0)+dut(<0,1>)}=6
(4)ve(2)=max{ve(0)+dut(<0,2>)}=4
(5)ve(3)=max{ve(0)+dut(<0,3>)}=5
(6)ve(4)=max{ve(1)+dut(<1,4>),ve(2)+dut(<2,4>)}=7
(7)ve(5)=max{ve(3)+dut(<3,5>)}=7
(8)ve(6)=max{ve(4)=dut(<4,6>)}=16
(9)ve(7)=max{ve(4)+dut(<4,7>)}=14
(10) ve(8)=max{ve(6)+dut(<6,8>),ve(7)+dut(<7,8>)}=18
(2) 计算各顶点的最迟开始时间：
vl(8)=ve(8)=18
vl(7)=min{vl(8)-dut(<7,8>)}=14
vl(6)=min{vl(8)-dut(<6,8>)}=16
94vl(5)=min{vl(7)-dut(<5,7>)}=10
vl(4)=min{vl(6)-dut(<4,6>),vl(7)-dut(<4,7>)}=7
vl(3)=min{vl(5)-dut(<3,5>)}=8
vl(2)=min{vl(4)-dut(<2,4>)}=6
vl(1)=min{vl(4)-dut(<1,4>)}=6
vl(0)=min{vl(1)-dut(<0,1>),vl(2)-dut(<0,2>),vl(3)-dut(<0,3>)}=0
(3) 计算各活动的最早开始时间：
e(a1)=ve(0)=0
e(a2)=ve(0)=0
e(a3)=ve(0)=0
e(a4)=ve(1)=6
e(a5)=ve(2)=4
e(a6)=ve(3)=5
e(a7)=ve(4)=7
e(a8)=ve(4)=7
e(a9)=ve(5)=7
e(a10)=ve(6)=16
e(a11)=ve(7)=14
对图7.24所示网的计算结果如下所示
(4) 计算各活动的最迟开始时间：
l(a11)=vl(8)-dut(<7,8>)=14
l(a10)=vl(8)-dut(<6,8>)=16
l(a9)=vl(7)-dut(<5,7>)=10
l(a8)=vl(7)-dut(<4,7>)=7
l(a7)=vl(6)-dut(<4,6>)=7
l(a6)=vl(5)-dut(<3,5>)=8
l(a5)=vl(4)-dut(<2,4>)=6
l(a4)=vl(4)-dut(<1,4>)=6
l(a3)=vl(3)-dut(<0,3>)=3
l(a2)=vl(2)-dut(<0,2>)=2
95l(a1)=vl(1)-dut(<0,1>)=0
7.6 最 短 路 径
7.6.1 求某一顶点到其它各顶点的最短路径
有向网G6的带权邻接矩阵
96G6：v0到各点的最短路径，D向量的变化
当我们按长度递增的顺序来产生各个最短路径时，设S为已经求得的最短路径的终点集合。
我们可以证明：下一条最短路径或者是弧（v0，vx），或者是中间经过S中的某些顶点而后到达vx的路径。
可用反证法：假设下一条最短路径上有一个顶点vy不在S中， 即此路径为（v0，…，vy，…，vx）。显然，
（v0，…，vy）的长度小于（v0，…，vy，…，vx）的长度，故下一条最短路径应为（v0，…，vy），这与假设
的下一条最短路径（v0，…，vy，…， vx）相矛盾！因此，下一条最短路径上不可能有不在S中的顶点vy，
即假设不成立。
（1） 在vi、vj间加入顶点v1，得（vi, …，v1）和(v1, …，vj)， 其中（vi, …, v1）是vi到v1 的
且中间顶点号不大于0的最短路径， (v1, …, vj) 是v1到vj 的且中间顶点号不大于0的最短路径，这两条
路径在上一步中已求出。 将（vi, …, v1, …, vj）与上一步已求出的且vi到vj 中间顶点号不大于0的最
短路径比较，取其中较短的路径作为vi到vj 的且中间顶点号不大于1的最短路径。
（2）在vi、vj间加入顶点v2，得（vi, …, v2）和(v2, …, vj)， 其中（vi, …, v2）是vi到v2 的且
中间顶点号不大于1的最短路径， (v2, …, vj) 是v2到vj 的且中间顶点号不大于1的最短路径，这两条路
径在上一步中已求出。将（vi, …, v2, …, vj）与上一步已求出的且vi到vj 中间顶点号不大于1的最短路
径比较， 取其中较短的路径作为vi到vj 的且中间顶点号不大于2的最短路径。
……
依此类推，经过n次比较和修正，在第（n-1）步，将求得vi到vj 的且中间顶点号不大于n-1的最短路
径，这必是从vi到vj的最短路径。
图g中所有顶点偶对vi、vj间的最短路径长度对应一个n阶方阵D。在上述n+1步中，D的值不断变化，
对应一个n阶方阵序列。
定义：
n阶方阵序列： D-1, D0, D1, D2, …，DN-1
其中: D-1［i］［j］= g.arcs［i］［j］
Dk［i］［j］=Min{Dk-1［i］［j］, Dk-1［i］［k］+Dk-1［k］［j］} 0≤k≤n-1
97作业4：
1：给定图的拓扑排序的问题求解；
2：给定图的关键路径的问题求解；
3：给定图的最短路径的问题求解；
本章教学总结：
98
