当前位置:首页 >> 工学 >>

数据结构-清华大学严蔚敏PPT


算法与数据结构
教材:《数据结构(C语言版)》。严蔚敏,吴伟民 编
著。清华大学出版社。

参考文献:
1 《数据结构》 。张选平,雷咏梅 编, 严蔚敏 审。 机械工业出版社。 2 《数据结构与算法分析》。Clifford A. Shaffer著, 张 铭,刘晓丹 译。电子工业出版社。 3 《数据结构习题与解析(C语实言版)》。李春葆。 清华大学出版社。 4 《数据结构与算法》。夏克俭 编著。国防工业出 版社。

第1章

绪 论

目前,计算机已深入到社会生活的各个领域,其应 用已不再仅仅局限于科学计算,而更多的是用于控制, 管理及数据处理等非数值计算领域。计算机是一门研究 用计算机进行信息表示和处理的科学。这里面涉及到两 个问题:信息的表示,信息的处理。

信息的表示和组织又直接关系到处理信息的程序的 效率。随着应用问题的不断复杂,导致信息量剧增与信 息范围的拓宽,使许多系统程序和应用程序的规模很大, 结构又相当复杂。因此,必须分析待处理问题中的对象 的特征及各对象之间存在的关系,这就是数据结构这门 课所要研究的问题。

计算机求解问题的一般步骤
编写解决实际问题的程序的一般过程:
– 如何用数据形式描述问题?—即由问题抽象出一个

适当的数学模型; – 问题所涉及的数据量大小及数据之间的关系; – 如何在计算机中存储数据及体现数据之间的关系?

– 处理问题时需要对数据作何种运算?
– 所编写的程序的性能是否良好? 上面所列举的问题基本上由数据结构这门课程来回答。

1.1 数据结构及其概念
《算法与数据结构》是计算机科学中的一门综合性

专业基础课。是介于数学、计算机硬件、计算机软件三 者之间的一门核心课程,不仅是一般程序设计的基础, 而且是设计和实现编译程序、操作系统、数据库系统及 其他系统程序和大型应用程序的重要基础。

1.1.1 数据结构的例子
例1:电话号码查询系统
设有一个电话号码薄,它记录了N个人的名字和其 相应的电话号码,假定按如下形式安排:(a1, b1),(a2, b2),…(an, bn),其中ai, bi(i=1,2…n) 分别表示某人的 名字和电话号码。 本问题是一种典型的表格问题。如 表1-1,数据与数据成简单的一对一的线性关系。
姓名 陈海 李四锋 电话号码 13612345588 13056112345

。。。

。。。

表1-1 线性表结构

例2:磁盘目录文件系统
磁盘根目录下有很多子目录 及文件,每个子目录里又可以包 含多个子目录及文件,但每个子 目录只有一个父目录,依此类推: 本问题是一种典型的树型结 构问题,如图1-1 ,数据与数据 成一对多的关系,是一种典型的 非线性关系结构—树形结构。

图1-1

树形结构

例3:交通网络图
从一个地方到另外一个地方可以有多条路径。本问 题是一种典型的网状结构问题,数据与数据成多对多的 关系,是一种非线性关系结构。
广州 佛山 惠州

东莞
中山 深圳

珠海
图1-2 网状结构

1.1.2 基本概念和术语
数据(Data) :是客观事物的符号表示。在计算机科 学中指的是所有能输入到计算机中并被计算机程序处理 的符号的总称。 数据元素(Data Element) :是数据的基本单位,在 程序中通常作为一个整体来进行考虑和处理。
一个数据元素可由若干个数据项(Data Item)组成。 数据项是数据的不可分割的最小单位。数据项是对客观 事物某一方面特性的数据描述。

数据对象(Data Object):是性质相同的数据元素的 集合,是数据的一个子集。如字符集合 C={‘A’,’B’,’C,…} 。

数据结构(Data Structure):是指相互之间具有(存在 )一定联系(关系)的数据元素的集合。元素之间的相互联 系(关系)称为逻辑结构。数据元素之间的逻辑结构有四 种基本类型,如图1-3所示。

① 集合:结构中的数据元素除了“同属于一个集合” 外,没有其它关系。 ② 线性结构:结构中的数据元素之间存在一对一的 关系。 ③ 树型结构:结构中的数据元素之间存在一对多的 关系。

④ 图状结构或网状结构:结构中的数据元素之间存 在多对多的关系。

图1-3

四类基本结构图

1.1.3 数据结构的形式定义
数据结构的形式定义是一个二元组: Data-Structure=(D,S) 其中:D是数据元素的有限集,S是D上关系的有限集。 例2:设数据逻辑结构B=(K,R)
K={k1, k2, …, k9}
R={ <k1, k3>,<k1, k8>,<k2, k3>,<k2, k4>,<k2, k5>,<k3, k9>,<k5, k6>,<k8, k9>,<k9, k7>,<k4, k7>,<k4, k6> }

画出这逻辑结构的图示,并确定那些是起点,那些是终点

数据元素之间的关系可以是元素之间代表某种含义 的自然关系,也可以是为处理问题方便而人为定义的 关系,这种自然或人为定义的 “关系”称为数据元素 之间的逻辑关系,相应的结构称为逻辑结构。

1.1.4 数据结构的存储方式
数据结构在计算机内存中的存储包括数据元素的 存储和元素之间的关系的表示。

元素之间的关系在计算机中有两种不同的表示方法: 顺序表示和非顺序表示。由此得出两种不同的存储结构: 顺序存储结构和链式存储结构。 – 顺序存储结构:用数据元素在存储器中的相对位 置来表示数据元素之间的逻辑结构(关系)。

– 链式存储结构:在每一个数据元素中增加一个存 放另一个元素地址的指针(pointer ),用该指针来表 示数据元素之间的逻辑结构(关系)。

例:设有数据集合A={3.0,2.3,5.0,-8.5,11.0} ,两种
不同的存储结构。 – 顺序结构:数据元素存放的地址是连续的; – 链式结构:数据元素存放的地址是否连续没有要 求。
数据的逻辑结构和物理结构是密不可分的两个方面, 一个算法的设计取决于所选定的逻辑结构,而算法的实 现依赖于所采用的存储结构。 在C语言中,用一维数组表示顺序存储结构;用结 构体类型表示链式存储结构。

数据结构的三个组成部分: 逻辑结构: 数据元素之间逻辑关系的描述
D_S=(D,S)

存储结构: 数据元素在计算机中的存储及其逻辑
关系的表现称为数据的存储结构或物理结构。

数据操作: 对数据要进行的运算。
本课程中将要讨论的三种逻辑结构及其采用的存储 结构如图1-4所示。

逻辑结构
线性表

物理结构
顺序存储结构 链式存储结构 复合存储结构
逻辑结构与所采用的存储结构



图1-4

数据的逻辑结构 线性结构 受限线性表 一般线性表 线性表推广 数组 集合 广义表 非线性结构 树形结构 一般树 二叉树 图状结构 有向图 无向图

栈和队列 串

图1-5

数据逻辑结构层次关系图

1.1.5 数据类型
数据类型(Data Type):指的是一个值的集合和定 义在该值集上的一组操作的总称。 数据类型是和数据结构密切相关的一个概念。 在C 语言中数据类型有:基本类型和构造类型。 数据结构不同于数据类型,也不同于数据对象,它 不仅要描述数据类型的数据对象,而且要描述数据对象 各元素之间的相互关系。

1.1.6 数据结构的运算
数据结构的主要运算包括: ⑴ 建立(Create)一个数据结构; ⑵ 消除(Destroy)一个数据结构; ⑶ 从一个数据结构中删除(Delete)一个数据元素; ⑷ 把一个数据元素插入(Insert)到一个数据结构中; ⑸ 对一个数据结构进行访问(Access); ⑹ 对一个数据结构(中的数据元素)进行修改 (Modify); ⑺ 对一个数据结构进行排序(Sort); ⑻ 对一个数据结构进行查找(Search)。

1.2 抽象数据类型
抽象数据类型(Abstract Data Type ,简称ADT): 是指一个数学模型以及定义在该模型上的一组操作。 ADT的定义仅是一组逻辑特性描述, 与其在计算 机内的表示和实现无关。因此,不论ADT的内部结构如 何变化,只要其数学特性不变,都不影响其外部使用。 ADT的形式化定义是三元组:ADT=(D,S,P) 其中:D是数据对象,S是D上的关系集,P是对D的基 本操作集。

ADT的一般定义形式是:
ADT <抽象数据类型名>{

数据对象: <数据对象的定义>
数据关系: <数据关系的定义> 基本操作: <基本操作的定义> } ADT <抽象数据类型名> – 其中数据对象和数据关系的定义用伪码描述。

– 基本操作的定义是:
<基本操作名>(<参数表>) 初始条件: <初始条件描述>

操作结果: <操作结果描述>

– 初始条件:描述操作执行之前数据结构和参数应

满足的条件;若不满足,则操作失败,返回相应的出 错信息。 – 操作结果:描述操作正常完成之后,数据结构的 变化状况和 应返回的结果。

1.3 算法分析初步
1.3.1 算法
算法(Algorithm):是对特定问题求解方法(步骤)的一种 描述,是指令的有限序列,其中每一条指令表示一个或 多个操作。 算法具有以下五个特性 ① 有穷性: 一个算法必须总是在执行有穷步之后结 束,且每一步都在有穷时间内完成。 ② 确定性:算法中每一条指令必须有确切的含义。 不存在二义性。且算法只有一个入口和一个出口。 ③ 可行性: 一个算法是能行的。即算法描述的操作 都可以通过已经实现的基本运算执行有限次来实现。

④ 输入: 一个算法有零个或多个输入,这些输入 取自于某个特定的对象集合。
⑤ 输出: 一个算法有一个或多个输出,这些输出 是同输入有着某些特定关系的量。 一个算法可以用多种方法描述,主要有:使用自然 语言描述;使用形式语言描述;使用计算机程序设计语 言描述。 算法和程序是两个不同的概念。一个计算机程序是 对一个算法使用某种程序设计语言的具体实现。算法必 须可终止意味着不是所有的计算机程序都是算法。 在本门课程的学习、作业练习、上机实践等环节, 算法都用C语言来描述。在上机实践时,为了检查算法 是否正确,应编写成完整的C语言程序。

1.3.2 算法设计的要求
评价一个好的算法有以下几个标准
① 正确性(Correctness ): 算法应满足具体问题 的需求。 ② 可读性(Readability): 算法应容易供人阅读和 交流。可读性好的算法有助于对算法的理解和修改。

③ 健壮性(Robustness): 算法应具有容错处理。 当输入非法或错误数据时,算法应能适当地作出反 应或进行处理,而不会产生莫名其妙的输出结果。
④ 通用性(Generality): 算法应具有一般性 ,即 算法的处理结果对于一般的数据集合都成立。

⑤ 效率与存储量需求: 效率指的是算法执行的时 间;存储量需求指算法执行过程中所需要的最大存 储空间。一般地,这两者与问题的规模有关。

1.3.3 算法效率的度量
算法执行时间需通过依据该算法编制的程序在计算 机上运行所消耗的时间来度量。其方法通常有两种: 事后统计:计算机内部进行执行时间和实际占用空间的 统计。

问题:必须先运行依据算法编制的程序;依赖软硬 件环境,容易掩盖算法本身的优劣;没有实际价值。
事前分析:求出该算法的一个时间界限函数。

与此相关的因素有:

– 依据算法选用何种策略;
– 问题的规模; – 程序设计的语言; – 编译程序所产生的机器代码的质量; – 机器执行指令的速度;

撇开软硬件等有关部门因素,可以认为一个特定算 法“运行工作量”的大小,只依赖于问题的规模(通 常用n表示),或者说,它是问题规模的函数。

算法分析应用举例
算法中基本操作重复执行的次数是问题规模n的某 个函数,其时间量度记作 T(n)=O(f(n)),称作算法的 渐近时间复杂度(Asymptotic Time complexity),简 称时间复杂度。 一般地,常用最深层循环内的语句中的原操作的执 行频度(重复执行的次数)来表示。

“O”的定义: 若f(n)是正整数n的一个函数,则 O(f(n)) 表示? M≥0 ,使得当n ≥ n0时,| f(n) | ≤ M | f(n0) | 。
表示时间复杂度的阶有: O(1) :常量时间阶 O (n):线性时间阶 O(㏒n) :对数时间阶 O(n㏒n) :线性对数时间阶

O (nk): k≥2 ,k次方时间阶 例1 两个n阶方阵的乘法

for(i=1,i<=n; ++i)
for(j=1; j<=n; ++j)

{ c[i][j]=0 ;
for(k=1; k<=n; ++k) c[i][j]+=a[i][k]*b[k][j] ; } 由于是一个三重循环,每个循环从1到n,则总次数为: n×n×n=n3 时间复杂度为T(n)=O(n3)

例2 {++x; s=0 ;}
将x自增看成是基本操作,则语句频度为1,即时 间复杂度为O(1) 。

如果将s=0也看成是基本操作,则语句频度为2,其时 间复杂度仍为O(1),即常量阶。

例3 for(i=1; i<=n; ++i)
{ ++x; s+=x ; } 语句频度为:2n,其时间复杂度为:O(n) ,即为线性 阶。 例4 for(i=1; i<=n; ++i)

for(j=1; j<=n; ++j)
{ ++x; s+=x ; } 语句频度为:2n2 ,其时间复杂度为:O(n2) ,即为 平方阶。

定理:若A(n)=a m n m +a m-1 n m-1 +…+a1n+a0是一个

m次多项式,则A(n)=O(n m) 例5 for(i=2;i<=n;++i) for(j=2;j<=i-1;++j) {++x; a[i,j]=x; } 语句频度为: 1+2+3+…+n-2=(1+n-2) ×(n-2)/2 =(n-1)(n-2)/2 =n2-3n+2 ∴时间复杂度为O(n2),即此算法的时间复杂度为平方 阶。 – 一个算法时间为O(1)的算法,它的基本运算执行 的次数是固定的。因此,总的时间由一个常数(即 零次多项式)来限界。而一个时间为O(n2)的算法则 由一个二次多项式来限界。

以下六种计算算法时间的多项式是最常用的。其 关系为:

O(1)<O(㏒n)<O(n)<O(n㏒n)<O(n2)<O(n3)
– 指数时间的关系为: O(2n)<O(n!)<O(nn) 当n取得很大时,指数时间算法和多项式时间算法 在所需时间上非常悬殊。因此,只要有人能将现有指 数时间算法中的任何一个算法化简为多项式时间算法, 那就取得了一个伟大的成就。 – 有的情况下,算法中基本操作重复执行的次数还 随问题的输入数据集不同而不同。

例1:素数的判断算法。
Void prime( int n)
/* n是一个正整数 */

{ int i=2 ; while ( (n% i)!=0 && i*1.0< sqrt(n) ) i++ ; if (i*1.0>sqrt(n) ) printf(“&d 是一个素数\n” , n) ; else printf(“&d 不是一个素数\n” , n) ; } 嵌套的最深层语句是i++;其频度由条件( (n% i)!=0 && i*1.0< sqrt(n) ) 决定,显然i*1.0< sqrt(n) , 时间复杂度O(n1/2)。

例2:冒泡排序法。
Void bubble_sort(int a[],int n) { change=false; for (i=n-1; change=TURE; i>1 && change; --i) for (j=0; j<i; ++j) if (a[j]>a[j+1]) { a[j] ←→a[j+1] ; change=TURE ; } } – 最好情况:0次 – 最坏情况:1+2+3+?+n-1=n(n-1)/2 – 平均时间复杂度为: O(n2)

1.3.4 算法的空间分析
空间复杂度(Space complexity) :是指算法编写 成程序后,在计算机中运行时所需存储空间大小的度 量。记作: S(n)=O(f(n)) 其中: n为问题的规模(或大小) 该存储空间一般包括三个方面: – 指令常数变量所占用的存储空间; – 输入数据所占用的存储空间; – 辅助(存储)空间。 一般地,算法的空间复杂度指的是辅助空间。 – 一维数组a[n]: 空间复杂度 O(n) – 二维数组a[n][m]: 空间复杂度 O(n*m)

习题一
1 简要回答术语:数据,数据元素,数据结构,数据 类型。 2 数据的逻辑结构?数据的物理结构?逻辑结构与物 理结构的区别和联系是什么? 3 数据结构的主要运算包括哪些? 4 算法分析的目的是什么?算法分析的主要方面是什 么? 5 分析以下程序段的时间复杂度,请说明分析的理由 或原因。


Sum1( int n ) { int p=1, sum=0, m ; for (m=1; m<=n; m++) { p*=m ; sum+=p ; } return (sum) ; }

⑶ 递归函数
fact( int n ) { if (n<=1) return(1) ; else return( n*fact(n-1)) ; }


Sum2( int n ) { int sum=0, m, t ; for (m=1; m<=n; m++) { p=1 ; for (t=1; t<=m; t++) p*=t ; sum+=p ; } return (sum) ; }

第2章

线性表

线性结构是最常用、最简单的一种数据结构。而线 性表是一种典型的线性结构。其基本特点是线性表中的 数据元素是有序且是有限的。在这种结构中: ① 存在一个唯一的被称为“第一个”的数据元素; ③ 除第一个元素外,每个元素均有唯一一个直接前 驱;
④ 除最后一个元素外,每个元素均有唯一一个直接 后继。

② 存在一个唯一的被称为“最后一个”的数据元素;

2.1 线性表的逻辑结构
2.1.1 线性表的定义
线性表(Linear List) :是由n(n≧0)个数据元素(结 点)a1,a2, …an组成的有限序列。该序列中的所有结 点具有相同的数据类型。其中数据元素的个数n称为线 性表的长度。

当n=0时,称为空表。
当n>0时,将非空的线性表记作: (a1,a2,…an) a1称为线性表的第一个(首)结点,an称为线性表的最后 一个(尾)结点。

a1,a2,…ai-1都是ai(2≦i≦n)的前驱,其中ai-1是ai的直 接前驱;
ai+1,ai+2,…an都是ai(1≦i ≦n-1)的后继,其中ai+1是ai 的直接后继。

2.1.2 线性表的逻辑结构
线性表中的数据元素ai所代表的具体含义随具体应 用的不同而不同,在线性表的定义中,只不过是一个抽 象的表示符号。

◆ 线性表中的结点可以是单值元素(每个元素只有一 个数据项) 。
例1: 26个英文字母组成的字母表: (A,B,C、…、Z)

例2 : 某校从1978年到1983年各种型号的计算机拥 有量的变化情况:(6,17,28,50,92,188)
例3 : 一副扑克的点数 A) (2,3,4,…,J,Q,K,

◆ 线性表中的结点可以是记录型元素,每个元素 含有多个数据项 ,每个项称为结点的一个域 。每个 元素有一个可以唯一标识每个结点的数据项组,称 为关键字。

例4 : 某校2001级同学的基本情况: {(‘2001414101’,‘张里户’,‘男’, 06/24/1983), (‘2001414102’,‘张化司’, ‘男’,08/12/1984) …, (‘2001414102’, ‘李利辣’,‘女’,08/12/1984) }

◆ 线性表是一种相当灵活的数据结构,其长度可根

据需要增长或缩短。
◆ 对线性表的数据元素可以访问、插入和删除。

2.1.3 线性表的抽象数据类型定义
ADT List{
数据对象:D = { ai | ai∈ElemSet, i=1,2,…,n, n≧0 } 数据关系:R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n } 基本操作: InitList( &L )

操作结果:构造一个空的线性表L;

ListLength( L ) 初始条件:线性表L已存在; 操作结果:若L为空表,则返回TRUE,否则返回 FALSE; …. GetElem( L, i, &e ) 初始条件:线性表L已存在,1≦i≦ListLength(L); 操作结果:用e返回L中第i个数据元素的值; ListInsert ( L, i, &e ) 初始条件:线性表L已存在,1≦i≦ListLength(L) ; 操作结果:在线性表L中的第i个位置插入元素e; … } ADT List

2.2 线性表的顺序存储
2.2.1 线性表的顺序存储结构
顺序存储 :把线性表的结点按逻辑顺序依次存放 在一组地址连续的存储单元里。用这种方法存储的线性 表简称顺序表。

顺序存储的线性表的特点:
◆ 线性表的逻辑顺序与物理顺序一致;
◆ 数据元素之间的关系是以元素在计算机内“物理

位置相邻”来体现。 设有非空的线性表:(a1,a2,…an) 。顺序存储如图 2-1所示。

Loc(a1) Loc(ai)+(i-1)* l

… a1 a2 … ai … an …
图2-1 线性表的顺序存储表示

在具体的机器环境下:设线性表的每个元素需占 用l个存储单元,以所占的第一个单元的存储地址作为 数据元素的存储位置。则线性表中第i+1个数据元素的 存储位置LOC(ai+1)和第i个数据元素的存储位置 LOC(ai)之间满足下列关系: LOC(ai+1)=LOC(ai)+l

线性表的第i个数据元素ai的存储位置为:
LOC(ai)=LOC(a1)+(i-1)*l

在高级语言(如C语言)环境下:数组具有随机存取 的特性,因此,借助数组来描述顺序表。除了用数组来 存储线性表的元素之外,顺序表还应该有表示线性表的 长度属性,所以用结构类型来定义顺序表类型。 #define OK 1 #define ERROR -1 #define MAX_SIZE 100 typedef int Status ; typedef int ElemType ; typedef struct sqlist { ElemType Elem_array[MAX_SIZE] ; int length ; } SqList ;

2.2.2 顺序表的基本操作
顺序存储结构中,很容易实现线性表的一些操作: 初始化、赋值、查找、修改、插入、删除、求长度等。
以下将对几种主要的操作进行讨论。

1

顺序线性表初始化
{ L->elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L -> elem_array ) return ERROR ;
else { L->length= 0 ; return OK ; }

Status Init_SqList( SqList *L )

2

顺序线性表的插入

在线性表 L= (a1,…a i-1,ai, ai+1,…,an) 中的第i(1≦i≦n)个位置上插入一个新结点e,使其成为 线性表: L=(a1,…a
i-1,e,ai,ai+1,…,an)

实现步骤
(1) 将线性表L中的第i个至第n个结点后移一个位置。

(2) 将结点e插入到结点ai-1之后。
(3) 线性表长度加1。

