nbhkdz.com冰点文库

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

时间:2011-10-03


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

早期的程序设计主要偏重于数值计算领域,采用的数据结构相对简单。 早期的程序设计主要偏重于数值计算领域,采用的数据结构相对简单。例如 FORTRAN 语 言仅定义了数组(包括多维数组)和复数两种结构型数据, 言仅定义了数组(包括多维数组)和复数两种结构型数据,这两种数据类

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

简单类型 构造类型

整型、实型、字符型、 整型、实型、字符型、布尔型 静态数据类型 数组、记录、集合、 数组、记录、集合、字符串

文件、 文件、指针 动态数据的类型 线性结构 数组、 数组、栈、队列、链表、串 队列、链表、

非线性结构 树、图

通常高级程序设计语言都提供了各种简单类型和静态构造类型的数据结构。 通常高级程序设计语言都提供了各种简单类型和静态构造类型的数据结构。例如 就提供了12种类型的定义。 12种类型中除了文件和指针属于动态结构的构造 12种类型的定义 PASCAL 就提供了12种类型的定义。这12种类型中除了文件和指针属于动态结构的构造 类型外,其余10种均属于简单类型和静态构造类型。在上表的数据结构中,像数组、 10种均属于简单类型和静态构造类型 类型外,其余10种均属于简单类型和静态构造类型。在上表的数据结构中,像数组、栈、 串和队列等数据结构属于线性数据结构,而树和图属于非线性数据结构 和图属于非线性数据结构。 串和队列等数据结构属于线性数据结构,而树和图属于非线性数据结构。线性数据结构易 于表示各结点之间的联系,其存储方式相对简单; 于表示各结点之间的联系,其存储方式相对简单;非线性数据结构往往能比较形象地反映 各结点之间的层次关系。无论是线性结构或非线性结构,若采用数组方式存储, 各结点之间的层次关系。无论是线性结构或非线性结构,若采用数组方式存储,则属于静 态数据类型;若采用指针类型存储,则属于动态数据类型。 态数据类型;若采用指针类型存储,则属于动态数据类型。考虑到篇幅限制和读者大多具 语言的基础,本书侧重讲解线性结构和非线性结构两种。 备 pascal 语言或 c 语言的基础,本书侧重讲解线性结构和非线性结构两种。

