当前位置:首页 >> 学科竞赛 >>

备战NOIP2010提高组初赛复习——数据结构


备战 NOIP2010 提高组初赛复习——数据结构篇

早期的程序设计主要偏重于数值计算领域,采用的数据结构相对简单。例如 FORTRAN 语言仅定 义了数组(包括多维数组)和复数两种结构型数据,这两种数据类型足以应付当时多数的科学计算 问题。 但是随着现代科技的发展,计算机逐渐应用于数据处理和非数值计算问题,从客观事物中抽象 出的数据日益显现出多样化的特征,简单的数据类型已远远不能满足需要,各数据元素之间的复杂 联系已经不是普通的数学方程式所能表达的了。在这种背景下,一种专门研究数据之间结构关系的 学科—数据结构便应运而生。 数据结构专门研究各种数据的表示、数据的类型以及它们之间关系的集合, 其研究范围主要包 括各种数据结构的性质,即它们的逻辑结构、物理结构以及施于其上的操作。数据结构的类型种类 繁多,可以从不同的角度来划分:若从数据元素的值在使用时具有不可分割的性质或者是它可以由 更基本的成份组成这个角度来划分,数据结构可以分成简单类型和构造类型两大类;如果从数据所 占据的内存空间在程序执行期间是否发生变化这个角度来划分, 数据结构又可以分成静态结构和动 态结构两大类;如果从数据结点后继关系的多少和是否具有层次性的角度划分,数据结构还可以分 成线性结构和非线性结构两大类。 简单类型 构造类型 线性结构 非线性结构 整型、实型、字符型、布尔型 静态数据类型 数组、记录、集合、字符串 文件、指针 动态数据的类型 数组、栈、队列、链表、串 树、图

通常高级程序设计语言都提供了各种简单类型和静态构造类型的数据结构。例如 PASCAL 就 提供了12种类型的定义。这12种类型中除了文件和指针属于动态结构的构造类型外,其余1 0种均属于简单类型和静态构造类型。在上表的数据结构中,像数组、栈、串和队列等数据结构 属于线性数据结构,而树和图属于非线性数据结构。线性数据结构易于表示各结点之间的联系, 其存储方式相对简单;非线性数据结构往往能比较形象地反映各结点之间的层次关系。无论是线 性结构或非线性结构,若采用数组方式存储,则属于静态数据类型;若采用指针类型存储,则属 于动态数据类型。考虑到篇幅限制和读者大多具备 pascal 语言或 c 语言的基础,本书侧重讲解 线性结构和非线性结构两种。 数据结构和算法有着密切的联系,简洁有效的算法很大程度上出自于对数据结构的正确选 取。奥林匹克信息学竞赛的试题大都属于非数值计算问题,从问题中抽象出的数据多半是结构类 型的,因此,对于参与这项活动的学生来说,学好、用好数据结构尤为重要。为此。我们在本书 中详尽地介绍了数据结构的有关概念和基本操作, 同时辅之于一些实例, 围绕编程实际展开讨论, 尽可能多给读者一点启示。

第一章 顺序存储结构的线性表
线性表是最常用且比较简单的一种数据结构,它是由有限个数据元素组成的有序集合,每个 数据元素有一个数据项或者含多个数据项。 例如 26 个英文字母表(A, ??, B, Z)是一个线性表,
1

表中每一个数据元素由单个字母组成数据项。又如(图 1—1)也是一个线性表,表中含 8 个数 据元素,每一个数据元素由 n 个选手在该项目的竞赛成绩组成。

学生 项目 项目 1 ?? 项目 i

学生 1

??

学生 j

??

学生 n

项目总分

xij

?x
i ?1

n

ij

?? 项目 8 选手总分 sum

Sum xj=

?x
i ?1

8

ij

(图 1—1) 线性表具有如下结构特征: 均匀性:即同一线性表的各数据元素的数据类型一致且数据项数相同; 有序性:表中数据元素之间的相对位置是线性的,即存在唯一的“第一个”和“最后一个” 数据元素。 除第一个和最后一个外, 其它元素前面均只有一个数据元素 (直接前趋) 和后面均只有一个数据元素(直接后继) 。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构二类线性表。 顺序存储结构是 指用一组地址连续的存贮单元依次存储线性表的元素,通常用数组实现;而在链式存储结构的线 性表中,逻辑上相邻的两元素,其物理位置不要求相邻。其实现既可采用静态数组,亦可采用动 态指针。为了扩大用户空间和更多地体现链式存储结构的便利,实践中大都采用动态链表形式。 为此,本书在讲解顺序存储结构的线性表时采用数组类型,在讲解链式存储结构的线性表采用指 针类型。另外,根据存取方式的限制和表元素类型的限制,还存在几种特殊类型的线性表:栈、 队列、串,它们一般采用顺序存储结构

§1.1

数组

我们称有限个同类型数据元素的序列为数组,它是一种定长的线性表。若数组元素不再有分 量,该序列叫一维数组;若数据元素为数组,则称该元素为多维数组。例如 var A:array[c‥d] of atype; B:array[c1‥d1,c2‥d2] of btype; A 为一维数组, 表长为 (d-c+1) 元素类型为 atype; 为二维数组, , B 表长为 1-c1) 2-c2), (d *(d 元素类型为 btype。一维数组和多维数组的元素个数由其类型说明或变量说明静态确定,执行中 不能增减其内存空间。 一、数组的顺序存储结构 数组的物理实现是一块连续的存储空间,它是按首址(表中第 1 个元素的地址)十 位移来 访问每一个元素的。设 loc(a[i])—A 表中元素 i 的内存地址(c≤i≤d) ;

2

loc(b[i,j])—B 表中(i,j)元素的内存地址(c1≤i≤d1,c2≤j≤d2) ; loc(a[i])=loc(a[c])+(i-c)*la la—atype 类型的长度; 首址 位移 loc(b[i,j])=loc(b[c1,c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb lb—btype 类型的长度; 首址 位移 一维数组按照下标递增的顺序访问表中元素 a[c]→a[c+1]→??→a[d] 二维数组按照先行后列的顺序访问表中元素 b[c1,c2]→b[c1,c2+1]→??→b[c1,d2]→??→b[i-1,d2]→b[i,c2]→??→b[d1,d2-1] →b[d1,d2] 在数组中,数据元素的下标间接反映了数据元素的存储地址。而计算机内存是随机存取的装 置,所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了,数组中任意一个元 素的存取时间都相等。从这个意义上讲,数组的存储结构是一个随机存取的结构。 二、数组在顺序存储结构下的插入与删除 设数组定义为 Const m=数组的长度上限; Type vtype=array [1‥m]of elementype; {数组类型} var n:integer; {数组的实际长度} v:vtype; {数组} 按上述定义,v 为一个长度为 n 的数组 v={v[1],v[2],??,v[n]},元素类型为 elementype。 1、插入操作 现要在数组的第 i-1 个元素 v[i-1]与第 i 个元素 v[i]之间插入一个新元素 b,插入后将得 到一个长度为 n+1 的新数组 v’={v’[1],?,v’[n],v’[n+1]} 插入前后两数组的元素 v[j]与 v’[j]满足如下关系

?v[ j ] ? v [ j ] ? ?b ?v[ j ? 1] ?
'

1 ? j ? i ?1 j?i i ?1 ? j ? n ?1

显然,若插入运算在数组未尾(即在 v[n]后插入新元素)进行,则只要在数组末尾增加一 个元素即可。但是,在一般情况下,如果插入运算在第 i(1≤i≤n)个元素之前进行,则原来第 i 个元素及其之后的所有元素都必须移动。移动从最后一个元素(即 v[n])开始,直到第 i 个元 素之间共 n-i+1 个元素依次向后移动一个位置,然后将新元素插入第 i 项: procedure insert(b:elementype; i:integer; var n:integer; var v:vtype); begin if n≥m {上溢} then writeln(‘overflow’) else if (i<1)or(i>n+1) then writeln(‘without’) else begin for j:=n downto i do v[j+1]←v[j]; {v[i]‥v[n]向后移动一个位置}

3

v[i]←b; n←n+1; end;{else}

{b 插入 i 位置, 数组的长度+1} v

end; {insert} 执行 insert 过程的时间复杂度:对顺序存储的数组作一次插入运算,平均起来,大约需要移动 数组中一半的元素。 2、删除操作 现要删除数组 v 中的第 i 个元素, 使得删除后的 v 数组变为 v’={v’[1], v’[2], ??, v’[n-1]}, 其长度变为 n-1。显然删除前后两数组元素 v[j]和 v’[j]满足下列关系

?v[ j ] v ' [ j] ? ? ?v[ j ? 1]

1 ? j ? i ?1 i ? j ? n ?1

同样,为了删除数组中第 i 个元素,则原来第 i 个元素之后的所有元素必须依次向前移动一个位 置。如果要删除数组最后一个元素,则很简单,不需要移动数组元素;如果要删除数组的第一个 元素,则很复杂,必须将数组中的所有元素依次向前移动一个位置。在一般情况下,要删除第 i 个元素,需要将数组中第 i+1 到第 n 共 n-i 个元素依次向前移动一个位置。 procedure delet (i:integer; var n:integer; var v:vtype); begin if (i<1)or (i>n) then writeln (‘without’) else begin for j:=i to n-1 do v[j]←v[j+1]; {v[i+1]‥v[n]向前移动一个位置} n←n-1; {v 数组的长度-1} end;{else} end;{delet} 执行 delet 过程的时间复杂度:对顺序存储的数组作一次删除,平均起来,大约需要移动表 中一半的元素。 综上所述,数组的顺序分配,其结构比较简单,便于随机访问数组中的任一元素。但是如果 数组要保持线性表特征的话(由下标指明元素间的有序性) ,其增删操作的效率比较低。特别当 数组很大时,插入与删除运算颇为费时。因此,比较小的数组或元素不常变动(很少进行插入与 删除运算)的数组可用作线性表,而对于大的线性表或元素经常变动的线性表,可以采用链式存 储结构。 三、数组的应用实例 1、 在编程时 (使用任一种高级语言, 不一定是 Pascal) , 如果需要从磁盘文件中输入一个很大的二维 数组 (例 如 1000*1000的 double型数组)按行读(即外层循环是关于行的)与按列读(即外层循 环是关于列的)相 , 比,在输入效率上( ) 。 A. 没有区别 C. 按行读的方式要高一些 B. 有一些区别,但机器处理速度很快,可忽略不计 D. 按列读的方式要高一些 E. 取决于数组的存储方式。

§1.2



栈是一种线性表,对它的插入和删除都限制在表的同一端进行。这一端叫做栈的“顶” ,另一
4

端则叫做栈的“底” 。 根据栈的定义,每次删除的总是当前“最年轻”的表目,即最后插入的表目,而最先插入的表 目则被放在栈的底部,要到最后才能删除。因此,栈又被称为“后进先出表” (LIFO—last input first output) 。仿佛食堂里的一叠盘子,每次只许一个一个地往上堆,一个一个地往下取。 通常栈可以用顺序的方式存储,分配一块连续的存储区域存放栈中的表目,并用一个变量 t 指 向当前栈顶。假设栈中表目数的上限为 m,所有表目都具有同一类型 stype,则可以用下列方式定 义栈: Const m=栈表目数的上限; Type stack=array[1‥m] of stype; {栈类型} Var s:stack; {栈} t: integer; {栈顶指针} m t→ ?????

1 栈s (图 1.2—1) 一、栈的基本运算 1、过程 push(s,x,t)—往栈 s 中压入一个值为 x 的表目 procedure push (var s:stack; x:stype; var t:integer); begin if t=m then writeln(‘overflow’) else begin t←t+1; s[t]←x; end;{else} end;{Push} 2、函数 pop(s,t)—从栈中弹出一个表目 function pop (var s:stack; var t:integer):stype; begin if t=0 then writeln (‘underflow’) else begin pop←s[t]; t←t-1; end;{else} end;{pop} 3 函数 top(s,t)—读栈顶元素 function top (s:stack; t:integer):stype; begin if t=0 then writeln (‘stack empty’)
5

{上溢} {x 入栈}

{下溢} {栈顶元素出栈}

else top←s[t]; end;{top}

{返回栈顶元素}

二、栈的应用 1. 递归过程和函数调用时,处理参数和返回地址,通常使用一种称为( )的数据结构。 A.队列 B.多维数组 C.线性表 D.链表 E.栈 2. 设栈 S 的初始状态为空,元素 a,b,c,d,e,f 依次入栈,出栈顺序为 b,d,c,f,e,a 那 么栈容量至少应该是( ) 。 A.6 B.5 C.4 D.3 E.2 3. 某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站状态为空,从 这一 时刻开始的出入记录为: “进,出,进, 进,出,出,进,进, 出,出”假设车辆入站的 顺序为 1, 进, 进, 。 2,3,??,则车辆出站的顺序为( 。 ) A. 1, 2, 3, 4, 5 B. 1, 2, 4, 5, 7 C. 1, 4, 3, 7, 6 D. 1, 4, 3, 7, 2 E. 1, 4, 3, 7, 5 4. 地面上有标号为 A、B、C 的 3 根细柱, 在 A 柱上放有 10 个直径相同中间有孔的圆盘, 从上到 下次依次编号为 1, 2, 3, ??, A 柱上的部分盘子经过 B 柱移入 C 柱, 也可以在 B 柱上暂存。 将 如果 B 柱上的操作记录为: “进,进,出,进,进,出,出,进,进,出,进,出,出” 。那 么, 在 C 柱上, 从下到上的盘子的编号为( ) 。 A. 2 4 3 6 5 7 B. 2 4 1 2 5 7 C. 2 4 3 1 7 6 D. 2 4 3 6 7 5 E. 2 1 4 3 7 5 5. 设栈 S 的初始状态为空,元素 a, b, c, d, e 依次入栈,以下出栈序列不可能出现的有( )(不定 项)。 A. a, b, c, e, d B. b, c, a, e, d C. a, e, c, b, d D. d, c, e, b, a 6. 表达式 a*(b+c)-d 的后缀表达式是: A) abcd*+B) abc+*dC) abc*+d- D) -+*abcd