算法描述
Status Insert_SqList(Sqlist *L,int i , ElemType e) { int j ; if ( i<0||i>L->length-1) return ERROR ; if (L->length>=MAX_SIZE) { printf(“线性表溢出!\n”); return ERROR ; } for ( j=L->length–1; j>=i-1; --j ) L->Elem_array[j+1]=L>Elem_array[j];
/* i-1位置以后的所有结点后移 */

L->Elem_array[i-1]=e;

/* 在i-1位置插入

时间复杂度分析
在线性表L中的第i个元素之前插入新结点,其时 间主要耗费在表中结点的移动操作上,因此,可用结点 的移动来估计算法的时间复杂度。 设在线性表L中的第i个元素之前插入结点的概率 为Pi,不失一般性,设各个位置插入是等概率,则 Pi=1/(n+1),而插入时移动结点的次数为n-i+1。 总的平均移动次数: Einsert=∑pi*(n-i+1) (1≦i≦n) ∴ Einsert=n/2 。 即在顺序表上做插入运算,平均要移动表上一半结 点。当表长n较大时,算法的效率相当低。因此算法的 平均时间复杂度为O(n)。

3

顺序线性表的删除

在线性表 L=(a1,…a i-1,ai, ai+1,…,an) 中删除结点ai(1≦i≦n),使其成为线性表: L= (a1,…ai-1,ai+1,…,an)

实现步骤
(1) 将线性表L中的第i+1个至第n个结点依此向前 移动一个位置。

(2) 线性表长度减1。

算法描述
ElemType Delete_SqList(Sqlist *L,int i) { int k ; ElemType x ;

if (L->length==0) { printf(“线性表L为空!\n”); return ERROR; } else if ( i<1||i>L->length ) { printf(“要删除的数据元素不存在!\n”) ; return ERROR ; } else { x=L->Elem_array[i-1] ; /*保
存结点的值*/

for ( k=i ; k<L->length ; k++) L->Elem_array[k-1]=L>Elem_array[k];
/* i位置以后的所有结点前移 */

L->length--; return (x);

时间复杂度分析
删除线性表L中的第i个元素,其时间主要耗费在表 中结点的移动操作上,因此,可用结点的移动来估计算 法的时间复杂度。 设在线性表L中删除第i个元素的概率为Pi,不失 一般性,设删除各个位置是等概率,则Pi=1/n,而删除 时移动结点的次数为n-i。 则总的平均移动次数: Edelete=∑pi*(n-i) (1≦i≦n) ∴ Edelete=(n-1)/2 。 即在顺序表上做删除运算,平均要移动表上一半结 点。当表长n较大时,算法的效率相当低。因此算法的 平均时间复杂度为O(n)。

4

顺序线性表的查找定位删除

在线性表 L= (a1,a2,…,an) 中删除值为x的 第一个结点。

实现步骤
(1) 在线性表L查找值为x的第一个数据元素。 (2) 将从找到的位置至最后一个结点依次向前移动一 个位置。

(3) 线性表长度减1。

算法描述
Status Locate_Delete_SqList(Sqlist *L, ElemType x)
/* 删除线性表L中值为x的第一个结点 */

while (i<L->length)
个结点*/

/*查找值为x的第一

{

if (L->Elem_array[i]!=x ) i++ ; else { for ( k=i+1; k< L->length; k++) L->Elem_array[k-1]=L>Elem_array[k]; L->length--; break ; }

} if (i>L->length) { printf(“要删除的数据元素不存在!\n”) ;

时间复杂度分析
时间主要耗费在数据元素的比较和移动操作上。

首先,在线性表L中查找值为x的结点是否存在;
其次,若值为x的结点存在,且在线性表L中的位置为i , 则在线性表L中删除第i个元素。 设在线性表L删除数据元素概率为Pi,不失一般性, 设各个位置是等概率,则Pi=1/n。
◆ 比较的平均次数: Ecompare=∑pi*i

(1≦i≦n)

∴ Ecompare=(n+1)/2 。
◆ 删除时平均移动次数:Edelete=∑pi*(n-i) (1≦i≦n)

∴ Edelete=(n-1)/2 。 平均时间复杂度:Ecompare+Edelete=n , 即为O(n)

2.3 线性表的链式存储
2.3.1 线性表的链式存储结构
链式存储 :用一组任意的存储单元存储线性表
中的数据元素。用这种方法存储的线性表简称线性链 表。 存储链表中结点的一组任意的存储单元可以是连 续的,也可以是不连续的,甚至是零散分布在内存中 的任意位置上的。 链表中结点的逻辑顺序和物理顺序不一定相同。

为了正确表示结点间的逻辑关系,在存储每个结点 值的同时,还必须存储指示其直接后继结点的地址(或 位置),称为指针(pointer)或链(link),这两部分组 成了链表中的结点结构,如图2-2所示。 链表是通过每个结点的指针域将线性表的n个结点 按其逻辑次序链接在一起的。 每一个结只包含一个指针域的链表,称为单链表。 为操作方便,总是在链表的第一个结点之前附设一 个头结点(头指针)head指向第一个结点。头结点的数 据域可以不存储任何信息(或链表长度等信息)。
data next
data :数据域,存放结点的值。next :指针 域,存放结点的直接后继的地址。
图2-2 链表结点结构

单链表是由表头唯一确定,因此单 链表可以用头指针的名字来命名。 例1、线性表L=(bat,cat,eat,fat, hat)

……
1100

hat NULL

……
1300

其带头结点的单链表的逻辑状态和物理 存储方式如图2-3所示。
head

cat 1305 eat 3700 …… bat 1300

1305

3695
head bat
图2-3

cat

eat

fat

hat ?

3700

fat 1100 ……

带头结点的单链表的逻辑状态、物理存储方式

1 结点的描述与实现
C语言中用带指针的结构体类型来描述

typedef struct Lnode
{ ElemType data; }LNode;
/*数据域,保存结点的值 */ /*指针域*/

struct Lnode *next;
/*结点的类型 */

2 结点的实现
结点是通过动态分配和释放来的实现,即需要时分 配,不需要时释放。实现时是分别使用C语言提供的标 准函数:malloc() ,realloc(),sizeof() ,free() 。

动态分配 p=(LNode*)malloc(sizeof(LNode));
函数malloc分配了一个类型为LNode的结点变量的空 间,并将其首地址放入指针变量p中。 动态释放 free(p) ;

系统回收由指针变量p所指向的内存区。P必须是最近一 次调用malloc函数时的返回值。

3 最常用的基本操作及其示意图 ⑴ 结点的赋值
LNode *p; p=(LNode*)malloc(sizeof(LNode)); p->data=20; p->next=NULL ;

p 20 NULL



常见的指针操作


p

q …

p

① q=p ;

a … 操作前 p a b 操作前 p
a b 操作前 q a b c … …

a … 操作后 q p …

② q=p->next ;



a b 操作后 p a b 操作后 q a p b

③ p=p->next ; ④ q->next=p ; (a)









… p







… 操作前

c … 操作后

q

p b … x 操作前 p … x y



a



(b)


q
a b

y q



⑤ q->next=p->next ; q (a)
… p a b y x q 操作前 a q … a b b

操作后 …

… a b p … y x 操作后 p y






(b)

… x 操作前 p





x

y



操作后

2.3.2 单线性链式的基本操作
1 建立单链表
假设线性表中结点的数据类型是整型,以32767 作为结束标志。动态地建立单链表的常用方法有如下两 种:头插入法,尾插入法。

⑴ 头插入法建表
从一个空表开始,重复读入数据,生成新结点, 将读入数据存放到新结点的数据域中,然后将新结点插 入到当前链表的表头上,直到读入结束标志为止。即每 次插入的结点都作为链表的第一个结点。

算法描述
LNode *create_LinkList(void)
/* 头插入法创建单链表,链表的头结点head作为返回值 */

{

int data ; LNode *head, *p; head= (LNode *) malloc( sizeof(LNode)); head->next=NULL; /* 创建链表的表头结
点head */

while (1) { scanf(“%d”, &data) ; if (data==32767) break ; p= (LNode

p–>next=head–>next ; head– >next=p ;
/* 钩链,新创建的结点总是作为第一个结点

*/

} return (head); }

(2)

尾插入法建表

头插入法建立链表虽然算法简单,但生成的链表 中结点的次序和输入的顺序相反。若希望二者次序一致, 可采用尾插法建表。该方法是将新结点插入到当前链表 的表尾,使其成为当前链表的尾结点。

算法描述
LNode *create_LinkList(void)
/* 尾插入法创建单链表,链表的头结点head作为返回值

*/ {

int data ; LNode *head, *p, *q; head=p=(LNode *)malloc(sizeof(LNode)); p->next=NULL; /* 创建单链表的表头结点
head */

while (1) { scanf(“%d”,& data); if (data==32767) break ;

/*钩链,新创建的结点总是作为最后一个结点*/

} return (head); } 无论是哪种插入方法,如果要插入建立的单线 性链表的结点是n个,算法的时间复杂度均为O(n)。 对于单链表,无论是哪种操作,只要涉及到钩链( 或重新钩链),如果没有明确给出直接后继,钩链(或 重新钩链)的次序必须是“先右后左”。

2 单链表的查找
(1) 按序号查找 取单链表中的第i个元素。
对于单链表,不能象顺序表中那样直接按序号i访 问结点,而只能从链表的头结点出发,沿链域next逐 个结点往下搜索,直到搜索到第i个结点为止。因此, 链表不是随机存取结构。 设单链表的长度为n,要查找表中第i个结点,仅 当1≦i≦n时,i的值是合法的。

算法描述
ElemType Get_Elem(LNode *L , int i) { int j ; LNode *p; p=L->next; j=1;
*/ /* 使p指向第一个结点

while (p!=NULL && j<i) { p=p–>next; j++; }
p , j计数 */

/* 移动指针

if (j!=i) return(-32768) ; else return(p->data);
/* p为NULL 表示i太大; j>i表示i为0 */

} 移动指针p的频度:

(2) 按值查找
按值查找是在链表中,查找是否有结点值等于给定 值key的结点? 若有,则返回首次找到的值为key的结 点的存储位置;否则返回NULL。查找时从开始结点出 发,沿链表逐个将结点的值和给定值key作比较。

算法描述
LNode *Locate_Node(LNode *L,int key)
/* 在以L为头结点的单链表中查找值为key的第一个结点 */

{

LNode *p=L–>next; while ( p!=NULL&& p–>data!=key) p=p–>next; if (p–>data==key) return p;

else
{ } printf(“所要查找的结点不存在!!\n”); retutn(NULL);

}

3 单链表的插入
插入运算是将值为e的新结点插入到表的第i个结 点的位置上,即插入到ai-1与ai之间。因此,必须首先 找到ai-1所在的结点p,然后生成一个数据域为e的新 结点q,q结点作为p的直接后继结点。

算法描述
void Insert_LNode(LNode *L,int i, ElemType e)
/* 在以L为头结点的单链表的第i个位置插入值为e的结 点 */

{

int j=0; LNode *p,*q;
p=L–>next ; while ( p!=NULL&& j<i-1)

if (j!=i-1) printf(“i太大或i为0!!\n ”); else { q=(LNode *)malloc(sizeof(LNode)); q–>data=e; q–>next=p–>next; p–>next=q; }
}

设链表的长度为n,合法的插入位置是1≦i≦n。算法 的时间主要耗费移动指针p上,故时间复杂度亦为O(n)。

4 单链表的删除
⑴ 按序号删除
删除单链表中的第i个结点。
为了删除第i个结点ai,必须找到结点的存储地址。 该存储地址是在其直接前趋结点ai-1的next域中,因 此,必须首先找到ai-1的存储位置p,然后令p–>next 指向ai的直接后继结点,即把ai从链上摘下。最后释放 结点ai的空间,将其归还给“存储池”。 设单链表长度为n,则删去第i个结点仅当1≦i≦n时 是合法的。则当i=n+1时,虽然被删结点不存在,但 其前趋结点却存在,是终端结点。故判断条件之一是 p–>next!=NULL。显然此算法的时间复杂度也是

算法描述
void Delete_LinkList(LNode *L, int i)
/* 删除以L为头结点的单链表中的第i个结点 */

{ int j=1; LNode *p,*q; p=L; q=L->next; while ( p->next!=NULL&& j<i) { p=q; q=q–>next; j++; } if (j!=i) printf(“i太大或i为0!!\n ”); else { p–>next=q–>next; free(q); } }

⑵ 按值删除
删除单链表中值为key的第一个结点。

与按值查找相类似,首先要查找值为key的结点是 否存在? 若存在,则删除;否则返回NULL。

算法描述
void Delete_LinkList(LNode *L,int key)
/* 删除以L为头结点的单链表中值为key的第一个结点 */

{

LNode *p=L, *q=L–>next; while ( q!=NULL&& q–>data!=key) { p=q; q=q–>next; } if (q–>data==key) { p->next=q->next; free(q); } else printf(“所要删除的结点不存在!!\n”);

}

算法的执行与形参key有关,平均时间复杂度为 O(n)。
从上面的讨论可以看出,链表上实现插入和删除运 算,无需移动结点,仅需修改指针。解决了顺序表的插 入或删除操作需要移动大量元素的问题。

变形之一:
删除单链表中值为key的所有结点。 与按值查找相类似,但比前面的算法更简单。

基本思想:从单链表的第一个结点开始,对每个结点
进行检查,若结点的值为key,则删除之,然后检查下 一个结点,直到所有的结点都检查。

算法描述
void Delete_LinkList_Node(LNode *L,int key)
/* 删除以L为头结点的单链表中值为key的第一个结点 */

{

LNode *p=L, *q=L–>next; while ( q!=NULL) { if (q–>data==key) { p->next=q->next; free(q); q=p->next; } else { p=q; q=q–>next; } }

}

变形之二:
删除单链表中所有值重复的结点,使得所有结点的 值都不相同。 与按值查找相类似,但比前面的算法更复杂。

基本思想:从单链表的第一个结点开始,对每个结点

进行检查:检查链表中该结点的所有后继结点,只要有 值和该结点的值相同,则删除之;然后检查下一个结点, 直到所有的结点都检查。

算法描述
void Delete_Node_value(LNode *L)
/* 删除以L为头结点的单链表中所有值相同的结点 */

{

LNode *p=L->next, *q, *ptr; while ( p!=NULL) /* 检查链表中所有结点
*/

{

*q=p, *ptr=p–>next;
/* 检查结点p的所有后继结点ptr */

while (ptr!=NULL) { if (ptr–>data==p->data) { q->next=ptr->next; free(ptr); ptr=q->next; }

p=p->next ;
} }

5 单链表的合并
设有两个有序的单链表,它们的头指针分别是 La 、 Lb,将它们合并为以Lc为头指针的有序链表。合并前 的示意图如图2-4所示。
Lc pc La pa -7 3 4 12 9 …… ……

23 ?
15 ?

Lb
-2 pb
图2-4

两个有序的单链表La ,Lb的初始状态

合并了值为-7,-2的结点后示意图如图2-5所示。
Lc La -7 Lb -2 4 pb 9

pa
3 12

…… ……

23

?

15 ?

pc
图2-5

合并了值为-7 ,-2的结点后的状态

算法说明
算法中pa ,pb分别是待考察的两个链表的当前 结点,pc是合并过程中合并的链表的最后一个结点。

算法描述
LNode *Merge_LinkList(LNode *La, LNode *Lb)
/* 合并以La, Lb为头结点的两个有序单链表 */

{

LNode *Lc, *pa , *pb , *pc, *ptr ;

Lc=La ; pc=La ; pb=Lb->next ;

pa=La->next ;

while (pa!=NULL && pb!=NULL) { if (pa->data<pb->data) { pc->next=pa ; pc=pa ; pa=pa->next ; }
/* 将pa所指的结点合并,pa指向下一个结点 */

if (pa->data==pb->data) { pc->next=pa ; pc=pa ; pa=pa->next ; ptr=pb ; pb=pb->next ; free(ptr) ; }
/* 将pa所指的结点合并,pb所指结点删除 */

} if (pa!=NULL) pc->next=pa ; else pc->next=pb ; /*将剩余的结点链上*/ free(Lb) ; return(Lc) ;

}

算法分析

2.3.3 循环链表
循环链表(Circular Linked List):是一种
头尾相接的链表。其特点是最后一个结点的指针域指向 链表的头结点,整个链表的指针域链接成一个环。

从循环链表的任意一个结点出发都可以找到链表 中的其它结点,使得表处理更加方便灵活。
图2-6是带头结点的单循环链表的示意图。
head

head
a1 a2 非空表
图2-6 单循环链表示意图

……

an

空表

循环链表的操作
对于单循环链表,除链表的合并外,其它的操作和 单线性链表基本上一致,仅仅需要在单线性链表操作算 法基础上作以下简单修改: ⑴ 判断是否是空链表:head->next==head ;

⑵ 判断是否是表尾结点:p->next==head ;

2.4 双向链表
双向链表(Double Linked List) :指的是构
成链表的每个结点中设立两个指针域:一个指向其直接 前趋的指针域prior,一个指向其直接后继的指针域 next。这样形成的链表中有两个方向不同的链,故称 为双向链表。 和单链表类似,双向链表一般增加头指针也能使双 链表上的某些运算变得方便。 将头结点和尾结点链接起来也能构成循环链表,并 称之为双向循环链表。 双向链表是为了克服单链表的单向性的缺陷而引入 的。

1

双向链表的结点及其类型定义

双向链表的结点的类型定义如下。其结点形式如 图2-7所示,带头结点的双向链表的形式如图2-8所示。 typedef struct Dulnode { ElemType data ; struct Dulnode *prior , *next ; }DulNode ;
prior data next head ? ? head
图2-7 双向链表结点形式

?

a1

a2

……

an ?

空双向链表

非空双向链表 图2-8 带头结点的双向链表形式

双向链表结构具有对称性,设p指向双向链表中的 某一结点,则其对称性可用下式描述:
(p->prior)->next=p=(p->next)->prior ; 结点p的存储位置存放在其直接前趋结点p>prior的直接后继指针域中,同时也存放在其直接后 继结点p->next的直接前趋指针域中。

2 双向链表的基本操作
(1) 双向链表的插入 将值为e的结点插入双向链表
p p 中。插入前后链表的变化如图 2-9所示。 …… ai ai+1 …… ……
图2-9 双向链表的插入

ai

ai+1

……

S e

S e

① 插入时仅仅指出直接前驱结点,钩链时必须注意 先后次序是: “先右后左” 。部分语句组如下:
S=(DulNode *)malloc(sizeof(DulNode)); S->data=e;

S->next=p->next;
常重要 */

p->next->prior=S;
/* 钩链次序非

p->next=S; S->prior=p;

② 插入时同时指出直接前驱结点p和直接后继结点 q,钩链时无须注意先后次序。部分语句组如下:

S=(DulNode *)malloc(sizeof(DulNode));
S->data=e;

(2)

双向链表的结点删除

设要删除的结点为p ,删除时可以不引入新的辅助 指针变量,可以直接先断链,再释放结点。部分语句组 如下: p->prior->next=p->next;

p->next->prior=p->prior;
free(p);

注意:
与单链表的插入和删除操作不同的是,在双向链 表中插入和删除必须同时修改两个方向上的指针域的指 向。

2.5 一元多项式的表示和相加
1 一元多项式的表示

一元多项式 p(x)=p0+p1x+p2x2+ … +pnxn , 由n+1个系数唯一确定。则在计算机中可用线性表(p0 , p1 ,p2 ,… ,pn )表示。既然是线性表,就可以用顺 序表和链表来实现。两种不同实现方式的元素类型定义 如下: (1) 顺序存储表示的类型 (2) 链式存储表示的类型 typedef struct ploy typedef struct { float coef ; /*系数部分*/ { float coef; /*系数部分*/ int expn ; /*指数部分*/ int expn; /*指数部分*/ struct ploy *next ; } ElemType ; } Ploy ;

2

一元多项式的相加
不失一般性,设有两个一元多项式:

P(x)=p0+p1x+p2x2+ … +pnxn ,
Q(x)=q0+q1x+q2x2+ … +qmxm (m<n)

R(x)=P(x)+ Q(x)
R(x)由线性表R((p0+q0) ,(p1+q1) , (p2+q2) , … ,(pm+qm) , … , pn)唯一表示。

⑴ 顺序存储表示的相加
线性表的定义
typedef struct { ElemType a[MAX_SIZE] ; int length ;

}Sqlist ;
用顺序表示的相加非常简单。访问第5项可直接 访问:L.a[4].coef , L.a[4].expn

(2) 链式存储表示的相加
当采用链式存储表示时,根据结点类型定义,凡 是系数为0的项不在链表中出现,从而可以大大减少链 表的长度。

一元多项式相加的实质是:
? 指数不同: 是链表的合并。

? 指数相同: 系数相加,和为0,去掉结点,和不 为0,修改结点的系数域。

算法之一:
就在原来两个多项式链表的基础上进行相加,相加 后原来两个多项式链表就不在存在。当然再要对原来 两个多项式进行其它操作就不允许了。

算法描述
Ploy *add_ploy(ploy *La, ploy *Lb)
/* 将以La ,Lb为头指针表示的一元多项式相加 */

{ ploy *Lc , *pc , *pa , *pb ,*ptr ; float x ; Lc=pc=La ; pa=La->next ; pb=Lb>next ;

while (pa!=NULL&&pb!=NULL)
{ if (pa->expn<pb->expn) { pc->next=pa ; pc=pa ; pa=pa>next ; }
/* 将pa所指的结点合并,pa指向下一个结点 */

else
{ x=pa->coef+pb->coef ;

if (abs(x)<=1.0e-6)
/* 如果系数和为0,删除两个结点 */

{ ptr=pa ; pa=pa->next ; free(ptr) ; ptr=pb ; pb=pb->next ; free(ptr) ; } else
/* 如果系数和不为0,修改其中 一个结点的系数域,删除另一个结点 */

{ pc->next=pa ; pa>coef=x ;

}
}
/* end of while */

if (pa==NULL) pc->next=pb ; else pc->next=pa ; return (Lc) ; }

算法之二:
对两个多项式链表进行相加,生成一个新的相加后 的结果多项式链表,原来两个多项式链表依然存在, 不发生任何改变,如果要再对原来两个多项式进行其 它操作也不影响。

算法描述
Ploy *add_ploy(ploy *La, ploy *Lb)
/* 将以La ,Lb为头指针表示的一元多项式相加,生成一 个新的结果多项式 */

{ ploy *Lc , *pc , *pa , *pb , *p ; x; pa=La->next ; pb=Lb->next ; while (pa!=NULL&&pb!=NULL) { if (pa->expn<pb->expn)

float

Lc=pc=(ploy *)malloc(sizeof(ploy)) ;

{ p=(ploy *)malloc(sizeof(ploy))
;

/* 生成一个新的结果结点并赋值 */

pc->next=p ; pc=p ; pa=pa>next ; }
/* 生成的结点插入到结果链表的最后,pa指 向下一个结点 */

if (pa->expn>pb->expn) { p=(ploy *)malloc(sizeof(ploy))

;
p->coef=pb->coef ; p>expn=pb->expn ; p->next=NULL ;
/* 生成一个新的结果结点并赋值 */

if (pa->expn==pb->expn) { x=pa->coef+pb->coef ; if (abs(x)<=1.0e-6)
/* 系数和为0,pa, pb分别直接后继 结点 */

{ pa=pa->next ; pb=pb>next ; }
/* 若系数和不为0,生成的结点 插入到结果链表的最后, pa, pb分别直接后继结点 */

else

{ p=(ploy *)malloc(sizeof(ploy)) ; p->coef=x ; p-

}
}

}

/* end of while */

if (pb!=NULL) while(pb!=NULL) { p=(ploy *)malloc(sizeof(ploy)) ; p->coef=pb->coef ; p>expn=pb->expn ; p->next=NULL ;
/* 生成一个新的结果结点并赋值 */

pc->next=p ; pc=p ; pb=pb>next ;

if (pa!=NULL) while(pa!=NULL) { p=(ploy *)malloc(sizeof(ploy)) ; p->coef=pb->coef ; p>expn=pa->expn ;
p->next=NULL ;
/* 生成一个新的结果结点并赋值 */

pc->next=p ; pc=p ; pa=pa>next ;
} return (Lc) ; }

习题二
1 简述下列术语:线性表,顺序表,链表。

2 何时选用顺序表,何时选用链表作为线性表的存 储结构合适?各自的主要优缺点是什么?
3 在顺序表中插入和删除一个结点平均需要移动多 少个结点?具体的移动次数取决于哪两个因素? 4 链表所表示的元素是否有序?如有序,则有序性 体现于何处?链表所表示的元素是否一定要在物理上是 相邻的?有序表的有序性又如何理解? 5 设顺序表L是递增有序表,试写一算法,将x插入 到L中并使L仍是递增有序表。

6 写一求单链表的结点数目ListLength(L)的算 法。
7 写一算法将单链表中值重复的结点删除,使所得 的结果链表中所有结点的值均不相同。 8 写一算法从一给定的向量A删除值在x到 y(x≤y)之间的所有元素(注意:x和y是给定的参数, 可以和表中的元素相同,也可以不同)。 9 设A和B是两个按元素值递增有序的单链表,写一 算法将A和B归并为按按元素值递减有序的单链表C, 试分析算法的时间复杂度。

第3章 栈和队列
栈和队列是两种应用非常广泛的数据结构,它们都 来自线性表数据结构,都是“操作受限”的线性表。 栈在计算机的实现有多种方式:

◆ 硬堆栈:利用CPU中的某些寄存器组或类似的硬 件或使用内存的特殊区域来实现。这类堆栈容量有限, 但速度很快;

◆ 软堆栈:这类堆栈主要在内存中实现。堆栈容量 可以达到很大。在实现方式上,又有动态方式和静态 方式两种。 本章将讨论栈和队列的基本概念、存储结构、基本 操作以及这些操作的具体实现。

3.1 栈
3.1.1 栈的基本概念
1 栈的概念
栈(Stack):是限制在表的一端进行插入和删除
操作的线性表。又称为后进先出LIFO (Last In First Out)或先进后出FILO (First In Last Out) 线性表。

栈顶(Top):允许进行插入、删除操作的一端,
又称为表尾。用栈顶指针(top)来指示栈顶元素。

栈底(Bottom):是固定端,又称为表头。 空栈:当表中没有元素时称为空栈。

设栈S=(a1,a2,…an),则 a1称为栈底元素,an为栈顶元素, 如图3-1所示。

进栈(push)

出栈(pop)

top

栈中元素按a1,a2,…an的次 序进栈,退栈的第一个元素应为栈顶 元素。即栈的修改是按后进先出的原 bottom 则进行的。 图3-1

an ?? ai ?? a2 a1
顺序栈示意图

2 栈的抽象数据类型定义
ADT Stack{

数据对象:D ={ ai|ai∈ElemSet, i=1,2,…,n,n≥0 }
数据关系:R ={<ai-1, ai>|ai-1,ai∈D, i=2,3,…,n } 基本操作:初始化、进栈、出栈、取栈顶元素等

} ADT Stack

3.1.2 栈的顺序存储表示

栈的顺序存储结构简称为顺序栈,和线性表相类似, 用一维数组来存储栈。根据数组是否可以根据需要增大, 又可分为静态顺序栈和动态顺序栈。 ◆ 静态顺序栈实现简单,但不能根据需要增大栈的 存储空间; ◆ 动态顺序栈可以根据需要增大栈的存储空间,但 实现稍为复杂。

3.1.2.1 栈的动态顺序存储表示
采用动态一维数组来存储栈。所谓动态,指的是栈 的大小可以根据需要增加。

◆ 用bottom表示栈底指针,栈底固定不变的;栈 顶则随着进栈和退栈操作而变化。用top(称为栈顶 指针)指示当前栈顶位置。
◆ 用top=bottom作为栈空的标记,每次top指向 栈顶数组中的下一个存储位置。

◆ 结点进栈:首先将数据元素保存到栈顶(top所 指的当前位置),然后执行top加1,使top指向栈顶 的下一个存储位置;

◆ 结点出栈:首先执行top减1,使top指向栈顶 元素的存储位置,然后将栈顶元素取出。 图3-2是一个动态栈的变化示意图。
top
top bottom top 空栈

bottom 元素a进栈 top

a

bottom 元素b,c进栈

c b a

top bottom 元素c退栈

b a

bottom 元素d,e,f进栈

f e d b a

图3-2 (动态)堆栈变化示意图

基本操作的实现
1 栈的类型定义
#define STACK_SIZE 100
*/
/* 栈初始向量大小 /* 存储空间分

#define STACKINCREMENT 10
配增量 */

#typedef int ElemType ;
typedef struct sqstack

{

ElemType *bottom;
ElemType *top;

/* 栈不存在时值为

NULL */ /* 栈顶指针 */

int

stacksize ;

/* 当前已分配空间,以元素

为单位 */

2 栈的初始化
Status Init_Stack(void)
{ SqStack S ; S.bottom=(ElemType *)malloc(STACK_SIZE *sizeof(ElemType)); if (! S.bottom) return ERROR; S.top=S.bottom ;
相同 */ /* 栈空时栈顶和栈底指针

S. stacksize=STACK_SIZE;
return OK ; }

3 压栈(元素进栈)
Status push(SqStack S , ElemType e)

{ if (S.top-S.bottom>=S. stacksize-1)
{ S.bottom=(ElemType *)realloc((S. STACKINCREMENT+STACK_SIZE) *sizeof(ElemType)); /* 栈满,追加存储空
间 */

if (! S.bottom) return ERROR;

S.top=S.bottom+S. stacksize ;
S. stacksize+=STACKINCREMENT ;

4 弹栈(元素出栈)
Status pop( SqStack
/*弹出栈顶元素*/

S, ElemType *e )

{

if ( S.top== S.bottom )

return ERROR ;
*/

/* 栈空,返回失败标志

S.top-- ; e=*S. top ; return OK ; }

3.1.2.2 栈的静态顺序存储表示
采用静态一维数组来存储栈。 栈底固定不变的,而栈顶则随着进栈和退栈操作变 化的, ◆ 栈底固定不变的;栈顶则随着进栈和退栈操作而 变化,用一个整型变量top(称为栈顶指针)来指示当 前栈顶位置。 ◆ 用top=0表示栈空的初始状态,每次top指向栈 顶在数组中的存储位置。 ◆ 结点进栈:首先执行top加1,使top指向新的 栈顶位置,然后将数据元素保存到栈顶(top所指的 当前位置)。

◆ 结点出栈:首先把top指向的栈顶元素取出,然 后执行top减1,使top指向新的栈顶位置。 若栈的数组有Maxsize个元素,则 top=Maxsize-1时栈满。图3-3是一个大小为5的栈 的变化示意图。
top top top bottom top bottom 空栈

a
Top=1 1个元素进栈 bottom

c b a

top bottom

b a
bottom

e d b a
Top=4 栈满

Top=3 3个元素进栈

Top=2 元素c进栈

图3-3 静态堆栈变化示意图

基本操作的实现
1 栈的类型定义
/* 栈向

# define MAX_STACK_SIZE 100
量大小 */

# typedef int ElemType ; typedef struct sqstack

{ ElemType stack_array[MAX_STACK_SIZE] ;
int top; }SqStack ;

2 栈的初始化
SqStack Init_Stack(void)
{ } SqStack S ; S.bottom=S.top=0 ; return(S) ;

3 压栈(元素进栈)
Status push(SqStack S , ElemType e)
/* 使数据元素e进栈成为新的栈顶 */

{ if (S.top==MAX_STACK_SIZE-1) return ERROR;
*/
/* 栈满,返回错误标志

S.top++ ;
顶 */

/*

栈顶指针加1 */ /* e成为新的栈 */

S.stack_array[S.top]=e ; return OK;
/* 压栈成功

}

4

弹栈(元素出栈)
S, ElemType *e )
/*弹出栈顶元素*/

Status pop( SqStack
{ if ( S.top==0 )

return ERROR ;
*/

/* 栈空,返回错误标志

*e=S.stack_array[S.top] ; S.top-- ; return OK ;

}

当栈满时做进栈运算必定产生空间溢出,简称“上 溢”。上溢是一种出错状态,应设法避免。

当栈空时做退栈运算也将产生溢出,简称“下溢”。 下溢则可能是正常现象,因为栈在使用时,其初态或终 态都是空栈,所以下溢常用来作为控制转移的条件。

3.1.3 栈的链式存储表示
1 栈的链式表示

栈的链式存储结构称为链栈,是运算受限的单链表。 其插入和删除操作只能在表头位置上进行。因此,链栈 没有必要像单链表那样附加头结点,栈顶指针top就是 链表的头指针。图3-4是栈的链式存储表示形式。 链栈的结点类型说明如下: typedef struct Stack_Node { ElemType data ; struct Stack_Node *next ; } Stack_Node ;
top

? top
空栈

a4
a3 a2 a1 ?
非空栈

图3-4 链栈存储形式

2

链栈基本操作的实现

(1) 栈的初始化
Stack_Node *Init_Link_Stack(void)

{

Stack_Node *top ;
top=(Stack_Node *)malloc(sizeof(Stack_Node )) ; top->next=NULL ; return(top) ;

}

(2) 压栈(元素进栈)
Status push(Stack_Node *top , ElemType e)
{ Stack_Node *p ; p=(Stack_Node *)malloc(sizeof(Stack_Node)) ;

if (!p) return ERROR;
/* 申请新结点失败,返回错误标志 */

p->data=e ; p->next=top->next ; top->next=p ;
/* 钩链 */

return OK;

(3) 弹栈(元素出栈)
Status pop(Stack_Node *top , ElemType *e)
/* 将栈顶元素出栈 */

{

Stack_Node *p ; ElemType e ; if (top->next==NULL )

return ERROR ;
*/

/* 栈空,返回错误标志
/* 取栈顶元 */

p=top->next ; e=p->data ;
素 */
/*

top->next=p->next ; free(p) ;

修改栈顶指针

3.2 栈的应用
由于栈具有的“后进先出”的固有特性,因此,栈 成为程序设计中常用的工具和数据结构。以下是几个栈 应用的例子。

3.2.1 数制转换
十进制整数N向其它进制数d(二、八、十六)的转 换是计算机实现计算的基本问题。 转换法则:该转换法则对应于一个简单算法原理: n=(n div d)*d+n mod d

其中:div为整除运算,mod为求余运算
例如 (1348)10= (2504)8,其运算过程如下: n 1348 168 n div 8 168 21 n mod 8 4 0

21
2

2
0

5
2

采用静态顺序栈方式实现

void conversion(int n , int d)
/*将十进制整数N转换为d(2或8)进制数*/

{ SqStack S ;

int k, *e ; }

S=Init_Stack();
while (n>0) { k=n%d ; push(S , k) ; n=n/d ;
/* 求出所有的余数,进栈 */

while (S.top!=0) { pop(S, e) ;

/* 栈不空时出栈,输出 */

printf(“%1d” , *e) ; }

}

3.2.2

括号匹配问题

在文字处理软件或编译程序设计时,常常需要检 查一个字符串或一个表达式中的括号是否相匹配?

匹配思想:从左至右扫描一个字符串(或表达式),则

每个右括号将与最近遇到的那个左括号相匹配。则可以 在从左至右扫描过程中把所遇到的左括号存放到堆栈中。 每当遇到一个右括号时,就将它与栈顶的左括号(如果 存在)相匹配,同时从栈顶删除该左括号。

算法思想:设置一个栈,当读到左括号时,左括号进
栈。当读到右括号时,则从栈中弹出一个元素,与读到 的左括号进行匹配,若匹配成功,继续读入;否则匹配 失败,返回FLASE。

算法描述
#define TRUE 0

#define FLASE -1
SqStack S ; S=Init_Stack() ; /*堆栈初始化*/ int Match_Brackets( ) { char ch , x ;

scanf(“%c” , &ch) ;
while (asc(ch)!=13)

{ if ((ch==‘(’)||(ch==‘[’)) push(S , ch) ; else if (ch==‘]’) { x=pop(S) ; if (x!=‘[’) { printf(“’[’括号不匹配”) ; return FLASE ; } } else if (ch==‘)’) { x=pop(S) ; if (x!=‘(’) { printf(“’(’括号不匹配”) ; return FLASE ;} }

if (S.top!=0) { printf(“括号数量不匹配!”) ; return FLASE ; } else return TRUE ; }

3.2.2 栈与递归调用的实现
栈的另一个重要应用是在程序设计语言中实现递归 调用。

递归调用:一个函数(或过程)直接或间接地调用
自己本身,简称递归(Recursive)。

递归是程序设计中的一个强有力的工具。因为递归 函数结构清晰,程序易读,正确性很容易得到证明。
为了使递归调用不至于无终止地进行下去,实际上 有效的递归调用函数(或过程)应包括两部分:递推规则 (方法),终止条件。

例如:求n!

1
Fact(n)=

当n=0时

终止条件
递推规则

n*fact(n-1) 当n>0时

为保证递归调用正确执行,系统设立一个“递归工 作栈”,作为整个递归调用过程期间使用的数据存储区。
每一层递归包含的信息如:参数、局部变量、上一 层的返回地址构成一个“工作记录” 。每进入一层递 归,就产生一个新的工作记录压入栈顶;每退出一层递 归,就从栈顶弹出一个工作记录。

从被调函数返回调用函数的一般步骤:
(1) 若栈为空,则执行正常返回。 ⑵ 从栈顶弹出一个工作记录。 ⑶ 将“工作记录”中的参数值、局部变量值赋给相 应的变量;读取返回地址。

⑷ 将函数值赋给相应的变量。
(5) 转移到返回地址。

3.3

队 列

3.3.1 队列及其基本概念
1 队列的基本概念

队列(Queue):也是运算受限的线性表。是一种 先进先出(First In First Out ,简称FIFO)的线性 表。只允许在表的一端进行插入,而在另一端进行删除。
队首(front) :允许进行删除的一端称为队首。 队尾(rear) :允许进行插入的一端称为队尾。

例如:排队购物。操作系统中的作业排队。先进入 队列的成员总是先离开队列。

队列中没有元素时称为空队列。在空队列中依次 加入元素a1, a2, …, an之后,a1是队首元素,an是队 尾元素。显然退出队列的次序也只能是a1, a2, …, an , 即队列的修改是依先进先出的原则进行的,如图3-5所 示。 出队 a1 , a2 , … , an 入队
队首 队尾

图3-5 队列示意图

2 队列的抽象数据类型定义
ADT Queue{

数据对象:D ={ ai|ai∈ElemSet, i=1, 2, …, n, n >= 0 }

数据关系:R = {<ai-1, ai> | ai-1, ai∈D, i=2,3,…,n }
约定a1端为队首,an端为队尾。

基本操作:
Create():创建一个空队列; EmptyQue():若队列为空,则返回true ,否则返 回flase ; ??

InsertQue(x) :向队尾插入元素x;
DeleteQue(x) :删除队首元素x; } ADT Queue

3.3.2 队列的顺序表示和实现
利用一组连续的存储单元(一维数组) 依次存放从队 首到队尾的各个元素,称为顺序队列。

对于队列,和顺序栈相类似,也有动态和静态之分。 本部分介绍的是静态顺序队列,其类型定义如下: #define MAX_QUEUE_SIZE 100 typedef struct queue { ElemType Queue_array[MAX_QUEUE_SIZE] ; int front ;

int rear ;
}SqQueue;

3.3.2.1 队列的顺序存储结构
设立一个队首指针front ,一个队尾指针rear ,分 别指向队首和队尾元素。
◆ 初始化:front=rear=0。

◆ 入队:将新元素插入rear所指的位置,然后rear加 1。
◆ 出队:删去front所指的元素,然后加1并返回被删 元素。 ◆ 队列为空:front=rear。

◆ 队满:rear=MAX_QUEUE_SIZE-1或front=rear。

在非空队列里,队首指针始终指向队头元素,而 队尾指针始终指向队尾元素的下一位置。 顺序队列中存在“假溢出”现象。因为在入队和 出队操作中,头、尾指针只增加不减小,致使被删除元 素的空间永远无法重新利用。因此,尽管队列中实际元 素个数可能远远小于数组大小,但可能由于尾指针巳超 出向量空间的上界而不能做入队操作。该现象称为假溢 出。如图3-6所示是数组大小为5的顺序队列中队首、 队尾指针和队列中元素的变化情况。

Q.rear Q.rear Q.rear Q.front (a) 空队列 Q.front a3 a2 a1 Q.rear Q.front Q.front

a5 a4

(b) 入队3个元素 (c) 出队3个元素 图3-6 队列示意图

(d) 入队2个元素

3.3.2.2

循环队列

为充分利用向量空间,克服上述“假溢出”现象的 方法是:将为队列分配的向量空间看成为一个首尾相接 的圆环,并称这种队列为循环队列(Circular Queue)。 在循环队列中进行出队、入队操作时,队首、队尾 指针仍要加1,朝前移动。只不过当队首、队尾指针指 向向量上界(MAX_QUEUE_SIZE-1)时,其加1操作的 结果是指向向量的下界0。
这种循环意义下的加1操作可以描述为: if (i+1==MAX_QUEUE_SIZE) i=0; else i++ ; 其中: i代表队首指针(front)或队尾指针(rear)

用模运算可简化为: i=(i+1)%MAX_QUEUE_SIZE ;
显然,为循环队列所分配的空间可以被充分利用 ,除非向量空间真的被队列元素全部占用,否则不会上 溢。因此,真正实用的顺序队列是循环队列。

例:设有循环队列QU[0,5],其初始状态是
front=rear=0,各种操作后队列的头、尾指针的状 态变化情况如下图 3-7所示。 rear
front
0 5 4 3 1 2 front

d
5 rear

0
4

1 3

e
2 b 5 rear

0 4

1

front 2 b

g

3

g

(a) 空队列

(b) d, e, b, g入队

(c) d, e出队

rear

rear

k

0 4

1 2 b 3

front

k j 5

k
1 2 4 3 front

0

0 4

1 3

r
2 p rear

j 5
i

j 5
i

g

front

i

(d) i, j, k入队

(e) b, g出队

(f) r, p, s, t入队

图3-7 循环队列操作及指针变化情况

入队时尾指针向前追赶头指针,出队时头指针向前 追赶尾指针,故队空和队满时头尾指针均相等。因此, 无法通过front=rear来判断队列“空”还是“满”。 解决此问题的方法是:约定入队前,测试尾指针在循环 意义下加1后是否等于头指针,若相等则认为队满。即:
◆ rear所指的单元始终为空。

◆ 循环队列为空:front=rear 。
◆ 循环队列满: (rear+1)%MAX_QUEUE_SIZE =front。

循环队列的基本操作
1 循环队列的初始化
SqQueue Init_CirQueue(void)

{ SqQueue Q ;
Q.front=Q.rear=0; return(Q) ;

}

2 入队操作
Status Insert_CirQueue(SqQueue Q , ElemType e)
/* 将数据元素e插入到循环队列Q的队尾 */

{ if ((Q.rear+1)%MAX_QUEUE_SIZE== Q.front)
return ERROR;
/* 队满,返回错误标志 */

Q.Queue_array[Q.rear]=e ; /* 元素e入队 */ Q.rear=(Q.rear+1)% MAX_QUEUE_SIZE ;
/* 队尾指针向前移动 */

return OK;
}

/* 入队成功

*/

3 出队操作
Status Delete_CirQueue(SqQueue Q, ElemType *x )
/* 将循环队列Q的队首元素出队 */

{ if (Q.front+1== Q.rear)
return ERROR ;
/* 队空,返回错误标志 */

*x=Q.Queue_array[Q.front] ; /* 取队首元素 */ Q.front=(Q.front+1)% MAX_QUEUE_SIZE ;
/* 队首指针向前移动 */

return OK ;
}

3.3.3 队列的链式表示和实现
1 队列的链式存储表示
队列的链式存储结构简称为链队列,它是限制仅 在表头进行删除操作和表尾进行插入操作的单链表。

需要两类不同的结点:数据元素结点,队列的队首 指针和队尾指针的结点,如图3-8所示。
数据元素结点类型定义: typedef struct Qnode
data
数据元素结点

{ ElemType
}QNode ;

data ;

front rear
指针结点

struct Qnode *next ;

图3-8 链队列结点示意图

指针结点类型定义:
typedef struct link_queue { QNode *front , *rear ;

}Link_Queue ;

2

链队运算及指针变化

链队的操作实际上是单链表的操作,只不过是删 除在表头进行,插入在表尾进行。插入、删除时分别修 改不同的指针。链队运算及指针变化如图3-9所示。

front rear
(a) 空队列



front rear
(b) x入队

x ∧

front rear

x
(c) y再入队

y ∧

front rear

x
(d) x出队

y ∧

图3-9 队列操作及指针变化

3 链队列的基本操作
⑴ 链队列的初始化
LinkQueue *Init_LinkQueue(void) { LinkQueue *Q ; QNode *p ; p=(QNode *)malloc(sizeof(QNode)) ; /* 开辟头结点 */

p->next=NULL ;
Q=(LinkQueue *)malloc(sizeof(LinkQueue)) ;
/* 开辟链队的指针结点 */

Q.front=Q.rear=p ; return(Q) ; }

⑵ 链队列的入队操作
在已知队列的队尾插入一个元素e ,即修改队尾指 针(Q.rear)。 Status Insert_CirQueue(LinkQueue *Q , ElemType e)
/* 将数据元素e插入到链队列Q的队尾 */

{ p=(QNode *)malloc(sizeof(QNode)) ; if (!p) return ERROR;
/* 申请新结点失败,返回错误标志 */

p->data=e ; p->next=NULL ; return OK; }

/* 形成新结点 */

Q.rear->next=p ; Q.rear=p ; /* 新结点插入到队尾 */

⑶ 链队列的出队操作
Status Delete_LinkQueue(LinkQueue *Q, ElemType *x)
{ QNode *p ;

if (Q.front==Q.rear) return ERROR ; /* 队空 */
p=Q.front->next ; /* 取队首结点 */

*x=p->data ;
Q.front->next=p->next ;
/* 修改队首指针 */

if (p==Q.rear) Q.rear=Q.front ;
/* 当队列只有一个结点时应防止丢失队尾指针 */

free(p) ;

return OK ;

⑷ 链队列的撤消
void Destroy_LinkQueue(LinkQueue *Q )
/* 将链队列Q的队首元素出队 */

{ while (Q.front!=NULL)

{ Q.rear=Q.front->next;
/* 令尾指针指向队列的第一个结点 */

free(Q.front); Q.ront=Q.rear;

/* 每次释放一个结点 */

/* 第一次是头结点,以后是元素结点 */

}
}

习 题 三
1 设有一个栈,元素进栈的次序为a, b, c。问经过 栈操作后可以得到哪些输出序列?
2 循环队列的优点是什么?如何判断它的空和满?

3 设有一个静态顺序队列,向量大小为MAX,判断 队列为空的条件是什么?队列满的条件是什么?
4 设有一个静态循环队列,向量大小为MAX,判断 队列为空的条件是什么?队列满的条件是什么? 5 利用栈的基本操作,写一个返回栈S中结点个数的 算法int StackSize(SeqStack S) ,并说明S为何 不作为指针参数的算法?

6 一个双向栈S是在同一向量空间内实现的两个栈, 它们的栈底分别设在向量空间的两端。试为此双向栈设 计初始化InitStack(S) ,入栈Push(S,i,x),出栈 Pop(S,i,x)算法,其中i为0或1 ,用以表示栈号。
7 设Q[0,6]是一个静态顺序队列,初始状态为 front=rear=0,请画出做完下列操作后队列的头尾 指针的状态变化情况,若不能入对,请指出其元素,并 说明理由。

a, b, c, d入队
a, b, c出队 i , j , k , l , m入队 d, i出队 n, o, p, q, r入队

8 假设Q[0,5]是一个循环队列,初始状态为 front=rear=0,请画出做完下列操作后队列的头尾 指针的状态变化情况,若不能入对,请指出其元素,并 说明理由。
d, e, b, g, h入队

d, e出队
i , j , k , l , m入队 b出队 n, o, p, q, r入队

第 4章 串
在非数值处理、事务处理等问题常涉及到一系列 的字符操作。计算机的硬件结构主要是反映数值计算的 要求,因此,字符串的处理比具体数值处理复杂。本章 讨论串的存储结构及几种基本的处理。

4.1 串类型的定义
4.1.1 串的基本概念
串(字符串):是零个或多个字符组成的有限序列。 记作: S=“a1a2a3…”,其中S是串名,ai(1≦i≦n)是 单个,可以是字母、数字或其它字符。 串值:双引号括起来的字符序列是串值。

串长:串中所包含的字符个数称为该串的长度。
空串(空的字符串):长度为零的串称为空串,它不 包含任何字符。

空格串(空白串):构成串的所有字符都是空格的串 称为空白串。

注意:空串和空白串的不同,例如“ ”和“”分别表 示长度为1的空白串和长度为0的空串。 子串(substring):串中任意个连续字符组成的子 序列称为该串的子串,包含子串的串相应地称为主串。

子串的序号:将子串在主串中首次出现时的该子串 的首字符对应在主串中的序号,称为子串在主串中的序 号(或位置)。 例如,设有串A和B分别是:
A=“这是字符串”,B=“是”

则B是A的子串,A为主串。B在A中出现了两次,其中 首次出现所对应的主串位置是3。因此,称B在A中的序 号为3 。

特别地,空串是任意串的子串,任意串是其自身的 子串。 串相等:如果两个串的串值相等(相同),称这两个 串相等。换言之,只有当两个串的长度相等,且各个对 应位置的字符都相同时才相等。 通常在程序中使用的串可分为两种:串变量和串常
量。 串常量和整常数、实常数一样,在程序中只能被引 用但不能不能改变其值,即只能读不能写。通常串常量 是由直接量来表示的,例如语句错误(“溢出”)中“溢 出”是直接量。 串变量和其它类型的变量一样,其值是可以改变。

4.1.2 串的抽象数据类型定义
ADT String{

数据对象:D = { ai|ai∈CharacterSet, i=1,2,…,n, n ≥0 }
数据关系:R = {<ai-1, ai>| ai-1, ai∈D, i=2,3,…,n }

基本操作:
StrAssign(t , chars)

初始条件: chars是一个字符串常量。
操作结果:生成一个值为chars的串t 。 StrConcat(s, t)

初始条件:串s, t 已存在。

操作结果:将串t联结到串s后形成新串存放到s中。 StrLength(t) 初始条件:字符串t已存在。

操作结果:返回串t中的元素个数,称为串长。
SubString (s, pos, len, sub) 初始条件:串s, 已存在, 1≦pos≦StrLength(s)且 0≦len≦StrLength(s) –pos+1。 操作结果:用sub返回串s的第pos个字符起长度为len 的子串。 …… } ADT String

4.2 串的存储表示和实现

串是一种特殊的线性表,其存储表示和线性表类似, 但又不完全相同。串的存储方式取决于将要对串所进行 的操作。串在计算机中有3种表示方式: ◆ 定长顺序存储表示:将串定义成字符数组,利用 串名可以直接访问串值。用这种表示方式,串的存 储空间在编译时确定,其大小不能改变。 ◆ 堆分配存储方式:仍然用一组地址连续的存储单 元来依次存储串中的字符序列,但串的存储空间是 在程序运行时根据串的实际长度动态分配的。 ◆ 块链存储方式:是一种链式存储结构表示。

4.2.1 串的定长顺序存储表示
这种存储结构又称为串的顺序存储结构。是用一 组连续的存储单元来存放串中的字符序列。所谓定长顺 序存储结构,是直接使用定长的字符数组来定义,数组 的上界预先确定。 定长顺序存储结构定义为: #define MAX_STRLEN 256 typedef struct { char str[MAX_STRLEN] ;

int length;
} StringType ;

1 串的联结操作
Status StrConcat ( StringType s, StringType t)
/* 将串t联结到串s之后,结果仍然保存在s中 */

{ int i, j ;

if ((s.length+t.length)>MAX_STRLEN)
Return ERROR ;
/* 联结后长度超出范围 */ /* 串t联结

for (i=0 ; i<t.length ; i++)
s.str[s.length+i]=t.str[i] ;
到串s之后 */

s.length=s.length+t.length ; /* 修改联结
后的串长度 */

return OK ;

2

求子串操作

Status SubString (StringType s, int pos, int len, StringType *sub) { int k, j ; if (pos<1||pos>s.length||len<0||len>(s. length-pos+1)) return ERROR ;
度 */ /* 参数非法 */ /* 求得子串长

sub->length=len-pos+1 ;

for (j=0, k=pos ; k<=leng ; k++, j++)
sub->str[j]=s.str[i] ;
得子串 */ /* 逐个字符复制求

4.2.2 串的堆分配存储表示
实现方法:系统提供一个空间足够大且地址连续的 存储空间(称为“堆”)供串使用。可使用C语言的动态 存储分配函数malloc()和free()来管理。 特点是:仍然以一组地址连续的存储空间来存储字 符串值,但其所需的存储空间是在程序执行过程中动态 分配,故是动态的,变长的。 串的堆式存储结构的类型定义

typedef struct
{ char *ch;
/* 若非空,按长度分配,否则为NULL */ /* 串的长度 */

int length;
} HString ;

1 串的联结操作
Status Hstring *StrConcat(HString *T, HString *s1, HString *s2)
/* 用T返回由s1和s2联结而成的串 */

{

int k, j , t_len ;

if (T.ch) free(T);

/* 释放旧空间

*/

t_len=s1->length+s2->length ;

if ((p=(char *)malloc(sizeof((char)*t_len))==NUL L) { printf(“系统空间不够,申请空间失败 ! \n”) ;
return ERROR ; }

for (k=s1->length, j=0 ; j<s2->length; k++, j++) T->ch[j]=s1->ch[j] ; /* 将串s2复制到
串T中 */

free(s1->ch) ; free(s2->ch) ; return OK ;

}

4.2.3 串的链式存储表示
串的链式存储结构和线性表的串的链式存储结构类 似,采用单链表来存储串,结点的构成是: ◆ data域:存放字符,data域可存放的字符个数称为 结点的大小; ◆ next域:存放指向下一结点的指针。 若每个结点仅存放一个字符,则结点的指针域就非 常多,造成系统空间浪费,为节省存储空间,考虑串结 构的特殊性,使每个结点存放若干个字符,这种结构称 为块链结构。如图4-1是块大小为3的串的块链式存储结 构示意图。

head

a

b c

e

p c

??

g @ @?

图4-1 串的块链式存储结构示意图

串的块链式存储的类型定义包括: ⑴ 块结点的类型定义

#define BLOCK_SIZE 4
typedef struct Blstrtype { char data[BLOCK_SIZE] ; struct Blstrtype *next; }BNODE ;

(2) 块链串的类型定义 typedef struct

{ BNODE head;
int Strlen ;

/* 头指针 */
/* 当前长度 */

} Blstring ;
在这种存储结构下,结点的分配总是完整的结点为 单位,因此,为使一个串能存放在整数个结点中,在串 的末尾填上不属于串值的特殊字符,以表示串的终结。 当一个块(结点)内存放多个字符时,往往会使操作 过程变得较为复杂,如在串中插入或删除字符操作时通 常需要在块间移动字符。

4.3 串的模式匹配算法
模式匹配(模范匹配):子串在主串中的定位称为模
式匹配或串匹配(字符串匹配) 。模式匹配成功是指在 主串S中能够找到模式串T,否则,称模式串T在主串S 中不存在。 模式匹配的应用在非常广泛。例如,在文本编辑 程序中,我们经常要查找某一特定单词在文本中出现的 位置。显然,解此问题的有效算法能极大地提高文本编 辑程序的响应性能。

模式匹配是一个较为复杂的串操作过程。迄今为止, 人们对串的模式匹配提出了许多思想和效率各不相同的 计算机算法。介绍两种主要的模式匹配算法。

4.3.1 Brute-Force模式匹配算法
设S为目标串,T为模式串,且不妨设:
S=“s0s1s2…sn-1” , T=“t0t1t2 …tm-1”

串的匹配实际上是对合法的位置0≦i≦n-m依次将 目标串中的子串s[i…i+m-1]和模式串t[0…m-1]进 行比较: ◆ 若s[i…i+m-1]=t[0…m-1]:则称从位置i 开始的匹配成功,亦称模式t在目标s中出现;
◆ 若s[i…i+m-1]≠t[0…m-1]:从i开始的匹 配失败。位置i称为位移,当s[i…i+m1]=t[0…m-1]时,i称为有效位移;当 s[i…i+m-1] ≠t[0…m-1]时,i称为无效位移。

这样,串匹配问题可简化为找出某给定模式T在给 定目标串S中首次出现的有效位移。

算法实现
int IndexString(StringType s , StringType t , int pos )
/* 采用顺序存储方式存储主串s和模式t, 返回位置,否则返回-1 */ */

/*
/*

若模式t在主串s中从第pos位置开始有匹配的子串,*/

{ char *p , *q ; int k , j ; k=pos-1 ; j=0 ; p=s.str+pos-1 ; q=t.str ;
/* 初始匹配位置设置 */

while (k<s.length)&&(j<t.length)

{ if (*p==*q) j++ ; }

{ p++ ; q++ ; k++ ;

else { k=k-j+1 ; j=0 ; q=t.str ; p=s.str+k ; }
/* 重新设置匹配位置 */

}
if (j==t.length) return(k-t.length) ;
*/
/* 匹配,返回位置 */

else return(-1) ; }

/*

不匹配,返回-1

该算法简单,易于理解。在一些场合的应用里, 如文字处理中的文本编辑,其效率较高。 该算法的时间复杂度为O(n*m) ,其中n 、m 分别是主串和模式串的长度。通常情况下,实际运行过 程中,该算法的执行时间近似于O(n+m) 。

理解该算法的关键点
当第一次sk≠tj时:主串要退回到k-j+1的位置,而 模式串也要退回到第一个字符(即j=0的位置)。
比较出现sk≠tj时:则应该有sk-1=tj-1,…,skj+1=t1, sk-j=t0 。

4.3.2

模式匹配的一种改进算法

该改进算法是由D.E.Knuth ,J.H.Morris和 V.R.Pratt提出来的,简称为KMP算法。其改进在于:

每当一趟匹配过程出现字符不相等时,主串指示 器不用回溯,而是利用已经得到的“部分匹配”结果, 将模式串的指示器向右“滑动”尽可能远的一段距离后, 继续进行比较。

例:设有串s=“abacabab” ,t=“abab” 。则第一
次匹配过程如图4-2所示。
s=“a b cbb” || || ≠ t=“a b b” i=3 j=3 匹配失败

图4-2 模式匹配示例

在i=3和j=3时,匹配失败。但重新开始第二次 匹配时,不必从i=1 ,j=0开始。因为s1=t1,t0≠t1, 必有s1≠t0,又因为t0=t2,s2=t2,所以必有s2=t0。 由此可知,第二次匹配可以直接从i=3 、j=1开始。
总之,在主串s与模式串t的匹配过程中,一旦出现 si≠tj ,主串s的指针不必回溯,而是直接与模式串的 tk(0≦k<j进行比较,而k的取值与主串s无关,只与模 式串t本身的构成有关,即从模式串t可求得k值。)

不失一般性,设主串s=“s1s2…sn” ,模式串 t=“t1 t2 …tm” 。 当si≠tj(1≦i≦n-m,1≦j<m,m<n)时,主串s 的指针i不必回溯,而模式串t的指针j回溯到第k(k<j) 个字符继续比较,则模式串t的前k-1个字符必须满足 4-1式,而且不可能存在k’>k满足4-1式。 t1t2…tk-1= si-(k-1) si-(k-2) … si-2 si-1 (4-1) 而已经得到的 “部分匹配”的结果为: tj-(k-1) tj-k… tj-1=si-(k-1) si-(k-2) … si-2 si-1 (4-2) 由式(4-1)和式(4-2)得: t1t2…tk-1=tj-(k-1) tj-k… tj-1

i 主串s

模式串t
k
图4-3 KMP算法示例

j

定义next[j]函数为
0 当j=1时 next[j]= Max{k|1<k<j∧t1t2…tk-1=tj-(k-1) tj-k… tj-1 } 该集合不空时

1

其它情况

在求得了next[j]值之后,KMP算法的思想是:

设目标串(主串)为s,模式串为t ,并设i指针和j指 针分别指示目标串和模式串中正待比较的字符,设i和j 的初值均为1。若有si=tj,则i和j分别加1。否则,i不 变,j退回到j=next[j]的位置,再比较si和tj,若相等, 则i和j分别加1。否则,i不变,j再次退回到 j=next[j]的位置,依此类推。直到下列两种可能: (1) j退回到某个下一个[j]值时字符比较相等,则 指针各自加1继续进行匹配。 ?退回到j=0,将i和j分别加1,即从主串的下一个 字符si+1模式串的t1重新开始匹配。

KMP算法如下

#define Max_Strlen 1024 int next[Max_Strlen]; int KMP_index (StringType s , StringType t)
/* 用KMP算法进行模式匹配,匹配返回位置,否则返回-1 */ /*用静态存储方式保存字符串, s和t分别表示主串和模式串 */

{

int k=0 , j=0 ; /*初始匹配位置设置 */ while (k<s.length)&&(j<t.length { if ((j==-1)|| (s. str[k]==t.str[j])) { k++ ; j++ ; } else j=next[j] ; }

很显然,KMP_index函数是在已知下一个函数 值的基础上执行的,以下讨论如何求next函数值? 由式(4-3)知,求模式串的next[j]值与主串s 无关,只与模式串t本身的构成有关,则可把求next函 数值的问题看成是一个模式匹配问题。由next函数定 义可知:
当j=1时:next[1]=0。 设next[j]=k,即在模式串中存在:t1t2…tk1=tj-(k-1)tj-k… tj-1 ,其中下标k满足1<k<j的某 个最大值,此时求next[j+1]的值有两种可能: ⑴ 若有tk=tj :则表明在模式串中有: t1t2…tk-1tk=tj-(k-1)tj-k… tj-1 tj,且不可能存 在k’>k满足上式,即:

(2) 若有tk≠tj :则表明在模式串中有:t1 t2…tk1 tk≠tj-(k-1) tj-k… tj-1 tj ,当tk≠tj时应将模式向 右滑动至以模式中的第next[k]个字符和主串中的 第j个字符相比较。若next[k]= k’,且tj = tk’, 则说明在主串中第j+1字符之前存在一个长度为k’( 即next[k])的最长子串,与模式串中从第一个字 符起长度为k’的子串相等。即 next[j+1]=k’+1
同理,若tj≠tk,应将模式继续向右滑动至将模式 中的第next[k’]个字符和tj对齐,??,依此类推,直 到tj和模式串中的某个字符匹配成功或者不存在任何 k’(1< k’<j)满足等式:t1 t2…tk-1 tk’=tj-(k’-1) tj-k’… tj-1 tj

根据上述分析, 求next函数值的算法如下: void next(StringType t , int next[])
/* 求模式t的next串t函数值并保存在next数组中 */

{

int k=1 , j=0 ; next[1]=0; while (k<t.length) { if ((j==0)|| (t.str[k]==t.str[j])) { k++ ; j++ ; if ( t.str[k]!=t.str[j] )
next[k]=j; else next[k]=next[j];

} else next[j]=j ;
}

习 题 四
⑴ 解释下列每对术语的区别:空串和空白串;主串 和子串;目标串和模式串。
⑵ 若x和y是两个采用顺序结构存储的串,写一算法 比较这两个字符串是否相等。 ⑶ 写一算法void StrRelace(char *T, char *P, char *S),将T中第一次出现的与P相等的子串 替换为S,串S和P的长度不一定相等,并分析时间复杂 度。

第5章 数组和广义表
数组是一种人们非常熟悉的数据结构,几乎所有 的程序设计语言都支持这种数据结构或将这种数据结 构设定为语言的固有类型。数组这种数据结构可以看 成是线性表的推广。 科学计算中涉及到大量的矩阵问题,在程序设计 语言中一般都采用数组来存储,被描述成一个二维数 组。但当矩阵规模很大且具有特殊结构(对角矩阵、三 角矩阵、对称矩阵、稀疏矩阵等),为减少程序的时间 和空间需求,采用自定义的描述方式。 广义表是另一种推广形式的线性表,是一种灵活 的数据结构,在许多方面有广泛的应用。

5.1 数组的定义
数组是一组偶对(下标值,数据元素值)的集合。 在数组中,对于一组有意义的下标,都存在一个与其对 应的值。一维数组对应着一个下标值,二维数组对应着 两个下标值,如此类推。
数组是由n(n>1)个具有相同数据类型的数据元素 a1,a2,…,an组成的有序序列,且该序列必须存储在 一块地址连续的存储单元中。 ◆ 数组中的数据元素具有相同数据类型。

◆ 数组是一种随机存取结构,给定一组下标,就可 以访问与其对应的数据元素。
◆ 数组中的数据元素个数是固定的。

5.1.1 数组的抽象数据类型定义
1 抽象数据类型定义
ADT Array{
数据对象:ji= 0,1,…,bi-1 , 1,2, …,n ; D = { aj1j2…jn | n>0称为数组的维数,bi是数组第i维的 长度,ji是数组元素第i维的下标,aj1j2…jn∈ElemSet } 数据关系:R = {R1, R2, …, Rn} Ri={<aj1j2 …ji…jn , aj1j2 …ji+1…jn>|0≦jk≦bk-1 , 1≦k≦n且k≠i,0≦ji≦bi-2, aj1j2 …ji+1…jn∈D }

基本操作: ……

由上述定义知,n维数组中有b1?b2 ? … ? bn个 数据元素,每个数据元素都受到n维关系的约束。

2

直观的n维数组

以二维数组为例讨论。将二维数组看成是一个定长 的线性表,其每个元素又是一个定长的线性表。

设二维数组A=(aij)m?n,则
A=(α1,α2,…,αp) (p=m或n) 1 ≦ j≦ n 1 ≦ i ≦m

其中每个数据元素αj是一个列向量(线性表) :
αj =(a1j ,a2j ,…,amj) 或是一个行向量: αi =(ai1 ,ai2 ,…,ain) 如图5-1所示。

a11 a12 … a1n a21 a22 … a2n A= … … … … … am1 am2 … amn
(a) 矩阵表示形式

a11 a12 … a1n A= a21 a22 … a2n …………… am1 am2 … amn
列向量的一维数组形式

(b)

A=
(c)

a11 a21 ┆ am1

a12 a1n a22 ┆ a2n ┆ ┆ ┆ am2 ┆ amn

行向量的一维数组形式

图5-1 二维数组图例形式

5.2 数组的顺序表示和实现
数组一般不做插入和删除操作,也就是说,数组 一旦建立,结构中的元素个数和元素间的关系就不再发 生变化。因此,一般都是采用顺序存储的方法来表示数 组。

问题:计算机的内存结构是一维(线性)地址结构,
对于多维数组,将其存放(映射)到内存一维结构时,有 个次序约定问题。即必须按某种次序将数组元素排成一 列序列,然后将这个线性序列存放到内存中。

二维数组是最简单的多维数组,以此为例说明多维 数组存放(映射)到内存一维结构时的次序约定问题。

通常有两种顺序存储方式
⑴ 行优先顺序(Row Major Order) :将数
组元素按行排列,第i+1个行向量紧接在第i个行向量 后面。对二维数组,按行优先顺序存储的线性序列为: a11,a12,…,a1n, a21,a22,…a2n ,……, am1,am2,…,amn PASCAL、C是按行优先顺序存储的,如图52(b)示。

⑵ 列优先顺序(Column Major Order) :
将数组元素按列向量排列,第j+1个列向量紧接在第j 个列向量之后,对二维数组,按列优先顺序存储的线性 序列为:

a11 a12 … a1n a21 a22 … a2n A= … … … … … am1 am2 … amn
(a) 二维数组的表示形式

a11 a12 … a1n a21 a22



第 1 行 第 2 行

a11 a21 … am1 a12 a22



第 1 列 第 2 列

… a2n




第 m 行

… am2




第 n 列

am1 am2 … Amn

a1m a2m … amn

图5-2 二维数组及其顺序存储图例形式





(b) 行优先顺序存储

(c) 列优先顺序存储

设有二维数组A=(aij)m?n,若每个元素占用的存储 单元数为l(个),LOC[a11]表示元素a11的首地址,即 数组的首地址。

1

以“行优先顺序”存储
⑴ 第1行中的每个元素对应的(首)地址是: LOC[a1j]=LOC[a11]+(j-1)?l j=1,2, …,n (2) 第2行中的每个元素对应的(首)地址是: LOC[a2j]=LOC[a11]+n?l +(j-1)?l j=1,2, …,n ………

⑶ 第m行中的每个元素对应的(首)地址是:

由此可知,二维数组中任一元素aij的(首)地址是: LOC[aij]=LOC[a11]+[(i-1)?n +(j-1)]?l (5-1)

i=1,2, …,m

j=1,2, …,n

根据(5-1)式,对于三维数组A=(aijk)m?n?p, 若每个元素占用的存储单元数为l(个),LOC[a111]表 示元素a111的首地址,即数组的首地址。以“行优先顺 序”存储在内存中。

三维数组中任一元素aijk的(首)地址是:
LOC(aijk)=LOC[a111]+[(i-1)?n?p+(j1)?p+(k-1)]?l (5-2)

推而广之,对n维数组A=(aj1j2…jn) ,若每个元 素占用的存储单元数为l(个),LOC[a11 …1]表示元素

n维数组中任一元素aj1j2…jn的(首)地址是:
LOC[aj1j2…jn]=LOC[a11 …1]+[(b2?…?bn)?(j1-1) + (b3?…?bn)?(j2-1)+ … + bn?(jn-1-1)+ (jn-1)] ?l

(5-3)

2

以“列优先顺序”存储
⑴ 第1列中的每个元素对应的(首)地址是:
LOC[aj1]=LOC[a11]+(j-1)?l j=1,2, …,m (2) 第2列中的每个元素对应的(首)地址是: LOC[aj2]=LOC[a11]+m?l +(j-1)?l j=1,2, …,m ……… ⑶ 第n列中的每个元素对应的(首)地址是: LOC[ajn]=LOC[a11]+ (n-1)?m?l +(j1)?l j=1,2, …,m

由此可知,二维数组中任一元素aij的(首)地址是:

5.3 矩阵的压缩存储
在科学与工程计算问题中,矩阵是一种常用的数 学对象,在高级语言编程时,通常将一个矩阵描述为一 个二维数组。这样,可以对其元素进行随机存取,各种 矩阵运算也非常简单。
对于高阶矩阵,若其中非零元素呈某种规律分布或 者矩阵中有大量的零元素,若仍然用常规方法存储,可 能存储重复的非零元素或零元素,将造成存储空间的大 量浪费。对这类矩阵进行压缩存储: ◆ 多个相同的非零元素只分配一个存储空间; ◆ 零元素不分配空间。

5.3.1 特殊矩阵
特殊矩阵:是指非零元素或零元素的分布有一定规律
的矩阵。

1

对称矩阵

若一个n阶方阵A=(aij)n?n中的元素满足性质: aij=aji 1≦i,j≦n且i≠j 则称A为对称矩阵,如图5-3所示。
1 5 A= 1 3 7 5 0 8 0 0 1 8 9 2 6 3 0 2 5 1 7 0 6 1 3 a11 a21 a22 A= a31 a32 a33 ……… … an1 an2 … ann

图5-3 对称矩阵示例

对称矩阵中的元素关于主对角线对称,因此,让 每一对对称元素aij和aji(i≠j)分配一个存储空间,则 n2个元素压缩存储到n(n+1)/2个存储空间,能节约 近一半的存储空间。

不失一般性,假设按“行优先顺序”存储下三角 形(包括对角线)中的元素。
设用一维数组(向量)sa[0…n(n+1)/2]存储n 阶对称矩阵,如图5-4所示。为了便于访问,必须找出 矩阵A中的元素的下标值(i,j)和向量sa[k]的下标值 k之间的对应关系。
K 1
sa

2

3

4



n(n-1)/2 … n(n+1)/2

a11 a21 a22 a31 a32 a33 … an1 an2 … ann
图5-4 对称矩阵的压缩存储示例

若i≧j:ai j在下三角形中,直接保存在sa中。ai j之 前的i-1行共有元素个数: 1+2+…+(i-1)=i?(i-1)/2
而在第i行上,ai j之前恰有j-1个元素,因此,元素ai j保 存在向量sa中时的下标值k之间的对应关系是: k=i?(i-1)/2+j-1 i≧j

若i<j:则aij是在上三角矩阵中。因为aij=aji,在向 量sa中保存的是aji 。依上述分析可得:
k=j?(j-1)/2+i-1 i<j 对称矩阵元素ai j保存在向量sa中时的下标值k与 (i,j)之间的对应关系是:
K=

i?(i-1)/2+j-1 j?(j-1)/2+i-1

当 i≧ j 时 当i<j时

1≦i,j≦ n

(5-4)

根据上述的下标对应关系,对于矩阵中的任意元 素aij,均可在一维数组sa中唯一确定其位置k;反之, 对所有k=1,2, …,n(n+1)/2,都能确定sa[k]中的元素在矩 阵中的位置(i,j)。

称sa[0…n(n+1)/2]为n阶对称矩阵A的压缩存储。

2

三角矩阵
以主对角线划分,三角矩阵有上三角和下三角两

种。 上三角矩阵的下三角(不包括主对角线)中的元 素均为常数c(一般为0)。下三角矩阵正好相反,它的主 对角线上方均为常数,如图5-5所示。

a11 a12 … a1n
c a22 … a2n … … … c c … ann
(a) 上三角矩阵示例

a11 c … c
a21 a22 … c … … … an1 an2 … ann
(b) 下三角矩阵示例

图5-5 三角矩阵示例

三角矩阵中的重复元素c可共享一个存储空间,其 余的元素正好有n(n+1)/2个,因此,三角矩阵可压缩存 储到向量sa[0…n(n+1)/2]中,其中c存放在向量的第1个 分量中。 上三角矩阵元素ai j保存在向量sa中时的下标值k与 (i,j)之间的对应关系是:

K=

i?(i-1)/2+j-1

当 i≧ j 时

n?(n+1)/2

1≦i,j≦ n

当i<j时

(5-5)

下三角矩阵元素ai j保存在向量sa中时的下标值k与 (i,j)之间的对应关系是: K= i?(i-1)/2+j-1 当 i≦ j 时

n?(n+1)/2

当i>j时

1≦i,j≦n

(5-6)

3

对角矩阵

矩阵中,除了主对角线和主对角线上或下方若干 条对角线上的元素之外,其余元素皆为零。即所有的非 零元素集中在以主对角线为了中心的带状区域中,如图 5-6所示。

a11 a12 0 …. 0 a21 a22 a23 0 …. 0 0 a32 a33 a34 0 …. 0 … … … …. 0 …. 0 …. 0 an-1 n-2 an-1 n-1 an-1 n 0 0 an n-1 an n

A=

图5-6 三对角矩阵示例

如上图三对角矩阵,非零元素仅出现在主对角(ai i,1≦i≦n)上、主对角线上的那条对角线(ai i+1,1≦i≦n1) 、主对角线下的那条对角线上(ai+1 i,1≦i≦n-1)。 显然,当| i-j |>1时,元素aij=0。

由此可知,一个k对角矩阵(k为奇数)A是满足下述 条件: 当| i-j |>(k-1)/2时, ai j=0

对角矩阵可按行优先顺序或对角线顺序,将其压缩 存储到一个向量中,并且也能找到每个非零元素和向量 下标的对应关系。 仍然以三对角矩阵为例讨论。

当i=1,j=1、2,或i=n, j=n-1、n或
1<i<n-1,j=i-1、i、i+1的元素aij外,其余元素都 是 0。 对这种矩阵,当以按“行优先顺序”存储时, 第 1行和第n行是2个非零元素,其余每行的非零元素都要 是3个,则需存储的元素个数为 3n-2 。 K 1 2 3 4 5 6 7 8 … 3n-3 3n-2
sa
a11 a12 a21 a22 a23 a32 a33 a34 … an n-1 ann
图5-7 三对角矩阵的压缩存储示例

如图5-7所示三对角矩阵的压缩存储形式。数组sa 中的元素sa[k]与三对角矩阵中的元素aij存在一一对应关 系,在aij之前有i-1行,共有3?i-1个非零元素,在第i行, 有j-i+1个非零元素,这样,非零元素aij的地址为:

LOC[ai j] =LOC[a11] +[3?i-1+(j-i+1)]?l
=LOC[a11]+(2?i+j)?l 上例中,a34对应着sa[10] , k=2?i+j=2?3+4=10

称sa[0…3?n-2]是n阶三对角矩阵A的压缩存储。
上述各种特殊矩阵,其非零元素的分布都是有规律 的,因此总能找到一种方法将它们压缩存储到一个向量 中,并且一般都能找到矩阵中的元素与该向量的对应关 系,通过这个关系,仍能对矩阵的元素进行随机存取。

5.3.2

稀疏矩阵

稀疏矩阵(Sparse Matrix):对于稀疏矩阵,目前还
没有一个确切的定义。设矩阵A是一个n?m的矩阵中有 s个非零元素,设 δ=s/(n?m),称δ为稀疏因子,如果 某一矩阵的稀疏因子δ满足δ≦0.05时称为稀疏矩阵,如 图5-8所示。
0 12 0 0 -3 0 9 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4

A= 0 0 24 0 0 2 0 0
0 18 0 0 0 0 0 0 0 0 0 0 0 0 -7 0 0 0 0 -6 0 0 0 0
图5-8 稀疏矩阵示例

5.3.2.1

稀疏矩阵的压缩存储

对于稀疏矩阵,采用压缩存储方法时,只存储非0 元素。必须存储非0元素的行下标值、列下标值、元素 值。因此,一个三元组(i, j, aij)唯一确定稀疏矩阵的一 个非零元素。

如图5-8的稀疏矩阵A的三元组线性表为:
( (1,2,12), (1,3,9), (3,1,-3), (3,8,4), (4,3,24), (5,2,18), (6,7,-7), (7,4,-6) )

1 三元组顺序表
若以行序为主序,稀疏矩阵中所有非0元素的三元组, 就可以得构成该稀疏矩阵的一个三元组顺序表。

1

三元组顺序表

若以行序为主序,稀疏矩阵中所有非0元素的三元 组,就可以得构成该稀疏矩阵的一个三元组顺序表。 相应的数据结构定义如下:

⑴ 三元组结点定义
#define MAX_SIZE 101 typedef int elemtype ; typedef struct { int row ;
/* 行下标 */

int col ;
}Triple ;

/* 列下标 */
/* 元素值 */

elemtype value;

⑵ 三元组顺序表定义
typedef struct

{

int rn ;
int cn ; int tn ; Triple

/*
/* /*

行数
列数

*/
*/ */

非0元素个数

data[MAX_SIZE] ;

}TMatrix ;

图5-8所示的稀疏矩阵及其相应的转置矩阵所对应 的三元组顺序表如图5-9所示。

7 8 9 1 1 3 3 4 4 5 6 7

rn行数 cn列数 tn元素个数 2 12 3 9 1 -3 8 4 3 24 6 2 2 18 7 -7 4 -6

8 7 9 1 2 2 3 3 4 6 7 8

rn行数 cn列数 tn元素个数 3 -3 1 12 5 18 1 9 4 24 7 -6 4 2 6 -7 2 4

row col value
(a) 原矩阵的三元组表

row col value
(b)转置矩阵的三元组表

图5-9 稀疏矩阵及其转置矩阵的三元组顺序表

矩阵的运算包括矩阵的转置、矩阵求逆、矩阵的加 减、矩阵的乘除等。在此,先讨论在这种压缩存储结构 下的求矩阵的转置的运算。

一个m?n的矩阵A,它的转置B是一个n?m的矩阵, 且b[i][j]=a[j][i],0≦i≦n,0≦j≦m,即B的行是A的列, B的列是A的行。 设稀疏矩阵A是按行优先顺序压缩存储在三元组表 a.data中,若仅仅是简单地交换a.data中i和j的内容,得 到三元组表b.data,b.data将是一个按列优先顺序存储 的稀疏矩阵B,要得到按行优先顺序存储的b.data,就 必须重新排列三元组表b.data中元素的顺序。

求转置矩阵的基本算法思想是:
① 将矩阵的行、列下标值交换。即将三元组表中的 行、列位置值i 、j相互交换; ② 重排三元组表中元素的顺序。即交换后仍然是按 行优先顺序排序的。

方法一:
算法思想:按稀疏矩阵A的三元组表a.data中的列次
序依次找到相应的三元组存入b.data中。
每找转置后矩阵的一个三元组,需从头至尾扫描 整个三元组表a.data 。找到之后自然就成为按行优先 的转置矩阵的压缩存储表示。

按方法一求转置矩阵的算法如下: void TransMatrix(TMatrix a , TMatrix b) { int p , q , col ;

b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ;
/* 置三元组表b.data的行、列数和非0元素个数 */

if (b.tn==0) else { q=0;

printf(“ The Matrix A=0\n” );

for (col=1; col<=a.cn ; col++)
/* 每循环一次找到转置后的一个三元组 */

for (p=0 ;p<a.tn ; p++)
/* 循环次数是非0元素个数 */

if (a.data[p].col==col)

{ b.data[q].row=a.data[p].col ;
b.data[q].col=a.data[p].row ;

b.data[q].value=a.data[p].value;
q++ ; } } }

算法分析:本算法主要的工作是在p和col的两个循

而一般传统矩阵的转置算法为:

for(col=1; col<=n ;++col)
for(row=0 ; row<=m ;++row) b[col][row]=a[row][col] ; 其时间复杂度为O(n?m)。当非零元素的个数tn 和m?n同数量级时,算法TransMatrix的时间复杂度 为O(m?n2)。 由此可见,虽然节省了存储空间,但时间复杂度却 大大增加。所以上述算法只适合于稀疏矩阵中非0元素 的个数tn远远小于m?n的情况。

方法二(快速转置的算法)
算法思想:直接按照稀疏矩阵A的三元组表a.data的
次序依次顺序转换,并将转换后的三元组放置于三元组 表b.data的恰当位置。

前提:若能预先确定原矩阵A中每一列的(即B中
每一行)第一个非0元素在b.data中应有的位置,则在 作转置时就可直接放在b.data中恰当的位置。因此, 应先求得A中每一列的非0元素个数。 附设两个辅助向量num[ ]和cpot[ ] 。
◆ num[col]:统计A中第col列中非0元素的个 数; ◆ cpot[col] :指示A中第一个非0元素在

显然有位置对应关系:
cpot[1]=1

cpot[col]=cpot[col-1]+num[col-1]

2≦col≦a.cn

例图5-8中的矩阵A和表5-9(a)的相应的三元组表可 以求得num[col]和cpot[col]的值如表5-1:
表5-1 num[col]和cpot[col]的值表

col 1 2 3 4 5 6 7 8 num[col] 1 2 2 1 0 1 1 1 cpot[col] 1 3 5 6 6 7 8 9

快速转置算法如下:
void FastTransMatrix(TMatrix a, TMatrix b) { int p , q , col , k ; int num[MAX_SIZE] , copt[MAX_SIZE] ; b.rn=a.cn ; b.cn=a.rn ; b.tn=a.tn ;
/* */ 置三元组表b.data的行、列数和非0元素个数

if (b.tn==0) printf(“ The Matrix A=0\n” ) ; else { for (col=1 ; col<=a.cn ; ++col) num[col]=0 ;

for (cpot[0]=1, col=2 ; col<=a.cn ; ++col)
cpot[col]=cpot[col1]+num[col-1] ;
/* 求第col列中第一个非0元在b.data中的 序号 */

for (p=1 ; p<=a.tn ; ++p) { col=a.data[p].col ; q=cpot[col] ; b.data[q].row=a.data[p].col ;

b.data[q].col=a.data[p].row ;
b.data[q].value=a.data[p].value ;

2

行逻辑链接的三元组顺序表

将上述方法二中的辅助向量cpot[ ]固定在稀疏矩阵 的三元组表中,用来指示“行”的信息。得到另一种 顺序存储结构:行逻辑链接的三元组顺序表。其类型 描述如下: #define MAX_ROW 100 typedef struct { Triple data[MAX_SIZE] ; int rpos[MAX_ROW];
/* 非0元素的三元组表 */ /* 各行第一个非0位置表 */

int

rn ,cn , tn ;

/* 矩阵的行、列数和非0元个数 */

}RLSMatrix ;

稀疏矩阵的乘法
设有两个矩阵:A=(aij)m?n ,B=(bij)n?p 则: C=(cij)m?p 其中 cij=∑aik?bkj 1≦k≦n , 1≦i≦m ,1≦j≦p 经典算法是三重循环: for ( i=1 ; i<=m ; ++i) for ( j=1 ; j<=p ; ++j) { c[i][j]=0 ; for ( k=1 ; k<=n ; ++k) c[i][j]= c[i][j]+a[i][k]?b[k][j]; } 此算法的复杂度为O(m?n?p)。

设有两个稀疏矩阵A=(aij)m?n ,B=(bij)n?p ,其 存储结构采用行逻辑链接的三元组顺序表。

算法思想:对于A中的每个元素a.data[p](p=1,
2, … , a.tn),找到B中所有满足条件: a.data[p].col=b.data[q].row的元素 b.data[q],求得 a.data[p].value?b.data[q].value,该乘积是cij 中的一部分。求得所有这样的乘积并累加求和就能得到 cij。 为得到非0的乘积,只要对a.data[1…a.tn] 中 每个元素(i,k,aik)(1≦i≦a.rn,1≦k≦a.cn) ,找到 b.data中所有相应的元素(k,j,bkj)(1≦k≦b.rn, 1≦j≦b.cn) 相乘即可。则必须知道矩阵B中第k行的所

b.rpos[row]指示了矩阵B的第row行中第一 个非0元素在b.data[ ]中的位置(序号),显然, b.rpos[row+1]-1指示了第row行中最后一个非0 元素在b.data[ ]中的位置(序号) 。最后一行中最后 一个非0元素在b.data[ ]中的位置显然就是b.tn 。
两个稀疏矩阵相乘的算法如下: void MultsMatrix(RLSMatrix a, RLSMatrix b, RLSMatrix c)
/* 求矩阵A 、B的积C=A?B,采用行逻辑链接的顺序表 */

{

elemtype ctemp[Max_Size] ;

int p , q , arow , ccol , brow , t ;
if (a.cn!=b.rn) { printf(“Error\n”) ;

else
{

c.rn=a.rn ; c.cn=b. n ; c.tn=0 ; if (a.tn*b.tn!=0)
*/ /* C 是非零矩阵

/*

初始化C */

{ for (arow=1 ; arow<=a.rn ; ++arow)

{
加器清零

ctemp[arow]=0 ; /* 当前行累
*/

c.rpos[arow]=c.tn+1; p=a.rops[arow]; for ( ; p<a.rpos[arow+1];++p)

for (q=b.rpos[brow] ; q<t ; ++q)

{ ccol=b.data[q].col ;
/* 积元素在c中的列号 */

ctemp[ccol]+=a.data[p].value*b.d ata[q].value ; }

}

/* 求出c中第arow行中的非0元素

*/

for (ccol=1 ; ccol<=c.cn ; ++ccol) if ( ctemp[ccol] !=0 ) { if ( ++c.tn>MAX_SIZE) { printf(“Error\n”) ; exit(0); }

c.data[c.tn]=(arow , ccol , ctemp[ccol]) ; } }

}
}

3

十字链表

对于稀疏矩阵,当非0元素的个数和位置在操作过 程中变化较大时,采用链式存储结构表示比三元组的 线性表更方便。

矩阵中非0元素的结点所含的域有:行、列、值、 行指针(指向同一行的下一个非0元)、列指针(指向同一 列的下一个非0元)。其次,十字交叉链表还有一个头结 点,结点的结构如图5-10所示。
row col value down right
(a) 结点结构

rn cn tn down right
(b) 头结点结构

图5-10 十字链表结点结构

由定义知,稀疏矩阵中同一行的非0元素的由 right指针域链接成一个行链表, 由down指针域链接 成一个列链表。则每个非0元素既是某个行链表中的一 个结点,同时又是某个列链表中的一个结点,所有的非 0元素构成一个十字交叉的链表。称为十字链表。
此外,还可用两个一维数组分别存储行链表的头指 针和列链表的头指针。对于图5-11(a)的稀疏矩阵A , 对应的十字交叉链表如图5-11(b)所示,结点的描述 如下: typedef struct Clnode { int row , col ; /* 行号和列号 */ elemtype value ; /* 元素值 */ struct Clnode *down , *right ;

typedef struct Clnode { int rn; /* 矩阵的
行数 */

int
int

数 */

cn;

/* 矩阵的列
/* 非0元素

A.chead

A.rchead ?

?

总数 */

tn;

1 2 12 ? 2 5 -4 ? ? 32 5 ? ?

OLNode *rhead ; OLNode *chead 0 12 0 0 0; 0 0 ; 0 0 -4 } CrossList A=
0 0 5 0 0 3 0 0 0 0
(a) 稀疏矩阵

43 3 ? ?
(b) 稀疏矩阵的十字交叉链表

图5-11 稀疏矩阵及其十字交叉链表

5.4 广义表
广义表是线性表的推广和扩充,在人工智能领域 中应用十分广泛。 在第2章中,我们把线性表定义为n(n≧0 )个元 素a1, a2 ,…, an的有穷序列,该序列中的所有元素具 有相同的数据类型且只能是原子项(Atom)。所谓原子 项可以是一个数或一个结构,是指结构上不可再分的。 若放松对元素的这种限制,容许它们具有其自身结构, 就产生了广义表的概念。

广义表(Lists,又称为列表 ):是由n(n
≧0)个元素组成的有穷序列: LS=(a1,a2,…,an)

其中ai或者是原子项,或者是一个广义表。LS是广 义表的名字,n为它的长度。若ai是广义表,则称为 LS的子表。
习惯上:原子用小写字母,子表用大写字母。 若广义表LS非空时:

◆ a1(表中第一个元素)称为表头;
◆ 其余元素组成的子表称为表尾;(a2,a3,…, a n) ◆ 广义表中所包含的元素(包括原子和子表)的个数 称为表的长 度。

◆ 广义表中括号的最大层数称为表深 (度)。
有关广义表的这些概念的例子如表5-2所示。

表5-2

广义表及其示例

D A B C 0 1 2 3 ∞ 2

广 义 表 表长n 表深h
A=() B=(e) C=(a,(b,c, d)) D=(A,B,C) E=(a,E) F=(()) 0 1 2 3 2 1

e a
b c

d

图5-12 广义表的图形表示

广义表的重要结论:
⑴ 广义表的元素可以是原子,也可以是子表,子表 的元素又可以是子表, …。即广义表是一个多层次 的结构。 表5-2中的广义表D的图形表示如图5-12所示。 (2) 广义表可以被其它广义表所共享,也可以共享其 它广义表。广义表共享其它广义表时通过表名引用。 (3) 广义表本身可以是一个递归表。

(4) 根据对表头、表尾的定义,任何一个非空广义表 的表头可以是原子,也可以是子表, 而表尾必定是 广义表。

5.4.1 广义表的存储结构
由于广义表中的数据元素具有不同的结构,通常 用链式存储结构表示,每个数据元素用一个结点表示。 因此,广义表中就有两类结点:
◆ 一类是表结点,用来表示广义表项,由标志域, 表头指针域,表尾指针域组成;

◆ 另一类是原子结点,用来表示原子项,由标志域, 原子的值域组成。如图5-13所示。
只要广义表非空,都是由表头和表尾组成。即一 个确定的表头和表尾就唯一确定一个广义表。

标志tag=0 原子的值
(a) 原子结点

标志tag=1 表头指针hp
(b) 表结点

表尾指针tp

图5-13 广义表的链表结点结构示意图

相应的数据结构定义如下: typedef struct GLNode { int tag ; /* 标志域,为1:表结点;为0 :原子结点 */ union { elemtype value; /* 原子结点的值域 */ struct { struct GLNode *hp , *tp ; }ptr ; /* ptr和atom两成员共用 */ }Gdata ; } GLNode ; /* 广义表结点类型 */

例: 对A=(),B=(e),C=(a, (b, c, d) ),D=(A, B, C), E=(a, E)的广义表的存储结构如图5-14所示。
A=NULL B 1 C 1 0 a ∧ 0 e 1 1 0 b D 1 ∧ 1 1 ∧ 1 E

1 0 a

1



1



0 c
1 ∧

0 d

图5-14 广义表的存储结构示意图

对于上述存储结构,有如下几个特点:
(1) 若广义表为空,表头指针为空;否则,表头指 针总是指向一个表结点,其中hp指向广义表的表头 结点(或为原子结点,或为表结点) ,tp指向广义表 的表尾(表尾为空时,指针为空,否则必为表结点)。

(2) 这种结构求广义表的长度、深度、表头、表尾 的操作十分方便。
(3) 表结点太多,造成空间浪费。也可用图5-15所 示的结点结构。
tag=0 原子的值 表尾指针tp
(a) 原子结点

tag=1 表头指针hp 表尾指针tp
(b) 表结点

图5-15 广义表的链表结点结构示意图

习题五
⑴ 什么是广义表?请简述广义表与线性表的区别?

⑵ 一个广义表是(a, (a, b), d, e, (a, (i, j), k)) ,请画出该广义表的链式存储结构。
⑶ 设有二维数组a[6][8],每个元素占相邻的4个 字节,存储器按字节编址,已知a的起始地址是1000, 试计算: ① 数组a的最后一个元素a[5][7]起始地址; ② 按行序优先时,元素a[4][6]起始地址; ③ 按行序优先时,元素a[4][6]起始地址。

⑷ 设A和B是稀疏矩阵,都以三元组作为存储结构, 请写出矩阵相加的算法,其结果存放在三元组表C中, 并分析时间复杂度。 ⑸ 设有稀疏矩阵B如下图所示,请画出该稀疏矩阵 的三元组表和十字链表存储结构。
0 3 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -3 0 0 18 0 0 0 0 0 0 0 0 0 0 4 0

A= 0 0 2 0 0 2 0 0
0 0 0 0 4 0 5 0 0 0 -3 0 0 0 0 0

第6章 树和二叉树
树型结构是一类非常重要的非线性结构。直观地, 树型结构是以分支关系定义的层次结构。 树在计算机领域中也有着广泛的应用,例如在编 译程序中,用树来表示源程序的语法结构;在数据库系 统中,可用树来组织信息;在分析算法的行为时,可用 树来描述其执行过程等等。 本章将详细讨论树和二叉树数据结构,主要介绍 树和二叉树的概念、术语,二叉树的遍历算法。树和二 叉树的各种存储结构以及建立在各种存储结构上的操作 及应用等。

6.1 树的基本概念
6.1.1 树的定义和基本术语
1 树的定义
树(Tree)是n(n≧0)个结点的有限集合T,若n=0 时称为空树,否则: ⑴ 有且只有一个特殊的称为树的根(Root)结点; ⑵ 若n>1时,其余的结点被分为m(m>0)个互不 相交的子集T1, T2, T3…Tm,其中每个子集本身又 是一棵树,称其为根的子树(Subtree)。 这是树的递归定义,即用树来定义树,而只有一个 结点的树必定仅由根组成,如图6-1(a)所示。

2 树的基本术语
⑴ 结点(node):一个数据元素及其若干指向其
子树的分支。

⑵ 结点的度(degree) 、树的度:结点所拥有
的子树的棵数称为结点的度。树中结点度的最大值称 为树的度。
A B A
(a) 只有根结点

C F G

D H I N J

E K L

M

图6-1 树的示例形式

(b) 一般的树

如图6-1(b)中结点A的度是3 ,结点B的度是2 ,结点 M的度是0,树的度是3 。

⑶ 叶子(left)结点、非叶子结点:树中度为0的
结点称为叶子结点(或终端结点)。相对应地,度不为 0的结点称为非叶子结点(或非终端结点或分支结点)。 除根结点外,分支结点又称为内部结点。 如图6-1(b)中结点H、I、J、K、L、M、N是叶子 结点,而所有其它结点都是分支结点。

⑷ 孩子结点、双亲结点、兄弟结点
一个结点的子树的根称为该结点的孩子结点(child) 或子结点;相应地,该结点是其孩子结点的双亲结点 (parent)或父结点。

如图6-1(b)中结点B 、C、D是结点A的子结点,而 结点A是结点B 、C、D的父结点;类似地结点E 、F是 结点B的子结点,结点B是结点E 、F的父结点。
同一双亲结点的所有子结点互称为兄弟结点。 如图6-1(b)中结点B 、C、D是兄弟结点;结点E 、 F是兄弟结点。

⑸ 层次、堂兄弟结点
规定树中根结点的层次为1,其余结点的层次等于 其双亲结点的层次加1。 若某结点在第l(l≧1)层,则其子结点在第l+1层。

双亲结点在同一层上的所有结点互称为堂兄弟结点。 如图6-1(b)中结点E、F、G、H、I、J。

⑹ 结点的层次路径、祖先、子孙
从根结点开始,到达某结点p所经过的所有结点成 为结点p的层次路径(有且只有一条)。 结点p的层次路径上的所有结点(p除外)称为p的 祖先(ancester) 。

以某一结点为根的子树中的任意结点称为该结点的 子孙结点(descent)。

⑺ 树的深度(depth):树中结点的最大层次值,又
称为树的高度,如图6-1(b)中树的高度为4。

⑻ 有序树和无序树:对于一棵树,若其中每一个
结点的子树(若有)具有一定的次序,则该树称为有 序树,否则称为无序树。

⑼ 森林(forest):是m(m≧0)棵互不相交的树的集
合。显然,若将一棵树的根结点删除,剩余的子树就 构成了森林。

3 树的表示形式
⑴ 倒悬树。是最常用的表示形式,如图6-1(b)。 ⑵ 嵌套集合。是一些集合的集体,对于任何两个
集合,或者不相交,或者一个集合包含另一个集合。 图6-2(a)是图6-1(b)树的嵌套集合形式。

⑶ 广义表形式。图6-2(b)是树的广义表形式。

⑷ 凹入法表示形式。见P120
树的表示方法的多样化说明了树结构的重要性。

A

D H J I

E
(A(B(E(K,L),F),C(G(M,N)),D(H,I,J)
(b) 广义表形式

B
F

K L

C G M N

(a) 嵌套集合形式 图6-2 树的表示形式

定义
ADT Tree{
数据对象D:D是具有相同数据类型的数据元素的集 合。 数据关系R:若D为空集,则称为空树; ……

基本操作:
…… } ADT Tree 详见p118~119。

6.2
1 二叉树的定义

二叉树

6.2.1 二叉树的定义
二叉树(Binary tree)是n(n≥0)个结点的有限 集合。若n=0时称为空树,否则:
⑴ 有且只有一个特殊的称为树的根(Root)结点; ⑵ 若n>1时,其余的结点被分成为二个互不相交的 子集T1,T2,分别称之为左、右子树,并且左、右子 树又都是二叉树。 由此可知,二叉树的定义是递归的。

二叉树在树结构中起着非常重要的作用。因为二叉 树结构简单,存储效率高,树的操作算法相对简单,且 任何树都很容易转化成二叉树结构。上节中引入的有关 树的术语也都适用于二叉树。

2

二叉树的基本形态
二叉树有5种基本形态,如图6-3所示。
A A (a) (b)
(d) 左子树为空

A

A

(c)

(d)
(c) 右子树为空

(e)

(a) 空二叉树

(b) 单结点二叉树

(e) 左、右子树都不空

图6-3 二叉树的基本形态

性质1:在非空二叉树中,第i层上至多有2i-1个结点
(i≧1)。



证明:用数学归纳法证明。
当i=1时:只有一个根结点,21-1=20 =1,命题成 立。 现假设对i>1时,处在第i-1层上至多有2(i-1)-1个 结点。
由归纳假设知,第i-1层上至多有2i-2个结点。由于 二叉树每个结点的度最大为2,故在第i层上最大结点 数为第i-1层上最大结点数的2倍。 即 2×2i-2=2i-1
k

证毕

证明:深度为k的二叉树的最大的结点数为二叉树中每
层上的最大结点数之和。

由性质1知,二叉树的第1层、第2层?第k层上的 结点数至多有: 20、21 …2k-1 。

∴ 总的结点数至多有: 20+21+ …+2k-1=2k-1
证毕

性质3:对任何一棵二叉树,若其叶子结点数为n0,
度为2的结点数为n2,则n0=n2+1。

证明:设二叉树中度为1的结点数为n1,二叉树中总
结点数为N,因为二叉树中所有结点均小于或等于2, 则有:N=n0+n1+n2 再看二叉树中的分支数:

除根结点外,其余每个结点都有唯一的一个进入分 支,而所有这些分支都是由度为1和2的结点射出的。 设B为二叉树中的分支总数,则有: N=B+1

∴ ∴ ∴


B=n1+2?n2 N=B+1=n1+2?n2+1 n0+n1+n2=n1+2?n2+1 n0=n2+1

证毕

满二叉树和完全二叉树
一棵深度为k且有2k-1个结点的二叉树称为满二 叉树(Full Binary Tree)。
如图6-4(a) 就是一棵深度为4的满二叉树。

1 2 3 2

1
3

4
8 9 10

5
11 1 2 4 5 3 12

6 13 14

7
15 8

4
9 1 2 3 10

5
11 12

6

7

(a) 满二叉树

(b) 完全二叉树

6

4 6

5
7

(c) 非完全二叉树

图6-4 特殊形态的二叉树

满二叉树的特点:
◆ 基本特点是每一层上的结点数总是最大结点数。

◆ 满二叉树的所有的支结点都有左、右子树。
◆ 可对满二叉树的结点进行连续编号,若规定从根 结点开始,按“自上而下、自左至右”的原则进行。 完全二叉树(Complete Binary Tree):如果深度为 k,由n个结点的二叉树,当且仅当其每一个结点都与 深度为k的满二叉树中编号从1到n的结点一一对应,该 二叉树称为完全二叉树。 或深度为k的满二叉树中编号从1到n的前n个结点 构成了一棵深度为k的完全二叉树。 其中 2k-1 ≦ n≦2k-1 。

完全二叉树是满二叉树的一部分,而满二叉树是完 全二叉树的特例。

完全二叉树的特点:
若完全二叉树的深度为k ,则所有的叶子结点都出现 在第k层或k-1层。对于任一结点,如果其右子树的最 大层次为l,则其左子树的最大层次为l或l+1。

性质4:n个结点的完全二叉树深度为:?㏒2n? +1。
其中符号: ?x?表示不大于x的最大整数。
?x? 表示不小于x的最小整数。

证明:假设完全二叉树的深度为k,则根据性质2及完
全二叉树的定义有:

2k-1-1<n≦2k-1 ∴



2

k-1

≦n<2k 因为k是整数。 证毕

取对数得:k-1<㏒2n<k k= ?㏒2n? +1

性质5:若对一棵有n个结点的完全二叉树(深度为└㏒
2n┘+1)的结点按层(从第1层到第?㏒2n?

+1层)序自左 至右进行编号,则对于编号为i(1≦i≦n)的结点:
⑴ 若i=1:则结点i是二叉树的根,无双亲结点; 否则,若i>1,则其双亲结点编号是 ?i/2? 。 ⑵ 如果2i>n:则结点i为叶子结点,无左孩子;否 则,其左孩子结点编号是2i。 ⑶ 如果2i+1>n:则结点i无右孩子;否则,其右 孩子结点编号是2i+1。

证明:用数学归纳法证明。首先证明⑵和⑶,然后
由⑵和⑶导出⑴。

当i=1时,由完全二叉树的定义知,结点i的左孩 子的编号是2,右孩子的编号是3。
若2>n,则二叉树中不存在编号为2的结点,说明结 点i的左孩子不存在。 若3>n,则二叉树中不存在编号为3的结点,说明结 点i的右孩子不存在。 即:

现假设对于编号为j(1≦j≦i)的结点,(2)和(3)成立。

◆ 当2j≦n :结点j的左孩子编号是2j;当2j>n时, 结点j的左孩子结点不存在。

◆ 当2j+1≦n :结点j的右孩子编号是2j+1;当 2j+1>n时,结点j的右孩子结点不存在。 当i=j+1时,由完全二叉树的定义知,若结点i的左 孩子结点存在,则其左孩子结点的编号一定等于编号 为j的右孩子的编号加1,即结点i的左孩子的编号为: (2j+1)+1=2(j+1)=2i

如图6-5所示,且有2i≦n。相反,若2i>n,则左孩子结 点不存在。同样地,若结点i的右孩子结点存在,则其 右孩子的编号为:2i+1,且有2i+1≦n。相反,若 2i+1>n,则左孩子结点不存在。结论(2)和(3)得证。
再由(2)和(3)来证明(1) 。

当i=1时,显然编号为1的是根结点,无双亲结点。

└i/2┘


i+1 i+1 … 2i+3 2i

i 2i+1

i
2i 2i+1

2i+2

2i+2

2i+3

(a) i和i+1结点在同一层

(b) i和i+1结点不在同一层

图6-5 完全二叉树中结点i和i+1的左右孩子

当i>1时,设编号为i的结点的双亲结点的编号为 m,若编号为i的结点是其双亲结点的左孩子,则由 (2)有:
i=2m ,即m=?i/2? ; 若编号为i的结点是其双亲结点的右孩子,则由(3)有:

i=2m+1 ,即m=?(i-1) /2? ;

结构
1 顺序存储结构
二叉树存储结构的类型定义: #define MAX_SIZE 100

typedef telemtype sqbitree[MAX_SIZE];
用一组地址连续的存储单元依次“自上而下、自左 至右”存储完全二叉树的数据元素。 对于完全二叉树上编号为i的结点元素存储在一维 数组的下标值为i-1的分量中,如图6-6(c)所示。

对于一般的二叉树,将其每个结点与完全二叉树上 的结点相对照,存储在一维数组中,如图6-6(d)所示。

a b c b g ?

a c

d

e i
j k

f

d
? f

e
g

?

h

h

l

(a) 完全二叉树

(b) 非完全二叉树

1 2 3 4 5 6 7 8 9 10 11 12 a b c d e f g h i j k l
(c) 完全二叉树的顺序存储形式

1 2 3 4 5 6 7 8 9 10 11 a b c d e ? h ? ? f g
(d) 非完全二叉树的顺序存储形式
图6-6 二叉树及其顺序存储形式

最坏的情况下,一个深度为k且只有k个结点的单支 树需要长度为2k-1的一维数组。

2 链式存储结构
设计不同的结点结构可构成不同的链式存储结构。

(1) 结点的类型及其定义
① 二叉链表结点。有三个域:一个数据域,两个分 别指向左右子结点的指针域,如图6-7(a)所示。
typedef struct BTNode { ElemType data ; struct BTNode *Lchild , *Rchild ;

}BTNode ;

② 三叉链表结点。除二叉链表的三个域外,再增加一 个指针域,用来指向结点的父结点,如图6-7(b)所示。
typedef struct BTNode_3 { ElemType data ; struct BTNode_3 *Lchild , *Rchild , *parent ;

}BTNode_3 ;
Lchild data Rchild
(a) 二叉链表结点

Lchild data parent Rchild
(b) 三叉链表结点

图6-7 链表结点结构形式

(2) 二叉树的链式存储形式
例有一棵一般的二叉树,如图6-8(a)所示。以二叉 链表和三叉链表方式存储的结构图分别如图6-8(b) 、 68(c)所示。
a b c e g
(a) 二叉树

T b

a ?

T b

a ? ?

d f

?c ? ?e

d ?f ? ?g ?
(b) 二叉链表

? c

? ? e

d ? f ? g ? ?

(c) 三叉链表

图6-8 二叉树及其链式存储结构

6.3

遍历二叉树及其 应用

遍历二叉树(Traversing Binary Tree):是
指按指定的规律对二叉树中的每个结点访问一次且仅访 问一次。

所谓访问是指对结点做某种处理。如:输出信息、 修改结点的值等。
二叉树是一种非线性结构,每个结点都可能有左、 右两棵子树,因此,需要寻找一种规律,使二叉树上的 结点能排列在一个线性队列上,从而便于遍历。

二叉树的基本组成:根结点、左子树、右子树。若 能依次遍历这三部分,就是遍历了二叉树。

若以L、D、R分别表示遍历左子树、遍历根结点和 遍历右子树,则有六种遍历方案:DLR、LDR、LRD、 DRL、RDL、RLD。若规定先左后右,则只有前三种 情况三种情况,分别是:

DLR——先(根)序遍历。
LDR——中(根)序遍历。 LRD——后(根)序遍历。 对于二叉树的遍历,分别讨论递归遍历算法和非递 归遍历算法。递归遍历算法具有非常清晰的结构,但初 学者往往难以接受或怀疑,不敢使用。实际上,递归算 法是由系统通过使用堆栈来实现控制的。而非递归算法 中的控制是由设计者定义和使用堆栈来实现的。

6.3.1
1 递归算法

先序遍历二 叉树

算法的递归定义是:
若二叉树为空,则遍历结束;否则 ⑴ 访问根结点; ⑵ 先序遍历左子树(递归调用本算法); ⑶ 先序遍历右子树(递归调用本算法)。

先序遍历的递归算法
void PreorderTraverse(BTNode *T)

{ if (T!=NULL)
{ visit(T->data) ;
/* 访问根结点 */

PreorderTraverse(T->Lchild) ; PreorderTraverse(T->Rchild) ; }

}

说明:visit()函数是访问结点的数据域,其要求视具体
问题而定。树采用二叉链表的存储结构,用指针变量 T 来指向。

2 非递归算法
设T是指向二叉树根结点的指针变量,非递归算法是:

若二叉树为空,则返回;否则,令p=T;
⑴ 访问p所指向的结点; ⑵ q=p->Rchild ,若q不为空,则q进栈; ⑶ p=p->Lchild ,若p不为空,转(1),否则转 (4);

⑷ 退栈到p ,转(1),直到栈空为止。

算法实现:

#define MAX_NODE 50 void PreorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T, *q ; int top=0 ; if (T==NULL) printf(“ Binary Tree is Empty!\n”) ; else { do { visit( p-> data ) ; q=p->Rchild ; if ( q!=NULL ) stack[++top]=q ; p=p->Lchild ; if (p==NULL) { p=stack[top] ; top-- ; } } while (p!=NULL) ; } }

6.3.2
1 递归算法

中序遍历二 叉树

算法的递归定义是:
若二叉树为空,则遍历结束;否则
⑴ 中序遍历左子树(递归调用本算法); ⑵ 访问根结点; ⑶ 中序遍历右子树(递归调用本算法)。

中序遍历的递归算法
void InorderTraverse(BTNode *T) { if (T!=NULL) { InorderTraverse(T->Lchild) ; visit(T->data) ; } }
/*图6-8(a) 的二叉树,输出的次序是: cbegdfa */ /* 访问根结点 */

InorderTraverse(T->Rchild) ;

2 非递归算法
设T是指向二叉树根结点的指针变量,非递归算法是:
若二叉树为空,则返回;否则,令p=T ⑴ 若p不为空,p进栈, p=p->Lchild ; ⑶ p=p->Rchild ,转(1);

⑵ 否则(即p为空),退栈到p,访问p所指向的结点;

直到栈空为止。

算法实现:

#define MAX_NODE 50 void InorderTraverse( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T ; int top=0 , bool=1 ; if (T==NULL) printf(“ Binary Tree is Empty!\n”) ; else { do { while (p!=NULL) { stack[++top]=p ; p=p->Lchild ; } if (top==0) bool=0 ; else { p=stack[top] ; top-- ; visit( p->data ) ; p=p->Rchild ; } } while (bool!=0) ; } }

叉树
1 递归算法
算法的递归定义是:
若二叉树为空,则遍历结束;否则

⑴ 后序遍历左子树(递归调用本算法);
⑵ 后序遍历右子树(递归调用本算法) ; ⑶ 访问根结点 。

后序遍历的递归算法
void PostorderTraverse(BTNode *T) { if (T!=NULL) { PostorderTraverse(T->Lchild) ; PostorderTraverse(T->Rchild) ;

visit(T->data) ;
} }

/* 访问根结点 */

/*图6-8(a) 的二叉树,输出的次序是: cgefdba

*/

遍历二叉树的算法中基本操作是访问结点,因此, 无论是哪种次序的遍历,对有n个结点的二叉树,其时 间复杂度均为O(n) 。

如图6-9所示的二叉树表示表达式:(a+b*(c-d)-e/f)
按不同的次序遍历此二叉树,将访问的结点按先后次序 排列起来的次序是: 其先序序列为: 其中序序列为: -+a*b-cd/ef a+b*c-d-e/f

其后序序列为:

abcd-*+ef/+
a b

- / * c d e f

图6-9 表达式 (a+b*(c-d)-e/f)二叉树

2 非递归算法

在后序遍历中,根结点是最后被访问的。因此, 在遍历过程中,当搜索指针指向某一根结点时,不能立 即访问,而要先遍历其左子树,此时根结点进栈。当其 左子树遍历完后再搜索到该根结点时,还是不能访问, 还需遍历其右子树。所以,此根结点还需再次进栈,当 其右子树遍历完后再退栈到到该根结点时,才能被访问。 因此,设立一个状态标志变量tag :
tag=
0 : 结点暂不能访问 1 : 结点可以被访问

其次,设两个堆栈S1、S2 ,S1保存结点,S2保存结 点的状态标志变量tag 。S1和S2共用一个栈顶指针。
设T是指向根结点的指针变量,非递归算法是:

若二叉树为空,则返回;否则,令p=T;
⑴ 第一次经过根结点p,不访问:

p进栈S1 , tag 赋值0,进栈S2,p=p->Lchild 。
⑵ 若p不为空,转(1),否则,取状态标志值tag : ⑶ 若tag=0:对栈S1,不访问,不出栈;修改S2栈顶 元素值(tag赋值1) ,取S1栈顶元素的右子树,即 p=S1[top]->Rchild ,转(1); ⑷ 若tag=1:S1退栈,访问该结点; 直到栈空为止。

算法实现:
#define MAX_NODE 50 void PostorderTraverse( BTNode *T) { BTNode *S1[MAX_NODE] ,*p=T ; int S2[MAX_NODE] , top=0 , bool=1 ; if (T==NULL) printf(“Binary Tree is Empty!\n”) ; else { do { while (p!=NULL) { S1[++top]=p ; S2[top]=0 ; p=p->Lchild ; } if (top==0) bool=0 ;

else if (S2[top]==0) { p=S1[top]->Rchild ; S2[top]=1 ; } else { p=S1[top] ; top-- ; visit( p->data ) ; p=NULL ;
/* 使循环继续进行而不至于死循环 */

} } while (bool!=0) ;

}
}

叉树
层次遍历二叉树,是从根结点开始遍历,按层次 次序“自上而下,从左至右”访问树中的各结点。 为保证是按层次遍历,必须设置一个队列,初始 化时为空。

设T是指向根结点的指针变量,层次遍历非递归算 法是:
若二叉树为空,则返回;否则,令p=T,p入队; ⑴ 队首元素出队到p; ⑵访问p所指向的结点;

⑶将p所指向的结点的左、右子结点依次入队。直 到队空为止。

#define MAX_NODE 50 void LevelorderTraverse( BTNode *T) { BTNode *Queue[MAX_NODE] ,*p=T ; int front=0 , rear=0 ; if (p!=NULL) { Queue[++rear]=p; /* 根结点入队 */ while (front<rear) { p=Queue[++front]; visit( p->data ); if (p->Lchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ if (p->Rchild!=NULL) Queue[++rear]=p; /* 左结点入队 */ } }

6.3.5 二叉树遍历算法的应用
“遍历”是二叉树最重要的基本操作,是各种其它 操作的基础,二叉树的许多其它操作都可以通过遍历来 实现。如建立二叉树的存储结构、求二叉树的结点数、 求二叉树的深度等。

1 二叉树的二叉链表创建
⑴ 按满二叉树方式建立 (补充)
在此补充按满二叉树的方式对结点进行编号建立链式 二叉树。对每个结点,输入i、ch。 i : 结点编号,按从小到大的顺序输入 ch : 结点内容,假设是字符 在建立过程中借助一个一维数组S[n] ,编号为i的 结点保存在S[i]中。

算法实现:

#define MAX_NODE 50 typedef struct BTNode { char data ; struct BTNode *Lchild , *Rchild ; }BTNode ; BTNode *Create_BTree(void)
/* 建立链式二叉树,返回指向根结点的指针变量 */

{ BTNode *T , *p , *s[MAX_NODE] ; char ch ; int i , j ; while (1) { scanf(“%d”, &i) ; if (i==0) break ; /* 以编号0作为输入结束 */ else { ch=getchar() ;

p=(BTNode *)malloc(sizeof(BTNode)) ; p–>data=ch ; p–>Lchild=p–>Rchild=NULL ; s[i]=p ; if (i==1) T=p ; else { j=i/2 ; /* j是i的双亲结点编号 */ if (i%2==0) s[j]->Lchild=p ; else s[j]->Rchild=p ; }
} } return(T) ; }

⑵ 按先序遍历方式建立
对一棵二叉树进行“扩充”,就可以得到有该二叉 树所扩充的二叉树。有两棵二叉树T1及其扩充的二叉树 T2如图6-10所示。
A A B D C D ? ? ? B E C

F G ?
?

?

E G

F

?

?

(a) 二叉树T1

(b) T1的扩充二叉树T2

图6-10 二叉树T1及其扩充二叉树T2

二叉树的扩充方法是:在二叉树中结点的每一个空 链域处增加一个扩充的结点(总是叶子结点,用方框 “□”表示)。对于二叉树的结点值: ◆ 是char类型:扩充结点值为“?”;
◆ 是int类型:扩充结点值为0或-1;

下面的算法是二叉树的前序创建的递归算法,读入 一棵二叉树对应的扩充二叉树的前序遍历的结点值序列。 每读入一个结点值就进行分析:

◆ 若是扩充结点值:令根指针为NULL;
◆ 若是(正常)结点值:动态地为根指针分配一个结 点,将该值赋给根结点,然后递归地创建根的左子 树和右子树。

算法实现:
#define NULLKY ‘?’ #define MAX_NODE 50 typedef struct BTNode { char data ; struct BTNode *Lchild , *Rchild ; }BTNode ; BTNode *Preorder_Create_BTree(BTNode *T)
/* 建立链式二叉树,返回指向根结点的指针变量 */

{ char ch ; ch=getchar() ; getchar(); if (ch==NULLKY) { T=NULL; return(T) ; }

else { T=(BTNode *)malloc(sizeof(BTNode)) ; T–>data=ch ; Preorder_Create_BTree(T->Lchild) ; Preorder_Create_BTree(T->Rchild) ; return(T) ; }
}

当希望创建图6-10(a)所示的二叉树时,输入的字符 序列应当是: ABD??E?G??CF???

2 求二叉树的叶子结点数
可以直接利用先序遍历二叉树算法求二叉树的叶 子结点数。只要将先序遍历二叉树算法中vist()函数简 单地进行修改就可以。

算法实现:
#define MAX_NODE 50 int search_leaves( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T; int top=0, num=0; if (T!=NULL)

{ stack[++top]=p ; while (top>0) { p=stack[top--] ; if (p->Lchild==NULL&&p>Rchild==NULL) num++ ; if (p->Rchild!=NULL ) stack[++top]=p->Rchild; if (p->Lchild!=NULL ) stack[++top]=p->Lchild; } } return(num) ; }

3 求二叉树的深度
利用层次遍历算法可以直接求得二叉树的深度。

算法实现:
#define MAX_NODE 50 int search_depth( BTNode *T) { BTNode *Stack[MAX_NODE] ,*p=T; int front=0 , rear=0, depth=0, level ;
/* level总是指向访问层的最后一个结点在队列的位 置 */

if (T!=NULL)

{ Queue[++rear]=p;
*/

/*

根结点入队

while (front<rear) { p=Queue[++front]; if (p->Lchild!=NULL) Queue[++rear]=p; /* 左结点入队 */

if (p->Rchild!=NULL)
Queue[++rear]=p; if (front==level)
/* 正访问的是当前层的最后一个结点 */ /* 左结点入队 */

{ depth++ ; level=rear ; }

}
}

}

6.4 线索树
遍历二叉树是按一定的规则将树中的结点排列成一 个线性序列,即是对非线性结构的线性化操作。如何找 到遍历过程中动态得到的每个结点的直接前驱和直接后 继(第一个和最后一个除外)?如何保存这些信息?

设一棵二叉树有n个结点,则有n-1条边(指针连线) , 而n个结点共有2n个指针域(Lchild和Rchild) ,显然有 n+1个空闲指针域未用。则可以利用这些空闲的指针域 来存放结点的直接前驱和直接后继信息。
对结点的指针域做如下规定:

◆ 若结点有左孩子,则Lchild指向其左孩子,否则, 指向其直接前驱; ◆ 若结点有右孩子,则Rchild指向其右孩子,否则, 指向其直接后继; 为避免混淆,对结点结构加以改进,增加两个标志域, 如图6-10所示。
Lchild Ltag data Rchild Rtag
图6-10 线索二叉树的结点结构

Ltag=

0:Lchild域指示结点的左孩子 1:Lchild域指示结点的前驱

Rtag=

0:Rchild域指示结点的右孩子
1:Rchild域指示结点的后继

用这种结点结构构成的二叉树的存储结构;叫做线 索链表;指向结点前驱和后继的指针叫做线索;按照某 种次序遍历,加上线索的二叉树称之为线索二叉树。

线索二叉树的结点结构与示例
typedef struct BiThrNode
{ ElemType data; struct BiTreeNode *Lchild , *Rchild ; int Ltag , Rtag ; }BiThrNode ;

如图6-11是二叉树及相应的各种线索树示例。

A B

A

C
E F H I

B

C
E F H I NIL

D
G

D
G

(a) 二叉树

(b) 先序线索树的逻辑形式 结点序列:ABDCEGFHI

A

A C

NIL
D

B E

NIL
F NIL D

B E

C F

G

H

I

G

H

I

(c) 中序线索树的逻辑形式 结点序列:DBAGECHFI

(d) 后序线索树的逻辑形式 结点序列:DBGEHIFCA

0 A 0 0 B 1 ? 1 D 1 1 G 1 0 E 1 1 H 1 0 C 0 0 F 0 1 F 1 ?

(e) 中序线索树的链表结构

图6-11 线索二叉树及其存储结构

说明:画线索二叉树时,实线表示指针,指向其左、
右孩子;虚线表示线索,指向其直接前驱或直接后继。 在线索树上进行遍历,只要先找到序列中的第一个 结点,然后就可以依次找结点的直接后继结点直到后继 为空为止。

如何在线索树中找结点的直接后继?以图6-11(d) , (e)所示的中序线索树为例: ◆ 树中所有叶子结点的右链都是线索。右链直接指 示了结点的直接后继,如结点G的直接后继是结点E。

◆ 树中所有非叶子结点的右链都是指针。根据中序遍 历的规律,非叶子结点的直接后继是遍历其右子树时 访问的第一个结点,即右子树中最左下的(叶子)结点。 如结点C的直接后继:沿右指针找到右子树的根结点F, 然后沿左链往下直到Ltag=1的结点即为C的直接后继 结点H。

如何在线索树中找结点的直接前驱?若结点的 Ltag=1,则左链是线索,指示其直接前驱;否则,遍历 左子树时访问的最后一个结点(即沿左子树中最右往下 的结点) 为其直接前驱结点。

对于后序遍历的线索树中找结点的直接后继比较复 杂,可分以下三种情况:
◆ 若结点是二叉树的根结点:其直接后继为空; ◆ 若结点是其父结点的左孩子或右孩子且其父结点 没有右子树:直接后继为其父结点;

◆ 若结点是其父结点的左孩子且其父结点有右子树: 直接后继是对其父结点的右子树按后序遍历的第一个 结点。

6.4.1

线索化二叉 树

二叉树的线索化指的是依照某种遍历次序使二叉 树成为线索二叉树的过程。

线索化的过程就是在遍历过程中修改空指针使其指 向直接前驱或直接后继的过程。
仿照线性表的存储结构,在二叉树的线索链表上也 添加一个头结点head,头结点的指针域的安排是: ◆ Lchild域:指向二叉树的根结点;

◆ Rchild域:指向中序遍历时的最后一个结点;
◆ 二叉树中序序列中的第一个结点Lchild指针域 和最后一个结点Rchild指针域均指向头结点head。

如同为二叉树建立了一个双向线索链表,对一棵线 索二叉树既可从头结点也可从最后一个结点开始按寻找 直接后继进行遍历。显然,这种遍历不需要堆栈,如图 6-12所示。结点类型定义 #define MAX_NODE 50 typedef enmu{Link , Thread} PointerTag ;
/* Link=0表示指针, Thread=1表示线索 */

typedef struct BiThrNode { ElemType data; struct BiTreeNode *Lchild , *Rchild ; PointerTag Ltag , Rtag ;

}BiThrNode;

A B D E C F

A

NIL
D

B E

C F NIL

G

H

I

head 0 1

G

H

I

(a) 二叉树

(b) 中序线索树的逻辑形式

Thrt 0 B 1 1 D 1

0 A 0
0 C 0 0 E 1 0 F 0

1 G 1

1 H 1

1 F 1

(c) 中序线索二叉链表
图6-12 中序线索二叉树及其存储结构

1 先序线索化二叉树
void preorder_Threading(BiThrNode *T) { BiThrNode *stack[MAX_NODE]; BiThrNode *last=NULL, *p ; int top=0 ; if (T!=NULL) { stack[++top]=T; while (top>0) { p=stack[top--] ; if (p->Lchild!=NULL) p->Ltag=0 ; else { p->Ltag=1 ; p->Lchild!=last ; } if (last!=NULL) if (last->Rchild!=NULL) last->Rtag=0 ;

else { last->Rtag=1 ; last->Rchild!=p ; } last=p ; if (p->Rchild!=NULL) stack[++top]=p->Rchild ; if (p->Lchild!=NULL) stack[++top]=p->Lchild ;

} Last->Rtag=1; /* 最后一个结点是叶子结点 */
}

}

2 中序线索化二叉树
void inorder_Threading(BiThrNode *T) { BiThrNode *stack[MAX_NODE]; BiThrNode *last=NULL, *p=T ; int top=0 ; while (p!=NULL||top>0) if (p!=NULL) { stack[++top]=p; p=p->Lchild; } else { p=stack[top--] ; if (p->Lchild!=NULL) p->Ltag=0 ; else { p->Ltag=1 ; p->Lchild!=last ; } if (last!=NULL) if (last->Rchild!=NULL) last->Rtag=0 ;

else { last->Rtag=1 ; last->Rchild!=p ; } last=p ; P=p->Rchild; } last->Rtag=1; /* 最后一个结点是叶子结点 */ } }

6.4.2

线索二叉树的 遍历

在线索二叉树中,由于有线索存在,在某些情况 下可以方便地找到指定结点在某种遍历序列中的直接前 驱或直接后继。此外,在线索二叉树上进行某种遍历比 在一般的二叉树上进行这种遍历要容易得多,不需要设 置堆栈,且算法十分简洁。

1 先序线索二叉树的先序遍历
void preorder_Thread_bt(BiThrNode *T) { BiThrNode *p=T ; while (p!=NULL) { visit(p->data) ; if (p->Ltag==0) p=p->Lchild ; else p=p->Rchild } }

2 中序线索二叉树的中序遍历
void inorder_Thread_bt(BiThrNode *T) { BiThrNode *p ; if (T!=NULL) { p=T; while (p->Ltag==0 ) p=p->Lchild; /* 寻找最左的结点 */ while (p!=NULL) { visit(p->data) ; if (p->Rtag==1) p=p->Rchild ; /* 通过右线索找到后继 */ else /* 否则,右子树的最左结点为后继 */ { p=p->Rchild ;

while (p->Ltag==0 ) p=p->Lchild;

}
} }

}

6.5 树与森林
本节将讨论树的存储结构、树及森林与二叉树之间 的相互转换、树的遍历等。

6.5.1 树的存储结构
树的存储结构根据应用的不同而不同。

1 双亲表示法(顺序存储结构)
用一组连续的存储空间来存储树的结点,同时在 每个结点中附加一个指示器(整数域) ,用以指示双亲结 点的位置(下标值) 。数组元素及数组的类型定义如下: #define MAX_SIZE 100
typedef struct PTNode { ElemType data ; int parent ; }PTNode ;

typedef struct

R A B D E C F G H I 0 1 2 3 4 5 6 7 8 9 R A B C D E F G H I -1 0 0 0 1 1 3 6 6 6

{ PTNode Nodes[MAX_SIZE] ;
int root; }Ptree ; 图6-13所示是一棵树及其双亲 表示的存储结构。这种存储结构利 用了任一结点的父结点唯一的性质。 可以方便地直接找到任一结点的父 结点,但求结点的子结点时需要扫 描整个数组。
/* 根结点位置 */

int num ; /* 结点数 */

图6-13 树的双亲存储结构

2 孩子链表表示法
树中每个结点有多个指针域,每个指针指向其一棵 子树的根结点。有两种结点结构。

⑴ 定长结点结构
指针域的数目就是树的度。 其特点是:链表结构简单,但指针域的浪费明显。 结点结构如图6-14(a) 所示。在一棵有n个结点,度为k 的树中必有n(k-1)+1空指针域。

⑵ 不定长结点结构
树中每个结点的指针域数量不同,是该结点的度, 如图6-14(b) 所示。没有多余的指针域,但操作不便。

data child1 child2 ? childn
(a) 定长结点结构

data k child1 child2 ? childk
(b) 不定长结点结构

图6-14 孩子表示法的结点结构

⑶ 复合链表结构
对于树中的每个结点,其孩子结点用带头结点的 单链表表示,表结点和头结点的结构如图6-15所示。 n个结点的树有n个(孩子)单链表(叶子结点的孩子链 表为空),而n个头结点又组成一个线性表且以顺序存储 结构表示。
data firstchild childno next
(a) 头结点 (b) 表结点

图6-15 孩子链表结点结构

数据结构类型定义如下: #define MAX_NODE 100 typedef struct listnode { int childno ; }CTNode; typedef struct { ElemType data ; CTNode *firstchild ;
/* 孩子结点编号 */

struct listno *next ;
/* 表结点结构 */

}HNode; /* 头结点结构 */

typedef struct { HNode nodes[MAX_NODE] ; int root; /* 根结点位置 */ int num ; /* 结点数 */

}CLinkList; /* 头结点结构 */
图6-13所示的树T的孩子链表表示的存储结构如图 6-16所示。

nodes 0 1 2 3 4 5 6 7 8 9
MAX_NODE-1

A B ? C D ? R E ? F G ? H ? I ? ┇┇
4 9

3 6 ?

5 ?

0
7

1 8

2 ?
9 ?

root num

图6-16 图6-13的树T的孩子链表存储结构

3 孩子兄弟表示法(二叉树表示法)
以二叉链表作为树的存储结构,其结点形式如图617(a)所示。 两个指针域:分别指向结点的第一个子结点和下一 个兄弟结点。结点类型定义如下: typedef struct CSnode { ElemType data ;

struct CSnode *firstchild, *nextsibing ;
}CSNode; 图6-17(b)所示树的孩子兄弟表示的存储结构如图617(c)。

firstchild data nextsibing
孩子结点

R

兄弟结点

A B D
R? A E

C G F

(a) 结点结构

(b) 树

?D

?B C?

?E? ?G

?F ?
(c) 孩子兄弟存储结构 图6-17 树及孩子兄弟存储结构

6.5.2 森林与二叉树的转换
由于二叉树和树都可用二叉链表作为存储结构, 对比各自的结点结构可以看出,以二叉链表作为媒介可 以导出树和二叉树之间的一个对应关系。 ◆ 从物理结构来看,树和二叉树的二叉链表是相同 的,只是对指针的逻辑解释不同而已。 ◆ 从树的二叉链表表示的定义可知,任何一棵和树 对应的二叉树,其右子树一定为空。 图6-18直观地展示了树和二叉树之间的对应关系。



R
A B D C

对应关系

二叉树

R A

E
存储

R A ?D?
解释 存储

D E

B C

B ?E?

解释

R?
A

R? A B ?E? ?C?

?C?

?D?

B
?C?

?D?

?E?
图6-18 树与二叉树的对应关系

1 树转换成二叉树

对于一般的树,可以方便地转换成一棵唯一的二 叉树与之对应。将树转换成二叉树在“孩子兄弟表示法” 中已给出,其详细步骤是: ⑴ 加虚线。在树的每层按从“左至右”的顺序在 兄弟结点之间加虚线相连。 ⑵ 去连线。除最左的第一个子结点外,父结点与所 有其它子结点的连线都去掉。

⑶ 旋转。将树顺时针旋转450,原有的实线左斜。
⑷ 整型。将旋转后树中的所有虚线改为实线,并向 右斜。该转换过程如图6-19所示。

这样转换后的二叉树的特点是: ◆ 二叉树的根结点没有右子树,只有左 子树; ◆ 左子结点仍然是原来树中相应结点的 R 左子结点,而所有沿右链往下的右子结点 A 均是原来树中该结点的兄弟结点。
R A B D C A R B C G D G F F
(C) 转换后的二叉树

D

B

E F E

C

E

G

(a) 一般的树

(b) 加虚线,去连线后

图6-19 树向二叉树的转换过程

2 二叉树转换成树
对于一棵转换后的二叉树,如何还原成原来的树 ? 其步骤是:

⑴ 加虚线。若某结点i是其父结点的左子树的根结 点,则将该结点i的右子结点以及沿右子链不断地搜 索所有的右子结点,将所有这些右子结点与i结点的 父结点之间加虚线相连,如图6-20(a)所示。
⑵ 去连线。去掉二叉树中所有父结点与其右子结点 之间的连线,如图6-20(b)所示。 ⑶ 规整化。将图中各结点按层次排列且将所有的虚 线变成实线,如图6-20(c)所示。

R A A B E

R R B E A B

D

D C

C
G F

C
G

D

E

G F
(a) 加虚线后

(C) 还原后的树

F
(b) 去连线后
图6-20 二叉树向树的转换过程

3 森林转换成二叉树
当一般的树转换成二叉树后,二叉树的右子树必 为空。若把森林中的第二棵树(转换成二叉树后)的根结 点作为第一棵树(二叉树)的根结点的兄弟结点,则可导 出森林转换成二叉树的转换算法如下:

设F={T1, T2,?,Tn}是森林,则按以下规则可转换成 一棵二叉树B=(root,LB,RB)
① 若n=0,则B是空树。 ② 若n>0,则二叉树B的根是森林T1的根root(T1), B的左子树LB是B(T11,T12, ?,T1m) ,其中T11,T12, ?,T1m是T1的子树(转换后),而其右子树RB是从森林 F’={T2, T3,?,Tn}转换而成的二叉树。

转换步骤:
① 将F={T1, T2,?,Tn} 中的每棵树转换成二叉树。

② 按给出的森林中树的次序,从最后一棵二叉树开 始,每棵二叉树作为前一棵二叉树的根结点的右子 树,依次类推,则第一棵树的根结点就是转换后生 成的二叉树的根结点,如图6-21所示。
A A B C D L H G K M B C H

G L
K M D B C

A G L H K M
(c) 森林对应的二叉树

D
(b) 森林中每棵树 对应的二叉树

(a) 森林

图6-21 森林转换成二叉树的过程

4 二叉树转换成森林
若B=(root,LB,RB)是一棵二叉树,则可以将其 转换成由若干棵树构成的森林:F={T1, T2,?,Tn} 。

转换算法:
① 若B是空树,则F为空。 ② 若B非空,则F中第一棵树T1的根root(T1)就是二 叉树的根root, T1中根结点的子森林F1是由树B的左 子树LB转换而成的森林;F中除T1外其余树组成的 的森林F’={T2, T3,?,Tn} 是由B右子树RB转换得到的 森林。

上述转换规则是递归的,可以写出其递归算法。以 下给出具体的还原步骤。

① 去连线。将二叉树B的根结点与其右子结点以及 沿右子结点链方向的所有右子结点的连线全部去掉, 得到若干棵孤立的二叉树,每一棵就是原来森林F中 的树依次对应的二叉树,如图6-22(b)所示。
② 二叉树的还原。将各棵孤立的二叉树按二叉树还 原为树的方法还原成一般的树,如图6- 22(c)所示。
A B C D H L K G M D B C H

A
G B

A L
K M C L H

G K

M

D

(a) 二叉树

(b) 去连线后 图6-22 二叉树还原成森林的过程

(c) 还原成森林

6.5.3 树和森林的遍历
1 树的遍历
由树结构的定义可知,树的遍历有二种方法。

⑴ 先序遍历:先访问根结点,然后依次先序遍历 完每棵子树。如图6-23的树,先序遍历的次序是:
ABCDEFGIJHK

⑵ 后序遍历:先依次后序遍历完每棵子树,然后 访问根结点。如图6-23的树,后序遍历的次序是:
CDBFGIJHEKA

A B E D F I G H J K

C

图6-23 树

说明:
◆ 树的先序遍历实质上与将树转换成二叉树 后对二叉树的先序遍历相同。 ◆ 树的后序遍历实质上与将树转换成二叉树 后对二叉树的中序遍历相同。

2 森林的遍历
设F={T1, T2,?,Tn}是森林,对F的遍历有二种方法。 ⑴ 先序遍历:按先序遍历树的方式依次遍历F中的 每棵树。 ⑵ 中序遍历:按后序遍历树的方式依次遍历F中的 每棵树。

6.6 赫夫曼树及其应用
赫夫曼(Huffman)树又称最优树,是一类带权 路径长度最短的树,有着广泛的应用。

6.6.1 最优二叉树(Huffman树)
1 基本概念
① 结点路径:从树中一个结点到另一个结点的之 间的分支构成这两个结点之间的路径。 ② 路径长度:结点路径上的分支数目称为路径长 度。

③ 树的路径长度:从树根到每一个结点的路径长 度之和。
例图6-23的树。A到F :结点路径 AEF ;路径 长度(即边的数目) 2 ;树的路径长度: 3?1+5?2+2?3=19

④ 结点的带权路径长度:从该结点的到树的根结点 之间的路径长度与结点的权(值)的乘积。
权(值):各种开销、代价、频度等的抽象称呼。 ⑤ 树的带权路径长度:树中所有叶子结点的带权路 径长度之和,记做:

WPL=w1?l1+w2?l2+?+wn?ln=∑wi?li (i=1,2,?,n)
其中:n为叶子结点的个数;wi为第i个结点的权值; li为第i个结点的路径长度。 ⑥ Huffman树:具有n个叶子结点(每个结点的 权值为wi) 的二叉树不止一棵,但在所有的这些二 叉树中,必定存在一棵WPL值最小的树,称这棵树 为Huffman树(或称最优树) 。

在许多判定问题时,利用Huffman树可以得到最 佳判断算法。
如图6-24是权值分别为2、3、6、7,具有4个叶 子结点的二叉树,它们的带权路径长度分别为: (a) WPL=2?2+3?2+6?2+7?2=36 ;

(b)
(c) 树。

WPL=2?1+3?2+6?3+7?3=47 ;
WPL=7?1+6?2+2?3+3?3=34 。

其中(c)的 WPL值最小,可以证明是Huffman

2 3 2

7 6

3
(a)

6

7

6
(b)

7

2
(c)

3

图6-24 具有相同叶子结点,不同带权路径长度的二叉树

2 Huffman树的构造
① 根据n个权值{w1, w2, ?,wn},构造成n棵二 叉树的集合F={T1, T2, ?,Tn},其中每棵二叉树 只有一个权值为wi的根结点,没有左、右子树;

② 在F中选取两棵根结点权值最小的树作为左、右 子树构造一棵新的二叉树,且新的二叉树根结点权 值为其左、右子树根结点的权值之和; ③ 在F中删除这两棵树,同时将新得到的树加入F 中;
④ 重复②、③,直到F只含一颗树为止。

构造Huffman树时,为了规范,规定F={T1,T2, ?,Tn}中权值小的二叉树作为新构造的二叉树的左子树, 权值大的二叉树作为新构造的二叉树的右子树;在取值 相等时,深度小的二叉树作为新构造的二叉树的左子树, 深度大的二叉树作为新构造的二叉树的右子树。

图6-25是权值集合W={8, 3, 4, 6, 5, 5}构造 Huffman树的过程。所构造的Huffman树的WPL 是:
3 4

WPL=6?2+3?3+4?3+8?2+5?3+5?3 =79
5 5 6 8 5 5 6 7 8 6 7 8
第一步

10 5

3
第二步

4 18

3

4
第三步
0

5

8
5

10 5
第四步

13 6
3 7 4 6

13

31
1 0 1

1

7
3 4

8 5
第五步

10 5

0

13
0

18
0

1

6

7

8

10

1

图6-25 Huffman树的构造过程

3

4

5

5

第六步

6.6.2 赫夫曼编码及其算法
1 Huffman编码
在电报收发等数据通讯中,常需要将传送的文字 转换成由二进制字符0、1组成的字符串来传输。为了 使收发的速度提高,就要求电文编码要尽可能地短。此 外,要设计长短不等的编码,还必须保证任意字符的编 码都不是另一个字符编码的前缀,这种编码称为前缀编 码。 Huffman树可以用来构造编码长度不等且译码 不产生二义性的编码。

设电文中的字符集C={c1,c2, ?,ci, ?,cn},各个 字符出现的次数或频度集W={w1,w2, ?,wi, ?,wn}。

Huffman编码方法
以字符集C作为叶子结点,次数或频度集W作为结 点的权值来构造 Huffman树。规定Huffman树中左 分支代表“0”,右分支代表“1” 。 从根结点到每个叶子结点所经历的路径分支上的 “0”或“1”所组成的字符串,为该结点所对应的编码, 称之为Huffman编码。 由于每个字符都是叶子结点,不可能出现在根结点 到其它字符结点的路径上,所以一个字符的Huffman 编码不可能是另一个字符的Huffman编码的前缀。

若字符集C={a, b, c, d, e, f}所对应的权值集 合为W={8, 3, 4, 6, 5, 5},如图6-25所示,则字 符a,b, c,d, e,f所对应的Huffman编码分别是:10, 010,011,00 ,110,111。

2 Huffman编码算法实现
(1) 数据结构设计
Huffman树中没有度为1的结点棵有n个叶子 结点的Huffman树共有2n-1个结点,则可存储在大 小为2n-1的一维数组中。实现编码的结点结构如图626所示。

原因:
◆ 求编码需从叶子结点出发走一条从叶子到根的路

Weight Parent Lchild Rchild Weight:权值域; Parent:双亲结点下标 Lchild, Rchild:分别标识左、右子树的下标
图6-26 Huffman编码的结点结构

◆ 译码需从根结点出发走一条到叶子结点的路径。

结点类型定义:
#define MAX_NODE 200 typedef struct { unsigned int Weight ;
/* 权值域 */ /* Max_Node>2n-1 */

unsinged int Parent , Lchild , Rchild ;
} HTNode ;

(2) Huffman树的生成 算法实现
void Create_Huffman(unsigned n, HTNode HT[ ], unsigned m)
/* 创建一棵叶子结点数为n的Huffman树 */

{ unsigned int w ; int k , j ; for (k=1 ; k<m ; k++) { if (k<=n) { printf(“\n Please Input Weight : w=?”); scanf(“%d”, &w) ;HT[k].weight=w ; } /* 输入时,所有叶子结点都有权值 */ else HT[k].weight=0; /* 非叶子结点没有权值 */

HT[k].Parent=HT[k].Lchild=HT[k].Rchild=0 ; } /* 初始化向量HT */ for (k=n+1; k<m ; k++) { unsigned w1=32767 , w2=w1 ;
/* w1 , w2分别保存权值最小的两个权值 */

int p1=0 , p2=0 ;
/* p1 , p2保存两个最小权值的下标 */

for (j=1 ; j<=k-1 ; j++) { if (HT[k].Parent==0) /* 尚未合并 */ { if (HT[j].Weight<w1) { w2=w1 ; p2=p1 ; w1=HT[j].Weight ; p1=j ; }

else if (HT[j].Weight<w2) { w2=HT[j].Weight ; p2=j ; } }
/* 找到权值最小的两个值及其下标 */

} HT[k].Lchild=p1 ; HT[k].Rchild=p2 ; HT[k].weight=w1+w2 ; HT[p1].Parent=k ; HT[p2].Parent=k ;

}
}

说明:生成Huffman树后,树的根结点的下标是2n-1 ,
即m-1 。

(3) Huffman编码算法
根据出现频度(权值)Weight,对叶子结点的 Huffman编码有两种方式: ① 从叶子结点到根逆向处理,求得每个叶子结点对 应字符的Huffman编码。 ② 从根结点开始遍历整棵二叉树,求得每个叶子结 点对应字符的Huffman编码。

由Huffman树的生成知,n个叶子结点的树共有2n-1 个结点,叶子结点存储在数组HT中的下标值为1∽n。
① 编码是叶子结点的编码,只需对数组HT[1…n]的 n个权值进行编码; ② 每个字符的编码不同,但编码的最大长度是n。

求编码时先设一个通用的指向字符的指针变量,求 得编码后再复制。

算法实现
void Huff_coding(unsigned n , Hnode HT[] , unsigned m)
/* m应为n+1,编码的最大长度n加1 */

{ int k , sp ,fp ; char *cd , *HC[m] ; cd=(char *)malloc(m*sizeof(char)) ;
/* 动态分配求编码的工作空间 */

cd[n]=‘\0’ /* 编码的结束标志 */ for (k=1 ; k<n+1 ; k++) /* 逐个求字符的编码 */ { sp=n ; p=k ; fp=HT[k].parent ;

for ( ; fp!=0 ;p=fp , fp=HT[p].parent)
/* 从叶子结点到根逆向求编码 */

if (HT[fp].parent==p) cd[--sp]=‘0’ ; else cd[--sp]=‘1’ ; HC[k]=(char *)malloc((n-sp)*sizeof(char)) ;
/* 为第k个字符分配保存编码的空间 */

trcpy(HC[k] , &cd[sp]) ;

} free(cd) ;
}

习题六
⑴ 假设在树中, 结点x是结点y的双亲时,用(x,y) 来表示树边。已知一棵树的树边集合为 { (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) } ,用树型表示法表示该树,并回答下 列问题: ① 哪个是根结点? 哪些是叶子结点? 哪个是g的 双亲? 哪些是g的祖先? 哪些是g的孩子? 那些是e 的子孙? 哪些是e的兄弟? 哪些是f的兄弟? ② b和n的层次各是多少? 树的深度是多少? 以 结点c为根的子树的深度是多少?

⑵ 一棵深度为h的满k叉树有如下性质: 第h层上 的结点都是叶子结点,其余各层上每个结点都有k棵非 空子树。 如果按层次顺序(同层自左至右)从1开始对全 部结点编号,问: ① 各层的结点数是多少?

② 编号为i的结点的双亲结点(若存在)的编号是多 少?
③ 编号为i的结点的第j个孩子结点(若存在)的编 号是多少? ④ 编号为i的结点的有右兄弟的条件是什么? 其右 兄弟的编号是多少?

⑶ 设有如图6-27所示的二叉树。 ① 分别用顺序存储方法和链接存储方法画出该二 叉树的存储结构。 ② 写出该二叉树的先序、中序、后序遍历序列。 ⑷ 已知一棵二叉树的先序遍历序列和中序遍历序列 分别为ABDGHCEFI和GDHBAECIF,请画出这棵 二叉树,然后给出该树的后序遍历序列。 a ⑸ 设一棵二叉树的中序遍历序列 b c 和后序遍历序列分别为BDCEAFHG 和DECBHGFA ,请画出这棵二叉 d e f g 树,然后给出该树的先序序列。 h k m n
图6-27 二叉树

⑹ 已知一棵二叉树的中序遍历序列和后序遍历序列 分别为dgbaekchif和gdbkeihfca,请画出这棵二 叉树对应的中序线索树和后序线索树。 ⑺ 以二叉链表为存储结构,请分别写出求二叉树的 结点总数及叶子结点总数的算法。 ⑻ 设图6-27所示的二叉树是森林F所对应的二叉树, 请画出森林F。

⑼ 设有一棵树,如图6-28所示。
① 请分别用双亲表示法、孩子表示法、孩子兄弟 表示法给出该树的存储结构。 ② 请给出该树的先序遍历序列和后序遍历序列。 ③ 请将这棵树转换成二叉树。

⑽ 设给定权值集合w={3,5,7,8,11,12} ,请构造关于w 的一棵huffman树,并求其加权路径长度WPL 。
⑾ 假设用于通信的电文是由字符集{a, b, c, d, e, f, g, h}中的字符构成, 这8个字符在电文中出现的概率分别 为{0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10} 。 ① 请画出对应的huffman树(按左子树根结点的权 小于等于右子树根结点的权的次序构造)。 ② 求出每个字符的huffman编码。

a b
c

m

d e h k g f n
图6-28 一般的树

第7章



图(Graph)是一种比线性表和树更为复杂的数 据结构。

线性结构:是研究数据元素之间的一对一关系。
在这种结构中,除第一个和最后一个元素外,任何一 个元素都有唯一的一个直接前驱和直接后继。

树结构:是研究数据元素之间的一对多的关系。
在这种结构中,每个元素对下(层)可以有0个或多个元 素相联系,对上(层)只有唯一的一个元素相关,数据 元素之间有明显的层次关系。

图结构:是研究数据元素之间的多对多的关系。
在这种结构中,任意两个元素之间可能存在关系。即结 点之间的关系可以是任意的,图中任意元素之间都可能 相关。 图的应用极为广泛,已渗入到诸如语言学、逻辑 学、物理、化学、电讯、计算机科学以及数学的其它分 支。

7.1 图的基本概念
7.1.1 图的定义和术语
一个图(G)定义为一个偶对(V,E) ,记为 G=(V,E) 。其中: V是顶点(Vertex)的非空有限集 合,记为V(G);E是无序集V&V的一个子集,记为 E(G) ,其元素是图的弧(Arc)。 将顶点集合为空的图称为空图。其形式化定义为: G=(V ,E) V={v|v?data object}

E={<v,w>| v,w?V∧p(v,w)}
P(v,w)表示从顶点v到顶点w有一条直接通路。

弧(Arc) :表示两个顶点v和w之间存在一个
关系,用顶点偶对<v,w>表示。通常根据图的顶点偶 对将图分为有向图和无向图。

有向图(Digraph): 若图G的关系集合E(G)
中,顶点偶对<v,w>的v和w之间是有序的,称图G是 有向图。
在有向图中,若 <v,w>?E(G) ,表示从顶点v 到顶点w有一条弧。 其中:v称为弧尾(tail)或始点 (initial node),w称为弧头(head)或终点 (terminal node) 。

无向图(Undigraph): 若图G的关系集合
E(G)中,顶点偶对<v,w>的v和w之间是无序的,称 图G是无向图。

在无向图中,若?<v,w>?E(G) ,有 <w,v>?E(G) ,即E(G)是对称,则用无序对(v,w) 表示v和w之间的一条边(Edge),因此(v,w) 和 (w,v)代表的是同一条边。
例1:设有有向图G1和无向图G2,形式化定义分别是:

G1=(V1 ,E1)
V1={a,b,c,d,e} E1={<a,b>,<a,c>, <a,e>,<c,d>,<c,e> ,<d,a>,<d,b>,<e,d>} G2=(V2 ,E2)

V2={a,b,c,d}
E2={(a,b), (a,c), (a,d), (b,d), (b,c), (c,d)}

a e

b
d

a b
图7-1 图的示例

d c

c

(a) 有向图G1

(b) 无向图G2

完全无向图:对于无向图,若图中顶点数为n ,
用e表示边的数目,则e ?[0,n(n-1)/2] 。具有n(n-1)/2条 边的无向图称为完全无向图。

完全无向图另外的定义是:
对于无向图G=(V,E),若?vi,vj ?V ,当vi≠vj时, 有(vi ,vj)?E,即图中任意两个不同的顶点间都有一条无 向边,这样的无向图称为完全无向图。

完全有向图:对于有向图,若图中顶点数为n ,
用e表示弧的数目,则e?[0,n(n-1)] 。具有n(n1)条边的有向图称为完全有向图。 完全有向图另外的定义是: 对于有向图G=(V,E),若?vi,vj?V ,当vi ≠vj时,有<vi ,vj>?E∧<vj , vi >?E ,即图中任意 两个不同的顶点间都有一条弧,这样的有向图称为完全 有向图。

有很少边或弧的图(e<n㏒n)的图称为稀疏图, 反之称为稠密图。

权(Weight):与图的边和弧相关的数。权可以表示
从一个顶点到另一个顶点的距离或耗费。

子图和生成子图:设有图G=(V,E)和

G’=(V’,E’),若V’?V且E’?E ,则称图G’是G的子图; 若V’=V且E’?E,则称图G’是G的一个生成子图。

顶点的邻接(Adjacent):对于无向图
G=(V,E),若边(v,w)?E,则称顶点v和w 互为邻 接点,即v和w相邻接。边(v,w)依附(incident)与 顶点v和w 。 对于有向图G=(V ,E),若有向弧<v,w>?E, 则称顶点v “邻接到”顶点w,顶点w “邻接自”顶点 v ,弧<v,w> 与顶点v和w “相关联” 。

顶点的度、入度、出度:对于无向图G=(V,
E), ?vi?V,图G中依附于vi的边的数目称为顶点vi的 度(degree),记为TD(vi)。

显然,在无向图中,所有顶点度的和是图中边的 2倍。 即 ∑TD(vi)=2e i=1, 2, …, n ,e为图 的边数。
对有向图G=(V,E),若?vi ?V ,图G中以vi 作为起点的有向边(弧)的数目称为顶点vi的出度 (Outdegree),记为OD(vi) ;以vi作为终点的有向 边(弧)的数目称为顶点vi的入度(Indegree),记为 ID(vi) 。顶点vi的出度与入度之和称为vi的度,记为 TD(vi) 。即 TD(vi)=OD(vi)+ID(vi)

路径(Path)、路径长度、回路(Cycle) :
对无向图G=(V,E),若从顶点vi经过若干条边能到达 vj,称顶点vi和vj是连通的,又称顶点vi到vj有路径。

或路径是图G中连接两顶点之间所经过的顶点序 列。即
Path=vi0vi1…vim ,vij?V且(vij-1, vij)?E j=1,2, …,m 或

Path=vi0vi1 …vim ,vij?V且<vij-1, vij>?E j=1,2, …,m
路径上边或有向边(弧)的数目称为该路径的长度。 在一条路径中,若没有重复相同的顶点,该路径 称为简单路径;第一个顶点和最后一个顶点相同的路径 称为回路(环);在一个回路中,若除第一个与最后一个 顶点外,其余顶点不重复出现的回路称为简单回路(简 单环)。

连通图、图的连通分量:对无向图G=(V,
E),若?vi ,vj ?V,vi和vj都是连通的,则称图G是 连通图,否则称为非连通图。若G是非连通图,则极大 的连通子图称为G的连通分量。 对有向图G=(V,E),若?vi ,vj ?V,都有以 vi为起点, vj 为终点以及以vj为起点,vi为终点的有 向路径,称图G是强连通图,否则称为非强连通图。若 G是非强连通图,则极大的强连通子图称为G的强连通 分量。
“极大”的含义:指的是对子图再增加图G中的 其它顶点,子图就不再连通。

生成树、生成森林:一个连通图(无向图)的生
成树是一个极小连通子图,它含有图中全部n个顶点和 只有足以构成一棵树的n-1条边,称为图的生成树,如 图7-2所示。 关于无向图的生成树的几个结论: ◆ 一棵有n个顶点的生成树有且仅有n-1条边; ◆ 如果一个图有n个顶点和小于n-1条边,则是非 连通图; ◆ 如果多于n-1条边,则一定 有环; ◆ 有n-1条边的图不一定是 生成树。
a b d c

图7-2 图G2的一棵生成树

有向图的生成森林是这样一个子图,由若干棵有向 树组成,含有图中全部顶点。
有向树是只有一个顶点的入度为0 ,其余顶点的入度均 为1的有向图,如图7-3所示。

网:每个边(或弧)都附加一个权值的图,称为带权
图。带权的连通图(包括弱连通的有向图)称为网或网络。 网络是工程上常用的一个概念,用来表示一个工程或某 种流程,如图7-4所示。
a c

b
e d c

a b c

d e

c b
2

a c

6
3

b 3
4 5

e

1

(a) 有向图

(b) 生成森林

d

图7-3 有向图及其生成森林

图7-4 带权有向图

7.1.2 图的抽象数据类型定义
图是一种数据结构,加上一组基本操作就构成了图 的抽象数据类型。 图的抽象数据类型定义如下:

ADT Graph{
数据对象V:具有相同特性的数据元素的集合,称 为顶点集。

数据关系R:R={VR}
VR={<v,w>|<v,w>| v,w?V∧p(v,w) ,<v,w>表示 从v到w的弧,P(v,w)定义了弧<v,w>的信息 }

基本操作P:
Create_Graph() : 图的创建操作。 初始条件:无。 操作结果:生成一个没有顶点的空图G。 GetVex(G, v) : 求图中的顶点v的值。

初始条件:图G存在,v是图中的一个顶点。
操作结果:生成一个没有顶点的空图G。 … … DFStraver(G,V):从v出发对图G深度优先遍历。 初始条件:图G存在。

操作结果:对图G深度优先遍历,每个顶点访问 且只访问一次。

?? BFStraver(G,V):从v出发对图G广度优先遍历。 初始条件:图G存在。 操作结果:对图G广度优先遍历,每个顶点访问 且只访问一次。 } ADT Graph 详见p156~157。

7.2 图的存储结构
图的存储结构比较复杂,其复杂性主要表现在:
◆ 任意顶点之间可能存在联系,无法以数据元素 在存储区中的物理位置来表示元素之间的关系。

◆ 图中顶点的度不一样,有的可能相差很大,若 按度数最大的顶点设计结构,则会浪费很多存储单 元,反之按每个顶点自己的度设计不同的结构,又 会影响操作。
图的常用的存储结构有:邻接矩阵、邻接链表、 十字链表、邻接多重表和边表。

7.2.1 邻接矩阵(数组)表示法
基本思想:对于有n个顶点的图,用一维数组
vexs[n]存储顶点信息,用二维数组A[n][n]存储顶 点之间关系的信息。该二维数组称为邻接矩阵。在邻接 矩阵中,以顶点在vexs数组中的下标代表顶点,邻接 矩阵中的元素A[i][j]存放的是顶点i到顶点j之间关系 的信息。

1 无向图的数组表示
(1) 无权图的邻接矩阵
无向无权图G=(V,E)有n(n≧1)个顶点,其邻 接矩阵是n阶对称方阵,如图7-5所示。其元素的定义 如下: 1 若(vi , vj)?E,即vi , vj邻接 A[i][j]= 0 若(vi , vj)?E,即vi , vj不邻接
a b d vexs a b c d
(b) 顶点矩阵

c

0 1 1 1

1 0 1 1

1 1 0 1

1 1 1 0

(a) 无向图

(c) 邻接矩阵

图7-5 无向无权图的数组存储

(2) 带权图的邻接矩阵
无向带权图G=(V,E) 的邻接矩阵如图7-6所示。其 元素的定义如下: Wij 若(vi , vj)?E,即vi , vj邻接,权值为wij A[i][j]= ∞ 若(vi , vj)?E,即vi , vj不邻接时
a
2
6 3 1

b 3
4 5

e

c

d

(a) 带权无向图

vexs a b c d e

∞ 6 2 ∞ 6 ∞ 3 4 2 3 ∞ 1 ∞ 4 3 ∞ ∞ 3 ∞ 5

∞ 3 ∞ 5 ∞

(b) 顶点矩阵 (c) 邻接矩阵 图7-6 无向带权图的数组存储

(3) 无向图邻接矩阵的特性
◆ 邻接矩阵是对称方阵;

◆ 对于顶点vi,其度数是第i行的非0元素的个数;
◆ 无向图的边数是上(或下)三角形矩阵中非0元素 个数。

2 有向图的数组表示
(1) 无权图的邻接矩阵
若有向无权图G=(V,E)有n(n≧1)个顶点,则其邻 接矩阵是n阶对称方阵,如图7-7所示。元素定义如下: A[i][j]= 1 若<vi, vj>?E,从vi到vj有弧 0 若<vi , vj>?E 从vi到vj 没有弧

a e

b d

c

vexs a b c d e
(b) 顶点矩阵

0 0 0 1 0

1 0 0 1 0

1 0 0 0 0

0 1 0 0 1 1 0 0 1 0

(a) 有向图

(c) 邻接矩阵

图7-7 有向无权图的数组存储

(2) 带权图的邻接矩阵
有向带权图G=(V,E)的邻接矩阵如图7-8所示。其 元素的定义如下: A[i][j]=
wij 若<vi,vj>?E,即vi , vj邻接,权值为wij



若<vi,vj>?E,即vi , vj不邻接时

a
2

6

b 3
4 5

3

e

c

1

d

vexs a b c d e
(b) 顶点矩阵

∞ ∞ ∞ ∞ ∞

6 2 ∞∞ 3 ∞ 4 ∞ ∞∞

∞ ∞ 1 ∞ ∞

∞ 3 ∞ 5 ∞

(a) 带权有向图

(c) 邻接矩阵

图7-8 带权有向图的数组存储

⑶ 有向图邻接矩阵的特性
◆ 对于顶点vi,第i行的非0元素的个数是其出度 OD(vi);第i列的非0元素的个数是其入度ID(vi) 。 ◆ 邻接矩阵中非0元素的个数就是图的弧的数目。

3 图的邻接矩阵的操作
图的邻接矩阵的实现比较容易,定义两个数组分 别存储顶点信息(数据元素)和边或弧的信息(数据元素 之间的关系) 。其存储结构形式定义如下: #define INFINITY MAX_VAL #define MAX_VEX 30
/* 最大值∞ */ /* 根据图的权值类型,分别定义为最大整数或实数 */ /* 最大顶点数目 */

typedef enum {DG, AG, WDG,WAG} GraphKind ;
/* {有向图,无向图,带权有向图,带权无向图} */

typedef struct ArcType { VexType vex1, vex2 ; /* 弧或边所依附的两个顶点 */

ArcValType ArcVal ;

/* 弧或边的权值 */

ArcInfoType ArcInfo ; /* 弧或边的其它信息 */ }ArcType ; /* 弧或边的结构定义 */ typedef struct { GraphKind kind ; /* 图的种类标志 */

int vexnum , arcnum ; /* 图的当前顶点数和弧数 */
VexType vexs[MAX_VEX] ; /* 顶点向量 */

AdjType adj[MAX_VEX][MAX_VEX];
}MGraph ;
/* 图的结构定义 */

利用上述定义的数据结构,可以方便地实现图的各 种操作。

(1) 图的创建
AdjGraph *Create_Graph(MGraph * G) { printf(“请输入图的种类标志:”) ; scanf(“%d”, &G->kind) ; G->vexnum=0 ;
/* 初始化顶点个数 */

return(G) ;
}

(2) 图的顶点定位
图的顶点定位操作实际上是确定一个顶点在vexs数 组中的位置(下标) ,其过程完全等同于在顺序存储的线 性表中查找一个数据元素。

算法实现:
int LocateVex(MGraph *G , VexType *vp) { int k ;

for (k=0 ; k<G->vexnum ; k++)
if (G->vexs[k]==*vp) return(k) ; return(-1) ; }
/* 图中无此顶点 */

(3) 向图中增加顶点
向图中增加一个顶点的操作,类似在顺序存储的线 性表的末尾增加一个数据元素。

算法实现:
int AddVertex(MGraph *G , VexType *vp) { int k , j ; if (G->vexnum>=MAX_VEX)

{ printf(“Vertex Overflow !\n”) ; return(-1) ; }
if (LocateVex(G , vp)!=-1)

{ printf(“Vertex has existed !\n”) ; return(-1) ; }
k=G->vexnum ; G->vexs[G->vexnum++]=*vp ;

if (G->kind==DG||G->kind==AG) for (j=0 ; j<G->vexnum ; j++) G->adj[j][k].ArcVal=G->adj[k][j].ArcVal=0 ;
/* 是不带权的有向图或无向图 */

else for (j=0 ; j<G->vexnum ; j++) { G->adj[j][k].ArcVal=INFINITY ; G->adj[k][j].ArcVal=INFINITY ;
/* 是带权的有向图或无向图 */

} return(k) ; }

(4) 向图中增加一条弧
根据给定的弧或边所依附的顶点,修改邻接矩阵中 所对应的数组元素。

算法实现:
int AddArc(MGraph *G , ArcType *arc) { int k , j ; k=LocateVex(G , &arc->vex1) ; j=LocateVex(G , &arc->vex1) ; if (k==-1||j==-1) { printf(“Arc’s Vertex do not existed !\n”) ; return(-1) ; }

if (G->kind==DG||G->kind==WDG) { G->adj[k][j].ArcVal=arc->ArcVal; G->adj[k][j].ArcInfo=arc->ArcInfo ;
/* 是有向图或带权的有向图*/

} else { G->adj[k][j].ArcVal=arc->ArcVal ; G->adj[j][k].ArcVal=arc->ArcVal ; G->adj[k][j].ArcInfo=arc->ArcInfo ; G->adj[j][k].ArcInfo=arc->ArcInfo ;
/* 是无向图或带权的无向图,需对称赋值 */

} return(1) ; }

7.2.2 邻接链表法
基本思想:对图的每个顶点建立一个单链表,存 储该顶点所有邻接顶点及其相关信息。每一个单链表设 一个表头结点。 第i个单链表表示依附于顶点Vi的边(对有向图是 以顶点Vi为头或尾的弧)。

1 结点结构与邻接链表示例
链表中的结点称为表结点,每个结点由三个域组 成,如图7-9(a)所示。其中邻接点域(adjvex)指示 与顶点Vi邻接的顶点在图中的位置(顶点编号),链域 (nextarc)指向下一个与顶点Vi邻接的表结点,数据 域(info)存储和边或弧相关的信息,如权值等。对于 无权图,如果没有与边相关的其他信息,可省略此域。 每个链表设一个表头结点(称为顶点结点),由两 个域组成,如图7-9(b)所示。链域(firstarc)指向链 表中的第一个结点,数据域(data) 存储顶点名或其他 信息。
表结点: adjvex info nextarc 顶点结点: data firstarc
图7-9 邻接链表结点结构

在图的邻接链表表示中,所有顶点结点用一个向 量 以顺序结构形式存储,可以随机访问任意顶点的链 表,该向量称为表头向量,向量的下标指示顶点的序号。
用邻接链表存储图时,对无向图,其邻接链表是 唯一的,如图7-10所示;对有向图,其邻接链表有两 种形式,如图7-11所示。
v4 0 1 2 3 4 v1 v2 v3 v4 v5 ┇┇ 1 0 0 0 2 2 2 ? 1 2 3 ? 3 ? 3 4 ? 4 ?

v1 v2

v5
v3

MAX_VEX-1
图7-10 无向图及其邻接链表

v1
v2

v4
v5 v3
(a) 有向图

0 1 2 3 4
MAX_VEX-1

v1 2 v2 0 ? v3 3 v4 1 v5 1 ┇┇┇

1 0 2 ? 3 ?

3 ? 1

4 ?

0 1 2 3 4
MAX_VEX-1

v1 1 v2 2 v3 1 v4 2 v5 1 ┇┇┇

2 ? 0 3 ? 0 2 ?

(b) 正邻接链表,出度直观

2 ? 4 ?

(c) 逆邻接链表,入度直观

图7-11 有向图及其邻接链表

2 邻接表法的特点
◆ 表头向量中每个分量就是一个单链表的头结点, 分量个数就是图中的顶点数目; ◆ 在边或弧稀疏的条件下,用邻接表表示比用邻 接矩阵表示节省存储空间;

◆ 在无向图,顶点Vi的度是第i个链表的结点数;
◆ 对有向图可以建立正邻接表或逆邻接表。正邻 接表是以顶点Vi为出度(即为弧的起点)而建立的邻 接表;逆邻接表是以顶点Vi为入度(即为弧的终点) 而建立的邻接表; ◆ 在有向图中,第i个链表中的结点数是顶点Vi的 出 (或入)度;求入 (或出)度,须遍历整个邻接表;

◆ 在邻接表上容易找出任一顶点的第一个邻接点和 下一个邻接点;

3 结点及其类型定义
#define MAX_VEX 30 typedef int InfoType; typedef enum {DG, AG, WDG,WAG} GraphKind ;
/* 最大顶点数 */

typedef struct LinkNode
{ int adjvex ;
置(下标) // 邻接点在头结点数组中的位

InfoType
如权值

info ;

// 与边或弧相关的信息,

typedef struct VexNode { VexType data; int indegree ;
度或没有
// 顶点信息 // 顶点的度, 有向图是入度或出 // 指向第一个表结点 */

LinkNode *firstarc ; }VexNode ; typedef struct ArcType { VexType vex1, vex2 ;
两个顶点 */

/* 顶点结点类型定义

/* 弧或边所依附的

InfoType
如权值

info ;

// 与边或弧相关的信息,

}ArcType ;

/* 弧或边的结构定义 */

typedef struct
{ GraphKind kind ;
/* 图的种类标志 */

int vexnum ;
VexNode }ALGraph ; AdjList[MAX_VEX] ;
/* 图的结构定义 */

利用上述的存储结构描述,可方便地实现图的基 本操作。

(1) 图的创建
ALGraph *Create_Graph(ALGraph * G) { printf(“请输入图的种类标志:”) ; scanf(“%d”, &G->kind) ;

G->vexnum=0 ;
return(G) ;

/* 初始化顶点个数 */

}

(2) 图的顶点定位
图的顶点定位实际上是确定一个顶点在AdjList数 组中的某个元素的data域内容。

算法实现:
int LocateVex(ALGraph *G , VexType *vp) { int k ; for (k=0 ; k<G->vexnum ; k++) if (G->AdjList[k].data==*vp) return(k) ;

return(-1) ;
}

/* 图中无此顶点 */

(3) 向图中增加顶点
向图中增加一个顶点的操作,在AdjList数组的末尾 增加一个数据元素。

算法实现:
int AddVertex(ALGraph *G , VexType *vp) { int k , j ; if (G->vexnum>=MAX_VEX)

{ printf(“Vertex Overflow !\n”) ; return(-1) ; }
if (LocateVex(G , vp)!=-1)

{ printf(“Vertex has existed !\n”) ; return(-1) ; }
G->AdjList[G->vexnum].data=*vp ;

G->AdjList[G->vexnum].degree=0 ;
G->AdjList[G->vexnum].firstarc=NULL ; k=++G->vexnum ;

return(k) ;
}

(4) 向图中增加一条弧
根据给定的弧或边所依附的顶点,修改单链表:无 向图修改两个单链表;有向图修改一个单链表。

算法实现:
int AddArc(ALGraph *G , ArcType *arc)

{ int k , j ;
LinkNode *p ,*q ;

k=LocateVex(G , &arc->vex1) ; j=LocateVex(G , &arc->vex2) ; if (k==-1||j==-1) { printf(“Arc’s Vertex do not existed !\n”) ; return(-1) ; } p=(LinkNode *)malloc(sizeof(LinkNode)) ; p->adjvex=arc->vex1 ; p->info=arc->info ; p->nextarc=NULL ; /* 边的起始表结点赋值 */ q=(LinkNode *)malloc(sizeof(LinkNode)) ; q->adjvex=arc->vex2 ; q->info=arc->info ; q->nextarc=NULL ; /* 边的末尾表结点赋值 */

if (G->kind==AG||G->kind==WAG) { q->nextarc=G->adjlist[k].firstarc ; G->adjlist[k].firstarc=q ; p->nextarc=G->adjlist[j].firstarc ; G->adjlist[j].firstarc=p ; } /* 是无向图, 用头插入法插入到两个单链表 */ else /* 建立有向图的邻接链表, 用头插入法 */ { q->nextarc=G->adjlist[k].firstarc ; G->adjlist[k].firstarc=q ; /* 建立正邻接链表用 */ //q->nextarc=G->adjlist[j].firstarc ; //G->adjlist[j].firstarc=q ; /* 建立逆邻接链表用 */ } return(1);
}

7.2.3 十字链表法
十字链表(Orthogonal List)是有向图的
另一种链式存储结构,是将有向图的正邻接表和逆邻接 表结合起来得到的一种链表。 在这种结构中,每条弧的弧头结点和弧尾结点都 存放在链表中,并将弧结点分别组织到以弧尾结点为头 (顶点)结点和以弧头结点为头(顶点)结点的链表中。 这种结构的结点逻辑结构如图7-12所示。
顶点结 点firstin firstout Data

弧结点
tailvex headvex info hlink tlink

图7-12 十字链表结点结构

◆ data域:存储和顶点相关的信息; ◆ 指针域firstin:指向以该顶点为弧头的第一条弧 所对应的弧结点; ◆ 指针域firstout:指向以该顶点为弧尾的第一条弧 所对应的弧结点; ◆ 尾域tailvex:指示弧尾顶点在图中的位置; ◆ 头域headvex:指示弧头顶点在图中的位置;

◆ 指针域hlink:指向弧头相同的下一条弧;
◆ 指针域tlink:指向弧尾相同的下一条弧; ◆ Info域:指向该弧的相关信息;

结点类型定义
#define INFINITY MAX_VAL
*/
/* 最大值∞

#define MAX_VEX 30 // 最大顶点数 typedef struct ArcNode { int tailvex , headvex ; // 尾结点和头结点
在图中的位置

InfoType


info ;

// 与弧相关的信息, 如权

struct ArcNode *hlink , *tlink ; }ArcNode ; /* 弧结点类型定义 */ typedef struct VexNode { VexType data; // 顶点信息

typedef struct
{ int vexnum ;

VexNode xlist[MAX_VEX] ;
}OLGraph ;
/* 图的类型定义 */

图7-13所示是一个有向图及其十字链表(略去了 表结点的info域)。 从这种存储结构图可以看出,从一个顶点结点的 firstout出发,沿表结点的tlink指针构成了正邻接表 的链表结构,而从一个顶点结点的firstin出发,沿表 结点的hlink指针构成了逆邻接表的链表结构。

V0

V1

0 V0 1 V1

0 1 ∧
2 0

0 2



V2

V3

2 V2 3 V3

2 3 ∧∧
3 1∧ 3 2 ∧∧

3 0∧

图7-13 有向图的十字链表结构

7.2.4 邻接多重表
邻接多重表(Adjacency Multilist)是无
向图的另一种链式存储结构。
邻接表是无向图的一种有效的存储结构,在无向 图的邻接表中,一条边(v,w)的两个表结点分别初选在 以v和w为头结点的链表中,很容易求得顶点和边的信 息,但在涉及到边的操作会带来不便。

邻接多重表的结构和十字链表类似,每条边用一 个结点表示;邻接多重表中的顶点结点结构与邻接表中 的完全相同,而表结点包括六个域如图7-14所示。
顶点结点 表结点

data firstedge

mark ivex jvex info ilink jlink

图7-14 邻接多重表的结点结构

◆ Data域:存储和顶点相关的信息;
◆ 指针域firstedge:指向依附于该顶点的第一条边 所对应的表结点; ◆ 标志域mark:用以标识该条边是否被访问过; ◆ ivex和jvex域:分别保存该边所依附的两个顶点 在图中的位置; ◆ info域:保存该边的相关信息;

◆ 指针域ilink:指向下一条依附于顶点ivex的边;
◆ 指针域jlink:指向下一条依附于顶点jvex的边;

结点类型定义
#define INFINITY MAX_VAL
*/ /* 最大值∞

#define MAX_VEX 30

/* 最大顶点数 */

typedef emnu {unvisited , visited} Visitting ;
typedef struct EdgeNode

{ Visitting mark ;
的位置

// 访问标记

int ivex , jvex ; // 该边依附的两个结点在图中 InfoType


info ;

// 与边相关的信息, 如权

typedef struct VexNode { VexType data;
第一条边 // 顶点信息 // 指向依附于该顶点的 */

ArcNode *firsedge ; }VexNode ; typedef struct { int vexnum ;

/* 顶点结点类型定义

VexNode mullist[MAX_VEX] ;
}AMGraph ;

图7-15所示是一个无向图及其邻接多重表。

邻接多重表与邻接表的区别:
后者的同一条边用两个表结点表示,而前者只用 一个表结点表示;除标志域外,邻接多重表与邻接表表 达的信息是相同的,因此,操作的实现也基本相似。
v1 v2 v4 v3 0 1 2 3 v1 v2 v3 v4 0 2 1 1∧ 0 2 2∧ 3 0∧ 3∧

图7-15 无向图及其多重邻接链表

7.2.5 图的边表存储结构
在某些应用中,有时主要考察图中各个边的权值 以及所依附的两个顶点,即图的结构主要由边来表示, 称为边表存储结构。 在边表结构中,边采用顺序存储,每个边元素由 三部分组成:边所依附的两个顶点和边的权值;图的顶 点用另一个顺序结构的顶点表存储。如图7-16所示。

边表存储结构的形式描述如下:
#define INFINITY MAX_VAL
*/ /* 最大值∞

#define MAX_VEX 30 #define MAX_EDGE 100

/* 最大顶点数 */ /* 最大边数 */

typedef struct ENode
{ int ivex , jvex ; WeightType
*/
/* 边所依附的两个顶点 */ /* */ /* 边的权值

weight ;

}ENode ;

/* 边表元素类型定义

typedef struct { int vexnum , edgenum ;
数 表 */ 顶点数和边

VexType vexlist[MAX_VEX] ;
*/

/*
/*

顶点


ENode edgelist[MAX_EDGE] ;
表 */

}ELGraph ;

6

v0 7

顶点表





v1 9 8 v2 3 2 v3 4 v4

0 1 2 3 4

v0 v1 v2 v3 v4

图7-16 无向图的边表表示

0 0 1 1 2 2 3

1 6 2 7 3 2 4 9 3 8 4 3 4 4

7.3 图的遍历
图的遍历(Travering Graph):从图的某一
顶点出发,访遍图中的其余顶点,且每个顶点仅被访问 一次。图的遍历算法是各种图的操作的基础。 ◆ 复杂性:图的任意顶点可能和其余的顶点相邻 接,可能在访问了某个顶点后,沿某条路径搜索后 又回到原顶点。 ◆ 解决办法:在遍历过程中记下已被访问过的顶 点。设置一个辅助向量Visited[1…n](n为顶点数 ),其初值为0,一旦访问了顶点vi后,使 Visited[i]为1或为访问的次序号。 图的遍历算法有深度优先搜索算法和广度优先搜索 算法。采用的数据结构是(正)邻接链表。

7.3.1 深度优先搜索算法
深度优先搜索(Depth First Search-DFS)遍历类似树的先序遍历,是树的先序遍历的推
广。

1 算法思想
设初始状态时图中的所有顶点未被访问,则: ⑴ :从图中某个顶点vi出发,访问vi;然后找到vi 的一个邻接顶点vi1 ; ⑵:从vi1出发,深度优先搜索访问和vi1相邻接且 未被访问的所有顶点; ⑶:转⑴ ,直到和vi相邻接的所有顶点都被访问为

⑷ :继续选取图中未被访问顶点vj作为起始顶点, 转(1),直到图中所有顶点都被访问为止。

图7-17是无向图的深度优先搜索遍历示例(红色 箭头)。某种DFS次序是:v1→ v3 → v2 → v4 →

v5

v1 v2

v3
v4
(a) 无向图G

v5

0 1 2 3 4
MAX_VEX-1

v1 v2 v3 v4 v5 ┇┇

2 2 0 4 ? 3 ?

1 ? 0 ? 1 ?

(b) G的邻接链表

图7-17 无向图深度优先搜索遍历

2 算法实现
由算法思想知,这是一个递归过程。因此,先设计 一个从某个顶点(编号)为v0开始深度优先搜索的函数, 便于调用。 在遍历整个图时,可以对图中的每一个未访问的顶 点执行所定义的函数。
typedef emnu {FALSE , TRUE} BOOLEAN ; BOOLEAN Visited[MAX_VEX] ;

void DFS(ALGraph *G , int v)
{ LinkNode *p ;

Visited[v]=TRUE ;
Visit[v] ;
/* 置访问标志,访问顶点v */

p=G->AdjList[v].firstarc; /* 链表的第一个结点 */ while (p!=NULL) { if (!Visited[p->adjvex]) DFS(G, p->adjvex) ;
/* 从v的未访问过的邻接顶点出发深度优先搜索 */

p=p->nextarc ; } }

void DFS_traverse_Grapg(ALGraph *G) { int v ; for (v=0 ; v<G->vexnum ; v++) Visited[v]=FALSE ; /* 访问标志初始化 */ p=G->AdjList[v].firstarc ; for (v=0 ; v<G->vexnum ; v++) if (!Visited[v]) DFS(G , v); }

3 算法分析
遍历时,对图的每个顶点至多调用一次DFS函数。 其实质就是对每个顶点查找邻接顶点的过程,取决于存 储结构。当图有e条边,其时间复杂度为O(e),总时间 复杂度为O(n+e) 。

7.3.2 广度优先搜索算法
广度优先搜索(Breadth First Search-BFS)遍历类似树的按层次遍历的过程。

1 算法思想
设初始状态时图中的所有顶点未被访问,则: ⑴ :从图中某个顶点vi出发,访问vi; ⑵:访问vi的所有相邻接且未被访问的所有顶点vi1, vi2,…,vim; ⑶:以vi1,vi2, …,vim的次序,以vij(1≦j≦m) 依此作为vi ,转⑴;

⑷ :继续选取图中未被访问顶点vk作为起始顶点, 转⑴,直到图中所有顶点都被访问为止。
图7-18是有向图的广度优先搜索遍历示例(红色箭头)。 上述图的BFS次序是:v1→ v2 → v4 → v3 → v5
v4 v5 v3 0 1 2 3 4 v1 2 v2 0 ? v3 3 v4 1 v5 1 ┇┇┇

1 0 2 ? 3 ?

3 ? 1 4 ?

v1 v2

(a) 有向图G’

MAX_VEX-1 (b) G’的正邻接链表 图7-18 有向图广度优先搜索遍历

2 算法实现
为了标记图中顶点是否被访问过,同样需要一个访 问标记数组;其次,为了依此访问与vi相邻接的各个顶 点,需要附加一个队列来保存访问vi的相邻接的顶点。 typedef emnu {FALSE , TRUE} BOOLEAN ;

BOOLEAN Visited[MAX_VEX] ;
typedef struct Queue { int elem[MAX_VEX] ;
/* 定义一个队列保存将要访问顶点 */

int front , rear ; }Queue ;

void BFS_traverse_Grapg(ALGraph *G) { int k ,v , w ; LinkNode *p ; Queue *Q ; Q=(Queue *)malloc(sizeof(Queue)) ; Q->front=Q->rear=0 ; /* 建立空队列并初始化 */ for (k=0 ; k<G->vexnum ; k++) Visited[k]=FALSE ; /* 访问标志初始化 */ for (k=0 ; k<G->vexnum ; k++) { v=G->AdjList[k].data ; /* 单链表的头顶点 */ if (!Visited[v]) /* v尚未访问 */ { Q->elem[++Q->rear]=v ; /* v入对 */ while (Q->front!=Q->rear)

{ w=Q->elem[++Q->front] ; Visited[w]=TRUE ; /* 置访问标志 */ Visit(w) ; /* 访问队首元素 */ p=G->AdjList[w].firstarc ; while (p!=NULL) { if (!Visited[p->adjvex]) Q->elem[++Q->rear]=p->adjvex ; p=p->nextarc ; } } /* end while */
} }
/* end if */

} /* end for */

用广度优先搜索算法遍历图与深度优先搜索算法遍 历图的唯一区别是邻接点搜索次序不同,因此,广度优 先搜索算法遍历图的总时间复杂度为O(n+e) 。
图的遍历可以系统地访问图中的每个顶点,因此, 图的遍历算法是图的最基本、最重要的算法,许多有关 图的操作都是在图的遍历基础之上加以变化来实现的。

7.4 图的连通性问题
本节所讨论的内容是图的遍历算法的具体应用。

7.4.1 无向图的连通分量与生成树
1 无向图的连通分量和生成树
对于无向图,对其进行遍历时:
◆ 若是连通图:仅需从图中任一顶点出发,就能访 问图中的所有顶点;

◆ 若是非连通图:需从图中多个顶点出发。每次从 一个新顶点出发所访问的顶点集序列恰好是各个连 通分量的顶点集;

如图7-19所示的无向图是非连通图,按图中给 定的邻接表进行深度优先搜索遍历,2次调用DFS所得 到的顶点访问序列集是: { v1 ,v3 ,v2}和{ v4 ,v5 }
v1 v2 v3 v4
(a) 无向图G

v5

0 1 2 3 4

v1 v2 v3 v4 v5 ┇┇

2 2 0

1 ? 0 ? 1 ?

v1 v2

v3

v4

4 ? 3 ?

v5

(c) 深度优先生成森林

MAX_VEX-1 (b) G的邻接链表 图7-19 无向图及深度优先生成森林

⑴ 若G=(V,E)是无向连通图, 顶点集和边集 分别是V(G) ,E(G) 。若从G中任意点出发遍历时, E(G)被分成两个互不相交的集合: T(G) :遍历过程中所经过的边的集合;

B(G) :遍历过程中未经过的边的集合;
显然: E(G)=T(G)∪B(G) ,T(G)∩B(G)=? 显然,图G’=(V, T(G))是G的极小连通子图,且 G’是一棵树。G’称为图G的一棵生成树。 从任意点出发按DFS算法得到生成树G’称为深度 优先生成树;按BFS算法得到的G’称为广度优先生成 树。

⑵ 若G=(V,E)是无向非连通图,对图进行遍历 时得到若干个连通分量的顶点集:V1(G) ,V2(G) ,…,Vn(G)和相应所经过的边集:T1(G) ,T2(G) , …,Tn(G) 。 则对应的顶点集和边集的二元组: Gi=(Vi(G),Ti(G)) (1≦i≦n)是对应分量的生成树,所有这些生成树构成了 原来非连通图的生成森林。

说明:当给定无向图要求画出其对应的生成树或生成
森林时,必须先给出相应的邻接表,然后才能根据邻接 表画出其对应的生成树或生成森林。

2 图的生成树和生成森林算法
对图的深度优先搜索遍历DFS(或BFS)算法稍作修 改,就可得到构造图的DFS生成树算法。 在算法中,树的存储结构采用孩子—兄弟表示法。 首先建立从某个顶点V出发,建立一个树结点,然后再 分别以V的邻接点为起始点,建立相应的子生成树,并 将其作为V 结点的子树链接到V结点上。显然,算法是 一个递归算法。

算法实现:

(1) DFStree算法
typedef struct CSNode { ElemType data ; struct CSNode *firstchild , *nextsibling ; }CSNode ; CSNode *DFStree(ALGraph *G , int v) { CSNode *T , *ptr , *q ; LinkNode *p ; int w ; Visited[v]=TRUE ; T=(CSNode *)malloc(sizeof(CSNode)) ; T->data=G->AdjList[v].data ; T->firstchild=T->nextsibling=NULL ; // 建立根结点

q=NULL ; p=G->AdjList[v].firstarc ; while (p!=NULL) { w=p->adjvex ; if (!Visited[w]) { ptr=DFStree(G,w) ; /* 子树根结点 */ if (q==NULL) T->firstchild=ptr ; else q->nextsibling=ptr ; q=ptr ; } p=p->nextarc ; } return(T) ;
}

(2) BFStree算法
typedef struct Queue { int elem[MAX_VEX] ; int front , rear ; }Queue ; /* 定义一个队列保存将要访问顶点 */ CSNode *BFStree(ALGraph *G ,int v) { CSNode *T , *ptr , *q ; LinkNode *p ; Queue *Q ; int w , k ; Q=(Queue *)malloc(sizeof(Queue)) ; Q->front=Q->rear=0 ; /*建立空队列并初始化*/ Visited[v]=TRUE ;

T=(CSNode *)malloc(sizeof(CSNode)) ;
T->data=G->AdjList[v].data ;

T->firstchild=T->nextsibling=NULL ; // 建立根结点
Q->elem[++Q->rear]=v ; /* v入队 */ while (Q->front!=Q->rear) { w=Q->elem[++Q->front] ; q=NULL ; p=G->AdjList[w].firstarc ;

while (p!=NULL)
{ k=p->adjvex ; if (!Visited[k]) { Visited[k]=TRUE ;

ptr=(CSNode *)malloc(sizeof(CSNode))
; ptr->data=G->AdjList[k].data ; ptr->firstchild=T->nextsibling=NULL ; if (q==NULL) T->firstchild=ptr ; else q->nextsibling=ptr ; q=ptr ; Q->elem[++Q->rear]=k ; /* k入对 */

} /* end if */ p=p->nextarc ;
}
/* end while p */

} /* end whil Q */ return(T) ;

(3) 图的生成森林算法
CSNode *DFSForest(ALGraph *G) { CSNode *T , *ptr , *q ; int w ; for (w=0; w<G->vexnum; w++) Visited[w]=FALSE; T=NULL ; for (w=0 ; w<G->vexnum ; w++) if (!Visited[w])

相关文章:
数据结构-清华大学严蔚敏PPT.ppt
数据结构-清华大学严蔚敏PPT - 算法与数据结构 教材:《数据结构(C语言版)
3-数据结构-清华大学严蔚敏PPT-栈和队列_图文.ppt
3-数据结构-清华大学严蔚敏PPT-栈和队列_工学_高等教育_教育专区。数据结构
清华大学严蔚敏数据结构_图文.ppt
搜试试 3 帮助 全部 DOC PPT TXT PDF XLS 百度文库 教育专区 高等教育 理学清华大学严蔚敏数据结构_理学_高等教育_教育专区 暂无评价|0人阅读|0次下载|举报...
4-数据结构-清华大学严蔚敏PPT-串_图文.ppt
4-数据结构-清华大学严蔚敏PPT-串_工学_高等教育_教育专区。数据结构第4章
数据结构严蔚敏PPT完整版_图文.ppt
数据结构严蔚敏PPT完整版 - 算法与数据结构 教材:《数据结构(C语言版)》。严蔚敏,吴伟民 编著。清华大学出版社。 参考文献: 1 《数据结构》 。张选平,雷咏梅 ...
数据结构-清华大学严蔚敏PPT - 副本 (1)_图文.ppt
数据结构-清华大学严蔚敏PPT - 副本 (1) - 算法与数据结构 教材:《数
数据结构-清华大学严蔚敏PPT - 副本 (5)_图文.ppt
数据结构-清华大学严蔚敏PPT - 副本 (5) - 第5章 数组和广义表 数组
1-数据结构-清华大学严蔚敏PPT-绪论_图文.ppt
1-数据结构-清华大学严蔚敏PPT-绪论_工学_高等教育_教育专区。数据结构第一
数据结构-清华大学严蔚敏PPT - 副本 (3)_图文.ppt
数据结构-清华大学严蔚敏PPT - 副本 (3) - 第3章 栈和队列 栈和队列
数据结构-清华大学严蔚敏PPT - 副本 (2)_图文.ppt
数据结构-清华大学严蔚敏PPT - 副本 (2) - 第2章 线性表 线性结构是
数据结构严蔚敏PPT(完整版)_图文.ppt
数据结构严蔚敏PPT(完整版) - 算法与数据结构 教材:《数据结构(C语言版)》。严蔚敏,吴伟民 编著。清华大学出版社。 参考文献: 1 《数据结构》 。张选平,雷...
数据结构-清华大学严蔚敏PPT - 副本 (11)_图文.ppt
数据结构-清华大学严蔚敏PPT - 副本 (11) - 第11章 文件与外部排序
数据结构-清华大学严蔚敏_图文.pdf
数据结构-清华大学严蔚敏 - ...... 搜试试 5 悬赏文档 全部 DOC PPT TXT PDF XLS 广告 ...数据结构-清华大学严蔚敏_计算机软件及应用_IT/计算机_专业资料...
严蔚敏版数据结构(C语言版)PPT-第一章_图文.ppt
数据结构》c语言版本 ?参考书:数据结构 严蔚敏清华大学出版社 关于本书内容编写说明数据结构的基本概念(第1章 绪论)线性表(第2章) 基( 本三 部 基本的数据...
数据结构严蔚敏(全部章节814张PPT)_(课件)1_图文.ppt
数据结构严蔚敏(全部章节814张PPT)_(课件)1_理学_高等教育_教育专区。算法与数据结构教材:《数据结构(C语言版)》。严蔚敏,吴伟民 编 著。清华大学出版社。参考...
数据结构-清华大学严蔚敏PPT - 副本 (4)_图文.ppt
数据结构-清华大学严蔚敏PPT - 副本 (4) - 第4章 串 在非数值处理、
清华大学严蔚敏数据结构_图文.ppt
清华大学严蔚敏数据结构 - 数据结构 计算机系 第一章 1.1 1.2 1.3 1.4 绪论 什么是数据结构 基本概念和术语 抽象数据类型的表示与实现 算法和算法分 1.4.1...
数据结构源代码(清华大学+严蔚敏).doc
数据结构源代码(清华大学+严蔚敏) - void Union(List &
数据结构_严蔚敏_清华大学出版社_习题及答案.doc
数据结构_严蔚敏_清华大学出版社_习题及答案 - 第 1 章 绪论 ......
数据结构-严蔚敏_图文.ppt
交流信箱:jxp1972@163.com 3.关于数据结构课程: 教材、重要性、时间安排(64+...数据结构-清华大学严蔚敏... 814页 5下载券 数据结构严蔚敏PPT 814页 5下载...
更多相关标签: