數(shù)據(jù)結(jié)構(gòu)課件

數(shù)據(jù)結(jié)構(gòu)1/2571.2數(shù)據(jù)構(gòu)造有關(guān)概念

數(shù)據(jù)：

客觀對象符號表達。例如：學(xué)號，姓名，班名都是數(shù)據(jù)。

數(shù)據(jù)元素：數(shù)據(jù)基本單位。相稱于“統(tǒng)計”,在計算機程序中一般作為一種整體考慮和處理。又稱結(jié)點、表目等等數(shù)據(jù)項:

相稱于統(tǒng)計中“域”,是數(shù)據(jù)不可分割最小單位,如學(xué)號數(shù)據(jù)對象：性質(zhì)相同數(shù)據(jù)元素集合.

例如:所有班名相同統(tǒng)計集合數(shù)據(jù)構(gòu)造有關(guān)概念2/257數(shù)據(jù)邏輯構(gòu)造：

數(shù)據(jù)之間構(gòu)造關(guān)系，是現(xiàn)實中詳細關(guān)系抽象。

數(shù)據(jù)構(gòu)造:數(shù)據(jù)構(gòu)造基本操作：指對數(shù)據(jù)構(gòu)造加工處理數(shù)據(jù)存放構(gòu)造(物理構(gòu)造)：

數(shù)據(jù)構(gòu)造在計算機內(nèi)存中表達數(shù)據(jù)構(gòu)造基本操作實現(xiàn)：基本操作在計算機上實現(xiàn)（辦法)數(shù)據(jù)構(gòu)造概念主要包括下列基本概念：3/257數(shù)據(jù)邏輯構(gòu)造關(guān)系：非空集合X上一種關(guān)系r是指X笛卡爾乘積上一種子集合。即例如：X是我們?nèi)嗤凹?。X上同鄉(xiāng)關(guān)系X是數(shù)學(xué)系全體老師和同窗組成集合。X上師生關(guān)系實數(shù)集合上不大于“<”關(guān)系。4/257數(shù)據(jù)存放構(gòu)造

數(shù)據(jù)在計算機中表達稱為數(shù)據(jù)物理構(gòu)造，又稱為數(shù)據(jù)存放構(gòu)造。

存放構(gòu)造分為次序存放構(gòu)造和鏈?zhǔn)酱娣艠?gòu)造。

在高級語言中，經(jīng)常使用數(shù)據(jù)類型這個概念來作為高級語言中描述存放構(gòu)造工具。5/257線性表定義：n個數(shù)據(jù)元素有限序列基本操作：隨機訪問、插入、刪除、前驅(qū)、后繼、倒序等實現(xiàn)方式：次序存放：數(shù)組線性表、堆棧、隊列、數(shù)組6aiai+1…………Loc(ai)Loc(ai+1)=Loc(ai)+llLoc(ai)=Loc(a1)+?(i-1)*l6/257

線性表是最簡單常用數(shù)據(jù)構(gòu)造，次序存放構(gòu)造鏈?zhǔn)酱娣艠?gòu)造也是應(yīng)用中最常用存放辦法，棧隊列串是特殊線性表，數(shù)組和廣義表是線性表擴展；有助于理解和掌握樹和圖等復(fù)雜數(shù)據(jù)構(gòu)造存放構(gòu)造和圖等復(fù)雜構(gòu)造操作算法，由于樹和圖存放構(gòu)造大多或是這兩種存放構(gòu)造擴充，或是它們組合。7/257線性表概念說明：設(shè)A=（a1,a2,...,an

）是一線性表1）線性表數(shù)據(jù)元素能夠是多種各樣，但同一線性表中元素必須是同一類型；2）在表中ai-1

領(lǐng)先于ai，ai

領(lǐng)先于ai+1

，稱ai-1

是ai

直接前驅(qū)，ai+1

是ai

直接后繼；3）線性表中元素個數(shù)n稱為線性表長度，n=0時稱為空表；8/257線性表概念4）在線性表中，除第一種元素和最后一種元素之外，其他元素都有且僅有一種直接前驅(qū)，有且僅有一種直接后繼，具有這種構(gòu)造特性數(shù)據(jù)構(gòu)造稱為線性構(gòu)造。線性表是一種線性數(shù)據(jù)構(gòu)造；5）ai是線性表第i個元素，稱i為數(shù)據(jù)元素ai

序號，每一種元素在線性表中位置，僅取決于它序號；9/257線性表實現(xiàn)方式：次序存放：數(shù)組線性表、堆棧、隊列、數(shù)組10

是一種隨機存取存放構(gòu)造，方便隨機存取第i個數(shù)據(jù)元素

插入、刪除復(fù)雜度為O(n)，需要移動大量元素10/25711線性表、堆棧、隊列、數(shù)組線性表實現(xiàn)方式：鏈?zhǔn)酱娣牛烘湵砭€性鏈表

插入、刪除復(fù)雜度為O(1)，僅需修改指針而不需要移動元素

是一種非隨機存取存放構(gòu)造，不方便隨機存取第i個數(shù)據(jù)元素11/257自測題在n個結(jié)點次序表中，算法時間復(fù)雜度是O(1)操作是：訪問第i個結(jié)點(1≤i≤n)和求第i個結(jié)點直接前驅(qū)(2≤i≤n)在第i個結(jié)點后插入一種新結(jié)點（1≤i≤n）刪除第i個結(jié)點（1≤i≤n）將n個結(jié)點從小到大排序線性表、堆棧、隊列、數(shù)組1212/25713線性表、堆棧、隊列、數(shù)組線性表實現(xiàn)方式：鏈?zhǔn)酱娣牛烘湵砭€性鏈表存放地址數(shù)據(jù)域指針域1LiNULL7Qian1313Sun119Zhao7頭指針H=19HZhaoQianSunLi

若p->data=ai則p->next->data=ai+1typedefstruct

LNode{ElemType data;

struct

LNode*next;}LNode,*LinkList;有時附加頭結(jié)點13/257自測題線性表若采取鏈?zhǔn)酱娣艠?gòu)造時，要求內(nèi)存中可用存放單元地址:必須是連續(xù)部分地址必須是連續(xù)一定是不連續(xù)連續(xù)或不連續(xù)都能夠線性表、堆棧、隊列、數(shù)組1414/257自測題下面論述不正確是（）線性表在鏈?zhǔn)酱娣艜r，查找第i個元素時間同i值成正比線性表在鏈?zhǔn)酱娣艜r，查找第i個元素時間同i值無關(guān)線性表在次序存放時，查找第i個元素時間同i值成正比線性表在次序存放時，查找第i個元素時間同i值無關(guān)線性表、堆棧、隊列、數(shù)組1515/257自測題在一種單鏈表中，若p所指結(jié)點不是最后結(jié)點，在p之后插入s所指結(jié)點，則執(zhí)行：s->next=p;p->next=s;s->next=p->next;p->next=s;s->next=p->next;p=s;p->next=s;s->next=p;線性表、堆棧、隊列、數(shù)組16ps16/257自測題在單鏈表中，指針p指向元素為x結(jié)點，實現(xiàn)“刪除x后繼”語句是：p=p->next;p->next=p->next->next;p->next=p;p=p->next->next;線性表、堆棧、隊列、數(shù)組17xp17/25718線性表、堆棧、隊列、數(shù)組線性表實現(xiàn)方式：鏈?zhǔn)酱娣牛烘湵硌h(huán)鏈表雙向鏈表HHHH有時設(shè)尾指針可簡化某些操作，如兩表合并。18/257自測題設(shè)一種鏈表最常用操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用()最節(jié)省時間。單鏈表單循環(huán)鏈表帶尾指針單循環(huán)鏈表帶頭結(jié)點雙循環(huán)鏈表線性表、堆棧、隊列、數(shù)組1919/257自測題將線性表La和Lb頭尾連接，要求時間復(fù)雜度為O(1)，且占用輔助空間盡可能小。應(yīng)當(dāng)使用哪種構(gòu)造？單鏈表單循環(huán)鏈表帶尾指針單循環(huán)鏈表帶頭結(jié)點雙循環(huán)鏈表線性表、堆棧、隊列、數(shù)組20tmp=La->next;La->next=Lb->next;Lb->next=tmp;LaLb20/257堆棧概念：后進先出，限定僅在表尾進行插入刪除線性表。表達與實現(xiàn)：次序棧：數(shù)組，top++，top--鏈棧：鏈表，top即為頭指針應(yīng)用：括號匹配檢查、體現(xiàn)式求值、n階Hanoi塔問題（典型遞歸）、迷宮問題21線性表、堆棧、隊列、數(shù)組21/257自測題判定一種棧ST(最多元素為m0)為空條件是：ST->top!=0ST->top

