計算機軟件基礎：15第四章數(shù)據(jù)結構圖

《計算機軟件基礎》多媒體教程

第十五講

第四章數(shù)據(jù)結構

4.8最優(yōu)二叉樹(哈夫曼樹)

※編碼問題

一段報文為“GOOD_GOOD_GOODGODGO"，字符集合是{O,G,D},將字符用“0”

和T編碼，可獲得報文同編碼。

例如，將字符按等長編碼：

0:00G:10_:01D:11

可得到報文的編碼：

10000011011000001101100000111000111000

GOOD_GOOD_GOODGODGO

由于各個字符出現(xiàn)的蕨度(次數(shù))是{0:8,G:5,_:2,D:4},

因此編碼總長度為(8+5+2+4)x2=38

編碼問題：如何使編碼總長度最短？

※最優(yōu)二叉樹

假設二叉樹的n個葉結點給定一個帶權值Wk,那么從根結點到各個葉結點的路徑長度

Lk與結點的權值Wk乘積之和叫做二叉樹的帶權路徑長度(WPL,權路徑長度)。

WPL=^WkxLk

k=1

給定一組帶權值的葉結點，可以構成不同形式的二叉樹。在這些所有的二叉樹中，權路

徑長度WPL最小的二叉樹稱為最優(yōu)二叉樹(哈夫曼樹，HuffmanTree)。

例如，葉結點：{7,5,3,1},WPL(A)>WPL(B)。__________________________________

二叉樹AC

XV-二叉樹BQ

c(@*-3=2C(@L5=2

@L7=3\5)L5=30LI=3(3)L2=3

WPL(A)=7x3+5x3+3x2+1x1=43WPL(B)=7x1+5x2+3x3+1x3=29

※哈夫曼樹構造算法

1.根據(jù)給定的n個權值(wi,W2,wn),構成n棵二叉樹的集合F={TI,T2,…,Tn},其中

每個丁中只有一個權值為Wi的根結點。

2.在F中選取兩棵根結點權值最小的樹作為左右子樹構造一棵新的二叉樹，且置其根結

點的權值為其左右子樹權值之和。

3.在F中刪除這兩棵樹，同時將新得到的二叉樹加入F中。

4.重復2,3,直到F中只含一棵二叉樹為止，即為哈夫曼樹。

初始：F={{7},{5},{3},。}}Step1：合并{3}{1},得F={{7},{5},{4}}

⑦⑤③①

⑦⑤@

Step2：合并{5}{4},得尸={{9},{7}}Step3：合并{9}{7},得F={16},構造結束

⑦氏

※哈夫曼樹生成示例

根據(jù)報文“GOOD_GOOD_GOODGODGO”生成哈夫曼樹。

字符集合為{0:8,&5,_:2,D:4}。

初始：F={{8},{5},{4},{2}}Step1：合并{2}{4}，F(xiàn)={{8},{6},{5}}

⑧。⑤G②一④D

⑧。⑤

Step2：合并{6}{5},F={{11},{8}}Step3：合并{11}{8},F={19},構造結束

o@刑

G?J?