数据结构和算法有着密切的联系, 数据结构和算法有着密切的联系,简洁有效的算法很大程度上出自于对数据结构的正 确选取。奥林匹克信息学竞赛的试题大都属于非数值计算问题, 确选取。奥林匹克信息学竞赛的试题大都属于非数值计算问题,从问题中抽象出的数据多 半是结构类型的 因此,对于参与这项活动的学生来说,学好、用好数据结构尤为重要。 构类型的, 半是结构类型的,因此,对于参与这项活动的学生来说,学好、用好数据结构尤为重要。 为此。我们在本书中详尽地介绍了数据结构的有关概念和基本操作,同时辅之于一些实例, 为此。我们在本书中详尽地介绍了数据结构的有关概念和基本操作,同时辅之于一些实例, 围绕编程实际展开讨论,尽可能多给读者一点启示。 围绕编程实际展开讨论,尽可能多给读者一点启示。 第一章 顺序存储结构的线性表 线性表是最常用且比较简单的一种数据结构,它是由有限个数据元素组成的有序集合, 线性表是最常用且比较简单的一种数据结构,它是由有限个数据元素组成的有序集合, 每个数据元素有一个数据项或者含多个数据项。 个英文字母表(A (A, ……,Z)是 每个数据元素有一个数据项或者含多个数据项。例如 26 个英文字母表(A,B,……,Z)是 一个线性表,表中每一个数据元素由单个字母组成数据项。又如( 一个线性表,表中每一个数据元素由单个字母组成数据项。又如(图 1—1)也是一个线性 个数据元素,每一个数据元素由 个选手在该项目的竞赛成绩组成。 表,表中含 8 个数据元素,每一个数据元素由 n 个选手在该项目的竞赛成绩组成。

学生 项目 项目 1 学生 1 …… 学生 j …… 学生 n 项目总分

……

项目 i

xij

……

项目 8 选手总分 sum Sum xj=

( 图 1— 1) 线性表具有如下结构特征: 线性表具有如下结构特征: 均匀性:即同一线性表的各数据元素的数据类型一致且数据项数相同; 均匀性:即同一线性表的各数据元素的数据类型一致且数据项数相同; 有序性:表中数据元素之间的相对位置是线性的,即存在唯一的 第一个” 有序性:表中数据元素之间的相对位置是线性的,即存在唯一的“第一个”和“最后 一个”数据元素。除第一个和最后一个外,其它元素前面均只有一个数据元素(直接前趋) 一个”数据元素。除第一个和最后一个外,其它元素前面均只有一个数据元素(直接前趋) 和后面均只有一个数据元素(直接后继)。 和后面均只有一个数据元素(直接后继)。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构二类线性表。 按照表中数据元素的存储方式分顺序存储结构和链式存储结构二类线性表。顺序存储 结构是指用一组地址连续的存贮单元依次存储线性表的元素,通常用数组实现; 结构是指用一组地址连续的存贮单元依次存储线性表的元素,通常用数组实现;而在链式 存储结构的线性表中,逻辑上相邻的两元素,其物理位置不要求相邻。 存储结构的线性表中,逻辑上相邻的两元素,其物理位置不要求相邻。其实现既可采用静 态数组,亦可采用动态指针。为了扩大用户空间和更多地体现链式存储结构的便利, 态数组,亦可采用动态指针。为了扩大用户空间和更多地体现链式存储结构的便利,实践 中大都采用动态链表形式。为此,本书在讲解顺序存储结构的线性表时采用数组类型 性表时采用数组类型, 中大都采用动态链表形式。为此,本书在讲解顺序存储结构的线性表时采用数组类型,在 讲解链式存储结构的线性表采用指针类型。另外, 讲解链式存储结构的线性表采用指针类型。另外,根据存取方式的限制和表元素类型的限 还存在几种特殊类型的线性表: 队列、 制,还存在几种特殊类型的线性表:栈、队列、串,它们一般采用顺序存储结构 §1.1 数组 我们称有限个同类型数据元素的序列为数组,它是一种定长的线性表。 我们称有限个同类型数据元素的序列为数组,它是一种定长的线性表。若数组元素不 再有分量,该序列叫一维数组;若数据元素为数组,则称该元素为多维数组。 再有分量,该序列叫一维数组;若数据元素为数组,则称该元素为多维数组。例如 var atype; A:array[c‥d] of atype; array[c‥ btype; B:array[c1‥d1,c2‥d2] of btype; array[c1‥d1,c2‥ 为一维数组 表长为 d-c+1) 元素类型为 atype; 为二维数组, atype; 为二维数组, *(d2-c2), A 为一维数组, ( c+1) , B 表长为 d1-c1) (d1-c1) *(d2-c2), 元素类型为 btype。 btype。一维数组和多维数组的元素个数由其类型说明或变量说明静态确定, 一维数组和多维数组的元素个数由其类型说明或变量说明静态确定,执 行中不能增减其内存空间。 行中不能增减其内存空间。 一、数组的顺序存储结构 数组的物理实现是一块连续的存储空间,它是按首址( 个元素的地址) 数组的物理实现是一块连续的存储空间,它是按首址(表中第 1 个元素的地址)十 位 移来访问每一个元素的。 移来访问每一个元素的。设 loc(a[i])— 的内存地址( loc(a[i])—A 表中元素 i 的内存地址(c≤i≤d); loc(b[i,j])— 表中( 元素的内存地址(c1≤ d1,c2≤ d2); loc(b[i,j])—B 表中(i,j)元素的内存地址(c1≤i≤d1,c2≤j≤d2); loc(a[i])=loc(a[c])+(iloc(a[i])=loc(a[c])+(i-c)*la 首址 位移 la— 类型的长度; la—atype 类型的长度;

loc(b[i, j])=loc(b[c1, c2])+((d2-c2+1)*(i-c1)+(j-c2))*lb lb—btype 类型的长 lb— loc(b[i, j])=loc(b[c1, c2])+((d2-c2+1)*(i-c1)+(j度; 首址 位移

一维数组按照下标递增的顺序访问表中元素 一维数组按照下标递增的顺序访问表中元素 a[c]→a[c+1]→……→a[d] a[c]→a[c+1]→……→a[d] →……→ 二维数组按照先行后列的顺序访问表中元素 b[c1,c2]→b[c1,c2+1]→……→b[c1,d2]→……→b[i- d2]→b[i,c2]→……→ b[c1,c2]→b[c1,c2+1]→……→b[c1,d2]→……→b[i-1,d2]→b[i,c2]→……→ →……→b[c1 →……→b[i b[d1,d2-1]→b[d1, b[d1,d2-1]→b[d1,d2] 在数组中,数据元素的下标间接反映了数据元素的存储地址。 在数组中,数据元素的下标间接反映了数据元素的存储地址。而计算机内存是随机存取的 装置,所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了, 装置,所以在数组中存取一个数据元素只要通过下标计算它的存储地址就行了,数组中任 意一个元素的存取时间都相等。从这个意义上讲,数组的存储结构是一个随机存取的结构。 意一个元素的存取时间都相等。从这个意义上讲,数组的存储结构是一个随机存取的结构。 二、数组在顺序存储结构下的插入与删除 设数组定义为 m=数组的长度上限 数组的长度上限; Const m=数组的长度上限; [1‥ elementype; Type vtype=array [1‥m]of elementype; 类型} 类型} var n:integer; integer; 长度} 长度} v:vtype; vtype; {数组} 数组} {数组的实际 {数组

按上述定义, v v={v[1], v[2], ……, v[n]}, elementype。 按上述定义, 为一个长度为 n 的数组 v={v[1], v[2], ……, v[n]}, 元素类型为 elementype。

1、插入操作

v[i-1]与第 v[i]之间插入一个新元素 现要在数组的第 i-1 个元素 v[i-1]与第 i 个元素 v[i]之间插入一个新元素 b,插入后 ={v’[1], [n], 将得到一个长度为 n+1 的新数组 v’={v’[1],…,v’[n],v’[n+1]} v[j]与 [j]满足如下关系 插入前后两数组的元素 v[j]与 v’[j]满足如下关系

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

2、删除操作 个元素, ={v’[1], [2],……, 现要删除数组 v 中的第 i 个元素,使得删除后的 v 数组变为 v’={v’[1],v’[2],……, [n-1]}, v[j]和 [j]满足下列关系 v’[n-1]},其长度变为 n-1。显然删除前后两数组元素 v[j]和 v’[j]满足下列关系

同样, 个元素, 同样,为了删除数组中第 i 个元素,则原来第 i 个元素之后的所有元素必须依次向前移动 一个位置。如果要删除数组最后一个元素,则很简单,不需要移动数组元素; 一个位置。如果要删除数组最后一个元素,则很简单,不需要移动数组元素;如果要删除 数组的第一个元素,则很复杂,必须将数组中的所有元素依次向前移动一个位置。 数组的第一个元素,则很复杂,必须将数组中的所有元素依次向前移动一个位置。在一般 情况下, 个元素, 情况下,要删除第 i 个元素,需要将数组中第 i+1 到第 n 共 n-i 个元素依次向前移动一个 位置。 位置。 (i:integer; n:integer; v:vtype); procedure delet (i:integer; var n:integer; var v:vtype); begin if (i<1)or (i>n) (‘without’ then writeln (‘without’) else begin j: nv[j]←v[j+1]; for j:=i to n-1 do v[j]←v[j+1]; 位置} 位置} n← n-1; 度-1} end; end;{else} end; end;{delet} {v 数组的长 {v[i+1]‥v[n]向前移动一个 {v[i+1]‥v[n]向前移动一个

过程的时间复杂度:对顺序存储的数组作一次删除,平均起来, 执行 delet 过程的时间复杂度:对顺序存储的数组作一次删除,平均起来,大约需要移动 表中一半的元素。 表中一半的元素。 综上所述,数组的顺序分配,其结构比较简单,便于随机访问数组中的任一元素。 综上所述,数组的顺序分配,其结构比较简单,便于随机访问数组中的任一元素。但是如 果数组要保持线性表特征的话(由下标指明元素间的有序性),其增删操作的效率比较低。 ),其增删操作的效率比较低 果数组要保持线性表特征的话(由下标指明元素间的有序性),其增删操作的效率比较低。 特别当数组很大时,插入与删除运算颇为费时。因此,比较小的数组或元素不常变动( 特别当数组很大时,插入与删除运算颇为费时。因此,比较小的数组或元素不常变动(很 少进行插入与删除运算)的数组可用作线性表, 少进行插入与删除运算)的数组可用作线性表,而对于大的线性表或元素经常变动的线性 可以采用链式存储结构。 表,可以采用链式存储结构。 三、数组的应用实例 Pascal),如果需要从磁盘文件中输入一 1、在编程时(使用任一种高级语言,不一定是 Pascal),如果需要从磁盘文件中输入一 在编程时(使用任一种高级语言, 数组( 型数组),按行读( ),按行读 个很大的二维 数组(例如 1000*1000 的 double 型数组),按行读(即外层循环是关于 行的)与按列读( 环是关于列的)相比,在输入效率上( 行的)与按列读(即外层循 环是关于列的)相比,在输入效率上( )。 A. 没有区别 有一些区别,但机器处理速度很快, B. 有一些区别,但机器处理速度很快,可忽略不计

C. 按行读的方式要高一些 储方式。 储方式。 § 1. 2 栈

D. 按列读的方式要高一些

E. 取决于数组的存

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

m

t→

……………

1 栈s (图 1.2—1)

一、栈的基本运算 push(s, t)— 1、过程 push(s,x,t)—往栈 s 中压入一个值为 x 的表目 s:stack; stype; t:integer); procedure push (var s:stack; x:stype; var t:integer); begin writeln(‘overflow’ if t=m then writeln(‘overflow’) {上溢} 上溢} t←t+1; s[t]← end; else begin t←t+1; s[t]←x; end;{else} 入栈} 入栈} end; end;{Push} {x

pop(s,t)— 2、函数 pop(s,t)—从栈中弹出一个表目 stack; t:integer):stype; function pop (var s:stack; var t:integer):stype; begin (‘underflow’ if t=0 then writeln (‘underflow’) {下溢} 下溢} pop←s[t]; end; else begin pop←s[t]; t←t-1; end;{else} 素出栈} 素出栈} end; end;{pop} {栈顶元 {栈顶元

top(s,t)— 3 函数 top(s,t)—读栈顶元素

function (s:stack; integer):stype; function top (s:stack; t:integer):stype; begin (‘ empty’ if t=0 then writeln (‘stack empty’) top←s[t]; else top←s[t]; 顶元素} 顶元素} end; 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. B. 5 C. C. 4 D. D. 3 E. E. 2

某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。 3. 某个车站呈狭长形,宽度只能容下一台车,并且只有一个出入口。已知某时刻该车站 状态为空, 这一时刻开始的出入记录为: 状态为空,从 这一时刻开始的出入记录为:“进,出,进,进,进,出,出,进,进,进, ……,则车辆出站的顺序为( 出,出”。假设车辆入站的 顺序为 1,2,3,……,则车辆出站的顺序为( )。 A. 1, 2, 3, 4, 5 D. 1, 4, 3, 7, 2 B. 1, 2, 4, 5, 7 E. 1, 4, 3, 7, 5 C. 1, 4, 3, 7, 6

根细柱, 个直径相同中间有孔的圆盘, 4. 地面上有标号为 A、、 的 3 根细柱, 在 A 柱上放有 10 个直径相同中间有孔的圆盘, 从 B C ……, 上到下次依次编号为 1, 2, 3, ……,将 A 柱上的部分盘子经过 B 柱移入 C 柱, 也可以在 B 柱上暂存。 柱上的操作记录为: 柱上暂存。如果 B 柱上的操作记录为:“进,进,出,进,进,出,出,进,进,出,进, 那么, 柱上, 从下到上的盘子的编号为( 出,出”。那么, 在 C 柱上, 从下到上的盘子的编号为( )。 A. 2 4 3 6 5 7 D. 2 4 3 6 7 5 B. 2 4 1 2 5 7 E. 2 1 4 3 7 5 C. 2 4 3 1 7 6

的初始状态为空, 依次入栈, 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

a*(b+c)- 的后缀表达式是: 6. 表达式 a*(b+c)-d 的后缀表达式是: abcd*+A) abcd*+abc+*dB) abc+*dabc*+dC) abc*+dD) -+*abcd

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

a d

b e

c

d

b

c

d

B

c

一个队列 元素 ( 图 1. 3— 1)

删除一个元素

插入一个

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

q:equeue; equeue; {队列} 队列} r,f:integer; integer; 首指针} 首指针} {队尾指针和队

Q: 1 m ( 图 3. 1— 2)

二、队列的基本运算 队列的运算主要有两种 ADD(q, r)— 1、过程 ADD(q,x,r)—在队列 q 的尾端插入元素 x q: equeue; qtype; r:integer); procedure ADD(var q: equeue; x:qtype; var r:integer); begin (‘overflow’ if r=m then writeln (‘overflow’) {上溢} 上溢} begin else begin 元素 x} r←r+1; q[r]←x; r+1; q[r]← end; end;{else} end; end;{ADD} {后移队尾指针并插入 {后移队尾指针并插入

DEL(q, 2、过程 DEL(q,y,f,r)—取出 q 队列的队首元素 y q:equeue; y:qtype; f:integer); procedure DEL(var q:equeue; var y:qtype; var f:integer); begin

(‘ flow’ if f=r then writeln (‘under flow’) {下溢} 下溢} else begin 首元素} 首元素} q[f]; f←f+1; y←q[f]; f+1; end; end;{else} end; end;{DEL} {后移队首指针并取出队 {后移队首指针并取出队

由于队列只能在一端插入,在另一端删除,因此随着入队及出队运算的不断进行, 由于队列只能在一端插入,在另一端删除,因此随着入队及出队运算的不断进行,就会出 不断进行 现一种有别于栈的情形:队列在数组中不断地向队尾方向移动, 现一种有别于栈的情形:队列在数组中不断地向队尾方向移动,而在队首的前面产生一片 不能利用的空闲存储区,最后会导致当尾指针指向数组最后一个位置( r=m) 不能利用的空闲存储区,最后会导致当尾指针指向数组最后一个位置(即 r=m)而不能再加 入元素时,存储空间的前部却有一片存储区无端浪费,这种现象称为“假溢出” 例如: 入元素时,存储空间的前部却有一片存储区无端浪费,这种现象称为“假溢出”。例如:

m

m

m

r→m Am

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

三、循环队列及其运算

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

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

循环队列的运算有两种: 循环队列的运算有两种: ADD2(q, 1、过程 ADD2(q,x,r)—在循环队列 q 中插入一个新元素 x q:equeue; qtype; r:integer); procedure ADD2 (var q:equeue; x:qtype; var r:integer); begin m; t←(r+1) mod m; r+1) 入位置} 入位置} {计算插

writeln(‘full’ if t=f then writeln(‘full’) 队列满} {队列满} else begin 入队尾} 入队尾} q[r]← r←t; q[r]←x; end; end;{else} end; end;{ADD2} {新元素 {新元素 x 插

EL2(q, f)— 2 过程 DEL2(q,y,f)—从循环队列 q 中取出队首元素 y q:equeue; y:qtype; f:inteqer); procedure DEL2 (var q:equeue; var y:qtype; var f:inteqer); begin (‘empty’ if f=r then writeln (‘empty’) 队列空} {队列空} else begin +1) m; q[f]; f←(f +1) mod m;y←q[f]; 首元素} 首元素} end; end;{else} end; 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 的容量至少应该为( )。 B) C) D) A)2 B)3 C)4 D)5 {取出队

§ 1. 4 串 前面介绍的线性表的操作都是对一个元素进行处理的, 前面介绍的线性表的操作都是对一个元素进行处理的,但实际中我们经常要对一串元 个元素进行处理的 素进行操作。如信息检查系统、文字编辑系统、自然语言翻译系统以及音乐分析程序等等, 素进行操作。如信息检查系统、文字编辑系统、自然语言翻译系统以及音乐分析程序等等,

都是以字符串数据作为处理对象的。随着非数值的广泛应用, 都是以字符串数据作为处理对象的。随着非数值的广泛应用,字符串的处理将显得越来越 重要。 重要。 一、串的基本概念 串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这个串的长度。 串是由零个或多个字符组成的有限序列。一个串中包含的字符个数称为这个串的长度。 长度为零的串称为空串,它不包含任何字符。 长度为零的串称为空串,它不包含任何字符。 通常用撇‘’将字符串括起来。 通常用撇‘’将字符串括起来。例如 ‘’将字符串括起来 ⑴‘x1’ ⑴‘x1’ x1 ⑵‘123’ ⑵‘123’ 123 ⑶‘’ ⑷‘ ’ 长度为 2 的串 长度为 3 的数串 长度为 0 的空串 包含一个空白字符( 包含一个空白字符(长度为 1)的非空串

是两个串: 假设 s1 和 s2 是两个串: s1=a1……an s1=a1……an …… s2=b1……bm s2=b1……bm …… ai、 代表字符( )。如果存在整数 ),使得 其中 ai、bi 代表字符(0≤m≤n)。如果存在整数 i(0≤i≤n-m),使得 bj=ai+j j=1‥ j=1‥m

同时成立, 的子串, s2。 同时成立,则称 s2 是 s1 的子串,又称串 s1 包含串 s2。 串中所能包含的字符依赖于具体机器的字符集, 串中所能包含的字符依赖于具体机器的字符集,按字符的字符集中的次序可以规定字 符的大小。 ASCII(美国信息变换标准码) EBCDIC( 符的大小。目前世界上最为广泛的字符集是 ASCII(美国信息变换标准码)和 EBCDIC(扩 充的二进制编码、十进制信息码),它们都规定数字字符‘ ’‥‘9 ),它们都规定数字字符 充的二进制编码、十进制信息码),它们都规定数字字符‘0’‥‘9’的字符集是顺序排 列的,字母字符‘ ’‥‘Z ’‥‘z 的字符集也是顺序排列的, 列的,字母字符‘A’‥‘Z’(‘a’‥‘z’)的字符集也是顺序排列的,因此用 ord 函 数计算字符在字符集中的序号就有 ord(‘ )<ord(‘ ord(‘a’)<ord(‘b’)<……<ord(‘z’) )<……<ord(‘ ……<ord( ord(‘ )<ord(‘ ord(‘0’)<ord(‘1’)<……<ord(‘q’) )<……<ord(‘ ……<ord( 并且对所有数字 i(0≤i≤9)满足 i=ord(‘ i=ord(‘i’)-ord(‘0’) ord(‘

作比较, ord(ch1)<ord(ch2), 通常可对两个字符 ch1 和 ch2 作比较, 谓 ch1<ch2 的含义就是指 ord(ch1)<ord(ch2), 所 必要时可以将串按其构成的字符用字符顺序排列,从而定义两个串的大小。 必要时可以将串按其构成的字符用字符顺序排列,从而定义两个串的大小。例如 ‘a’<’abo’<’x’ abo’ ‘012’<’123’<’2’ 012’ 123’ 程序中使用的串可以分成两种 1、串常数 串常数具有固定的串值,即可以用直接量表示,用以原样输出,亦可以给串常数命名, 串常数具有固定的串值,即可以用直接量表示,用以原样输出,亦可以给串常数命名, 以便反复使用时书写和修改方便。 以便反复使用时书写和修改方便。例如 const 名串常数} 名串常数} (‘overflow’ writeln (‘overflow’) 出串常数} 出串常数} {原样输 {原样输 object=’ structure’ object=’data structure’; {命

2、串变量 串变量的取值是可以改变的,但必须用名字来识别, 串变量的取值是可以改变的,但必须用名字来识别,说明串变量的方法与其它变量相 似。例如 var s:string[30]; string[30]; 个字符,且顺序存在一个字符数组中, 上面定义了一个串变量 s,s 最多能容纳 30 个字符,且顺序存在一个字符数组中,类似于 var char; s:array[0‥30]of char; array[0‥ s[0]记载了 的实际长度。 类型中省略长度标记, 个字符。 其中 s[0]记载了 s 的实际长度。 string 类型中省略长度标记, 若 则串长上限为 255 个字符。 二、串的基本运算 中提供了一些串运算的库函数, PASCAL 中提供了一些串运算的库函数,我们将作以简单的介绍 1、连接运算——函数 concat(s1,[,s2,…,sn]) 连接运算——函数 concat(s1, s2, ——

s1, 类型, 类型。 255, 其中值参 s1,‥,sn 为 string 类型,函数值为 string 类型。若连接后的串长大于 255, 则自动截断超出部分。 则自动截断超出部分。

2、求子串——函数 copy(s,i,l) 求子串——函数 copy(s, —— 类型, 类型。 个字符开始、 其中值参 s 为 string 类型,i 和 l 为 integer 类型。函数返回 s 串中第 i 个字符开始、长 的子串( 类型)。 )。若 的长度,则回送一个空串; 度为 l 的子串(string 类型)。若 i 大于 s 的长度,则回送一个空串;若 l 大于第 i 个字 符开始的余串长度,则仅回送余串。 符开始的余串长度,则仅回送余串。

s, 3、删子串——过程 delete(var s,i,l) 删子串——过程 —— 类型, 类型。 其中变量参数 s 为 string 类型,值参 i、l 为 ingteger 类型。该过程删去 s 中第 i 个字符 的子串, 的长度,则不删任何字符; 开始的长度为 l 的子串,并返回剩余串 s。若 i 大于原串 s 的长度,则不删任何字符;若 l 个字符开始的余串长度,则删去余串。 大于第 i 个字符开始的余串长度,则删去余串。

s, 4、插入子串——过程 insert(s1, var s,i) 插入子串——过程 insert(s1, —— 类型, 类型。 变量参数 s 为 string 类型,值参 s1 为 string 类型。该过程将 s1 子串插入空串 s 的 个字符位置处, 个字符, 第 i 个字符位置处,并返回插入后的结果 s。若插入后 s 的串长大于 255 个字符,则截断超 出部分。 出部分。

5、求串长——函数 length(s) 求串长——函数 —— 类型。 串的实际长度值( 类型)。 值参 s 为 string 类型。该函数返回 s 串的实际长度值(integer 类型)。

6、搜索子串位置——函数 pos(s1,s2) 搜索子串位置——函数 pos(s1, —— 类型。 的一个子串, 值参 s1 和 s2 为 string 类型。若 s1 是 s2 的一个子串,则返回 s1 中第 1 个字符在 s2 串中 的位置( 类型); );若 的一个子串, 的位置(integer 类型);若 s1 非 s2 的一个子串,则返回 0。

7、数值转换为数串——过程 str(x,var s) 数值转换为数串——过程 str(x, —— 类型, 类型。 值参 x 为 integer 类型或 real 类型,变量参数 s 为 string 类型。该过程将返回数值 x 对 应的数串 s。

v, 8、数串转换为数值——过程 val(s,var v,var c) 数串转换为数值——过程 val(s, —— 类型, 类型, 值参 s 为 string 类型,变量参数 v 为 integer 类型或 real 类型,变量参数 c 为 integer 类型。 若转换成功, 类型。该过程试将 s 串转换成数值 v。若转换成功,则 c 为 0,并返回对应的数值 v;否则 为无效字符的序数。 c 为无效字符的序数。

9、字符的大写转换——函数 upcase(ch) 字符的大写转换——函数 —— 类型。 字符的大写体( 类型) 值参 ch 为 char 类型。该函数返回 ch 字符的大写体(char 类型) 三、串的应用实例 字符串“ababacbab”和字符串“abcba”的最长公共子串是( 1. 字符串“ababacbab”和字符串“abcba”的最长公共子串是( )。 A. abcba B. cba C. abc D. ab E. bcba )。 D. D.17 E. E. 7

S=“Olympic” 的非空字串的数目是( 2. 设字符串 S=“Olympic”,S 的非空字串的数目是( A.29 B. B.28 C. C.16

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

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

31 37 43

zhao zheng zhou

7 19 25

31

在单链表中每个结点的存储地址可以任意分配, 在单链表中每个结点的存储地址可以任意分配,即表中元素的存储位置可以不连续且 是无序的 序的, 指针确定: a1… 是无序的,而它们的逻辑顺序由链表中的 next 指针确定:假设线性表 a1…an 采用单链表 的存储结构, 的结点, 的结点( 的存储结构,其中 p 指针指向 ai 的结点,则 p↑.next 指针指向值为 ai+1 的结点(p next<>nil)。 )。换句话说 data=ai, next↑ data=ai+1。 ↑.next<>nil)。换句话说 p↑.data=ai,p↑.next↑.data=ai+1。 二、单链表的操作 1、动态建立单链表 a1…an。试建立其单链表的存储结构, 指向单链表的“哨兵” 设线性表 a1…an。试建立其单链表的存储结构,其中 head 指向单链表的“哨兵”。 creathead:pointer); Procedure creat-Link(var head:pointer); begin head←nil; head←nil; 个空表} 个空表} i: for i:=n downto 1 do begin new(p); data←ai; new(p); p↑.data←ai; 的结点} 的结点} p↑.next←head; head←p; next←head; head← 点之前} 点之前} end; end;{for} new(p); next←head; head← new(p); p↑.next←head; head←p; “哨兵”} 哨兵” end; end;{creak_link} {加 {将新结点插入单链表第 1 个结 将新结点插入单链表第 {生成一个值为 ai {建立一

2、插入操作 为指向“哨兵” 在单链表的第 i 个结点前插入元素 x。head 为指向“哨兵”的首指针 (x:elemenetype; integer; head:pointer); pocedure insert_Link (x:elemenetype; i:integer; var head:pointer); begin new(s); data← new(s); s↑.data←x; 的结点} 的结点} p←head; head; 兵”} while(p<>nil)and(j<iwhile(p<>nil)and(j<i-1)do 个结点} 个结点} p← ext; j+1; end; begin p←p↑.next; j←j+1; end; {while} if p<>nil then begin 元素 x} next← s↑.next←p↑.next; p↑.next←s; next← next; end{then} (‘without’ else writeln (‘without’); {i>表长} {i>表长} 表长 end; end;{insert_Link} {第 {第 i-1 个结点后插入 {寻找单链表中第 {寻找单链表中第 i-1 j←0; {p 指向 哨 “ {生成值为 x

3、删除操作 为指向“哨兵”的首指针。 个结点。 设 head 为指向“哨兵”的首指针。删除单链表的第 i 个结点。 delet_Link(i:integre; head:pointer); Procedure delet_Link(i:integre; var head:pointer); begin

p←head; j←0; head; 哨兵” “哨兵”} (p↑ next<>nil)and(j<i il)and(j<iwhile (p↑.next<>nil)and(j<i-1)do 结点 p} p← next; j+1; end; begin p←p↑.next; j←j+1; end;{while} p↑ if p↑.next=nil {i>表长 表长} {i>表长} (‘without’ then writeln (‘without’) else begin 结点 q} q←p↑.next; next; p↑.next←p↑.next↑.next; next← next↑ next; dispose(q); dispose(q); end; end;{else} end; end;{delet_Link}

{p 指向

{寻找第 {寻找第 i-1 个

{删除第 i 个

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

end; end;{while} if p=nil {i>表长} {i>表长} 表长 writeln(‘without’ then writeln(‘without’) get_Link← data; else get_Link←p↑.data; 结点值} 结点值} end; end;{get_Link} {取得表中第 i 个

三、单链表的应用举例 单链表的应用举例

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

da: dupointer; da: dupointer; “哨兵”} 哨兵”

{双向链表的

域为空(nil) (nil), 指向链表的第一个结点, “哨兵”的 priou 域为空(nil),后继指针 next 指向链表的第一个结点,data 域为空或 哨兵” 者设置特定的值。 者设置特定的值。

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

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

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

end; end;{for} q↑.next←la; la↑.priou←q; next←la; la↑ priou← 尾相接} 尾相接} end; end; {creat_dulist} {首

2、读取双向循环链表中第 i 个结点的地址 哨兵”的双向循环链表中, 个结点的地址。 i>表长 表长, nil; 在 la 为“哨兵”的双向循环链表中,确定第 i 个结点的地址。若 i>表长,返回 nil; i=表长 表长+ la: 若 i=表长+1,则返回哨兵指针 la: (i,la):dupointer ter; function get_dulist (i,la):dupointer; begin p←la↑.next; j←1; la↑ next; 始搜索} 始搜索} p← next; j+1; end; while (p<>la)and(j<i)do begin p←p↑.next; j←j+1; end;{while} get_dulist← if j=i then get_dulist←p get_dulist←nil; else get_dulist←nil; end; end; {get_dulist} {从第1个结点开 从第1

3、插入操作 la。 双向循环链表的哨兵指针为 la。在该链表的第 i 个元素之前插入元素 x: (x:elementype; integer; la:dupointer); procedure insert_dulist (x:elementype;i:integer;var la:dupointer); begin {生成新结点 s, 寻找双向循环链表中的第 i 个 结点 p} new(s); new(s);s↑.data←x;p←qet_dulist(i,la); data← qet_dulist(i,la); if p<>nil

then begin p↑.priou↑.next←s; priou↑ next← 结点 s} s↑.priou←p↑.priou; priou← priou; p↑.priou←s; priou← end; end;{then} (‘without’ else write in (‘without’); end; {insert_dulist} end; {insert_dulist} s↑.next←p; next← {在结点 p 前插入

4、删除操作 la。 双向循环链表的哨兵为 la。删除该链表中的第 i 个结点 q (i:integer; la:dupointer); procedure delet_dulist (i:integer;var la:dupointer); begin (i,la); p←get_dulist (i,la); 结点 p} if p<>nil then begin 结点 p } next↑ priou← priou; p↑.priou↑.next←p↑.next; p↑.next↑.priou←p↑.priou; priou↑ next← next; disPose(p); disPose(p); end (‘without’ else writeln (‘without’); end; end;{delet_dulist} 三 双向循环链表的应用实例 在带尾指针( 指向尾结点) 1. 在带尾指针(链表指针 clist 指向尾结点)的非空循环单链表中每个结点都以 next 字 段的指针指向下一个节点。假定其中已经有 个以上的结点。下面哪些说法是正确的: 段的指针指向下一个节点。假定其中已经有 2 个以上的结点。下面哪些说法是正确的: {从双向循环链表中删除 {寻找双向循环链表中的第 i 个

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

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

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

在树中,一个结点包含一个元素以及所有指向其子树的分支,其中除根结点外, 在树中,一个结点包含一个元素以及所有指向其子树的分支,其中除根结点外,有后 件的结点称为分支结点。而没有后件的结点称为树叶。由树的定义可知, 件的结点称为分支结点。而没有后件的结点称为树叶。由树的定义可知,树叶本身也是其 父结点的子树。 ))中 为根起点, 父结点的子树。如(图 3.1—1(b))中,r 为根起点,w,h,e,f,s,m,o,n,j,u 为叶结点; 到结点 rcti。 为叶结点;从根 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, 的集合{Ta Tb,Tc}就为森林 {Ta, 就为森林。 的三棵子树 Ta,Tb,Tc 的集合{Ta,Tb,Tc}就为森林。 所谓有序树是指树中同层结点从左而右排列,其次序不容互换,这样的树称为有序树。 所谓有序树是指树中同层结点从左而右排列,其次序不容互换,这样的树称为有序树。 二、树的表示方法和存储结构 树的表示方法很多。例如( 采用的就是自然界的树形表示法, 树的表示方法很多。例如(图 3.1—1)采用的就是自然界的树形表示法,常用的还有括号 表示法: 表示法: 先将根结点放入一对圆括号中,然后把它的子树按由左而右的顺序放入括号中, 先将根结点放入一对圆括号中,然后把它的子树按由左而右的顺序放入括号中,而对子树 也采用同样方法处理: 也采用同样方法处理: 同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。 同层子树与它的根结点用圆括号括起来,同层子树之间用逗号隔开,最后用闭括号括起来。 例如( 1(b)) 例如(图 3.1—1(b))可写成如下形式 (r(a(w,x(d(h),e)),b(f),c(s,t(i(m,o,n),j),u))) ),e)),b ),c ),j),u

而树的存储结构有多种,其中使用较多的是链式存储结构。由于树中结点可以有多个元素, 而树的存储结构有多种,其中使用较多的是链式存储结构。由于树中结点可以有多个元素, 所以可以用多重链表来描述比较方便。所谓多重链表, 所以可以用多重链表来描述比较方便。所谓多重链表,就是每个结点由数据域和 n(n 为树 的度) 个域组成,其表示方法如下: 的度)个指针域共 n+1 个域组成,其表示方法如下: n=树的度 树的度; Const n=树的度; Type treetype=↑node; treetype=↑node; de 型} node=record data:datatype; data:datatype; 域} next:array[1‥ treetype; next:array[1‥n] of treetype; 域} end; end; Var root:treetype; root:treetype; 针} 例如( 1(b))的树, 例如(图 3.1—1(b))的树,其多重链表为 {根结点指 {指向各儿子的指针 {数据 {结点类

显然, 取树的度作为每个结点的链域数 即指向儿子结点的指针数)虽使各种算法简化, (即指向儿子结点的指针数)虽使各种算法简化, 显然, 但会造成存储空间的大量浪费。因为可能有很多结点中存在空链域。容易验证, 但会造成存储空间的大量浪费。因为可能有很多结点中存在空链域。容易验证,一棵具有 n n*(k个空链域,因此需要寻找一种恰当的树形式, 个结点且度为 K 的树中必存在 n*(k-1)+1 个空链域,因此需要寻找一种恰当的树形式,即 要使每个结点的结构相同、又要尽可能减少存储空间的浪费 方便运算。下面将要看到, 少存储空间的浪费, 要使每个结点的结构相同、又要尽可能减少存储空间的浪费,方便运算。下面将要看到, 用二叉树来表示树,就能达到这个目的。 用二叉树来表示树,就能达到这个目的。 §3.2 二叉树 一、二叉树的基本概念和基本性质 1、二叉树的基本概念 二叉树是一种很重要的非线性数据结构,它的特点是每个结点最多有两个后件, 二叉树是一种很重要的非线性数据结构,它的特点是每个结点最多有两个后件,且其子树 有左右之分(次序不能任意颠倒)。下面给出二叉树的递归定义: )。下面给出二叉树的递归定义 有左右之分(次序不能任意颠倒)。下面给出二叉树的递归定义: 二叉树是以结点为元素的有限集,它或者为空,或者满足以下条件: 二叉树是以结点为元素的有限集,它或者为空,或者满足以下条件:

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

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

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

k(k≥1)的二叉树中最多有 2k- 个结点。 性质 2:在深度为 k(k≥1)的二叉树中最多有 2k-1 个结点。 证明 2i- 个结点, 个结点。 由性质 1, 在二叉树第 i 层上最多有 2i-1 个结点, 因此深度为 k 的二叉树最多有 个结点。

在任何二叉树中, 性质 3:在任何二叉树中,叶子结点数总比度为 2 的结点多 1。 证明 n0—二叉树的叶结点数; n1— 的结点数; n2— 设 n0—二叉树的叶结点数;n1—二叉树中度为 1 的结点数; n2—二叉树中度为 2 的结点 数; n=n0+n1+n2 (1)

由于二叉树中除了根结点外,其余每个结点都有且仅有一个分支进入。 由于二叉树中除了根结点外,其余每个结点都有且仅有一个分支进入。设 B 为进入分支的 总数, 总数,因此 n=B+1 ( 2)

的结点射出的, 又由于所有的进入分支是由度为 1 和度为 2 的结点射出的,因此又有 B=n1+2n2 将(3)代入(2)得出 代入( n=n1+2n2+1 比较( 比较(1)和(4),得出 ),得出 n0=n2+1 即叶子数比度为 2 的结点数多 1 二、树或森林转换成二叉树 1、普通有序树转换成二叉树 我们在§ 中曾讲过,在用多重链表示普通树时,会浪费存储空间。另外, 我们在§3.1 中曾讲过,在用多重链表示普通树时,会浪费存储空间。另外,由于树 中各结点的度各不相同,因此对树中各结点的搜索比较困难。在实际应用中, 中各结点的度各不相同,因此对树中各结点的搜索比较困难。在实际应用中,往往将普通 树转化成二叉树,这种处理是极其有利的。 树转化成二叉树,这种处理是极其有利的。 (4) (3)

的规则如下: 假设所讨论的普通树为有序树 T,则将其转化成二叉树 T’的规则如下: 中的结点一一对应; ⑴T 中的结点与 T’中的结点一一对应; N1, 的左儿子结点; ⑵T 中某结点 N 的第一个儿子结点为 N1,则在 T’中 N1 为对应结点 N 的左儿子结点; 以后的其它子结点, ⑶T 中某结点 N 的第一个儿子结点 N1 以后的其它子结点,在 T’中被依次链接成一串 的右儿子结点; 开始于 N1 的右儿子结点; 由上述转化规则可以看出,一棵有序树转化成二叉树的根结点是没有右子树的, 由上述转化规则可以看出,一棵有序树转化成二叉树的根结点是没有右子树的,并且除保 留每个结点的最左分支外,其余分支应去掉, 留每个结点的最左分支外,其余分支应去掉,然后从最左的儿子开始依次连接该结点的全 部儿子。例如将( 所示的普通有序树转换成二叉树( 部儿子。例如将(图 3.2—3(a))所示的普通有序树转换成二叉树(图 3.2—3(b))

2、森林转换为二叉树 F={T1,…Tm}由 棵互不相交的普遍有序树组成。 设森林 F={T1,…Tm}由 m 棵互不相交的普遍有序树组成。 我们可以按下述规则将森林 F 转 B={root,LB, 换成一棵二叉树 B={root,LB,RB}: 为空(m=0), ),则 为空树; ⑴若 F 为空(m=0),则 B 为空树; 非空( ),则 root(T1); ⑵若 F 非空(m≠0),则 B 的根 root 即为森林中第一棵树的根 root(T1);B 的左子树 F1={T11,T12, T1k}转换而成的二叉树 转换而成的二叉树; LB 是从 T1 的根结点的子树森林 F1={T11,T12,…T1k}转换而成的二叉树;其右子树 RB 是 F2={T2,T3, Tm}转换成的二叉树 转换成的二叉树。 从森林 F2={T2,T3,…,Tm}转换成的二叉树。 例如

由此可见, 由此可见,森林转换成二叉树的方法为 ⑴将各棵树的根相连; 将各棵树的根相连; ⑵将森林中的每棵树转换成相应的二叉树; 将森林中的每棵树转换成相应的二叉树; ⑶以第一棵树为轴心,顺时针粗略地旋转 900; 以第一棵树为轴心,顺时针粗略地旋转 900; 三、二叉树的存储结构 二叉树的存储结构有两种形式 1、 顺序存储结构 将每个结点依次存放在一维数组中,用数组下标指示结点编号, 将每个结点依次存放在一维数组中,用数组下标指示结点编号,编号的方法是从根结 然后由左而右进行连续编号。 点开始编号 1,然后由左而右进行连续编号。每个结点的信息包括

数据值: 数据值: 父结点编号: 父结点编号:

data prt

左儿子结点编号: 左儿子结点编号: lch 右儿子结点编号: 右儿子结点编号: rch 满二叉树和完全二叉树一般采用顺序存储结构 满二叉树和完全二叉树一般采用顺序存储结构 m=树中结点数上限 树中结点数上限; Const m=树中结点数上限; Type node=record 点类型} 点类型} data:datatype; data:datatype; {数据值} 数据值} prt,lch,rch: prt,lch,rch:0‥m; 子编号} 子编号} end; end; treetype=array[1‥ node; treetype=array[1‥m] of node; 表类型} 表类型} Var Tree:treetype; Tree:treetype; {二叉树} 二叉树} {二叉树的顺序 {父结点、左儿子、右儿 父结点、左儿子、 {结 {结

例如采用数组 tree 存储二叉树

下面我们将普通有序树转换成二叉树, 存储转换结果。 下面我们将普通有序树转换成二叉树,并使用顺序存储结构 Tree 存储转换结果。普通有序 树的输入信息含 n 行,其中第 i 行(1≤i≤n)的元素依次为 ai。 的儿子序列, 结点 i 的数据值 ai。 以后各元素为结点 i 的儿子序列, 0 结束。 ai 后仅含一个 0, 以 结束。 若 为叶子。 则说明结点 i 为叶子。

例如( (a))的多叉树对应的输入信息为 例如(图 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 转换过程如下: 转换过程如下: (tree, sizeof tree) 0) (tree) , ; fillchar tree, 叉树初始化} 叉树初始化} i← 1; 输入} 输入} {二

{从结点 1 开始

i≤ while i≤n do 重复} 重复} begin ai; data←ai; 读结点 i 的数据值 ai;tree[i] .data←ai; 读结点 i 的第一个儿子序号 j; if j<>0 then 非叶子} 非叶子} begin tree[i].lch← tree[i].lch←j;tree[j].prt←i; tree[j].prt← 儿子} 儿子} p← j; 点} repeat 读结点 i 的下一个儿子序号 j; if j<>0 then begin tree[p].rch← tree[j].prt← tree[p].rch←j;tree[j].prt←p; 子} p← j; end; end;{then} j=0; until j=0; 信息} 信息} end; end;{then} i←i+1;换行; i+1;换行; 息} end; end;{while}