==0ST->top!=m0ST->top

==m0線性表、堆棧、隊列、數(shù)組2222/257自測題有六個元素以6，5，4，3，2，1次序進棧，問下列哪一種不是合法出棧序列？543612453126346521234156線性表、堆棧、隊列、數(shù)組2323/257自測題若一種棧輸入序列為1，2，3，…，n，輸出序列第一種元素是i，則第j個輸出元素是：i–j–1i–jj–i–1不確定線性表、堆棧、隊列、數(shù)組2424/257隊列概念：先進先出，限定僅在隊尾進行插入、僅在隊頭進行刪除線性表。表達與實現(xiàn)：次序隊列：循環(huán)數(shù)組，(rear+1)%N,(front+1)%N鏈棧：鏈表，front為頭指針，rear為尾指針應(yīng)用：離散事件模擬25線性表、堆棧、隊列、數(shù)組25/257自測題循環(huán)隊列用數(shù)組A[0,N-1]寄存其元素值，已知其頭尾指針分別是front和rear，則目前隊列中元素個數(shù)是：(rear-front+N)%Nrear-front+1rear-front-1rear-front線性表、堆棧、隊列、數(shù)組26[0][1][...][N-1]frontrear26/257自測題棧和隊列共同特點是：都是先進后出

都是先進先出

只允許在同一端點處插入和刪除

沒有共同點

線性表、堆棧、隊列、數(shù)組2727/257一、存放空間分派方面：次序存放開辟連續(xù)，固定長度存放空間。出現(xiàn)溢出情況時，不能動態(tài)擴充。鏈?zhǔn)酱娣胖?，結(jié)點存放空間是通過malloc函數(shù)來動態(tài)分派，能夠不連續(xù)，不存在溢出情況。

結(jié)論：事先能確定線性表大體長度，應(yīng)選擇次序存放方式，不然為了避免造成份配空間過大或過小，宜采取鏈?zhǔn)酱娣欧绞健６?、操作方面：次序存放，能夠隨機訪問，經(jīng)常訪問線性表中元素操作非常方便。但要進行插入和刪除操作每次都會出現(xiàn)元素大量移動。鏈?zhǔn)酱娣?，只能次序訪問，訪問鏈表中任意元素時，必須都從第一種結(jié)點開始次序查找。要進行插入和刪除操作時，只需修改結(jié)點指針域。

結(jié)論：假如線性表頻繁地進行插入和刪除操作，宜采取鏈?zhǔn)酱娣?；若頻繁訪問線性表中元素，宜采取次序存放。線性表實現(xiàn)辦法比較(補充)

28/257自測題在具有n個結(jié)點單鏈表中，實現(xiàn)下列哪個操作，其算法時間復(fù)雜度是O(n)

A．遍歷鏈表和求鏈表第i個結(jié)點B．在地址為p結(jié)點之后插入一種結(jié)點C．刪除開始結(jié)點D．刪除地址為p結(jié)點后繼結(jié)點

29/257自測題鏈表不具有特點是：插入、刪除不需要移動元素可隨機訪問任一元素?zé)o須事先估計存放空間所需空間與線性長度成正比

30/257自測題若某表最常用操作是在最后一種結(jié)點之后插入一種結(jié)點或刪除最后一種結(jié)點。則采取哪種存放方式最節(jié)省運算時間？單鏈表雙鏈表單循環(huán)鏈表帶頭結(jié)點雙循環(huán)鏈表

31/257自測題若某線性表最常用操作是存取任一指定序號元素和在最后進行插入和刪除運算，則利用哪種存放方式最節(jié)省時間？次序表

雙鏈表單循環(huán)鏈表帶頭結(jié)點雙循環(huán)鏈表

32/257自測題令P代表入棧，O代表出棧。則將一種字符串3*a+b/c變?yōu)?a*bc/+堆棧操作序列是哪個？（例如將ABC變成BCA操作序列是PPOPOO。）PPPOOOPPOPPOOO

POPOPOPPOPPOOO

POPPOOPPOPPOOO

POPPOOPPOPOOPO

33/257自測題某線性表中最常用操作是在最后一種元素之后插入一種元素和刪除第一種元素，則采取什么存放方式最節(jié)省運算時間？

單鏈表僅有頭指針單循環(huán)鏈表雙鏈表僅有尾指針單循環(huán)鏈表34/257自測題對于一種具有n個結(jié)點單鏈表，在給定值為x結(jié)點后插入一種新結(jié)點時間復(fù)雜度為O(n)O(1)O(n/2)O(n2)

35/257自測題設(shè)一種棧輸入序列是1，2，3，4，5,則下列序列中，是棧合法輸出序列是？

5123445132431253215436/257自測題若已知一種棧入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn。若p1=n，則pi為：in–in–i+1不確定

37/257自測題將5個字母‘ooops’按此次序入棧，則有多少種不一樣出棧次序能夠仍然得到‘ooops’？1356

38/257自測題循環(huán)隊列用數(shù)組A[0,N－1]寄存其元素值，已知其頭尾指針分別是front和rear，則目前隊列中元素個數(shù)是：(rear-front+N)%Nrear-front+1rear-front-1rear-front[0][1][...][N-1]frontrear39/257

設(shè)二維數(shù)組A[i][j](c1≤i≤d1,c2≤j≤d2)其中c1、c2和d1、d2分別為二維數(shù)組A下標(biāo)下界和上界，每個數(shù)組元素占L個存放單元，設(shè)第一種元素A[c1][c2]存放位置為LOC(c1,c2)，則該二維數(shù)組中任一元素A[i][j]存放位置可由下式確定：

