數(shù)據(jù)結(jié)構(gòu)(C語(yǔ)言描述)講解

1、1 數(shù)據(jù)結(jié)構(gòu)輔導(dǎo) 李青山 西安電子科技大學(xué) 5/faculty/liqingshan 029-8820-4611 2 課程內(nèi)容框架 數(shù) 據(jù) 結(jié) 構(gòu) 基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)應(yīng)用數(shù)據(jù)結(jié)構(gòu) 棧 隊(duì) 列 線 性 表 線性結(jié)構(gòu) 非線性結(jié)構(gòu) 串 查 找 內(nèi) 部 排 序 外 部 排 序 文 件 動(dòng) 態(tài) 存 管 理 儲(chǔ) 數(shù) 組 廣 義 表 樹 二 叉 樹 圖 3 基本概念 1.2基本概念和術(shù)語(yǔ) 數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象 結(jié)構(gòu) *集合：松散的關(guān)系 *線性結(jié)構(gòu)：一對(duì)一的關(guān)系 *樹形結(jié)構(gòu)：一對(duì)多的關(guān)系 *網(wǎng)狀結(jié)構(gòu)：多對(duì)多的關(guān)系 數(shù)據(jù)結(jié)構(gòu) Data_Structure=（D，S）

2、4 數(shù)據(jù)結(jié)構(gòu)的分類 1.2基本概念和術(shù)語(yǔ)（續(xù)） 邏輯結(jié)構(gòu)： 數(shù)據(jù)元素之間的邏輯關(guān)系（本來(lái)的關(guān)系） 存儲(chǔ)結(jié)構(gòu)： 數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的映象。包括數(shù)據(jù)元 素的表示和關(guān)系的表示兩個(gè)方面。 分類： *順序存儲(chǔ)結(jié)構(gòu) *鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 描述方式： 用高級(jí)語(yǔ)言中的“數(shù)據(jù)類型”來(lái)描述 5 算法 1.3算法和算法分析 內(nèi)涵: 是對(duì)特定問(wèn)題求解步驟的一種描述，是指令 的有限序列，其中每一條指令表示一個(gè)或多個(gè) 操作。 特性: *有窮性：有窮步+有窮時(shí)間/每一步 *確定性：指令的語(yǔ)義無(wú)二義性 *可行性：算法能用基本操作完成 *輸入：零個(gè)或多個(gè)輸入 *輸出：一個(gè)或多個(gè)輸出 6 算法設(shè)計(jì)的要求 1.3算法和算法分析（續(xù)） 正