§1.3

队列

一、队列的基本概念 队列是不同于栈的另一种线性表。在日常生活中,无论是购物、订票或候车都有可能要排队。 排队所遵循的原则是“先来先服务” ,后来者总是加到队尾,排头者总是先离开队伍。队列就是从 日常生活中的排队现象抽象出来的。所谓队列,就是允许在一端进行插入,在另一端进行删除的线 性表。允许插入的一端称为队尾,通常用一个队尾指针 r 指向队尾元素,即 r 总是指向最后被插入 的元素; 允许删除的一端称为队首, 通常也用一个队首指针 f 指向排头元素的前面。 初始时 f=r=0。

?
a b c d

f

?
b c d

f

?
B c d e

f

?
r

?
r

?
r

6

删除一个元素 插入一个元素 (图 1.3—1) 显然,在队列这种数据结构中,最先插入在元素将是最先被删除;反之最后插入的元素将最后 被删除,因此队列又称为“先进先出” (FIFO—first in first out)的线性表。 与栈相似,队列的顺序存储空间可以用一维数组 q[1‥m]模拟: Const m = 队列元素的上限; Type equeue=array[1?m] of qtype; {队列的类型定义} Var q:equeue; {队列} r,f:integer; {队尾指针和队首指针}

一个队列

?
Q: 1 (图 3.1—2)

f

?
m

r

二、队列的基本运算 队列的运算主要有两种 1、过程 ADD(q,x,r)—在队列 q 的尾端插入元素 x procedure ADD(var q: equeue; x:qtype; var r:integer); begin if r=m then writeln (‘overflow’) {上溢} else begin {后移队尾指针并插入元素 x} r←r+1; q[r]←x; end;{else} end;{ADD} 2、过程 DEL(q,y,f,r)—取出 q 队列的队首元素 y procedure DEL(var q:equeue; var y:qtype; var f:integer); begin if f=r then writeln (‘under flow’) {下溢} else begin {后移队首指针并取出队首元素} f←f+1; y←q[f]; end;{else} end;{DEL} 由于队列只能在一端插入,在另一端删除,因此随着入队及出队运算的不断进行,就会出现一 种有别于栈的情形:队列在数组中不断地向队尾方向移动,而在队首的前面产生一片不能利用的空 闲存储区,最后会导致当尾指针指向数组最后一个位置(即 r=m)而不能再加入元素时,存储空间 的前部却有一片存储区无端浪费,这种现象称为“假溢出” 。例如: m m m r→m Am

7

A4 3 A3 f,r→3 2 A2 2 1 A1 1 f→ 加入三个元素 删除三个元素队列空 f=0 r=3 f=r=3 (图 1.3 —3) f→3 2 1 加入 m-3 个元素队列满 r=m f=3

1 f,r→ 初始时队列空 f=r=0

三、循环队列及其运算 所谓循环队列, 就是将队列存储空间的最后一个位置绕到第一个位置, 形成逻辑上的环状空间, 供队列循环使用,循环队列的定义如队列。

当存储空间的最后一个位置已被使用而要进行入队运算时,只要存储空间第一个位置空闲,便 可将元素加入到第一个位置,即将存储空间的第一个位置作为队尾。采用首尾相接的循环队列结构 后,可以有效地解决假溢出的问题,避免数据元素的移动。 对循环队列操作有以下几种状态: ? 初始时队列空,队首指针和队尾指针均指向存储空间的最后一个位置,即 f=r=m。 ? 入队运算时,尾指针进一,即 r←r+1; if r=m+1 then r←1; 这两条语句可用一条语句替代: r←(r+1) mod m; ? 出队运算时,首指针进一,即 f←f+1;if f=m+1 then f←1; 这两条语句可用一条语句替代: f←(f+1)mod m; ? 队列空时有 f=r。 ? 队列满时有 f=(r+1) mod m。 (为了区分队列空和队列满,改用“队尾指针追上队首指 针” 这 一特征作为队列满标志。这种处理方法的缺点是浪费队列空间的一个存储单元) 循环队列的运算有两种: 1、过程 ADD2(q,x,r)—在循环队列 q 中插入一个新元素 x procedure ADD2 (var q:equeue; x:qtype; var r:integer); begin t←(r+1) mod m; if t=f then writeln(‘full’)
8

{计算插入位置} {队列满}

else begin r←t; q[r]←x; end;{else} end;{ADD2}

{新元素 x 插入队尾}

2 过程 DEL2(q,y,f)—从循环队列 q 中取出队首元素 y procedure DEL2 (var q:equeue; var y:qtype; var f:inteqer); begin if f=r then writeln (‘empty’) {队列空} else begin f←(f +1) mod m;y←q[f]; {取出队首元素} end;{else} end;{DEL2} 四、队列的应用举例 1. 设栈 S 和队列 Q 的初始状态为空,元素 e 1 ,e 2 ,e 3 ,e 4 ,e 5 ,e 6 依次通过栈 S,一个元 素出栈后即进入队列 Q,若出队的顺序为 e 2 ,e 4 ,e 3 ,e 6 ,e 5 ,e 1 ,则栈 S 的容量至少 应该为( ) 。 A)2 B)3 C)4 D)5

§1.4



前面介绍的线性表的操作都是对一个元素进行处理的, 但实际中我们经常要对一串元素进行操 作。如信息检查系统、文字编辑系统、自然语言翻译系统以及音乐分析程序等等,都是以字符串数 据作为处理对象的。随着非数值的广泛应用,字符串的处理将显得越来越重要。 一、串的基本概念 串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这个串的长度。长度为 零的串称为空串,它不包含任何字符。 通常用撇‘’将字符串括起来。例如 ⑴‘x1’ 长度为 2 的串 ⑵‘123’ 长度为 3 的数串 ⑶‘’ 长度为 0 的空串 ⑷‘ ’ 包含一个空白字符(长度为 1)的非空串 假设 s1 和 s2 是两个串: s1=a1??an s2=b1??bm 其中 ai、bi 代表字符(0≤m≤n) 。如果存在整数 i(0≤i≤n-m) ,使得 bj=ai+j j=1‥m 同时成立,则称 s2 是 s1 的子串,又称串 s1 包含串 s2。 串中所能包含的字符依赖于具体机器的字符集,按字符的字符集中的次序可以规定字符的大 小。目前世界上最为广泛的字符集是 ASCII(美国信息变换标准码)和 EBCDIC(扩充的二进制编
9

码、十进制信息码) ,它们都规定数字字符‘0’‥‘9’的字符集是顺序排列的,字母字符‘A’ ‥‘Z’ (‘a’‥‘z’ )的字符集也是顺序排列的,因此用 ord 函数计算字符在字符集中的序号就 有 ord(‘a’)<ord(‘b’)<??<ord(‘z’) ord(‘0’)<ord(‘1’)<??<ord(‘q’) 并且对所有数字 i(0≤i≤9)满足 i=ord(‘i’)-ord(‘0’) 通常可对两个字符 ch1 和 ch2 作比较,所谓 ch1<ch2 的含义就是指 ord(ch1)<ord(ch2),必要时 可以将串按其构成的字符用字符顺序排列,从而定义两个串的大小。例如 ‘a’<’abo’<’x’ ‘012’<’123’<’2’ 程序中使用的串可以分成两种 1、串常数 串常数具有固定的串值,即可以用直接量表示,用以原样输出,亦可以给串常数命名,以便反 复使用时书写和修改方便。例如 const object=’data structure’; {命名串常数} writeln (‘overflow’) {原样输出串常数} 2、串变量 串变量的取值是可以改变的,但必须用名字来识别,说明串变量的方法与其它变量相似。例如 var s:string[30]; 上面定义了一个串变量 s,s 最多能容纳 30 个字符,且顺序存在一个字符数组中,类似于 var s:array[0‥30]of char; 其中 s[0]记载了 s 的实际长度。若 string 类型中省略长度标记,则串长上限为 255 个字符。 二、串的基本运算 PASCAL 中提供了一些串运算的库函数,我们将作以简单的介绍 1、连接运算——函数 concat(s1,[,s2,?,sn]) 其中值参 s1,‥,sn 为 string 类型,函数值为 string 类型。若连接后的串长大于 255,则自动截断 超出部分。 2、求子串——函数 copy(s,i,l) 其中值参 s 为 string 类型,i 和 l 为 integer 类型。函数返回 s 串中第 i 个字符开始、长度为 l 的子串 (string 类型) 。若 i 大于 s 的长度,则回送一个空串;若 l 大于第 i 个字符开始的余串长度,则仅 回送余串。 3、删子串——过程 delete(var s,i,l) 其中变量参数 s 为 string 类型,值参 i、l 为 ingteger 类型。该过程删去 s 中第 i 个字符开始的长度 为 l 的子串,并返回剩余串 s。若 i 大于原串 s 的长度,则不删任何字符;若 l 大于第 i 个字符开始 的余串长度,则删去余串。

10

4、插入子串——过程 insert(s1, var s,i) 变量参数 s 为 string 类型,值参 s1 为 string 类型。该过程将 s1 子串插入空串 s 的第 i 个字符位 置处,并返回插入后的结果 s。若插入后 s 的串长大于 255 个字符,则截断超出部分。 5、求串长——函数 length(s) 值参 s 为 string 类型。该函数返回 s 串的实际长度值(integer 类型) 。 6、搜索子串位置——函数 pos(s1,s2) 值参 s1 和 s2 为 string 类型。 s1 是 s2 的一个子串, 若 则返回 s1 中第 1 个字符在 s2 串中的位置 (integer 类型) ;若 s1 非 s2 的一个子串,则返回 0。 7、数值转换为数串——过程 str(x,var s) 值参 x 为 integer 类型或 real 类型,变量参数 s 为 string 类型。该过程将返回数值 x 对应的数串 s。 8、数串转换为数值——过程 val(s,var v,var c) 值参 s 为 string 类型,变量参数 v 为 integer 类型或 real 类型,变量参数 c 为 integer 类型。该过程 试将 s 串转换成数值 v。若转换成功,则 c 为 0,并返回对应的数值 v;否则 c 为无效字符的序数。 9、字符的大写转换——函数 upcase(ch) 值参 ch 为 char 类型。该函数返回 ch 字符的大写体(char 类型) 三、串的应用实例 1. 字符串“ababacbab”和字符串“abcba”的最长公共子串是( )。 A. abcba B. cba C. abc D. ab E. bcba 2. 设字符串 S=“Olympic” 的非空字串的数目是( ,S ) 。 A.29 B.28 C.16 D.17