{若多叉树信息末输入处理完,则 若多叉树信息末输入处理完,

{若结点 {若结点 j

{结点 j 作为结点 i 的左

{从结点 j 出发转换其它兄弟结

{结点 j 作为结点 p 的右儿

的所有儿子 {直至处理完结点 i 的所有儿子

{准备输入结点 i+1 的儿子信

例如( (a))的多叉树经上述转换运算后得出的 数组如下: 例如(图 3.2-3(a))的多叉树经上述转换运算后得出的 tree 数组如下: data prt lch rch

1 2 3 4 5 6 7 8 9

‘ r’ ‘ a’ ‘ b’ ‘ c’ ‘ w’ ‘ x’ ‘ f’ ‘ s’ ‘ t’

0 1 2 3 2 5 3 4 8 9 6

2 5 7 8 0

0 3 4 0 6

11 0 0 0 0 9

13 10 0 0

10 ‘u’ 11 ‘d’ 12 ‘e’ 13 ‘i’ 14 ‘j’ 15 ‘h’ 16 ‘m’ 17 ‘o’ 18 ‘n’

15 12 0

11 0 9

16 14 0 0 17 18 0

13 0 11 0 13 0 16 0 17 0

2、 链式存储结构 对于一般的二叉树,通常采用链式分配,即用二重链表表示一般的二叉树。 对于一般的二叉树,通常采用链式分配,即用二重链表表示一般的二叉树。这种链式 分配即可以采用静态数据结构(数组),又可以采用动态数据结构(指针)。 ),又可以采用动态数据结构 )。人们一般采 分配即可以采用静态数据结构(数组),又可以采用动态数据结构(指针)。人们一般采 用后者。由于二叉树中每个结点通常包括数据元素和两个分支。 用后者。由于二叉树中每个结点通常包括数据元素和两个分支。因此二叉树对应的二重链 表中每个结点应有三个域: 表中每个结点应有三个域:

值域: 值域:

data

左指针域: 左指针域: lch 右指针域: 右指针域: rch 这种链表也称为二叉链表。 这种链表也称为二叉链表。二叉链表头指针 bt 指向二叉树的根结点 Type bitrpetr=↑bnode; bitrpetr=↑bnode; 型} benode=record 型} data:datatype; data:datatype; 域} lch,rch:bitreptr; lch,rch:bitreptr; 域} end; end; Var bt: bitreptr; bt: bitreptr; 针} 例如用( ))所示的二叉链表存储二叉树 所示的二叉链表存储二叉树( 例如用(图 3.2-6(b))所示的二叉链表存储二叉树(图 3.2-6(b))。 {头指 {左指针域和右指针 {值 {结点类 {结点指针类

四、树的遍历 1、二叉树的遍历 所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。 所谓二叉树的遍历是指按照一定的规律不重复地访问二叉树中的每一个结点。在访问 到每个结点时,可以取出结点中的信息,亦可以对结点作其它的处理,对于线性结构来说, 到每个结点时,可以取出结点中的信息,亦可以对结点作其它的处理,对于线性结构来说, 遍历并非难事,但对二叉树来说,由于它是一种非线性结构, 遍历并非难事,但对二叉树来说,由于它是一种非线性结构,必须要找到一种完全而有规 则的遍历方法,通过遍历得到二叉树中各个结点信息的线性序列 信息的线性序列。 则的遍历方法,通过遍历得到二叉树中各个结点信息的线性序列。

分别表示遍历左子树、访问根结点、遍历右子树, 如果用 L、D、R 分别表示遍历左子树、访问根结点、遍历右子树,则对二叉树的遍历 可以有下列六种组合: 可以有下列六种组合: LDR、 LRD、 DLR、 DRL、RDL、 LDR、 LRD、 DLR、 DRL、RDL、 RLD 若再限定先左后右的次序, 若再限定先左后右的次序,则只剩下三种组合 LDR、 LRD、 LDR、 LRD、 DLR 这三种遍历规则分别称为中序遍历。后序遍历和前序遍历。 这三种遍历规则分别称为中序遍历。后序遍历和前序遍历。下面分别介绍这三种遍历的方 在讲解过程中,二叉树的存储采用动态的二重链表形式。 法。在讲解过程中,二叉树的存储采用动态的二重链表形式。 为了方便叙述,我们以( 为例,解释三种遍历规则。 为了方便叙述,我们以(图 3.2-7)为例,解释三种遍历规则。

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

bt>↑ Data; 访问处理 bt>↑.Data; preorder(bt↑ lch); preorder(bt↑.lch); 左子树} 左子树} preorder(bt. rch); preorder(bt.↑rch); 右子树} 右子树} end; end;{then} end; end;{preorder} {递归遍历 {递归遍历

⑵中序遍历 中序遍历的规则如下: 中序遍历的规则如下: 若二叉树为空,则退出; 若二叉树为空,则退出;否则 ⑴中序遍历左子树; 中序遍历左子树; ⑵访问处理根结点; 访问处理根结点; ⑶中序遍历右子树; 中序遍历右子树; 若中序遍历( 中的二叉树,可以得到如下的中序序列: 若中序遍历(图 3.2—7)中的二叉树,可以得到如下的中序序列: d b h e i a f c g 算法如下: 算法如下: inorder(bt:bitreptr); procedure inorder(bt:bitreptr); begin if bt<>nil then begin inorder(bt↑ lch); inorder(bt↑.lch); 左子树} 左子树} bt↑ data; 访问处理 bt↑.data; {递归遍历

inorder(bt↑ rch); inorder(bt↑.rch); 右子树} 右子树} end; end;{then} end; end;{inorder}

{递归遍历

⑶后序遍历 后序遍历的规则如下: 后序遍历的规则如下: 若二叉树为空,则退出; 若二叉树为空,则退出;否则 ⑴后序遍历左子树; 后序遍历左子树; ⑵后序遍历右子树; 后序遍历右子树; ⑶访问处理根结点; 访问处理根结点; 若后序遍历( 中的二叉树, 若后序遍历(图 3.2—7)中的二叉树,可以得到如下的后序序列 d h i e b f g c a 算法如下: 算法如下: (bt:bitreptr); procedure postorder (bt:bitreptr); begin if bt<>nil then begin (bt↑ lch); postorder (bt↑.lch); 左子树} 左子树} postorder(bt↑ rch); postorder(bt↑.rch); 右子树 右子树} bt↑ data; 访问 bt↑.data; end; end;{then} end; end;{postorder} {递归遍历 {递归遍历

§3.3 树的应用举例

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

图结构在人工智能、数学、物理、化学、计算机科学等许多领域被广泛应用。 图结构在人工智能、数学、物理、化学、计算机科学等许多领域被广泛应用。奥林匹克信 息学竞赛的许多试题,亦需要用图来描述数据元素间的联系。 息学竞赛的许多试题,亦需要用图来描述数据元素间的联系。 §4.1 图的基本概念和存储结构 一、图的基本概念 G=( 如果数据元素集合 D 中的各元素之间存在任意的前后件关系 R,则此数据结构 G=(D, 称为图。如果将数据元素抽象为结点,元素之间的前后件关系用边表示, R)称为图。如果将数据元素抽象为结点,元素之间的前后件关系用边表示,则图亦可以表 G=( ),其中 是结点的有穷(非空)集合, 为边的集合。 示为 G=(V,E),其中 V 是结点的有穷(非空)集合,E 为边的集合。如果元素 a 是元素 b 的前件,这种前后件关系对应的边用(a b)表示 (a, 表示, (a,b)∈ 的前件,这种前后件关系对应的边用(a,b)表示,即(a,b)∈E。 G=( (a,b)∈ 必有( 在图 G=(V,E)中,如果对于任意的 a,b∈V,当(a,b)∈E 时,必有(b,a)∈E(即 对称),对称此图为无向图; ),对称此图为无向图 (a,b)∈ (b, 关系 R 对称),对称此图为无向图;如果对于任意的 a,b∈V,当(a,b)∈E 时 ,(b,a) 未必成立,则称此图为有向图。在有向图中, ∈E 未必成立,则称此图为有向图。在有向图中,通常用带箭头的边连接两个有关联的结点 方向由前件指向后件);而对一无向图,用不带箭头的边连接两个有关联的结点。 );而对一无向图 (方向由前件指向后件);而对一无向图,用不带箭头的边连接两个有关联的结点。例如 (a))为无向图,( ,(图 (b))为有向图。 (图 4.1—(a))为无向图,(图 4.1—(b))为有向图。

个结点的无向图中, 在具有 n 个结点的无向图中,边的最大数目为 。而边数达到最大值的图称为无向完 全图。( 。(图 (A))所示的图是无向完全图。 全图。(图 4.1—(A))所示的图是无向完全图。 在无向图中一个结点相连的边数称为该结点的度,例如( 1(A)) 在无向图中一个结点相连的边数称为该结点的度,例如(图 4.1—1(A))中结点 1、 有向图中一个结点的后件个数称为该结点的出度, 结点 2、结点 3、结点 4 的度分别为 1。有向图中一个结点的后件个数称为该结点的出度, 其前件个数称为该结点的入度。一个结点的入度和出度之和称为该结点的度。 其前件个数称为该结点的入度。一个结点的入度和出度之和称为该结点的度。图中结点的 最大度数称为图的度。例如( 1(B)) 最大度数称为图的度。例如(图 4.1—1(B))中结点 1 的出度和入度分别为 1,结点 1 和 的结点 1 度都为 2。整个图的度为 2。

x1…… ……xk(k>1) 在图 G=(V,E)中,如果对于结点 a,b,存在满足下述条件的结点序列 x1……xk(k>1) x1=a, 1 x1=a,xk=b (xi,xi+1)∈ 2 (xi,xi+1)∈E i=1‥ i=1‥k-1

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

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

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

A1=

A2=

可以明显地看出, A1[i,j]=A1[j,i](1≤ 由相邻矩阵 A1 和 A2 可以明显地看出,无向图的相邻矩阵 A1[i,j]=A1[j,i](1≤i, n)且对角线上的 A[i,i]均为 )。正因为如此 正因为如此, j≤n)且对角线上的 A[i,i]均为 0(或 )。正因为如此,在实际存储相邻矩阵时只需存储 其上三角(或下三角)的元素 个结点的无向图, 其上三角(或下三角)的元素。因此具有 n 个结点的无向图,其相邻矩阵的存储容量可节约 A2[i,j]不一定与 A2[j,i](1≤ n)相同 相同, 至 。而有向图的相邻矩阵中 A2[i,j]不一定与 A2[j,i](1≤i,j≤n)相同,且图中出现 A2[i,i]也不一定是 自反边时其对角线上的 A2[i,i]也不一定是 0(或 )。 用相邻矩阵表示图,容易判定任意两个结点之间是否有边相联, 用相邻矩阵表示图,容易判定任意两个结点之间是否有边相联,并容易求得各个结点的度 对于无权无向图的相邻矩阵, 的度数; 数。对于无权无向图的相邻矩阵,第 i 行元素值的和就是 Vi 的度数;对于无权有向图的相 邻矩阵, 的出度, 的入度; 邻矩阵,第 i 行元素值的和就是 Vi 的出度,第 i 列元素值的和就是 Vi 的入度;对于有权 无向图的相邻矩阵, 中元素值<>0 的度数; 无向图的相邻矩阵,第 i 行(或第 i 列)中元素值<>0 的元素个数就是 Vi 的度数;对于有 权有向图的相邻矩阵, 行中元素值<>0 的出度; 列元素值<>0 权有向图的相邻矩阵,第 i 行中元素值<>0 的元素个数就是 Vi 的出度;第 i 列元素值<>0 的入度。在无权有向图或无向图中, Vi、 的元素个数就是 Vi 的入度。在无权有向图或无向图中,判定两个结点 Vi、Vj 之间是否存 的路径, Am=A*A*……*A( ……*A 矩阵相乘后的乘积矩阵) 在长度为 m 的路径,只要考虑 Am=A*A*……*A(m 个 A 矩阵相乘后的乘积矩阵)中(i,j) 就行了。 的元素值是否为 0 就行了。

2、图的邻接表表示法 用相邻矩阵表示图,占用的存储单元数只与结点数有关而与边数无关。 用相邻矩阵表示图,占用的存储单元数只与结点数有关而与边数无关。一个含 n 个结 点的图, 多得多,那么其相邻矩阵是一个稀疏矩阵, 点的图,若其边数比 n2 多得多,那么其相邻矩阵是一个稀疏矩阵,占用许多空间来存储 0 当然是无端浪费。 果用邻接表表示法来存储图, (或 )当然是无端浪费。如果用邻接表表示法来存储图,则占用的存储单元既与图的结点 数有关,又与边数有关。 个结点的图,如果边数少,则占用的存储单元也少。 数有关,又与边数有关。同样是 n 个结点的图,如果边数少,则占用的存储单元也少。 个边表( 同邻接表法表示图需要保存一个顺序存储的结点表和 n 个边表(每个边表为一个单链 存储与一个结点相连的所有边的信息)。结点表的每个表目对应于图的一个结点, )。结点表的每个表目对应于图的一个结点 表,存储与一个结点相连的所有边的信息)。结点表的每个表目对应于图的一个结点,包 括: ⑴结点信息,即 结点信息, 与该结点相连的边数( ? 与该结点相连的边数(m); 访问标志(visited); ? 访问标志(visited); ⑵边表的首指针(firstarc)。图中每个结点都有一个边表,其中每一个结点对应 边表的首指针(firstarc)。图中每个结点都有一个边表, )。图中每个结点都有一个边表 于与该结点相关联的一条边, 于与该结点相关联的一条边,包括 与此边相关联的另一个结点序号( ? 与此边相关联的另一个结点序号(V); 若为带权图的话,该边的权值( ? 若为带权图的话,该边的权值(W); 指向边表的下一个结点的后继指针(nextarc); ? 指向边表的下一个结点的后继指针(nextarc); 邻接表的定义如下: 邻接表的定义如下:

max=图的结点数上限 图的结点数上限; const max=图的结点数上限; Type arcptr=↑arcnode; arcptr=↑arcnode; 指针类型} 指针类型} arcnode=record; arcnode=record; 结点类型} 结点类型} v:integer; integer; 端点序号} 端点序号} nextar:arcptr; nextar:arcptr; 后继指针} 后继指针} w:real; real; 的权值} 的权值} end; end; vexnode=record 表目类型} 表目类型} m:integer; integer; 连的边数} 连的边数} visited:boolean; visited:boolean; {访问标志} 访问标志} firstarc:arcptr; firstarc:arcptr; 表的首指针} 表的首指针} end; end; adjlist=array[1‥ vexnode; adjlist=array[1‥max]of vexnode; 邻接表类型} {邻接表类型} var dig:adjlist; dig:adjlist; 邻接表} {邻接表} integer; n,e :integer; 数和边数} 数和边数} {结点 {边 {结点表的 {结点表的 {该边 {边表的 {关联该边的另一 {边表的 {边表的

{与该结点相

用邻接表结构存贮图的过程如下: 用邻接表结构存贮图的过程如下: 读 n 和 e; i: for i:=1 to n do 点表初始化} 点表初始化} begin with dig[i] do begin m←0;firstarc←nil;visited←false; firstarc←nil;visited←false; end; end;{with} end; end;{for} i: for i:=1 to e do begin 条边<vj vk>关联的结点序号 <vj, Wjk; 读第 i 条边<vj,vk>关联的结点序号 j,k 和该边的权 Wjk; dig[j]. dig[j].m+1; dig[j].m←dig[j].m+1; new[q]; new[q]; q↑ with q↑do begin v←k;w←wjk;nextarc←dig[j].firstarc; wjk;nextarc←dig[j].firstarc; end; end;{with} dig[j].firstarc← dig[j].firstarc←q; end; end;{for} {结 {结

例如( 4(a)) 对应的邻接表表示如( 4(b)) 例如(图 4.1—4(a))中有向图 G 对应的邻接表表示如(图 4.1—4(b))

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

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

出发,深度优先搜索的递归过程如下: 从 vi 出发,深度优先搜索的递归过程如下: (i:integer); procedure dfs (i:integer); begin 访问处理结点 i; dig[i].visited←true; dig[i].visited←true; 已访问标志} 已访问标志} q←dig[i].firstarc; dig[i].firstarc; 所有子树} vi 所有子树} {按深度优先搜索的顺序遍历 {置 vi

while q<>nil do begin dig[q↑ v]. dfs(q↑ v); if dig[q↑.v].visited=false then dfs(q↑.v); arc; q←q↑.next arc; end; end;{while} end; end;{dfs} dfs(i), 所在的连通分支( 调用一次 dfs(i),可按深度优先搜索的顺序访问处理结点 i 所在的连通分支(或强连通分 )。整个图按深度优先搜索顺序遍历的过程如下 整个图按深度优先搜索顺序遍历的过程如下: 支)。整个图按深度优先搜索顺序遍历的过程如下: procedure traver1; procedure traver1; begin i: dig[i].visited←false; for i:=1 to n do dig[i].visited←false; 结点未访问标志} 结点未访问标志} {置所有

i: dig[i]. dfs[i]; for i:=1 to n do if dig[i].visited=false then dfs[i]; {深度优先搜 索每一个未访问的结点} 索每一个未访问的结点} end; end;{traver1}

2、广度优先搜索 广度优先搜索类似于树的按层次遍历的过程。 广度优先搜索类似于树的按层次遍历的过程。 假设从图中某结点 出发, 的各个未曾访问的邻接点, 假设从图中某结点 v0 出发,在访问了 v0 之后依次访问 v0 的各个未曾访问的邻接点, 然后分别从这些邻接点出发按广度优先搜索的顺序遍历图, 然后分别从这些邻接点出发按广度优先搜索的顺序遍历图,直至图中所有可被访问的结点 都被访问到。若此时图中尚有结点未被访问,则任选其中的一个作起始点,重复上述过程, 都被访问到。若此时图中尚有结点未被访问,则任选其中的一个作起始点,重复上述过程, 直至图中所有结点都被访问到为止。换句话说, 直至图中所有结点都被访问到为止。换句话说,按广度优先顺序搜索遍历图的过程是以 v0 为起始点,由近及远, ……的结点 的结点。 为起始点,由近及远,依次访问和 v0 有路径相连且路径长度为 1,2,3……的结点。 假如以( 4(a))中的有向图为例, 出发按广度优先搜索的顺序遍历, 假如以(图 4.1—4(a))中的有向图为例,从 v3 出发按广度优先搜索的顺序遍历,得 v3→v2→v4→v1→ 到的结点序列是 v3→v2→v4→v1→v5 由于队列“先进先出”的存取规则与广度优先搜索的遍历顺序相吻合, 由于队列“先进先出”的存取规则与广度优先搜索的遍历顺序相吻合,因此使用了一个工 按访问的先后顺序存储被访问过的结点序号。 作队列 q,按访问的先后顺序存储被访问过的结点序号。从结点 vi 出发广度优先搜索的过 程如下: 程如下:

(i:integer); procedure bfs (i:integer); begin 访问处理结点 i; dig[i].visited←true; dig[i].visited←true; 已访问标志} 已访问标志} 结点 i 进入队列 q; while 队列 q 非空 do begin 从队列 q 中移出队首元素 v; dig[v].firstarc; p←dig[v].firstarc; 有相邻结点} 有相邻结点} while p<>nil do begin dig[p↑ v]. if dig[p↑.v].visited=false then begin dig[p↑ v].visited←true; 访问 p↑.v; dig[p↑.v].visited←true; p↑.v 进入队列 q; end; end;{then} p←p↑.nextarc; nextarc; end; end;{while} end; end;{while} end; end;{bfs} bfs(i)可按广度优先搜索的顺序访问处理结点 调用一次 bfs(i)可按广度优先搜索的顺序访问处理结点 i 所在的连通分支 或强连通分支) (或强连通分支) 。 整个图按广度优先搜索顺序遍历的过程如下: 整个图按广度优先搜索顺序遍历的过程如下: traver2; procedure traver2; {依次访问 v 的所 {置 vi

begin i: dig[i].visited←false; for i:=1 to n do dig[i].visited←false; 结点未访问标志} 结点未访问标志} {置所有

i: dig[i]. bfs[i]; for i:=1 to n do if dig[i].visited=false then bfs[i];{广度优先搜 索每一个未访问的结点} 索每一个未访问的结点} end; end;{traver2}

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

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

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

2、计算最小生成树 下面我们来讨论最小生成树的算法。 下面我们来讨论最小生成树的算法。

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

⑵构造最小生成树 从任意结点开始( vn)构造最小生成树:首先把这个结点包括进生成树里, 从任意结点开始(不妨设为 vn)构造最小生成树:首先把这个结点包括进生成树里, 然后在那些其一个端点已在生成树里、 然后在那些其一个端点已在生成树里、另一端点还未在生成树里的所有边中找出权最小的 一条边,并把这条边、包括不在生成树的另一端点包括进生成树, 依次类推, 一条边,并把这条边、包括不在生成树的另一端点包括进生成树,…。依次类推,直至将 所有结点都包括进生成树为止 当有两条具有同样最小权的边可供选择时,选哪条都行。 为止。 所有结点都包括进生成树为止。当有两条具有同样最小权的边可供选择时,选哪条都行。 因此最小生成树的形式不是唯一的。 就是( 因此最小生成树的形式不是唯一的。 例如 图 4. —3(b)) (图 4. —3(c)) ( 2 3(b)) 和 2 3(c)) 就是(图 4. 2 3(a))的两棵形式不同的最小生成树 但它们权的总和相等。 的两棵形式不同的最小生成树, —3(a))的两棵形式不同的最小生成树,但它们权的总和相等。 我们可以通过反证法证明上述算法的正确性: 我们可以通过反证法证明上述算法的正确性: vx,vy∈ (vx,vy)∈ vx∈ (vx,vy)的权 假设 vx,vy∈V,(vx,vy)∈E,vx∈最小生成树 T’,vy 最小生成树 T’,(vx,vy)的权 值在待扩展边集中最小,而最终生成的最小生成树中并不包含这条边。 是连通的, 值在待扩展边集中最小,而最终生成的最小生成树中并不包含这条边。由于 T’是连通的, vx, vy。把边(vx,vy)加入T 中得到一个回路 vx…vy, 因此有从 vx 到 vy 的路径 vx,…,vy。把边(vx,vy)加入T’中得到一个回路 vx…vy, vx。 vx… =(vp, vq), vp∈ , T’ W(e’ )>W(e)。 vx。 子路径 vx…vy 中必有边 e’ =(vp, , vq) 其中 vp∈T’ vq T’ 由条件可知 W(e’ , )>W(e)。 回路打开, 的各边权和, 从回路中去掉 e’,回路打开,成为另一棵生成树 T”且各边权和不大于 T’的各边权和, 是一棵包括边(vx,vy)的最小生成集,与假设矛盾。 因此 T”是一棵包括边(vx,vy)的最小生成集,与假设矛盾。