LOC(i,j)=LOC(c1,c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L

在C語言中，下標(biāo)從零開始，則數(shù)組元素A[i][j]存放位置是:LOC(i,j)=LOC(0,0)+(i*(d2+1)+j)*L數(shù)組次序存放(以行為主序)

如何從下標(biāo)求得對應(yīng)數(shù)組元素存放位置？40/257

若6行5列數(shù)組以列序為主序次序存放，基地址為1000，每個元素占2個存放單元，則第3行第4列元素（假定無第0行第0列）地址是()。A.1040B.1042C.1026D.備選答案A，B，C都不對自測題41/257自測題數(shù)組A[1..5,1..6]每個元素占5個單元，將其按行優(yōu)先次序存放在起始地址為1000連續(xù)內(nèi)存單元中，則元素A[5,5]地址為1140114511201125

42/257樹和二叉樹43/2571.樹概念樹形構(gòu)造是一種主要非線性構(gòu)造，討論是層次和分支關(guān)系。樹是n個結(jié)點有限集合，在任一棵非空樹中：

（1）有且僅有一種稱為根結(jié)點。

（2）其他結(jié)點可分為個互不相交集合，并且這些集合中每一集合都本身又是一棵樹，稱為根子樹。JIACBDHGFEKLM樹是遞歸構(gòu)造，在樹定義中又用到了樹概念44/257樹圖示例：下面圖是一棵樹T={A,B,C,D,E,F,G,H,I,J，K，L，M}A是根，其他結(jié)點能夠劃分為3個互不相交集合：

T1={B,E,F，K，L}T2={C,G}T3={D,H,I,J，M}

這些集合中每一集合都本身又是一棵樹，它們是A子樹。

例如對于T1，B是根，其他結(jié)點被劃分為2個互不相交集合：

T11={E，K，L}，T12={F}，T11,T12

是B子樹。JIACBDHGFEKLM45/257從邏輯構(gòu)造看：

1）樹中只有根結(jié)點沒有前趨；

2）除根外，其他結(jié)點都有且僅一種前趨；3）樹結(jié)點，能夠有零個或多種后繼；

4）除根外其他結(jié)點，都存在唯一條從根到該結(jié)點途徑；5）樹是一種分枝構(gòu)造（除了一種稱為根結(jié)點外）每個元素都有且僅有一種直接前趨，有且僅有零個或多種直接后繼。JIACBDHGFEKLM46/2572.樹應(yīng)用(1)1）樹可表達具有分枝構(gòu)造關(guān)系對象例1．家族族譜設(shè)某家庭有13個組員A、B、C、D、E、F、G、H、I、J，K，L，M他們之間關(guān)系可下列圖所示樹表達：例2．單位行政機構(gòu)組織關(guān)系JIACBDHGFEKLM47/2574.樹基本術(shù)語(1)JIACBDHGFEKLM樹結(jié)點：包括一種數(shù)據(jù)元素及若干指 向子樹分支；孩子結(jié)點：結(jié)點子樹根稱為該結(jié)點孩子；雙親結(jié)點：B結(jié)點是A結(jié)點孩子，則A結(jié)點是B結(jié)點雙親；弟兄結(jié)點：同一雙親孩子結(jié)點；堂兄結(jié)點：同一層上結(jié)點；祖先結(jié)點:從根到該結(jié)點所經(jīng)分支上所有結(jié)點;子孫結(jié)點：以某結(jié)點為根子樹中任一結(jié)點都稱為該結(jié)點子孫48/257

JIACBDHGFEKLM樹基本術(shù)語結(jié)點層次：根結(jié)點層定義為1；根孩子為第二層結(jié)點，依此類推；樹深度：樹中結(jié)點最大層次結(jié)點度：結(jié)點擁有子樹個數(shù)樹度：樹中最大結(jié)點度。葉子結(jié)點：也叫終端結(jié)點，是度為0結(jié)點；分枝結(jié)點：度不為0結(jié)點；有序樹：子樹有序樹，如：家族樹；無序樹：不考慮子樹次序；森林；互不相交樹集合；森林和樹之間聯(lián)系是：一棵樹去掉根，其子樹組成一種森林；一種森林增加一種根結(jié)點成為樹。49/257二叉樹樹是一種分枝構(gòu)造對象，在樹概念中，對每一種結(jié)點孩子個數(shù)沒有限制，因此樹形態(tài)多種多樣，本章我們主要討論一種最簡單樹——二叉樹。50/257二叉樹概念(定義)1、二叉樹定義：二叉樹：或為空樹，或由根及兩顆不相交左子樹、右子樹組成，并且左、右子樹本身也是二叉樹。說明：

1）二叉樹中每個結(jié)點最多有兩顆子樹；二叉樹每個結(jié)點度不大于等于2;2）左、右子樹不能顛倒——有序樹;3）二叉樹是遞歸構(gòu)造，在二叉樹定義中又用到了二叉樹概念;

A

F

G

E

D

C

B51/257

A

F

G

E

D

C

B

(a)、(b)是不一樣二叉樹，(a)左子樹有四個結(jié)點，(b)左子樹有兩個結(jié)點，(a)

A

G

E

D

B

C

F(b)52/2572.二叉樹基本形態(tài)φ(a)空樹(b)僅有根(c)右子樹空(d)左子樹空(e)左、右子樹均在53/2573.應(yīng)用舉例:能夠用二叉樹表達體現(xiàn)式

a+b*(c-d)-e/f

e

d

c

b

f

a

+

*

/

-

-54/257二叉樹性質(zhì)性質(zhì)1在二叉樹第i層上最多有2i-1個結(jié)點性質(zhì)2深度為k二叉樹最多有2k-1個結(jié)點性質(zhì)3設(shè)二叉樹葉子結(jié)點數(shù)為n0，度為2結(jié)點n2，則n0=

n2+1

A

F

G

E

D

C

B55/257性質(zhì)3證明：

設(shè)n1為二叉樹T中度為1結(jié)點數(shù)。n為二叉樹總結(jié)點數(shù)。則有

n=n0+n1+n2(*)

設(shè)B為二叉樹總分支數(shù)。由于除了根結(jié)點外每個結(jié)點都有一種進入分支，因此

n=B+1

由于這些分支是由度為1或2結(jié)點發(fā)出，因此B=n1+2n2由此得n=n1+2n2+1(**)由(*)和(**)得結(jié)論：n0=n2+156/257滿二叉樹假如深度為k二叉樹，有2k-1個結(jié)點則稱為滿二叉樹；

A

B

C

E

D

F

G注：在有些書上，滿二叉樹定義成沒有度為1結(jié)點二叉樹此二叉樹深度為357/257完全二叉樹：假如一顆二叉樹只有最下一層結(jié)點數(shù)也許未達成最大，并且最下層結(jié)點都集中在該層最左端，則稱為完全二叉樹；

A

E

D

C

B

G

A

E

D

C

B(a)(c)(b)、(b)完全二叉樹(c)不是完全二叉樹

A

G

F

E

D

C

B58/257性質(zhì)5：在完全二叉樹中編號為i結(jié)點1）若有左孩子，則左孩編號為2i2）若有右孩子，則右孩子結(jié)點編號為2i+13）若有雙親，則雙親結(jié)點編號為trunc(i/2)完全二叉樹性質(zhì)下面是兩個有關(guān)完全二叉樹性質(zhì)性質(zhì)4

具有n個結(jié)點完全二叉樹深度為：trunc(log2n)+1.trunc(x) 為取整函數(shù)。對完全二叉樹結(jié)點編號：從上到下，每一層從左到右

A

F

E

D

C

B12345659/257三．二叉樹存貯構(gòu)造

1二叉樹次序構(gòu)造滿二叉樹或完全二叉樹次序構(gòu)造用一組連續(xù)內(nèi)存單元，按編號次序依次存放完全二叉樹元素.例如，用一維數(shù)組bt[]寄存一棵完全二叉樹，將標(biāo)號為i結(jié)點數(shù)據(jù)元素寄存在分量bt[i]中。存放位置隱含了樹中關(guān)系，樹中關(guān)系是通過完全二叉樹性質(zhì)實現(xiàn)。例如，bt[6]（i=6)雙親結(jié)點標(biāo)號是k=trunc(i/2)=3,雙親結(jié)點所對應(yīng)數(shù)組分量bt[k]=bt[3]次序構(gòu)造圖示