E.7

第二章 链式存储结构的线性表
第一章所讨论的线性表的顺序存储结构具有存储数据元素方便的特点, 且插入与删除的算法结 构比较简单。但是也存在着一些固有的缺点: 1.在作插入或删除运算时需要移动大量元素; 2.在给长度变化较大的线性表预先分配存储空间时,必须按最大空间分配,造成内存的无端浪 费; 3.表的容量难以扩充; 线性表的链或存储结构即能够方便地进行插入与删除操作而不必移动大量元素, 又无需预先分 配内存,可以方便地扩充表空间。因此,这种存储结构是线性表的一种有效表示方法。

11

§2.1 单链表

一、单链表的基本概念 在链式存储结构的线性表中, 数据元素的存储空间一般是不连续的。为了能够完整地表示线性 表的逻辑结构,每一个数据元素的表示必须由两部分信息组成 1.数据元素的值; 2.数据元素在线性表中的逻辑位置; 这两部分信息构成线性链表的一个结点。因此,链式存储结构的线性表由若干个结点组成,每 个结点有两个域:一个是数据域 data,用以存放数据元素的值;另一个是指针域 next,用以存放 后件的存储地址。人们一般借助于高级语言的“指针”数据类型来描述这种数据结构。 Type Pointer=↑nodetype; nodetype=record data: elementype; {数据域} next: pointer; {指针域} end; var head:pointer; head 为表的首指针,指向链表的第一个结点。有时在链表的第一个结点前附设一个结点,该结点 称为“哨兵” ,head 指向“哨兵” 。整个链表的存取必须从 head 指针出发,沿每个结点的 next 指 针顺序进行,最后一个结点的 next 指针为“空” (nil) 。因此又称这种链式存储结构为单链表。例 如 存储地址 数据域 指针域 1 li 43 7 qian 13 13 sun 1 19 wang nil 25 wu 37 head 31 zhao 7 31 37 zheng 19 43 zhou 25

在单链表中每个结点的存储地址可以任意分配,即表中元素的存储位置可以不连续且是无序 的,而它们的逻辑顺序由链表中的 next 指针确定:假设线性表 a1?an 采用单链表的存储结构,其 中 p 指针指向 ai 的结点,则 p↑.next 指针指向值为 ai+1 的结点(p↑.next<>nil) 。换句话说 p ↑.data=ai,p↑.next↑.data=ai+1。

12

二、单链表的操作 1、动态建立单链表 设线性表 a1?an。试建立其单链表的存储结构,其中 head 指向单链表的“哨兵” 。 Procedure creat-Link(var head:pointer); begin head←nil; {建立一个空表} for i:=n downto 1 do begin new(p); p↑.data←ai; {生成一个值为 ai 的结点} p↑.next←head; head←p; {将新结点插入单链表第 1 个结点之前} end;{for} new(p); p↑. next←head; head←p; {加 “哨兵” } end;{creak_link} 2、插入操作 在单链表的第 i 个结点前插入元素 x。head 为指向“哨兵”的首指针 pocedure insert_Link (x:elemenetype; i:integer; var head:pointer); begin new(s); s↑.data←x; {生成值为 x 的结点} p←head; j←0; {p 指向“哨兵”} while(p<>nil)and(j<i-1)do {寻找单链表中第 i-1 个结点} begin p←p↑.next; j←j+1; end; {while} if p<>nil then begin {第 i-1 个结点后插入元素 x} s↑.next←p↑.next; p↑.next←s; end{then} else writeln (‘without’); {i>表长} end;{insert_Link}

3、删除操作 设 head 为指向“哨兵”的首指针。删除单链表的第 i 个结点。 Procedure delet_Link(i:integre; var head:pointer); begin p←head; j←0; while (p↑.next<>nil)and(j<i-1)do begin p←p↑.next; j←j+1; end;{while} if p↑.next=nil then writeln (‘without’) else begin q←p↑.next; p↑.next←p↑.next↑.next; dispose(q);
13

{p 指向 “哨兵” } {寻找第 i-1 个结点 p} {i>表长} {删除第 i 个结点 q}

end;{else} end;{delet_Link} 4、读取单链表元素 设 head 为指向“哨兵”的首指针。读取单链表中第 i 个数据元素。 function get_Link(i:integer; var head:Pointer):elementype; begin p←head↑.next; j←1; {p 指向表中第 1 个结点} while (p<>nil)and(j<i)do {顺 next 指针往后寻找第 i 个结点 p} begin p←p↑.next; j←j+1; end;{while} if p=nil {i>表长} then writeln(‘without’) else get_Link←p↑.data; {取得表中第 i 个结点值} end;{get_Link}

三、单链表的应用举例

§2.2

双向循环链表

以上讨论的线性单链表的结点中,只有一个指示后件的指针域 next。因此,从某结点出发, 只能顺 next 指针扩后寻查其它结点。若要寻查某结点的直接前趋,则需从“哨兵”head 出发,另 外,对于空表与第一个结点的处理必须单独考虑,使得空表与非空表的运行不统一。为了克服单链 表的这个缺点,我们引入了另一种链接方式——双向循环链表。 一、双向链表 顾名思义,在双向链表的结点中有两个指针域,其一指向直接后继(next) ;另一个指向直接 前趋(priou) ,可描述如下: Type dupointer=↑node; node=record data:elementype; {数据域} priou, next: dupointer; {前趋指针,后继指针} end; var da: dupointer; {双向链表的 “哨兵” } “哨兵”的 priou 域为空(nil),后继指针 next 指向链表的第一个结点,data 域为空或者设置 特定的值。
14

在双向链表中插入或删除结点,需同时修改两个方向的指针

二、双向循环链表 所谓双向循环链表,除了具备双向链表的特征外,还具有下述特点: 1.双向循环链表中, “哨兵”的 data 域为任意或者根据需要设置,next 域指向线性表的第一 个结点,priou 域指向线性表的最后一个结点,哨兵指针 la 指向“哨兵” ; 2.双向循环链表中最后一个结点的 next 域指向“哨兵” ,即在双同循环链表中,所有结点的指 针构造了一个环状链;

显然,双向循环链表的定义与双向链表一致。对双向循环链表来说,有如下几种操作: 1、构造双向循环链表 la 假设线性表中有 n 个数据元素 a1,??,an。试建立其双向循环链表存贮结构,la 为双向循环 链表的哨兵: procedure creat_dulist (var la:dupointer); begin new (la); la↑.next←la; la↑.priou←la; q←la; {建立空表} for i:=1 to n do {建立双向循环链表} begin new(p); p↑.data←ai; q↑.next←p; p↑.priou←q;q←p; end;{for}
15

q↑.next←la; la↑.priou←q; end; {creat_dulist}

{首尾相接}

2、读取双向循环链表中第 i 个结点的地址 在 la 为“哨兵”的双向循环链表中,确定第 i 个结点的地址。若 i>表长,返回 nil;若 i=表 长+1,则返回哨兵指针 la: function get_dulist (i,la):dupointer; begin p←la↑.next; j←1; {从第1个结点开始搜索} while (p<>la)and(j<i)do begin p←p↑.next; j←j+1; end;{while} if j=i then get_dulist←p else get_dulist←nil; end; {get_dulist} 3、插入操作 双向循环链表的哨兵指针为 la。在该链表的第 i 个元素之前插入元素 x: procedure insert_dulist (x:elementype;i:integer;var la:dupointer); begin {生成新结点 s, 寻找双向循环链表中的第 i 个结点 p} new(s);s↑.data←x;p←qet_dulist(i,la); if p<>nil then begin p↑.priou↑.next←s; {在结点 p 前插入结点 s} s↑.priou←p↑.priou; p↑.priou←s; s↑.next←p; end;{then} else write in (‘without’); end; {insert_dulist} 4、删除操作 双向循环链表的哨兵为 la。删除该链表中的第 i 个结点 q procedure delet_dulist (i:integer;var la:dupointer); begin p←get_dulist (i,la); {寻找双向循环链表中的第 i 个结点 p} if p<>nil then begin {从双向循环链表中删除结点 p } p↑. priou↑. next←p↑. next; p↑. next↑. priou←p↑. priou; disPose(p); end else writeln (‘without’); end;{delet_dulist} 三 双向循环链表的应用实例 1. 在带尾指针(链表指针 clist 指向尾结点)的非空循环单链表中每个结点都以 next 字段的指针
16

指向下一个节点。假定其中已经有 2 个以上的结点。下面哪些说法是正确的: A) 如果 p 指向一个待插入的新结点,在头部插入一个元素的语句序列为: p^.next:= clist^.next; clist^.next:= p; B) 如果 p 指向一个待插入的新结点,在尾部插入一个元素的语句序列为: p^.next:= clist; clist^.next:= p; C) 在头部删除一个结点的语句序列为: p:= clist^.next; clist^.next:= clist^.next^.next; dispose(p); D) 在尾部删除一个结点的语句序列为。 p:= clist; clist:= clist ^.next; dispose(p);

第三章 非线性结构(1)—树
前两章讨论的线性表(包括栈、队列、与串)属于线性结构。在这种结构中,不管其存储方式 如何, 数据元素的逻辑位置之间呈线性关系, 每一个数据元素通常只有一个前件 (除第一个元素外) 和一个后件(除最后一个元素外) 。在实际生活中,可以用线性结构描述数据元素之间逻辑关系的 问题是很广泛的,但也有很多问题不能依靠线性结构来解决,因此在这类问题中,数据元素间的逻 辑关系不能用线性结构明确、方便地描述出来。 例如某学校试图将学生成绩表中的百分制成绩转换成五个等级,其中成绩 0~59 分为不及格, 60~69 分为及格,70~79 分为中,80~89 分为良,90~100 分为优。现有 n 个学生的百分制成绩, 如何将他们的成绩转换成五级分制。 (图 3—1)揭示了一个百分制成绩的判定转换过程。对于这样 一张简单的表,已经不能用线性结构来表示。因为表中数据元素可能有两个后件,它们之间的关系 已经不是线性的了。

至少存在一个结点(数据元素)有多于一个前件或后件的数据结构称为非线性结构。 (图 3— 1)中所示的表是一个非线性结构。由该图可以看出,虽然每一个结点可能有多个后件,但它们的 前件却只有一个(第一个结点无前件) 。这种非线性结构称为树,树表示了数据元素之间的层次关 系,而这种层次关系仿佛像一棵倒长的树。 下面讨论树的基本概念,其中重点讨论的是二叉树。

17

§3.1 树的基本概念及其存储结构

一、树的概念 树是一种常见的非线性的数据结构。树的递归定义如下: 树是 n(n>0)个结点的有限集,这个集合满足以下条件: ⑴ 有且仅有一个结点没有前件(父亲结点) ,该结点称为树的根; ⑵ 除根外,其余的每个结点都有且仅有一个前件; ⑶ 除根外,每一个结点都通过唯一的路径连到根上。这条路径由根开始,而未端就在该结 点上,且除根以外,路径上的每一个结点都是前一个结点的后件(儿子结点) ; 由上述定义可知,树结构没有封闭的回路。

在树中,一个结点包含一个元素以及所有指向其子树的分支,其中除根结点外,有后件的结点 称为分支结点。而没有后件的结点称为树叶。由树的定义可知,树叶本身也是其父结点的子树。如 (图 3.1—1(b) )中,r 为根起点,w,h,e,f,s,m,o,n,j,u 为叶结点;从根 r 到结点 i 的唯一路径为 rcti。 一个结点的子树数目称为该结点的度。在(图 3.1—1(b) )中,结点 i 度为 3,结点 t 的度 为 2,结点 b 的度为 1。显然,所有树叶的度为 0。所有结点中最大的度称为该树的度。 (图 3.1 —1(b) )中的树的度为 3。 树是分层次的。结点所在的层次是从根算起的。根结点在第一层,根的后件在第二层,其余各 层依次类推。即若某个结点在第 k 层,则该结点的后件均处在第 k+1 层。 (图 3.1—1(b) )中的 树共有五层。在树中,父结点在同一层的所有结点构成兄弟关系。树中最大的层次称为树的深度, 亦称高度。 (图 3.1—1(b) )中树的深度为 5。 所谓森林,是指若干棵互不相交的树的集合。如(图 3.1—(b) )去掉根结点 r,其原来的三 棵子树 Ta,Tb,Tc 的集合{Ta,Tb,Tc}就为森林。 所谓有序树是指树中同层结点从左而右排列,其次序不容互换,这样的树称为有序树。