下面给出构造最小生成树的算法: 下面给出构造最小生成树的算法: fillchar(t,sizeof(t), fillchar(t,sizeof(t),∞) ; i: t[i*(i+1)/2]← for i:=1 to n do t[i*(i+1)/2]←0; 未包括进生成树} 未包括进生成树} i: for i:=1 to 边数 e do 三角元素} 三角元素} begin {所有结点

{输入相邻矩阵的下 {输入相邻矩阵的下

条边<vx vy>; <vx, 读第 i 条边<vx,vy>; t[x*(x-1)/2+y]← if x>y then t[x*(x-1)/2+y]←wxy t[y*(y-1)/2+x]←wxy; else t[y*(y-1)/2+x]←wxy; end{for} t[n*(n+1)/2]← t[n*(n+1)/2]←1; 1)/2] 小生成树} 小生成树} k: for k:=2 to n do 条边} 的 n-1 条边} begin min←∞; min←∞; ←∞ i: for i:=1 to n do 成树里的边} 成树里的边} if t[i*(i+1)/2]=1 在生成树中} 在生成树中} then begin j: for j:=1 to n do if t[j*(j+1)/2]=0 在生成树中} 在生成树中} then begin l←i*(iif j<i then l←i*(i-1)/2+j 中的位置 位置} 素在 t 中的位置} l←j*(j-1)/2+i; else l←j*(j-1)/2+i; if t[l]<min then 最小,则记下} 最小,则记下} min←t[l]; end; begin min←t[l];p←l;q←j;end;{then} end; end;{then} end; end;{then} {若 el=<vi,vj>的权目前 {若 el=<vi,vj>的权目前 {计算(i,j)元 计算( {若 vj 不 {搜索那些其一个端点已在生成树里、另一端点还未在生 搜索那些其一个端点已在生成树里、 {vn 进入最

{顺序构造最小生成树

{若 vi

t[q*(q+1)/2]← t[p]← t[p]; t[q*(q+1)/2]←1;t[p]←-t[p]; 加入最小生成树} 加入最小生成树} end; end;{for} i: for i:=2 to n do j: ifor j:=1 to i-1 do

{vq 和相连的权最小的边 el

t[i*(i输出最小生成树的边( if t[i*(i-1)/2+j]<0 then 输出最小生成树的边(i,j);

§4.3 最短路径问题 这一章节讲一个比较简单但又是很重要的问题—最短路径问题。 这一章节讲一个比较简单但又是很重要的问题—最短路径问题。这个问题有着大量的 生产实际的背景。 实上大至海陆空各种运输,小至一个人每天上班,都会遇到这一问题。 生产实际的背景。事实上大至海陆空各种运输,小至一个人每天上班,都会遇到这一问题。 甚至有些问题从表面上看与最短路径问题没有什么关系,却也可以归结为最短路径问题。 甚至有些问题从表面上看与最短路径问题没有什么关系,却也可以归结为最短路径问题。 下面就举一个这样的例子: 下面就举一个这样的例子: 一个人带了一只狼、一只羊和一颗白菜想要过河。河上有一只独木船,每次除了人以外, 一个人带了一只狼、一只羊和一颗白菜想要过河。河上有一只独木船,每次除了人以外, 只能带一样东西,另外如果人不在旁时狼就要吃羊,羊就要吃白菜。问应该怎样安排渡河, 只能带一样东西,另外如果人不在旁时狼就要吃羊,羊就要吃白菜。问应该怎样安排渡河, 才能做到即把所有东西都带过河,而且在河上来回的次数又最少? 才能做到即把所有东西都带过河,而且在河上来回的次数又最少? 代表人, 代表狼, 代表羊, 代表白菜。 我们设变量 M 代表人,W 代表狼,S 代表羊,V 代表白菜。开始时设人和其它三样东西在河 的左岸, 表示。 的左岸,这种情况用 MWSV 表示。 我们用一个集合表示目前左岸的情况,很显然, 我们用一个集合表示目前左岸的情况,很显然,可能出现的情况有 16 种: 表示目前左岸的情况 [MWSV] [WS] [MWS] [WV] [MWV] [SV] [MSV] [M] [WSV] [W] [MW] [S] [MS] [V] [MV] [Φ [Φ ]

种可能发生狼吃羊、羊吃白菜的情况: 删除下列 6 种可能发生狼吃羊、羊吃白菜的情况: [WSV] [MW] [MV] [WS] [SV] [M]

种情况 现在我们就来构造一个图 G,它的结点就是剩下的 10 种情况。G 中的边是按下述原则来连 如果甲经过一次渡河可以变成情况乙,那么就在情况甲与情况乙之间连一条河。 的:如果甲经过一次渡河可以变成情况乙,那么就在情况甲与情况乙之间连一条河。

以后,渡河的问题就归结为下述问题了: 作出了图 G 以后,渡河的问题就归结为下述问题了:“在 G 中找一条连接结点 MWSV 与Φ, 并且包含边数最少的路” 并且包含边数最少的路”。如果我们设 G 的与各边的长度都是 1,那么也可以把渡河问题归 结为: 的最短路” 把问题转化为图的问题后, 结为:“找一条连接 MWSV 与Φ的最短路”。把问题转化为图的问题后,就可用一种系统的 方法解决,而不是通常人们所用的凑的方法和凭经验的方法。 方法解决,而不是通常人们所用的凑的方法和凭经验的方法。

下面,我们可以给最短路径问题下一个抽象的定义: 下面,我们可以给最短路径问题下一个抽象的定义: G=( 是一个有向图,它的每一条边( ),在 设 G=(V,E)是一个有向图,它的每一条边(U,V)∈E都有一个权 W(U,V),在 G 中 V0, Vj(VJ 的最短有向路找出来( 指定一个结点 V0,要求把从 V0 到 G 的每一个结点 Vj(VJ∈V)的最短有向路找出来(或者 的有向路, Vj)。 指出不存在从 V0 到 Vj 的有向路,即 V0 不可达 Vj)。 在上述定义中, 是给定的,因此我们又形象地称为单源最短路径问题。 在上述定义中,由于源结点 V0 是给定的,因此我们又形象地称为单源最短路径问题。当然 最短路径问题远不止上述一种,但它们一般都可用单源问题的算法来解决。例如: 最短路径问题远不止上述一种,但它们一般都可用单源问题的算法来解决。例如: 1、单目标最短路径问题 VJ(VJ∈ 的每条最短路径。 找出每一个结点 VJ(VJ∈V)到某指定结点 Vs 的每条最短路径。 把图中的每条边的方向反 我们就可以把这一问题变成单源最短路径问题; 向,我们就可以把这一问题变成单源最短路径问题; 2、单对顶点间最短路径问题 的最短路径。 对于给定结点 U 和 V,找出一条从 U 到 V 的最短路径。如果我们解决了源结点为 U 的单源 问题,则这问题自然获得了解决。目前还没有一种比单源算法更快的算法来解决这一问题; 问题,则这问题自然获得了解决。目前还没有一种比单源算法更快的算法来解决这一问题; 3、每对结点间的最短路径问题 的最短路径。 对于每对结点 U 和 V 找出从 U 到 V 的最短路径。我们可以将每个结点作为源点运行一次单 源算法就可以解决这一问题。但是,如果采用另一种算法( 算法), ),运行的效率将更 源算法就可以解决这一问题。但是,如果采用另一种算法(floyd 算法),运行的效率将更 高。我们将对该算法作以介绍 一、计算单源最短路径 1、算法的基本思路 解决单源最短路径的基本思想是把图中所有结点分为两组 第一组:包括已确定最短路径的结点; 第一组:包括已确定最短路径的结点; 径的结点 第二组:包括尚未确定最短路径的结点; 第二组:包括尚未确定最短路径的结点; 我们按最短路径长度递增的顺序把第二组的结点加到第一组中去, 我们按最短路径长度递增的顺序把第二组的结点加到第一组中去,直至 v0 可达的所有结点 都包含于第一组。在这个过程中, 都包含于第一组。在这个过程中,总保持从 v0 到第一组各结点的最短路径长度都不大于从 至第二组任何结点的路径长度。另外,每一个结点对应一个距离值。 v0 至第二组任何结点的路径长度。另外,每一个结点对应一个距离值。第一组结点对应的 到此结点的最短路径长度; 距离值就是由 v0 到此结点的最短路径长度;第二组结点对应的距离值就是 v0 经由第一组 结点(中间结点)至此结点的最短路径长度。具体作法是: 结点(中间结点)至此结点的最短路径长度。具体作法是: 进入第一组, 第二组包含其它所有结点,这些结点对应的 初始时 v0 进入第一组,v0 的距离值为 0;第二组包含其它所有结点,这些结点对应的 距离值这样确定( 为第二组中的结点) 距离值这样确定(设 vi 为第二组中的结点)

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

2、变量说明 下面给出算法中的变量说明 图的结点数; 设 n—图的结点数; adj—有向图的相邻矩阵。 adj—有向图的相邻矩阵。其中

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

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

3、算法流程 计算单源最短路径的过程如下: 计算单源最短路径的过程如下: fillchar(adj,sizeof(adj),0); fillchar(adj,sizeof(adj),0); 立相邻矩阵 adj} i: for i:=1 to n do j: for j:=1 to n do if( adj[i,j]← if(i,j)∈E then adj[i,j]←wij adj[i,j]←∞ ←∞; else adj[i,j]←∞; {建

i: for i:=1 to n do 集合初始化} 集合初始化} begin dist[i].length←adj[v0,i]; dist[i].length←adj[v0,i]; dist[i].length<>∞ if dist[i].length<>∞ dist[i].pre← then dist[i].pre←v0 dist[i].pre← else dist[i].pre←0; end; end;{for} adj[v0,v0]← adj[v0,v0]←1; v0 入第一组} 入第一组} repeat min←∞; min←∞; u←0; ←∞ i: for i:=1 to n do 小的结点 u} (adj[i,i]=0)and(dist[i]. if (adj[i,i]=0)and(dist[i].length<min) then begin min←dist[i].length; u←i; min←dist[i].length; end; end;{then} if u<>0 的结点} 的结点} then begin adj[u,u]← adj[u,u]←1; 入第一组} 入第一组} i: for i:=1 to n do 结点距离值} 结点距离值}

{路径 {路径

{源结点 v0 进

{从第二组中找距离值最 {从第二组中找距离值最

{第二组中存在一个距离值最小 {第二组中存在一个距离值最小

{结点 u 进

{修正第二组中 {修正第二组中 u 可达的

(adj[i,i]=0)and(dist[i].length>dist[u].length+adj[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].length←dist[u].length+adj[u,i]; dist[i] pre← dist[i].pre←u; end; end;{then} end; end;{then} u=0; until u=0; 一组为止} 一组为止} {直至 n 个结点全部加入第

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

adj—有向图的相邻矩阵。 adj—有向图的相邻矩阵。其中

path—最短路径集合。 path[i,j]为 path—最短路径集合。其中 path[i,j]为 vi 至 vj 的最短路上 vj 的前趋结点序号 (1≤ (1≤i,j≤n) Var adj:array[1‥ real; adj:array[1‥n,1‥n] of real; path:array[1‥ 0‥ path:array[1‥n,1‥n] of 0‥n;

adj(0)、 adj(n)。 这个算法的基本思想是递推地产生一个矩阵序列 adj(0)、…、adj(n)。其中 [i,j]=adj[i,j], adj( [i,j]’ adj(0) [i,j]=adj[i,j],即 adj(0)[i,j]’为 vi 到 vj 中间结点序号不大于 0(不经 过任何中间结点) 过任何中间结点)的最短路径长度 …………………… adj(k)[i,j]为 的最短路径长度; adj(k)[i,j]为 vi 到 vj 中间结点序号不大于 k 的最短路径长度; k)[i …………………… adj(n)[i, j]为 的最短路径长度, adj(n)[i,j]为 vi 到 vj 中间结点序号不大于 n 的最短路径长度,即为所要求的从 vI 至 vj 的最短路径长度; 的最短路径长度; ( 1≤ i, j≤ n) adj(0)、adj(1)、 adj(n)的过程 的过程, 递推产生 adj(0)、adj(1)、…、adj(n)的过程,就是逐步允许越来越多的结点作为路径 的中间结点,直到所有结点都允许作为中间结点时最短路径便求出来了。 的中间结点,直到所有结点都允许作为中间结点时最短路径便求出来了。假设已求得 adj(kadj(k)呢 adj(k-1) ,怎样由它推导出 adj(k)呢?vi 经由 vk 到 vj 的中间结点序号不大于 k 的最短 路径由两段组成: 路径由两段组成: 的最短路径, adj(k-1)[i,k]; ? 由 vi 至 vk 的中间结点序号不大于 k-1 的最短路径,其长度为 adj(k-1)[i,k]; 的最短路径, adj(k-1)[k,j]; ? 由 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]。 第一种情况: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)[i,j]=adj(k-1)[i,j]; 第二种情况:adj(k-1)[i,j]>adj(k-1)[i,k]+adj(k-1)[k,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, =path[k,j]; adj(k)[i,j]=adj(k-1)[i,k]+adj(k-1)[k,j],path[i,j] =path[k,j]; 下面给出算法: 下面给出算法: (adj,sizeof(adj), fillchar (adj,sizeof(adj),∞); adj( {计算 adj(0)} i: for i:=1 to n do j: for j:=1 to n do wij<>∞ adj[i,j]←wij;path[i,j]← if wij<>∞ then begin adj[i,j]←wij;path[i,j]←j;end{then} path[i,j]← else path[i,j]←0; k: for k:=1 to n do adj(0)、 adj( adj(0)、‥adj(n)} i: for i:=1 to n do 一个结点对} 一个结点对} j: for j:=1 to n do adj[i,k]+adj[k,j]<adj[i, if adj[i,k]+adj[k,j]<adj[i,j] {若 vi 经由 vk 至 vj 的路径目 前最优,则记下} 前最优,则记下} then begin adj[i,j]←adj[i,k]+adj[k,j]; adj[i,j]←adj[i,k]+adj[k,j]; path[i,j]←path[k,j]; path[i,j]←path[k,j]; end, end,{then} adj(0)、 {顺序计算 adj(0)、

{枚举每 {枚举每

算法结束时, 之间的最短路径方案是什么? 算法结束时,由矩阵 path 可推知任一结点对 i、j 之间的最短路径方案是什么? print(i,j); Procedure print(i,j); begin

if i=j then 输出 i path[i, else if path[i,j]=0 then 输出结点 i 与结点 j 之间不存在通路 else begin (i,path[i,j]); print (i,path[i,j]); 输出 j; end; end;{else} end; end;{print}

2、计算图的传递闭包 下面我们将问题再简化一些: 下面我们将问题再简化一些:对于任何结点对 i,j∈V,只要判断是否存在一条由 i 到 化一些 的路径,而不需要具体了解最短路径的长度和构成。该问题又称作图的传递闭包。 j 的路径,而不需要具体了解最短路径的长度和构成。该问题又称作图的传递闭包。显然读 者可以直接得出算法: 算法。 者可以直接得出算法:对图中的每条边赋权 1,然后对该图运行 floyd 算法。若算法结束时 adj[i,j]<n, 之间至少存在一条通路; adj[i,j]=∞ adj[i,j]<n,则表明结点 i 至结点 j 之间至少存在一条通路;若 adj[i,j]=∞,则表明结 之间无路。但这种算法如同“杀鸡用牛刀”得不偿失。 点 i 与结点 j 之间无路。但这种算法如同“杀鸡用牛刀”得不偿失。下面我们来介绍另一 种方法,该方法在实际应用中可以节省时间和空间。 种方法,该方法在实际应用中可以节省时间和空间。设

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

且对于 k≥1 tij(k)=tij(k(tik(ktkj(ktij(k)=tij(k-1) ∨ (tik(k-1) ∧tkj(k-1)) 由于布尔值的存储量少于整数且位逻辑运算的执行速度快于算术运算, 由于布尔值的存储量少于整数且位逻辑运算的执行速度快于算术运算,因此后者无论在时 间和空间上都优于前一种算法。具体运算过程如下: 间和空间上都优于前一种算法。具体运算过程如下: (t,sizeof(t),false); fillchar (t,sizeof(t),false); i: t[i,i]←true; for i:=1 to n do t[i,i]←true;

k: for k:=1 to 边数 e do begin 输入第 k 条边关联的结点序号 i,j; t[i,j]←true; t[i,j]←true; end; end;{for} k: for k:=1 to n do t(1)‥ 推 t(1)‥t(n)} i: for i:=1 to n do 一个结点对} 一个结点对} j: t[i,j]←t[i,j]or(t[i, t[k,j]); for j:=1 to n do t[i,j]←t[i,j]or(t[i,k]and t[k,j]); i: for i:=1 to n do j: t[i, for j:=1 to n do if (i<>j)and t[i,j] then 输出 vi 与 vj 间有通 路; {递 {递

{枚举每 {枚举每

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

这样的比较结果(p1,p2∈ ’‥’Z ),记为 p1>p2。 A>B,B>D, “p1 比 p2 高”这样的比较结果(p1,p2∈{‘A’‥’Z’}),记为 p1>p2。例如 A>B,B>D, F>D。士兵的身高关系如( F>D。士兵的身高关系如(图 4.4—1)所示

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

从其中任何一个结点出发,都可经由其它两个项点返回本身, 从其中任何一个结点出发,都可经由其它两个项点返回本身,因此就无法把结点排成满足 条件的序列。任何无环的有向图,其结点都可以排出一个拓扑序列。 条件的序列。任何无环的有向图,其结点都可以排出一个拓扑序列。

2、拓扑排序的方法 下面给出拓扑排序的方法 的结点且输出之; ⑴从图中选择一个入度为 0 的结点且输出之; ⑵从图中删除该结点及其所有出边(即与之相邻的所有结点的入度减一); 从图中删除该结点及其所有出边(即与之相邻的所有结点的入度减一); 反复执行这两个步骤,直至所有结点都输出了,也就是整个拓扑排序完成了。 反复执行这两个步骤,直至所有结点都输出了,也就是整个拓扑排序完成了。或者直至剩 的结点,这就说明此图中有环,拓扑排序不能再进行下去了。 图中再没有入度为 0 的结点,这就说明此图中有环,拓扑排序不能再进行下去了。 对于士兵排队问题, 对于士兵排队问题,我们首先构造一张有向图 G: var array[ A’ Z’ ’ ’ Z’ of 0‥1; ‘ ‥’ , A ‥’ ] 0‥ g: 的相邻矩阵} 的相邻矩阵} integer; d:array[‘A’‥’Z’] of integer; array[‘ ’‥’Z 点的度数序列} 点的度数序列} set s: of ‘A’ Z’ ‥’ ; 兵名集合} 兵名集合} {图

{结

{士

图中的结点为士兵。 a>b, g[a,b]← 引入一条有向边); );计算结点 图中的结点为士兵。若 a>b,则 g[a,b]←1 (即 a 向 b 引入一条有向边);计算结点 b 的 入度( 高的人数)d(b)←d(b)+1。 入度(即比士兵 b 高的人数)d(b)←d(b)+1。显然最高士兵对应的结点入度为 0: s←[]; []; 合初始化} 合初始化} while begin 信息; 读 a>b 信息; (a∈ ’‥’Z (b∈ ’‥’Z if (a∈{‘A’‥’Z’})and (b∈{‘A’‥’Z’}) then begin s←s+[a,b]; s+[a,b]; 兵名集合} 兵名集合} g[a,b]← g[a,b]←1; ( a, b) } d[b]←d[b]+1; d[b]←d[b]+1; 的入度} 的入度} end; end;{then} end; end;{while} {累计结点 b {构造有向边 {计算士 文件未输入完 do {士兵名集

然后通过下述方法计算士兵名字符集 然后通过下述方法计算士兵名字符集 m 和士兵人数 k m←’’; ←’’; a=’ for a=’A’ to ‘Z’ do m←m+a; if a s then m←m+a; k←length(m); length(m);

接下来对有向图G作拓扑排序。 中有回路,则排队方案不存在; 接下来对有向图G作拓扑排序。若图 G 中有回路,则排队方案不存在;否则拓扑序列 n 即为一个排队方案。拓扑排序的过程如下: 即为一个排队方案。拓扑排序的过程如下:

n←’’; ←’’; 初始化为空} 初始化为空} i: for i:=1 to k do 个出列士兵} 个出列士兵} begin j← 1; (d[m[j]]>0)and(j≤ j←j+1; while (d[m[j]]>0)and(j≤k)do j←j+1; 的结点序号 j} if j>k then 无解退出} 无解退出} then begin 输出失败信息;halt; 输出失败信息;halt; end; end;{then} n←n+m[j] 扑序列 n} ←∞; a←m[j]; d[a]←∞; m[j]; d[a]←∞ j: for j:=1 to k do 去结点 j} [a, d[m[j]]←d[m[j]]if g [a,m[j]]>0 then d[m[j]]←d[m[j]]-1; end; end;{for} 输出拓扑序列 n; 二、计算关键路径 1、AOV网 、AOV网

{拓扑序列 n

{依次搜索每一 {依次搜索每一

{搜索第 i 个入度为 0

{若入度为 的结点不存在,则队列不存在最高的士兵, {若入度为 0 的结点不存在,则队列不存在最高的士兵,

{入度为 {入度为 0 的结点 j 进入拓

{删

如果有向图的结点表示活动,有向边表示活动间的优先关系, 如果有向图的结点表示活动,有向边表示活动间的优先关系,那么我们通过拓扑排序 将图中的结点排成一个满足活动先后顺序要求的线性序列。但在实际生活中, 将图中的结点排成一个满足活动先后顺序要求的线性序列。但在实际生活中,往往会抽象 出另一种类型的有向图:有向图的结点表示事件,有向边表示活动, 出另一种类型的有向图:有向图的结点表示事件,有向边表示活动,边上的权标明一项活 动需要的时间。结点所表示的事件实际上就是它入边代表的活动均已完成, 动需要的时间。结点所表示的事件实际上就是它入边代表的活动均已完成,出边代表的活 动可以开始这样一种状态。 动可以开始这样一种状态。例如

项活动、 个事件。 a1、a2、 并行实施; 上图含 11 项活动、9 个事件。其中事件 v1 表示开始时活动 a1、a2、a3 并行实施;事 a4、 已经完成, a7、 可以开始。 表示整个计划完成。 件 v5 代表活动 a4、a5 已经完成,活动 a7、a8 可以开始。V9 表示整个计划完成。活动依事 件的顺序要求进行。 a4、a5、 v2、v3、 分别发生后才能进行, 件的顺序要求进行。例如活动 a4、a5、a6 只有当事件 v2、v3、v4 分别发生后才能进行, v5、 的发生。 a10、 完成后,整个计划完成。 而它们的完成又标志事件 v5、v6 的发生。当活动 a10、a11 完成后,整个计划完成。上述 有向图应该是无环的, 的开始结点 v1) 有向图应该是无环的,且存在唯一的入度为 0 的开始结点(上图中的 v1)和唯一的出度为 的完成结点( v9)。 )。这样的有向图称作 活动结点网络)。 )。利用 0 的完成结点(上图中的 v9)。这样的有向图称作 AOV 网(活动结点网络)。利用 AOV 网 可以估算出整个计算完成至少需要多少时间, 可以估算出整个计算完成至少需要多少时间,为提前完成计划应该加快哪些活动的速度等 问题。解决这些问题有一种有效的方法——求关键路径方法。 ——求关键路径方法 问题。解决这些问题有一种有效的方法——求关键路径方法。

2、计算关键路径 网中的活动可以并行进行, 由于 AOV 网中的活动可以并行进行,因此完成整个计划的最少时间是从开始结点到完 (图 4 成结点的最长路径长度 路径上各边权的和) 具有最大长度的路径称作关键路径。 图 4. (路径上各边权的和) 具有最大长度的路径称作关键路径。 。 ( v1→v2→v5→v8→ 是一条关键路径, 18。换句话说 —3)中 v1→v2→v5→v8→v9 是一条关键路径,长度为 18。换句话说,整个计划至少需要 个时间单位完成。关键路径上的活动又称关键活动。 18 个时间单位完成。关键路径上的活动又称关键活动。如果不能按期完成这些活动会贻误 整个计划。找出关键活动后就可以适当调度,集中力量于关键活动, 整个计划。找出关键活动后就可以适当调度,集中力量于关键活动,以保证计划如期或提 前完成。为找出关键活动,我们先定义几个变量: 前完成。为找出关键活动,我们先定义几个变量: 网的结点数; 网的有向边数; n—AOV 网的结点数; m—AOV 网的有向边数; ee[i]— 事件可能发生的最早时间, 的最长路径长度; ee[i]—vi 事件可能发生的最早时间,即从开始结点 v1 至结点 vi 的最长路径长度; le[i]— ee[n]时刻发生的前提下 时刻发生的前提下, le[i]—在保证完成结点 vn 所代表的事件在 ee[n]时刻发生的前提下,事件 vi 允许发 le[i]=ee(n)最长路径长度; 生的最晚时 间,即 le[i]=ee(n)-vi 至 vn 最长路径长度; e[k]— ak(对应边<vi vj>)可能的最早开始时间, <vi, e[k]—活动 ak(对应边<vi,vj>)可能的最早开始时间,即等于事件 vi 的可能的最早 ee[i]; 发生时间 ee[i]; l[k]— ak(对应边<vi,vj>)允许的最晚完成时间 对应边<vi 允许的最晚完成时间, l[k]—活动 ak(对应边<vi,vj>)允许的最晚完成时间,即等于事件 vj 允许最晚发生时间 le[j]; le[j]; (1≤ (1≤i, j≤n, 1≤k≤m)] l[k]-e[k]。 wk(即 显然活动 ak 的最大可利用时间是 l[k]-e[k]。若最大可利用时间等于 ak 边所带的权 wk(即 为计划时间) 是关键活动。 延期,则整个计划将顺延。 wk, 为计划时间),则 ak 是关键活动。Ak 延期,则整个计划将顺延。若最大可利用时间大于 wk, 不是关键活动 关键活动, wk。只要不超过最大可利用时间, 则 ak 不是关键活动,ak 的完成时间允许超过 wk。只要不超过最大可利用时间,无妨于整 个计划完成的进度。我们可以采取以下步骤,计算上面定义的几个变量值, 个计划完成的进度。我们可以采取以下步骤,计算上面定义的几个变量值,从而找到关键 活动: 活动: ee[1]=0, ⑴首先令 ee[1]=0,然后向前递推 ee[j] ee[j]=max{ee[i]+wij} 2≤ 2≤ j≤ n, (i,j)∈ (i,j)∈以 j 为头的弧集

显然,ee[j]的计算必须在 的所有前趋结点的最早发生时间都已求得前提下进行; 显然,ee[j]的计算必须在 vj 的所有前趋结点的最早发生时间都已求得前提下进行; le[n]=ee[n]起向后倒推 ⑵从 le[n]=ee[n]起向后倒推 le[i] le[i]=min{le[j]le[i]=min{le[j]-wij} e[j] i=ni=n-1‥1, (i,j)∈ (i,j)∈以 i 为尾的弧集

显然,le[i]的计算必须在 显然,le[i]的计算必须在 vi 的所有后继结点的最晚发生时间都已求得的前提下进 行。 v1‥ 必须是拓扑序列。 由⑴、⑵可以看出结点序列 v1‥vn 必须是拓扑序列。 ak=<vi,vj>(1≤ m), e[k]和 ⑶对于每一条边 ak=<vi,vj>(1≤k≤m),求 e[k]和 l[k] e[k]←ee[i], l[k]← e[k]←ee[i], l[k]←le[j] l[k]-e[k]=wij, 为关键活动。 若 l[k]-e[k]=wij,则 ak 为关键活动。

网用邻接表存储。算法中使用的变量定义如下 义如下: AOV 网用邻接表存储。算法中使用的变量定义如下: Type pointer=↑edge; pointer=↑edge; 指针类型} 指针类型} edge=record 点类型} 点类型} no: no:1‥n 点序号} 点序号} w:real; real; 边的权} 边的权} link:pointer; link:pointer; 一条边} 一条边} end; end; node=record 表类型 表类型} info:datatype; info:datatype; 件信息} 件信息} {事 {结点 {结点 {后继指针,指向下 后继指针, {该 {该边另一端 {该边另一端 {边表的结 {边表的结 {边表的

out:pointer; out:pointer; 首指针} 首指针} end; end; Var

{边表

nodelist:array[1‥ node; 网的邻接表。结点表中的结点为拓扑 nodelist:array[1‥n] of node; {AOV 网的邻接表。结点表中的结点为拓扑 序列, nodelist[i]. 个结点在原图中的序号} 序列,其中 nodelist[i].info 存储序列中的第 i 个结点在原图中的序号} ee,le:array[1‥ real; ee,le:array[1‥n] of real;{事件最早发生的时间序列和事件最晚发生的时 间序列} 间序列} real; e,l:array[1‥m] of real;{活动最早发生的时间序列和活动最晚完成的时 array[1‥ 间序列} 间序列}

算法如下: 算法如下: 网进行拓扑排序, 对 AOV 网进行拓扑排序,各结点及其关联的边按拓扑序列的顺序存入邻接表 nodelist; nodelist; i: ee[i]← for i:=1 to n do ee[i]←0; 初始化} 初始化} i: nfor i:=1 to n-1 do 间表 ee} begin p←nodelist[i].out; nodelist[i].out; while p<>nil do begin j←p↑.no; no; ee[j]<ee[i]+p↑ ee[j]←ee[i]+p↑ if ee[j]<ee[i]+p↑.w then ee[j]←ee[i]+p↑.w; p←p↑.link; link; end; end;{while} end; end;{for} {所有事件的最早发生时间

{计算各个事件的最早发生时 {计算各个事件的最早发生时

i: le[i]←ee[n]; for i:=1 to n do le[i]←ee[n]; 初始化} 初始化} i:=nfor i:=n-1 downto 1 do 间表 le} begin p←nodelist[i].out; nodelist[i].out; while p<>nil do begin j←p↑.no; no;

{所有事件的最晚发生时间

{计算各个事件的最晚发生时 {计算各个事件的最晚发生时

le[i]>le[j]le[i]←le[j]if le[i]>le[j]-p↑.w then le[i]←le[j]-p↑.w; p←p↑.link; link; end; end;{while} end; end;{for} k← 0; 初始化} 初始化} i: nfor i:=1 to n-1 do begin p←nodelist[i].out; nodelist[i].out; while p<>nil do {计算事件 i 发生后开始的各项活动的最早开始时间和最晚完成 时间} 时间} begin j←p↑.no;k←k+1; no; k+1; e[k]←ee[i]; l[k]←le[j]; e[k]←ee[i]; l[k]←le[j]; l[k]-e[k]=p↑ 输出关键活动为<vi vj>, <vi, if l[k]-e[k]=p↑.w then 输出关键活动为<vi,vj>,其花费的时间为 p↑.w; p←p↑.link; link; {开始计算关键活动。活动序号 开始计算关键活动。

end; end;{while} end; end;{for}

找出关键活动后, 网中去掉, 找出关键活动后,只要将所有的非关键活动从 AOV 网中去掉,这时从开始结点至完成 结点的所有路径都是关键路径。 网中的关键路径可能不止一条。 结点的所有路径都是关键路径。AOV 网中的关键路径可能不止一条。并不是加快任一关键活 动就可以缩短整个计划的完成时间。 动就可以缩短整个计划的完成时间。只有加快那些包括在所有关键路径上的关键活动才能 达到目的的。例如( v1→v2→v5→ 达到目的的。例如(图 4.4—3)所示 AOV 网中的关键路径为 v1→v2→v5→v8→v9 和 v1 v2→v5→v7→v9。 的速度, →v2→v5→v7→v9。如果仅加快事件 v8 和 v9 之间的关键活动 a11 的速度,是不能缩短计 划完成时间的,因为第一条路径不包括活动 a11。 a1, 划完成时间的,因为第一条路径不包括活动 a11。如果加快 v1 和 v2 之间的关键活动 a1, 而导致整个计划提前完成。 则由于两条关键路径都包含关键活动 a1 而导致整个计划提前完成。