01234567m-1

ABCDEF

A

F

E

D

C

B12345660/257非完全二叉樹次序構(gòu)造按完全二叉樹形式補齊二叉樹所缺乏那些結(jié)點，對二叉樹結(jié)點編號,將二叉樹原有結(jié)點按編號存放到內(nèi)存單元“對應(yīng)”位置上。但這種方式對于畸形二叉樹，揮霍較大空間。

A

F

G

E

D

C

B1672453810

A

F

G

E

D

C

B9012345678910m-1ABCDE#F##G61/2572二叉鏈表二叉鏈表中每個結(jié)點包括三個域：數(shù)據(jù)域、左指針域、右指針域

A

F

E

D

C

BtypedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;}BiTNode,*BiTree;∧

D

A

B

∧C

∧∧

E

∧∧

F

∧二叉鏈表圖示62/257

A

F

E

D

C

B3三叉鏈表三叉鏈表中每個結(jié)點包括四個域：數(shù)據(jù)域、雙親指針域、左指針域、右指針域typedefstructBT3Node{TElemTypedata;structBT3Node*lchild,*rchild,*parent;}BT3Node,*B3Tree;ABDFEC63/257二叉樹遍歷遍歷：按某種搜索途徑訪問二叉樹每個結(jié)點，并且每個結(jié)點僅被訪問一次。訪問：含義很廣，能夠是對結(jié)點多種處理，如修改結(jié)點數(shù)據(jù)、輸出結(jié)點數(shù)據(jù)。遍歷是多種數(shù)據(jù)構(gòu)造最基本操作，許多其他操作能夠在遍歷基礎(chǔ)上實現(xiàn)。

如何訪問二叉樹每個結(jié)點，并且每個結(jié)點僅被訪問一次？？64/257二叉樹遍歷辦法二叉樹由根、左子樹、右子樹三部分組成二叉樹遍歷能夠分解為：訪問根，遍歷左子樹和遍歷右子樹令：L：遍歷左子樹

T：訪問根結(jié)點

R：遍歷右子樹

有六種遍歷辦法：

TLR，LTR，LRT，

TRL，RTL，RLT

商定先左后右,有三種遍歷辦法：TLR、LTR、LRT

，分別稱為先序遍歷、中序遍歷、后序遍歷

A

F

G

E

D

C

B65/257

先序遍歷（TLR）若二叉樹非空

（1）訪問根結(jié)點；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；

先序遍歷序列：A,B,D,E,G,C,F

A

F

G

E

D

C

B例：先序遍歷右圖所示二叉樹（1）訪問根結(jié)點A

（2）先序遍歷左子樹：即按TLR次序遍歷左子樹

（3）先序遍歷右子樹：即按TLR次序遍歷右子樹66/257中序遍歷（LTR）若二叉樹非空

（1）中序遍歷左子樹

（2）訪問根結(jié)點（3）中序遍歷右子樹中序遍歷序列：D,B,G,E,A,C,F

A

F

G

E

D

C

B例：中序遍歷右圖所示二叉樹（1）中序遍歷左子樹：即按LTR次序遍歷左子樹

（2）訪問根結(jié)點A

（3）中序遍歷右子樹：即按LTR次序遍歷右子樹67/257后序遍歷（LRT）若二叉樹非空

（1）后序遍歷左子樹

（2）后序遍歷右子樹（3）訪問根結(jié)點

后序遍歷序列：D,G,E,B,F,C,A例：后序遍歷右圖所示二叉樹（1）后序遍歷左子樹：即按LRT次序遍歷左子樹

（2）后序遍歷右子樹：即按LRT次序遍歷右子樹（3）訪問根結(jié)點A

A

F

G

E

D

C

B68/257

e

d

c

b

f

a

+

*

/

-

-

后序遍歷序列：a,b,c,d,-,*,+,e,f,/,-

中序遍歷序列：a,+,b,*,c,-,d,-,e,/,f

先序遍歷序列：-,+,a,*,b,-,c,d,/,e,f例：先序遍歷、中序遍歷、后序遍歷下列圖所示二叉樹波蘭體現(xiàn)式逆波蘭體現(xiàn)式69/257線索二叉樹

在二叉樹二叉鏈存放構(gòu)造中,n個結(jié)點二叉樹會有n+1個空指針，為了充足利用這n+1個空指針，引入線索二叉樹概念：在空指針處寄存指向該結(jié)點在某種序列(先序、中序、后序)中前驅(qū)(左兒女指針位置)或后繼結(jié)點指針(右兒女指針位置)---線索.

得到三種線索二叉樹:先序線索樹、中序線索樹、后序線索樹由于空指針位置被占用，需要標(biāo)識對應(yīng)指針是兒女指針還是線索指針。70/257二樹與二叉樹轉(zhuǎn)換

二叉樹與樹都可用二叉鏈表存貯，以二叉鏈表作中介，可導(dǎo)出樹與二叉樹之間轉(zhuǎn)換。樹與二叉樹轉(zhuǎn)換辦法樹根結(jié)點X第一種孩子結(jié)點X緊鄰右弟兄二叉樹根結(jié)點X左孩子結(jié)點X右孩子71/257IACBDHGFEFIABDHGCE樹根結(jié)點X第一種孩子結(jié)點X緊鄰右弟兄二叉樹根結(jié)點X左孩子結(jié)點X右孩子72/257森林森林是樹集合：

將森林中樹根當(dāng)作弟兄，可用樹孩子弟兄表達法存放森林轉(zhuǎn)換規(guī)則：若F={T1，T2，T3，…，Tn}是森林，則

B（F）={root,LB,RB}（1）若F為空，即n=0，則B(F)為空樹。（2）若F非空，則B（F）根是T1根，其左子樹為LB，是從T1根結(jié)點子樹森林F1={T11，T12，…，T1m}轉(zhuǎn)換而成二叉樹；其右子樹為RB，是從除T1外森林F’={T2，T3，…，Tn}轉(zhuǎn)換而成二叉樹；73/257

J

A

L

KIHGFEACBD包括3棵樹森林

B

C

D

E

F

G

H

I

J

K

L

F

D

C

A

B

E

G

H

I

J

K

L每棵樹對應(yīng)二叉樹森林對應(yīng)二叉樹74/257二叉樹還原為森林轉(zhuǎn)換規(guī)則：若B(F)={root,LB,RB}是一棵二叉樹，則轉(zhuǎn)換為森林F={T1，T2，…，Tn}規(guī)則為（1）若B為空，則F為空森林。（2）若B非空，則F第一棵樹T1根是二叉樹根，T1中根結(jié)點子森林F1是由B左子樹LB轉(zhuǎn)換而成森林，F(xiàn)中除T1外其他樹組成森林F'={T2，T3，…，Tn}是由B(F)右子樹RB轉(zhuǎn)換而成；75/257樹和森林遍歷一、先根法：若森林非空，則可按下列規(guī)則遍歷(1)訪問第一棵樹根結(jié)點(2)先根遍歷第一棵樹中根結(jié)點子樹組成森林(3)先根遍歷除去第一棵樹之后剩下樹組成森林二、后根法：若森林非空，則可按下列規(guī)則遍歷(1)后根遍歷第一棵樹中根結(jié)點子樹組成森林(2)訪問第一棵樹根結(jié)點(3)后根遍歷除去第一棵樹之后剩下樹組成森林76/257森林遍歷舉例：