二、树的表示方法和存储结构
树的表示方法很多。例如(图 3.1—1)采用的就是自然界的树形表示法,常用的还有括号表 示法: 先将根结点放入一对圆括号中,然后把它的子树按由左而右的顺序放入括号中,而对子树也采
18

用同样方法处理: 同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。例 如(图 3.1—1(b))可写成如下形式 (r(a(w,x(d(h) ) ,e),b(f) ,c(s,t(i(m,o,n) ,u)) ,j) ) 而树的存储结构有多种,其中使用较多的是链式存储结构。由于树中结点可以有多个元素,所 以可以用多重链表来描述比较方便。所谓多重链表,就是每个结点由数据域和 n(n 为树的度)个指 针域共 n+1 个域组成,其表示方法如下: Const n=树的度; Type treetype=↑node; {结点类型} node=record data:datatype; {数据域} next:array[1‥n] of treetype; {指向各儿子的指针域} end; Var root:treetype; {根结点指针} 例如(图 3.1—1(b))的树,其多重链表为

显然,取树的度作为每个结点的链域数(即指向儿子结点的指针数)虽使各种算法简化,但会 造成存储空间的大量浪费。因为可能有很多结点中存在空链域。容易验证,一棵具有 n 个结点且度 为 K 的树中必存在 n*(k-1)+1 个空链域,因此需要寻找一种恰当的树形式,即要使每个结点的结构 相同、又要尽可能减少存储空间的浪费,方便运算。下面将要看到,用二叉树来表示树,就能达到 这个目的。

§3.2 二叉树

一、二叉树的基本概念和基本性质 1、二叉树的基本概念 二叉树是一种很重要的非线性数据结构,它的特点是每个结点最多有两个后件,且其子树有左 右之分(次序不能任意颠倒) 。下面给出二叉树的递归定义: 二叉树是以结点为元素的有限集,它或者为空,或者满足以下条件: ⑴有一个特定的结点称为根; ⑵余下的结点分为互不相交的子集 L 和 R,其中 R 是根的左子树;L 是根的右子树;L 和 R 又 是二叉树;
19

由上述定义可以看出,二叉树和树是两个不同的概念:树的每一个结点可以有任意多个后件, 且子树可以不分次序(除有序树外) ;而二叉树中每个结点的后件不能超过 2 且子树有左右之分。 我们称二叉树中结点的左后件为左儿子,右后件为右儿子。 前面引入的有关树的一些基本术语对二叉树仍然适用。 (图 3.2—1)列出二叉树的五种基本 形态:

满二叉树和完全二叉树是二叉树的两个特殊形态: 满二叉树: 如果一棵二叉树的任何结点,或者是树叶,或者恰有两棵非空子树,则此二叉树称 作满二叉树。 (例如图(3. 2—2(a))) 可以验证具有 n 个叶结点的满二叉树共有 2n-1 个结点。 完全二叉树:如果一棵二叉树最多只有最下面两层结点度数可以小于 2,并且最下面一层的结点 都集中在该层最左边的若干位置上,则称此二叉树为完全二叉树(例如(图 3.2 —2(b)) )

2、 二叉树的基本性质 下面介绍地叉树的三个主要性质 i-1 性质 1:在二叉树的第 i(≥1)层上,最多有 2 个结点 证明 数学归纳法 i-1 0 ⑴i=1 时只有一个根结点,即 2 =2 =1,结论成立; k-1 ⑵假设第 k(i=k)层上最多有 2 个结点; k-1 ⑶考虑 i=k+1。由归纳假设,在二叉树第 k 层上最多有 2 个结点,而每一个结点的 k-1 (k+1)-1 i 度数最大为 2,因此在第 k+1 层上最多有 2.2 =2 =2 ,结论成立。 综上所述,性质 1 成立。 性质 2:在深度为 k(k≥1)的二叉树中最多有 2 -1 个结点。 证明 i-1 由性质 1,在二叉树第 i 层上最多有 2 个结点,因此深度为 k 的二叉树最多有
k

?
i ?1

k

2 i ?1 ? 2 k ? 1 个结点。

20

性质 3:在任何二叉树中,叶子结点数总比度为 2 的结点多 1。 证明 设 n0—二叉树的叶结点数;n1—二叉树中度为 1 的结点数; n2—二叉树中度为 2 的结点 数; n=n0+n1+n2 (1) 由于二叉树中除了根结点外,其余每个结点都有且仅有一个分支进入。设 B 为进入分支 的总数,因此 n=B+1 (2) 又由于所有的进入分支是由度为 1 和度为 2 的结点射出的,因此又有 B=n1+2n2 (3) 将(3)代入(2)得出 n=n1+2n2+1 (4) 比较(1)和(4) ,得出 n0=n2+1 即叶子数比度为 2 的结点数多 1 二、树或森林转换成二叉树 1、普通有序树转换成二叉树 我们在§3.1 中曾讲过,在用多重链表示普通树时,会浪费存储空间。另外,由于树中各结 点的度各不相同, 因此对树中各结点的搜索比较困难。 在实际应用中, 往往将普通树转化成二叉树, 这种处理是极其有利的。 假设所讨论的普通树为有序树 T,则将其转化成二叉树 T’的规则如下: ⑴T 中的结点与 T’中的结点一一对应; ⑵T 中某结点 N 的第一个儿子结点为 N1,则在 T’中 N1 为对应结点 N 的左儿子结点; ⑶T 中某结点 N 的第一个儿子结点 N1 以后的其它子结点,在 T’中被依次链接成一串开始于 N1 的右儿子结点; 由上述转化规则可以看出,一棵有序树转化成二叉树的根结点是没有右子树的,并且除保留每 个结点的最左分支外,其余分支应去掉,然后从最左的儿子开始依次连接该结点的全部儿子。例如 将(图 3.2—3(a))所示的普通有序树转换成二叉树(图 3.2—3(b))

2、森林转换为二叉树 设森林 F={T1,?Tm}由 m 棵互不相交的普遍有序树组成。 我们可以按下述规则将森林 F 转换成一 棵二叉树 B={root,LB,RB}: ⑴若 F 为空(m=0) ,则 B 为空树;
21

⑵若 F 非空(m≠0) ,则 B 的根 root 即为森林中第一棵树的根 root(T1);B 的左子树 LB 是从 T1 的根结点的子树森林 F1={T11,T12,?T1k}转换而成的二叉树;其右子树 RB 是从森林 F2={T2, T3,?,Tm}转换成的二叉树。 例如

由此可见,森林转换成二叉树的方法为 ⑴将各棵树的根相连; ⑵将森林中的每棵树转换成相应的二叉树; 0 ⑶以第一棵树为轴心,顺时针粗略地旋转 90 ; 三、二叉树的存储结构 二叉树的存储结构有两种形式 1、 顺序存储结构 将每个结点依次存放在一维数组中,用数组下标指示结点编号,编号的方法是从根结点开始编 号 1,然后由左而右进行连续编号。每个结点的信息包括 数据值: data 父结点编号: prt 左儿子结点编号: lch 右儿子结点编号: rch 满二叉树和完全二叉树一般采用顺序存储结构 Const m=树中结点数上限; Type node=record {结点类型} data:datatype; {数据值} prt,lch,rch:0‥m; {父结点、左儿子、右儿子编号} end; treetype=array[1‥m] of node; {二叉树的顺序表类型} Var Tree:treetype; {二叉树} 例如采用数组 tree 存储二叉树

22

下面我们将普通有序树转换成二叉树,并使用顺序存储结构 Tree 存储转换结果。普通有序树的输 入信息含 n 行,其中第 i 行(1≤i≤n)的元素依次为 结点 i 的数据值 ai。以后各元素为结点 i 的儿子序列,以 0 结束。若 ai 后仅含一个 0,则说明 结点 i 为叶子。 例如(图 3.2-3(a) )的多叉树对应的输入信息为 ‘r’ 2 3 4 0 ‘a’ 5 6 0 ‘b’ 7 0 ‘c’ 8 9 10 0 ‘w’ 0 ‘x’ 11 12 0 ‘f’ 0 ‘s’ 0 ‘t’ 13 14 0 ‘u’ 0 ‘d’ 15 0 ‘e’ 0 ‘i’ 16 17 18 0 ‘j’ 0 ‘h’ 0 ‘m’ 0 ‘o’ 0 ‘h’ 0 转换过程如下: fillchar(tree,sizeof(tree) ; ,0) {二叉树初始化} i←1; {从结点 1 开始输入} while i≤n do {若多叉树信息末输入处理完,则重复} begin 读结点 i 的数据值 ai;tree[i] .data←ai; 读结点 i 的第一个儿子序号 j; if j<>0 then {若结点 j 非叶子} begin tree[i].lch←j;tree[j].prt←i; {结点 j 作为结点 i 的左儿子} p←j; {从结点 j 出发转换其它兄弟结点}

23

repeat 读结点 i 的下一个儿子序号 j; if j<>0 then begin tree[p].rch←j;tree[j].prt←p; {结点 j 作为结点 p 的右儿子} p←j; end;{then} until j=0; {直至处理完结点 i 的所有儿子信息} end;{then} i←i+1;换行; {准备输入结点 i+1 的儿子信息} end;{while} 例如(图 3.2-3(a) )的多叉树经上述转换运算后得出的 tree 数组如下: data prt lch rch 1 ‘r’ 0 2 0 2 ‘a’ 1 5 3 3 ‘b’ 2 7 4 4 ‘c’ 3 8 0 5 ‘w’ 2 0 6 6 ‘x’ 5 11 0 7 ‘f’ 3 0 0 8 ‘s’ 4 0 9 9 ‘t’ 8 13 10 10 ‘u’ 9 0 0 11 ‘d’ 6 15 12 12 ‘e’ 11 0 0 13 ‘i’ 9 16 14 14 ‘j’ 13 0 0 15 ‘h’ 11 0 0 16 ‘m’ 13 0 17 17 ‘o’ 16 0 18 18 ‘n’ 17 0 0

2、 链式存储结构 对于一般的二叉树,通常采用链式分配,即用二重链表表示一般的二叉树。这种链式分配即可 以采用静态数据结构(数组) ,又可以采用动态数据结构(指针) 。人们一般采用后者。由于二叉树 中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链表中每个结点应有三个域: 值域: data 左指针域: lch 右指针域: rch 这种链表也称为二叉链表。二叉链表头指针 bt 指向二叉树的根结点 Type bitrpetr=↑bnode; {结点指针类型} benode=record {结点类型} data:datatype; {值域} lch,rch:bitreptr; {左指针域和右指针域} end; Var bt: bitreptr; {头指针}
24

例如用(图 3.2-6(b) )所示的二叉链表存储二叉树(图 3.2-6(b)。 )

四、树的遍历 1、二叉树的遍历 所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。 在访问到每个结 点时,可以取出结点中的信息,亦可以对结点作其它的处理,对于线性结构来说,遍历并非难事, 但对二叉树来说,由于它是一种非线性结构,必须要找到一种完全而有规则的遍历方法,通过遍历 得到二叉树中各个结点信息的线性序列。 如果用 L、D、R 分别表示遍历左子树、访问根结点、遍历右子树,则对二叉树的遍历可以有下 列六种组合: LDR、 LRD、 DLR、 DRL、RDL、 RLD 若再限定先左后右的次序,则只剩下三种组合 LDR、 LRD、 DLR 这三种遍历规则分别称为中序遍历。后序遍历和前序遍历。下面分别介绍这三种遍历的方法。 在讲解过程中,二叉树的存储采用动态的二重链表形式。 为了方便叙述,我们以(图 3.2-7)为例,解释三种遍历规则。

⑴前序遍历 前序遍历的规则如下: 若二叉树为空,则退出。否则 ⑴访问处理根结点; ⑵前序遍历左子树;
25