3、確性（Correctness） 可讀性（Readablity） 健壯性（Robustness） 高時(shí)間效率與低存儲(chǔ)量需求 7 算法時(shí)間效率的度量 1.3算法和算法分析（續(xù)） 算法時(shí)間效率度量的基本做法 在算法中選取一種對(duì)于所研究問(wèn)題來(lái)說(shuō)是 基本操作的原操作，以該基本操作重復(fù)執(zhí)行的 次數(shù)作為算法的時(shí)間度量。 一般而言，這個(gè)基本操作是最深層循環(huán)內(nèi) 的語(yǔ)句中的原操作。 算法時(shí)間復(fù)雜度 T(n)=O (f(n) 稱為算法的漸近時(shí)間復(fù)雜度， 簡(jiǎn)稱時(shí)間復(fù)雜度。 8 算法存儲(chǔ)空間的度量 1.3算法和算法分析（續(xù)） 算法存儲(chǔ)空間度量的基本做法 用程序執(zhí)行中需要的輔助空間的消耗作為 存儲(chǔ)空間度量的依據(jù)，是問(wèn)題規(guī)

4、模n的函數(shù)。 而程序執(zhí)行中本身需要的工作單元不能算。 算法空間復(fù)雜度 S(n)=O (f(n) 稱為算法的空間復(fù)雜度。 9 2.線性表 3.棧、隊(duì)列和串 第一部分 線性數(shù)據(jù)結(jié)構(gòu) 10 線性數(shù)據(jù)結(jié)構(gòu)的特點(diǎn) 2.1線性表的邏輯結(jié)構(gòu) 在數(shù)據(jù)元素的非空有限集中 存在唯一的一個(gè)被稱作“第一個(gè)”的數(shù)據(jù)元素； 存在唯一的一個(gè)被稱作“最后一個(gè)”的數(shù)據(jù)元 素； 除第一個(gè)之外，集合中的每一個(gè)數(shù)據(jù)元素均只 有一個(gè)前驅(qū)； 除最后一個(gè)之外，集合中每一個(gè)數(shù)據(jù)元素均只 有一個(gè)后繼。 11 基本概念和術(shù)語(yǔ) 2.1線性表的邏輯結(jié)構(gòu)（續(xù)） 線性表：n個(gè)數(shù)據(jù)元素的有限序列（線性表中 的數(shù)據(jù)元素在不同環(huán)境下具體含義可以不同， 但在同

5、一線性表中的元素性質(zhì)必須相同）。 表長(zhǎng)：線性表中元素的個(gè)數(shù)n(n=0)。 空表：n=0時(shí)的線性表稱為空表。 位序：非空表中數(shù)據(jù)元素 ai 是此表的第 i 個(gè)元 素，則稱 i 為 ai 在線性表中的位序。 12 線性表的抽象數(shù)據(jù)類型定義 2.1線性表的邏輯結(jié)構(gòu)（續(xù)） ADT List 數(shù)據(jù)對(duì)象：D=ai | ai屬于ElemSet, i = 1,2, ,n, n=0 數(shù)據(jù)關(guān)系：R1=| ai-1, ai屬于D, i =2,3, , n 基本操作： InitList( p-next=s 22 單鏈表上刪除運(yùn)算的實(shí)現(xiàn) 2.3線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)（續(xù)） 刪除 q （a1， ai, ai+1, an)

6、表長(zhǎng)為n ListDelete( if (!S.base) exit (OVERFLOW); / 存儲(chǔ)分配失敗 S.top = S.base + S.stacksize; S.stacksize =+ STACKINCERMENT; *S.top+ = e; return OK; / Push 入棧 a1 ai a2 base top a1 e ai a2 base top 順序棧上的入棧 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） 33 Status Pop(SqStack e = * -S.top; return OK; / Pop出棧 a1 ai-1 a2 base top a1 ai ai-

7、1 a2 base top 順序棧上的出棧 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） 34 棧的鏈?zhǔn)酱鎯?chǔ)-鏈棧 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） basetop typedef struct ElemTypedata struct Lnode*next Lnode,* StackPtr an-1a1 an typedef struct StackPtr top StackPtr base LinkStack 35 鏈棧上的入棧與出棧 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） 鏈棧上的入棧與出棧與單鏈表上元素插入刪除 操作類似 插入刪除位置都在棧頂處，不花費(fèi)查找時(shí)間 ?？盏呐袛?36 隊(duì)列的順序存儲(chǔ)

8、-循環(huán)隊(duì)列（一） 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） a1 ai a2 front 一般順序存儲(chǔ)的隊(duì)列特點(diǎn)： 隊(duì)空條件：front = rear 隊(duì)滿條件：rear = MAXSIZE 隊(duì)滿條件下的隊(duì)滿為假滿（假溢出） （真滿時(shí)：rear = MAXSIZE, front = 0） rear 37 /-動(dòng)態(tài)分配- #define MAXSIZE 100 /最大隊(duì)列長(zhǎng)度 typedef struct QElemType*base intfront/指向隊(duì)頭元素當(dāng)前位置 intrear / 指向隊(duì)尾元素下一個(gè)位置 SqQueue 隊(duì)列的順序存儲(chǔ)-循環(huán)隊(duì)列（二) 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)

9、） 38 循環(huán)隊(duì)列特點(diǎn)： 隊(duì)空條件： *front = rear（方式一） *標(biāo)志域 + （front = rear） （方式二） 隊(duì)滿條件： *(rear+1) % MAXSIZE = front （方式一） *標(biāo)志域 + （front = rear） （方式二） 隊(duì)滿條件下的隊(duì)滿為真滿 隊(duì)列的順序存儲(chǔ)-循環(huán)隊(duì)列（三) 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） 39 隊(duì)列的順序存儲(chǔ)-循環(huán)隊(duì)列（四) 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） Status EnQueue(SqQueue Q.baseQ.rear = e; Q.rear = (Q.rear +1) % MAXSIZE; return O

10、K; / EnQueue Status InitQueue(SqQueue if (! Q.base) exit(overflow); Q.front = Q.rear = 0 ; return OK; / InitQueue Status DeQueue(SqQueue e = Q.baseQ.front; Q.front = (Q.front +1) % MAXSIZE; return OK; / DeQueue 40 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)-鏈隊(duì)列（一） 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） typedef struct QElemTypedata struct QNode*next QNode

11、,* QueuePtr a2an a1 typedef struct QueuePtr rear QueuePtr front LinkQueue q.rear.front 41 Status EnQueue(LinkQueue if (!p) exit(overflow); p-data = e;p-next = NULL; Q.rear-next = p;Q.rear = p; return OK; / EnQueue Status InitQueue(LinkQueue if (! Q.front) exit(overflow); Q.front-next = NULL ; return

12、 OK; / InitQueue Status DeQueue(LinkQueue p = Q.front-next; e = p-data; Q.front-next = p-next; if (Q.rear = =p) Q.rear = Q.front; free(p); return OK; / DeQueue 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)-鏈隊(duì)列（二） 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） 42 串的順序存儲(chǔ)（一） 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） /-串的定長(zhǎng)順序存儲(chǔ)表示- #define MAXSTRLEN 255 /最大串長(zhǎng)度 typedef unsigned char SStringMA

13、XSTRLEN+1 /0號(hào)單元存放串的長(zhǎng)度 串順序存儲(chǔ)的特點(diǎn)： 連續(xù)存儲(chǔ)單元靜態(tài)分配 串操作中的原操作一般為“字符序列的復(fù)制” 截尾法處理串值序列的上越界 43 Status SubString(SString Sub1.len = Spos.pos+len-1; Sub0 =len; return OK; / SubString 串的順序存儲(chǔ)（二） 3.2 棧、隊(duì)列和串的存儲(chǔ)結(jié)構(gòu)（續(xù)） Status Concat(SString j = 1; /字符之后的位置。若不存在， while (i= s0 else return 0; / Index 算法時(shí)間復(fù)雜度：T(n) = O(n*m) 邏輯

14、函數(shù)為 Index(S,T,pos) S = a1a2aianT = t1t2tjtm 一般而言，mn 算法思路： 從主串S的第pos個(gè)字符起和模式的第一個(gè) 字符比較之，若相等，繼續(xù)逐個(gè)比較后續(xù)字 符，否則從主串的下一個(gè)字符起再重新和模 式的字符比較之。 45 3.3 串的模式匹配算法（續(xù)） 第一趟 主串： a b a b c a b c a c b a b/i =3 模式串： a b c/j =3 第二趟 主串： a b a b c a b c a c b a b /i =2 模式串： a /j =1 第三趟 主串： a b a b c a b c a c b a b /i =7 模式串：

15、a b c a c /j =5 第四趟 主串： a b a b c a b c a c b a b /i =4 模式串： a /j =1 第五趟 主串： a b a b c a b c a c b a b /i =5 模式串： a /j =1 第六趟 主串： a b a b c a b c a c b a b /i =11 模式串： a b c a c /j =6 模式串T= abcac 46 改進(jìn)算法-思路 3.3 串的模式匹配算法（續(xù)） KMP算法思路： 從主串S的第pos個(gè)字符起和模式的第一個(gè)字符 比較之，若相等，繼續(xù)逐個(gè)比較后續(xù)字符。當(dāng)一趟 匹配過(guò)程中出現(xiàn)字符比較不等時(shí)，不回朔i指針，

16、而 是利用已經(jīng)得到的“部分匹配”的結(jié)果將模式串向 右“滑動(dòng)”盡可能遠(yuǎn)的一段距離后，繼續(xù)進(jìn)行比較。 優(yōu)點(diǎn)： 在匹配過(guò)程中，主串的跟蹤指針不回朔 時(shí)間效率達(dá)到T(n) = O(n+m) 如何理解“部分匹配”？ 主串： a c a b a a c a a b c a c 模式串： a c a a b 47 改進(jìn)算法-原理 3.3 串的模式匹配算法（續(xù)） 設(shè)主串S=s1s2sisn, 模式串T= t1t2tjtm 在匹配過(guò)程中，當(dāng)主串中第i個(gè)字符與模式串中第j個(gè)字符 “失配”時(shí)（si不等于tj），將模式串“向右滑動(dòng)”，讓模式 串中第k（kj）個(gè)字符與si對(duì)齊繼續(xù)比較。這時(shí)有： t1t2tk-1 = s

17、i-k+1si-k+2si-1 -(1) 而由部分匹配成功的結(jié)果可知： t1t2tj-1 = si-j+1si-j+2si-1-(2) 由(2)式可以推知： tj-k+1tj-k+2tj-1 = si-k+1si-k+2si-1 -(3) 由(1)式與(3)式可以推知： t1t2tk-1 = tj-k+1tj-k+2tj-1 -(4) 48 令nextj = k，表示當(dāng)模式串中第j個(gè)字符與主串中相應(yīng)字符 “失配”時(shí)，在模式中需重新和主串中該字符進(jìn)行比較的字符的位 置。根據(jù)其語(yǔ)義，定義如下： 0當(dāng)j = 1時(shí) /相當(dāng)于主串中i指針推進(jìn)一個(gè)位置 Nextj = Max k | 1kj 且 t1t2

18、tk-1 = tj-k+1tj-k+2tj-1 / 1其他情況 改進(jìn)算法-Next函數(shù)定義 3.3 串的模式匹配算法（續(xù)） 設(shè)主串S=s1s2sisn, 模式串T= t1t2tjtm Next函數(shù)值僅取決于模式串本身的結(jié)構(gòu)而與相匹配的主串無(wú)關(guān) j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c nextj 0 1 1 2 2 3 1 2 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a c nextj 保證得到第 一個(gè)“配串” 49 改進(jìn)算法-匹配過(guò)程 3.3 串的模式匹配算法（續(xù)） 第一趟 主串： a c a b a a b a a b c a

19、c a a b c /i =2 模式串： a b/j =2, next2=1 第二趟 主串： a c a b a a b a a b c a c a a b c /i =2 模式串： a/j =1, next1=0 第三趟 主串： a c a b a a b a a b c a c a a b c /i =8 模式串： a b a a b c/j =6, next6=3 第四趟 主串： a c a b a a b a a b c a c a a b c /i =14 模式串： (a b) a a b c a c /j =9 j 1 2 3 4 5 6 7 8 模式串 a b a a b c a

20、 c nextj 0 1 1 2 2 3 1 2 50 int Index_KMP(SString S,SString T, int pos) /返回子串T在主串S中第pos個(gè)字符之后的位置。若不存在,函數(shù)值為0 i = pos;j = 1; while (i= s0 else return 0; / Index_KMP 算法時(shí)間復(fù)雜度：T(n) = O(n+m) 改進(jìn)算法-KMP算法 3.3 串的模式匹配算法（續(xù)） 51 4.數(shù)組 5.廣義表 6.樹和二叉樹 7.圖 第二部分 非線性數(shù)據(jù)結(jié)構(gòu) 52 4.數(shù)組 5.廣義表 6.樹和二叉樹 7.圖 教學(xué)內(nèi)容-第六章 53 6.1樹的邏輯結(jié)構(gòu) 基本

21、概念和術(shù)語(yǔ) 樹：樹T是n個(gè)結(jié)點(diǎn)的有限集。非空樹中： （1）有且只有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)； （2）當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為m(m0)各互不相交 的有限集T1,T2,Tm,其中每一個(gè)集合本身又是 一棵樹，并且稱為根的子樹(SubTree)。 樹的結(jié)點(diǎn)：一個(gè)數(shù)據(jù)元素和指向其子樹的分支。 結(jié)點(diǎn)的度：結(jié)點(diǎn)擁有的子樹數(shù)。 終端結(jié)點(diǎn)（或葉子）：度為0的結(jié)點(diǎn)。 非終端結(jié)點(diǎn)（或分支結(jié)點(diǎn)、或內(nèi)部結(jié)點(diǎn)） ：度不為0的結(jié)點(diǎn)。 樹的度：樹內(nèi)各結(jié)點(diǎn)的度的最大值。 （結(jié)點(diǎn)的）孩子：結(jié)點(diǎn)的子樹的根。 54 6.1樹的邏輯結(jié)構(gòu)（續(xù)） 樹的性質(zhì)及樹的表示 樹的性質(zhì)： 遞歸性 層次性 樹的表示形式： 樹形表示 集合嵌

22、套表示 廣義表形式表示 凹入表示 55 datafirstchild nextsibling結(jié)點(diǎn) 6.2樹的存儲(chǔ)結(jié)構(gòu)（續(xù)） 孩子兄弟表示法（二叉鏈表） /-樹的二叉鏈表（孩子-兄弟）存儲(chǔ)表示- typedef struct CSNode ElemTypedata;/樹結(jié)點(diǎn)數(shù)據(jù)域 struct CSNode *firstchild, *nextsibling; CSNode, *CSTree; 56 6.3二叉樹的邏輯結(jié)構(gòu) 二叉樹的描述性定義及其基本形態(tài) 二叉樹：二叉樹BT是n個(gè)結(jié)點(diǎn)的有限集。非空二叉樹 中：（1）有且只有一個(gè)特定的稱為根(Root)的結(jié)點(diǎn)； （2）當(dāng)n1時(shí)，其余結(jié)點(diǎn)可分為2個(gè)互

23、不相交 的有限集BTL,BTR, BTL,BTR分別又是一棵二叉樹， BTL 稱為根的左子樹； BTR稱為根的右子樹。 二叉樹的基本形態(tài)： 五種：空二叉樹；僅有根結(jié)點(diǎn)的二叉樹；右子樹為 空的二叉樹；左、右子樹均不為空的二叉樹；左子樹 為空的二叉樹。 57 6.3二叉樹的邏輯結(jié)構(gòu)（續(xù)） 二叉樹的數(shù)學(xué)性質(zhì) 性質(zhì)1：在二叉樹的第i層上至多右2i-1個(gè)結(jié)點(diǎn)(i=1); 性質(zhì)2：深度為k的二叉樹至多有2k 1個(gè)結(jié)點(diǎn)(k=1); 性質(zhì)3：二叉樹T，若葉子結(jié)點(diǎn)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2， 則有n0 = n2 +1; 性質(zhì)1： 證明 i=1時(shí)，顯然有2i-1 = 20 =1； 假設(shè)對(duì)于所有的j，1=ji，

24、第j層上至多有2j-1 個(gè)結(jié)點(diǎn)，則 當(dāng)j=i時(shí)，由假設(shè)知2i-1 層上至多右2i-2 ,而二叉樹的每個(gè)結(jié) 點(diǎn)的度至多為2，故在第i層上 最大結(jié)點(diǎn)數(shù)為i-1層上最大 結(jié)點(diǎn)數(shù)的2倍，即2* 2i-2 = 2i-1 。 證畢 性質(zhì)3： 證明 n = n0 + n1 + n2 n = B+1 B = n1 + 2n2 所以： n0 = n2 + 1 證畢 性質(zhì)4：具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為：以2為底的n的 對(duì)數(shù)值取下整+1； 性質(zhì)5：n個(gè)結(jié)點(diǎn)的完全二叉樹結(jié)點(diǎn)按照層序編號(hào)，則對(duì)任一 結(jié)點(diǎn)i(1=i1，則其雙親是結(jié)點(diǎn)(i/2)取下整；(2)如果2in,則結(jié)點(diǎn)i 無(wú)左孩子（結(jié)點(diǎn)i為葉子結(jié)點(diǎn)）；否則其左

25、孩子是結(jié)點(diǎn) 2i； (3)如果如果2i+1n,則結(jié)點(diǎn)i無(wú)右孩子；否則其右孩子是結(jié)點(diǎn) 2i+1。 滿二叉樹：深度為k且有2k 1個(gè)結(jié)點(diǎn)的二叉樹; 完全二叉樹：深度為k，有n個(gè)結(jié)點(diǎn)的二叉樹，當(dāng)且僅當(dāng)其每 一個(gè)結(jié)點(diǎn)都與深度為k的滿二叉樹中編號(hào)從1至n的結(jié)點(diǎn)一一 對(duì)應(yīng)時(shí)，稱之為完全二叉樹。 性質(zhì)4： 證明 假設(shè)深度為k，由性質(zhì)2以及完全二叉樹定義有： 2k-1 1 n =2k 1 推出 2k-1 = n 2k k 1 = 以2為底的n的對(duì)數(shù) lchild,Visit) if(Visit(T-data) if(InOrderTraverse(T-rchild,Visit)return OK; else

26、return ERROR; /當(dāng)訪問(wèn)失敗時(shí)，出錯(cuò) elsereturn OK; /一次遞歸訪問(wèn)終止 InOrderTraverse / 算法時(shí)間復(fù)雜度：O(n) 6.5二叉樹的遍歷及線索化（續(xù)） 中序遍歷的算法 Status InOrderTraverse1(BiTree T, Status (* Visit) (TElemType e) /中序遍歷二叉樹T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit InitStack(S); Push(S,T); /根指針入棧 While (!StackEmpty(S) while (GetTop(S,p) /向左走到盡頭 Pop(S,p)/空指針退棧

27、if (! StackEmpty(S) /訪問(wèn)結(jié)點(diǎn)，向右一步 Pop(S,p);if (!Visit(p-data) return ERROR /訪問(wèn)出錯(cuò) Push(S,p-rchild); /if /while return OK; InOrderTraverse / 算法時(shí)間復(fù)雜度：O(n) Status InOrderTraverse2(BiTree T, Status (* Visit) (TElemType e) /中序遍歷二叉樹T的非遞歸算法，對(duì)每個(gè)數(shù)據(jù)元素調(diào)用函數(shù)Visit InitStack(S); p = T; While ( p | !StackEmpty(S) if (p

28、) Push (S,p); p = p-lchild; /根指針入棧,遍歷左子樹 else /根指針退棧，訪問(wèn)根結(jié)點(diǎn)，遍歷右子樹 Pop(S,p);if (!Visit(p-data) return ERROR /訪問(wèn)出錯(cuò) p = p-rchild); /else /while return OK; InOrderTraverse / 算法時(shí)間復(fù)雜度：O(n) 68 6.5二叉樹的遍歷及線索化（續(xù)） 二叉樹遍歷的典型應(yīng)用 已知二叉樹的前序 遍歷序列和中序遍歷序 列，或者已知二叉樹的 后序遍歷序列和中序遍 歷序列，可以唯一確定 這棵二叉樹。 E A B C D F I J HG K Step1:

29、判定根，由 PostOrder知根為A； Step2:判定左子樹元 素集合，由InOrder知 為C B E D G F H InOrder: C B E D G F H A J I K PostOrder: C E G H F D B J K I A Step3:判定右子樹元 素集合，由InOrder知 為J I K Step4:分別對(duì)左、右子樹元 素集合按照中序和后序序 列遞歸進(jìn)行Step1-Step3， 直到元素集合為空。 69 6.5二叉樹的遍歷及線索化（續(xù)） 線索二叉樹 遍歷本質(zhì)是結(jié)點(diǎn)之間非線性關(guān)系線性化的過(guò)程 遍歷后的元素之間的某種線性關(guān)系一般隱藏在遍歷規(guī)則下 需要多次對(duì)同一棵樹遍

30、歷時(shí)，如何提高效率？ 在二叉鏈表結(jié)構(gòu)中增加線索域，顯式描述遍歷后的線索關(guān)系 節(jié)省線索域空間，充分利用二叉鏈表中空的n+1個(gè)指針域 線索鏈表：二叉樹的存儲(chǔ)結(jié)構(gòu)，結(jié)點(diǎn)結(jié)構(gòu)定義見(jiàn)前面。 線索：指向結(jié)點(diǎn)前驅(qū)和后繼的指針，叫做線索。 線索二叉樹：加上線索的二叉樹。 線索化：對(duì)二叉樹以某種次序遍歷使其變?yōu)榫€索二叉樹的過(guò) 程。 線索二叉樹上遍歷的過(guò)程， 就是根據(jù)線索和遍歷規(guī)則不斷 找當(dāng)前結(jié)點(diǎn)后繼結(jié)點(diǎn)的過(guò)程。 70 6.5二叉樹的遍歷及線索化（續(xù)） 線索二叉樹上的中序遍歷 InOrder: C B E D G F H A J I K 設(shè)當(dāng)前結(jié)點(diǎn)指針為p， 其前驅(qū)結(jié)點(diǎn)為q，后 繼結(jié)點(diǎn)指針為s,則有： 求結(jié)點(diǎn)p的

31、后繼： 1.若 p-rtag = 1 則 s = p-rchild; 2.若p-rtag = 0 s為p的右子樹的中 序遍歷序列的第一個(gè) 結(jié)點(diǎn)，即右子樹最左 下結(jié)點(diǎn) E A B C D F I J HG K 求結(jié)點(diǎn)p的前驅(qū)： 1.若 p-ltag = 1 則 q = p-lchild; 2.若p-rtag = 0 q為p的左子樹的中 序遍歷序列的第一個(gè) 結(jié)點(diǎn)，即左子樹最右 下結(jié)點(diǎn) 71 6.6樹、森林與二叉樹的轉(zhuǎn)換 森林與樹相互遞歸定義 森林：m棵互不相交的樹的集合。 樹：樹是一個(gè)二元組Tree = (root，F(xiàn)),root是根，F(xiàn)是m(m0) 棵樹的森林，F(xiàn) =T1,T2,Tm其中Ti =

32、 (ri，F(xiàn)i) 稱為根的第i 棵子樹；當(dāng)m != 0時(shí)，在樹根和其子樹森林之間存在下列關(guān) 系：RF = | i = 1,2,m, m0 72 6.6樹、森林與二叉樹的轉(zhuǎn)換（續(xù)） 樹與二叉樹的轉(zhuǎn)換 目的：利用二叉樹運(yùn)算來(lái)簡(jiǎn)化樹和森林上的運(yùn)算； 依據(jù)：樹與二叉樹具有相同的二叉鏈表存儲(chǔ)結(jié)構(gòu) ； E A BC D F I A B D E C I F 73 E A BC D F I JHG K A B D E C I F K J G H 6.6樹、森林與二叉樹的轉(zhuǎn)換（續(xù)） 74 E A B C D F I J HG K E A B C D FH G KI J 6.6樹、森林與二叉樹的轉(zhuǎn)換（續(xù)） 75

33、6.7二叉樹的應(yīng)用 哈夫曼樹(Huffman Tree) 結(jié)點(diǎn)之間路徑長(zhǎng)度：樹中兩個(gè)結(jié)點(diǎn)之間的分支構(gòu)成這兩個(gè)結(jié) 點(diǎn)的路徑，路徑上的分支數(shù)目為路徑長(zhǎng)度。 樹的路徑長(zhǎng)度：樹根到每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度：該結(jié)點(diǎn)到樹根之間的路徑長(zhǎng)度與結(jié)點(diǎn) 上權(quán)的乘積。 樹的帶權(quán)路徑長(zhǎng)度：樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和， 記為：WPL = w1k1 + w2k2 + wiki + wnkn。 最優(yōu)二叉樹（哈夫曼樹）：設(shè)n個(gè)權(quán)值w1, w2, wn ,構(gòu)造 一棵有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)wi,則其中 帶權(quán)路徑長(zhǎng)度WPL最小的二叉樹稱為最優(yōu)二叉樹（哈夫曼 樹） 。 76 6.7二叉樹的

34、應(yīng)用（續(xù)） 哈夫曼算法(Huffman Algorithmic) 輸入： n個(gè)權(quán)值w1, w2, wn ； 輸出：一棵哈夫曼樹 算法： 步驟一： 根據(jù)給定的n個(gè)權(quán)值w1, w2, wn 構(gòu)成n棵二叉樹的集 合F =T1, T2 , Tn ，其中每棵二叉樹Ti 中只有一個(gè)帶權(quán)為wi 的 根結(jié)點(diǎn)，其左右子樹均為空。 步驟二：在F中選取兩棵根結(jié)點(diǎn)的權(quán)值最小的樹作為左、右子樹 構(gòu)造一棵新的二叉樹，且置新的二叉樹的根結(jié)點(diǎn)的權(quán)值為其左、 右子樹上根結(jié)點(diǎn)的權(quán)值之和。 步驟三：在F中刪除這兩棵樹，同時(shí)將新得到的二叉樹加入F中。 步驟四：重復(fù)步驟二與三，直到F只含有一棵樹為止。 77 給定權(quán)的集合: 15,3,

35、14,2,6,9,16,17 6.7二叉樹的應(yīng)用（續(xù)） 哈夫曼算法(Huffman Algorithmic) 15,3,14,2,6,9,16,17 15,5,14,6,9,16,17 15,11,14,9,16,17 15,14,20,16,17 29,20,16,17 29,20,33 49,33 82 9 49 6 1617 82 32 5 141511 2029 33 WPL =(2+3)*5+6*4+(9+14+15)*3+(16+17)*2 = 229 78 6.7二叉樹的應(yīng)用（續(xù)） 哈夫曼編碼(Huffman Code) 等長(zhǎng)編碼：每個(gè)被編碼對(duì)象的碼長(zhǎng)相等。 優(yōu)點(diǎn)：碼長(zhǎng)等長(zhǎng)，易于

36、解碼； 缺點(diǎn)：被編碼信息總碼長(zhǎng)較大，尤其是當(dāng)存在 許多不常用的被編碼對(duì)象時(shí) 前綴編碼：任一個(gè)被編碼對(duì)象的編碼都不是另一個(gè) 被編碼對(duì)象的編碼的前綴。 優(yōu)點(diǎn)：當(dāng)存在被編碼對(duì)象使用概率不同時(shí)，被 編碼信息總碼長(zhǎng)可以減??； 缺點(diǎn)：碼長(zhǎng)不等長(zhǎng)，不易于解碼 79 6.7二叉樹的應(yīng)用（續(xù)） 哈夫曼編碼(Huffman Code)-前綴編碼 利用二叉樹來(lái)設(shè)計(jì)二進(jìn)制的 前綴編碼： 被編碼對(duì)象出現(xiàn)在二叉樹的 葉子結(jié)點(diǎn)。約定左分支表示字符 “0”，右分支表示字符“1”， 則可以從根結(jié)點(diǎn)到葉子結(jié)點(diǎn)的路 徑上分支字符組成的字符串作為 該葉子結(jié)點(diǎn)對(duì)應(yīng)對(duì)象的編碼。 b a e dc f 0 0 0 0 0 1 11 1 1

37、 a(00) b(010) c(0110) d(0111) e(10) f(11) 這種編碼的譯碼過(guò)程從根開 始。沿著某條分支走到葉子結(jié)點(diǎn) 時(shí)，走過(guò)的二進(jìn)制字符串即譯為 該葉子結(jié)點(diǎn)對(duì)應(yīng)的對(duì)象。然后循 環(huán)掃描總編碼后的字符串。 80 6.7二叉樹的應(yīng)用（續(xù)） 哈夫曼編碼與譯碼 利用哈夫曼算法可以得到總 碼長(zhǎng)最短的二進(jìn)制前綴編碼，即 為哈夫曼編碼。 設(shè)某次編碼應(yīng)用中不同被編 碼對(duì)象有n種，以此n種被編碼對(duì) 象出現(xiàn)的頻率作權(quán)，構(gòu)造出的哈 夫曼樹即為這n種對(duì)象的編碼樹， 由此可得到其二進(jìn)制的前綴編碼。 假定用于通訊的電文如下， 現(xiàn)在要對(duì)其編碼，采用哈夫曼編 碼。寫出編碼后的二進(jìn)制串。 電文：castc

38、atssatatatasa c(110) a(0) s(111) t(10) Set = c,a,s,t W =2,7,4,5 電文編碼： 11001111011001011111101001001001110 5 18 7 11 6 42 0 0 0 1 1 1 cs a t 81 4.數(shù)組 5.廣義表 6.樹和二叉樹 7.圖 教學(xué)內(nèi)容-第七章 82 ADT Graph 數(shù)據(jù)對(duì)象：V=具有相同性質(zhì)的數(shù)據(jù)元素 數(shù)據(jù)關(guān)系：R: R=VR VR = | v,w屬于V且P(v,w), 是從v到w的一 條弧，謂詞P(v,w)定義了弧 的意義或信息 基本操作：P: CreateGraph( DFSTra

39、verseGraph(G,v,Visit(); ; BFSTraverseGraph(G,v,Visit() ADT Graph 7.1圖的邏輯結(jié)構(gòu) 圖的抽象數(shù)據(jù)類型 83 7.1圖的邏輯結(jié)構(gòu)（續(xù)） 基本概念和術(shù)語(yǔ) 頂點(diǎn)(Vertex)、弧(Arc)、有向圖(Digraph)、邊(Edge)、無(wú)向 圖(Undigraph)、完全圖(Completed graph)、有向完全圖、稀疏 圖(Sparse graph)、權(quán)(Weight)、網(wǎng)(Network)、子圖(Subgraph)、 鄰接點(diǎn)(Adjacent)、（頂點(diǎn)的）度(Degree)、 （頂點(diǎn)的）入度 (InDegree)、（頂點(diǎn)的）出度

40、(OutDegree)、（頂點(diǎn)之間）路徑 (Path)、（頂點(diǎn)之間）路徑長(zhǎng)度、回路或環(huán)(Cycle)、簡(jiǎn)單路 徑、簡(jiǎn)單回路（簡(jiǎn)單環(huán)）、 （頂點(diǎn)之間）連通、連通圖 (Connected Graph)、連通分量(Connected Component)、 強(qiáng)連通圖、強(qiáng)連通分量、（連通圖的）生成樹：（有向圖的） 生成森林 84 0 1 0 1 0 1 0 1 0 1 G1.arcs = 0 1 0 1 1 1 0 1 0 0 0 1 1 0 0 7.2樹的存儲(chǔ)結(jié)構(gòu)（續(xù)） 數(shù)組表示法 V3 V1V2 V5V4 G1 V1V2 V4V3 G2 0 1 1 0 0 0 0 0 G2.arcs = 1 0

41、0 1 1 1 1 0 85 7.2圖的存儲(chǔ)結(jié)構(gòu)（續(xù)） 鄰接表-圖的鏈?zhǔn)酱鎯?chǔ) 基本思路： 對(duì)圖中每個(gè)頂點(diǎn)建立一個(gè)單鏈表，第i個(gè)單鏈表中的結(jié)點(diǎn)表示依 附于頂點(diǎn)vi的邊（對(duì)有向圖是以頂點(diǎn)vi為尾的?。?。每個(gè)表結(jié)點(diǎn)由三 個(gè)域組成：鄰接點(diǎn)域(adjvex)指示與頂點(diǎn)vi鄰接的點(diǎn)在圖中的位置； 鏈域(nextarc)指示下一條邊或弧的結(jié)點(diǎn)；數(shù)據(jù)域(info)存儲(chǔ)和邊或弧 相關(guān)的信息。頭結(jié)點(diǎn)由兩個(gè)域組成：鏈域(firstarc)指向鏈表中第一個(gè) 結(jié)點(diǎn)；數(shù)據(jù)域(data)存儲(chǔ)頂點(diǎn)vi信息。 頭結(jié)點(diǎn)以順序結(jié)構(gòu)形式存取，以便隨機(jī)訪問(wèn)任一頂點(diǎn)的鏈表。 Adjvexnextarcinfodatafirstarc 表

42、結(jié)點(diǎn)頭結(jié)點(diǎn) 86 7.2圖的存儲(chǔ)結(jié)構(gòu)（續(xù)） V10 V21 V32 V43 V54 21 20 420 31 431 V3 V1V2 V5V4 G1 V1V2 V4V3 G2 V10 V32 V21 V43 30 0 32 30 V10 V2 1 V32 V43 30 2 21 20 87 7.2圖的存儲(chǔ)結(jié)構(gòu)（續(xù)） 鄰接表-圖的鏈?zhǔn)酱鎯?chǔ) 鄰接表的優(yōu)點(diǎn)： 邊（或?。┫∈钑r(shí)，節(jié)省空間； 和邊（或?。┫嚓P(guān)的信息較多時(shí)，節(jié)省空間； 容易求得當(dāng)前頂點(diǎn)的第一個(gè)鄰接點(diǎn)、下一個(gè)鄰接點(diǎn)。 對(duì)有向圖，也可建立逆向鄰接表，即對(duì)每個(gè)頂點(diǎn) 建立一個(gè)鏈接以該頂點(diǎn)為頭的弧的表。 88 7.3圖的遍歷 遍歷圖 在圖中查找具有

43、某種特征的結(jié)點(diǎn) 需要對(duì)結(jié)點(diǎn)進(jìn)行訪問(wèn)（處理、輸出等）操作 圖的遍歷算法是求解圖的連通性問(wèn)題、拓?fù)渑判蚝?求關(guān)鍵路徑等算法的基礎(chǔ) 圖的遍歷(Traversing Graph)：從圖的某一個(gè)頂點(diǎn)出發(fā)， 按照某條路徑訪問(wèn)每個(gè)結(jié)點(diǎn),使得每個(gè)結(jié)點(diǎn)均被訪問(wèn)一 次，而且僅被訪問(wèn)一次。 遍歷本質(zhì)：結(jié)點(diǎn)之間非線性關(guān)系線性化的過(guò)程 遍歷思路： *深度優(yōu)先：類似于樹的先根遍歷； *廣度優(yōu)先：類似于樹的層次遍歷。 89 7.3圖的遍歷（續(xù)） 深度優(yōu)先搜索 遍歷思路： 從圖的某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次從v的未被訪問(wèn)的 鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都 被訪問(wèn)到；若此時(shí)圖中尚有頂點(diǎn)未被

44、訪問(wèn)，則另選圖中一個(gè)未曾被訪 問(wèn)的頂點(diǎn)作為始點(diǎn)，重復(fù)上述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為 止。 這是一個(gè)遞歸算法，遍歷過(guò)程中，當(dāng)某個(gè)頂點(diǎn)的所有鄰接點(diǎn)都被 訪問(wèn)到后，需要“回朔”，即沿著調(diào)用的逆方向回退到上一層頂點(diǎn)， 繼續(xù)考察該頂點(diǎn)的下一個(gè)鄰接點(diǎn)。 Boolean visitedMAX;/訪問(wèn)標(biāo)志數(shù)組 Status (*VisitFunc) (int v);/函數(shù)變量 Void DFSTraverse(Graph G,Status (*Visit)(int v) VisitFunc = Visit； /使用全局變量VisitFunc，使DFS不必設(shè)函數(shù)指針參數(shù) for (v =0; vG.ve

45、xnum; +v) visitedv = FALSE; /標(biāo)志數(shù)組初始化 for (v =0; vG.vexnum; +v) if (!visitedv) DFS(G,v); Status DFS (Graph G, int v) /從第v個(gè)頂點(diǎn)出發(fā)遞歸地深度優(yōu)先遍歷圖G，對(duì)每個(gè)元素調(diào)用函數(shù)Visit visitedv = TRUE;VisitFunc(v); /訪問(wèn)第v個(gè)頂點(diǎn) for ( w =FirstAdjVex(G,v); w; w =NextAdjVex(G,v,w) if (!visitedw) DFS(G,w); / 算法時(shí)間復(fù)雜度與存儲(chǔ)結(jié)構(gòu)相關(guān) 鄰接矩陣存儲(chǔ):T(n)=O(n2

46、); 鄰接表存儲(chǔ):T(n)=O(n+e) 90 7.3圖的遍歷（續(xù)） 深度優(yōu)先搜索 V12 V9V10 V11 V1 G3 V3 V6 V2 V8 V5V4V7 一種DFS遍歷序列： V1 , V2 , V4 , V8 , V5 , V3 , V6 , V7 , V9 , V10 , V12 , V11 當(dāng)存儲(chǔ)結(jié)構(gòu)和算法確定后，遍歷序列唯一。 91 7.3圖的遍歷（續(xù)） 廣度優(yōu)先搜索 遍歷思路： 從圖的某個(gè)頂點(diǎn)v出發(fā)，訪問(wèn)此頂點(diǎn)，然后依次訪問(wèn)v的未被訪問(wèn) 的鄰接點(diǎn)，然后從這些鄰接點(diǎn)出發(fā)依次訪問(wèn)它們的鄰接點(diǎn)，并使“先 被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)， 直至圖中所有已被

47、訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)都被訪問(wèn)到；若此時(shí)圖中尚有 頂點(diǎn)未被訪問(wèn)，則另選圖中一個(gè)未曾被訪問(wèn)的頂點(diǎn)作為始點(diǎn)，重復(fù)上 述過(guò)程，直至圖中所有頂點(diǎn)都被訪問(wèn)到為止。 一層層遍歷。如何保證上層次序先于下層次序？保證“先被訪問(wèn) 的頂點(diǎn)的鄰接點(diǎn)”先于“后被訪問(wèn)的頂點(diǎn)的鄰接點(diǎn)”被訪問(wèn)？可以通 過(guò)隊(duì)列來(lái)控制實(shí)現(xiàn)。 Boolean visitedMAX;/訪問(wèn)標(biāo)志數(shù)組 Void BFSTraverse(Graph G,Status (*Visit)(int v) for (v =0; vG.vexnum; +v) visitedv = FALSE; /標(biāo)志數(shù)組初始化 InitQueue(Q);/置空的輔助隊(duì)列 for (

48、v =0; vG.vexnum; +v) if (!visitedv) visitedv = TRUE;Visit (v); EnQueue(Q,u); While(!QueueEmpty(Q) DeQueue(Q,u); for ( w =FirstAdjVex(G,u); w; w =NextAdjVex(G,u,w) if (!visitedw) Visitedw =TRUE; Visit(w); Enqueue(Q,w); /while if / 算法時(shí)間復(fù)雜度與存儲(chǔ)結(jié)構(gòu)相關(guān) 鄰接矩陣存儲(chǔ):T(n)=O(n2); 鄰接表存儲(chǔ):T(n)=O(n+e) 92 7.3圖的遍歷（續(xù)） 廣度優(yōu)先

49、搜索 V12 V9V10 V11 V1 G3 V3 V6 V2 V8 V5V4V7 一種BFS遍歷序列： V1 , V2 , V3 , V4 , V5 , V6 , V7 , V8 , V9 , V10 , V12 , V11 當(dāng)存儲(chǔ)結(jié)構(gòu)和算法確定后，遍歷序列唯一。 93 7.4圖的應(yīng)用 無(wú)向圖的連通分量 無(wú)向圖的生成樹 連通網(wǎng)的最小生成樹 有向無(wú)環(huán)圖的拓?fù)渑判?有向無(wú)環(huán)圖的關(guān)鍵路徑 有向網(wǎng)的最短路徑 典型應(yīng)用 94 7.4圖的應(yīng)用（續(xù)） 無(wú)向圖的連通分量 思路：利用遍歷圖的算法求解無(wú)向圖的連通性。 方法：利用圖的遍歷（DFS與BFS均可）算法，對(duì)連通圖， 從任一定點(diǎn)出發(fā)遍歷，可訪問(wèn)到所有頂點(diǎn)

50、；對(duì)非連通圖， 需從多個(gè)頂點(diǎn)出發(fā)進(jìn)行遍歷，每一次從一個(gè)新的起始點(diǎn)出 發(fā)遍歷得到的頂點(diǎn)序列恰為其各個(gè)連通分量中的頂點(diǎn)集。 最終求得一個(gè)無(wú)向圖的所有連通分量。 95 7.4圖的應(yīng)用（續(xù)） 無(wú)向圖的生成樹 思路： 利用遍歷圖的算法求解無(wú)向連通圖的生成樹和無(wú)向非連通圖的生成 森林。 方法： 對(duì)連通圖G，設(shè)E(G)為連通圖G中所有邊的集合，則從圖中任一頂 點(diǎn)出發(fā)遍歷圖時(shí)，必將E(G)分為兩個(gè)集合T(G)和B(G)，其中T(G)是遍 歷圖過(guò)程中歷經(jīng)邊的集合；B(G)是剩余邊的集合。T(G)和圖G中所有 頂點(diǎn)一起構(gòu)成連通圖G的極小連通子圖，它是連通圖的一棵生成樹。 根據(jù)遍歷方法，生成樹分為DFS生成樹和BF

51、S生成樹。 對(duì)無(wú)向非連通圖，每個(gè)連通分量對(duì)應(yīng)一個(gè)生成樹，形成生成森林。 V12 V9V10 V11 V1 G3 V3 V6 V2 V8 V5V4V7 96 V12 V9V10 V11 V1 G3 V3 V6 V2 V8 V5V4V7 7.4圖的應(yīng)用（續(xù)） 無(wú)向圖的生成樹 97 7.4圖的應(yīng)用（續(xù)） 連通網(wǎng)的最小生成樹 問(wèn)題： 用連通網(wǎng)表示的網(wǎng)絡(luò)上如何構(gòu)造代價(jià)最小的通信網(wǎng)。 對(duì)于n個(gè)頂點(diǎn)的連通網(wǎng)可以建立許多不同的生成樹，每一棵生成樹 都是一個(gè)通信網(wǎng)。一個(gè)生成樹的代價(jià)就是樹上各邊的代價(jià)之和，表示 著通信網(wǎng)上總通信耗費(fèi)量。使通信網(wǎng)上總通信耗費(fèi)量最小的問(wèn)題就是 求解最小生成樹的問(wèn)題，即如何構(gòu)造連通網(wǎng)的

52、最小代價(jià)生成樹 思路： 利用最小生成樹的MST性質(zhì)。 方法： *普里姆(prim)算法； *克魯斯卡爾(kruskal)算法。 最小生成樹的MST性質(zhì)： 假設(shè)N = (V,E)是 一個(gè)連通網(wǎng)，U是頂點(diǎn) 集V的一個(gè)非空子集。 若(u,v)是一條具有最小 權(quán)值（代價(jià)）的邊，其 中u屬于U,v屬于V-U， 則必存在一棵包含邊 (u,v)的最小生成樹。 證明: （反證法） 假設(shè)N = (V,E)的任何一棵最小生 成樹都不含邊(u,v) 。設(shè)T是連通網(wǎng)上的一 棵最小樹，當(dāng)將邊(u,v) 加入到T中時(shí)，由 生成樹的定義，T中必存在一條包含(u,v) 的回路。另一方面，由于T是生成樹，則 在T上必存在另一條

53、邊(u,v) ，其中u屬 于U,v屬于V-U，且u和u，v和v之間均 有路徑相通。刪去邊(u,v)，便可消除上 述回路，同時(shí)得到另一棵生成樹T。因 為(u,v)的代價(jià)不高于(u,v)，則T的代價(jià) 亦不高于T，T是一棵包含(u,v)的最小生 成樹。矛盾! 98 7.4圖的應(yīng)用（續(xù)） 連通網(wǎng)的最小生成樹-prim算法 輸入：連通網(wǎng)N = (V, E)，最小生成樹邊的集合TE =空集 輸出：一棵最小生成樹T = (V, TE) 步驟： step1.初始：U =u0(u0屬于V),TE = ； step2.在所有u屬于U，v屬于V U的邊(u,v)中找一條代價(jià)最小的 邊(u0, v0 )并入集合TE，

54、同時(shí)v0 并入U(xiǎn)； step3.重復(fù)step2，直至 U = V為止 最后TE中有n-1條邊， T = (V, TE)即為N的一棵最小生成樹。 效率： T(n) = O(n2)，與e無(wú)關(guān)（其中n為網(wǎng)中結(jié)點(diǎn)個(gè)數(shù)， e為邊的個(gè)數(shù)） 99 7.4圖的應(yīng)用（續(xù)） 連通網(wǎng)的最小生成樹-prim算法 V1 6 V4 V6 V2 V5 V3 6 3 55 1 5 64 2 U =v1 , V-U=v2, v3, v4, v5, v6, TE= U =v1, v3 , V-U=v2, v4, v5, v6, TE= (v1, v3) U =v1, v3 ,v6 , V-U=v2, v4, v5, TE= (v

55、1, v3 ), (v3, v6 ) U =v1, v3 ,v6 , v4 , V-U=v2, v5, TE= (v1, v3 ), (v3, v6 ) , (v4, v6 ) U =v1, v3 ,v6 , v4 , v2 , V-U=v5, TE= (v1, v3 ), (v3, v6 ) , (v4, v6 ) , (v2, v3 ) U =v1, v3 ,v6 , v4 , v2 , v5 , V-U=, TE = (v1, v3 ),(v3, v6 ),(v4, v6 ),(v2, v3 ),(v2, v5 ) 100 7.4圖的應(yīng)用（續(xù)） 連通網(wǎng)的最小生成樹-kruskal算法 輸

56、入：連通網(wǎng)N = (V, E)，最小生成樹邊的集合TE =空集 輸出：一棵最小生成樹T = (V, TE) 步驟： step1.初始：只有n個(gè)頂點(diǎn)而無(wú)邊的非連通圖T = (V,TE=)； step2.在E中選擇代價(jià)最小的邊，若該邊依附的頂點(diǎn)落在T中不同 的連通分量上，則將此邊加入到T的TE集合中，否則舍去此 邊而選擇下一條代價(jià)最小的邊； step3.重復(fù)step2，直至 T中所有頂點(diǎn)都在同一個(gè)連通分量上為止 效率： T(n) = O(eloge)，與n無(wú)關(guān)（其中n為網(wǎng)中結(jié)點(diǎn)個(gè)數(shù)， e為邊的個(gè)數(shù)） 101 7.4圖的應(yīng)用（續(xù)） 連通網(wǎng)的最小生成樹-kruskal算法 V1 6 V4 V6 V2

57、V5 V3 6 3 55 1 5 64 2 V =v1,v2, v3, v4, v5, v6, TE= V =v1,v2, v3, v4, v5, v6, TE= (v1, v3) V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) , (v2, v5 ) V =v1,v2, v3, v4, v5, v6, TE= (v1, v3 ), (v4, v6 ) , (v2, v5 ) , (v3, v6 ) V =v1,v2, v3, v4, v5

58、, v6, TE = (v1, v3 ),(v3, v6 ),(v4, v6 ),(v2, v3 ),(v2, v5 ) 102 7.4圖的應(yīng)用（續(xù)） 有向無(wú)環(huán)圖(DAG)：一個(gè)無(wú)環(huán)的有向圖。其作用： *描述含有公共子式的表達(dá)式 *描述一項(xiàng)工程或系統(tǒng)的進(jìn)行過(guò)程 #工程能否順利進(jìn)行； #工程完成所必需的最短時(shí)間 拓?fù)渑判?Topological Sort) ：由某個(gè)集合上的一個(gè)偏序得到 該集合上的一個(gè)全序的操作。這個(gè)全序稱為拓?fù)溆行?(Topological Order)。 AOV-網(wǎng)：用頂點(diǎn)表示活動(dòng)，用弧表示活動(dòng)間的優(yōu)先關(guān)系的有 向圖稱為頂點(diǎn)表示活動(dòng)的圖(Activity On Vertex

59、Network)。 AOE-網(wǎng)：頂點(diǎn)表示事件，弧表示活動(dòng)，權(quán)表示活動(dòng)持續(xù)時(shí)間 的帶權(quán)有向無(wú)環(huán)圖稱為邊表示活動(dòng)的網(wǎng)(Activity On Edge ) 有向無(wú)環(huán)圖中基本概念 103 7.4圖的應(yīng)用（續(xù)） 為了工程能進(jìn)行，其對(duì)應(yīng)的AOV-網(wǎng)中不應(yīng) 該存在環(huán)。檢測(cè)的辦法有： *DFS遍歷：從有向圖某個(gè)頂點(diǎn)v出發(fā)，在遍歷結(jié) 束之前如果出現(xiàn)從頂點(diǎn)u到頂點(diǎn)v的回邊，由于u 在生成樹上是v的子孫，則有向圖中必定存在包 含頂點(diǎn)v和u的環(huán)。 *拓?fù)渑判颍簩?duì)有向圖構(gòu)造其頂點(diǎn)的拓?fù)溆行蛐?列，若網(wǎng)中所有頂點(diǎn)都在它的拓?fù)溆行蛐蛄兄校?則該AOV-網(wǎng)中必定不存在環(huán)。 有向無(wú)環(huán)圖的拓?fù)渑判?104 7.4圖的應(yīng)用（續(xù)）

60、 有向無(wú)環(huán)圖的拓?fù)渑判蛩惴?輸入：AOV-網(wǎng) 輸出：包含全部頂點(diǎn)的一個(gè)拓?fù)湫蛄谢蛘卟糠猪旤c(diǎn)的序列（存在環(huán)） 步驟： step1.在圖中選取一個(gè)沒(méi)有前驅(qū)的頂點(diǎn)且輸出之； step2.在圖中刪除該頂點(diǎn)和所有以它為尾的弧； step3.重復(fù)step1、step2，直至 全部頂點(diǎn)均已輸出，或者當(dāng)前圖中 不存在無(wú)前驅(qū)的頂點(diǎn)為止（存在環(huán)）。 邏輯上：拓?fù)湫蛄胁晃ㄒ唬?物理上：拓?fù)湫蛄形ㄒ?105 7.4圖的應(yīng)用（續(xù)） 有向無(wú)環(huán)圖的拓?fù)渑判蛩惴?V1V2 V3 V4 V5V6 V10 V32 V2 1 V43 4 12 14 V5 4 V65 3 34 V1V2 V3 V4 V5 V3 V4 V5 V2 V