J

L

KIHGFEACBD

F

D

C

A

B

E

G

H

I

J

K

L先根序列：ABCDEFGHIJKL后根序列：BCDAGHFEJLKI在對應(yīng)二叉樹中.先根序列對應(yīng)是二叉樹先序序列,后根序列對應(yīng)是二叉樹中序序列77/257哈夫曼樹(最優(yōu)樹）及應(yīng)用

某些概念：途徑：從一種結(jié)點到另一種結(jié)點之間若干個分支序列途徑長度：途徑上分支數(shù)目稱為途徑長度；結(jié)點途徑長度：從根到該結(jié)點途徑長度樹途徑長度：樹中所有結(jié)點途徑長度之和；一般記為PL。在結(jié)點數(shù)相同條件下，完全二叉樹是途徑最短二叉樹。7132564881325746非完全二叉樹完全二叉樹78/257哈夫曼樹概念結(jié)點權(quán)：根據(jù)應(yīng)用需要能夠給樹結(jié)點賦權(quán)值；結(jié)點帶權(quán)途徑長度：從根到該結(jié)點途徑長度與該結(jié)點權(quán)乘積；樹帶權(quán)途徑長度=樹中所有葉子結(jié)點帶權(quán)途徑之和；一般記作

WPL=

wi

Li哈夫曼樹：假設(shè)有n個權(quán)值(w1,

w2,…,wn)，構(gòu)造有n個葉子結(jié)點二叉樹，每個葉子結(jié)點有一種wi

作為它權(quán)值。則帶權(quán)途徑長度最小二叉樹稱為哈夫曼樹。BDACAC

DB7524475279/257BDACC

AD75244752AC

DB4752CA

BD4752BWPL=7*2+5*2+2*2+4*2=36WPL=7*1+5*2+2*3+4*3=35WPL=7*3+5*3+2*1+4*2=46WPL=7*1+5*2+2*3+4*3=35要使二叉樹WPL小,就須在構(gòu)造樹時,將權(quán)值大結(jié)點接近根.80/2572應(yīng)用舉例在求得某些判定問題時，利用哈夫曼樹取得最佳判定算法。例編制一種將百分制轉(zhuǎn)換成五分制程序。最直觀辦法是利用if語句來實現(xiàn)?？捎枚鏄涿枋雠卸ㄟ^程。a

80a

90不及格良好中等及格優(yōu)秀a

60a

7081/257分?jǐn)?shù)0-5960-6970-7980-8990-100百分比數(shù)0.050.150.400.300.10按圖判定過程:轉(zhuǎn)換一種分?jǐn)?shù)所需比較次數(shù)=

從根到對應(yīng)結(jié)點途徑長度轉(zhuǎn)換10000個分?jǐn)?shù)所需總比較次數(shù)=10000

(0.05

1+0.15

2+0.4

3+0.3

4+0.1

4）

=31500

二叉樹帶權(quán)途徑長度a

80a

90不及格良好中等及格優(yōu)秀a

60a

70設(shè)有10000個百分制分?jǐn)?shù)要轉(zhuǎn)換，設(shè)學(xué)生成績在5個等級以上分布如下：構(gòu)造以分?jǐn)?shù)分布百分比為權(quán)值哈夫曼樹82/257優(yōu)化判定樹a

80a

90不及格良好中等及格優(yōu)秀a

60a

70YYYYNNNN轉(zhuǎn)換10000個分?jǐn)?shù)所需總比較次數(shù)=10000

(0.05

3+0.15

3+0.4

2+0.3

2+0.1

2）

=2202383/2573哈夫曼樹構(gòu)造構(gòu)造哈夫曼樹步驟：1．根據(jù)給定n個權(quán)值，構(gòu)造n棵只有一種根結(jié)點二叉樹，n個權(quán)值分別是這些二叉樹根結(jié)點權(quán)。設(shè)F是由這n棵二叉樹組成集合2．在F中選用兩棵根結(jié)點樹值最小樹作為左、右子樹，構(gòu)造一顆新二叉樹，置新二叉樹根權(quán)值=左、右子樹根結(jié)點權(quán)值之和；3．從F中刪除這兩顆樹，并將新樹加入F；4．反復(fù)2、3，直到F中只含一顆樹為止；84/257403060155101530例：構(gòu)造以W=（5，15，40，30，10）為權(quán)哈夫曼樹。305101540403015510154030301551015哈夫曼樹中權(quán)值小結(jié)點離根遠權(quán)值大結(jié)點離根近40100306015510153085/257自測題設(shè)森林F中有三棵樹，第一，第二，第三棵樹結(jié)點個數(shù)分別為M1，M2和M3。與森林F對應(yīng)二叉樹根結(jié)點右子樹上結(jié)點個數(shù)是

A．M1B．M1+M2C．M3D．M2+M3

86/257自測題森林二叉樹用T表達。已知T前序和中序遍歷成果，請畫出對應(yīng)森林前序：ABCDEFGHIJKL中序：CBEFDGAJIKLHABCDEFGHIJKLAHBDGCEFIKLJ87/257自測題哪種樹，樹中任何結(jié)點到根結(jié)點途徑上各結(jié)點值是有序？堆二叉排序樹完全二叉樹以上都不是

88/257自測題設(shè)一段文本中包括字符{a,b,c,d,e}，其出現(xiàn)頻率對應(yīng)為{3,2,5,1,1}。則通過哈夫曼編碼后，文本所占字節(jié)數(shù)為40362512

127425321189/257自測題對二叉排序樹進行什么遍歷能夠得到從小到大排序序列？前序遍歷中序遍歷后序遍歷層次遍歷

90/257自測題在任意一顆二叉樹中，任何兩個葉結(jié)點在先序、中序、后序中相對次序如何？

不變不同樣不能確定以上都不是

91/257自測題某二叉樹中序序列和后序序列正好相反，則該二叉樹一定是空或只有一種結(jié)點高度等于其結(jié)點數(shù)任一結(jié)點無左孩子任一結(jié)點無右孩子

92/257自測題結(jié)點中序遍歷為xyz不一樣二叉樹，它有幾個不一樣狀態(tài)？

3456

yxzzxyzyxxzyxyz93/257自測題設(shè)n、m為一棵二叉樹上兩個結(jié)點，在中序遍歷時，n在m前條件是A．n在m右方B．n是m祖先C．n在m左方D．n是m子孫94/257自測題設(shè)高為h二叉樹只有度為0和2結(jié)點，則此類二叉樹結(jié)點數(shù)最少為___，最多為____？

2h-1+1,2h–12h,2h–12h–1,2h–12h–1,2h-1–195/257自測題一棵完全二叉樹共有2435個結(jié)點，則其中度為0結(jié)點數(shù)為？12181217不確定812前11層共有211-1=2047個結(jié)點第12層共有2435-2047=388個結(jié)點388+[210–388/2]=121896/257自測題哪種樹，樹中任何結(jié)點到根結(jié)點途徑上各結(jié)點值是有序？堆二叉排序樹完全二叉樹以上都不是

9797/257自測題某二叉樹中序序列和后序序列正好相反，則該二叉樹一定是空或只有一種結(jié)點高度等于其結(jié)點數(shù)任一結(jié)點無左孩子任一結(jié)點無右孩子

9898/257自測題設(shè)n、m為一棵二叉樹上兩個結(jié)點，在中序遍歷時，n在m前條件是A．n在m右方B．n是m祖先C．n在m左方D．n是m子孫9999/257自測題若一棵哈夫曼樹共有9個頂點，則其葉子節(jié)點個數(shù)為（）。

A.4 B.5 C.6 D.7100/257自測題哈夫曼樹有n個葉結(jié)點，則該樹共有多少個結(jié)點？2n2n-12n+1不能確定101N0=nN1=02*N2=N–1N=N0+N1+N2N=?101/257圖

圖定義

圖G由兩個集合組成，記作G=<V,E>其中V是頂點非空有限集合，E是邊有限集合，其中邊是頂點無序?qū)蛴行驅(qū)?。G1=<V1,E1>V1={v0,v1,v2,v3,v4}E1={(v0,v1),(v0,v3),(v1,v2),(v1,v4),(v2,v3)(v2,v4)}G1圖示無序?qū)?vi,vj)：用連接頂點vi、vj線段表達，稱為無向邊；例