⑶前序遍历右子树; 例如对于如(图 3.2—7)所示的二叉树,前序遍历的过程为:先访问根结点 A,再遍历其左 子树,然后遍历其右子树。在遍历其左子树时,也按照前序规则,即先访问根结点 B,然后遍历其 左子树,最后遍历右子树,?,依次类推,直到根结点 A 的左子树的所有结点全部被访问完毕;再 以同样的规则访问 A 的右子树中的所有结点;最后可以得到如下的前序遍历序列(简称前序序列) a b d e h i c f g 算法如下: procedure preorder(bt:bitreptr); begin if bt<>nil then begin 访问处理 bt>↑.Data; preorder(bt↑.lch); {递归遍历左子树} preorder(bt.↑rch); {递归遍历右子树} end;{then} end;{preorder} ⑵中序遍历 中序遍历的规则如下: 若二叉树为空,则退出;否则 ⑴中序遍历左子树; ⑵访问处理根结点; ⑶中序遍历右子树; 若中序遍历(图 3.2—7)中的二叉树,可以得到如下的中序序列: d b h e i a f c g 算法如下: procedure inorder(bt:bitreptr); begin if bt<>nil then begin inorder(bt↑.lch); 访问处理 bt↑.data; inorder(bt↑.rch); end;{then} end;{inorder} ⑶后序遍历 后序遍历的规则如下: 若二叉树为空,则退出;否则 ⑴后序遍历左子树; ⑵后序遍历右子树; ⑶访问处理根结点; 若后序遍历(图 3.2—7)中的二叉树,可以得到如下的后序序列 d h i e b f g c a

{递归遍历左子树} {递归遍历右子树}

26

算法如下: procedure postorder (bt:bitreptr); begin if bt<>nil then begin postorder (bt↑.lch); postorder(bt↑.rch); 访问 bt↑.data; end;{then} end;{postorder}

{递归遍历左子树} {递归遍历右子树}

§3.3 树的应用举例

第四章 非线性结构(2)—图
图是较线性表和树更为复杂的一种数据结构。 在这种数据结构中, 数据结点间的联系是任意的, 因此它可以更广泛地表示数据元素之间的关系。可以说,线性表和树是图的特例。实际生活中的许 多事物可以抽象成图的形式。例如(图 4.—1)是一个公路网。为了方便地表示交通信息,我们 用结点代表城市,每条边代表连接两个城市间的公路,边长的权表示公路长度。这种公路网的表现 形式就是属于图的数据结构。

图结构在人工智能、数学、物理、化学、计算机科学等许多领域被广泛应用。奥林匹克信息学 竞赛的许多试题,亦需要用图来描述数据元素间的联系。

§4.1 图的基本概念和存储结构

一、图的基本概念 如果数据元素集合 D 中的各元素之间存在任意的前后件关系 R,则此数据结构 G=(D,R)称为 图。如果将数据元素抽象为结点,元素之间的前后件关系用边表示,则图亦可以表示为 G=(V,E) ,
27

其中 V 是结点的有穷(非空)集合,E 为边的集合。如果元素 a 是元素 b 的前件,这种前后件关系 对应的边用(a,b)表示,即(a,b)∈E。 在图 G=(V,E)中,如果对于任意的 a,b∈V,当(a,b)∈E 时,必有(b,a)∈E(即关系 R 对称) ,对称此图为无向图;如果对于任意的 a,b∈V,当(a,b)∈E 时 ,(b,a)∈E 未必成立, 则称此图为有向图。 在有向图中, 通常用带箭头的边连接两个有关联的结点 (方向由前件指向后件) ; 而对一无向图,用不带箭头的边连接两个有关联的结点。例如(图 4.1—(a))为无向图, (图 4.1 —(b))为有向图。

在具有 n 个结点的无向图中,边的最大数目为

n * (n ? 1) 。而边数达到最大值的图称为无向 2

完全图。 (图 4.1—(A))所示的图是无向完全图。 在无向图中一个结点相连的边数称为该结点的度,例如(图 4.1—1(A))中结点 1、结点 2、 结点 3、结点 4 的度分别为 1。有向图中一个结点的后件个数称为该结点的出度,其前件个数称为 该结点的入度。一个结点的入度和出度之和称为该结点的度。图中结点的最大度数称为图的度。例 如(图 4.1—1(B))中结点 1 的出度和入度分别为 1,结点 1 和的结点 1 度都为 2。整个图的度为 2。 在图 G=(V,E)中,如果对于结点 a,b,存在满足下述条件的结点序列 x1??xk(k>1) 1 x1=a,xk=b 2 (xi,xi+1)∈E i=1‥k-1 则称结点序列 x1=a,x2,?,xk=b 为结点 a 到结点 b 的一条路径,而路径上边的数目 k-1 称为该路 径的长度,并称结点集合{x1,?,xk}为连通集。如果一条路径上的结点除起点 x1 和终点 xk 可以相 同外,其它结点均不相同,则称此路径为一条简单路径。 (图 4.1—1(A))中 v1→v2→v3 是一条简 单路径,v1→v3→v4→v1→v3 不是简单路径。x1=xk 的简单路径称为回路(也称为环) 。例如(图 4.1 ——1(B))中,v1→v2→v1 为一条回路。 在一个有向图或无向图中, 若存在一个结点 w, 它与其他结点都是连通的, 则称此图为有根图, 结点 w 即为它的根。 (图 4.1—1(A))为有根图,v1、v2、v3、v4 都可以作为根; (图 4.1—(B)) 亦为有根图,v1 或 v2 为它的根。若对于有向图的任意两个结点 vi、vj 间(vi≠vj) ,都有一条从 vi 到 vj 的有向路径,同时还有一条从 vj 到 vi 的有向路径,则称该有向图是强连通的。有向图中强连 通的最大子图称为该图的强连通分支。 (图 4.1—1(B))不是强连通的,因为 v3 到 v2 不存在路径。 它含有两个强连通分支,如(图 4.1—2)所示。

28

对于无向图而言,若其中任两个结点之间的连通,则称该图是连通的。一个无向图的连通分支 定义为此图的最大连通子图。 (图 4.1—1(A))所示的图是连通的,它的最大连通子图即为其本身。 二、图的存储结构 由于图的结构复杂且使用广泛,所以其存储结构也是多种多样的,对应于不同的应用问题可有 不同的方法存储。这里,仅介绍其中两种: 1、图的相邻矩阵表示法 相邻矩阵是表示结点间相邻关系的矩阵。若 G=(V,E)是一个具有 n 个结点的图,则 G 的相 邻矩阵是如下定义的二维数组 A,其规模为 n*n

?1(或权) ? A[i, j ] ? ? ?0 (??) ?

(v i , v j ) ? E (v i , v j ) ? E

(图 4.1—3)中的图 G1 和图 G2 对应的相邻矩阵分别为 A1、A2:

?0 ? ?3 A1= ? 5 ? ?8 ?0 ?

3 5 8 0 ? ? 0 6 4 11 ? 6 0 2 0 ? ? 4 2 0 10 ? 11 0 10 0 ? ?

?0 ? ?1 A2= ? 0 ? ?1 ?0 ?

1 0 0 0? ? 0 0 0 1? 1 0 1 0? ? 0 0 0 0? 0 0 1 0? ?

由相邻矩阵 A1 和 A2 可以明显地看出,无向图的相邻矩阵 A1[i,j]=A1[j,i](1≤i,j≤n)且对角 线上的 A[i,i]均为 0(或 ? ? ) 。正因为如此,在实际存储相邻矩阵时只需存储其上三角(或下三角) 的元素。因此具有 n 个结点的无向图,其相邻矩阵的存储容量可节约至

(n ? 1)n 。而有向图的相邻 2

矩阵中 A2[i,j]不一定与 A2[j,i](1≤i,j≤n)相同,且图中出现自反边时其对角线上的 A2[i,i]也不 一定是 0(或 ? ? ) 。 用相邻矩阵表示图,容易判定任意两个结点之间是否有边相联,并容易求得各个结点的度数。 对于无权无向图的相邻矩阵,第 i 行元素值的和就是 Vi 的度数;对于无权有向图的相邻矩阵,第 i 行元素值的和就是 Vi 的出度,第 i 列元素值的和就是 Vi 的入度;对于有权无向图的相邻矩阵,第 i 行(或第 i 列)中元素值<>0 的元素个数就是 Vi 的度数;对于有权有向图的相邻矩阵,第 i 行中 元素值<>0 的元素个数就是 Vi 的出度;第 i 列元素值<>0 的元素个数就是 Vi 的入度。在无权有向 图或无向图中,判定两个结点 Vi、Vj 之间是否存在长度为 m 的路径,只要考虑 Am=A*A*??*A (m 个 A 矩阵相乘后的乘积矩阵)中(i,j)的元素值是否为 0 就行了。
29

2、图的邻接表表示法 用相邻矩阵表示图,占用的存储单元数只与结点数有关而与边数无关。一个含 n 个结点的图, 若其边数比 n2 多得多,那么其相邻矩阵是一个稀疏矩阵,占用许多空间来存储 0(或 ? ? )当然是 无端浪费。 如果用邻接表表示法来存储图, 则占用的存储单元既与图的结点数有关, 又与边数有关。 同样是 n 个结点的图,如果边数少,则占用的存储单元也少。 同邻接表法表示图需要保存一个顺序存储的结点表和 n 个边表(每个边表为一个单链表,存储 与一个结点相连的所有边的信息) 。结点表的每个表目对应于图的一个结点,包括: ⑴结点信息,即 ? 与该结点相连的边数(m) ; ? 访问标志(visited) ; ⑵边表的首指针(firstarc) 。图中每个结点都有一个边表,其中每一个结点对应于与该结点 相关联的一条边,包括 ? 与此边相关联的另一个结点序号(V) ; ? 若为带权图的话,该边的权值(W) ; ? 指向边表的下一个结点的后继指针(nextarc) ; 邻接表的定义如下: const max=图的结点数上限; Type arcptr=↑arcnode; {边表的指针类型} arcnode=record; {边表的结点类型} v:integer; {关联该边的另一端点序号} nextar:arcptr; {边表的后继指针} w:real; {该边的权值} end; vexnode=record {结点表的表目类型} m:integer; {与该结点相连的边数} visited:boolean; {访问标志} firstarc:arcptr; {边表的首指针} end; adjlist=array[1‥max]of vexnode; {邻接表类型} var dig:adjlist; {邻接表} n,e :integer; {结点数和边数} 用邻接表结构存贮图的过程如下: 读 n 和 e; for i:=1 to n do begin with dig[i] do begin m←0;firstarc←nil;visited←false; end;{with} end;{for}

{结点表初始化}

30

for i:=1 to e do begin 读第 i 条边<vj,vk>关联的结点序号 j,k 和该边的权 Wjk; dig[j].m←dig[j].m+1; new[q]; with q↑do begin v←k;w←wjk;nextarc←dig[j].firstarc; end;{with} dig[j].firstarc←q; end;{for} 例如(图 4.1—4(a))中有向图 G 对应的邻接表表示如(图 4.1—4(b))

用相邻表表示图,不仅是当 e<<n2 时节省了存储单元,而且因为与一个结点相关联的所有边都 链接在同一个边表里,也给运算提供了方便。

§4.2 图的遍历和生成树

一、图的遍历 给出一个图 G 和其中任意一个结点 V0,从 V0 出发系统地访问 G 中所有结点,每一个结点被访 问一次,这就叫图的遍历。遍历图的结果是按访问顺序将结点排成一个线性序列。遍历图的算法是 求解图的连通性问题、拓朴排序和求关键路径等算法的基础。通常有两种遍历方法:深度优先搜索 和广度优先搜索,它们对无向图和有向图都适用。 1、深度优先搜索 深度优先搜索类似于树的前序遍历,是树的前序遍历的推广。 假设初始时所有结点未曾被访问。深度优先搜索从某个结点 V0 出发,访问此结点。然后依次 从 V0 的未被访问的邻接点出发深度优先遍历图, 直至图中所有和 V0 有路径相连的结点都被访问到。 若此时图中尚有结点未被访问,则另选一个未曾访问的结点作起始点,重复上述过程,直至图中所 有结点都被访问为止。换句话说,深度优先搜索遍历图的过程是以 V0 为起始点,由左而右,依次 访问由 V0 出发的每条路径。 例如以(图 4.1—4(a))中的有向图 G 为例,从 v3 出发,按深度优先搜索的顺序遍历,得到 的结点序列是
31