?-@D(gA?

D

※哈夫曼樹編碼算法

令哈夫曼樹的左子路徑編碼'0'，右子路徑編碼T,從根到葉結點的路徑編碼的合成稱為

葉結點的哈夫曼編碼(Huffman碼)，這是一種不等長的前綴編碼，其特征是沒有一個編碼是

另一個編碼的前綴，使得解碼時不會混淆。

例如，報文為："GOOD_GOOD_GOODGODGO”，

字符集合為：{O:8,G:5,_:2,D:1}

葉結點的哈夫曼編碼為：0:0G:10_:110D:111

報文的哈夫曼編碼為：

1000111110100011111010001111001111000

GOOD_G00DGOODGODGOO

貝ij總編碼長度(權路徑長度)為：WPL=8X1+5X2+4X3+2X3=36

而采用等長編碼的總長度=38。

4.9圖

4.9.1圖的定義

※圖

設B=(K,R)是數(shù)據(jù)結構,K={ki,k2，…，％},R只有一個關系R={r},r={(ks,kt),|ks,kyK},

則稱B為圖。

※頂點

在圖的術語中，把結點node稱為頂點vertex.

因此，在圖中結點集合記為V={V1,V2，…,Vn}o

※邊

對于r中的(ks,kt),ks>kteK,記為(vs,vt),vs,vtev?稱為從Vs,到vt存在一條邊，記

為ei=(vs,vt)。

所有的邊組成邊的集合(邊集)E,即

E={ei,em,|?=(vs,vt),vs,vteV},

因而可將圖記為G=(V,E)o

※有向邊

在圖G=(V,E)中，若u,veV,(u,v)eE,且(u,v)W(v,u),則稱(u,v)為有向邊，記為e=<u,

v>,并稱u由起點，v為終點。

※無向邊

若u,vcV,(u,v)和(v,u)eE,且(u,v)=(v,u),則稱e=(u,v)為無向邊。

同時在圖形表示時，用雙向箭頭或者用無箭頭線表示e=(u,v)。

<u,v>

(u,V)

在圖中，若VGV,(v,v)GE,則稱(v,v)為自向邊。(在本課程中，不考慮自向邊。)

※無向圖

在G=(V,E)圖中，若對所有的u,vwv,e=(u,v)￡E,同時存在e'=(v,u)WE,且6=6’,

則稱G為無向圖。

有向圖

若有任一邊e=(u,v)GE,而(V,U)E,或者存在e=(v,u)eE,e'=(u,v)6E,但eHe',

則稱G為有向圖。

※子圖

設G'=(V',E'),G=(V,E),若成立V'V,E'E(稱V'包含于V,E'包含于E),即對所

有的u,v￡V.都存在u,vGV,同時對所有的e=(u,v)GE')都存在e=(u,v)WE,則稱G'

為G的子圖。

※完全圖

在無向圖G中,若對任何兩個頂點u和v,都存在無向邊，稱G為無向完全圖。

在有向圖G中,若對任何兩頂點u和v,都存在邊e=<u,v>和e'=<v,u>,稱G為有向

完全圖。

無向完全圖無向完全圖有向完全圖有向完全圖

※通路

在圖G=(V,E)中，如果存在一個頂點序列(vo,vi,v2，…,Vk),所有的(％,vi+1)eE|i=0,

k-1,而且vo=u,Vk=v,則稱在u和v之間存在通路。

※回路

則這個頂點序列稱為回路。

※連通圖

在無向圖G=(V,E)中，如果任何兩個頂點之間都存在通路，則稱G為連通圖。

非連通圖

4.9.2圖的基本操作和應用舉例

※圖的基本操作

0查找頂點或查找子圖。刪除頂點或子圖

。尋找通路或回路。遍歷全部頂點

0添加頂點或合并兩個圖本課程我們將只介紹幾種圖的遍歷方法。

※圖的應用舉例

(-)最短路徑問題

E.W.Dijkstra于1959年提出，又稱為

Dijkstra算法。定義一個帶權圖G=(V,E,

w),對所有的邊e=(u,v)eE|ueV,veV,

w(u,v)是邊e的權(w可以是邊e的路程，

費用等)。給定一個起點u和一個終點V,

求從u出發(fā)到v的一條最短路徑。例如從a

出發(fā)，尋找到達z的最短路徑,如右圖所示。

(-)歐拉回路問題

1736年，歐拉寫出了第一篇圖論的論文，回答了朋友提出的一個問題：在哥尼斯堡的

匹格河上有七座橋，能否從任何一個地方出發(fā)通過每座橋一次且僅一次后回到原地?該問題

稱為著名的哥尼斯堡七橋問題。

哥尼斯堡七橋問題等價于在圖中尋找一條回路，使得它的每一條邊出現(xiàn)一次且僅一次,

也就是如何一筆畫的問題，如下圖所示。

(三)哈密頓回路

哈密頓②爵士在1859年發(fā)明了一種“環(huán)球世界”的游戲。要求游戲者沿著頂點在標有

城市名稱的正十二面體的棱線行走，尋找一條通過每個城市恰好一次的回路。

哈密頓回路問題等價于在圖中尋找一條回路，使得它的每一個頂點出現(xiàn)一次且僅一次，

也是如何一筆畫的問題，如下圖所示。

(四)巡回售貨員問題

巡回售貨員問題(TSP,TravellingSalesmanProblem)又稱為貨郎擔問題。設有n個城

市，已知每兩個城市間的距離。一個貨郎自某個城市出發(fā)巡回售貨。問這個貨郎應該如何選

擇路線，使得每個城市經(jīng)過一次且僅一次，并且總的行程最短。

貨郎擔問題實際上是在一個帶權完全圖中尋找一條總的權最小的哈密頓回路。

(五)地圖的四色問題

1852年英國青年弗蘭西斯?格思里(FrancisGuthrie)在畫地圖時發(fā)現(xiàn)：如果相鄰的兩國

著上不同的顏色，那么畫任何一張地圖只要四種顏

色就夠To這就是地圖的四色(MapColorring)]nj題。

100多年來，許多科學家的證明都失敗了。直

到1976年美國伊利諾大學的阿佩爾(K.Appel)和

哈根(W.Haken)兩位教授用計算機化了1200多個

小時才得以證明。但是至今仍沒有能夠用通常的證

明方法來論證四色問題。

印刷電路板的分層問題是地圖四色問題的應用。將圖中的邊對應于導線，頂點對應于接

點，沒有導線連接的兩個接點間可能要裝配元件。由于同一層上導線不允許交叉，問如何設

計具有最少層數(shù)的印刷電路板？

(六)迷宮問題

迷宮(Maze)問題可描述為：從A到B間存在障礙，如何找到最佳的路徑？

B0

0

0

0

00000

0

0

0

0

AO00

00

00

0000

在集成電路和印刷電路板的布線時，用Lee氏算法求解迷宮問題是一個最基本也是最

有效的算法。

(七)皇后問題

皇后問題是一個古老而著名的問題,

是回溯算法的典型例題。該問題是十九世紀著名的數(shù)學家高斯①1850年提出：在8X8格的

國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列

或同一斜線上，問有多少種擺法。

高斯認為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解,

后來有人用圖論的方法解出92種結果。

4.9.3圖的存儲

圖的存儲有多種形式，這里只討論兩種常用的形式，即鄰接矩陣和鄰接表。

※鄰接矩陣

設G=(V,E)是圖，V={vi,V2，…，vn},則可定義一個nxn的鄰接矩陣A。

矩陣元素A[i,j](i,j=1，…,n)被定義為

若(4v,GE

若(M，Vj)gE

01100、0000

1011000110

1101111001

0110001100

lo010ojlo010oj

鄰接矩陣

A1鄰接矩陣A2

例如，無向圖Gi和有向圖G2可以分別用鄰接矩陣Al和鄰接矩陣A2表示，A2中的粗

體數(shù)字表示非對稱的有向邊，稱為非對稱元素。

※鄰接表

在圖G=(V,E)中，若(s,Vj)￡E,Vi,Vj￡V,則稱甘是s的鄰接頂點。鄰接表是指僅僅存

儲各頂點的鄰接頂點的信息。

鄰接表由表頭和表鏈組成，表頭用于存放所有頂點的數(shù)據(jù)場，表鏈用于存放每個Vi的鄰

接頂點的地址。表頭單元含有兩個指針場piv和P2V,通常用pw指向表頭的下一頂點，用

p2V指向各個表鏈。表鏈單元也含有兩個指針場P1V和P2V,通常用PW存放頂點的表頭地

址，用P2V指向表鏈的下一結點。___________

表頭av5vPlVP2V表鏈avPRp2V

>av>av

av1V1av2-i2r-~l3

Iavv2av

23*|ayjJ-qaVgj_*|ay4

v

Lav33av4

,*jaViaV2r_>]aV4aV5

-',1

LavV4av

45,*jav

2av3

L0CV5V5

(PAIM

※鄰接表存儲單元示例

表頭的存儲單元：用next存放表頭中下一單元的地址，用link存放表鏈的首地址。

表鏈的存儲單元：用vertex存放頂點在表頭中的地址，用next存放表鏈中下一單元的

地址。圖G的鄰接表及存儲單元如下圖所示。

※用數(shù)組存儲的鄰接表

表鏈

存儲鄰接表的數(shù)據(jù)定義表頭

#defineM1000avkeylinklink[0]link[1]link[2]link[3]

#defineVERTEXstructvertex

0%F16012

v匚ri匚八/儀六外憎/

1F240___023

(v2

----------A

longkey;2v3F3100134

short*link;/*表鏈首地址7

3v4F430-1-?12

)；4vF560

VERTEXVertex[M];53

其中，表頭用結構數(shù)組Vertex實現(xiàn)存儲，表鏈用動態(tài)數(shù)組Vertex[i]」ink實現(xiàn)存儲。

※用鏈表存儲的鄰接表

存儲鄰接表的數(shù)據(jù)定義

#defineVERTEXstructvertex

#defineLINKstructlink

VERTEX/*表頭結構*/

(

longkey;/*數(shù)據(jù)場*/

VERTEX*next;I*表頭中下一頂點指針*/

LINK*link;I*頂點的表鏈指針*/

};

LINK/*表鏈結構*/

(

VERTEX*vertex;/*表頭中的頂點指針*/

LINK*next;/*表鏈中下一結點指針*/

}；

VERTEXWertex;

VERTEX

key

next—?

link-?

表頭和表鏈分別是VERTEX和LINK類型的鏈表，因而稱為用鏈表存儲的鄰接表。Vertex

指向表頭，表頭的成員指針link指向各個表鏈。

※用鏈表存儲鄰接表的圖形表示

11101120

VertexF110廣F210TF310

F110T?ViF21011101120NULL

121012201230

F210F110F310F410

1220T1230,rNULL

T?V2F3101210J

1310132013301340

F31C)F110F210F410TF510

T>V3F41013101320T1330j1340NULL

14101420

F410F210F310

HV4F51014101420TNULL

1510

F510r*F310

?v|NULL

51510NULL

4.9.4圖的遍歷

※遍歷的定義

從某一頂點出發(fā)開始訪問，沿著邊逐個訪問頂點，直至遍及全圖。

當圖為連通時，遍歷是可能的。

※常用的遍歷方法

DFS：深度優(yōu)先搜索法(DepthFirstSearch)

BFS：廣度優(yōu)先搜索法(BreadthFirstSearch)

對樹來說，樹的DFS就是樹的前序遍歷，樹的BFS就是樹的層次遍歷

XDFS(深度優(yōu)先搜索法)

。算法描述

0)初始化：所有頂點標記為未訪問。

1)指定一個頂點V,開始DFS。

2)對給定的一個頂點V：

如果該點已訪問過，則跳過。

如果該點未訪問過，則訪問之，并加注己訪問的標記;

然后對于V的所有鄰接頂點逐個執(zhí)行DFS。

※用數(shù)組存儲的鄰接表實現(xiàn)DFS算法

。數(shù)據(jù)定義表頭表鏈

#defineM1000av|key|flagnlinklink[0]..

#defineUNVISITEDV

#defineVISITED'U)

#defineVERTEXstructvertex

VERTEX

(

longkey;

charflag;/*訪問標記7表頭表鏈

shortn;/*表鏈數(shù)組長度*/0Viflag3link125

short*link;/*表鏈動態(tài)數(shù)組*/

1v2flag2link04

｝；2V3flag2link03

VERTEXVertex[M];

3V4flag3link245

假定圖G已經(jīng)存儲，即用數(shù)組存儲的鄰接表如圖所示。

4V5flag3link

ODFS程序135

voiddfs(shortv)5V6flag3link034

short*link,i;

HM

printf(vertex=%ld\nJVertex[v].key);

Vertex[v].flag=VISITED;

for(i=0,link=Vertex[v].link;i<Vertex[v].n;i++)

if(Vertex[link[i]].flag==UNVISITED)

dfs(link[i]);

)

如果選Vertex⑼為首個遍歷的頂點，則dfs函數(shù)的調(diào)用形式為:

dfs（O）;

。DFS算法演示

為簡化起見，演示中以V[v]

替代Vertex[v],用link[k]表示

Vertex[k].link.用實線表示函數(shù)

調(diào)用，用虛線表示函數(shù)返回。

遍歷的結果：

125436

0Vl125

1v204

2v303

3v4245

4v5135

5v6034

XBFS（廣度優(yōu)先搜索法）

。算法描述

0）初始化：所有頂點標記為未訪問。

1）指定一個頂點，送入隊列。

2）只要隊列非空，從隊列中取出一個頂點V,

重復執(zhí)行：

如果V已訪問，跳過；

如果V未訪問，加訪問標記，打??；

將V的所有未訪問過的鄰接頂點送入隊列。

當隊列空時結束遍歷。

（DBFS算法演示

※用鏈表存儲的鄰接表實現(xiàn)BFS算法

0數(shù)據(jù)定義

#defineUNVISITED0/*未訪問*/

#defineVISITED1/*已訪問7

#defineVERTEXstructvertex

#defineLINKstructlink

VERTEX1*表頭結構*/

(

longkey；/*頂點數(shù)據(jù)值7

shortflag；/*訪問標記，初始為未