V0

V4

V3

V1

V2102/257有序?qū)?lt;vi,vj>：用以為vi起點、以vj為終點有向線段表達，稱為有向邊或弧；無向圖：在圖G中，若所有邊是無向邊，則稱G為無向圖；有向圖：在圖G中，若所有邊是有向邊，則稱G為有向圖；混和圖：在圖G中，即有沒有向邊也有有向邊，則稱G為混合圖；G2=<V2,E2>V2={v0v1,v2,v3}E2={<v0,v1>

,<v0,v2>,<v2,v3>,<v3,v0>，<v0,v3>}G2圖示

V0

V1

V2

V3103/2571鄰接點及關(guān)聯(lián)邊

鄰接點：邊兩個頂點關(guān)聯(lián)邊：若邊a=(v0,v1),則稱頂點v0、v1關(guān)聯(lián)邊a2頂點度、入度、出度無向圖：頂點V度=與V有關(guān)聯(lián)邊數(shù)目在有向圖中：頂點V出度=以V為起點有向邊條數(shù)頂點V入度=以V為終點有向邊條數(shù)頂點V度=V出度+V入度設(shè)圖G頂點數(shù)為n，邊數(shù)為e

圖所有頂點度數(shù)和=2*e(每條邊對圖所有頂點度數(shù)和“奉獻”2度）a圖基本術(shù)語

V0

V4

V3

V1

V2

V0

V1

V2

V3104/257完全圖、完全有向圖：

具有n個頂點、n*(n-1)/2條邊無向圖稱為完全圖。而具有n個頂點、n*(n-1)條邊無向圖稱為有向完全圖。稀疏圖和稠密圖：邊數(shù)e比較少圖（e<n*logn）稱為稀疏圖，反之，稱為稠密圖。網(wǎng)絡(luò)：邊帶有權(quán)圖。一般這個權(quán)表達在這條邊上花費或兩點間距離。105/257

途徑、回路

無向圖G=（V，E）中頂點序列v1,v2,…,vk,若

(vi,vi+1)

E(i=1,2,…k-1),v=v1,u=vk,則稱該序列是從頂點v到頂點u途徑；若v=u，則稱該序列為回路；

有向圖D=（V，E）中頂點序列v1,v2,…,vk,若

<vi,vi+1>

E(i=1,2,…k-1),v=v1,u=vk,則稱該序列是從頂點v到頂點u途徑；若v=u，則稱該序列為回路；

在圖1中，V0,V1,V2,V3是V0到V3途徑；V0,V1,V2,V3,V0是回路；在圖2中，V0,V2,V3是V0到V3途徑；V0,V2,V3,V0是回路；無向圖G1有向圖G2例

V0

V4

V3

V1

V2

V0

V1

V2

V3106/257

簡單途徑和簡單回路

在一條途徑中,若除起點和終點外,所有頂點各不相同,則稱該途徑為簡單途徑； 由簡單途徑組成回路稱為簡單回路；

在圖1中，V0,V1,V2,V3是簡單途徑；V0,V1,V2,V4,V1不是簡單途徑；在圖2中，V0,V2,V3,V0是簡單回路；無向圖G1有向圖G2例

V0

V4

V3

V1

V2

V0

V1

V2

V3107/257連通圖（強連通圖）

在無（有）向圖G=<V,E>中，若對任何兩個頂點v、u都存在從v到u途徑，則稱G是連通圖（強連通圖）

非連通圖

連通圖

強連通圖

非強連通圖

V0

V1

V2

V3

V0

V4

V3

V1

V2

V0

V1

V2

V3

V0

V2

V3

V1

V5

V4108/257子圖設(shè)有兩個圖G=（V，E）、G1=（V1，E1），若V1

V，E1

E，E1關(guān)聯(lián)頂點都在V1中，則稱G1是G子圖；例(b)、(c)是(a)子圖(a)(b)(c)

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2109/257連通分圖（強連通分量）

無向圖G極大連通子圖稱為G連通分量極大連通子圖意思是：該子圖是G連通子圖，將G任何不在該子圖中頂點加入，子圖不再連通；子圖中邊包括子圖中頂點所有有關(guān)聯(lián)邊。連通分量非連通圖

V0

V2

V3

V1

V5

V4

V0

V2

V1連通圖110/257有向圖D極大強連通子圖稱為D強連通分量極大強連通子圖意思是：該子圖是D強連通子圖，將D任何不在該子圖中頂點加入，子圖不再是強連通；強連通分量

V0

V1

V2

V3

V0

V2

V3

V1111/2577生成樹包括連通無向圖G所有頂點極小連通子圖稱為G生成樹極小連通子圖意思是：該子圖是G連通子圖，在該子圖中刪除任何一條邊，子圖不再連通，若T是G生成樹當(dāng)且僅當(dāng)T滿足如下條件

T是G連通子圖

T包括G所有頂點

T中無回路連通圖G1G1生成樹

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2

V0

V4

V3

V1

V2112/257圖存放構(gòu)造最少要保存兩類信息：

1)頂點數(shù)據(jù)

2)頂點間關(guān)系商定:G=<V,E>是圖,V={v0,v1,v2,…vn-1},設(shè)頂點角標(biāo)為它編號

如何表達頂點間關(guān)系？頂點編號？

V0

V4

V3

V1

V2

V0

V1

V2

V3圖存放構(gòu)造113/257鄰接矩陣：G鄰接矩陣是滿足如下條件n階矩陣：A[i][j]=1若(vi,vi+1)

E或<vi,vi+1>

E0不然01010010101011010001100011000000001000一數(shù)組表達法(鄰接矩陣表達)在數(shù)組表達法中，用鄰接矩陣表達頂點間關(guān)系

V0

V4

V3

V1

V2

V0

V1

V2

V3114/257無向圖數(shù)組表達法特點：1）無向圖鄰接矩陣是對稱矩陣，同一條邊表達了兩次；2）頂點v度：等于二維數(shù)組對應(yīng)行（或列）中1個數(shù)；3）判斷兩頂點v、u是否為鄰接點：只需判二維數(shù)組對應(yīng)分量是否為1；4）頂點不變，在圖中增加、刪除邊：只需對二維數(shù)組對應(yīng)分量賦值1或清0；5）設(shè)圖頂點數(shù)為n,存放圖用一維數(shù)組,數(shù)組元素有m個（m>=n),則G占用存放空間：m+n2；G占用存放空間只與它頂點數(shù)有關(guān)，與邊數(shù)無關(guān)；適用于邊稠密圖；對有向圖數(shù)組表達法可做類似討論

01010010101011010001100數(shù)組表達法空間代價只與圖頂點數(shù)有關(guān)

V0

V4

V3

V1

V2115/257圖基本操作：1）求無向圖某頂點vi度(或有向圖中vi出度)。A[i][0]到A[i][n-1]中非0個數(shù)，即數(shù)組A中第i行非0元素個數(shù)；2）求有向圖某頂點vi入度。：A[0][i]到A[n-1][i]中非0個數(shù)，即數(shù)組A中第i列非0元素個數(shù)；3）檢測圖中總邊數(shù)。掃描整個數(shù)組A，統(tǒng)計出數(shù)組中非0元素個數(shù)。無向圖總邊數(shù)為非0元素個數(shù)二分之一，而有向圖總弧數(shù)為非0元素個數(shù)；01010010101011010001100

V0

V4

V3

V1

V2

V0

V1

V2

V3011000000001000116/257鄰接表

鄰接表是圖鏈?zhǔn)酱娣艠?gòu)造1無向圖鄰接表頂點：一般按編號次序?qū)㈨旤c數(shù)據(jù)存放在一維數(shù)組中；關(guān)聯(lián)同一頂點邊：用線性鏈表存放該結(jié)點表達邊（ViVj）,其中1是Vj在一維數(shù)組中位置例

V0

V4

V3

V1

V22

01234m-1V0V1V2V3V413422110034下標(biāo)編號link117/257

圖遍歷：從圖某頂點出發(fā)，訪問圖中所有頂點，并且每個頂點僅訪問一次。在圖中，訪問部分頂點后，也許又沿著其他邊回到已被訪問過頂點。為確保每一種頂點只被訪問一次，必須對頂點進行標(biāo)識，一般用一種輔助數(shù)組visit[MAX]作為對頂點標(biāo)識，當(dāng)頂點vi未被訪問，visit[i]值為0；當(dāng)vi已被訪問，則visit[i]值為1。

圖遍歷與樹遍歷有什么不一樣？

有兩種遍歷辦法（它們對無向圖，有向圖都適用）深度優(yōu)先遍歷廣度優(yōu)先遍歷圖遍歷118/257

V0

V7

V6

V5

V4

V3

V2

V1從圖中某頂點v出發(fā)：1）訪問頂點v；

2）依次從v未被訪問鄰接點出發(fā)，繼續(xù)對圖進行深度優(yōu)先遍歷；

V0,V1,V3,V7,V4,V2,V5,V6,由于沒有要求訪問鄰接點次序，深度優(yōu)先序列不是唯一這是序列（1）在遍歷過程中所通過途徑例一深度優(yōu)先遍歷求圖G以V0起點深度優(yōu)先序列：

V0

V1

V3

V2

V7

V6

V5

V4

V0,V1,V4,V7,V3,V2,V5,V6119/257假如將圖頂點鄰接點看作二叉樹結(jié)點左、右孩子深度優(yōu)先遍歷與先序遍歷是不是很類似？深度優(yōu)先遍歷從圖中某頂點v出發(fā)：（1）訪問頂點v；

（2）依次從v未被訪問鄰接點出發(fā)，對圖進行深度優(yōu)先遍歷；

先序遍歷（DLR）若二叉樹非空

（1）訪問根結(jié)點；（2）先序遍歷左子樹；

（3）先序遍歷右子樹；

V0

V7

V6

V5

V4

V3

V2

V1120/257圖遍歷：鄰接邊存放

V0

V7

V6

V5

V4

V3

V2

V1

01234567V0V1V2V3V4V5V6V7120115773064265243121/257

V0

V7

V6

V5

V4

V3

V2

V1圖中某未訪問過頂點vi出發(fā)：1）訪問頂點vi；2）訪問vi所有未被訪問鄰接點w1,w2,…wk

；3）依次從這些鄰接點出發(fā)，訪問它們所有未被訪問鄰接點;依此類推，直到圖中所有訪問過頂點鄰接點都被訪問；二廣度優(yōu)先遍歷（類似于樹按層遍歷）V0

V1

V3

V2

V7

V6

V5

V4這是序列（1）在遍歷過程中所通過途徑由于沒有要求訪問鄰接點次序，廣度優(yōu)先序列不是唯一例求圖G以V0起點廣度優(yōu)先序列V0,V1,V2,V3,V4,V5,V6,V7122/257從圖中某頂點vi出發(fā)：1）訪問頂點vi；（容易實現(xiàn)）2）訪問vi所有未被訪問鄰接點w1,w2,…wk

；（容易實現(xiàn)）3）依次從這些鄰接點（在步驟2）訪問頂點）出發(fā)，訪問它們所有未被訪問鄰接點;依此類推，直到圖中所有訪問過頂點鄰接點都被訪問；為實現(xiàn)3），需要保存在步驟(2）中訪問頂點，并且訪問這些頂點鄰接點次序為：先保存頂點，其鄰接點先被訪問。廣度優(yōu)先遍歷算法在廣度優(yōu)先遍歷算法中，需設(shè)置一隊列Q，保存已訪問頂點，并控制遍歷頂點次序。

V0

V7

V6

V5

V4

V3

V2

V1123/257QV0V1V2V3V7V1V2V3V0V4V5V6V7從圖中某頂點v出發(fā)：1）訪問頂點v；2）訪問v所有未被訪問鄰接點w1,w2,…wk

；3）依次從這些鄰接點出發(fā)，訪問它們所有未被訪問鄰接點;依此類推，直到圖中所有訪問過頂點鄰接點都被訪問；

V0

V7

V6

V5

V4

V3

V2

V1圖廣度遍歷演示隊列情況：124/257

連通圖G生成樹是一種連通圖G一種極小連通子圖。包括圖G所有頂點，但只有n-1條邊，并且是連通。生成樹可由遍歷過程中所通過邊組成。

深度優(yōu)先遍歷得到生成樹稱為深度優(yōu)先生成樹

廣度優(yōu)先遍歷得到生成樹稱為廣度優(yōu)先生成樹無向圖生成樹125/257例：圖廣度遍歷生成樹

V0

V7

V6

V5

V4

V3

V2

V1V0

V1

V3

V2

V7

V6

V5

V4126/257

要在n個都市間建立交通網(wǎng)，要考慮問題如何在確保n點連通前題下最節(jié)省經(jīng)費?V2V0V3V5V4

求解:連通6個都市且代價最小交通線路?如何求連通圖最小生成樹?？

若有一種連通無向圖G，有n個頂點，并且它邊是有權(quán)值。在G上構(gòu)造生成樹G’

,最小生成樹n-1條邊權(quán)值之和最小G’

。最小生成樹127/257Prim算法V2V0V3V5V4G=（V，E）為一種具有n個頂點帶權(quán)連通網(wǎng)絡(luò)，T=（U，TE）為構(gòu)造生成樹。（1）初始時，U={u0}，TE=

；（2）在所有u

U、v

V-U邊（u,v）中選擇一條權(quán)值最小邊，不妨設(shè)為（u,v)；（3）(u,v)加入TE，同步將v加入U；（4）反復(fù)(2)、（3），直到U=V為止；128/257V2V0V3V5V42V0V3V5V4V112V2V0V3V5V4V114V2V0V3V5V4V1142V2V0V3V5V4V11452V3V0V3V5V4V11453U={V0}U={V0,V2}U={V0,V2,V5}U={V0,V2,V5,V3}U={V0,V2,V5,V3,V1}U={V0,V2,V5,V3,V1,V4}Prim算法演示129/257

有關(guān)數(shù)據(jù)存放構(gòu)造無向連通網(wǎng)絡(luò):G

為選擇權(quán)值最小邊:置一種一維數(shù)組：closest[]，對i

V-Uclosest[i]=j表達(j,i)是一條邊，jU，

i

V-U且是i到U中各頂點“權(quán)最小邊”Lowcost[i]：用來保存上面連接i到U中各頂點“權(quán)最小邊”權(quán)。

普魯姆算法包括數(shù)據(jù)和操作：

數(shù)據(jù)：無向連通網(wǎng)絡(luò)

操作:

選擇權(quán)值最小邊，不妨設(shè)為（u,v)(u,v)加入TE，u加入UUV-U

viPrim算法實現(xiàn)V2V0V3V5V4V-U

vivj130/257關(guān)節(jié)點和連通度概念

假若圖中在刪去頂點v以及和v有關(guān)聯(lián)各邊之后，將該圖一種連通分量分割成兩個以上連通分量，則稱頂點v為該圖一種關(guān)節(jié)點。一種沒有關(guān)節(jié)點連通圖稱為重連通圖。若在連通圖上最少刪除k個頂點才能破壞圖連通性，則稱此圖連通度為k131/257關(guān)節(jié)點圖示ABCDELMFGHIJK132/257計算圖關(guān)節(jié)點辦法利用圖深度優(yōu)先遍歷能夠進行關(guān)節(jié)點計算：ABCDELMFGHIJKABCDELMFGHIJK133/257計算關(guān)節(jié)點辦法若深度優(yōu)先生成樹樹根有兩棵或兩棵以上子樹，則此根必為關(guān)節(jié)點。若生成樹中某個非葉子v某棵子樹中所有結(jié)點在圖中都沒有指向v祖先指針，則v為關(guān)節(jié)點。134/257有向無環(huán)圖及其應(yīng)用一、AOV網(wǎng)與拓撲排序二、AOE與關(guān)鍵途徑有向無環(huán)圖：沒有回路有向圖135/257例

作為學(xué)生必須學(xué)習(xí)一系列課程。有些課程是基礎(chǔ)課，必須先學(xué)習(xí)；而有些課程必須在學(xué)習(xí)完某些課程之后才能學(xué)習(xí)。假如用頂點表達學(xué)習(xí)課程，邊表達課程之間依賴關(guān)系，則形成了一種有向無環(huán)圖。AOV網(wǎng)(ActivityOnVertexnet)

用頂點表達活動，邊表達活動次序關(guān)系有向圖稱為AOV網(wǎng)AOV網(wǎng)136/257

某校計算機專業(yè)課程流程可AOV網(wǎng)表達。其中頂點：表達課程（也稱活動），弧：表達課程間先修關(guān)系；課程流程圖c1c2c3c4c5c6c7C8c9c10c11c12程序設(shè)計離散數(shù)學(xué)數(shù)據(jù)構(gòu)造匯編語言算法分析計算機體系編譯辦法操作系統(tǒng)高等數(shù)學(xué)線性代數(shù)電子電路數(shù)值分析無

c1c1,c2c1c3,c4c11c5,c3c3,c6無c9c9c9,c10,c1課程編號課程名稱先決條件

c4c1c2c3c12c9c10c11c6c7c8c5137/257AOV網(wǎng)與拓撲排序拓撲排序：所謂拓撲排序，是指在一種集合上通過一種偏序關(guān)系得到一種全序關(guān)系偏序關(guān)系：集合X上關(guān)系R具有自反性、反對稱性和傳遞性。全序關(guān)系：集合X上偏序關(guān)系R還滿足:對X上任何兩個元素x和y,必有xRy或yRx拓撲序列：通過拓撲排序得到序列138/257

一種可行學(xué)習(xí)計劃為：C1,C9,C4,C2,C10,C11,C12,C3,C6,C5,C7,C8

可行計劃特點：若在流程圖中頂點v是頂點u前趨，則在計劃序列中頂點v也是u前趨。拓撲排序：開課次序c4c1c2c3c12c9c10c11c6c7c8c5139/257拓撲序列：有向圖D一種頂點序列稱作一種拓撲序列，對于圖中任何兩點u、v，假如存在從u到v途徑，則在該序列中點u必然在點v前面。

拓撲排序：就是將有向圖中頂點排成拓撲序列。

如何判斷AOV網(wǎng)（有向圖）是否存在有向回路？？AOV網(wǎng)（有向圖）不存在有向回路當(dāng)且僅當(dāng)能對AOV網(wǎng)進行拓撲排序拓撲排序另類定義140/2571）在有向圖選一無前趨頂點v，輸出；

2）從有向圖中刪除v及以v為尾孤；

3）反復(fù)1、2、直接所有輸出所有頂點或有向圖中不存在無前趨頂點；例：V0,V1,V2,V3,V4,V5,V6如何在計算機上實現(xiàn)對有向圖拓撲排序？？拓撲排序辦法

V5

V3

V2

V0

V1

V4

V6141/2573）有關(guān)數(shù)據(jù)存放構(gòu)造01234562456334556

有向圖(AOV網(wǎng))：G

頂點入度：intdegree

整數(shù)棧intstack[]

：用于存放入度為0頂點編號下標(biāo)入度link0012232base654321010top初始時，只有v0,v1兩頂點入度為0拓撲排序算法

V5

V3

V2

V0

V1

V4

V6單獨寄存到數(shù)組indegree中142/257

對工程人們關(guān)懷兩類問題：1）工程能否次序進行，即工程流程是否“合理”

2）完成整項工程最少需要多少時間，哪些子工程是影響工程進度關(guān)鍵子工程？V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1頂點表達事件邊表達活動事件Vj發(fā)生表達

ak已結(jié)束ak

VjVi事件Vi發(fā)生表達

ak能夠開始

AOE網(wǎng)AOE網(wǎng)及關(guān)鍵途徑143/257AOV網(wǎng)，AOE網(wǎng)，用都能表達工程各子工程流程，一種用頂點表達活動，一種用邊表達活動，但AOV網(wǎng)側(cè)重表達活動前后次序，AOE網(wǎng)除表達活動先后次序，還表達了活動連續(xù)時間等，因此可利用AOE網(wǎng)處理工程所需最短時間及哪些子工程拖延會影響整個工程按時完成等問題。實際應(yīng)用中采取那一種圖，取決于要求解問題。

為計算完成整個工程最少需要多少時間，需將每一子工程所需時間作為權(quán)值賦給AOE網(wǎng)各邊。AOE網(wǎng)與AOV網(wǎng)由于常用AOE網(wǎng)表達工程，因此在正常情況下AOE網(wǎng)中只有一種定點入度為0，也只有一種定點出度為0144/257關(guān)鍵途徑與關(guān)鍵活動由于在AOE網(wǎng)中有些活動能夠并行進行，因此完成工程最短時間是從開始點到完成點最長途徑長度（帶權(quán)）。路經(jīng)長度最長途徑稱為關(guān)鍵途徑關(guān)鍵途徑上活動稱為關(guān)鍵活動V3V1V4V6V5V2a4=3a1=3a2=2a6=3a5=4a3=2a7=2a8=1145/257V1

開始事件,V6

結(jié)束事件事件vj最早發(fā)生時間ve[j]:事件vj最遲發(fā)生時間vl[i]:不推遲工期為前提活動ak最早開始時間e[k]活動ak

最晚開始時間1[i]:不推遲工期為前提活動ak

最大允許延遲時間

diff[k]=l[k]–e[k]關(guān)鍵途徑計算:ve,vl,e,l數(shù)組定義V3V1