v3→v2→v1→v5→v4 从 vi 出发,深度优先搜索的递归过程如下: procedure dfs (i:integer); begin 访问处理结点 i; dig[i].visited←true; {置 vi 已访问标志} q←dig[i]. firstarc; {按深度优先搜索的顺序遍历 vi 所有子树} while q<>nil do begin if dig[q↑.v].visited=false then dfs(q↑.v); q←q↑.next arc; end;{while} end;{dfs} 调用一次 dfs(i),可按深度优先搜索的顺序访问处理结点 i 所在的连通分支(或强连通分支) 。整个 图按深度优先搜索顺序遍历的过程如下: procedure traver1; begin for i:=1 to n do dig[i].visited←false; {置所有结点未访问标志} for i:=1 to n do if dig[i].visited=false then dfs[i]; {深度优先搜索每一个未访问的结点} end;{traver1} 2、广度优先搜索 广度优先搜索类似于树的按层次遍历的过程。 假设从图中某结点 v0 出发,在访问了 v0 之后依次访问 v0 的各个未曾访问的邻接点,然后分别 从这些邻接点出发按广度优先搜索的顺序遍历图,直至图中所有可被访问的结点都被访问到。若此 时图中尚有结点未被访问,则任选其中的一个作起始点,重复上述过程,直至图中所有结点都被访 问到为止。换句话说,按广度优先顺序搜索遍历图的过程是以 v0 为起始点,由近及远,依次访问 和 v0 有路径相连且路径长度为 1,2,3??的结点。 假如以(图 4.1—4(a))中的有向图为例,从 v3 出发按广度优先搜索的顺序遍历,得到的结点 序列是 v3→v2→v4→v1→v5 由于队列“先进先出”的存取规则与广度优先搜索的遍历顺序相吻合,因此使用了一个工作队 列 q,按访问的先后顺序存储被访问过的结点序号。从结点 vi 出发广度优先搜索的过程如下: procedure bfs (i:integer); begin 访问处理结点 i; dig[i].visited←true; {置 vi 已访问标志} 结点 i 进入队列 q; while 队列 q 非空 do begin 从队列 q 中移出队首元素 v; p←dig[v].firstarc; {依次访问 v 的所有相邻结点} while p<>nil do begin

32

if dig[p↑.v].visited=false then begin 访问 p↑.v; dig[p↑.v].visited←true; p↑.v 进入队列 q; end;{then} p←p↑.nextarc; end;{while} end;{while} end;{bfs} 调用一次 bfs(i)可按广度优先搜索的顺序访问处理结点 i 所在的连通分支(或强连通分支) 。整个图 按广度优先搜索顺序遍历的过程如下: procedure traver2; begin for i:=1 to n do dig[i].visited←false; {置所有结点未访问标志} for i:=1 to n do if dig[i].visited=false then bfs[i];{广度优先搜索每一个未访问的结点} end;{traver2}

二、生成树 1、图的生成树 若图是连通的无向图或强连通的有向图,则从其中任一个结点出发,调用 dfs 或 bfs 后便可以 系统地访问图中所有结点;若图是有根的有向图,则从根出发通过调用 dfs 或 bfs 亦可以系统地访 问遍历所有结点。 在这种情况下,图中的所有结点加上遍历过程中经过的边所构成子图称作图的生 成树。例如

对于不连通的无向图和不是强连通的有向图,若无根,或者若从根外的任意结点出发,一次调 用 bfs 或 dfs 后一般不能系统地访问遍历所有结点,而只能得到以出发结点为根的连通分支(或强 连通分支)的生成树。要访问其它结点需要从没有访问过的结点中找一个结点作为起始点,再次调 用 bfs 或 dfs,这样得到的是生成森林。例如(图 4.2—1(b))所示的有向图 G2 非连通,v3 是该图
33

的根。我们分别从 v1、v3 出发作二次深度优先搜索,得到 G2 的生成森林

由此可以看出,图的生成树不是唯一的,不同的搜索方法可以得出不同的生成树,即便是同一 种搜索方法,但出发点不同亦可导致不同的生成树。具有 n 个结点的带权连通图,其对应的生成树 有 n-1 条边。由此引出这样一个问题:如何找一个带权连通图的最小生成树,即各边的权的总和为 最小的生成树。这个问题很有实际意义。例如(图 4.2—3(a))所示的连通图为 6 个城市间的交通 网,边上的权是公路造价。现在要用公路把 6 个城市联系起来,这至少需要修筑 5 条公路。如何设 计可使得这 5 条公路的总造价最少呢?这就是所谓的最小生成树问题。

2、计算最小生成树 下面我们来讨论最小生成树的算法。 ⑴数据结构 A—连通图的相邻矩阵。若 Vi 包括进生成树,则 A[i,i]←1;若<vi,vj>包括进生成树,则 A[i,j]←-A[i,j](1≤i,j≤结点数 n)。算法结束时,A 矩阵中为负的元素指示最小生成树 的边。 t—存储相邻矩阵 A 的下三角元素。其中 t[i*(i-1)/2+j]存储 A[i,j](j≤i)。显然若 t[i*(i+1)/2]=1, 则 vi 在生成树中;若 t[i*(i-1)/2+j]取负时,表明(i,j)边在生成树中。t 数组的长度为

n * (n ? 1) 。 2
min—当前待扩展的最小权。 ⑵构造最小生成树 从任意结点开始(不妨设为 vn)构造最小生成树:首先把这个结点包括进生成树里,然后在那 些其一个端点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的一条边,并把这条 边、包括不在生成树的另一端点包括进生成树,?。依次类推,直至将所有结点都包括进生成树为 止。当有两条具有同样最小权的边可供选择时,选哪条都行。因此最小生成树的形式不是唯一的。 例如(图 4.2—3(b))和(图 4.2—3(c))就是(图 4.2—3(a))的两棵形式不同的最小生成树,但 它们权的总和相等。 我们可以通过反证法证明上述算法的正确性:

34

假设 vx,vy∈V,(vx,vy)∈E,vx∈最小生成树 T’,vy ? 最小生成树 T’,(vx,vy)的权值在待扩 展边集中最小,而最终生成的最小生成树中并不包含这条边。由于 T’是连通的,因此有从 vx 到 vy 的路径 vx, vy。 (vx, y) ?, 把边 v 加入T’中得到一个回路 vx?vy, x。 v 子路径 vx?vy 中必有边 e’=(vp, vq),其中 vp∈T’,vq ? T’,由条件可知 W(e’)>W(e)。从回路中去掉 e’,回路打开,成为另一棵生 成树 T”且各边权和不大于 T’的各边权和,因此 T”是一棵包括边(vx,vy)的最小生成集,与假 设矛盾。 下面给出构造最小生成树的算法: fillchar(t,sizeof(t),∞) ; for i:=1 to n do t[i*(i+1)/2]←0; {所有结点未包括进生成树} for i:=1 to 边数 e do {输入相邻矩阵的下三角元素} begin 读第 i 条边<vx,vy>; if x>y then t[x*(x-1)/2+y]←wxy else t[y*(y-1)/2+x]←wxy; end{for} t[n*(n+1)/2]←1; {vn 进入最小生成树} for k:=2 to n do {顺序构造最小生成树的 n-1 条边} begin min←∞; for i:=1 to n do {搜索那些其一个端点已在生成树里、另一端点还未在生成树里的边} if t[i*(i+1)/2]=1 {若 vi 在生成树中} then begin for j:=1 to n do if t[j*(j+1)/2]=0 {若 vj 不在生成树中} then begin if j<i then l←i*(i-1)/2+j {计算(i,j)元素在 t 中的位置} else l←j*(j-1)/2+i; if t[l]<min then {若 el=<vi, j>的权目前最小, v 则记下} begin min←t[l];p←l;q←j;end;{then} end;{then} end;{then} t[q*(q+1)/2]←1; t[p]←-t[p]; {vq 和相连的权最小的边 el 加入最小生成树} end;{for} for i:=2 to n do for j:=1 to i-1 do if t[i*(i-1)/2+j]<0 then 输出最小生成树的边(i,j) ;

§4.3 最短路径问题
这一章节讲一个比较简单但又是很重要的问题—最短路径问题。 这个问题有着大量的生产实际 的背景。事实上大至海陆空各种运输,小至一个人每天上班,都会遇到这一问题。甚至有些问题从 表面上看与最短路径问题没有什么关系, 却也可以归结为最短路径问题。 下面就举一个这样的例子:
35

一个人带了一只狼、一只羊和一颗白菜想要过河。河上有一只独木船,每次除了人以外,只能 带一样东西,另外如果人不在旁时狼就要吃羊,羊就要吃白菜。问应该怎样安排渡河,才能做到即 把所有东西都带过河,而且在河上来回的次数又最少? 我们设变量 M 代表人,W 代表狼,S 代表羊,V 代表白菜。开始时设人和其它三样东西在河 的左岸,这种情况用 MWSV 表示。 我们用一个集合表示目前左岸的情况,很显然,可能出现的情况有 16 种: [MWSV] [MWS] [MWV] [MSV] [WSV] [MW] [MS] [MV] [WS] [WV] [SV] [M] [W] [S] [V] [Φ ] 删除下列 6 种可能发生狼吃羊、羊吃白菜的情况: [WSV] [MW] [MV] [WS] [SV] [M] 现在我们就来构造一个图 G,它的结点就是剩下的 10 种情况。G 中的边是按下述原则来连的: 如果甲经过一次渡河可以变成情况乙,那么就在情况甲与情况乙之间连一条河。

作出了图 G 以后,渡河的问题就归结为下述问题了: “在 G 中找一条连接结点 MWSV 与Φ , 并且包含边数最少的路” 。如果我们设 G 的与各边的长度都是 1,那么也可以把渡河问题归结为: “找一条连接 MWSV 与Φ 的最短路” 。把问题转化为图的问题后,就可用一种系统的方法解决,而 不是通常人们所用的凑的方法和凭经验的方法。 下面,我们可以给最短路径问题下一个抽象的定义: 设 G=(V,E)是一个有向图,它的每一条边(U,V)∈E都有一个权 W(U,V) ,在 G 中指定 一个结点 V0,要求把从 V0 到 G 的每一个结点 Vj(VJ∈V)的最短有向路找出来(或者指出不存在从 V0 到 Vj 的有向路,即 V0 不可达 Vj) 。 在上述定义中,由于源结点 V0 是给定的,因此我们又形象地称为单源最短路径问题。当然最短 路径问题远不止上述一种,但它们一般都可用单源问题的算法来解决。例如: 1、单目标最短路径问题 找出每一个结点 VJ(VJ∈V)到某指定结点 Vs 的每条最短路径。把图中的每条边的方向反向,我们 就可以把这一问题变成单源最短路径问题; 2、单对顶点间最短路径问题 对于给定结点 U 和 V, 找出一条从 U 到 V 的最短路径。 如果我们解决了源结点为 U 的单源问题, 则这问题自然获得了解决。目前还没有一种比单源算法更快的算法来解决这一问题; 3、每对结点间的最短路径问题 对于每对结点 U 和 V 找出从 U 到 V 的最短路径。 我们可以将每个结点作为源点运行一次单源算 法就可以解决这一问题。但是,如果采用另一种算法(floyd 算法) ,运行的效率将更高。我们将 对该算法作以介绍 一、计算单源最短路径 1、算法的基本思路 解决单源最短路径的基本思想是把图中所有结点分为两组
36

第一组:包括已确定最短路径的结点; 第二组:包括尚未确定最短路径的结点; 我们按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至 v0 可达的所有结点都包含 于第一组。在这个过程中,总保持从 v0 到第一组各结点的最短路径长度都不大于从 v0 至第二组任 何结点的路径长度。另外,每一个结点对应一个距离值。第一组结点对应的距离值就是由 v0 到此 结点的最短路径长度;第二组结点对应的距离值就是 v0 经由第一组结点(中间结点)至此结点的 最短路径长度。具体作法是: 初始时 v0 进入第一组,v0 的距离值为 0;第二组包含其它所有结点,这些结点对应的距离值这 样确定(设 vi 为第二组中的结点)

?w0i disti ? ? ??

(v 0 , v i ) ? E (v 0 , v i ) ? E

然后每次从第二组的结点中选一个其距离值为最小的结点 vm 加到第一组中。每往第一组加入一个 结点 vm,就要对第二组的各结点的距离值作一次修正(设 vi 为第二组的结点) : 若加进 vm 做中间结点使得 v0 至 vi 的路径长度更短(即 vi 的距离值>vm 的距离值+Wmi) ,则要 修改 vi 的距离(vi 的距离值←vm 的距离值+Wmi) 。修改后再选距离值最小的一个结点加入到第一组 中,?。如此进行下去,直至第一组囊括图的所有结点或再无可加入第一组的结点存在。下面,我 们来证明这个算法: 显然,初始时对两个组的划分及各结点距离值的确定符合上述基本思想。因此要证明算法正确 性,关键是证明每次往第一组加入结点 vm 后,其两个组的划分及结点距离值仍然符合要求。也就 是要证明第二组中距离值最小的结点 vm,其距离值为 v0 到 vm 的最短路径长度,且 vm 就是第二组 中路径长度最小的结点。我们来证明这两点: ⑴ 若 vm 的距离值不是从 v0 到 vm 的最短路径长度,另有一条 v0 经由第二组某些结点(其中第一个 结点设为 vs)到达 vm 的路径,其长度比 vm 的距离值更小,即 vs 的距离值<v0 经由 vs 到 vm 的最短路径长度<vm 的距离值 与 vm 是第二组中距离值最小的结点矛盾。所以 vm 的距离值就是从 v0 到 vm 的最短路径长度。 ⑵设 vx 是第二组中除 vm 外的任何其它结点。 v0 至 vx 的最短路径上的中间结点为第一组的结点, 若 由距离值的定义可知,其路径长度势必大于等于 v0 至 vm 的最短路径长度;若 v0 至 vx 的最短路 径不仅包含第一组的结点为中间结点。设路径上第一个在第二组的中间结点为 vy,则 v0 至 vy 的路径长度就是 vy 的距离值,已大于等于 v0 至 vm 的最短路径长度,那么 v0 到 vx 的最短路径长 度当然也不会小于 v0 到 vm 的最短路径长度了,所以 vm 是第二组中最短路径为最小的结点。 2、变量说明 下面给出算法中的变量说明 设 n—图的结点数; adj—有向图的相邻矩阵。其中

?0 adj[i, i ] ? ? ?1 ?wij adj[i, j ] ? ? ??

结点i在第二组; 结点i在第一组; (i, j ) ? E (i, j ) ? E

(1≤i,j≤n,i≠j) dist—最短路径集合。其中

37

dist[i].pre—在 v0 至 vi 的最短路径上,vi 的前趋结点序号; dist[i].length—v0 至 vI 的最短路径长度,即 vi 的距离值; (1≤i≤n) Const n=图的结点数; Type path=record length:real; pre:0‥n; end; var adj:array[1‥n,1‥n] of real dist:array[1‥n] of path;

{路径集合的结点类型} {距离值} {前趋结点序号}

{相邻矩阵} {路径集合}

3、算法流程 计算单源最短路径的过程如下: fillchar(adj, sizeof(adj), 0); {建立相邻矩阵 adj} for i:=1 to n do for j:=1 to n do if(i,j)∈E then adj[i,j]←wij else adj[i,j]←∞; for i:=1 to n do {路径集合初始化} begin dist[i].length←adj[v0,i]; if dist[i].length<>∞ then dist[i].pre←v0 else dist[i].pre←0; end;{for} adj[v0,v0]←1; {源结点 v0 进入第一组} repeat min←∞; u←0; for i: to n do =1 {从第二组中找距离值最小的结点 u} if (adj[i,i]=0)and(dist[i].length<min) then begin u←i; min←dist[i].length; end;{then} if u<>0 {第二组中存在一个距离值最小的结点} then begin adj[u,u]←1; {结点 u 进入第一组} for i:=1 to n do {修正第二组中 u 可达的结点距离值} if (adj[i,i]=0)and(dist[i].length>dist[u].length+adj[u,i]) then begin dist[i].length←dist[u].length+adj[u,i]; dist[i].pre←u; end;{then}

38

end;{then} until u=0;

{直至 n 个结点全部加入第一组为止}

算法结束时,沿着结点 vi 的 pre 指针回溯,便可确定 v0 至 vi 的最短路径: procedure print(i:integer); begin if i=v0 then 输出结点 v0 else begin print(dist[i].pre); 输出结点 i 和 v0 至 vi 的最短路径长度 dist[i].length; end;{else} end;{print} 显然递归调用 print[1],?,print[n]后,可得知 v0 至所有结点的最短路径。 二、计算每一对结点间的最短路径(FLOYD 算法) 1、floyd 算法的描述 给出一个带权有向图,要求第一对结点间的最短路径,解决这个问题的一个方法是执行 n 次单 源算法,每次以一个结点为起始点,求得该结点至其它结点的最短路径。反复执行了 n 次单源算法 后,便可求出每对结点间的最短路径。总的执行时间为 0(n3)。下面我们介绍另一种算法,虽然其 执行时间亦为 0(n3),但其概念简单、程序简洁。设 n—有向图的结点个数; adj—有向图的相邻矩阵。其中

?vi 至v j的最短路长 ? adj[i, j ] ? ? ?? ?

vi 至v j 有通路; vi 至v j 无路;

path—最短路径集合。其中 path[i,j]为 vi 至 vj 的最短路上 vj 的前趋结点序号 (1≤i,j≤n) Var adj:array[1‥n,1‥n] of real; path:array[1‥n,1‥n] of 0‥n; 这个算法的基本思想是递推地产生一个矩阵序列 adj(0)、?、adj(n)。其中 ( ) adj(0) [i,j]=adj[i,j],即 adj 0 [i,j]’为 vi 到 vj 中间结点序号不大于 0(不经过任何中间 结点)的最短路径长度 ???????? adj(k)[i,j]为 vi 到 vj 中间结点序号不大于 k 的最短路径长度; ???????? adj(n)[i,j]为 vi 到 vj 中间结点序号不大于 n 的最短路径长度,即为所要求的从 vI 至 vj 的 最短路径长度; (1≤i,j≤n) (0) (1) 递推产生 adj 、adj 、?、adj(n)的过程,就是逐步允许越来越多的结点作为路径的中间结点, 直到所有结点都允许作为中间结点时最短路径便求出来了。假设已求得 adj(k-1) ,怎样由它推导出 adj(k)呢?vi 经由 vk 到 vj 的中间结点序号不大于 k 的最短路径由两段组成:
39

? 由 vi 至 vk 的中间结点序号不大于 k-1 的最短路径,其长度为 adj(k-1)[i,k]; ? 由 vk 到 vj 的中间结点序号不大于 k-1 的最短路径,其长度为 adj(k-1)[k,j]; 这两段路径的长度之和即为 vi 经由 vk 至 vj 的中间结点序号不大于 k 的最短路径长度。是否选择 vk 作为 vi 至 vj 最短路径上序号最大的一个中间结点,取决于两种情况: 第一种情况:adj(k-1)[i,j]≤adj(k-1)[i,k]+adj(k-1)[k,j]。显然中间不经过 vk 的方案更好,即 adj(k)[i,j]=adj(k-1)[i,j]; 第二种情况:adj(k-1)[i,j]>adj(k-1)[i,k]+adj(k-1)[k,j]。显然中间经过 vk 的方案更好,即 adj(k)[i,j]=adj(k-1)[i,k]+adj(k-1)[k,j],path[i,j] =path[k,j]; 下面给出算法: ( ) fillchar (adj, sizeof(adj), ∞); {计算 adj 0 } for i:=1 to n do for j:=1 to n do if wij<>∞ then begin adj[i,j]←wij;path[i,j]←j;end{then} else path[i,j]←0; ( ) for k: to n do =1 {顺序计算 adj(0)、 (0)、 adj ‥adj n } for i:=1 to n do {枚举每一个结点对} for j:=1 to n do if adj[i,k]+adj[k,j]<adj[i,j] {若 vi 经由 vk 至 vj 的路径目前最优,则记下} then begin adj[i,j]←adj[i,k]+adj[k,j]; path[i,j]←path[k,j]; end,{then} 算法结束时,由矩阵 path 可推知任一结点对 i、j 之间的最短路径方案是什么? Procedure print(i,j); begin if i=j then 输出 i else if path[i,j]=0 then 输出结点 i 与结点 j 之间不存在通路 else begin print (i,path[i,j]); 输出 j; end;{else} end;{print} 2、计算图的传递闭包 下面我们将问题再简化一些: 对于任何结点对 i, j∈V, 只要判断是否存在一条由 i 到 j 的路径, 而不需要具体了解最短路径的长度和构成。该问题又称作图的传递闭包。显然读者可以直接得出算 法:对图中的每条边赋权 1,然后对该图运行 floyd 算法。若算法结束时 adj[i,j]<n,则表明结点 i 至结点 j 之间至少存在一条通路;若 adj[i,j]=∞,则表明结点 i 与结点 j 之间无路。但这种算法如 同“杀鸡用牛刀”得不偿失。下面我们来介绍另一种方法,该方法在实际应用中可以节省时间和空 间。设

40

? ?true t[i, j ] ? ? ? false ?

从vi 至v j 至少存在一条通路; vi 与v j间无路;

我们递推产生 t(0)、t(1)、?t(n)。在递推过程中,路径长度的’+’运算和比较大小运算用相应的逻 辑运算符’∧’和’∨’代替。对于 i,j 和 k=1‥n,如果图中结点 i 至结点 j 间存在通路且所有结点序 号均属于{1‥k},则定义 tij(k)=1;否则 tij(k)=0。

t ij
且对于 k≥1

(0)

?true ?? ? false

(i ? j )or(i, j ) ? e (i ? j )and(i, j ) ? e

tij(k)=tij(k-1) ∨ (tik(k-1) ∧tkj(k-1)) 由于布尔值的存储量少于整数且位逻辑运算的执行速度快于算术运算, 因此后者无论在时间和空间 上都优于前一种算法。具体运算过程如下: fillchar (t,sizeof(t),false); for i:=1 to n do t[i,i]←true; for k:=1 to 边数 e do begin 输入第 k 条边关联的结点序号 i,j; t[i,j]←true; end;{for} for k:=1 to n do {递推 t(1)‥ t(n)} for i:=1 to n do {枚举每一个结点对} for j:=1 to n do t[i,j]←t[i,j]or(t[i,k]and t[k,j]); for i:=1 to n do for j:=1 to n do if (i<>j)and t[i,j] then 输出 vi 与 vj 间有通路;

§4.4 拓扑排序和计算关键路径

一、拓扑排序 1、拓扑排序的由来 拓扑排序是有向图的另一种重要运算。 给出有向图 G=(V, 若结点的线性序列 v1’, vn’(vi’ E)。 ?, ∈V,1≤i≤n)满足如下条件: vk’至 vk+1’有一条路径(1≤k<n-1) 则称该序列为拓扑序列。 实际问题中常用有向图来表示活动安排图,图中的结点对应一项活动,有向边<vi,vj>表示活 动 i 必须先于活动 j 完成。对有向图的结点进行拓扑排序,对应于实际问题就是将各项活动排出一 个线性的顺序关系。如果条件限制这些活动必须串行的话,那就应该按拓扑排序的安排顺序执行。 例如有 n 个士兵(1≤n≤26),编号依次为 A、B、C、??。队列训练时,指挥官要把一些士兵 从高到矮依次排成一行。但现在指挥官不能直接获得每个人的身高信息,只能获得“p1 比 p2 高” 这样的比较结果(p1,p2∈{‘A’‥’Z’}) ,记为 p1>p2。例如 A>B,B>D,F>D。士兵的身高关系如
41

(图 4.4—1)所示

对结点进行拓扑排序,可以得到 AFBD FABD ABFD 由上面例子可以看出,一个有向图结点的拓扑序列不是唯一的。并不是任何有向图的结点都可 以排成拓扑序列,有环图是不能排的。例如(图 4.4—2)所示的有环图

从其中任何一个结点出发,都可经由其它两个项点返回本身,因此就无法把结点排成满足条件的序 列。任何无环的有向图,其结点都可以排出一个拓扑序列。 2、拓扑排序的方法 下面给出拓扑排序的方法 ⑴从图中选择一个入度为 0 的结点且输出之; ⑵从图中删除该结点及其所有出边(即与之相邻的所有结点的入度减一) ; 反复执行这两个步骤,直至所有结点都输出了,也就是整个拓扑排序完成了。或者直至剩图中再没 有入度为 0 的结点,这就说明此图中有环,拓扑排序不能再进行下去了。 对于士兵排队问题,我们首先构造一张有向图 G: var g:array[‘A’‥’Z’,’A’‥’Z’] of 0‥1; {图的相邻矩阵} d:array[‘A’‥’Z’] of integer; {结点的度数序列} s:set of ‘A’‥’Z’; {士兵名集合} 图中的结点为士兵。若 a>b,则 g[a,b]←1 (即 a 向 b 引入一条有向边) ;计算结点 b 的入度(即 比士兵 b 高的人数)d(b)←d(b)+1。显然最高士兵对应的结点入度为 0: s←[]; {士兵名集合初始化} while 文件未输入完 do begin 读 a>b 信息; if (a∈{‘A’‥’Z’})and (b∈{‘A’‥’Z’}) then begin

42

s←s+[a,b]; g[a,b]←1; d[b]←d[b]+1; end;{then} end;{while} 然后通过下述方法计算士兵名字符集 m 和士兵人数 k m←’’; for a=’A’ to ‘Z’ do if a ? s then m←m+a; k←length(m);

{计算士兵名集合} {构造有向边(a,b)} {累计结点 b 的入度}

接下来对有向图G作拓扑排序。若图 G 中有回路,则排队方案不存在;否则拓扑序列 n 即为 一个排队方案。拓扑排序的过程如下: n←’’; {拓扑序列 n 初始化为空} for i:=1 to k do {依次搜索每一个出列士兵} begin j←1; while (d[m[j]]>0)and(j≤k)do j←j+1; {搜索第 i 个入度为 0 的结点序号 j} if j>k then {若入度为 0 的结点不存在, 则队列不存在最高的士兵, 无解退出} then begin 输出失败信息;halt; end;{then} n←n+m[j] {入度为 0 的结点 j 进入拓扑序列 n} a←m[j]; d[a]←∞; for j:=1 to k do {删去结点 j} if g [a,m[j]]>0 then d[m[j]]←d[m[j]]-1; end;{for} 输出拓扑序列 n; 二、计算关键路径 1、AOV网 如果有向图的结点表示活动,有向边表示活动间的优先关系,那么我们通过拓扑排序将图中的 结点排成一个满足活动先后顺序要求的线性序列。但在实际生活中,往往会抽象出另一种类型的有 向图:有向图的结点表示事件,有向边表示活动,边上的权标明一项活动需要的时间。结点所表示 的事件实际上就是它入边代表的活动均已完成,出边代表的活动可以开始这样一种状态。例如

43

上图含 11 项活动、9 个事件。其中事件 v1 表示开始时活动 a1、a2、a3 并行实施;事件 v5 代表 活动 a4、a5 已经完成,活动 a7、a8 可以开始。V9 表示整个计划完成。活动依事件的顺序要求进行。 例如活动 a4、a5、a6 只有当事件 v2、v3、v4 分别发生后才能进行,而它们的完成又标志事件 v5、v6 的发生。当活动 a10、a11 完成后,整个计划完成。上述有向图应该是无环的,且存在唯一的入度为 0 的开始结点(上图中的 v1)和唯一的出度为 0 的完成结点(上图中的 v9) 。这样的有向图称作 AOV 网(活动结点网络) 。利用 AOV 网可以估算出整个计算完成至少需要多少时间,为提前完成计划应 该加快哪些活动的速度等问题。解决这些问题有一种有效的方法——求关键路径方法。 2、计算关键路径 由于 AOV 网中的活动可以并行进行, 因此完成整个计划的最少时间是从开始结点到完成结点的 最长路径长度(路径上各边权的和) 。具有最大长度的路径称作关键路径。 (图 4.4—3)中 v1→v2 →v5→v8→v9 是一条关键路径,长度为 18。换句话说,整个计划至少需要 18 个时间单位完成。关 键路径上的活动又称关键活动。如果不能按期完成这些活动会贻误整个计划。找出关键活动后就可 以适当调度,集中力量于关键活动,以保证计划如期或提前完成。为找出关键活动,我们先定义几 个变量: n—AOV 网的结点数; m—AOV 网的有向边数; ee[i]—vi 事件可能发生的最早时间,即从开始结点 v1 至结点 vi 的最长路径长度; le[i]—在保证完成结点 vn 所代表的事件在 ee[n]时刻发生的前提下,事件 vi 允许发生的最晚时 间,即 le[i]=ee(n)-vi 至 vn 最长路径长度; e[k]—活动 ak(对应边<vi,vj>)可能的最早开始时间,即等于事件 vi 的可能的最早发生时间 ee[i]; l[k]—活动 ak(对应边<vi,vj>)允许的最晚完成时间,即等于事件 vj 允许最晚发生时间 le[j]; (1≤i, j≤n, 1≤k≤m)] 显然活动 ak 的最大可利用时间是 l[k]-e[k]。 若最大可利用时间等于 ak 边所带的权 wk(即为计划时间), 则 ak 是关键活动。Ak 延期,则整个计划将顺延。若最大可利用时间大于 wk,则 ak 不是关键活动, ak 的完成时间允许超过 wk。只要不超过最大可利用时间,无妨于整个计划完成的进度。我们可以 采取以下步骤,计算上面定义的几个变量值,从而找到关键活动: ⑴首先令 ee[1]=0,然后向前递推 ee[j] ee[j]=max{ee[i]+wij} 2≤j≤n, (i,j)∈以 j 为头的弧集 显然,ee[j]的计算必须在 vj 的所有前趋结点的最早发生时间都已求得前提下进行; ⑵从 le[n]=ee[n]起向后倒推 le[i] le[i]=min{le[j]-wij} i=n-1‥1, (i,j)∈以 i 为尾的弧集 显然,le[i]的计算必须在 vi 的所有后继结点的最晚发生时间都已求得的前提下进行。 由⑴、⑵可以看出结点序列 v1‥vn 必须是拓扑序列。 ⑶对于每一条边 ak=<vi,vj>(1≤k≤m),求 e[k]和 l[k] e[k]←ee[i], l[k]←le[j]

44

若 l[k]-e[k]=wij,则 ak 为关键活动。 AOV 网用邻接表存储。算法中使用的变量定义如下: Type pointer=↑edge; {边表的指针类型} edge=record {边表的结点类型} no:1‥n {该边另一端点序号} w:real; {该边的权} link:pointer; {后继指针,指向下一条边} end; node=record {结点表类型} info:datatype; {事件信息} out:pointer; {边表首指针} end; Var nodelist:array[1‥n] of node; {AOV 网的邻接表。结点表中的结点为拓扑序列, 其中 nodelist[i].info 存储序列中的第 i 个结点在原图中的序号} ee,le:array[1‥n] of real;{事件最早发生的时间序列和事件最晚发生的时间序列} e,l:array[1‥m] of real;{活动最早发生的时间序列和活动最晚完成的时间序列} 算法如下: 对 AOV 网进行拓扑排序,各结点及其关联的边按拓扑序列的顺序存入邻接表 nodelist; for i:=1 to n do ee[i]←0; {所有事件的最早发生时间初始化} for i:=1 to n-1 do {计算各个事件的最早发生时间表 ee} begin p←nodelist[i].out; while p<>nil do begin j←p↑.no; if ee[j]<ee[i]+p↑.w then ee[j]←ee[i]+p↑.w; p←p↑.link; end;{while} end;{for} for i:=1 to n do le[i]←ee[n]; {所有事件的最晚发生时间初始化} for i:=n-1 downto 1 do {计算各个事件的最晚发生时间表 le} begin p←nodelist[i].out; while p<>nil do begin j←p↑.no; if le[i]>le[j]-p↑.w then le[i]←le[j]-p↑.w; p←p↑.link; end;{while} end;{for}

45

k←0; {开始计算关键活动。活动序号初始化} for i:=1 to n-1 do begin p←nodelist[i].out; while p<>nil do {计算事件 i 发生后开始的各项活动的最早开始时间和最晚完成时间} begin j←p↑.no;k←k+1; e[k]←ee[i]; l[k]←le[j]; if l[k]-e[k]=p↑.w then 输出关键活动为<vi,vj>,其花费的时间为 p↑.w; p←p↑.link; end;{while} end;{for} 找出关键活动后,只要将所有的非关键活动从 AOV 网中去掉,这时从开始结点至完成结点的所 有路径都是关键路径。AOV 网中的关键路径可能不止一条。并不是加快任一关键活动就可以缩短整 个计划的完成时间。 只有加快那些包括在所有关键路径上的关键活动才能达到目的的。 (图 4. 例如 4 —3)所示 AOV 网中的关键路径为 v1→v2→v5→v8→v9 和 v1→v2→v5→v7→v9。如果仅加快事件 v8 和 v9 之间的关键活动 a11 的速度,是不能缩短计划完成时间的,因为第一条路径不包括活动 a11。如果 加快 v1 和 v2 之间的关键活动 a1, 则由于两条关键路径都包含关键活动 a1 而导致整个计划提前完成。

§4.5 图的应用实例

46


相关文章:
备战NOIP2010提高组初赛复习——算法篇之算法设计的常...
备战NOIP2010 提高组初赛复习——算法篇之算法设计的常用策略程序设计主要包括两个方面 ? 结构特性的设计(数据结构的设计) ; ? 行为特性的设计(算法设计) ; 第...
Noip2010提高组初赛试题及详细解析(C语言)
Noip2010提高组初赛试题及详细解析(C语言)_建筑/土木...从上至下、从左至右一次存放到一 个顺序结构的...(除了存储待排序元素以外的)付诸空间的大小与数据...
noip2010提高组解题报告
输入数据保证到达终点时刚好用光 M 张爬行卡片,即 N?1=ΣM ib 1 。 【输出】 输出文件名 tortoise.out。 全国信息学奥林匹克联赛(NOIP2010)复赛 提高组 第...
noip2010提高组初赛试题
noip2010提高组初赛试题 学习资料学习资料隐藏>> 第...从上至下、从左至右一次存放到一 个顺序结构的...(除了存储待排序元素以外的)付诸空间的大小与数据...
NOIP2010提高组复赛试题及解题报告
NOIP2010 提高组复赛试题及解题报告 1.机器翻译 (translate.pas/c/cpp) 【问题描述】 小晨的电脑上安装了一个机器翻译软件,他经常用这个软件来翻译英语文章。 ...
NOIP初赛复习——算法1
OK 备战 NOIP2010 提高组初赛复习——算法篇之算法设计的常用策略程序设计主要包括两个方面 ? 结构特性的设计(数据结构的设计) ; ? 行为特性的设计(算法设计) ;...
NOIP2010提高组初赛答案
NOIP2010提高组初赛答案NOIP2010提高组初赛答案隐藏>> 背包问题( ) 背包问题(2...砝码称重的测试数据如下: 4.1 1 1 0 0 0 0 Total=3 4.2 2 2 0 0 0...
Noip2010提高组初赛试题及答案(C语言)
Noip2010提高组初赛试题及答案(C语言)_初一数学_...从上至下、从左至右一次存放 到一个顺序结构的...(除了存储待排序元素以外的)付诸空间的大小与数据规...
NOIP2010提高组初赛试题答案C++
(除了存储待排序元素以外的)辅助空间的大小与数据...对同一个图而言,拓扑排序的结构是唯一的 C.拓扑...备战NOIP2010提高组初赛... 46页 免费 NOIP2010初赛...
NOIP2010提高组初赛标准答案(C&C++)
NOIP2010提高组初赛试题答... 13页 2财富值 第十六届全国青少年信息学... 12页 免费如要投诉违规内容,请到百度文库投诉中心;如要提出功能问题或意见建议,请点击...
更多相关标签: