资料结构与演算法  文件类型：PDF/Adobe Acrobat   文件大小：字节

资料结构与演算法
课程教学投影片
第一章–资料结构概论
本章各段大纲
1-1 资料与结构
1-2 资料结构与演算法
1-3 资料结构应用范围
1-1 资料与结构
资料是什麼
–2进位的0与1的讯号
–储存在储存媒体中
–藉由通讯网路或其他方式传送
电脑绝非万能,电脑也会受限於本身的能力
(有限的资料表示方式)
0.1储存在电脑中的数字为何
1-1 资料与结构
循环小数会有什麼问题
1-1 资料与结构
各种程式语言与应用软体会定义它自己使用的资料型态
有了资料型态之后,相同型态类型的资料即可作运算「组
织」起来,这裏所谓的「组织」即是本书要介绍的「结
构」
「资料」类似是建材,「结构」类似於将相同或可结合的
建材组织起来变成一道墙,如果再把「建筑方法」或「建
筑图」加进来才能建造出一座建筑物,而「建筑方法」和
「建筑图」即类似我们程式设计的「演算法」
(Algorithm)和「流程图」
1-1 资料与结构
1-2资料结构与演算法
资料结构的定义:
资料结构所探讨的是在电脑中有效率地存放
资料,使其方便被处理的学问.
演算法的简单定义:
解决问题的方法
1-2资料结构与演算法
范例,下图是美国主要都市的分布图和道路
交通的距离,试问资料该如何安排,才能表
现出有道路相连的城市间距离.
12
3
70
5
4
6
300
8001000
1700
1200
15001000
900
14001000
Los Angeles
San Francisco
Chicago
Boston
New York
Miamy
New Oricans
Deriver
600
1-2资料结构与演算法
范例解答:用二维阵列来表示,阵列元素中有值者代表某起点
到某终点的距离.例如Boston到Chicago的距离是1500,则
在P[4][3]中放入1500.
1-2资料结构与演算法
范例:已知有6笔资料,分别已储存在阵列A
中,请依由小到大排序.
1-2资料结构与演算法
范例:[递回问题-河内塔问题]已知有三个木桩,A,B,C,目前在A木
桩上有3个铁盘,由小到大叠放,在一起,请将这3个铁盘搬到C木桩,但
需遵守下列规则
(1)一次只能搬动一个铁盘.
(2)小的铁盘只能放在大的铁盘上面.
1-3 资料结构应用范围
应用方面:参考本书介绍的内容,有阵列,演算法,程
式设计,搜寻演算法,排序演算法,堆叠,伫列,链结
串列,递回,树,图形,杂凑
学习资料结构应该从最基本的阵列结构的使用及应
用在各种问题上开始;再来是演算法的分析方法及
简单的练习;再进入最常使用的搜寻演算法和排序
演算法
1-3 资料结构应用范围
资料结构与演算法
课程教学投影片
第二章–阵列
本章各段大纲
2-1 何谓阵列
2-2 阵列型式和计量
2-3 阵列的走访
2-4 矩阵运算
2-1 何谓阵列
阵列的结构:
2-1 何谓阵列
阵列的定义:
一组具有相同资料型态(data type)的元
素所组成的有序集合(ordered set).在
电脑中的实体配置空间时,阵列通常储存在
一块连续的记忆体中.阵列包含名称和注
标,注标只有一个时称为一维阵列,注标有
二个时称为二维阵列,以此类推,有n个注
标称为n维阵列.
2-1 何谓阵列
阵列的特性:
–连续的记忆体空间
–搭配一个以上的注标(index)可以方便存取阵
列中的资料
–有一维阵列,二维阵列..可扩充至n维阵列
–在生活上的应用很多,比如使用电脑系统中符号
表和记忆体的对应,可以快速的存取记忆体中的
资料
2-2 阵列型式和计量
阵列形式是指在阵列中所存放元素的资料型
态,例如整数,字元等等.
阵列计量是指计算阵列的储放空间数,(或
称个数)或所占位元组数.
2-2 阵列型式和计量
一维阵列的宣告范例:
intA[10] —C语言,范围从0到9
Dim A(10) As Integer —VB ,范围从0到10
一维阵列的使用范例:
A [0] = k
A [1] = k + 1 * 2 = k + 2
A [2] = k + 2 * 2 = k + 4
A [3] = k + 3 * 2 = k + 6
2-2 阵列型式和计量
二维阵列的宣告范例:
intA[10][10] —C语言
Dim A(10)(10) As Integer —VB
二维阵列的使用范例:
A [0][0] = k
A [1][0] = k + 1 * 2 = k + 2
A [2][0] = k + 2 * 2 = k + 4
A [3][0] = k + 3 * 2 = k + 6
2-2 阵列型式和计量2-2 阵列型式和计量
2-2 阵列型式和计量
范例2-1
宣告intNO[2][3];如
果起始位址182010,则
阵列NO存放再记忆中的
情形如何 又NO[i][j]
的序号为何 位址为
何
2-2 阵列型式和计量
三维阵列的宣告范例:
intA[10][10][10] —C语言
Dim A(10)(10)(10) As Integer —VB
三维阵列的使用范例:
A [0][0][0] = k
A [1][0][0] = k + 1 * 2 = k + 2
A [2][0][0] = k + 2 * 2 = k + 4
A [3][0][0] = k + 3 * 2 = k + 6
2-2 阵列型式和计量
范例2-2:
一个阵列char A[2][3][4],且A的起始位址是
1234,则A[0][2][3]的位址为何 A[i][j][k]的位
址为何
2-2 阵列型式和计量
对角线阵列
2-2 阵列型式和计量
上三角,下三角阵列
2-2 阵列型式和计量
三对角线阵列
2-3 阵列的走访
一维阵列走访:一维阵列的走访只要是利用一个回
圈,走访方法有由小到大,由大到0,奇数,偶数
和索引表走访
范例1:［由小到大］一个阵列NO[10],阵列分别
存入0,1,..,9的值,即NO[i]=i,印示出阵列内的
内容.
For(i=0;i=0;i--)
{
NO[i]=i;
printf("NO[%d]=%d\n",i,NO[i]);
}
2-3 阵列的走访
范例3:［奇偶数走访］一个阵列NO[10],阵列分
别存入9,-8,7,-6,…,1,0的值,印示出阵列内的内
容.
For(i=9;i>=0;i=i-2)
{
NO[i]=i;
printf("NO[%d]=%d\n",
i,NO[i]);
}
For(i=8;i>=0;i=i-2)
{
NO[i]=-i;
printf("NO[%d]=%d\n",
i,NO[i]);
}
2-3 阵列的走访
二维阵的走访:
–由左而右,再由上而下走
–由上而下,再由左而右走
–上下三角形走访
范列1:[对角线走访]只走访对角线元素,例如在
一个5×5的阵列中,(0,0),(1,1),(2,2),
(3,3),(4,4)位置分别放入20,21,23,24的
值(程式请参考2-3-2 二维阵的走访) .
2-3 阵列的走访
范例2:[由左而右,由上而下走访]设计一个4×6的
阵列,以行为主的方式,分别放入0,
1,..........,23的数值(程式请参考2-3-2 二
维阵的走访) .
范例3:[由上而下,由左而右走访]设计一个4×6的
阵列,以列为主的方式,分别放入0,1,2,
3………..,23的数值(程式请参考2-3-2 二维阵的
走访) .
2-3 阵列的走访
范例4:[上三角形走访]设计一个5×5的阵列,走访
上三角形放入数值1,2,3…..,14,15 (程式请
参考2-3-2 二维阵的走访) .
范例5:[下三角形走访]设计一个5×5的阵列,走访
下三角形放入数值1,2,3………..15(程式请参考
2-3-2 二维阵的走访) .
2-4 矩阵运算2-4 矩阵运算
矩阵加法,减法
2-4 矩阵运算
矩阵乘法
2-4 矩阵运算
矩阵转置
资料结构与演算法
课程教学投影片
第三章–演算法
本章各段大纲
3-1 演算法概观
3-2 演算的效率分析
3-3 渐进式表示法
3-1 演算法概观
演算法的定义:演算法是一组可完成特定工作的指
令集合,并且所有的演算法需满足下列条件
–输入(input):可以有多个输入或没有输入.
–输出(out input):至少要有一个输出.
–明确(definiteness):每个指令都是清楚且明确.
–有限(finiteness):在任何情况下,如果逐步追 演
算法的所有指令,演算法应在有限的步骤内结束.
–有效率(effectiveness):原则上每个指令都需简单
到只需用纸和笔即可推演出结果,而且每个指令的运算
不只需要如条件(3)定义的明确,还必须是可实行的
(feasible).
3-1 演算法概观
程式(program)=资料结构(data
structure)+演算法(algorithm)
演算法表示法
–数学式子(expression)表示法
–叙述(statement)表示法
–程式流程图(program flow diagram)表示法
–虚拟码(pseudo code)表示法
3-1 演算法概观
数学式子(expression)表示法
例如:计算摄氏温度C和华氏温度的转换
数学式子程式运算式
C=5/9*(F-32)
F=5/9*C+32
C=5*(F-32)/9
F=5*C/9+32
3-1 演算法概观
叙述(statement)表示法
01
02
03
04
05
06
07
08
09
10
11
main()
{
int sum,data,i;
sum=0
for(i=1;i<=5;i++)
{
scanf("％d"",&data);
sum=sum+data;
}
print f("％d"",sum);
}
3-1 演算法概观
程式流程图(program flow diagram)表示
法
3-1 演算法概观
虚拟码(pseudo code)表示法
仿Pascal语言的虚拟码仿C语言的虚拟码
01
02
03
04
05
06
07
08
09
10
11
12
13
procedure checksum
宣告及设定sum=0
宣告变数i,data为数学型态
for i=1 to 5 step 1
input data
sum=sum+data
end for
if sum mod 2=1 then
output "是奇数"
eles
output "是偶数"
end if
end procedure
void checksum c)
{
int sum=0,
int i,data
for(i=1;i<=5;i++)
{ scanf data
sum=sum+data
}
if (sum％2==1)
printf "是奇数"
else
printf "是偶数"
}
3-2 演算的效率分析
效率的评分方式
–时间复杂度(time complexity):演算法的执
行时间(执行次数,因电脑主机不同,速度会不
一样
–空间复杂度(space complexity):演算法对记
忆体(或储存媒体)空间需求
3-2 演算的效率分析-
排序演算法
的比较排序法平均时间最差情形稳定度额外空间备注
BubbleO(n2)O(n2)稳定O(1)n小时较好
ExchangeO(n2)O(n2)不稳定O(1)n小时较好
SelectionO(n2)O(n2)不稳定O(1)n小时较好
InsertionO(n2)O(n2)稳定O(1)大部份已排序时较好
RadixO(n logRB)O(n logRB)稳定O(n)B是箱子数(0~9)
R是基数(个十百)
ShellO(n log n)O(ns) 1<s<2不稳定O(1)s是所选分组
QuickO(n log n)O(n2)不稳定O(nlogn)n大时较好
MergeO(n log n)O(n log n)稳定O(1)n大时较好
HeapO(n log n)O(n log n)不稳定O(1)n大时较好
TreeO(n log n)O(n2)不稳定O(1)n大时较好
3-2 演算的效率分析-
统计数字次数的
演算法
用逻辑判断统计用阵列指标统计
0102030405060708091011
void ifsum()
{宣告及安排资料NO,ANS
for(i=Dj i<n,i++)
{if(NO〔i〕==1)ANS〔1〕=ANS〔1〕+1;
else if (NO〔i〕==2)ANS〔2〕=ANS〔2〕+1;
else if (NO〔i〕=3)ANS〔3〕=ANS〔3〕+1;
else if (NO〔i〕==4)ANS〔4〕=ANS〔4〕+1;
}for(i=1;i<=4;i++)
输出,i,ANS〔i〕;
}
oid arraysum()
宣告及安排资料NO,ANS
or(i<0;i<n,i++)
NS〔NO〔i〕〕=ANS〔NO〔i〕〕+1;
or(i=1;i<=4;i++)
出i,ANS〔i〕
3-2 演算的效率分析-
统计数字次
数的程式
用逻辑判断统计用阵列指标统计
010203040506070809101112
oid ifsum()
int NO〔100〕,ANS〔5〕,i;
=100
or(i=0;i<n,i++)
if NO〔i〕==1)ANS〔1〕=ANS〔1〕+1;
lse if (NO〔i〕==2)ANS〔2〕=ANS〔2〕+1;
lse if (NO〔i〕==3)ANS〔3〕=ANS〔3〕+1;
lse if (NO〔i〕==4)ANS〔4〕=ANS〔4〕+1;
or(i=1;i<=4;i++)
oid arraysum()
int NO〔100〕,ANS〔5〕,i;
=100
or(i=0;i<n,i++)
NS〔NO〔i〕〕=ANS〔NO〔i〕〕+1;
or(i=1;i<=4;i++)
rintf("％d的次数:％d",i,ANS〔i〕);
3-3 渐进式表示法
时间复杂度等级分类
㏒n<n<n㏒n<n2<n3<2n
3-3 渐进式表示法
Ο表示法
–定义: f(n)=(g（n）)若且唯若存在两个正常数C和
N0,当n≥n0时,f(n)≤c*g(n)
–范例: f(n)=4*n+10,则f(n)可以用Ο(n)来表
示,即g(n)=n
–证明:
要求得f(n)≤c*g(n)
∴4*n+10≤c*n
∴(c-4)*n≥10
所以c=5时→n≥10→n0=10
所以只要c≥5,且n0≥时,则4*n+10≤5*n
只要找得到C和n0,则4*n+10表示为Ο(n).
3-3 渐进式表示法
Ω表示法
–定义: f(n)=Ω(g(n))若且唯若存在两个正整数C
和n0,n≥n0时,f(n)≥c*g(n).
–范例: f(n)=4*n+10,则f(n)可以用Ω(n)来表
示,即g(n)=n
–证明:
要求f(n)≥c*g(n)
∴4*n+10≥c*n
∴(4-n)*n≥-10
∴c=1,n0=1时上式即可成立
∴c=1,n0=1时f(n)=Ω(n).
3-3 渐进式表示法
Θ表示法
–定义: f(n)=g(（n）)若且唯若在多个正数C1,C2和
n0,当n≥n0时,C1* g(n)≤f(n)≤C2* g(n).
–范例: f(n)=4*n+10,则f(n)可以用Θ(n)来表示,
即g(n)=n
–证明:
要求得C1n≤4*n+10≤C2n
由3-4-2节范例1得知C2=5,no=10,满足4*n+10<C2n
由3-4-3节范例1得知C1=1,no=1,满足C1n≤4*n+10
所以存在C1=1,C2=5,no=10,满足Θ(n)=f(n)的定义
所以f(n)=4*n+10=Θ(n)
资料结构与演算法
课程教学投影片
第四章–阵列结构的演算法应用
本章各段大纲
4-1 多项式的运算
4-2 捉大头抽签游戏
4-3 魔术方块
4-4 对奖演算法与资料结构
4-1 多项式的运算
p(x)=anxn+an-1xn-1+…+a1x1+a(运算式)
阵列表示法如下:
012nn+1
P阵列nanan-1...............a1a0
4-1 多项式的运算
p(x)=3x100+2x50+ x25+4 (运算式)
压缩阵列表示法1如下:
压缩阵列表示法2如下:
Index01234
V 43214
W 10050250
012345678
W4310025012540
4-1 多项式的运算
p(x,y)=an0xny0+a(n-1)1xn-1y1+…+a00x0y0(运算
式)
阵列表示法如下:
01234
060504
130000
202000
310000
x0
x1
:
:
xm
y0 y1 …………yn
a00a01
…………a1n
a10a11
…………a2n
am1an2
…………amn
:
:
4-1 多项式的运算
p(x,y)=x100+2x50y50+3x25y50+4y100+5 (运算式)
稀疏阵列表示法1如下:
012345
V512345
XW100502500
YW050501000
4-1 多项式的运算
p(x,y)=x100+2x50y50+3x25y50+4y100+5 (运算式)
稀疏阵列表示法2如下:
0123456789101112131415
V5110
0
02505032550410
0
0500
4-1 多项式的运算
01
02
03
04
05
06
07
08
09
10
/* 演算法名称:两个多项式相加的演算法(两个多项式的项数要相同)*/
/* 输入:二个用阵列代表的多项式*/
/* 输出:用阵列代表的二个多项式相加的结果*/
poyadd(A,B,C,n)
{
int A[n+2],B[n+2],C[n+2],i;
for (i=1;i<=n;i++)
C[i]=A[i]+B[i];
}
0123
A
V
3122
A
W
310
0123
B
V
3223
B
W
320
01234
C
V
C
W
范例:假设有二个多项式A(x)=x3+2x+2,B(x)=2x3+2x2+3,求
C(x)=A(x)+B(x)
4-1 多项式的运算-多项式相加4-1 多项式的运算-多项式相加
4-1 多项式的运算
有关两个多项式相加减的详细演算法(两个多项式
的项数不同),请参考程式4_1.cpp的函式
void polyadd(AV,AW,BV,BW,CV,CW);
polyadd演算法必须走访过所有A,B阵列中的项
目,所以走访次数为A项次数+B项次数,假设A
(x),B(x)多项式的非零项目分别有m1和m2个,
则其时间复杂度为O(m1+m2),0≤m1,m2≤n.最差情况
是m1=m2=n,时间复杂度为O(n)
多项式减法运算的演算法与加法运算的演算法相类
似,只是将加法运算改为减法运算
4-2 捉大头抽签游戏
游戏解释:
捉大头抽签游戏如下一页的附图,最上面一排是参加抽签
者的名字,最下面一排是签号,奖品或工差.每个人依序
顺著直线往下走,当碰到有横线时,即转向横向前进,碰
到直线再往下,以此累堆,则只要横线不要跨过3条直线
(只能跨在二直线之间),则此游戏执行完毕后,最上面
一排的每个人会一一对应到最下面一排的位直,且是1对1
对应.
4-2 捉大头抽签游戏4-2 捉大头抽签游戏
游戏的原理是应用到矩阵的乘法运算,当你每划一条横线
时,即代表这两条直线的资料顺序交换
其实这个游戏的原理是应用到矩阵的乘法运算,当你每划
一条横线时,即代表这两条直线的资料顺序交换.例如上
一页的图中,原来{A0,A1,A2,A3,A4}顺序的资料,经过第0层
横线后的顺序为{A1,A0,A3,A2,A4},再经过第1层横线后的顺
序为{A1,A3,A0,A2,A4},以此类堆,到最后一排的顺序为
{A4,A1,A0,A2,A3},对应到{P0,P1,P2,P3,P4}.
4-2 捉大头抽签游戏4-2 捉大头抽签游戏
捉大头抽签游戏的演算法如下, 其中bighead演算法的时间
复杂度计算是走访M阵列元素的次数,共有
(mr+1)*(mc+1),其时间复杂度为O(mr*mc).
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
/* 演算法名称:捉大头抽签游戏的演算法*/
/* 输入:用阵列代表的资料,mr是最大层编号,mc是最大横线编号*/
/* 输出:捉大头抽签游戏的结果*/
void bighead(A,B,P,M,mr,mc)
{
int i,j;
for(i=0;i<=mr;i++)
for(j=o;j<=mc;j++)
if(M[i][j]==1)swap(B[j],B[j+1]);
for(j=0;j<=mc;j++)
printf("第%d位抽签者,名字%C,对应到签号%d",
B[j],A[B[j]],P[j]);
/*假设A阵列存放字元*/
}
4-3 魔术方块
「魔术方块」是一个古老的问题,它是在一个n×n的矩阵中
填入1到n2的数字,n为奇数,使得每一行,每一列,每条对
角线,横线及直线加总的值都相等,例如图4-4即为3×3和
5×5的魔术方块.
4-3 魔术方块
H.Coxeter提出产生魔术方块的规则如下,且这规
则可用程式来实作.
由1开始填资料,且放在第0列的中间位置,如果是n×n的魔
术方块,则宣告阵列A为此魔术方块,注标编号由0~n-1,
所以中间位置为(n-1)/2.
将魔术方块想像成上下左右相接,往左上角填入下一个数
字,则有下列情况:
(A)位置超出上方范围,则用最底层相对应的位置.
(B)位置超出左边范围,则用最右边相对应的位置.
(C)如果找到的位置已放入资料,则位置调为下一行,同一列位置且放
入下一个数字.
(D)如果找到的位置未放入资料,则放入下一个数字.
4-3 魔术方块
以3×3魔术方块的产生方式为例,说明如
下:
1. (n-1)/2=(3-1)/2=1,所以M[0][1]=1
4-3 魔术方块
2. (0,1)位置往左上的位置为(-1,0),-1
超出范围,调整位置为(2,0),放入2.
4-3 魔术方块
3. (2,0)位置往左上的位置为(1,-1),-1
超出范围,调整位置为(1,2),放入3.
4-3 魔术方块
4. (1,2)位置往左上的位置为(0,1),目前
已有资料,调整位置为往下,新位置为
(2,2),放入4.
4-3 魔术方块
5. (2,2)位置往左上的位置为(1,1),放入
5.
4-3 魔术方块
6. (1,1)位置往左上的位置为(0,0),放入
6.
4-3 魔术方块
7. (0,0)往左上的位置为(-1,-1),-1超出
范围,调整位置为(2,2),但(2,2)已有资
料,所以往下,新位置为(1,0),放入7.
4-3 魔术方块
8. (1,0)往左上的位置为(0,-1),-1超出
范围,调整范围为(0,2),放入8.
4-3 魔术方块
9. (0,2)往左上的位置为(-1,-1),-1超出
范围,调整范围为(2,1),放入9.
4-3 魔术方块
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 演算法名称:魔术方块的演算法*/
/* 输入:一个正方形阵列M和维度n,n必须是奇数*/
/* 输出:魔术方块*/
void square(int *M,int n)
{
int p,q,k;
p=0;
q=(n-1)/2;
M[0][q]=1;
for(k=2;k0)
{
p=(p+1)%n;
M[p][q]=k;
}else{
M[p][q]=k;
}
}
}
4-3 魔术方块
square演算法中由一个回圈所构成,其执行
了n2-1次,时间复杂度为O(n2),而n×n的魔
术方块至少要填入n2个数字,至少须Ω(n2)
的时间,所以square演算法已达解这个问题
的最佳演算法,其时间复杂度可表示为
θ(n2).
4-4 对奖演算法与资料结构
一般对奖的方式有许多型式,例如统一发票对奖
(统一发票号码的后几位与开奖号码相同),序号对
奖(用摇号码球或抽签方式开出中奖号码,再从对
奖资料中找寻是否有相同序号者)及乐透彩对奖.
以台湾发行的乐透彩为例,签注的方式是从1到42
的号码中选出6个不重覆的号码a0,a1,a2,a3,
a4,a5,而主办单位会开出6个号码P0,P1,P2,
P3,P4,P5,外加一个特别号P6,得奖方式如下页
4-4 对奖演算法与资料结构
头奖:如果{ a0,a1,a2,a3,a4,a5}={ P0,P1,P2,P3,
P4,P5},即6个号码完全相同.
贰奖:如果{ a0,a1,a2,a3,a4,a5}中的5个号码出现在
{ P0,P1,P2,P3,P4,P5}中,且另1个号码等於P6.
参奖:如果{ a0,a1,a2,a3,a4,a5}中有5个号码出现在
{ P0,P1,P2,P3,P4,P5}中,且另1个号码不等於P6.
肆奖:如果{ a0,a1,a2,a3,a4,a5}中有4个号码出现在
{ P0,P1,P2,P3,P4,P5}中.
伍奖:如果{ a0,a1,a2,a3,a4,a5}中有3个号码出现在
{ P0,P1,P2,P3,P4,P5}中.
4-4 对奖演算法与资料结构
4-4 对奖演算法与资料结构4-4 对奖演算法与资料结构
第一个演算法,lottol演算法用了三个回圈来比较A和P阵列
的值,总共执行6×6×n=36n的比较次数,时间复杂度为
O(n).
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
/* 演算法名称:对奖的演算法一*/
/* 输入:对奖号码阵列P,签注号码阵列A,n为号码个数*/
/* 输出:对奖结果阵列C*/
void lottol(P,A,C,n)
{
int i,j,k;
for(i=0;i<=n-1;i++)
{
for(j=0;j<=5;j++)
for(k=0;kA[k][0],代表P[0]比较大,则P[0]再准备与下一
个A[k][1]比较,即j=j+1.
–P[0]M[k][j],则j=j+1,回到步骤2.
5如果P[i]<M[k][j],则i=i+1,回到步骤3.
6结束.
4-4 对奖演算法与资料结构4-4 对奖演算法与资料结构
由上述演算步骤和说明可得知lotto2演算法如下
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/* 演算法名称:对奖的演算法二*/
/* 输入:对奖号码阵列P,签注号码阵列A,n为号码个数*/
/* 输出:对奖结果阵列C*/
void lotto2(P,A,C,n)
{
int i,j,k;
for(k=0;k<=n-1;k++)
{
i=o;j=0;
while(i<=6&&jA[k][j])
i++;
else
j++;
}
}
}
4-4 对奖演算法与资料结构
述lotto2演算法用了一个不定回圈while,执行回圈的次数
最少6次(当6个号码都一样时),最多12次(当i,j的值皆从
0开始,逐步递增到6时),如果有n笔资料,则最佳情况是
执行6n次,最差情况是执行12n次,时间复杂度虽然也是
O(n),但是就实际执行次数来看,它比reloto1演算法的固
定36n次,两者相比为1/6~1/3倍,即lotto2较lotto1快3至
6倍.而且lotto2演算法是用到多项式加法polyadd演算法
的原理,所以学习「资料结构与演算法」时,所学习过的
方法或结构,并不是只限用於解决该类问题而已,而是广
泛地吸收各种演算法的原理和结构设计,以利於应用在各
类问题的解答.
4-4 对奖演算法与资料结构
4-4 对奖演算法与资料结构4-4 对奖演算法与资料结构
4-4 对奖演算法与资料结构
01
02
03
04
05
06
07
08
09
10
11
/* 演算法名称:对奖的演算法三*/
/* 输入:对奖号码阵列P,签注号码阵列A,n为号码个数*/
/* 输出:对奖结果阵列C*/
void lotto3(P,A,C,n)
{
int k,j;
for(k=0;k<=n-1;k++)
for(j=0;j<=6;j++)
C[k]=C[k]+P[A[k][j]];
}
4-4 对奖演算法与资料结构
4-4 对奖演算法与资料结构
例如6个号码5,10,15,22,32,42经上述公式换算结果
PM=51015223242.则乐透彩的演算法如下:
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
/* 演算法名称:对奖的演算法四*/
/* 输入:对奖号码阵列P,签注号码阵列A,n为号码个数*/
/* 输出:对奖结果阵列C*/
void lotto4(P,A,C,n)
{
int i,j;
long PM,AM;
PM=0;AM=0;
for(i=0;i<=6;i++)
PM=PM+P[i]*10**(2*i)
for(i=0;i<=n-1;i++)
{
for(j=0;j<=6;j++)
AM=AM+A[i][j]*10**(2*j);
if(PM==AM)
C[i]=C[i]+1;
}
}
4-4 对奖演算法与资料结构
lotto4演算法的执行次数计算包括产生PM的6次,产生AM共
有6n次,比较PM和AM共有n次,所以共有6+6n+n=6+7n次,
时间复杂度是O(n).但lotto4只能比较出数字是否完全一
样,且数字序列必须先排序过,因为第k笔的数字全中时
C[k]=1,否则C[k]=0,而lotto3演算法可由C[k]的值得知
签中几个号码,C[k]的值界於0~6之间.
Lotto4演算法主要是介绍有时候设计演算法时,可以朝数
字系统方向思考,例如第13章介绍的杂凑函数即是利用杂
凑法将资料安排在特定的位置,可利用於资料的搜寻,此
即大家所执知的杂凑搜寻演算法.
4-4-5 问卷调查与电脑阅卷
以电脑阅卷模仿lotto3演算法为例,假设题目皆是选择题,选答有1,
2,3,4四种情况,共有m题,答对者给4分,答错者倒扣1分,则可以宣
告答案的阵列A为二维阵列,第1维是题目序号,第2维是答案序号,阵
列中所存放的值是4或-1,4代表选答正确给4分,-1代表选答错误倒扣1
分,则其结构如下:
4-4-5 问卷调查与电脑阅卷
另考生作答的资料以二维阵列S来存放,第1维是考生序号,第2维是题
目序号,S阵列存放的资料为作答资料,则其阵列结构如下:
4-4-5 问卷调查与电脑阅卷4-4-5 问卷调查与电脑阅卷
电脑阅卷的演算法如下:
01
02
03
04
05
06
07
08
09
10
11
/* 演算法名称:电脑阅卷的演算法*/
/* 输入:A为答案阵列资料,S作答阵列资料*/
/* 输出:K为考生的阵列成绩资料*/
void comexam(A,S,K,m,q,n)
{
int A[m+1][q+1],S[n][m+1],K[n];
for(i=0;i<=n-1;i++)
for(j=0;j<=m;j++)
R[i]=R[i]+A[j][S[i][j]];
}
资料结构与演算法
课程教学投影片
第五章–搜寻演算法
本章各段大纲
5-1 搜寻演算法概观
5-2 线性搜寻法
5-3 二元搜寻法
5-4 插补搜寻法
5-1 搜寻演算法概观
搜寻(search)是指在资料序列中找寻符合特定条件
的资料
筛选功能只是搜寻方法的延伸
作搜寻时,主要是以要搜寻的资料(称为键值[key
value])与资料序列中的资料作比较
搜寻根据运作过程中资料的储存方式分类
–内部搜寻:如果要搜寻的资料可以全部载入记忆体中后再
进行搜寻称为「内部搜寻」
–外部搜寻:如果搜寻的资料量太大,无法全部载入记忆体
中,必须藉助储存设备(例如硬碟或磁带)的空间再进行
搜寻,称为「外部搜寻」
5-1 搜寻演算法概观
分类名称方法
线性搜寻法(Linear Search)资料不用先排序,依指定次序逐一比较.
二元搜寻法(Binary Search)资料一定要先排序好,利用二分法方法,每次搜寻资料范围的中
间位置比较,且调整要搜寻的资料范围.
插补搜寻法(Interpolation Search)资料一定要先排序好,利用内插法,每次找到更适合的位置比
较,且调整要搜寻的资料范围.插补搜寻法是改进二元搜寻法每
次找中间点的缺点,可更快速完成搜寻.
杂凑搜寻法
(Hasing Search)
先将原资料利用杂凑函数建立杂凑表,将要搜寻的资料用同样杂
凑函数运算出位址值,比较此位址的值是否为要搜寻的资料(进一
步还需处理碰撞和溢位问题).
费氏搜寻法(Fibonacci Search)利用费氏搜寻二元树的特性,依树的走访顺序来搜寻资料.
5-1 搜寻演算法概观
搜寻法平均时间
线性搜寻法O(n)
二元搜寻法O(log n)
插补搜寻法O(log n)
杂凑搜寻法O(1)
费伯那西搜寻法O(log n)
5-2 线性搜寻法
线性搜寻法(Linear Search,或称循序搜寻法)是
最简单的搜寻方法
想法:
–利用线性扫瞄方式(一个资料以一定的顺序接著一个资
料的方式)扫瞄一定范围的资料,逐一比较.
–如果要搜寻的资料与比较资料di相同时,则搜寻程序结
束,否则取下一个di+1值,继续比较.
最佳时间是O(1)
平均时间是O(n)
最差时间是O(n)
5-2 线性搜寻法-操作步骤5-2 线性搜寻法-演算法
01
02
03
04
05
06
07
08
09
10
11
12
/* 演算法名称:线性搜寻法*/
/* 输入:整数阵列资料,要搜寻的键值*/
/* 输出:整数阵列资料中搜寻键值的位置*/
int linear_search(int A[],int n,int key)
{ int i=0;
while (iA[mid],代表有可能找到的资料位於mid+1和upper之间.
c)如果key<A[mid],代表有可能找到的资料位於low和mid-1之间.
3.如果不是上述(a)的情况,只要调整要搜寻资料的范围,即情况(b)的
low=mid+1,upper不变;情况(c)的upper=mid-1,low不变.如果
upperx:表示欲搜寻的x必定在mid位置之前,所以调整上界范围为mid-
1,即upper=mid-1.
5-4 插补搜寻法-演算法
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* 演算法名称:插补搜寻演算法*/
/* 输入:整数阵列资料,要搜寻的键值*/
/* 输出:整数阵列资料中搜寻键值的位置*/
int int search(int x)
{
int low=o,upper=max-1,mid; /*max是阵列宣称的维数*/
mid=low+(x=A[low])*(upper-low)/(A[upper]-A[low]);
if(midupper)
mid=upper;
while(low<=upper)
{
if(x=A[mid])
return 1; /*搜寻成功*/
else if(xA[mid])
low=mid+1;
if(low<upper)
mid=low+(x-A[low])*(upper-low)/(A[upper]-A[low])
if(midupper)
mid=upper;
}
return 0; /*搜寻失败*/
}
资料结构与演算法
课程教学投影片
第六章–排序演算法
本章各段大纲
6-1 排序演算法概观
6-2 气泡排序法
6-3 交换排序法
6-4 选择排序法
6-5 插入排序法
6-6 谢尔排序法
6-7 基数排序法
6-8 快速排序法
6-9 合并排序法
6-1 排序演算法概观
排序(sorting)是将一组资料依据资料的特性,将资料由
小到大或由大到小排列的一种资料演算方法
排序法依据排序资料存放位置分类
–内部排序法:把资料全部放在主记忆体内进行排序的方式,此
种排序方法对於少量资料特别有效.
–外部排序法:当资料量多时,无法全部读入主记忆体内去进行
排序,必须借用外部的储存装置,将排序后的部分结果暂存在
辅助记忆体,待资料全部排序完成后,再将排序结果统一输出
的排序方法.
作排序处理时,对於要处理的资料,可能有两个或都个
资料具有相同的值,如果两个相同值在排序前和排序后
的前后位置并未调动,则此排序称为具有稳定性(stable)
排序,否则称为不稳定性(unstable) 排序
6-1 排序演算法概观
排序演算法由技术或结构来分类:
–交换法:利用比较两个资料,然后交换位置.
–插入法:选取某范围内的最小或最大资料,插入适当的位置.
–选择法:选取某范围内的最小或最大资料,安排在适当的位置.
-数字法:根据资料的个位
数,十位数,百位数依序
安排其资料位置,可得排
序结果,不需用到资料的
比较动作.
-树状结构法:利用树状结
构的特性,进行树走访,
输出有次序的资料
6-1 排序演算法概观-
排序法的比较
6-2 气泡排序法
最简单的排序方法之一
它的想法是利用相邻的两资料di和di+1相互比较,如果前
面资料比后面资料大,则将此两资料交换位置(即大气泡在
小气泡上面),然后再以同样方法比较下两个相邻的资料
di+1和di+2,以此累推
平均时间为O(n2)
最差情形为O(n2)
属於稳定排序
额外空间为O(1)
6-2 气泡排序法-操作步骤说明6-2 气泡排序法-操作步骤说明
6-2 气泡排序法-操作步骤说明6-2 气泡排序法-操作步骤说明
6-2 气泡排序法-演算法
01
02
03
04
05
06
07
08
09
10
11
/* 演算法名称:气泡排序*/
/* 输入:排序前的整数阵列资料*/
/* 输出:排序后的整数阵列资料*/
void bubble_sort(int *A)
{ int i,j;
for (i = 0 ; i <= n-2 ; i++)
for (j = 0 ; j A[j+1] )
swap(A[j],A[j+1]);
}
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
/* 演算法名称:加强型气泡排序*/
/* 输入:排序前的整数阵列资料*/
/* 输出:排序后的整数阵列资料*/
void bubble_sort(int *A)
{ int i,j,xflag=0;
for (i = 0 ; (i <= n-2)&&(xflag==0) ; i++)
/* 如果xflag=1代表j回圈内未作任何交换,资料已排序好*/
{ xflag=1;
for (j = 0 ; j A[j+1] )
{ swap(A[j],A[j+1]);
xflag=0;
}
}
}
6-3 交换排序法
最简单的排序方法之一
它的想法:
–利用要排序范围中的第0个资料di与范围中其他资料dj比较,如果前
面资料比后面资料大,则将此两资料交换位置(即较小者放在范围中
的第0个位置),然后再以同样方法比较第0个和dj+1的资料,以此累
推.
–当执行完步骤1时,最小值即位在范围中的第0个位置,利用回圈逐
次缩小要排序的范围,最后可得由小到大的排序.
平均时间为O(n2)
最差情形为O(n2)
属於不稳定排序
额外空间为O(1)
6-3 交换排序法-操作步骤说明6-3 交换排序法-操作步骤说明
6-3 交换排序法-操作步骤说明6-3 交换排序法-演算法
01
02
03
04
05
06
07
08
09
10
11
/* 演算法名称:交换排序*/
/* 输入:排序前的整数阵列资料*/
/* 输出:排序后的整数阵列资料*/
void exchange_sort(int *A)
{ int i,j;
for (i = 0 ; i <= n-2 ; i++)
for (j = i+1 ; j A[j] )
swap(A[i],A[j]);
}
6-4 选择排序法
它的想法:
–第0次在阵列中搜寻出最小的值A[i],A[i]和第0个位置A[0]交换.
–此时剩下n-1个值,同样从其中找出最小的值A[j],A[j]和第1个位
置A[1]交换.
–重复上述步骤,在剩下的范围内找出最小的值和最小阵列注标的资
料交换.此利用回圈逐次缩小要排序的范围,最后可得由小到大的
排序.
平均时间为O(n2)
最差情形为O(n2)
属於不稳定排序
额外空间为O(1)
6-4 选择排序法-操作步骤说明
6-4 选择排序法-操作步骤说明6-4 选择排序法-操作步骤说明
6-4 选择排序法-演算法
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
/* 演算法名称:选择排序*/
/* 输入:排序前的整数阵列资料*/
/* 输出:排序后的整数阵列资料*/
void select_sort(int *A)
{
int i,j,small;
for (i = 0 ; i x)
{
A[j+1] = A[j];
j--;
}
A[j+1]=x;
}
}
6-6 谢尔排序法
它的想法:
–从前面介绍过的气泡排序法,交换排序法,选择排序法,插入排序法四者可
以发现如果资料已大约排序好时,其交换资料位置的动作将会减少,例如在
插入排序法过程中,如果某一资料di不是较小时,则其往前比较和交换的次
数会减少.
–如何用简易的方式先让某些资料有一定的大小次序呢 Donald Shell提出了
先将资料以固定的间隔位置分组(例如每隔4个分成一组,则第1组的资料注标
为0,4,8,...,第2组的资料注标为1,5,9,...以此累推),先排序各分
组中的小部份资料,形成以分组来看资料已排序好;以全部资料来看较小值
已排在较前面(因为各组的最小值已在各分组的最前面),较大值已排在较后
面(因为各组的最大值已在各分组的最后面).
–将初步分组处理过的资料用插入排序法来排序,则资料交换和移动次数可减
少,可得到比插入排序法更好的效率.
平均时间为O(nlogn)
最差情形为O(ns),1<s<2, s是所选分组
属於不稳定排序
额外空间为O(1)
6-6 谢尔排序法-操作步骤说明
6-6 谢尔排序法-操作步骤说明
6-6 谢尔排序法-演算法
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 演算法名称:谢尔排序*/
/* 输入:排序前的整数阵列资料*/
/* 输出:排序后的整数阵列资料*/
void shell_sort(int *A)
{
int i,j,x,hcount,hgroup;
for (hcount = 2 ; hcount < (n/2) ; hcount=hcount*2)
{ // hcount:每个群组的间隔
for (hgroup = 1 ; hgroup x)
{
A[j+hcount] = A[j];
j-=hcount;
}
A[j+hcount]=x;
}
}
}
InsertSort(A); // 最后再作一次插入排序
}
6-7 基数排序法
它的想法:
–先将数字资料A[n]依个位数来分类,放入由数字0,1,2,...9的暂存阵
列D[10][n]中,再由数字的顺序放回原阵列.则此时的资料已依个数
数大小由小到大排序.
–将数字资料A[n]依十位数来分类,放入由数字0,1,2,...9的暂存阵列
D[10][n]中,再由数字的顺序放回原阵列.则此时的资料已依十位数
和个数数大小由小到大排序.
–同理再作百位数,千位数,...即可得由小到大排序好的数字.
平均时间为O(nlogRB), B是箱子数(0~9),R是基数(个十百)
最差情形为O(nlogRB)
属於稳定排序
额外空间为O(n)
6-7 基数排序法-操作步骤说明
6-7 基数排序法-操作步骤说明6-7 基数排序法-操作步骤说明
6-7 基数排序法-演算法01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
/* 演算法名称:基数排序*/
/* 输入:排序前的整数阵列资料*/
/* 输出:排序后的整数阵列资料*/
void radix_sort(int *A)
{
int i,j,k,index,no;
int maxno,digitno;
int nocount[10]={0,0,0,0,0,0,0,0,0,0}; // 数字阵列资料暂存区的计数
int noarray[10][n]; // 数字阵列资料的暂存区
maxno=maxNumber(A); // 取得阵列资料的最大值
digitno=maxdigit(maxno); // 取得数字的最大位数,0代表1位数,1代表2位数...
//for (i=0;i<=digitno;i++)
for (i=0;i<=2;i++)
{
for(j=0;j<=9;j++){ nocount[j]=0; }
for(j=0;j<=n-1;j++)
{// 取出资料的数字
no=digitk(A[j],i);
noarray[no][nocount[no]]=A[j];
nocount[no]=nocount[no]+1;
}
index = 0;
for(j=0;j<=9;j++) // 取出各数字阵列的资料回A阵列
{
for(k=0;k<nocount[j];k++)
{ A[index]=noarray[j][k]; index++; }
}
}
}
6-8 快速排序法
它的想法:
–一般排序法(气泡排序法,交换排序法,选择排序法,插入排序法)一
次回圈都只能减少1个资料量(1个资料已安排在最前面位置),其时间
为O(logn2).
–而谢尔排序法每次只排序分组的资料量,可得到时间为O(log
n5/3),由此可知,如果每次要排序的资料量能大幅减少时,应该效
率越高.
–如果能在安排完1个资料后,让它分成两半,各自再排序这两半的资
料,则效果可更好.快速排序法即是以此想法为出发点.
平均时间为O(nlogn)
最差情形为O(n2)
属於不稳定排序
额外空间为O(nlogn)
6-8 快速排序法-操作步骤说明6-8 快速排序法-操作步骤说明
6-8 快速排序法-操作步骤说明6-8 快速排序法-操作步骤说明
6-8 快速排序法-操作步骤说明6-8 快速排序法-操作步骤说明
6-8 快速排序法-演算法01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 演算法名称:快速排序*/
/* 输入:排序前的整数阵列资料*/
/* 输出:排序后的整数阵列资料*/
void quick_sort(int *A,int left,int right)
{
int low,upper, point;
if(left = upper)
break;
swap(A[low], A[upper]);
}
A[left] = A[upper];
A[upper] = point;
quick_sort(A, left, upper-1); // 对左边进行递回
quick_sort(A, upper+1, right); // 对右边进行递回
}
}
6-9 合并排序法
它的想法:
–由前一个快速排序法得知,如果能将资料分段来处理会有较好的效果,如果用二分法的
概念来看,如果有两个已排序好的资料,利用合并(merge)的方式能变成4个已排序好的
资料,同理4个变成8个,8个变成16个,以此累推,如果总资料量有n个,由前一章的二
分搜寻法的推理得知,有n个资料利用二分搜寻法只要搜寻log2 n次,同理1个合并成2
个,2个合并成4个,4个合并成8个...,合并成n个时,只需合并log2 n次.
–如果每次作合并的过程只需比较资料量的次数,即2个合并成4个时,只需比较4次,n个
资料有n/2对资料,需作n/4次合并,所以总比较次数只需4 x n/4=n次,同理2个n/2资料
量合并成n个资料量时,只需比较n次,则可以说利用合并方法每次产生的新数列,最多
只要比较n次.
–为了配合演算法和程式的方便运作,我们可以利用「各个击破」(divide-and-conquer)
方法,将原先线性的方法调整为将数列分成两个子数列,每一个子数列拥有n/2个资料,
此过程称为分割(divide),用同样的方法再将子数列一直作分割,直到资料量只剩1个
时,这时再利用合并(merge)二个子数列成为一个新数列的方法,一直往上合并所有的子
数列,则最后可得已排序好的数列.
平均时间为O(nlogn)
最差情形为O(nlogn)
属於稳定排序
额外空间为O(1)
6-9 合并排序法-操作步骤说明6-9 合并排序法-演算法
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
/* 演算法名称:合并二个数列合并成新数列的merge演算法*/
/* 输入:二个已经排序过的整数数列*/
/* 输出:排序后的一个整数数列资料*/
void merge(int *A1, int A1_start,
int *A2, int A2_start, int A2_end,
int *A3, int A3_start, int A3_end)
{
int i, j, k=0 , h;
int B[n]; /* 暂存阵列*/
i = A2_start;
j = A3_start;
while(i <= A2_end && j <= A3_end) {
if(A2[i] <= A3[j])
B[k++] = A2[i++];
else
B[k++] = A3[j++];
}
while (i<=A2_end) B[k++]=A2[i++];
while (j<=A3_end) B[k++]=A3[j++];
for(h=0;h<k;h++)
A1[A1_start+h] = B[h];
/* 将暂存阵列中的资料取出存到原本的阵列中*/
}
资料结构与演算法
课程教学投影片
第七章–堆叠
本章各段大纲
7-1 堆叠概观
7-2 堆叠的资料结构
7-3 运算式的应用
7-4 后序表示法求值
7-1 堆叠概观-定义
「堆叠」(stack)是一个抽象的逻辑结构,顾名思义它是
将物件叠放在一起,且一个一个往上堆放(如果以水平方
向来看,它则类似仓库的置物件,物品往里面塞),但要
拿取物件时,则只能从最上层(水平方向则是最外层)取
出,不能从中间取出物件(假如你是堆放碟子时,一般你
也是从上面拿出碟子,不会从中间抽出某个碟子,否则容
易打破碟子).
堆叠的定义:
–堆叠是一个有序串列(ordered list),而且只能在一
个特定的出入口进行资料的增加或删除.
7-1 堆叠概观-特性与应用
堆叠的特性
–先进后出(First in last out,FILO)
–后进先出(Last in first out,LIFO)
–加入元素到堆叠中称为推入(push)
–自堆叠中取出元素称为弹出(pop)
堆叠的应用
–cpu动作
–运算式的处理
–副程式的呼叫
7-1 堆叠概观-范例7-2 堆叠的资料结构
define maxtop100;
char stack[maxtop+1]; 或int
stack[maxtop+1];
inttop=-1;
7-2 堆叠的资料结构
判断堆叠是否已满
if (top==maxtop)
…/*stack已满*/
else
…/*stack未满*/
end if
判断堆叠是否为空
if (top==-1)
…/*stack为空*/
else
…/*stack不为空*/
end if
7-2 堆叠的资料结构
将资料放入堆叠Push
stack[++top]=data;
将资料从堆叠取出Pop
return stack[top--];
7-3 运算式的应用
中序表示法
–当我们把运算式写成((1+2)*3)-4/2)+5,运算子(+,-
,*,/)的左右两边式运算元时,此种式子称为中序表
示法
后序表示法
–后序表示法是将中序表示法中的运算子和运算元素重新
调整顺序,使得运算子放於运算元后面的表示法
前序表示法
–前序表示法和后序表示法相类似,只是运算子的顺序是
在运算元前面
7-3 运算式的应用-运算式范例
7-3 运算式的应用-运算子优先次序
优先顺序运算子
1括号
2负号
3*,/,%
4+,-
5
6==,!=
7&&
8||
7-3 运算式的应用
由中序表示法转换成后序表示法的方法有两
种:
–加括号去除法:这种方法是人类使用的方法,
主要是应付於考试,想快速得到后序表示法时使
用.
–堆叠处理法:由左而右扫描资料,依据资料是
运算元或运算子作不同的处理,运算子还要考虑
其优先次序.
7-3 运算式的应用-
中序转后序,加括号去
除法
7-3 运算式的应用-
中序转后序,堆叠处
理法
7-3 运算式的应用
中序表示法转换前序表示法一样也有两种方
法:
–加括号去除法
–堆叠处理法
7-3 运算式的应用-
中序转前序,加括号去除
法
7-3 运算式的应用-
中序转前序,堆叠处
理法1.由右而左依序取得资料di.
2.如果di是运算元,直接输出.
3.如果di是运算子(含左右括号),则
a.如果di=")",放入堆叠
b.如果di="(",依次输出堆叠中的运算子,直到取出")"为止
c.如果di不是")"或"(",则与堆叠顶点的运算子ds作优先顺序比较
i.di较ds优先时,di放入堆叠,回圈输出堆叠的资料,直到优先次
序相等
ii.di不较ds优先或相等时,ds输出,di放入堆叠
4.如果运算式已读取完成,而堆叠中尚有运算子时,依序由顶端
输出.
7-4 后序表示法求值
1.由左往右扫描字元,一次取出一个资料di.
2.如果di是运算元,放入堆叠.
3.如果di是运算子,依此运算子所需的运算元
个数,从堆叠中取出计算,计算结果再放回
堆叠.
4.如果资料处理完毕,取出堆叠的值,即是答
案.
7-4后序表示法转换机器码
资料结构与演算法
课程教学投影片
第八章–伫列
本章各段大纲
8-1 伫列概观
8-2 伫列的资料结构和操作
8-3 环状伫列
8-4 双向伫列和特殊伫列
8-1 伫列概观-定义
「伫列」(Queue)是一个抽象的逻辑结构,顾名
思义它是将物件排列成队伍,有入口和出口,物件
只能从入口进入,只能从出口出去,类似於排队购
票,排在最前面者比排在后面者先购买到票,不能
从中间插队.
定义
–伫列是一个有序串列(ordered list),而且所有加入
的动作只能在一个特定的入口进行,删除的动作只能在
一个特定的出口进行.
8-1 伫列概观-特性
先进先出(first in first out,FIFO)
后进后出(last in last out,LILO)
加入元素到伫列中称为加入(Addition)
自伫列中删除元素称为删除(Delete)
8-1 伫列概观-范例8-1 伫列概观-运用
列印伫列
键盘缓冲区的应用
副程式的呼叫
8-2 伫列的资料结构和操作
define maxq100;
char queue[maxq];
intfront =-1;
intrear =-1;
8-2 伫列的资料结构和操作
判断伫列是否已满
if (rear==maxtop-1)
…/*伫列已满*/
else
…/*伫列未满*/
end if
判断伫列是否为空
if (rear==front)
…/*伫列为空*/
else
…/*伫列不为空*/
end if
8-2 伫列的资料结构和操作
将资料放入伫列
if (isfull())queuefull()
/*isfull()检查是否queue已满*/
else queue[++rear]=data /*queuefull()是作相关处理*/
将资料从伫列取出
if (isempty())/*isempty是检查伫列是否已空了*/
{
queueempty();
/*queueempty是伫列空时,又要取出资料的处理*/
return 0;/*传回0代表失败*/
}else return queue[++front];
/*一切正常front,加1,且传回资料*/
8-3 环状伫列
线性伫列中「已删除区域」其实它是
空的,只要我们从前端front和后端
到达伫列阵列指标的最大值时,能再
从左边编号.开始控制增加或删除资
料时,则这个伫列就可以一直运转,
除非这个伫列真的每个位置都放满资
料,才是真的「伫列已满」,或真的
伫列中都没有资料可供删除时,才是
真的「伫列已空」.这种伫列结构称
为环状伫列(circular queue).
8-3 环状伫列-演算法
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 演算法名称:addcq & delcq */
/* 输入:*/
/* 输出:*/
defint cmaxq 100;
char cqueue[cmaxq];
int cfront=-1;
int crear=-1;
void addcq (int data)
{
if (iscfull()) cqueuefull()
else cqueue [++rear%cmaxq]=data
}
int delcq()
{
if (iscempty())
{
cqueueempty();
return 0;
}
else return cqueue[++cfront%cmaxq];
}
8-3 环状伫列-演算法
01
02
03
04
05
06
07
08
09
/* 演算法名称:iscEmpty */
/* 输入:*/
/* 输出:*/
int iscEmpty()
{
if (rear==ftont) return 1; /*1代表伫列已空*/
else return 0; /*0代表伫列未空*/
}
01
02
03
04
05
06
07
08
09
10
/* 演算法名称:iscfull */
/* 输入:*/
/* 输出:*/
int iscfull()
{
if (rear+1=ftont) return 1; /*1代表伫列已满*/
else return 0;
/*0代表伫列未满*/
}
8-4 双向伫列和特殊伫列
特殊伫列
–重点在於改变先前介绍的addq()或addcq演算法
–例如,假如将伫列结构应用在医院诊所的挂号
系统,如果求诊者一视同仁,都按照挂号编号看
诊,则当有需要急诊之某一病患,或者有优先权
较高者可以把要处理的先放到伫列的最前面,这
样在从伫列取出时就可以最先取出了
8-4 双向伫列和特殊伫列
双向伫列
–线性伫列和环状伫列只能有唯一的入口和唯一的出口,
此称为单向伫列(single-end-queue),伫列可加以变
化成为两端都可入口和出口的双向伫列(double-end-
queue,dqueue).
–双向伫列是扩充原先前端front只能删除资料,后端rear
只能增加资料的功能,让前端front可能加入资料,后端
rear也能删除资料,因此可改为左端(left)和右端
(right).Left或right要加入资料或删除资料是由你
设计的程式来控制.
资料结构与演算法
课程教学投影片
第九章–链结串列
本章各段大纲
9-1 链结串列概观
9-2 单一链结串列以阵列表示
9-3 双向链结串列以阵列表示
9-4 链结串列用指标和结构来表示
9-5 链结串列应用在其它结构
9-1 链结串列概观
串列的定义:串列(list)的抽象观念是指一
组相同资料型态元素的有序集合.
例子如下
–正奇数串列(1,3,5,7,9,……).
–正偶数串列(2,4,6,8,10,……).
–费伯那西数串列(1,1,2,3,5,8,……).
–正质数串列(2,3,5,7,11,13,……).
–大写英文字母串列(A,B,C,D,……,X,Y,Z).
9-1 链结串列概观
串列的应用
–因为串列中的元素是有次序的,一般串列中元素的排列
次序是由小而大,例如正整数串列的1<2<3<4
–有序的串列应用到电脑中的情况则有ASCⅡ码,如
A<B<……Z<a<b<……<z
练习1:
(a)ASCⅡ码中A的下1个B,则第10个是什麼
(b)ASCⅡ码中A的号码是65,则Z的号码为多少
解答:(a) K (b) 90
9-1 链结串列概观
在资料处理或资料结构的领域中,对於一些资料(或数字),我们可以利
用类似箭头的链结(link)将资料统合起来,可以一个连到下一个,而形
成有次序的资料(或数字),则此结构称为链结串列(linked list).
链结串列定义:链结串列(link list)是一种有顺序的串列,且资料项应
包含链结(link),可以链结到其它资料.此资料项称为节点,其型式
为.
(1)
(2)顺著链结的顺序则为
3226249511
9511322624
9-1 链结串列概观
链结串列有以下的特性:
–链结串列一般可以用阵列结构型式来表示.
–节点顺序在记忆体中的实际位址可以不连续,或者是经由随机配
置,不像阵列的元素在记忆体中的实际位址是连续的.
依链结的型式不同,链结串列分为下列几类:
–单向链结:节点之间按顺序,一个链结一个.最后没有链结者,其
link值为Null或特定值.
–环状链结:同单向链结的型式,但是最后一个节点指向第1个节点.
–双向链结:节点包含资料和左右两个链结.
–树状链结:链结的型式如树状结构.
–图形链结:链结的型式如图形结构.
9-1 链结串列概观
单向链结
9-1 链结串列概观
环状链结
9-1 链结串列概观
双向链结
9-1 链结串列概观
树状链结
9-1 链结串列概观
图形链结
9-1 链结串列概观
链结串列的应用:
假如我们用阵列存放了某些数值资料,且依大小排序,如果此阵列在程
式运作中,会删除,增加,修改资料,且需要重新排序,例如原有资料
量n个,则由第6章排序方法得知排序演算法的时间是O(nlog n)或是
O(n2),但那些演算法都是针对固定的资料来排序.对於由上述问题资
料异动很频繁(例如有m次)时,每作一次资料异动(删除,增加,更新)
都要重新排序,则每次的时间都是O(n2)的话,则共需O(mn2),这在实
务应用上并不实际,但如果用链结串列结构来处理,则资料异动的时间
只在有限次数内,时间是O(1),如果加上搜寻到资料再异动时,搜寻的
最差时间是O(n),所以总共的异动时间为O(mn),这比O(mn2)或O(mn
log n)有效率
前两章介绍的堆叠,伫列也可以利用链结串列来表示其结构.只要资料
异动频繁且要维持其定义的次序性,都适合用链结串列.
9-2 单一链结串列以阵列表示
链结阵列的宣告方式如下
#define maxsize100;
intA〔maxsize〕〔2〕;
inthead;另外需要一个独立的变数来存放一个阵列的起始点
-1代表空链结
data
lin k
A
01 2
30 20 50 401030 20 50 4010
4
3
30 20 50 401030 20 50 4010
01 2
14-13214-132
4
3
原资料
排序
链结阵列原资料
排序
链结阵列
9-2 单一链结串列以阵列表示
寻找节点演算法说明图
3
0
11
30
5
50
4
20
-132
40 60100
11
30
5
50
4
20
-132
40 6010
01 2 4 5 6
Data=35,要找比data小的最后1个位置
A[0][0]=10 < data
link=A[1][0]=2 , ans=0
(1)link=head=0
(2)link=2 A[0][2]=20 < data(2)link=2 A[0][2]=20 < data
link=A[1][2]=4 , ans=2
(3)link=4 A[0][4]=30 data
传回4
head=0
9-2 单一链结串列以阵列表示
节点寻找的演算法如下
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
/* 演算法名称:节点寻找的演算法*/
/* 输入:要寻找的data */
/* 输出:找到的值或找不到的讯息*/
int lsearch(int data)
{ link=head;
ans=-1;
for (i=0, idata)
return ans;
else
{ ans=link;
link=A[1][link];
}
}
return ans; /* 已经看到最后面,没有资料了,回传失败*/
}
9-2 单一链结串列以阵列表示
新增节点演算法图解1
9-2 单一链结串列以阵列表示
新增节点演算法图解2
9-2 单一链结串列以阵列表示
新增节点演算法图解3
9-2 单一链结串列以阵列表示
新增节点演算法图解4
9-2 单一链结串列以阵列表示
新增节点linsert演算法01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 演算法名称:新增节点linsert演算法*/
/* 输入:节点资料*/
/* 输出:节点资料*/
int linsert(int data,int n)
{
for (i=0;i<=n-1;i++)
{
ANS=lsearch(data[i]);
if (ANS==-1)
{
A[0][i]=data[i];
A[1][i]=head;
head=i;
}
else
{
A[1][i]=A[1][ANS];
A[1][ANS]=i;
A[0][i]=data[i];
}
}
}
9-2 单一链结串列以阵列表示
新增单一节点演算法图解1
9-2 单一链结串列以阵列表示
新增单一节点演算法图解2
9-2 单一链结串列以阵列表示
新增单一节点ladd( )的演算法如下
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
/* 演算法名称:新增单一节点ladd( ) */
/* 输入:节点资料*/
/* 输出:节点资料*/
void ladd(data, i)
{
ANS=lsearch(data);
if (ANS==-1)
{
A[0][i]=data[i];
A[1][i]=head;
head=I;
}
else
{
A[1][i]=A[1][ANS];
A[1][ANS]=i;
A[0][i]=data;
}
}
9-2 单一链结串列以阵列表示
删除某个节点
删除节点j
jiji
原图
kjkj
kiki
删除节点j
A[1][i]
A[1][j]
==kk
A[1][i]
=A[1][j]
k
9-2 单一链结串列以阵列表示
删除根节点
删除节点j
jj
kk
head= A[1][j]
head
jj
原链结
kk
head
删除根节点
9-2 单一链结串列以阵列表示
删除节点演算法图解1
9-2 单一链结串列以阵列表示
删除节点演算法图解2
9-2 单一链结串列以阵列表示
ldelete( )演算法如下
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
/* 演算法名称:删除节点ldelete()*/
/* 输入:节点资料*/
/* 输出:节点资料*/
ldelete(data)
{
link=head; j=-1;
for(X=0; X 35(2)plink=3 A[0][3]=50 > 35
plink=A[2][3]=1 , Ans=3
(3)plink=1 A[0][1]=40 > 35
plink =A[2][1]=4 , Ans=1
(4)plink=4 A[0][4]=30 < 35
传回An s=1
9-3 双向链结串列以阵列表示
dlpsearch( )演算法
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
/* 演算法名称:双向链结串列搜寻节点dlpsearch */
/* 输入:节点资料*/
/* 输出:节点资料*/
int dlpsearch(data)
{
plink=tail;
for (i=0;iA[1][i]=A[1][ANS]
(2)y原先是A[2][A[1][ANS]]
->y'=A[2][A[1][ANS]]
->A[2][i]=A[2][A[1][ANS]]
(3)A[1][ANS]=i
(4)A[2][A[1][ANS]]=i
(5)A[0][i]=data
双向链
结新增
节点图
解说明
3
2
1
05030401020
-12403
1203-12
1
05030401020
-12403
1203-1
01 2 4
data
next
pr ev
56
head=1
tail=4
10104040303020205050
01324
加入35,->由dlpsearch(35)传回ANS=3(假设next=1,pr ev= 2),目前i= 5
30304040
23x
30 530 5
35323532
4040
(4)(3)
(2)y'
(1)x'
23
30 230 2403403
23x
30 530 5
35323532
405405
(1)x'(2) y'
z' z'
23
y
5
所以录结阵列为
3
355030401020
2-12403
13203-1
355030401020
2-12403
13203-1
01 2 4 5
head=1
tail=4
(1)A[n ext][i]=A[n ext][ANS]
->A[1][5]=A[1][3]=2
(2)A[prev]A[i]=A[prev][A[n ext][ANS]]
->A[2][2]=3
(3)A[n ext][ANS]=I
->A[1][3]=5
(4)A[prev][A[1][ANS]]=5
->A[2][2]=5
(5)A[0][i]=35
9-3 双向链结串列以阵列表示
双向链结新增单一节点的演算式dlpadd( )如下
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/* 演算法名称:双向链结新增单一节点的演算式dlpadd( ) */
/* 输入:节点资料*/
/* 输出:节点资料*/
void dlpsearch(data, i)
{
int ANS;
int next=1,prev=2;
ANS=dlpsearch(data);
if (ANS==-1)
{
A[0][i]=data;
A[prev][i]=tail;
A[next][i]=-1;
A[1][tail]=i;
tail=i;
}
else
{
A[next][i]=A[next][ANS];
A[prev][i]=A[prev][ A[next][ANS] ];
A[next][ANS]=i;
A[prev] [ A[1][ANS] ]=i;
A[0][i]=data;
}
}
9-3 双向链结串列以阵列表示
双向链结删除一般节点图解说明
jik
y'
x'
x'=A[next][j]
y'=A[prev][j]
x'i
y'
k
删除j
因为是找到j,所以i=A[prev][j],k=A[next][j]
(1)建立x'於i->A[next][A[prev][j]=A[next][j]
(2)建立y'於k->A[prev][A[next][j]=A[prev][j]
双向链
结删除
前端尾
端节点
图解说
明
k
head
jz'
Null
删除j
k
head
Null
z'
删除尾端节点
Null
tail
删除尾端节点
Null
tail
k
z'
kz'j
因为是找到j
k=A[next][j]
因为z'=A[next][j]
所以head=A[next][j]
A[prev][A[next][j]]=-1
因为是找到j,所以k=A[next][j]
因为z'=A[prev][j]
所以tail=A[prev][j]
A[next][A[prev][j]]=-1
dldelete( )演算法的
图解说明
3
2
1
05030401020
-12403
1203-12
1
05030401020
-12403
1203-1
01 2 4
datanextprev
56
101030302020
013
head=-1
tail=4
4040
2
5050
4
head
tail
(1)删除10,因为找到j,所以k=A[next][j]=0
->head=A[next][j]=0
A[prev][A[next][j]]=A[2][0]=-1
2020
0j
head
k
3
2
1
05030401020
-12403
1203-12
1
05030401020
-12403
1203-1
01 2 456
head=0
tail=4
(2)删除50,因为找到j,j=4,所以k=A[prev][j]=A[2][4]=2
->tail=A[prev][j]=A[2][4]=2
A[next][A[prev][j]]=A[1][2]=-1
3
2
1
05030401020
-12403
1203-12
1
05030401020
-12403
1203-1
01 2 4 5 6
head=0
tail=2
4040
2
5050
tail
k
(3)再删除30,因为找到j,所以j=A[prev][j]=A[2][3]=0
k=A[next][j]=A[1][3]=2
建立x'於i->A[next][A[prev][j]]=A[next][j]
->A[1][0]=A[1][3]=2
建立y'於k->A[prev][A[next][j]]=A[prev][j]
->A[2][2]=A[2][3]=0
3
2
1
05030401020
-12403
1203-12
1
05030401020
-12403
1203-1
01 2 4 5 6
2020
6
3030
3
4040
2
ijk
y'
x'
9-4 链结串列用指标和结构来表示
链结串列用阵列表示的问题:
–用阵列来表示链结串列,因为阵列有注标可直接存取阵列中的资
料,但是当你宣告的阵列太小时,可能程式运作中会碰到无空间可
放资料的已满情况;或者宣告太大时,当程式并不会用到那麼多空
间时,又会浪费空间,你或许会说:「现在的记忆体空间,差不多
是28MB,256MB…,浪费一点点空间有何关系」.
–但是在设计程式时要考虑其移植性,即由个人电脑的作业环境移植
到随身和行动设备等只有少量资源的环境时,记忆体空间的计较就
成为很重要的课题了.
要解决固定阵列宣告所造成的不便时,一般有两种方法可克服:
–使用动态阵列:不要宣告阵列大小,只要宣告型态
–使用指标和结构:利用结构定义资料和指标,利用类似(structnode
*)malloc(sizeof(node)) 的函式,当需要存放空间时,再从记忆体取得.
9-4 链结串列用指标和结构来表示
结构宣告和使用
struct stu_struct
{
ch ar stu_n o[6];
char stu_name[20];
int stu_score;
}
typedef struct stu_struct stu_record;
char stu_no[6];
char stu_name[20];
in t stu_score;
使用:
xscore=stu_score
结构名称
结构中的元素
结构宣告
宣告结构变数结构变数名称
typedef stu_record xrecord;
在程式中要使用时宣告xrecord my_record;
xscore=my_record->stu_score
结构变数中的变数
9-4 链结串列用指标和结构来表示
如果定义了结构,也可以使用阵列变数来使
用结构,例如宣告一个有100笔资料的stu-
struct时,其宣告方式为:
xrecordmy_record[100];
则将成绩yscore放入第i个结构阵列中时,
其陈述句如下:
my_record[i]->stu_score=yscore;
9-4 链结串列用指标和结构来表示
链结串列之结构宣告
9-4 链结串列用指标和结构来表示
需要置配记忆体空间时,要引入标头档等和malloc函式,
如下:
#include
..{
head=(LINKLIST*) malloc(sizeof(LINKLIST));
if(head==NULL) /* 在这边要确认是否有要到合法的记忆体*/
Do Error Handling; /* 如果指标指向NULL表示现在记忆体不
足*/
else
node=head;/*node和head可指向同一位置*/
}
9-4 链结串列用指标和结构来表示
当删除节点时,要将记忆体空间释放,否则那些空间将会无法使用而浪
费,可在程式中使用free( )函式,如下:
…
free(node);
…
链结串列用指标结构建立3个节点,图解1
链结串列用指标结构建立3个节点,图解2 链结串列用指标结构建立3个节点,图解3
(7)node的指标指向newnode,newnode的data放入30,
newnode指标指向NULL
node->next=newnode
newnode->data=30
newnode->next=NULL
(8)将node移到newnode位置
node=newnode
10head10head
node
2020
newnode
3030
10head10head
node
2020
newnode
3030
9-4 链结串列用指标和结构来表示
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
/* 演算法名称: 建立链结演算法*/
/* 输入: 节点资料*/
/* 输出: 链结串列*/
#include
typedef struct str_link
{
int data;
struct str_link*next
}LINKLIST
void main( )
{
int A A[100];
int i, count;
LINKLIST *head,*node,*newnode;
A[0]=10;A[1]=20, A[3]=30;count=3 /*假设有3个资料要建立链
结串列*/
/*建立第1个节点*/
node=(LINKLIST*)malloc(sizeof(LINKLIST));
head=node;
Node->data=A[0];
Node->next-NULL;
for(i=1;inext=newnode;
newnode->data=A[i];
newnode->next=NULL;
node=newnode;
}
}
走访节点:由范
例可以知道要链
结下一个节点
时,只要用
node->next,要
存取节点资料则
用node->data,
要将节点node移
到它链结的节点
则用
node=node-
>next,某节点
要移到起始节点
时,则用node=
head.
101020 20 3030head
(1)node=head
(3)node->nextNULL->输入20,node=node->next
101020 20 3030head
node
(2)node->nextNULL->输出10,node=node->next
101020 20 3030head
node
101020 20 3030head
node
(4)node->nextNULL->回圈结束
(5)输出30
9-5 链结串列应用在其它结构
链结堆叠
链结堆叠和堆叠一样有一个top指标用来指示顶端位置,其节点结构一
样是资料链结,而且一样只能从顶端加入或删除节点.所以其实
链结堆叠可以说是链结串列的有限功能(链结串列可对任意节点进行新
增和删除功能),其结构定义如下:
typedefstructstr_linkstack
{intdata;
structstr_linkstack*next;
}LINKSTACK
LINKSTACK *top, newnode, node;
top
链结堆叠链结堆叠的push动作之函式lspush( )
的图解说明如下.
1010
2020
5050
55
:
top
top
加入新节点5
(4)(2)
(3)完成
55
1010
5050
:
top
2020
(1) newnode=(LINKSTACK *)
malloc(sizeof(LINKSTACK));
(2) newnode->data=5;
(3) newnode->next=top;
(4) top=newnode;
链结堆叠push动作:lspop( )在pop资料时,需检查是否
top==NULL,检查堆叠是否已经空了,如困未空再将top
指标指到下一个节点,且释放掉目前的节点,其图解说
明如下.
1010
2020
5050:
top
删除节点
1010
2020
5050:
(4)
top
完成
2020
5050
:
top
(1)假如top==NULL
代表堆叠已空,结束返回
(2)node=top;
(3)xdata=top->data;
(4)top=top->next;
(5)free(node)
(2)
node
9-5 链结串列应用在其它结构
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
/* 演算法名称:lspush( )和lspop( )演算法*/
/* 输入:节点资料*/
/* 输出:节点资料*/
typedef struct str_linkstack
{
int data;
struct str_linkstack *next;
}
LINKSTACK
LINKSTACK *top, *node, *newnode;
Void lspush(int xdata)
{
newnode=(LINKSTACK *) malloc(sizeof(LINKSTACK));
newnode->data=xdata;
newnode->next=top;
top=newnode;
}
int lspop( )
{
if (top==NULL)
{
lsempty( );return-1;
}
else
{
node=top;
xdata=top->data;
top=top->next;
free(node);
return xdata;
}
}
9-5 链结串列应用在其它结构
链结伫列(linked queue)同样是以链结串列来表示伫列,
在了解上一小节用链结指标处理链结堆叠后,此部份链结
伫列的lqadd( )(从尾端rear加入节点),lqdel( )(从前端
front删除节点)的动作和链结堆叠的lspush( )和lspop( )
相类似,如下图.
front rear
……
9-5 链结串列应用在其它结构
链结伫列可也以看成是链结串列的有限功能,它只能在固定的前端
(front)和后端(rear)加入或删除节点,但检查伫列是否已空时,不是
先前介绍的检查front和rear的关系:
front == rear-1
而是检查front的指标是否指到NULL.另外当伫列是空的时候,加入第
一个节点时front和rear设定为相同指标位置,之后front和rear即可个
别动作了.
链结伫列的结构定义如下:
typedefstructstr_linkgueue
{
intdata;
structstr_linkgueue*next;
}LINKQUEUE
LINKQUEUE *front, *rear, newnode, node;
9-5 链结串列应用在其它结构
链结伫列加入节点之函式lqadd( )的图解1
9-5 链结串列应用在其它结构
链结伫列加入节点之函式lqadd( )的图解2
9-5 链结串列应用在其它结构
链结伫列要删除节点时,要先检查伫列是否是空了,如困未空,则只要
将front指标指到下一个节点,且释放原节点,其图解说明如下
9-5 链结串列应用在其它结构
链结伫列要删除节点图解2
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
/* 演算法名称:链结伫列删除节点*/
/* 输入:节点资料*/
/* 输出:节点资料*/
typedef struct str_linkqueue
{
int data;
struct str_linkqueue *next;
}
LINKQUEUE
LINKQUEUE *front, *rear, *node, *newnode;
void lqadd(int xdata)
{
newnode=(LINKQUEUE *) maloc(sizeof(LINKQUEUE));
if(rear==NULL)
{
rear=newnode;
front=rear;
}
else
{
rear->next=newnode;
rear=newnode;
}
rear->next=NULL;
rear->data=xdata;
}
int lqdel( )
{
if (front==NULL)
{
lqempty();
return-1;
}
else
{
node=front
xdata=front->data
front=front->next
}
free(node);
}
9-5 链结串列应用在其它结构
链结串列可以说是阵列表示法的另一种替代
方案,只要你熟练结构和指标的应用,它也
是一种简单的资料表示方法,且可随机配置
记忆体空间,不会受限於阵列大小的宣告
在第11章树状结构中,同样可以用阵列或链
结串列两种方式来表示
dataleft rightdataleft right
dataleft rightdataleft rightdataleft rightdataleft right
dataright leftdataright leftdataleft rightdataleft rightdataleft rightdataleft right
链结树的表示方式如下
资料结构与演算法
课程教学投影片
第十章–递回
本章各段大纲
10-1 递回关系
10-2 数学问题
10-3 河内塔问题
10-4 迷宫问题
10-1 递回关系
for和while回圈
10-1 递回关系
for回圈可利用sum存放1+2+…+k的值,由i
来控制k,其推演方法如下
10-1 递回关系
以数学模式来表示时,其实是:f(k)=f(k-
1)+k,1<=k 0,n=m,m=j,回到步骤1.
3.如果j = 0,则m是最小公倍数.
10-2 数学问题
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
/* 演算法名称:最小公因数演算法gcd(n,m) */
/* 输入:二个整数键值*/
/* 输出:输出最小公因数*/
void main()
{ int a,b;
a=54;b=42;
if(a>b) printf("d%",gcd(a,b));
else printf("%d",gcd(b,a));
}
int gcd(n,m)
{ int j;
j=n % m;
while(j>0)
{ n=m;
m=j;
j=n % m;
}
return m;
}
10-2 数学问题
10-2 数学问题
范例3:求54,42的最小公倍数
解答:
–第1次呼叫:gcd(54,42) = gcd(42,54 % 42)
gcd(42,12)
–第2次呼叫:gcd(42,12) = gcd(12,42 % 12)
gcd(12,6)
–第3次呼叫:gcd(12,6) = gcd(6,12 % 6) gcd(6,0)
最小公因数6
10-3 河内塔问题
河内塔问题(Tower of Hanoi)是一个典型的递回演算法
问题,也是一个益智问题,相传有一座古庙,庙中有三根
木桩,共有24个铁盘由小至大在其中一根木桩上,且流传
著一个传说:「如果有一天能把24个铁盘从其中一个木桩
移到另一根木桩,且必须导守下列规则:(1)每天只能搬动
一个铁盘,(2)只能从最上层搬动,(3)必须维持较小的铁
盘在较大的铁盘上方.如果有朝一日能够完成这项工作,
则世界将会永久和平」.
这个问题要能够被完成共需224-1次的搬动,即16777215次
的搬动,每天只能搬一个铁盘,若一年用365天来计算,则
共需45965年.
河内塔问题图解
ABCABCABCABC
1
23
1
3121
23
ABC
1
23
ABC
123
ABC
1
23
ABC
123
32
原来状态
(1) A移到C
(2) A移到B
(3) C移到B
(4) A移到C
(5) B移到A
(6) B移到C
(7) A移到C
4个铁盘的河内塔问题图解
ABCABCABCABC
1
234
原来状态
(a)由前述方式(1)~(7),将前3个先搬到B
(b) A移到C
(c)由前述方式(1)~(7),将B中的3个铁盘移到C
4
1
23
1
2344
1
23
10-3 河内塔问题
河内塔问题的递回演算法如下
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
/* 演算法名称:河内塔问题演算法*/
/* 输入:n个铁盘*/
/* 输出:铁盘的移动程序*/
int Hanoi(char A, Char B, Char C, n)
/* 第1个参数是来源桩*/
/* 第2个参数是辅助桩*/
/* 第3个参数是目的桩*/
/* 上述参数即是n个铁盘从A搬到C */
{ if(n==1) printf("disk %d:%c->%c",n,A,C);
else
{ Hanoi(A,C,B,n-1); /* (n-1)个铁盘从A搬到B */
printf("disk %d:%c->%c",n,A,C);
Hanoi(B,A,C,n-1) /* (n-1)个铁盘从B移到C */
}
}
10-3 河内塔问题
演算法分析:时间复杂度的计算是以执行了多少次搬动来
计算,那麼H(n)等於多少呢 可由下列方式推演
当有n个铁盘要搬动时,总共要搬动2n-1次,所以可以说此
问题的时间复杂度是O(2n),这是到目前为止,在本书内容
中我们所见过最高的时间复杂度.
H(n)=2*H(n-1)+1
=2*(2*H(n-2)+1)+1=4*H(n-2)+2+1
=22*H(n-2)+21+20
=23*H(n-3)+22+21+20
=2n-1*H(1)+2n-2+…22+21+20=2n-1
10-4 迷宫问题
迷宫问题
迷宫问题是在一个空间中设计可通路径和不
可通的障碍,然后从入口开始找到一条可以
到达出口的路径,走出迷宫.例如老鼠走迷
宫,机器人走迷宫或你真实地置身於迷宫之
间,找出一条路径可达出口.
10-4 迷宫问题
对於迷宫问题我们可以将之模型成矩阵来讨论,假设在这矩阵中,1代
表障疑(围墙),0代表通道,然后设计一个入口或一个出口,则下图是
一个6x5的迷宫
10-4 迷宫问题
当你位於某一座标时,我们定义它可行进的方向有8个方向,以顺时针
方向来看,有上,右上,右,右下,下,左下,左,左上等
10-4 迷宫问题
(r,c)座标可以是阵列中的任意一点,但是当(r,c)点位於边缘时
(例如最上边一排时),要检查上方位置时将会超出矩阵范围,增加程
式控制的困难度,因此可以将阵列再加上一圈外围,且都设定为不可
通,如此每个(r,c)都可检查8个方向的路径,程式设计和演算法会较
简洁
10-4 迷宫问题
先试问,当你位於入口(1,1)位置想走到出口(6,5)的位置,你会采
取什麼策略,可能的策略是尝试错误的策略,如下:
–1.以顺时针方向检查这8个方向中,哪一个方向有路可通.
–2.如果位於某个点时,8个方向中有多个方向可通时,依顺时针次序,先走
访下一点,再检查下一点的8个可行方向,以此类推,直到找到一条路径可
达出口为止.
上述的策略是没有捷径或技术的策略,但确是可行的策略,在实际走访
时,你将很难用纸笔找出答案.但是上述策略若以递回关系来看却是很
简单,只要把递回演算法设计好,其余走访各点的功夫就交由电脑去尝
试错误了.
迷宫阵列走访1
迷宫阵列走访2迷宫阵列走访3
迷宫阵列走访4迷宫阵列走访5
迷宫阵列走访6迷宫阵列走访7
迷宫阵列走访8迷宫阵列走访9
迷宫阵列走访10迷宫阵列走访11
Step 11
目前在(6,5),已是出口了,走访结束.
迷宫走访的堆叠运作
(1,1)
(1,2)
Step 1
(1,1)
(1,2)
Step 2
(1,1)
(1,2)
Step 3
(1,1)
(1,2)
Step 4
(1,1)
(1,2)
Step 6
(1,1)
(1,2)
Step 7
(1,1)
(1,2)
Step 8
(1,1)
(1,2)
Step 9
(1,1)
(1,2)
Step 5
(1,1)
(1,2)
Step 10
(1,3)
(1,4)
(2,3)
(3,3)
(4,4)
(5,4)
(6.5)
(1,3)
(1,4)
(2,3)
(3,3)
(4,4)
(5,4)
(1,3)
(1,4)
(2,3)
(3,3)
(4,4)
(1,3)
(1,4)
(2,3)
(3,3)
(1,3)
(1,4)
(2,3)
(1,3)
(1,4)
(1,3)
(1,4)
(1,5)
(1,3)(1,3)
Step 11 结束
POP所有资料
(1,4)
POP
(1,5)10-4 迷宫问题
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/* 演算法名称:迷宫演算法*/
/* 输入:迷宫大小和限制*/
/* 输出:走出迷宫的路径*/
#define desr 6
#define desc 5
int maze(int r,int c)
{
if(A[r][c]==2)
return 1;
else if(A[r][c]==0)
{
A[r][c]=2;
if(maze(r+1,c-1)) return 1;
if(maze(r+1,c+1)) return 1;
if(maze(r-1,c+1)) return 1;
if(maze(r-1,c-1)) return 1;
if(maze(r,c-1)) return 1;
if(maze(r+1,c)) return 1;
if(maze(r,c+1)) return 1;
if(maze(r-1,c)) return 1;
A[r][c]=3;
return 0; /* 传回失败*/
}
else
return 0; /* 传回失败*/
}
资料结构与演算法
课程教学投影片
第十一章–树
本章各段大纲
11-1 树状结构和特性
11-2 二元树
11-3 二元树的资料结构
11-4 二元树的走访
11-5 二元运算树
11-6 堆积
11-7 二元搜寻树
11-1 树状结构和特性
在树状结构中,一般最顶端者称为根
(Root),由根开始延伸出节点(node),所延
伸出的其它节点称为分支节点(Branch
Node),最底端不再延伸的节点称为终端节
点(Terminal node) ,连结二节点的线称为
节线(Edge).
A
BCD
EFG
H
父节点
子节点
祖父节点
孙子节点
兄弟节点
树状结构
A
BCD
EFG
H
第1层
第2层
第3层
第4层
A节点(Root)节线(Edge)
内部节点
外部节点
树状结构的基本定义
一个树状结构的基本定义如下附图请参考上页:
–节点(Node):树状结构中的每个点,如附图中的A,B,C,D,E,
F,G,H.
–根节点(Root node):最顶点的节点,可连结到其他节点,但别的
节点不可连结到它,如附图的A.
–节线(Edge):连结二节点的线,分有方向性和无方向性两种.如
附图的节线为无方向性的节线.
–内部节点(Internal node):其底下还有节点者称为内部节点,也
称为非终止节点(Unterminalnode),如附图中的A,B,C,E.
–外部节点(External node):其底下没有节点者称为外部节点,也
称为终止节点(Terminal node),如附图中的D,F,G,H.
–分支度(Branch Degree):由某节点往下可连结的节点数,亦即某
节点往下的节线数.如附图中,A的分支度是3,B的分支度是2.
–层(Level):层也可定义为阶度(Order).根节点为第一层,根
节点所连结的节点称为第2层.如附图中,第2层的节点有B,C,D,
第3层的节点有E,F,G.
–高度(Height):树的最大阶度,如附图的最大阶度为4,所以高度
=4.
11-1 树状结构和特性
上下两层节点间有节线连结者的关系称为父
子节点,下层节点称为上层节点的子节点
(Children node),上层节点称为下层节点
的父节点(Parent node),同层的节点且有
共同父节点者称为兄弟(Twins或Sibling)节
点.若不只一层的关系,则同理可称为祖父
节点或孙子节点.
由树状结构所定义的基本结构可延伸下列计量名称
–总节点数:节点的总数.如图11-3的总节点数8.
–总节线数:节线的总数.如图11-3的总节线数7.
–路径长(Path Length):连结任二个节点的节线数总和称为路径长,也可
看成每条节线的路径,长度等於1.如图11-3中,A到E的路径长2,A到H的
路径长3,A到C的路径长1,A到G的路径长2.
–总路径长(Total Path Length):树根到所有节点路径长的总和称为总路
径长.
–最大分支度:所有分支度中最大数值,如A的分支度为3,B的分支度为2,
其余分支度皆为1,所以最大分支度为3.
–总分支度:所有节点分支度的总和.
特性:由以上的延伸定义,可得到下列的特性:
–总节点数=总节线数+1
如果总节点数为8,总节线数为7.除了根节点外,每一个节点都有一条节
线数.
–总分支度=总节线数
如果总分支度为7,总节线数也为7.
11-2 二元树
二元树定义和结构
–树状结构有非常多种,其中最常使用的称为二
元树(Binary tree).二元树的定义如下:
–二元树(Binary Tree):每个节点最多只能有2
个子节点的树,即每个节点的最大分支度为2或1
或0.
因为二元树最多只有2个子节点,以方向性来看,可以有以下的定义,
以下图为例:
–左节点(Left node):某节点的左边子节点,如B是A的左节点,C
是D的右节点,G是C的右节点,由此类推.
–右节点(Right node):某节点的右边子节点,如C是A的右节点,G
是C的右节点.
–左子树(Left Tree):由左节点所代表的树,如B节点以下的树称
为A的左子树.
–右子树(Right Tree):由右节点所代表的树,如C节点以下的树称
为A的右子树.
A
B
C
I
DEF
H
C是A的右节点
A的右子树
H是D的左节点
A的左子树
G是C的右节点
B是A的左节点左
左
左
G
J
右
右
右
右
左
左
11-2 二元树
二元树除了有一般树状结构的公式之外,尚有下列公式:
–【公式一】
二元树有N个分支度为2的节点时,则有N+1个外部节点(分支度为
0).
–【公式二】
若一个二元树只有分支度2或0时,其内部节点数是N时,则外部节点
路径长和=外部节点路径长和+2N
–【公式三】
二元树中阶层i的节点数,最多只有2(i-1)个,i≥1
–【公式四】
高度为i的二元树,节点总数最多只有2i-1个,i≥1
11-2 二元树
练习1
若一个二元树共有n个节点,则其最小高度
和最大高度为何 当n=280时最小高度和最
大高度为何
解答:最小高度=└log2 n┘+1,最大高度=n
n=300时,最小高度=└log2
(280)┘+1=8+1=9,最大高度=300
11-2 二元树
练习2
深度为5的二元树,最多有几个节点,最少
有几个节点
解答:深度h=5时,最多节点数=2h-1=25-
1=32-1=31,最小节点数=h=5.
11-2 二元树
练习3
如果一个二元树有6个分支度为2的节点时,
则其终端节点(树叶)有几个
解答:由公式一得知n0=n2+1,所以终端节
点=6+1=7.
完满二元树的定义
完满二元树(Full binary tree)是一个二元树,所有的外部节点都必须
在同一层.
左图是完满二元树,右图不是完满二元树,因为G外部节点在第3层,而
其他的外部节点H,I,J,K,L,M都在第4层.
A
BC
I
DEF
H
是完满二元树
G
J
不是完满二元树
LMNOK
A
BC
I
DEF
H
G
JLMK
11-2 二元树
【公式一】
一个完满二元树若总共有N个节点时,则高
度=└log2 (N+1)┘.
范例5
上一页中左图的完满二元树,总节点数15.
则高度=log2 (N+1) =log2 (15+1) =log2 24
=4.
11-2 二元树
【公式二】
高度为k的完满二元树,含有2k-1个节点
范例6
令一个二元树的根(root)之深度为l,则深
度为n的二元树最多共有多少的节点
(nodes)
答案:共有2n-1个节点,图解请参考下页
A
BC
I
DEF
H
G
JLMNOK
高度1=> 此层共有1个节点
高度2=> 此层共有21=2个节点
高度3=> 此层共有22=4个节点
高度4=> 此层共有23=8个节点
节点数总和=20+21+22+23=15=24-1=2k-1
完整二元树定义
完整二元树(Complete binary tree)是外部节点相差的阶数在1阶以
内,含0阶(0阶即是完满二元树),而且可以循序编号.
完满二元树必是完整二元树,但完整二元树不一定是完满二元树
A
BC
I
DEF
H
G
JK
11-2 二元树
【公式一】
高度为k的完整二元树,含有的节点数目介於2(k-1) 2k-1之
间,节点的编号次序如同完满二元树一般(中间无缺).
【公式二】
有n个节点的完整二元树,其高度为└log2n ┘+1
范例7
若存在一棵二元树有25个节点(node),那麼它的高度
(Height)不可能为4,若它是一棵完整二元树(Complete
Binary Tree),则它的高度为何
解答:
└log2 25┘+ 1 = 4+1=5
11-3 二元树的资料结构
二元树的编号系统
因为二元树只有左节点和右节点之分,而且各个节点又有阶层之分,所
以如果以根节点开始编号(0号),然后由左而右,由上而下编号,二
元树的编号次序如下图.
12
34
657
0
二元树的编号系统
–【结论一】
第k层的最左边编号为2(k-1),最右边的编号是2k-1,所以
k层的编号介於2(k-1)至2k-1之间
–【结论二】
第k层的节点数=最大编号-此层最小编号+1
=(2k-1)-(2(k-1))+1
=(2k)-(2(k-1))=2 x(2(k-1))-(2(k-1))=2(k-1)
–【结论三】
1个k层的二元树,节点数最多有2k-1个
–【结论四】
某节点的编号m,则其左节点的编号为2m,右节点的编号
为2m+1.
11-3 二元树的资料结构
练习
在二元树中,节点编号为3的节点,其父节
点,左子节点和右子节点的编号各为多少
解答:节点编号p时,其父节点编号
=└p/2┘=└3/2┘=└1.5┘=1.
其左节点编号=2p=2x3=6,其右节点
编号=2p+1=2x3+1=7.
11-3 二元树的资料结构
用一维阵列来表示
1
23
4576
B
A
C
DEFG
12
BCD GFEABCD GFEA
34567
D的父节点=X( 4/2 )=X(2)=B
E的父节点=X( 5/2 )=X(2)=B
C的左子节点=X(2*3)=X(6)=F
C的右子节点=X(2*3+1)=X(7)=G
D的父节点=X( 4/2 )=X(2)=BD的父节点=X( 4/2 )=X(2)=B=X( 4/2 )=X(2)=B
E的父节点=X( 5/2 )=X(2)=BE的父节点=X( 5/2 )=X(2)=B=X( 5/2 )=X(2)=B
C的左子节点=X(2*3)=X(6)=FC的左子节点=X(2*3)=X(6)=F
C的右子节点=X(2*3+1)=X(7)=GC的右子节点=X(2*3+1)=X(7)=G
X
11-3 二元树的资料结构
用二维阵列来表示
(2,1)
(3,1)
(4,1)
(2,2)
A
B
D
C
EFG
HIJKLMNO
(3,4)
(4,8)(4,2) (4,3) (4,4) (4,5) (4,6) (4,7)
(1,1)
(3,2) (3,3)
K
G
J
F
I
E
C
H
D
B
A
ONMLK
G
J
F
I
E
C
H
D
B
A
ONML
876543210876543210
X阵列
不用
0
1
2
3
4
不用
11-3 二元树的资料结构
【结论六】
某一节点的座标是(r,c)时,则其左子节点的座
标是(r+1,2c-1),右子节点的座标是(r+1,2c)
范例9
E节点的座标是(3,2),则
左子节点的座标是(3+1,2x2-1)=(4,3),X
(4,3)=J
右子节点的座标是(3+1,2x2)=(4,4),X
(4,4)=K
11-3 二元树的资料结构
【结论七】
某一节点的座标是(r,c)时,其父节点的座标是(r-
1,┌c/2┐).(┌p┐是取大於等於p的最小整数).
范例10
J节点的座标是(4,3),则其父节点的座标是(4-1,
┌3/2┐)=(3, ┌1.5┐)=(3,2),X(3,2)=E.
范例11
K节点的座标是(4,4),则其父节点的座标是(4-1,
┌4/2┐)=(3, ┌2┐)=(3,2),X(3,2)=E.
11-3 二元树的资料结构
比较
用一维阵列或二维阵列来表示二元树时,都是会用到转换
计算,求得父子节点的关系式.运算方式差不多,但以储
存空间来看,一维阵列表示法不会浪费空间,二维阵列表
示法除了浪费第0列,第0栏的空间(2k-1+k+1).另外未用
到的空间则有:
(2k-1-20)+(2k-1-21)+(2k-1-22)+…+(2k-1-2k-1)
=2k-1 x k -(20+21+22+…+2k-1)
=2k-1 x k -(2k -1)
二元树以结构阵列来表示
–现在一般的高阶语言(如C++,VisualBasic等)都提供结构的型态,
而且二元树最多只有左,右节点两种形式,所以二元树也适合用结
构来表示.
–以结构表示二元树时,只要宣告1个有三个项目的结构,其中一栏存
放节点的资料,另外两栏分别存放可连结到左子节点和右子节点的
链结索引指标,如下图.
A
BC
DEF
12
345
002A102A1
1-1B31-1B325C425C4
5-1F-15-1F-13-10-13-10-14-1E-14-1E-1
-1代表无子节点
rightdataleft索引指标
-1F-15
-1E-14
-1D-13
5C42
-1B31
2A10
rightdataleft索引指标
-1F-15
-1E-14
-1D-13
5C42
-1B31
2A10
以C语言为例,结构阵列的宣告方式如下:
structbitree
{
intleft;
char data;
intright;
}
typedefstructbitreebitreenode;
bitreenodea_bitree[100];
这样的定义方式,由父节点要连结子节点时,只要利用子节点索引指标
或右节点索引指标,即可取得左右节点的值.例如:
x=a_bitree[0].left; /* x是根的左子树索引指标
*/
xdata=a_bitree[x].data; /* xdata是根左子节点的值
*/
y=a_bitree[0].right; /* y是根的右子树索引指标
*/
ydata=a_bitree[y].data/* ydata是根右子节点的值
*/
只要控制好索引指标,即可控制二元树的存取.另外上述结构中,无法
由子节点找到父节点,所以我们再修改结构定义如下,即可同理取得父
节点的索引指标.
Structbitree1
{
intleft;
char data;
intright;
intparent;
}
typedefstructbitree1 bitreenode1;
bitreenode1 a_bitree1[100];
其父节点的资料取得方式如下:
p=a_bitree|[1].parent /* 取得父节点A的索引指标
*/
pdata=a_bitree1[p].data /* 取得父节点A的资料*/
-1
-1
-1
5
-1
2
right parentdataleft索引指标
2F-15
2E-14
1D-13
0C42
0B31
-1A10
-1
-1
-1
5
-1
2
right parentdataleft索引指标
2F-15
2E-14
1D-13
0C42
0B31
-1A10A
BC
DEF
12
345
0
二元树以链结串列来表示
–C语言提供链结串列的指令,所以也可以用链结串列来表示二元树,
此方法主要是以链结串列运用动态记忆体配置方式运作,和前一小
节的结构阵列很类似,但结构阵列是运用静态记忆体配置方式.
–以链结串列表示二元树时,要设计一个左子节点指标,一个右子节
点指标,一个资料栏位和一个父节点指标,如下图.
A
BC
DEF
parentrightAleftparentrightAleft
parentrightBleftparentrightBleftparentrightCleftparentrightCleft
parentrightDleftparentrightDleftparentrightEleftparentrightEleftparentrightFleftparentrightFleft
Null Null Null NullNullNull
Null
11-3 二元树的资料结构
表示二元树的链结串列宣告方式如下:
structbitree2
{
structbitree2 *left;
char data;
structbitree2 *right;
structbitree2 *parent;
}
typedefstructbitree2 bitreenode2;
bitreenode2 *p_bitree2;
相关建立树的范例程式请参考本书范例程式
11-4 二元树的走访
当我们已经将资料建立成二元树结构(不管资料结构是一
维阵列,二维阵列,结构阵列或链结串列等),当我们要
对此二元树操作时(找寻某资料,撷取各节点资料,统计
各节点等),必须「走访」(travrtsal)整个二元树.
常用的走访方法如下,D表示某节点,L表示走访左子树,
R表示走访右子树
–LDR:先走访左子树,再走访节点,最后走访右子树,以节点被走访
的次序是中间顺序,所以称为「中序法走访」(inorder
traversal).
–LRD:先走访左子树,再走访右子树,最后走访节点,节点最后被走
访,所以此法称为「后序法走访」(postordertraversal).
–DLR:先走访节点,再走访左子树,最后走访右子树,节点最先被走
访,所以称为「前序法走访」(preorder traversal).
前序法走访(preorder reaversal)如前所述是DLR方法,走访次序是【节点】
→【左子树】→【右子树】,在【左子树】中会递回处理,直到结束时才往下
一个走访,以一个运算式A*B+C/D-E建立成二元树后(建立方法下一节介绍),
其前序法走访将资料印出时,如果递回的关系以堆叠的角度来看,则操作次序
如下图.
次序次序走访节点走访节点堆叠
2
3
6
1
4
7
8
0
A+
*
/-
B
C
D
E
5
无左子树了
无左子树了
无左子树了
无左子树了
无左子树了,结束
输出+,push(2)
输出*,push(4)
输出A,pop(4)
输出B,pop(2)
输出,push(5)
输出C,pop(5)
输出D,pop(1)
所以前序法走访的资料次序为-+*A B / C D E
输出-,push(1)
11
21
421
21
1
51
3
6
-
+
*
E
/
ABCD
789
1
2
45
2
3
6
1
4
7
8
0
5
精简为
-
+
*
E
/
ABCD
1
输出E,结束
前序法走访演算法
01
02
03
04
05
06
07
08
09
void preorder(binode *d)
{
if (d!=Null)
{
prontf("%C", d->data);
preorder(d->left);
preorder(d->right);
}
}
范例
一个单循环淘汰赛比赛二元树如下图,列出前序法走访的结果,其中G1~G7代表比赛,P1~P8
代表比赛选手.
前序法走访是先走访节点,再左子树,再右子树,所以输出顺序为:
G1,G2,G4,P1,P2,G5,P3,P4,G3,G6,P5,P6,G7,P7,P8.
代表意义:
G1→G2→G4→P1→P2→G5→P3→P4→G3→G6→P5→P6→G7→P7→P8
G1是冠军,可设计程式依据此输出资料作进一步处理.
中序法走访(inordertraversal)
如前所述是LDR方法,走访次序是
【左子树】→【节点】→【右子
树】,在【左子树】中会用递回处
理,直到结束时才往下一个走访.同
样以一个运算式A*B+C/D-E建立成二
元树后(建立方法下一节介绍),以
中序法走访方式将资料印出,且如果
递回关系以堆叠的角度来看,则操作
次序如图11-17.
3
6
-
+
*
E
/
ABCD
789
1
2
45
2
310
1
613
15
8
9
12
5
14
4711
次序走访节点堆叠
7
8+
C无左子树了
放入5
取出2
取出5
5 1
B无左子树了1
9
10
11输出A B +C / D-E*
/
D
E
无左子树了
无左子树了,结束
12
13
14
15
16
取出1
-
2
3
6
1
4A
5
无左子树了
放入2
放入4
取出4
放入11
2 1
4 2 1
2 1
*2 1
堆叠动作
中序法走访演算法
01
02
03
04
05
06
07
08
09
void inorder(binode *d)
{
if (d!= Null)
{
inorder(d->left);
printf("%C", d->data);
inorder(d->right);
}
}
范例
以一个单循环淘汰赛的比赛二元树如下图,列出中序走访的结果,其中G1~G7代表比赛,
P1~P8代表比赛选手.
后序法走访(postorder
traversal)如前所述是
LRD方法,走访次序是
【左子树】→【右子树】
→【节点】,在【左子
树】中会用到递回处理,
直到结束时才往下一个走
访.同样以一个运算式
A*B+C/D-E建立成二元树
后(建立方法下一节介
绍),以后序法走访方式
将资料印出,且递回关系
以堆叠的角度来看,则操
作次序如图11-18
3
6
-
+
*
E
/
ABCD
789
1
2
45
2
39
1
5
13
17
816
12
7
14
4610
15
11
2
3
6
1
4A
B
5
无左,右子树了
无左子树了
放入2
放入4
取出4
放入11
2 1
4 2 1
2 1
1
2 1
7取出2*1
11
所以输出A B *C D/ +E -
-
走访节点堆叠次序堆叠动作
17
5 2 19放入5
C无左右节点取出5102 1
放入55 2 1
D12取出52 1
+14取出1
E16取出1
/13取出21
8放入22 1
15放入11
精简为
-
+
*
E
/
ABCD



后序法走访演算法
01
02
03
04
05
06
07
08
09
void postorder(binode *d)
{
if (d!=Null)
{
postorder(d->ledt);
postorder(d->right);
postorder("%C", d->data);
}
}
范例
以一个单循环淘汰赛的比赛二元树如下图,列出后序走访的结果,其中G1~G7代表比赛,
P1~P8代表比赛选手.
阶层走访
阶层走访(level-order traversal)是指依阶层的顺序走访,先访问阶层小的所
有节点,同一阶层由左而右走访,再往下一阶层走访,以此累推.
如果建立二元树的资料结构是一维阵列或二维阵列时,只要控制阵列的索引指标,
一维阵列的索引指标由小而大,二维阵列的索引指标控制由左而下再由上而下.
但如果二元树的资料结构是用结构阵列或链结串列的left和right指标来指到左子
树和右子树时,由於阶层走访的型式不是用递回关系,而是用伫列的结构,因为由
根走访完后,可将左子树的根节点先放入伫列,再放右子树的根节点,以此累推,
如下图说明.
-+子树E子树-+子树E子树(1)
(2)
-
+
*
E
/
ABCD
(3)
输出-
处理+子树
E子树*子树/子树+E子树*子树/子树+
(4)
输出+
处理E子树
/子树BA*/子树BA*
输出E
处理*子树
ABCD/ABCD/
输出*
处理/子树
输出/
ABCDABCD
(5)
阶层走访结果为-+ E * / A B C D
输出A
B
C
D
伫列
11-4 二元树的走访
利用中,前序法转二元树:
1.利用前序法的顺序(根,左子树,右子树)可知,第1
个一定是根.
2.利用中序法的顺序(左子树,根,右子树),配合步
骤(1)所找到的根作对应,可决定出根,再分成左子
树和右子树.
3.再分别依步骤(1),(2)处理左子树和右子树,找
出其他的根和终端节点.
范例16
假设一运算式前序法走访的资料次序为-+*AB/CDE,中序法走访的资料次序为A*B+C/D-E,请
画出此二元树.
11-4 二元树的走访
利用中,后序法转二元树:
1.利用后序法的顺序(左子树,右子树,根),得知最
后1个一定是根.
2.利用中序法的顺序(左子树,根,右子树),配合步
骤(1)所找到的根作对应,可决定出根,再分成左子
树和右子树.
3.再分别依步骤(1),(2)处理左子树和右子树,找
出其他的根和终端节点.
范例17
假设一运算式后序法走访的资料次序为AB*CD/+E-,中序法走访的资料次序为A*B+C/D-E,请
画出此二元树.
11-5 二元运算树
运算式的处理和计算是每种程式语言必须做的程序,
由於运算式的处理需考虑运算子的优先顺序,而且大
部分的运算子都有两个运算元(除了正负号之外),
而二元树的左右子树也有顺序之分,所以可以将运算
式表示成二元树,称为二元运算树(Binary
Expression Tree).再以二元树的走访方法,即能计
算出运算式的值.
【定义】
二元运算式是一个二元树,且内部节点是运算子(例
如+-*/等),外部节点则为纯资料的运算元,优先率
高的运算子是优先率较低的子树.
11-5 二元运算树
一般运算子的优先次序是(1)括号,(2)正负
号,(3)次方,(4)*/,(5)+-,(6)=
建立二元运算树:要将运算式转换为二元树
时有两种方法
–直接用观察的方法,画出二元运算树.
–利用堆叠法运算,以程式运作建立二元运算
式.
11-5 二元运算树
观察法,利用运算子的优先次序和二元运算树的特
性,将运算式表示成二元运算树,再建立二元树
供后续程式运作,一般简单的考题可用此方法,
快速建立二元运算树,其步骤如下:
1.根据运算子的优先次序和结合性,将运算式加入括号.
2.由内部括号开始,将括号中的运算子当树根,左边的运
算元当左子树,右边的运算元当右子树,依由内而外顺
序处理其余括号,直到最外层括号为止.
11-5 二元运算树
范例18,将A*B+C/D-E运算式化为二元运算树.
解答:依运算子优先次序加入括号(*/优先率高於+-)
A * B + C / D -E
→( A * B ) + C / D -E
→( A * B ) + ( C / D ) -E
→( ( A * B ) + ( C / D ) ) -E
→( ( ( A * B ) + ( C / D ) ) -E )
所以二元运算式= ( ( ( A * B ) + ( C / D ) ) -E )
*/
ABCD
+
*/
ABCD
-
+
*
E
/
ABCD
(1)(2)(3)(4)
11-5 二元运算树
堆叠法,运算式转换二元运算树正规的方法是利用堆叠法,以可程式
化的方法直接输入运算式来建立二元运算式,再进行其他处理.
要利用此方法时,会运用到堆叠章节(第7章)所介绍的内容,将中序
式转成后序式.再以后序式建立二元运算树,其步骤如下:
a)中序式→后序式.
b)后序式→二元运算树.
1.由左而右扫描.
2.如果是运算元:建立一节点,放入堆叠.
3.如果是运算子:POP所需的资料项,建立一子树,再放入堆
叠.
4.如果扫描到最后一个资料时步骤结束.
范例19
将A * B + C / D -E 运算式化为二元运算树.
11-6 堆积
堆积结构
一般对於所建立的二元树,如果要找出最大(最小)值
时,可以利用前序法,中序法,后序法走访各个节点,然
后比较各节点的值,找出最大(或最小)值,但是当我们
设计二元树的目的是随时可查询节点资料的最大(最小)
值,或前几大(前几小)的值时,每作一次查询都得走访
整棵树,这将很没有效率.
其实为了应付上述的搜寻问题,我们在建立二元树时,可
将资料设计成称为堆积(Heap)的特殊二元树,则搜寻最
大(最小)值时,只要走访最低阶层(或最高阶层)即
可,因为堆积是将资料依大小顺序安排节点,且要符合完
整二元树的定义,其正式定义分为最大堆积(max-heap)
和最小堆积(min-heap)两种.
最大堆积:最大堆积为一完整二元树,任一非终端节点的资料不小於其子节点的资料.
由前述定义可知,最大堆积的根节点一定是最大值,较大的资料位於阶层较低的层
25
1520
4
101216
5
18
是最大堆积不是最大堆积
25
1520
4
1012
5
阶层相差2
不是完整二元树
不是最大堆积
20
1530
4
101216
5
18
子节点比父节点大
不是最大堆积
最小堆积为一完整二元树,任一非终端节点的资料不大於其子节点的资料.
最小堆积的根节点一定是最小值,较小的资料位於阶层较低的层
2
520
30
151812
35
20
2
510
30
1518
25
阶层相差2
不是完整二元树
是最小堆积不是最小堆积
2
510
30
151812
25
9
子节点资料比父节点
小不是最小堆积
不是最小堆积
11-6 堆积
资料结构
因为堆积是一个完整二元树,之前中介绍过用阵列来表示二元树的方法,所以
一般完整二元树可以用一维阵列来当作它的资料结构,则程式运作的处理较简
单方便.
因为最大堆积和最小堆积只是大小顺序相反,其他都一样,所以接著所介绍的
范例和图例都以最大堆积为例.堆积以阵列的表示法如下图.
25
1015
58
12
34
0
12
10 15 5 82510 15 5 825
345 6…….0阵列指标
堆积的操作
因为最大堆积必须符合节点的资料比子节点大或等於,所以建立堆积,插入节点,删除节点
后,都还要维持堆积的特性,所以这些对於堆积的操作程序,则有一定的规则.
插入节点到最大堆积中
假设如上一页图中的最大堆积,如果要加入一个新节点,其资料为20时,其运作方式如下图
1.
假设如图1的最大堆积,再加上一新节点,其资料为40时,其运作方式如图2.
25
1015
58
12
34
0
205
25
1020
58
12
34
0
155
(1)(2)
20比15大
交换
20比25小
不交换
(3)
20放入阵列(2)的位置
12
10 15 5 82510 15 5 825
34 5012
10 15 5 1582510 15 5 15825
345012
10 20 5 1582510 20 5 15825
34 50
25
1020
58
12
34
0
155
(1)
40比20大
交换
40
12
1510 20 5 8251510 20 5 825
34 506
25
1040
58
12
34
155
(2)40又比25大
交换
20
12
1510 20 5 208251510 20 5 20825
34 506
0
66
40
1025
58
12
34
155
(3)
(4)再放入40
20
12
1510 25 5 208251510 25 5 20825
34506
0
6
12
1510 25 5 208401510 25 5 20840
34506
11-6 堆积
由上一页图1和图2的说明可得知:
–新加入的节点与其父节点比较大小,如果比父节点大,
则将父节点的资料放在新节点的编号位置(X),其父节点
的编号=└(X-1)/2┘,即(X-1)/2的商数.例如图1的
X=5,其父节点编号=└(5-1)/2┘=└4/2┘=2.而图2的
X=6,其父节点编号=└(6-1)/2┘=└5/2┘=2.
–如果步骤(1)中的父节点资料有拷贝到新节点时,则新加
入的节点还须一直往上找寻其父节点是否比它还小,重
复步骤(1)的程序,直到父节点比它大为止,才将新节点
的资料放在正确位置.
删除最大堆积中的某节点
当我们要删除最大堆积中的某节点时,原来的堆积要做调整才能维持最
大堆积的特性,一般的做法是根据被删除的节点位置,往下找其左右子
节点,看哪个大,往上移到此被删除的位置,再以此累推,依序检查是
否符合堆积的特性,直到维持堆积的特性或到达最底层为止.其操作步
骤如下:
–1.取得被删除节点的位置(例如index)和资料(例如X).
–2.取得最后节点的资料,例如xend,先假想目前index位址的资料是
xend.
–3.编号index节点的左右子节点的编号为2*index+1,2*index+2.现
在比较xend,左子节点的资料,右子节点的资料三者谁大.
(a)xend最大:表示xend放在xindex编号时,可维持堆积的特
性,程序进入步骤4.
(b)如果左子节点最大:将左子节点移到index编号的位置,且
index用2*index+1取代,重复步骤3的程序.
(c)如果右子节点最大:将右子节点移到index编号的位置,且
index用2*index+2取代,重复步骤3的程序.
–4.最后index编号节点的资料放xend.
最大堆积经常运用删除根节点的方法取出最大值,再维持最大堆积树,根据上述演算法步骤
的说明,其图解说明如下图.
40
1025
582015
最后一个放
到根节点
401025581520
0123456
0
12
34 56
20
1025
5815
401025581520
0123456
0
12
34 5
(1) (2)
25较大,
25放到根节点
xend=20
20和10,25比较
(3)
25
1020
5815重覆(2)的程序,直
到节点的资料比左
右子节点的资料大
为止251025581520
0123456
0
12
345
xend=20
(4)
25
1020
5815
2510205815
0123456
0
12
345
删除根节点
堆积树的应用-优先伫列
由11-2节我们知道一个有n个节点的堆积树,其最高阶度为log2n(假如n=2k-1时,有k
层),而堆积树新增节点或删除节点都是在阶层之间的移动节点,所以最差情况需移动
最大阶层时,其时间复杂度是O(logn).
另外最大堆积树节点间有阶层低的节点资料不小於左右子节点的特性,当我们要取得较
大(或最大)的资料,且删除它;另外也可以加入新的节点时,则可应用最大堆积树.
例如作业系统所使用优先伫列(priority queue).
一般的伫列是先进先出的特性,在伫列中的元素,先到先处理,不会根据各个元素的优
先率(或称权重)来处理,如果要用一般的伫列来达成优先率高的先处理时,其作法是
由伫列中找出优先率最高者,假如有n个元素,未经排列且用线性搜寻法时,其时间复杂
度为O(n),当n很大时,则堆积的O(logn)比线性搜寻的O(n)效率高许多,如下图.
A
BC
DEFG
GFEDCBA
40 50 30 40 60 80 10 0
(1 ) 找出最大者,所需时间O (n )
(2 ) 删除节点,所需时间O (n )
(3 ) 新增资料,所需时间O (n )
合计O (n )
元素
优先率
(1 ) 找出最大者,所需时间O(1 )
(2 ) 删除节点,所需时间最差情况O (le g n )
(3 ) 新增资料,所需时间最差情况O (le g n )
合计O (le g n )
堆积
(优先顺序)
10 0
8060
40 30 50 40
11-6 堆积
优先伫列在电脑系统中,应用的情况很普遍,例如列印伫列,中央处理
器的工作排程,记忆体可用空间管理,硬碟连续储存空间管理等.
列印伫列是指要列印的资料皆会送到作业系统所提供的印表机伫列中,
由列印管理程式管理印表机应该优先列印哪份资料,如果大家的优先率
一样时,以先到先服务为原则,有优先率差别时,则先服务优先率高
者.
中央处理器的工作排程,除了依据优先率来处理之外,在有分时(time
sharing)功能的作业系统中,希望每个处理程序(process)皆能在一
定的时间周期内被服务到,因此一般作业系统有一种「最短时间工作优
先」(shortest-job-first)的排程策略,即可应用最小堆积快速地取
出需最短时间的处理程序,且新加入的处理程序可以用最短的时间来维
护其优先伫列.
堆积排序法
当有n个资料要排序时,我们从第七章所介绍的各种排序法得知最佳的时间复杂
度是O(nlog n),例如快速排序法等.堆积的特殊结构稍加以变化,也可以得
到一个O(nlog n)的排序演算法,此利用堆积结构的演算法称为堆积排序法
(heap sort).
堆积排序法能够达到O(nlog n)的等级,主要是因为建立一个堆积时,最差情
况是n个O(logn),而且删除节点的最差情况也是O(logn),考虑所有n个节点
都要处理一遍时,则最差情况为O(nlog n).堆积排序法是用到11-6-2的两个
演算法.
因为最大堆积的根节点一定是堆积中所有节点的最大值,如果我们用另一阵列
来存放抽出的最大值,可依你的需要由小到大放置或由大到小放置,但是一般
堆积排序法是强调不多占用其他空间,所以我们只好把最大值放到原堆积阵列
的最后一个位置,则依此累推可得到由小到大的排序结果.
【结论】
–要得到由小到大的排序,需建立最大堆积;
–要得到由大到小的排序,需建立最小堆积.
假设一阵列已存放了要排序的资料,则堆积排序演算法可分为两部份:
–建立堆积.
–以删除根节点(和最后位置调换)的方法排序.
建立最大堆积
建立堆积且不希望用到多余的储存空间时,可利用11-6-2节加入新节点的演算法,加上回圈
控制目前的节点数,即第1次只有1节点,第2次只有2节点;第3次只有3个节点,以此累推.
尚未作用的节点,其阵列资料未做任何异动,建立最大堆积的流程如下图说明.
21317161511141
0123456
原始资料阵列X
阵列指标
建立堆积
(1)
(2)
(3)
21021
0123456
未变
21
31
0
1
31
21
31比21大
3121
0123456
31
21
0
1
71比31大
交换
71
2
71
21
0
1
31
2
712131
0123456
(4)
71
21
0
161比21大
交换
31
2
71613121
0123456
613
71
61
0
1
31
2
213
OK
(5)
71
61
0
1312
213514
7161312151
0123456
由最大堆积作由小到大排序
现在由图11-27所建立的最大堆积,只要每次抽出根节点,再维护剩余的节点为堆积,重复这
样的程序,即可得到由大到小的排序.但若是要在阵列资料中作排序,则要将根节点的和作
用中堆积的最后一个位置交换,例如最刚开始有7个元素,所以根节点(索引指标0)和最后
一个(索引指标6)交换,此时剩下的作用中堆叠只有6个元素(最后一个最大值不算),此6
个元素依11-6-2节介绍的删除根节点,把最后一个元素移到根节点再维护堆积的作法一样.
71614121511131
0123456
原最大
推积71
6141
21513111
0
12
345 6
索引指标
最大推积阵列
X71614121511131
0123456
原最大
推积71
6141
21513111
0
12
345 6
索引指标
最大推积阵列
X
(1 )
31
6141
21517111
0
12
34 5 6
61最大
往上移
61
3141
21517111
61514121311171
0123456
根(71 )和最后一个(31 )交换,重新整理成最大堆积树
51最大
61
5141
21317111
作用中
不作用
(2 )
11
5141
21317161
61最大交换
51
1141
21317161
51314121116171
0123456
根(61 )和作用中最后一个(11 )交换
31最大交换
51
3141
21117161
(3 )
11
3141
21517161
41最大交换
41
3111
21517161
41311121516171
0123456
根(51 )和作用中最后一个(11 )交换
(4 )
21
3111
41517161
31最大交换
31
2111
41517161
31211141516171
0123456
根(41 )和作用中最后一个(21 )交换
(5 )
11
2131
41517161
21最大交换
21
1131
41517161
21113141516171
0123456
根(31 )和作用中最后一个(11 )交换
(6 )
11
2131
41517161
只剩一个元素=>结束11213141516171
0123456
根(21 )和作用中最后一个(11 )交换
11-7 二元搜寻树
二元搜寻树
上一节介绍的堆积是具有父子节点之间的关系,可
看成是垂直方向的关系,本节要介绍的二元搜寻树
(Binary Search Tree)则是节点和左子树,右子树
之间的大小关系,可以看成是水平方向的关系.二
元搜寻树简单定义为:「二元树中任意节点x,其
左子树中所有节点元素皆小於x,其右子树中所有
节点元素皆大於x」.二元搜寻树和堆积的比较如
下一页附图.
X
Y是子数
中最大值
Z是子数
中最小值
YX
水平间条
1468
37
5
10
13
1115
X
Y是子数
中最大值
Z是子数
中最大值
Y h=3,n=7 ==> h=3,n=8 ==>
h=4,以此推累.代表每个非终端节点都尽可能有2个分支,此称为最小高度二元搜寻
树,要高度最小,则类似於完整二元树或完满二元树,以n=5为例,最小高度为3,如下
图
20
30
40
50
43
45
40
50
10
44
80
70
60
50
90
75
70
80
50
74
40
70
50
非完整二元树,但一定高度最小
30
20
完整二元树
60
70
50
30
10
70
50
30
901060
70
50
30
90
二元搜寻树的搜寻
二元搜寻树的最大特点是某节点的左子树所有节点的资料
皆比此节点的资料小,而右子树的情况则相反.所以二元
搜寻树最适合用於搜寻,且可经由安排搜寻资料的次序,
可搜寻出由小到大或由大到小的排序功能.
二元搜寻树在搜寻某资料k时,其步骤如下:
先将根节点的资料m比较:
–(1)k = m =>搜寻成功.
–(2)k > m =>
(a)如果是非终端节点:搜寻右子树,再重回步骤1,原根节点换成右子
树的根节点.
(b)如果是终端节点:结束,搜寻未成功.
–(3)k
(a)如果是非终端节点:搜寻左子树,再重回步骤1,原根节点换成左子
树的根节点.
(b)如果是终端节点:结束,搜寻未成功.
范例图示在下一页
2535
40
30
20比30小
20
5015
搜寻30搜寻20
2535
40
30
20
5015
Bin g o
2535
40
30
20
5015
Bin g o
搜寻45
2535
40
30
20
50152535
40
30
20
5015
35 >3 0
35 3 0
45 >4 0
Bin g o找不到
11-7 二元搜寻树
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
/* 演算法名称:二元搜寻树的搜寻节点*/
/* 输入:二元搜寻树中要搜寻的节点*/
/* 输出:二元搜寻树要搜寻节点的位置*/
bintree_search(tree)
{
ptr = tree;
while (ptr != null && key != ptr->data)
{
if(keydata) /* 如果key此节点要小,看左边*/
ptr=ptr->left;
else /* 否则,看右边*/
ptr=ptr->right;
}
return(ptr);
}
二元搜寻树与二元树,堆积,二分搜寻法比较
二元树和二元搜寻树比较
由图11-33得知,二元搜寻树搜寻一个资料时,一直往下搜寻,如果高度为h,则最多只
要搜寻h次,且┌log2(n+1) ┐≤h ≤n,所以一般称二元搜寻树的平均时间为O(log
n),而一般二元树的前序法,中序法,后序法走访来搜寻资料时,其最差情况是每个节
点都要走访过,时间是n,平均是n/2,其时间复杂度为O(n).
二元搜寻树和堆积比较
二元搜寻树寻找某资料的平均时间是O(logn),而堆积只具备某节点的资料比左,右子
树中所有的节点的资料大的性质,也是要用前序法,中序法,后序法走访来寻找某资
料,所以堆积的平均搜寻时间也是O(n).
但是在搜寻最大值时,最大堆积只是O(1),因为根节点就是最大值的节点.而二元搜寻
树的最大值则要一直往右子树找到终端节点,搜寻最小值则要一直往左子树找到终端节
点,其平均时间即为高度h,平均时间复杂度是O(logn).二元搜寻树寻找最大值和最小
值的方式如下图.
711
13
10
5
153
1468
往右子树寻找直到终端节点
第2大值
此终端节点是最大值
往左子树寻找直到终端节点
第2小值
此终端节点是最小值
二元搜寻树的搜寻和二分搜寻法比较
讨论二元搜寻树的目的是此树非常适合用於搜寻(故以此命名),其搜寻方式
如同二分法搜寻一样,都是先比较某点,即可决定接著要比较的范围是左子树
(二分搜寻法是左边范围)或右子树(二分搜寻法是右边范围),二分搜寻法
平均时间为O(logn),而二元搜寻树在最大高度情况来讨论时,其平均搜寻时
间为O(n),此为最差情况;以最小高度情况来讨论时,其平均搜寻时间为O(log
n).这可看出缩小二元搜寻树的高度对於此树的程式运作是很重要的(注:平衡
树[AVL tree]可缩小二元搜寻树的高度,且维持二元搜寻树的特性,本书因篇
幅关系,在此不作介绍).
二元搜寻树应用於排序
由上一节寻找二元搜寻树中最大值,最小值的方法得知,最大值是树状图形最
右边的节点,第2大值是其最大节点的父节点.同理最小值是树状图形最左边的
节点,第2小直是最小值节点的父节点,如先前二页的图所示.
所以当我们要搜寻由小到大的值时,可用前序法走访二元搜寻树所有节点,可
得到由小到大的排序资料,如下图.
同理,要搜寻由大到小的值时,可使用类似前序法的走访,但是左子树,右子
树的搜寻次序要相反,如下图.
711
13
10
5
153
1468
前序法走访:先一路往左,再
中间,再右边,得到
1, 3, 4, 5, 6, 7, 8, 10, 11, 13, 15
711
13
10
5
153
1468
类似前序法走访:先一路往右,
再中间,再左边,得到
15, 13, 11, 10, 8, 7, 6, 5, 4, 3, 1
建立二元搜寻树与新增资料
–二元搜寻树的建立可依寻找节点资料的方法来建立,假设二元搜寻
树中的资料皆相异时,则每次皆搜寻不到,但以最后的终端节点连
结此新节点,而建立二元搜寻树,其步骤如下:
–1.假如是空树,建立根节点.
–2.将新增节点的资料k与根节点的资料m相比较:
(1)k > m
–(a)如果是非终端节点:搜寻右子树,原根节点换成右子树
的根节点,重回步骤2.
–(b)如果是终端节点:新节点建立成此节点的右子节点.
(2)k 20,建立右节点
40
20
(3) 15,因1520,往右寻找
因3520,往右寻找
因25<40,往左寻找
因2520,往右寻找
因3020,往右寻找
因50>40,建立右节点40
20
15
35
25
30
50
资料的顺序20,40,15,35,30,25,50
(1) 20,空树,建立根节点20
(2) 40,因40>20,建立右节点
40
20
(3) 15,因1520,往右寻找
因3520,往右寻找
因30<40,往左寻找
因3020,往右寻找
因2540,建立右节点40
20
15
35
30
25
50
与图11-39不同的地方
与图11-39相同
当要建立二元搜寻树的资料已经排好顺序了,则所建立的二元搜寻树是左斜二元树
(由大到小的资料项)或是右斜二元树(由小到大的资料项).这种已排序好的资
料项将会造成1+2+…+(n-1)的比较次数,总和等於n(n-1)/2,时间复杂度是
O(n2),而图11-37和图11-38等非排序过的资料项,其平均时间复杂度是O(nlog
n).已排序好的资料项建立二元搜寻树的图解说明如下图.
资料项由小到大排序(15,20,25,30,35,40,50)
所建立的二元搜寻树
20
15
25
30
35
40
50
资料项由大到小排序(50,40,35,30,25,20,15)
所建立的二元搜寻树
40
50
35
30
25
20
15
11-7 二元搜寻树
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/* 演算法名称:二元搜寻树的新增节点*/
/* 输入:新增节点到二元搜寻树*/
/* 输出:新增节点后的二元搜寻树*/
search_and_add(tree, key)
{
q = null;
ptr = tree;
while (ptr != null)
{
if (key == ptr->data)
return(p);
q = ptr; /* 把q设定为ptr节点*/
/* ptr节点往下看*/
if(keydata) /* 如果key此节点要小,看左边*/
ptr=ptr->left;
else /* 否则,看右边*/
ptr=ptr->right;
}
v = maketree(key); /* 产生一个新的节点*/
if (q == null)
tree = v;
else if (key data)
q->left = v;
else
q->right = v;
return(v);
}
11-7 二元搜寻树
删除二元搜寻树的节点
一颗已建立的二元搜寻树同样会因程式的运作,增加
节点或删除节点,当要删除的节点是终端节点时,只
要将其父节点原先对此节点的连结去除(指向null)
即可.
如果要删除的节点不是终端节点,则被删除的节点要
以最适合的节点来放入此被删除节点的位置,最适合
的节点有两个可能:
–1.其左子树的最右边节点(因为是左子树的最大值).
–2.其右子树的最左边节点(因为是右子树中的最小值).
图解说明如下图
m
LnR1
关系
(1) L子树中的所有资料m
(3) Ln是L子树的最右边节点,Ln是
L子树的最大值
(4) R1是R子树的最左边节点,R1是
R子树的最小值
LR
...< Ln< m < R1< ...
L子树R子树
P
情况1: Ln取代m
Ln
R1
L'R... < Ln< R1< ...
L'子树R子树
P
符合二元搜寻树定义
情况2: R1取代m
R1
Ln
LR'
L子树R'子树
P
符合二元搜寻树定义
...< Ln< R1< ...
当你去除m时,不管是Ln或是R取代其位置,以R为
例,此时你要做的事情有:
1.将原来R1的父节点对R1的连结设成空连结.
2.将原来m的父节点p连结到m的连结,改为连
结到R1.
3.将原来m的左节点,改为R1的左连结,将原
来m的右连结改为R1的右连结.
经过上述三个步骤的处理,即可维护一个二元搜寻
树,且找到LR或R1点的次数最多是高度h的次数.所
以维护一个二元搜寻树的平均时间是
O(log n),最差情况是O(n).
11-7 二元搜寻树
有关二元搜寻树的删除节点演算法范例程式
请参考本书11-7-7 删除二元搜寻树的节点
资料结构与演算法
课程教学投影片
第十二章–图形
本章各段大纲
12-1图形结构
12-2图形的资料结构
12-3图形的走访
12-4扩张树和最小成本扩张树
12-5最短路径问题
12-6拓朴排序
12-1图形结构
图形结构类似於树状结构,树状结构主要是以阶层为特性,节点的布局是由上
而下的关系,而图形则没有如树的阶层关系,且每个点之间,都可以相互连
结.
图形结构的基本定义:
–顶点(Vertix):如同树状结构的节点,它是图形中的点,一般以V为代表
符号.
–边(Edge):如同树状结构的连结线,它是图形中两顶点之间的连线,一
般以E为代表符号.也有人称边为孤线(Arc).
–方向性:边可以分为有方向性(directed)和无方向性(undirected)两
种,有方向性的边称为有向边,无方向性的边称为无向边;同理有方向性
的图形称为有向图,无方向性的图称为无向图.
–回圈:一个顶点有一个边连结到它自己.
–平行:如果一个顶点连结到其他节点的无向边或有向边不只一条时,这种
图形称为多边图(multigraph).
CC
DDEE
FF
CCDD
A
BC
DEF
无向图
无向图
有向图
无向边
顶点
有向边
B
A
AB
BA
CD
BA
C
ED
平行回圈
平行
回圈
图形基本结构图示说明
两顶点之间最多有1条线,3个顶点间最多有3条线,其实n个顶点之间最多有n (n-1)/2条
边.
范例1:证明有n个顶点的图形,最多有n(n-1)/2无向边.
–(1) n个顶点之中的任两个顶点都有边时,其边数最大问题相当於n个顶点中,任何
两个顶点的组合数共有多少个,此问题以数学的组合公式可得
–(2)可以用递回的想法来证明,假设只有1个顶点时,没有边,有2个顶点时(即加入
1个新顶点)会增加1条边(即原有的顶点数),所以2个顶点时有1条边.
–当加入第3顶点时,则此顶点可和原先的2顶点相连,可再增加2条边,所以总共有3
条边.
–以数学递回公式表示:E(n)=k,n代表n个顶点,k代表k条边
E(1)=0
E(2)=E(1)+1=1
E(3)=E(2)+(3-1)=1+2=3
…
所以E(n)=E(n-1)+(n-1)
求E(n)=E(n-1)+(n-1)
=E(n-2)+(n-2)+(n-1)
=E(n-3)+(n-3)+(n-2)+(n-1)
…
=E(1)+1+2+…+(n-2)+(n-1)
=0+1+…+(n-2)+(n-1)
=n(n-1)/2得证
12-1图形结构
在顶点与顶点之间尚有以下的定义:
–相邻(adjacent):如果两个顶点(U和V)之间有边相连,则称这
两个顶点相邻,此边可用(U,V)表示.如果是有向图,则边有方向
性要考虑,如果由U连结到V,称U相邻到V,以(U,V)表示.如果
由V连结到U,称U从V相邻,以表示.
–分支度:在无向图中,顶点U上的总边数称为U的分支度
(degree).在有向图中,顶点U连结到别的顶点的边数,称为向外
分支度(out-degree);顶点U被所有顶点连结的边数称为向内分支
度.
–总分支度:无向图中总有顶点分支度的总和称为总分支度,同理有
向图中有向内总分支度和向外总分支度.
A
B
E
C
D
(a)
(b)
A
B
E
C
D
1223322分支度
总分支度EDCBA
1223322分支度
总分支度EDCBA
边有(A,B), (A,C) ,(B,D), (C,D),(C,E),(D,E)
分支度A:2 ,B:2 ,C:3 ,D:3 ,E:2
A和B相连,B和E不相邻.
改为
边有(A,B), (B,D), (D,E), (D,C), (E,C), (C,A)
ABCDE合计
向内分支度113128
向外分支度212218
相邻与分支度的关系
【结论一】
一无向图中,总分支度d和总边度e的关系为d=2*e.
例如图12-4(a)中有6条边,总分支度为12,因为每条边在算分支度时,被算了两次.
【结论二】
一有向图中,总向内分支度di,总向外分支度do,总有向边数e的关系为di=do=e.
子图:只取用原图形的部分顶点和部分边,但不能有不属於原图形的顶点或边,则此图
形称为原图形的子图,如下图.
路径(path):一条由顶点U连结到顶点V,所经过顶点V1,V2,…,Vn的路线称为路
径,以U-V1-V2…-Vn-V表示,此条路径所经过的边数称为路径长度(length).
A
B
E
C
D
A
B
ED
A
BC
D
A
B
E
C
原图形是子图是子图不是子图
不是原图
的边
A
B
E
C
D
A-B-D 路径长度2
A-C-D-E 路径长度3
A-B-D-C-E 路径长度4
A-C-B 不是路径,因C和B不相连
简单路径(simple path):除了顶点和终点之外,其他的顶点皆不同的路径,称为简单
路径.
回路(cycle):起点和终点相同的简单路径.
A-B-D-E是简单路径
A-B-D-C-E是简单路径
A-B-D-C-E-D不是简单路径,因为D重覆了
A
B
E
C
D
A-B-D-C-A 是回路
A-B-D-C-E-D-B-A 不是回路,因为B,D重覆
A-B-D-E-C 不是回路,起点是A,终点是C,两者不同
A
B
E
C
D
相连图形(connected graph):图形中的任何两个顶点皆有路径相连.
相连子图(connected component):图形中最大的相连图.
A
B
E
C
D
是相连图形非相连图形
A
BC
ED
无法连到E
A
BC
D
A
BC
相连组合
强固相连(strongly connected):在一有向图中,任意两顶点之间都有路径可相连.
无回路图形(acyclic graph):不存在回路(cycle)的图形.例如树即是一个相连图
形,无回路图形.
BA
CD
是强固相连不是强固相连,因A可连到C,但C
不可连到A
BA
CD
CB
FE
DA
有回路图形
CB
FE
DA
有回路图形
CB
FE
DA
无回路图形
CB
FE
DA
无回路图形
12-1图形结构
加权重图形
先前介绍的图形只有无向边和有向边表示顶点之间的连线关系,但有些问题
(例如最短路径问题)除了要记录顶点之间的连结关系,还需记录其他的资料
(例如成本,路径长,资料量等),此资料一般称为权重(weight).一般是
将这些资料标记在边上,一个有标示权重的图形称为「加权重图形」
(weighted edges graph),如下图.
C
A
D
B
E
2
2
3
4
10
5
8
12-2图形的资料结构
邻接阵列表示法
因为图形是一个平面的关系,任何两顶点之间皆可能有边相连,所以可以用二
维阵列来表示图形结构,此二维阵列称为邻接阵列(adjacency matrix).
C
A
D
B
E
C
A
D
B
E
邻接阵列
皆是0
对称
C
A
D
B
E
C
A
D
B
E
00001
00101
01010
00101
11010
00001
00101
01010
00101
11010
00000
00110
00000
01101
11010
00000
00110
00000
01101
11010
皆是0
4E
3D
2C
1B
0A
4E
3D
2C
1B
0A
4E
3D
2C
1B
0A
4E
3D
2C
1B
0A
43210
EDCBA
43210
EDCBA
43210
EDCBA
43210
EDCBA
12-2图形的资料结构
由上图知邻接矩阵是由0和1所组成的矩阵,而且无向图的邻接矩阵是对称的,
即X[i][j]=X[j][i],但有向图的邻接矩阵不一定对称.假如要计算各节点的分
支度时,可以加总其列的数字,即为该顶点的分支度,计算公式如下:
C
A
D
B
E
代表向
代表向
4E
3D
2C
1B
0A
4E
3D
2C
1B
0A
00000
1
0
0
0
1
2221
1110
0000
1101
0010
00000
1
0
0
0
1
2221
1110
0000
1101
0010
43210
EDCBA
43210
EDCBA
加总
加总
0
2
0
3
3
0
2
0
3
3
以有向图为例,如图12-16
对於加权重图形以邻接阵列来表示时,其方法和前面所介绍的方法类似,只是原先1代表有
边,0代表没有边,现在要将权重数值取代1,代表有边和权重,0还是代表没有边,如下图.
2C
A
D
B
E
2
3
4
10
5
8
C
A
D
B
E
2
3
4
10
5
8
C
A
D
B
E
2
3
4
10
5
8
2C
A
D
B
E
2
3
4
10
5
8
2
4E
3D
2C
1B
0A
4E
3D
2C
1B
0A
0802
80240
02050
4503
20030
0802
80240
02050
4503
20030
08002
00240
00000
0500
00030
08002
00240
00000
0500
00030
43210
EDCBA
43210
EDCBA
10
10
10
43210
EDCBA
43210
EDCBA
4E
3D
2C
1B
0A
4E
3D
2C
1B
0A
邻接串列表示法
当顶点数很多,边数很少时,如果使用邻接矩阵来表示时,将会造成一个稀矩阵,很浪费空间,且也
可能造成程式运作效率变差,当遇到这种情况时,可以考虑用另一种链结串列来表示.
用链结串列来表示时,每个链结串列仅代表一个顶点的结构,要代表所有顶点的链结串列要用到多个
链结串列,称为邻接串列(adjacency list),其顶点的结构是:
图形的邻接串列表示法如下图:
以C语言来表示上图的邻接串列时,其结构宣告如下:
structV/*宣告图形顶点结构*/
{
intvertex;/*邻接顶点资料*/
structV*next;/*下一个邻接顶点*/
}
typedefstructV *PVertex;/*定义图形结构*/
PVertexhead[100];/*宣告顶点阵列*/
2
0
3
1
4
2
0
3
1
4
4
3
2
1
0
E
D
C
B
A
4
3
2
1
0
E
D
C
B
A
22
Null
Null
33
2211Null
00
443311
Null
Null443311Null
12-3图形的走访
图形的走访
树有前序法,中序法和后序法走访三种,图
形的走访和树的走访概念相同,都是要能够
走访到所有顶点.图形的走访方法有深度优
先法(Depth-First-Search,DFS)和广度
优先法(Breadth-First-Search,BFS).
12-3图形的走访
深度优先法
深度优先法的「深度」可看成是「路径」的意思,亦即往路径方向走
访,在走访的过程中,每个顶点可能有很多邻接顶点,所以走访哪个顶
点并不确定,其走访步骤如下:
–1.由某一顶点U出发,标记已被走访.
–2.U的邻接顶点可能有很多个V1,V2,…,Vn,以回圈方式依序走访
V1,V2,…,Vn,当走访V1时,先标记V1已被走访,且有以下两种
情况.
(1)V1的邻接顶点皆已被走访过,则回到U,以下一次V,继续同
样步骤2的走访.
(2)V1尚有未被走访过的顶点,则同步骤2的方法,由其邻接顶
点W1,W2,…,Wm中,以回圈方式控制W1,W2,…,Wm的走
访,如果W1,W2,…,Wm已被走访过则略过,否则又回到步骤2
的程序.
12-3图形的走访
01
02
03
04
05
06
07
08
09
10
11
12
13
/* 演算法名称:深度优先法搜寻DFS */
/* 输入:图形G=(V,E) ,V={0,1,2,…,n-1} */
/* 输出:深度优先法搜寻顶点顺序*/
DFS(U)
{
visited(U); /* 将U做记号,表示已经走访过*/
for(U的所有相邻顶点V(V1,V2,…,Vn))
{
if(visited(V)==0) /* 如果V未走访过,呼叫DFS(V) */
call DFS(V)
}
}
21
45
306
(1)编号0,有邻接顶点1,4
(2)编号1,有邻接顶点0,2,5
已标记不处理
标记
(4)编号3,有邻接顶点2 ,6
(5)编号6,有邻接顶点3,5
(3)编号2,有邻接顶点1,3,4,5
(7)编号4,有邻接顶点0,2
(6)编号5,有邻接顶点1,2 ,4
所以深度走访的次序为0 1 2 3 6 5 4
21
45
360
再回头看是否还
有未被拜访的顶
点,此程序由递
回自动控制.
1111
65432106543210
111111
65432106543210
11111111
65432106543210
1111111111
65432106543210
111111111111
65432106543210
11111111111111
65432106543210
11111111111111
65432106543210
图形的深度优先法-
图示流程
12-3图形的走访
广度优先法
广度优先法跟深度优先法相反,顾名思义它是以某顶点的广度优先处理,即先
走访某顶点的所有邻接顶点,再逐一往下一个邻接顶点,作同样的广度优先法
程序,直到所有的顶点皆被走访过.其走访步骤如下:
–1.由某顶点U出发,并标记为已被走访过.
–2.U的邻接顶点可能有多个V1,V2,…,Vn,优先走访每个V1,V2,…,Vn顶点,
并标记已被走访过.当结束时,依序选取V1,V2,…,Vn,再回到步骤2的相
同处理程序.
–3.当所有的顶点皆被走访过,则步骤结束.
如果以资料结构和顶点处理的顺序的角度来看,其演算法步骤如下:
–1.由某顶点U出发,并标记为已被走访过.
–2.将U的所有邻接顶点放入伫列(queue)中.
–3.从伫列中取出一顶点V,标示此顶点已被走访,同步骤2的方法,将V的所
有邻接顶点放入伫列,重复步骤3直到伫列空了为止.上述的演算法步骤图
解说明如下一页图示.
21
45
306
11
65432106543210
1111
65432106543210
111111111111
11111111112535625356
65432106543210
111111
65432106543210
1111
65432106543210
(1)编号0,放入1,4到伫列
(2)编号1,放入0,2,5到伫列(2)编号1,放入0,2,5到伫列
(3)编号4,放入0,2,5(3)编号4,放入0,2,5
1414
标记标记
取出
425425
25252525
(4)编号2,放入1,3,5(4)编号2,放入1,3,5
5253552535
65432106543210
(5)编号5,放入1,2, 4,6(5)编号5,放入1,2, 4,6
(6)编号3,放入2,6(6)编号3,放入2,6
566566
11111111111111
65432106543210
(7)编号6,放入3, 5(7)编号6,放入3, 5
66
21
45
360
结束,广度优先法为0 1 4 2 5 3 6结束,广度优先法为0 1 4 2 5 3 6
图形的广度优先法-
图示流程
12-3图形的走访
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
/* 演算法名称:广度优先法搜寻BFS */
/* 输入:图形G=(V,E) ,V={0,1,2,…,n-1} */
/* 输出:广度优先法搜寻顶点顺序*/
BFS(U)
{
call addq(U); /*将U放入Q中,Q是伫列*/
While(Q not empty)
{
S = delq(U,Q) /*取出伫列中的元素*/
for(S的所有邻接顶点V)
{
if(visited(V)==0) /* 如果V未走访过*/
call addq(V,Q) /*V放入伫列*/
}
visited(S) /*S=1,标记已被走访过*/
}
}
12-3图形的走访
DFS与BFS比较
深度优先法(DFS)以深度(路径长度)优
先,可以用回圈和堆叠控制要走访的顶点;
而广度优先法(BFS)以广度(分支度)优
先,可以用伫列来控制要走访的顶点
DFS与BFS应用
图形的走访可应用於下列几项:
–1.找出一个无向图形的扩张树(spanning
tree):
一个无向图形的扩张树是指能以最少的边
数来连结图形中的所有节点,而不产生循
环的子图,如图12-18和12-19走访结果的
图形皆是扩张树.
–2.判断无向图形是否为一个相连图形
(connected graph):
在一个无向图中,若以顶点U出发,不管使
用深度优先法或广度优先法时,如果能走
访完所有的顶点,则此无向图是相连图
形,否则不是一个相连图形.
–3.找出一个无向图的相连子图:
在无向图形中,以任何一个尚未被走访过
的顶点当作起始点,每经过一次深度优先
法走访或广度优先法走访,可找到相连子
图.对於尚未被走访的顶点,再重复上述
方法即可找出所有的相连子图,其中最大
的相连子图称为「相连单元」,如右图.
(1)以0为出发顶点,深度优先法可得
10
423
85
67
10
423
,是一个相连子图.
(2)此时5,6,7,8无法被走访,以5为出发顶点,深度优先法可得
85
67
,也是另一个相连子图.
12-3图形的走访
01
02
03
04
05
06
07
08
09
10
11
/* 演算法名称:用深度优先法,找出图形的相连子图*/
/* 输入:图形G=(V,E) ,V={0,1,2,…,n-1} */
/* 输出:广度优先法找出图形G所有的相连子图的顶点顺序*/
ConnectGraph()
{
for(V的所有相邻顶点V(V0,V1,V2,…,Vn-1))
{
if(visited(Vi)==0) /* 如果Vi未走访过,呼叫DFS(Vi) */
call DFS(Vi)
}
}
12-4扩张树和最小成本扩张树
扩张树结构
由前一节介绍的深度优先法和广度优先法得知,如果是一
个有n个顶点的相连图形,经由这两种演算法走访的结果,
会得到用最少的边来连结所有的顶点,且不会形成回路,
这样的子图是一种树状结构,也就是任何两顶点之间的路
径唯一,这种可连结所有顶点且路径唯一的树状结构称为
扩张树(spanning tree)或称生成树,扩展树,它可应用
在许多方面,例如顶点代表乡镇,边代表道路,原先的图
形是计画中要兴建的道路,但现在希望兴建最少的道路,
但还是可以让所有的乡镇可通的情况下,则需要用到扩张
树.
【定义】
假设一相连图G=(V,E),V是顶点的集合,E是边的集合,则从任一顶点出发走访
所有的顶点,所经过的边组织成集合Ey,未被走访的边组织成集合En,则
E=Ey∪En且Ey∩En=Φ,则这些被走访的顶点V和边集合会形成一颗树
T=(V,Ey),则称T是G的扩张树.
A
BC
D
(b)
A
BC
D
(b)
A
BC
D
(c)
A
BC
D
(c)
A
BC
D
(d)
A
BC
D
(d)
A
BC
D
(e)
A
BC
D
(e)
皆是(a)的扩张树皆是(a)的扩张树
皆不是扩张树皆不是扩张树
A
BC
D
(f)
A
BC
D
(f)
A
BC
D
(g)
A
BC
D
(g)
A
BC
D
(h)
A
BC
D
(h)
A
BC
D
(i)
A
BC
D
(i)
A
BC
D
(a)
A
BC
D
(a)
扩张树在实际的应用上不止是找出顶点和边而已,如果一个相连图形的边加上
权重值(weight),来代表边的成本,距离等.则我们希望所产生的扩张树之
所有边的权重值加总为最小,具有这样性质的扩张树称为最小成本扩张树
(minimum-cost spanning tree).
例如以一个小型区域网路架设为例,如下图,假设顶点代表机房中的转接器
(hub),顶点1,2,3,4,5分别代表各部门的hub,因为地理因素关系,各顶
点能够连结的逻辑架构图如下图(a),但加上实际的权重(距离)时,其架构如
下图(b),以顶点0为出发点,则其扩张树有很多情形,如下图(c)(d)(e),你可
以量出各种可能,但是(d)图是所有扩张树中所有权重值总和最小者,即为最小
成本扩张树.
21
34
50
21
34
50
深度优先法
广度优先法
8
4
1523
1
13
5
1020
21
4
50
8
4
152
21
34
50
4
23
1
5
(a) (b)
(e)(d)
(e)
21
34
50
4
23
1020
权重值总和
=1+2+3+4+5=15
权重值总和=2+3+4+10+20=39
权重值总和=2+8+15+4+1=30
3
1
12-4扩张树和最小成本扩张树
由上一页图示得知,不能用深度优先法或广
度优先法求最小成本扩张树,接著介绍两种
著名的演算法-Kruskal演算法和Prime演算
法(分别称为K氏,P氏演算法)来求最小扩
张树,这两种演算法都是使用「贪心策略」
(greedy strategy).
12-4扩张树和最小成本扩张树
Kruskal演算法
Kruskal演算法是每次选取最小权重值的边,不用从某顶点出发,然后
检查是否形成回路,会形成回路的边不能取用,因为是由小到大取边以
形成扩张树,所以可建构最小成本扩张树(MST).一个有n个顶点的相
连图形,其Kruskal的演算步骤如下:
–1.边的权重值先由小到大排序.
–2.从所有未走访的边中取出最小权重值的边,记录此边已走访,检
查是否形成回路.
(1)形成回路,此边不能加入MST中,回到步骤2.
(2)未形成回路,此边加入MST中,如果边数已达(n-1)条则到
步骤3,否则回到步骤2.
–3.Kruskal可以找出MST,结束.
详细图示请看下一页
21
34
50
5
4
1523
1
138
1020
(1)建立边由小到大的排序(2)取出(3,4)建立边
(3)取出(0,1)建立边
(4)取出(0,2)建立边(5)取出(4,5)建立边
1(3,4)
10(0,4)
8(2,4)
5(1,2)
13(1,3)
15(2,5)
20(0,3)
4(4,5)
3(0,2)
2(0,1)
1(3,4)
10(0,4)
8(2,4)
5(1,2)
13(1,3)
15(2,5)
20(0,3)
4(4,5)
3(0,2)
2(0,1)
34
1
34
1
1
0
1
0
1
0
21
0
2
(6)取出(1,2)形成回路
不建立边
3434
3434
34
5
34
5
34
5
34
5
1
0
21
0
21
0
21
0
2
(7)取出(2,4),建立边,已
达6条边,结束.
1
0
2
34
5
1
0
21
0
2
34
5
34
5
权重值总和
=1+2+3+4+8=18
不检查20(0,3)
不检查15(2,5)
不检查13(1,3)
不检查10(0,4)
要8(2,4)
不要5(1,2)
要4(4,5)
要3(0,2)
要2(0,1)
要1(3,4)
不检查20(0,3)
不检查15(2,5)
不检查13(1,3)
不检查10(0,4)
要8(2,4)
不要5(1,2)
要4(4,5)
要3(0,2)
要2(0,1)
要1(3,4)
边MST边权重值
12-4扩张树和最小成本扩张树
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
/* 演算法名称:Kruskal演算法*/
/* 输入:图形G=(V,E),|V|=n,W(ei)为ei上的加权值*/
/* 输出:T,T是图形G的最小成本扩张树*/
Kruskal()
{
while((T的边数<=n-1)&&(E边的个数不为0))
{
从E中选出最小权重值的边ei
从E中删除ei
if (ei加入T中不会形成回路)
加入ei到T中
}
if(T的边数<(n-1))
输出"G无最小成本扩张树";
else
输出T;
}
12-4扩张树和最小成本扩张树
Kruskal演算法分析
假设有一个n个顶点e条边的相连图形作Kruskal演算
法,必须先对边进行排序,所需时间O(elog e),所
建立的E如果是阵列,则演算法虚拟码的第4行的时间
是O(e),如果用堆积来存放边,则第4,5行每次取出
最小边和删除的最平均时间是O(loge),最差情况要
对所有的边皆处理,则其时间为O(elog e),所以
Kruskal演算法的时间复杂度为O(elog e) 或者是O(n2
log n),因为e=O(n2).
12-4扩张树和最小成本扩张树
Prim演算法
在前一节介绍的Kruskal演算法要去检查所有加入
的边是否造成回路,另有一种Prim演算法是避免回
路的检查,作法是从某点U出发,列出顶点U所有邻
接点的边,选择最小的边(U,V)加入最小成本扩张
树中,然后删除(U,V)边,再加入顶点V除了(U,V)
边之外的所有连结边,再找出最小的边,以此类
推,直到找到了n-1条边,即可产生最小成本扩张
树.
12-4扩张树和最小成本扩张树
假设一无向图形G=(V,E),Tv为最小成本扩张树的
顶点,X是作用的边,TE是最小成本扩张树的边.
Prim演算法步骤如下:
–1.选出某一顶点U开始.
–2.将U的所有边加入X中,将U加入TU中.
–3.从X中找出最小权重值的边(U1,V1),X去除(U1,V1).
–4.将V1加入TU中,如果TU顶点数=n,则跳到步骤6.
–5.将V1对应到V-TU顶点的所有边加入X中,回到步骤3.
–6.TU,TE是最小成本扩张树,结束.
21
34
50
5
4
1523
13 8
1020
1
21
34
50
5
4
1523
13 8
1020
1
(1)由1开始
1
0
2
3
4
5
1
0
2
3
4
5
Tu V-TuTE
(2)选出最小者(0,2),权重值=3
21
0
23
选出最小者(0,2),权重值=3
21
0
23
21
0
23
2
3
4
5
1
20
3
Tu
13
10
5
TE V-Tu
21
0
23
4
8
选出最小者(2,4),权重值=8
21
0
23
4
8
21
0
23
4
8
选出最小者(2,4),权重值=8
2
3
13
0
(3)3
4
5
1
0
2
Tu
13
20
10
15
V-TuTE
8
(3)3
4
5
1
0
2
Tu
13
20
10
15
V-TuTE
8
Prim演算法的图解说明如图
21
0
23
4
8
选出最小者(4,3),权重值=1
3
1
21
0
23
4
8
选出最小者(4,3),权重值=1
3
21
0
23
4
8
选出最小者(4,3),权重值=1
3
1
(4)1
0
2
4
3
5
20
4
Tu
13
13
15
TE V-Tu
(4)1
0
2
4
3
5
20
4
Tu
13
13
15
TE V-Tu
21
0
23
4
8
选出最小者(4,5),权重值=4
3
5
4
1
(5)
1
0
2
4
3
5
4
Tu
15
TE V-Tu
21
0
23
4
8
选出最小者(4,5),权重值=4
3
5
4
1
21
0
23
4
8
选出最小者(4,5),权重值=4
3
5
4
1
(5)
1
0
2
4
3
5
4
Tu
15
TE V-Tu
1
0
2
4
3
5
Tu TE V-Tu
结束
(6)
1
0
2
4
3
5
1
0
2
4
3
5
Tu TE V-Tu
结束
(6)
12-4扩张树和最小成本扩张树
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
/* 演算法名称:Prim演算法*/
/* 输入:图形G=(V,E),|V|=n,,W(ei)为ei上的加权值*/
/* 输出:T,T是图形G的最小成本扩张树*/
Prim()
{
TU=V1
加入顶点U对V-TU的所有边到X中
while (TU的顶点数<n)
{
选出X中权重值最小的边,ei且删除之
u到TU中,边加入到TE中
加入顶点V对V-TU的所有边到X中
}
if(TU的顶点数<n)
输出"G无最小成本扩张树";
else
输出T;
}
12-5最短路径问题
最短路径问题
利用图形结构来表示问题的样貌时,要处理的典型
问题有最短路径问题.因为图形中某顶点到达各顶
点的路径不是唯一,如果要从众多的路径中找出路
径最短者,则称为最短路径问题,可分为两种形
式:
–出发点最短路径问题:由某顶点到所有顶点间的最短路
径.
–顶点对最短路径问题:所有任意两顶点间的最短路径.
出发点最短路径问题
「出发点最短路径问题」是分别列出某出发点到所有其他顶点的最短路径(如
果有权重值,是指路径的权重值总和最小,如果没有权重是指边数的总和,或
者边的权重值看成是1,计算权重值的总和).
应用
此问题的典型应用是由城市(顶点)与城市(顶点)之间交通路网(边)的距
离(权重值),计算由某顶点出发,经由交通路网的计算,得到某顶点到各城
市的最短路径,此问题可应用在旅行时的路线选择,或者是航空班机的转运服
务,或者是物流通运业的转运服务等,典型的交通路网如下图.
12
3
70
5
4
6
300
800
1000
1700
1200
1500
1000
900
1400
1000
Los An geles
San Fr an cisco
Ch icago
Boston
New York
Miamy
New Oricans
Deriver
600
此问题的形式也可应用在专案管理方面,例如某个工作(job)的完成之前,必须经由某
些工作必须先完成,才可开始,而且完成一个工作的途径或流程不唯一,则专案管理可
以用图形结构来表示,且经由解决由顶点到各个顶点的最短距离(工期)表示某个工作
(顶点)的完成时间.例如以一个系统开发为例,各个程式模组视为顶点,边的权重值
代表工期(天数),如下图.
专案起始
EA
CD
FS
专案结束
B
H
End
G
假设顶点S到所有的顶点最短路径如下
5
8
4
1
3
2
5
EA
CD
FS
专案结束
B
H
End
G
假设顶点S到所有的顶点最短路径如下
5
8
4
1
3
2
5
S
A
C
B
E
D
F
G
H
End
其中S到A是经过S B A,权重值为
2+1=3,而不是S A的权重值为5
8
2
1
1
12-5最短路径问题
原理
解决此问题的主要原理有点类似Prim演算法,如图12-27由顶点S出发,
它有3个相连顶点A,B,C,先取得C,此即为S'到C的最短路径,因为你
若不选择此条路径,想说或许从B,C连结出去,再连回A时可能会较短
距离(权重值),但这是不可能的.因为我们选择S-C是目前S-A,S-
B,S-C中最短者,所以S-B或S-C再加上其他路径一定还是比S-A大(不
考虑负数,否则无法运作).
接著由顶点S'连结到各顶点的看法变成{S,C}连结到各顶点了,因为可
经由C来「转接」,例如{S,C}现在可连结到{A,B,D}了.
此时S连结到B的最短路距离为2,但经由S-C-B的最短距离1+3=4,且计
算{S,C}到{A,B,D}所有可能的最短距离,此时取出最短距离的顶点(如
同第1次取出C的原理).以这样的方式和原理逐次取出顶点,即可解决
某顶点到所有顶点的最短路径问题.
12-5最短路径问题
演算法
假设一无向图G={V,E},V是顶点集合,E是边集合,Gm={Vm,Em},Gm,
Vm,Em是此问题解答的图形,顶点,边,W(i)代表各个边的权重值,Ek
代表作用中的边,n代表顶点数.步骤如下所示:
–1.取出V1出发点,加入Vm中.
–2.取出V1向外相连的边加入到Ek中.
–3.从Ek中取出最小者W(i),例如Vi为顶点,Vi加入Vm中Ei加入Em
中,如果Vm的顶点数=n则跳到步骤5.
–4.印出Vi其他未被放入Vm的相邻顶点,针对这些顶点检查是否出现
在Ek中.
(a)如果出现在Ek中:取Ek中的边(先前的最短路径+目前权重值)最小
值者,取代此边.
(b) 如果未出现在Ek中:将这些边+目前权重值,放入Ek中,回到步骤
3.
–5.列出顶点Vm和边Em,结束.
D阵列
BA
CD
ES
2
8
10
5
17
6
1113
3
9
4
9
BA
CD
ES
2
8
10
5
17
6
1113
3
9
4
9
43210
EDCBA
43210
EDCBA∞∞∞∞∞∞∞∞∞
71927192
EDCBAEDCBA
∞∞
调整
A
S
C
B
17
A
S
C
B
从S到顶点的路离
2
2+5=7
0+10=10
2+7=9
A
虚线是候选的边
取出S A
S
C
103
(1)
调整
A
S
C
B
17
A
S
C
B
17
A
S
C
B
从S到顶点的路离
2
2+5=7
0+10=10
2+7=9
A
S
C
BA
S
C
B
从S到顶点的路离
2
2+5=7
0+10=10
2+7=9
A
虚线是候选的边
取出S A
S
C
103
(1)A
虚线是候选的边
取出S A
S
C
103A
虚线是候选的边
取出S A取出S A
S
C
103
(1)
取出A C(2)
调整
A
S
C
B
2
9
4
19
D
A
S
C
B
277+4=11
19
D
7+=16
取出A C(2)取出A C取出A C(2)
调整调整
A
S
C
B
2
9
4
19
D
A
S
C
B
2
9
4
19
D
A
S
C
B
277+4=11
19
D
7+=16
A
S
C
B
277+4=11
19
D
7+=16
71627162
EDCBAEDCBA
11
219219219219219219219219
取出C D(3)A
S
C
B
27
11
19
D
16E
6
取出C D(3)取出C D取出C D(3)A
S
C
B
27
11
19
D
16E
6
A
S
C
B
27
11
19
D
16E
6
A
S
C
B
27
11
19
D
16E
6
17716217716211
EDCBAEDCBA
A
S
C
B
27
11
19
D
16E
11+6=17
A
S
C
B
27
11
19
D
16E
11+6=17
A
S
C
B
27
11
19
D
16E
11+6=17
A
S
C
B
27
11
19
D
16E
11+6=17
(4)取出C EA
S
C
B
2711
16
D
E
173
(4)取出C E(4)取出C EA
S
C
B
2711
16
D
E
173
A
S
C
B
2711
16
D
E
173
A
S
C
B
2711
16
D
E
173
EDCBAEDCBA
17716217716211
A
S
C
B
27
1116
D
16+3=19
E
17
A
S
C
B
27
1116
D
16+3=19
E
17
A
S
C
B
27
1116
D
16+3=19
E
17
A
S
C
B
27
1116
D
16+3=19
E
17
(5)取出D E
A
S
C
B
2711
16
D
E17
(5)取出D E(5)取出D E
A
S
C
B
2711
16
D
E17
12-5最短路径问题
第5行while执行次数共n-1次,时间复杂度O(n),第8,9,10行一样需要O(n)的时间,所
以总共时间为O(n2).
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/* 演算法名称:Dijkstra演算法*/
/* 输入:图形G=(V,E),|V|=n,V={0,1,…,n-1} */
/*两点i,j的距离为W[i,j] ,i!=k */
/* 输出:一顶点U到另一顶点V的最短距离,U!=V */
Dijkstra()
{
for (对每个顶点i=1 to n)
设定Dist[i]=eight(u,i)
/* 取出出发点顶点*/
Visited[m]<-1
Dist[m]=0
while (Vm的顶点数<n)
{
/* 找没有看过,而且集合中符合最小边的顶点*/
v = Dist集合中最小者,且Visited(v)=0
Visited(v)=0
for(对於尚未走访的顶点i)
{ Dist[i]<-min(Dist[i],Dist[v]+Weight[v,i]) }
}
}
12-5最短路径问题
顶点对最短路径问题
求最短路径的另一个问题是求任何两个顶点(点对点)之间的最短距
离,这个问题最简单的想法是用前一节介绍的dijkstra演算法,对每个
顶点都作一次dijkstra演算法,即可解决此问题不过本节要再介绍另一
个称为Floyd的演算法来解决此问题.
应用
顶点对最短路径问题除了可以应用在交通路网,计算城市与城市之间交
通的最短路径之外,还可应用在许多方面,例如,假如你是从事国际贸
易业,你要转送物品样本或销售产品给国外客户,你可以选择航空运送
或船舶运送,飞机或轮船有不同的转运站,而每个航程的费用又不一
样,你可以把这些资讯以图形结构来表示,然后求各顶点对之间的最小
成本.
原理
这个问题表面上看起来很困难,但如果你了解了其原理和演算法,其实很简
单,而且只要用到阵列结构及使用3层回圈即可,算是很简单的一种演算法.
本章介绍过用二维阵列A来表示图形结构的资料,当两顶点U,V之间有权重值W
时,则在A[U][V]指定W,即
A[U][V]=W
其实这个A阵列可看成未经过任何顶点W「转接」时的最小成本,如果U→W之间
有连结,W→V之间有连结,则考虑U→V的最短距离时,至少有U→V和U→W→V两
条路径,取两者距离小者,即为U到V的最短路径了,如下图.
W
UV
2
3
W
UV
2
3
UV
2U到V的路
径
距离A[U][V]UV
2
UV
2U到V的路
径
距离A[U][V]
UV
2
W3
路径=
距离A[U][W]=
A[U][V]+A[V][ W]=2+3=5
UV
2
W3
UV
2
W3
路径=
距离A[U][W]=
A[U][V]+A[V][ W]=2+3=5
W
UV
2
36
原先A[V][W]=6,但由上图知其实U V W
路径的最短路路径只有5,应取代A[U][W]的
值.所以当加入w点可转接时
A[U][W]=
min(A[U][W],(A[U][V]+ (A[V][W])
12-5最短路径问题
所以经过W点转接时,可以位每个顶点重新利用公式重新计算一遍,即
A[U][V]=min(A[U][W], A[U][V]+ A[V][W])
for (U=0;U<=n-1;U++)
for (W=0;W<=n-1;W++)
A[U][W]=min(A[U][W],A[U][V]+A[V][W]);
上述程式执行后的结果即为加入W点可转接时,所有顶点对之间的最短路径.
同理,如果一个图形有n个点,只要对每个顶点都逐一作上述的回圈运算,则最后的结果
A[U][V]即是经由所有顶点转接后的顶点U到顶点V的最短路径了,因此只要再架一层回圈
控制V,即可解决顶点对最短路径问题.
for (V=0;V<=n-1;V++)
for (U=0;U<=n-1;U++)
for (W=0;W<=n-1;W++)
A[U][W]=min(A[U][W],A[U][V]+A[V][W]);
12-5最短路径问题
这个Floyd演算法使用了n*n阵列,5,6,7行用了三个n次的回圈,所以时间复杂度为
O(n3),和Dijkstra演算法一样.
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
/* 演算法名称:Floyd演算法*/
/* 输入:图形G=(V,E),|V|=n,V={0,1,…,n-1} */
/*两点i,j的相邻矩阵为W[i,j] ,0<=i,j<=n-1 */
/* 输出:任意两点U,W最短距离矩阵A,U!=V */
Floyd()
{
for (u=0;u<=n-1;u++)
for (w=0;w<=n-1;w++)
A[u][w]=w[u][v];
/*原始邻接阵列/
for (v=0;v<=n-1;v++)
for (u=0;u<=n-1;u++)
for (w=0;wm,则y1=y/r
13-2 杂凑函数-平方取中法范例
13-2 杂凑函数-折叠法
折叠法是将键值分成几段,除了最后一个之
外,其余各段的长度要一样,再依下列两种
方法将各段数值加总得y,y值再作除以桶址
m的余数运算,得到k即为桶址
–第一种方法:称为移动折叠法,将各段数字直
接相加的y
–第二种方法:称为边界折叠法,将奇数段或偶
数段数字反转,加总数字,得y
13-2 杂凑函数-折叠法范例
13-2 杂凑函数-抽取法
抽取法是抽取键值x中最具杂凑效果的几个
单一数字组合成y值,例如桶址有1000个,
则抽取3个数字,如果抽取的数字比桶址范
围大,再以余数运算取其余数当作桶址.
13-2 杂凑函数-抽取法范例
13-2 杂凑函数-乘法
因为除法13-2-2节介绍的除法取决於m的选取,如
果m选得不恰当,容易造成碰撞,如果用乘法,则m
值比较不重要,不用像除法所需要的要求.
令键值为x,A是一个小数常数,0<A<1,则乘法杂
凑函数为:
–h(x)=m * (A*x的小数点) 的整数
–因为(k*A的小数点)是介於0~1之间的值,乘以m则其范围
为0~m-1,刚好可需作为桶址.
13-2 杂凑函数-乘法范例
13-2 杂凑函数-基数法
基数法是利用数字系统的基数取代来运算位址,方
法如下:
–如果键值x的数字系统基数是p(例如p=10,代表10进
位),则找一个比p大且与p互质(没有1以外的公因数)的
数值q当作键值x的新基数,即原来(x)p变成(x)q.
–将(x)q换算为p基数的数字,即(x)q变成(y)p.
–从y中取出一部份y1(例如后面几位)当作h(x)的值.
–将y1 与m作余数运算作为桶址,即y1 % m为桶址.
13-2 杂凑函数-基数法范例
13-2 杂凑函数-数位分析法
数位分析法是以统计学的分布曲度(skewness)原理
为基础,统计出所有键值资料的各个数字出现的情
况,找出其中某几个位置的数字分布最平均,抽取
这几个位置的数字当作桶址.
因为是用统计学的方法找出现有资料键值的最佳杂
凑函数,所以特别适用於如程式语言系统的保留
字,字典,索引关键字等的杂凑法应用.
13-2 杂凑函数-数位分析法范例
13-2 杂凑函数-数位分析法范例13-3 溢位处理
当我们用杂凑函数来转换桶址时,只保证相同的资料经相
同的杂凑函数可找到相同的桶址,所以适合应用於搜寻问
题.但使用杂凑函数的缺点是不同的资料,经相同的杂凑
函数转换后,可能得到相同的桶址,此时即发生碰撞,此
时可将资料放在下一个槽,如果槽满了,则会发生溢位,
溢位处理的方法有下列几项:
–线性探测法(linear probing)
–平方探测法(quadratic probing)
–再杂凑法(rehasing)
–键结串列法(linked list)
13-3 溢位处理-线性探测法
当杂凑法发生溢位时,第一个直觉的处理方法是往
下找看看是否有空的桶可存放资料,若有则将资料
存放於此,下次找资料时,除了用杂凑函数转换的
桶址要检查是否为查询值之外,还要往下找寻是否
因溢位处理而放於别的位置.
所以线性控测法是将桶址看成一个环状位址,如果
键值x,经杂凑函数转换为y,如果桶址y已有资
料,假设桶址空间为m,则设计一个回圈(注标变数
i),以(y+i) % m往下找寻新的位置(不会发生溢位
的位置).
13-3 溢位处理-线性探测法范例
13-3 溢位处理-平方探测法
因为线性探测法是往下找可以取资料的桶址,如果经常处
理溢位时,则杂凑表中的相类似资料会聚集在一起,很容
易造成其它资料原先要存取的桶址被占用,这是线性探测
的缺点.
而平方探测法是同样是采用向下探测的方法,但不是每次
递增1的线性方法,而是每次加上一个常数的平方的跳跃式
探测,其溢位处理的桶址找寻公式如下:
–(h(x)+i2) % m或(h(x)-i2) % m,i表示第i次碰撞
–其中1≤i ≤(m-1)/2,m是4h+3型的质数,如7,127…
13-3 溢位处理-平方探测法范例
13-3 溢位处理-再杂凑法
再杂凑法是利用多个杂凑函数rh1(x),
rh2(x),rh3(x)…,当发生溢位处理时,可
使用rh1函数再进行杂凑,如果还是发生溢位
处理时,再使用下一个rh2函数,以此类推,
一直到找到适合存取的桶址为止.
13-3 溢位处理-再杂凑法范例
13-3 溢位处理-键结串列法
上述线性探测法,平方探测法和再杂凑有一项缺点
是会占用别的桶址位置,因此很容易造成后面进来
的资料发生溢位处理情况,要避免溢位处理的发
生,最根本的方法是用键结串列法.
键结串列法是在桶址后建立键结串列,当发生碰撞
时即在此桶址往后再加上新的节点,且建立好键
结.当要找寻资料时,只要经由杂凑函数转换出桶
址后,即由键结串列的键结往下找寻资料.
13-3 溢位处理-键结串列法范例
13-4 杂凑搜寻法
杂凑搜寻法是对已经利用杂凑法和溢位处理法所建
立的杂凑表进行搜寻,如果没有任何溢位处理时,
则要搜寻的资料经同样的杂凑函数转换后的桶址,
即是搜寻比对的资料,如果此桶址无资料,代表搜
寻失败,如果有资料即搜寻成功.
如果有作过溢位处理时,则要搜寻的资料除了要比
对经同样的杂凑函数转换的桶址之外,还要跟著溢
位处理方法再搜寻其它桶址,才能决定搜寻成功或
失败.
13-4 杂凑搜寻法-演算法步骤
1.键值x,用杂凑函数转换为桶址y.
2.如果桶址y的资料等於x,输出搜寻成功,结束.
3.如果桶址y的资料为空资料,输出搜寻失败,结束.
4.如果桶址y的资料有资料且不等於x,再依溢位处理程序找
寻下一个桶址y1,且以此累堆,检查:
a)如果桶址y1的资料等於x,输出搜寻成功,结束.
b)如果桶址y1的资料空资料,输出搜寻失败,结束.
c)如果桶址y1的资料有资料且不等於x,再回到步骤4.
5.如果溢位处理程序处理完毕,或造成溢位处理进入回圈,
即回到桶址y,则输出搜寻失败,结束.
13-4 杂凑搜寻法-演算法
01
02
03
04
05
06
07
08
09
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/* =============== Program Description ================= */
/* 演算法名称:杂凑搜寻法*/
/* 输入:一个整数键值*/
/* 输出:从杂凑表中搜寻这个键值是否存在*/
/* ===================================================== */
int HashSearch(int key)
{
int address,count=0;
address = HashFun(key);
count++;
if(HashValue(address) = key)
return 1;
else if(HashValue(address) = NULL)
else
{
while (count<HashSize)
{/*溢位处理回圈,如果看过元素个数等於HashSize就离开*/
address = OverHandle(address); /*溢位处理*/
if(HashValue (address) = key)
return 1;
count++;
}
}
return 0;
}
int OverHandle(int address)
{/*以除法为例,把目前的address+1再对HashSize取余数得到下一个位置*/
return (address+1)%HashSize;
}