經(jīng)貿(mào)大學(xué)2016年數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)

1、數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)總復(fù)習(xí)第一章 緒論n重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容p 邏輯結(jié)構(gòu)和物理結(jié)構(gòu)邏輯結(jié)構(gòu)和物理結(jié)構(gòu)p 順序存儲和鏈?zhǔn)酱鎯樞虼鎯玩準(zhǔn)酱鎯 算法的五個(gè)特性算法的五個(gè)特性p 算法的時(shí)間復(fù)雜度算法的時(shí)間復(fù)雜度p 邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。邏輯結(jié)構(gòu)：數(shù)據(jù)元素之間的邏輯關(guān)系。p 物理結(jié)構(gòu)（存儲結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表物理結(jié)構(gòu)（存儲結(jié)構(gòu)）：數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示，包括數(shù)據(jù)元素的表示和關(guān)系的表示。示，包括數(shù)據(jù)元素的表示和關(guān)系的表示。3 順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu)：用數(shù)據(jù)元素在存儲器中用數(shù)據(jù)元素在存儲器中的的相對位置相對位置來表示數(shù)據(jù)元素之間的邏輯來表示數(shù)據(jù)元素之間的邏輯結(jié)構(gòu)結(jié)構(gòu)( (關(guān)系關(guān)系) )

2、。數(shù)據(jù)元素存放的地址是連數(shù)據(jù)元素存放的地址是連續(xù)的續(xù)的 鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址鏈?zhǔn)酱鎯Y(jié)構(gòu)：借助指示元素存儲地址得指針表示數(shù)據(jù)之間的邏輯關(guān)系。得指針表示數(shù)據(jù)之間的邏輯關(guān)系。數(shù)據(jù)數(shù)據(jù)元素存放的地址是否連續(xù)沒有要求元素存放的地址是否連續(xù)沒有要求45 順序存儲順序存儲以存儲位置的相鄰表示后繼關(guān)系y的存儲位置和x的存儲位置之間差一個(gè)常量C 鏈?zhǔn)酱鎯︽準(zhǔn)酱鎯σ愿郊有畔?指針)表示后記關(guān)系，需要用一個(gè)和x在一起的附加信息指示y的存儲位置x yyxp算法是為了解決某類問題而給出的一個(gè)有限長的算法是為了解決某類問題而給出的一個(gè)有限長的指指令序列令序列。p 算法有以下算法有以下5個(gè)特性：個(gè)特性：n有

3、窮性：有窮步驟，每步都有有窮的時(shí)間有窮性：有窮步驟，每步都有有窮的時(shí)間n確定性：每條指令有確定的含義確定性：每條指令有確定的含義n可行性：是能行的，基本運(yùn)算的有限次運(yùn)算完成可行性：是能行的，基本運(yùn)算的有限次運(yùn)算完成n輸入：輸入：0 0個(gè)或多個(gè)輸入，取自某個(gè)特定對象集合個(gè)或多個(gè)輸入，取自某個(gè)特定對象集合n輸出：一個(gè)或多個(gè)輸出，同輸入有某些特定關(guān)系輸出：一個(gè)或多個(gè)輸出，同輸入有某些特定關(guān)系6一個(gè)一個(gè)“好好”的算法需滿足：的算法需滿足：7程序程序中不含語法錯(cuò)誤；中不含語法錯(cuò)誤；程序?qū)τ趲捉M給定的輸入可得到滿足要求的結(jié)果程序?qū)τ趲捉M給定的輸入可得到滿足要求的結(jié)果程序?qū)τ诰奶暨x的、典型的輸入也可得到滿

4、足程序?qū)τ诰奶暨x的、典型的輸入也可得到滿足要求的結(jié)果要求的結(jié)果程序?qū)τ谝磺泻戏ǖ妮斎刖梢缘贸鰸M足要求的程序?qū)τ谝磺泻戏ǖ妮斎刖梢缘贸鰸M足要求的結(jié)果結(jié)果8算法主要是為算法主要是為了人的閱讀與交流了人的閱讀與交流，其次才是為計(jì)算機(jī)執(zhí)其次才是為計(jì)算機(jī)執(zhí)行行。因此算法應(yīng)該易于人的因此算法應(yīng)該易于人的理解理解；另另一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而一方面，晦澀難讀的程序易于隱藏較多錯(cuò)誤而難以調(diào)試和修改。難以調(diào)試和修改。9當(dāng)當(dāng)輸入輸入的數(shù)據(jù)非法的數(shù)據(jù)非法時(shí)，算法應(yīng)當(dāng)給予時(shí)，算法應(yīng)當(dāng)給予恰當(dāng)?shù)姆磻?yīng)恰當(dāng)?shù)姆磻?yīng)或進(jìn)行相應(yīng)的處理或進(jìn)行相應(yīng)的處理，而不是產(chǎn)生系統(tǒng)錯(cuò)誤或莫名，而不是產(chǎn)生系統(tǒng)錯(cuò)誤或莫名其妙的

5、結(jié)果其妙的結(jié)果。 處理出錯(cuò)處理出錯(cuò)的方法不應(yīng)是中斷程序的執(zhí)行，的方法不應(yīng)是中斷程序的執(zhí)行，而應(yīng)而應(yīng)該返回錯(cuò)誤提示該返回錯(cuò)誤提示，以便在更高抽象層次上進(jìn)行處，以便在更高抽象層次上進(jìn)行處理理。10假設(shè)，隨著問題規(guī)模假設(shè)，隨著問題規(guī)模n的增長，算法執(zhí)行時(shí)的增長，算法執(zhí)行時(shí)間的增長率和間的增長率和f(n)的增長率相同，則可記作：的增長率相同，則可記作： T(n)=O(f(n)稱稱T(n)為算為算法的（漸進(jìn)）時(shí)間復(fù)雜度法的（漸進(jìn)）時(shí)間復(fù)雜度11原操作原操作：固有數(shù)據(jù)類型的操作。固有數(shù)據(jù)類型的操作。（如：（如：+，-，/，nextn 因此，因此，鏈表不是隨機(jī)存取結(jié)構(gòu)鏈表不是隨機(jī)存取結(jié)構(gòu)n 設(shè)單鏈表的長度為

6、設(shè)單鏈表的長度為n，要查找表中第，要查找表中第i個(gè)結(jié)點(diǎn)，個(gè)結(jié)點(diǎn)，僅當(dāng)僅當(dāng)1in時(shí)，時(shí)，i的值是合法的的值是合法的單鏈表的插入實(shí)現(xiàn)步驟實(shí)現(xiàn)步驟：n 首先，找到首先，找到ai-1所在所在的結(jié)點(diǎn)的結(jié)點(diǎn)pn 然后，生成一個(gè)數(shù)據(jù)域?yàn)槿缓?，生成一個(gè)數(shù)據(jù)域?yàn)閑的新結(jié)點(diǎn)的新結(jié)點(diǎn)s，n s結(jié)點(diǎn)作為結(jié)點(diǎn)作為p的直接后繼結(jié)點(diǎn)，作為的直接后繼結(jié)點(diǎn)，作為ai結(jié)點(diǎn)的直結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)。接前驅(qū)結(jié)點(diǎn)。bpabpaes s-data=e;s-next=p-next; p-next=s;單鏈表的刪除實(shí)現(xiàn)步驟實(shí)現(xiàn)步驟：n 首先找到首先找到ai-1的位置的位置p；n 然后令然后令pnext指向指向ai的直接后繼結(jié)點(diǎn)，即把的直接后繼

7、結(jié)點(diǎn)，即把a(bǔ)i從鏈上摘下從鏈上摘下n 最后釋放結(jié)點(diǎn)最后釋放結(jié)點(diǎn)ai的空間的空間aipai-1ai+1 q=p-next;p-next=q-next; e=q-data; free(q);靜態(tài)鏈表011ZHAO22QIAN33SUN44LI55ZHOU66WU77ZHENG88WANG0910011ZHAO22QIAN33SUN44LI95ZHOU66WU77ZHENG88WANG09SHI510011ZHAO22QIAN33SUN44LI95ZHOU66WU87ZHENG88WANG09SHI510修改前修改前在第在第5個(gè)位置個(gè)位置插入插入SHI刪除刪除ZHENG循環(huán)鏈表n 循環(huán)鏈表循環(huán)鏈表(

8、Circular Linked List)：是一種頭尾相：是一種頭尾相接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向接的鏈表。其特點(diǎn)是最后一個(gè)結(jié)點(diǎn)的指針域指向鏈表的頭結(jié)點(diǎn)，鏈表的頭結(jié)點(diǎn)，整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)整個(gè)鏈表的指針域鏈接成一個(gè)環(huán)。n 從循環(huán)鏈表的從循環(huán)鏈表的任意一個(gè)結(jié)點(diǎn)出發(fā)任意一個(gè)結(jié)點(diǎn)出發(fā)都可以找到鏈表都可以找到鏈表中的其它結(jié)點(diǎn)，使得表處理更加方便靈活。中的其它結(jié)點(diǎn)，使得表處理更加方便靈活?？毡砜毡矸强毡矸强毡韆1 a2 anhead head 雙向鏈表的插入SepabSepab雙向鏈表的插入雙向鏈表的插入n 算法主要語句算法主要語句 S=(DulNode *)malloc(size

9、of(DulNode);S-data=e;S-prior=p-prior; p-prior-next=S;S-next=p; p-prior=S; n 設(shè)要?jiǎng)h除設(shè)要?jiǎng)h除的結(jié)點(diǎn)為的結(jié)點(diǎn)為p ，刪除時(shí)直接先斷鏈，刪除時(shí)直接先斷鏈，再，再釋放結(jié)點(diǎn)。部分語句組如下：釋放結(jié)點(diǎn)。部分語句組如下：p-prior-next=p-next;p-next-prior=p-prior;free(p);與單鏈與單鏈表的插入和刪除操作不同的是，在表的插入和刪除操作不同的是，在雙向鏈表中雙向鏈表中插入插入和和刪除刪除必須同時(shí)必須同時(shí)修改兩個(gè)方向上修改兩個(gè)方向上的指針域的指向的指針域的指向。雙向鏈表的刪除a1a2a3p優(yōu)點(diǎn)

10、優(yōu)點(diǎn)：易于查詢，索引快：易于查詢，索引快 缺點(diǎn)缺點(diǎn)：擴(kuò)展性弱，不易刪除、添加。：擴(kuò)展性弱，不易刪除、添加。優(yōu)點(diǎn)優(yōu)點(diǎn)：擴(kuò)展性強(qiáng)，易于刪除、添加：擴(kuò)展性強(qiáng)，易于刪除、添加缺點(diǎn)缺點(diǎn)：不易于查詢，索引慢：不易于查詢，索引慢二者優(yōu)缺點(diǎn)正好是互補(bǔ)關(guān)系，根據(jù)實(shí)際情況選擇使二者優(yōu)缺點(diǎn)正好是互補(bǔ)關(guān)系，根據(jù)實(shí)際情況選擇使用用順序存儲與鏈?zhǔn)酱鎯Φ膶Ρ鹊谌?棧和隊(duì)列n重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容p 棧和隊(duì)列邏輯結(jié)構(gòu)的特點(diǎn)棧和隊(duì)列邏輯結(jié)構(gòu)的特點(diǎn)p 順序棧的棧滿、?？张袛囗樞驐５臈M、?？张袛鄍 循環(huán)隊(duì)列的滿與空的判斷循環(huán)隊(duì)列的滿與空的判斷p 壓棧、出棧算法壓棧、出棧算法p 進(jìn)隊(duì)列、出隊(duì)列算法進(jìn)隊(duì)列、出隊(duì)列算法n 棧棧(Stack

11、)：限制在表尾進(jìn)行插入：限制在表尾進(jìn)行插入和刪除操作的線性表。又稱為后和刪除操作的線性表。又稱為后進(jìn)先出進(jìn)先出LIFO (Last In First Out)n 棧頂棧頂(Top)：允許進(jìn)行插入、刪：允許進(jìn)行插入、刪除操作的一端除操作的一端 n 棧底棧底(Bottom)：是固定端，又稱：是固定端，又稱為表頭。為表頭。n 空?？諚＃簍op=basen 滿棧滿棧: topmaxsize+1a1a2an棧頂棧頂棧底棧底進(jìn)棧進(jìn)棧(Push)出棧出棧(Pop) 采用一組地址連續(xù)的存儲單元依次存放自棧底到采用一組地址連續(xù)的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素：棧頂?shù)臄?shù)據(jù)元素：n 用base表示棧底指針，

12、棧底固定不變的；棧頂則隨著進(jìn)棧和退棧操作而變化。n 用top(稱為棧頂指針)指示當(dāng)前棧頂位置。n 用top=base作為?？盏臉?biāo)記，每次top指向棧頂數(shù)組中的下一個(gè)存儲位置。n 結(jié)點(diǎn)進(jìn)棧：首先將數(shù)據(jù)元素保存到棧頂(top所指的當(dāng)前位置)，然后執(zhí)行top加1，使top指向棧頂?shù)南乱粋€(gè)存儲位置;n 結(jié)點(diǎn)出棧：首先執(zhí)行top減1，使top指向棧頂元素的存儲位置，然后將棧頂元素取出。空?？諚?bottomtop元素元素a進(jìn)棧進(jìn)棧bottomtopa元素元素b，c進(jìn)棧進(jìn)棧bottomtopabc元素元素c退棧退棧bottomtopabbottomtopabdef元素元素d，e，f進(jìn)棧進(jìn)棧3 元素進(jìn)棧元素

13、進(jìn)棧Status push(SqStack S , ElemType e) /* 使數(shù)據(jù)元素使數(shù)據(jù)元素e進(jìn)棧成為新的棧頂進(jìn)棧成為新的棧頂 */if (S.top - S.base = S.stacksize) /棧滿棧滿 S.base=(SElemType *) realloc (S.base, (S.stacksize+STACKINCREMENT) * sizeof(SElemType); if (!S.base) exit (OVERFLOW); S.top=S.base+S.stacksize; S.stacksize+=STACKINCREMENT; *S.top+=e ; /* 棧

14、頂指針加棧頂指針加1 */return OK; /* 壓棧成功壓棧成功 */4 彈棧彈棧( (元素元素出棧出棧) )Status pop( SqStack &S, SElemType &e ) /*彈出棧頂元素彈出棧頂元素*/ if ( S.top=S.base)return ERROR ; /* ?？?，返回錯(cuò)誤標(biāo)志?？眨祷劐e(cuò)誤標(biāo)志 */e=*-S.top;return OK ; n 隊(duì)列隊(duì)列 (Queue)：也是運(yùn)算受限的線性表。是：也是運(yùn)算受限的線性表。是一種先一種先進(jìn)先出進(jìn)先出(First In First Out ，簡稱，簡稱FIFO)的線性表。的線性表。n 只允許在

15、表的一端進(jìn)行插入，而在另一端進(jìn)行刪只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除除n 隊(duì)頭隊(duì)頭 (front) ：允許進(jìn)行刪除的一端稱為隊(duì)頭。：允許進(jìn)行刪除的一端稱為隊(duì)頭。 n 隊(duì)尾隊(duì)尾 (rear) ：允許進(jìn)行插入的一端稱為隊(duì)尾。：允許進(jìn)行插入的一端稱為隊(duì)尾。a1 , a2 , , an出隊(duì)出隊(duì)入隊(duì)入隊(duì)隊(duì)尾隊(duì)尾隊(duì)頭隊(duì)頭 n 隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊(duì)列隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)簡稱為鏈隊(duì)列n 它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行它是限制僅在表頭進(jìn)行刪除操作和表尾進(jìn)行插入操作的單鏈表。插入操作的單鏈表。n 需要兩類不同的結(jié)點(diǎn)：需要兩類不同的結(jié)點(diǎn)：數(shù)據(jù)元素?cái)?shù)據(jù)元素結(jié)點(diǎn)，隊(duì)列結(jié)點(diǎn)，隊(duì)列的的隊(duì)首指針和隊(duì)尾

16、指針隊(duì)首指針和隊(duì)尾指針的結(jié)點(diǎn)的結(jié)點(diǎn)datafront rear(a) 空隊(duì)列空隊(duì)列front rear(b) x入隊(duì)入隊(duì) x front rear(c) y再入隊(duì)再入隊(duì) y front rear x(d) x出隊(duì)出隊(duì) y xfront rear設(shè)立一個(gè)隊(duì)首指針設(shè)立一個(gè)隊(duì)首指針front ，一個(gè)隊(duì)尾指針，一個(gè)隊(duì)尾指針rear ，分，分別指向隊(duì)首和隊(duì)尾元素別指向隊(duì)首和隊(duì)尾元素。 初始化初始化：front=rear=0。 入隊(duì)入隊(duì)：將新元素插入將新元素插入rear所指的位置，然后所指的位置，然后rear加加1。 出隊(duì)出隊(duì)：刪去刪去front所指的元素，然后加所指的元素，然后加1并返回被刪元并返回被刪

17、元素。素。 隊(duì)列為空隊(duì)列為空：front=rear。 隊(duì)滿隊(duì)滿：rear=MAX_QUEUE_SIZE-1(a) 空隊(duì)列空隊(duì)列Q.frontQ.rear(b) 入隊(duì)入隊(duì)3個(gè)元素個(gè)元素a3a2a1Q.frontQ.rear(c) 出隊(duì)出隊(duì)3個(gè)元素個(gè)元素Q.frontQ.rear(d) 入隊(duì)入隊(duì)2個(gè)元素個(gè)元素a5a4Q.frontQ.rearfront=rear=0將新元素插將新元素插入入rear所指的所指的位置，然后位置，然后rear加加1刪去刪去front所指所指的元素，然后的元素，然后加加1并返回被刪并返回被刪元素元素隊(duì)列已滿，隊(duì)列已滿，但仍有存儲但仍有存儲空間空間n 充分利用向量空間充分利

18、用向量空間，克服上述，克服上述“假溢出假溢出”現(xiàn)象現(xiàn)象n 將為隊(duì)列分配的向量空間看成為一個(gè)首尾相接將為隊(duì)列分配的向量空間看成為一個(gè)首尾相接的圓環(huán)，并稱這種隊(duì)列為的圓環(huán)，并稱這種隊(duì)列為循環(huán)隊(duì)列循環(huán)隊(duì)列123450循環(huán)循環(huán)隊(duì)列隊(duì)列frontrear123450(a) 空隊(duì)列空隊(duì)列frontrear(b) d, e, b, g入入隊(duì)隊(duì)frontdebgrear(c) d, e出隊(duì)出隊(duì)bgfrontrear(d) i, j, k入入隊(duì)隊(duì)bgfrontijkrear(e) b, g出隊(duì)出隊(duì)ijkrearfront(f) r, p, s, t入隊(duì)入隊(duì)ijkfrontrprearStatus EnQueue

19、(SqQueue Q , ElemType e) /* 將數(shù)據(jù)元素e插入到循環(huán)隊(duì)列Q的隊(duì)尾 */if (Q.rear+1)%MAXSIZE= Q.front)return ERROR; /* 隊(duì)滿，返回錯(cuò)誤標(biāo)志 */Q.baseQ. rear=e ; /* 元素e入隊(duì) */Q.rear = (Q.rear+1) % MAXSIZE ; /* 隊(duì)尾指針向前移動(dòng) */return OK; /* 入隊(duì)成功 */Status DeQueue(SqQueue Q, ElemType &e) /* 將循環(huán)隊(duì)列Q的隊(duì)首元素出隊(duì) */if (Q.front= Q.rear)return ERROR ;

20、 /* 隊(duì)空，返回錯(cuò)誤標(biāo)志 */e = Q.baseQ.front ; /* 取隊(duì)首元素 */Q.front = (Q.front+1)% MAXSIZE ; /* 隊(duì)首指針向前移動(dòng) */return OK ;第四章 串n重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容p 串的基本概念串的基本概念n 串串( (字符串字符串) )：是零個(gè)或多個(gè)字符組成的有限序列：是零個(gè)或多個(gè)字符組成的有限序列。記作。記作： S=a1a2a3n 其其中中S是串名，是串名，ai(1in)是單個(gè)，是單個(gè)，可以是字母、數(shù)字或可以是字母、數(shù)字或其它字符。其它字符。n 串值串值：雙引號括起來的字符序列是串值。：雙引號括起來的字符序列是串值。n 串長串長：

21、串中所包含的字符個(gè)數(shù)稱為該串的長度。：串中所包含的字符個(gè)數(shù)稱為該串的長度。n 空串空串( (空的字符串空的字符串) )：長度為零長度為零的串稱為空串，它不包含任的串稱為空串，它不包含任何字符。何字符。n 空空格串格串( (空白串空白串) )：構(gòu)成串的所有：構(gòu)成串的所有字符都是空格字符都是空格的串稱為空的串稱為空白串。白串。注意注意：空串和空白串的不同，例如：空串和空白串的不同，例如 和和分分別表示長度為別表示長度為1 1的空白串和長度為的空白串和長度為0的空串。的空串。第五章 數(shù)組和廣義表n重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容p 稀疏矩陣的壓縮存儲稀疏矩陣的壓縮存儲p 廣義表的基本概念、求表頭、表尾操作廣義表的基

22、本概念、求表頭、表尾操作兩種順序存儲方式兩種順序存儲方式n 行優(yōu)先順序行優(yōu)先順序(Row Major Order) ：將數(shù)組元素按行排列，第將數(shù)組元素按行排列，第i+1個(gè)行向量緊接在第個(gè)行向量緊接在第i個(gè)行向量后面。對二維數(shù)組，按行優(yōu)個(gè)行向量后面。對二維數(shù)組，按行優(yōu)先順序存儲的線性序列為：先順序存儲的線性序列為： a11,a12,a1n, a21,a22,a2n , am1,am2,amn PASCAL、C是按行優(yōu)先順序存儲的是按行優(yōu)先順序存儲的n 列優(yōu)先順序列優(yōu)先順序(Column Major Order) ：將數(shù)組元素按列向量將數(shù)組元素按列向量排列，第排列，第j+1個(gè)列向量緊接在第個(gè)列向量

23、緊接在第j個(gè)列向量之后，對二維數(shù)組，個(gè)列向量之后，對二維數(shù)組，按列優(yōu)先順序存儲的線性序列為：按列優(yōu)先順序存儲的線性序列為： a11,a21,am1, a12,a22,am2, , an1,an2,anm FORTRAN是按列優(yōu)先順序存儲的是按列優(yōu)先順序存儲的 a11 a12 a1n a21 a22 a2n am1 am2 amnA=(a) 二維數(shù)組的表示形式二維數(shù)組的表示形式(b) 行優(yōu)先順序存儲行優(yōu)先順序存儲(c) 列列優(yōu)先順序存儲優(yōu)先順序存儲a11 a12 a1n第第 1行行a21 a22 a2n第第2行行am1 am2 Amn 第第m行行a11 a21 am1第第1列列a12 a22 a

24、m2第第2列列a1m a2m amn第第n列列 給每一對對稱給每一對對稱元素元素aij和和aji(ij)分配分配1 1個(gè)存儲空間個(gè)存儲空間，則，則n2個(gè)元素壓縮存儲到個(gè)元素壓縮存儲到n(n+1)/2個(gè)存儲空間個(gè)存儲空間 假設(shè)按假設(shè)按“行優(yōu)先順序行優(yōu)先順序”存儲下三角形中的元素。存儲下三角形中的元素。 設(shè)用一維數(shù)組設(shè)用一維數(shù)組( (向量向量) )sa0n(n+1)/2存儲存儲n階對稱階對稱矩陣，矩陣， 為便于訪問，找出矩陣為便于訪問，找出矩陣A中的元素的下標(biāo)值中的元素的下標(biāo)值（i,j）和和向量向量sak的的下標(biāo)值下標(biāo)值k之間的對應(yīng)關(guān)系。之間的對應(yīng)關(guān)系。sa a00 a10 a11 an-1,0

25、an-1,1 an-1,n-1K 1 2 3 4 n(n-1)/2 n(n+1)/2對稱矩陣的對稱矩陣的壓縮存儲示例壓縮存儲示例n 廣義表廣義表(Lists，又稱為列表，又稱為列表 )：是由：是由n(n 0)個(gè)個(gè)元素組成的有窮序列：元素組成的有窮序列： LS=(a1，a2，an) a1(表中第一個(gè)元素表中第一個(gè)元素)稱為稱為表頭表頭； 其余元素組成的子表稱為其余元素組成的子表稱為表尾表尾；(a2，a3，an) 廣義表中所包含的元素廣義表中所包含的元素(包括原子和子表包括原子和子表)的的個(gè)數(shù)稱為個(gè)數(shù)稱為表的長度表的長度。 廣義表中括號的最大層數(shù)稱為表深廣義表中括號的最大層數(shù)稱為表深 (度度)。第

26、六章 樹和二叉樹n重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容p 樹和二叉樹的定義及相關(guān)概念樹和二叉樹的定義及相關(guān)概念p 二叉樹的二叉樹的5 5個(gè)性質(zhì)個(gè)性質(zhì)p 二叉樹的各種存儲結(jié)構(gòu)二叉樹的各種存儲結(jié)構(gòu)p 樹的各種存儲結(jié)構(gòu)樹的各種存儲結(jié)構(gòu)p 二叉樹的各種遍歷方法、中序遍歷算法二叉樹的各種遍歷方法、中序遍歷算法p 線索二叉樹的畫法線索二叉樹的畫法p 樹的兩種遍歷方法樹的兩種遍歷方法p 哈夫曼樹的構(gòu)造、哈夫曼編碼方法哈夫曼樹的構(gòu)造、哈夫曼編碼方法樹樹的的基本術(shù)語基本術(shù)語n 結(jié)點(diǎn)結(jié)點(diǎn)(node)：數(shù)據(jù)元素：數(shù)據(jù)元素若干指向其子樹的分支若干指向其子樹的分支n 結(jié)點(diǎn)的度結(jié)點(diǎn)的度(degree) ：結(jié)點(diǎn)所擁有的子樹的個(gè)數(shù)稱為：結(jié)點(diǎn)所擁

27、有的子樹的個(gè)數(shù)稱為結(jié)點(diǎn)的度結(jié)點(diǎn)的度。n 樹樹的度：的度：樹中結(jié)點(diǎn)度的樹中結(jié)點(diǎn)度的最大值最大值。AABDCEGFHIMJNKL只有根結(jié)點(diǎn)只有根結(jié)點(diǎn)樹的基本術(shù)語樹的基本術(shù)語n葉子結(jié)點(diǎn)葉子結(jié)點(diǎn)：即度為即度為0 0的結(jié)點(diǎn)的結(jié)點(diǎn)n分支結(jié)點(diǎn)分支結(jié)點(diǎn)：除葉子結(jié)點(diǎn)之外的其它結(jié)點(diǎn)除葉子結(jié)點(diǎn)之外的其它結(jié)點(diǎn)n孩子孩子(Child)(Child)：若結(jié)點(diǎn)若結(jié)點(diǎn)x x有子樹，則子樹的根結(jié)有子樹，則子樹的根結(jié)點(diǎn)是點(diǎn)是x x的孩子。的孩子。n雙親(Parent)：若x有孩子結(jié)點(diǎn)，則該x結(jié)點(diǎn)稱為其孩子結(jié)點(diǎn)的雙親結(jié)點(diǎn)。58ABDCEGFHIMJNKL樹的基本術(shù)語樹的基本術(shù)語n兄弟結(jié)點(diǎn)：同一個(gè)雙親的孩子結(jié)點(diǎn)n祖先結(jié)點(diǎn)：從根結(jié)點(diǎn)到

28、該結(jié)點(diǎn)所經(jīng)路徑上的所有結(jié)點(diǎn)。n子孫結(jié)點(diǎn)：以某個(gè)結(jié)點(diǎn)為根的子樹以某個(gè)結(jié)點(diǎn)為根的子樹中的任何一個(gè)結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)n結(jié)點(diǎn)的層次：從根開始定義，根為第1層，根的孩子為第2層n堂兄弟：雙親結(jié)點(diǎn)在同一層上雙親結(jié)點(diǎn)在同一層上59ABDCEGFHIJ樹的基本術(shù)語樹的基本術(shù)語n 有序樹有序樹：樹中各個(gè)節(jié)點(diǎn)的子樹樹中各個(gè)節(jié)點(diǎn)的子樹T1，T2，T3，之間是之間是有次序的有次序的，即，即為有序樹。即各個(gè)子樹之間的左為有序樹。即各個(gè)子樹之間的左右次序不能互換右次序不能互換n 無序樹無序樹：樹中各個(gè)節(jié)點(diǎn)的子樹樹中各個(gè)節(jié)點(diǎn)的子樹T1，T2，T3，之間之間沒有次序關(guān)系沒有次序關(guān)系的，的，即為無序樹。即為無序樹。60

29、ABCDEACBDE樹的基本術(shù)語樹的基本術(shù)語n 樹的深度樹的深度：樹中節(jié)點(diǎn)的樹中節(jié)點(diǎn)的最大層次，最大層次，也稱為樹的也稱為樹的高度或深度。高度或深度。61ABCDDEFHIJKLM第第1層層第第2層層第第3層層第第4層層62二叉樹的定義二叉樹的定義n 二叉樹或者為空樹二叉樹或者為空樹n 或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為或是由一個(gè)根結(jié)點(diǎn)加上兩棵分別稱為左子樹左子樹和和右子樹右子樹的、的、互不相交互不相交的二叉樹組成。的二叉樹組成。EGBEFAAAAA(a)(b)(c)(d)(e)二叉樹有二叉樹有5種基本形態(tài)：種基本形態(tài)：二叉樹的特點(diǎn)：二叉樹的特點(diǎn)：1）每個(gè)結(jié)點(diǎn)的度）每個(gè)結(jié)點(diǎn)的度1，則其，則其雙親

30、結(jié)點(diǎn)雙親結(jié)點(diǎn)parent(i) 的編號是的編號是 i/2 。如果如果2in，則編號為，則編號為 i 的結(jié)點(diǎn)無左孩子（編號為的結(jié)點(diǎn)無左孩子（編號為 i 的結(jié)點(diǎn)為葉子結(jié)的結(jié)點(diǎn)為葉子結(jié)點(diǎn)）；否則其左孩子結(jié)點(diǎn)點(diǎn)）；否則其左孩子結(jié)點(diǎn)LChild(i)的編號是的編號是2i 。如果如果2i+1n，則編號為，則編號為 i 的結(jié)點(diǎn)無右孩子；否則其右孩子結(jié)點(diǎn)的結(jié)點(diǎn)無右孩子；否則其右孩子結(jié)點(diǎn) RChild(i) 的編號是結(jié)點(diǎn)的編號是結(jié)點(diǎn)2i+1。ii+12i2i+12i+22i+3 i/2 (a) i和和i+1結(jié)點(diǎn)在同一層結(jié)點(diǎn)在同一層i+12i+22i+3i2i2i+1(b) i和和i+1結(jié)點(diǎn)不在同一層結(jié)點(diǎn)不在同一

31、層順序存儲結(jié)構(gòu)順序存儲結(jié)構(gòu) 二叉樹存儲結(jié)構(gòu)的類型定義：二叉樹存儲結(jié)構(gòu)的類型定義：# define MAX_SIZE 100 typedef telemtype sqbitreeMAX_SIZE;SqBiTree bt;n 用一組地址連續(xù)的存儲單元依次用一組地址連續(xù)的存儲單元依次“自上而下自上而下、自左自左至右至右”存儲完全二叉樹存儲完全二叉樹的數(shù)據(jù)元素的數(shù)據(jù)元素。n 對于完全二叉樹上對于完全二叉樹上編號為編號為i的結(jié)點(diǎn)元素存儲在一維的結(jié)點(diǎn)元素存儲在一維數(shù)組的下標(biāo)值為數(shù)組的下標(biāo)值為i-1的分量中的分量中n 對于一般的二叉樹，對于一般的二叉樹，將其每個(gè)結(jié)點(diǎn)與完全二叉樹上將其每個(gè)結(jié)點(diǎn)與完全二叉樹上的

32、結(jié)點(diǎn)相對照的結(jié)點(diǎn)相對照，存儲在一維數(shù)組中存儲在一維數(shù)組中abcdhiejklfg(a) 完全二叉樹完全二叉樹(b) 非完全二叉樹非完全二叉樹abcdefgh000 0 1 2 3 4 5 6 7 8 9 10 11 a b c d e f g h i j k l (c) 完全二叉樹的順序存儲形式完全二叉樹的順序存儲形式0 1 2 3 4 5 6 7 8 9 10 a b c d e 0 h 0 0 f g(d) 非完全二叉樹的順序存儲形式非完全二叉樹的順序存儲形式最壞的情況下，一個(gè)深度為最壞的情況下，一個(gè)深度為k且且只有只有k個(gè)結(jié)點(diǎn)的單支樹需要長度個(gè)結(jié)點(diǎn)的單支樹需要長度為為2k-1的一維數(shù)組的

33、一維數(shù)組。鏈?zhǔn)酱鎯Y(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu) 二叉鏈表二叉鏈表。結(jié)點(diǎn)有三個(gè)域：結(jié)點(diǎn)有三個(gè)域：一個(gè)數(shù)據(jù)域一個(gè)數(shù)據(jù)域，兩個(gè)分別指向左右子結(jié)，兩個(gè)分別指向左右子結(jié)點(diǎn)的點(diǎn)的指針域指針域 typedef struct BTNode ElemType data ; struct BTNode *Lchild , *Rchild ; BTNode ; Lchild data Rchild(a) 二叉鏈表結(jié)點(diǎn)二叉鏈表結(jié)點(diǎn) 三三叉鏈表叉鏈表除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，除二叉鏈表的三個(gè)域外，再增加一個(gè)指針域，用來用來指向指向結(jié)點(diǎn)的父結(jié)點(diǎn)結(jié)點(diǎn)的父結(jié)點(diǎn)typedef struct BTNode_3 ElemType

34、 data ;struct BTNode_3 *Lchild , *Rchild , *parent ;BTNode_3 ; Lchild data parent Rchild三三叉鏈表結(jié)點(diǎn)叉鏈表結(jié)點(diǎn)(2) 二叉樹的鏈?zhǔn)酱鎯π问蕉鏄涞逆準(zhǔn)酱鎯π问?a) 二叉樹二叉樹afedcbg(c) 三三叉鏈表叉鏈表 a b c d e f g T(b) 二二叉鏈表叉鏈表 a b c d e g f T1 雙親表示法雙親表示法typedef struct PTNode NodesMAX_SIZE ;int r，n; / 根結(jié)點(diǎn)位置，結(jié)根結(jié)點(diǎn)位置，結(jié)點(diǎn)數(shù)點(diǎn)數(shù) Ptree ; FGHIRABCDE 樹的雙親存

35、儲結(jié)構(gòu)樹的雙親存儲結(jié)構(gòu)R -10A 01B 02C 03D 14E 15F 36G 67H 68I 69r=0n=10n 這種存儲結(jié)構(gòu)利用了任一結(jié)點(diǎn)的這種存儲結(jié)構(gòu)利用了任一結(jié)點(diǎn)的雙親結(jié)點(diǎn)唯一的性質(zhì)。雙親結(jié)點(diǎn)唯一的性質(zhì)?？梢苑奖憧梢苑奖愕刂苯诱业饺我唤Y(jié)點(diǎn)的雙親地直接找到任一結(jié)點(diǎn)的雙親n 但求結(jié)點(diǎn)的孩子結(jié)點(diǎn)時(shí)需要掃描但求結(jié)點(diǎn)的孩子結(jié)點(diǎn)時(shí)需要掃描整個(gè)數(shù)組。整個(gè)數(shù)組。nodes789 35 012 6 0123456789MAX_NODE-1rnA B C D E F G H I R 410孩子鏈表存儲結(jié)構(gòu)孩子鏈表存儲結(jié)構(gòu)孩子鏈表表示法孩子鏈表表示法FGHIRABCDE(b) 樹樹 FGRABCDE(

36、c) 孩子兄弟存儲結(jié)構(gòu)孩子兄弟存儲結(jié)構(gòu) R A D C G B F E 孩子結(jié)點(diǎn)孩子結(jié)點(diǎn)兄弟結(jié)點(diǎn)兄弟結(jié)點(diǎn)firstchild data nextsibing(a) 結(jié)點(diǎn)結(jié)構(gòu)結(jié)點(diǎn)結(jié)構(gòu)3 孩子兄弟孩子兄弟表示法表示法先左先左后右的遍歷算法后右的遍歷算法n 先先(根根)序序的遍歷的遍歷算法算法DLRn 中中(根根)序序的遍歷的遍歷算法算法LDRn 后后(根根)序序的遍歷的遍歷算法算法LRD77根左左子樹子樹右右子樹子樹78n 遍歷序列可否唯一確定一棵二叉樹？遍歷序列可否唯一確定一棵二叉樹？ 先序序列：先序序列：ABIDEFGCHJ 中序序列：中序序列：IBFEDGAJHCABCIDEFGHJn 遍歷

37、二叉樹遍歷二叉樹的結(jié)果是求得結(jié)點(diǎn)的一個(gè)線性序列的結(jié)果是求得結(jié)點(diǎn)的一個(gè)線性序列。n 指向該線指向該線性序列中的性序列中的“前驅(qū)前驅(qū)”和和“后繼后繼”的指針，稱作的指針，稱作“線索線索”。n 包含包含“線索線索”的的存儲結(jié)構(gòu)存儲結(jié)構(gòu)稱作稱作“線索鏈表線索鏈表”；與其相應(yīng)的；與其相應(yīng)的二叉樹，稱為二叉樹，稱為“線索二叉樹線索二叉樹”。79AFHIEGBDCAFHIEGBDCNIL前序遍歷結(jié)點(diǎn)序列：前序遍歷結(jié)點(diǎn)序列：ABDCEGFHIAFHIEGBDC(a) 二叉樹二叉樹 (b) 先序線索樹的邏輯形式先序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：ABDCEGFHIAFHIEGBDCNIL(d) 后序線索樹

38、的邏輯形式后序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBGEHIFCA(c) 中序線索樹的邏輯形式中序線索樹的邏輯形式 結(jié)點(diǎn)序列：結(jié)點(diǎn)序列：DBAGECHFIAFHIEGBDCNILNILAFHIEGBDCNILn 線索二叉樹的指針信息存儲在哪里？線索二叉樹的指針信息存儲在哪里？p 設(shè)一棵二叉樹有設(shè)一棵二叉樹有n個(gè)結(jié)點(diǎn)，則有個(gè)結(jié)點(diǎn)，則有n-1條邊條邊 (指針指針連線連線) ， 而而n個(gè)結(jié)點(diǎn)共有個(gè)結(jié)點(diǎn)共有2n個(gè)指針域個(gè)指針域 (Lchild 和和 Rchild) ，顯然，顯然有有n+1個(gè)空閑指針域個(gè)空閑指針域未用。未用。p 可以利用這些空閑的指針域來存放結(jié)點(diǎn)的可以利用這些空閑的指針域來存放結(jié)點(diǎn)的

39、直直接前驅(qū)接前驅(qū)和和直接后繼直接后繼信息。信息。81對結(jié)點(diǎn)的指針域做如下規(guī)定：對結(jié)點(diǎn)的指針域做如下規(guī)定：n 若結(jié)點(diǎn)有左子樹，則若結(jié)點(diǎn)有左子樹，則Lchild指向其左子樹，指向其左子樹，Ltag0；否否則，指向其直接前驅(qū)，則，指向其直接前驅(qū)，Ltag1；n 若結(jié)點(diǎn)有右子樹，則若結(jié)點(diǎn)有右子樹，則Rchild指向其右子樹，指向其右子樹，Rtag0；否否則，指向其直接后繼，則，指向其直接后繼，Rtag1；Lchild Ltag data Rchild Rtag線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)線索二叉樹的結(jié)點(diǎn)結(jié)構(gòu)0：Lchild域指示結(jié)點(diǎn)的左孩子域指示結(jié)點(diǎn)的左孩子1 1：Lchild域指示結(jié)點(diǎn)的前驅(qū)域指示結(jié)點(diǎn)的前驅(qū)

40、Ltag=0 0：Rchild域指示結(jié)點(diǎn)的右孩子域指示結(jié)點(diǎn)的右孩子1 1：Rchild域指示結(jié)點(diǎn)的后繼域指示結(jié)點(diǎn)的后繼Rtag=6.4.3 樹和森林的遍歷樹和森林的遍歷1 樹的遍歷樹的遍歷 由樹結(jié)構(gòu)的定義可知，樹的遍歷有二種方法。由樹結(jié)構(gòu)的定義可知，樹的遍歷有二種方法。(1) 先根序遍歷先根序遍歷：先訪問根結(jié)點(diǎn)，然后：先訪問根結(jié)點(diǎn)，然后先序遍歷完先序遍歷完每棵子樹。每棵子樹。 (2) 后根序遍歷后根序遍歷：先：先依次后序遍歷完依次后序遍歷完每棵子樹，然后訪問根結(jié)每棵子樹，然后訪問根結(jié)點(diǎn)。點(diǎn)。ABDCKGJIFHE先序遍歷：先序遍歷：ABCDEFGIJHK后序遍歷：后序遍歷：CDBFIJGHEK

41、A基本概念基本概念 結(jié)點(diǎn)路徑結(jié)點(diǎn)路徑：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)的之間的分支構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。構(gòu)成這兩個(gè)結(jié)點(diǎn)之間的路徑。 路徑長度路徑長度：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長度：結(jié)點(diǎn)路徑上的分支數(shù)目稱為路徑長度。 樹的路徑長度樹的路徑長度：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和：從樹根到每一個(gè)結(jié)點(diǎn)的路徑長度之和。ABDCKGJIFHEA到到F ：結(jié)點(diǎn)路徑：結(jié)點(diǎn)路徑 AEF ；路徑長度路徑長度( (即邊的數(shù)目即邊的數(shù)目) )：2 ；樹的路徑長度樹的路徑長度：31+52+23=19 結(jié)點(diǎn)的帶權(quán)路徑長度結(jié)點(diǎn)的帶權(quán)路徑長度：從該結(jié)點(diǎn)的到樹的根結(jié)點(diǎn)之間的路：從該結(jié)點(diǎn)

42、的到樹的根結(jié)點(diǎn)之間的路徑長度與結(jié)點(diǎn)的權(quán)徑長度與結(jié)點(diǎn)的權(quán)( (值值) )的乘積的乘積。權(quán)權(quán)( (值值) )：各種：各種開銷開銷、代價(jià)代價(jià)、頻度頻度等的抽象稱呼等的抽象稱呼。 樹的帶權(quán)路徑長度樹的帶權(quán)路徑長度：樹中：樹中所有葉子結(jié)點(diǎn)所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之的帶權(quán)路徑長度之和，記做：和，記做： WPL=w1 l1+w2 l2+ +wn ln=wi li (i=1,2, ,n)其中：其中：n為葉子結(jié)點(diǎn)的個(gè)數(shù)為葉子結(jié)點(diǎn)的個(gè)數(shù)；wi為第為第i個(gè)結(jié)點(diǎn)的權(quán)值個(gè)結(jié)點(diǎn)的權(quán)值； li為第為第i個(gè)結(jié)點(diǎn)的路個(gè)結(jié)點(diǎn)的路徑長度。徑長度。 Huffman樹樹：具有：具有n個(gè)葉子結(jié)點(diǎn)個(gè)葉子結(jié)點(diǎn)(每個(gè)結(jié)點(diǎn)的權(quán)值為每個(gè)結(jié)點(diǎn)的權(quán)

43、值為wi) 的的二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵二叉樹不止一棵，但在所有的這些二叉樹中，必定存在一棵WPL值最小的樹值最小的樹，稱這棵樹為，稱這棵樹為Huffman樹樹(或稱最優(yōu)樹或稱最優(yōu)樹) ?；靖拍罨靖拍頗uffman樹的構(gòu)造樹的構(gòu)造根據(jù)根據(jù)n個(gè)權(quán)值個(gè)權(quán)值w1, w2, ,wn，構(gòu)造成，構(gòu)造成n棵二叉樹的集合棵二叉樹的集合F=T1, T2, ,Tn，其中每棵二叉樹只有一個(gè)權(quán)值為，其中每棵二叉樹只有一個(gè)權(quán)值為wi的的根結(jié)點(diǎn)，沒有左、右子樹；根結(jié)點(diǎn)，沒有左、右子樹；在在F中中選取兩棵根結(jié)點(diǎn)權(quán)值最小選取兩棵根結(jié)點(diǎn)權(quán)值最小的樹作為左的樹作為左、右子樹構(gòu)造右子樹構(gòu)造一棵新的二

44、叉樹，且新的二叉樹根結(jié)點(diǎn)權(quán)值為其左一棵新的二叉樹，且新的二叉樹根結(jié)點(diǎn)權(quán)值為其左、右子右子樹根結(jié)點(diǎn)的權(quán)值之和；樹根結(jié)點(diǎn)的權(quán)值之和；在在F中刪除這兩棵樹，同時(shí)將新得到的樹加入中刪除這兩棵樹，同時(shí)將新得到的樹加入F中；中；重復(fù)、，直到重復(fù)、，直到F只含一顆樹為止。只含一顆樹為止。規(guī)定規(guī)定F=T1,T2, ,Tn中中權(quán)值小權(quán)值小的二叉樹作為新構(gòu)造的二叉的二叉樹作為新構(gòu)造的二叉樹的樹的左子樹左子樹，權(quán)值大的二叉樹作為新構(gòu)造的二叉樹的右子權(quán)值大的二叉樹作為新構(gòu)造的二叉樹的右子樹樹；在取值相等時(shí)，在取值相等時(shí)，深度小深度小的二叉樹作為新構(gòu)造的二叉樹的的二叉樹作為新構(gòu)造的二叉樹的左左子樹子樹，深度大的二叉樹作

45、為新構(gòu)造的二叉樹的右子樹深度大的二叉樹作為新構(gòu)造的二叉樹的右子樹。 權(quán)值集合權(quán)值集合W=8, 3, 4, 6, 5, 5構(gòu)造構(gòu)造Huffman樹的過樹的過程程。所構(gòu)造的所構(gòu)造的Huffman樹的樹的WPL是是： WPL=6 2+3 3+4 3+8 2+5 3+5 3 =79345568第一步5568第二步34768第三步34755108第四步5510634713第六步1111100000855101863471331第五步8551018634713例子例子Huffman編碼編碼p在電報(bào)收發(fā)等數(shù)據(jù)通訊中在電報(bào)收發(fā)等數(shù)據(jù)通訊中，常需要將傳送的文字常需要將傳送的文字轉(zhuǎn)換成由二進(jìn)制字符轉(zhuǎn)換成由二進(jìn)制字

46、符0、1組成的字符串來傳輸組成的字符串來傳輸。n 為了使收發(fā)的速度提高為了使收發(fā)的速度提高，要求電文要求電文編碼要盡可編碼要盡可能短能短。n 要設(shè)計(jì)要設(shè)計(jì)長短不等長短不等的編碼，還必須保證的編碼，還必須保證任意字符任意字符的編碼都不是另一個(gè)字符編碼的前綴的編碼都不是另一個(gè)字符編碼的前綴，稱為，稱為前前綴編碼綴編碼。pHuffman樹可以用來構(gòu)造編碼長度不等且譯碼不樹可以用來構(gòu)造編碼長度不等且譯碼不產(chǎn)生二義性的編碼產(chǎn)生二義性的編碼。Huffman編碼方法編碼方法 設(shè)電文中的字符集設(shè)電文中的字符集C=c1,c2, ,ci, ,cn，各個(gè)字符，各個(gè)字符出現(xiàn)的次數(shù)或頻度集出現(xiàn)的次數(shù)或頻度集W=w1,w

47、2, ,wi, ,wn。 以以字符集字符集C作為葉子結(jié)點(diǎn)作為葉子結(jié)點(diǎn)，次數(shù)或頻度集次數(shù)或頻度集W作為結(jié)作為結(jié)點(diǎn)點(diǎn)的權(quán)值的權(quán)值來構(gòu)造來構(gòu)造Huffman樹樹。 規(guī)規(guī)定定Huffman樹中左分支代表樹中左分支代表“0”，右分支代表，右分支代表“1” 。 從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)歷從根結(jié)點(diǎn)到每個(gè)葉子結(jié)點(diǎn)所經(jīng)歷的路徑分支上的的路徑分支上的“0”或或“1”所組成的字符串所組成的字符串，為該結(jié)點(diǎn)所對應(yīng)的編碼為該結(jié)點(diǎn)所對應(yīng)的編碼，稱稱之為之為Huffman編碼編碼。 * *由于每個(gè)字符都是葉子結(jié)點(diǎn)由于每個(gè)字符都是葉子結(jié)點(diǎn)，不可能出現(xiàn)在根結(jié)點(diǎn)到其它字符，不可能出現(xiàn)在根結(jié)點(diǎn)到其它字符結(jié)點(diǎn)的路徑上，所以一個(gè)字符

48、的結(jié)點(diǎn)的路徑上，所以一個(gè)字符的Huffman編碼不可能是另一個(gè)字編碼不可能是另一個(gè)字符的符的Huffman編碼的前綴編碼的前綴。第七章 圖n重點(diǎn)內(nèi)容重點(diǎn)內(nèi)容p 圖的定義及相關(guān)術(shù)語圖的定義及相關(guān)術(shù)語p 圖的各種存儲結(jié)構(gòu)圖的各種存儲結(jié)構(gòu)p 圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷法圖的深度優(yōu)先遍歷和廣度優(yōu)先遍歷法p 圖的最小生成樹的概念圖的最小生成樹的概念p 克魯斯卡爾算法、普里姆算法生成最小生成樹克魯斯卡爾算法、普里姆算法生成最小生成樹p 圖的拓?fù)渑判?、關(guān)鍵路徑的求法圖的拓?fù)渑判颉㈥P(guān)鍵路徑的求法917.2 圖的存儲結(jié)構(gòu)圖的存儲結(jié)構(gòu)圖的數(shù)組存儲表示法基本思想基本思想：n 對于對于有有n個(gè)頂點(diǎn)的圖，用一維數(shù)組

49、個(gè)頂點(diǎn)的圖，用一維數(shù)組vexsn存存儲頂點(diǎn)信儲頂點(diǎn)信息息n 用二維數(shù)組用二維數(shù)組Ann存儲頂點(diǎn)之間關(guān)系的信存儲頂點(diǎn)之間關(guān)系的信息息n 該二維數(shù)組稱為該二維數(shù)組稱為鄰接矩陣鄰接矩陣n 在鄰接矩陣中在鄰接矩陣中：p 以頂點(diǎn)在vexs數(shù)組中的下標(biāo)代表頂點(diǎn)p 鄰接矩陣中的元素Aij存放的是頂點(diǎn)i到頂點(diǎn)j之間關(guān)系的信息921 無向圖的數(shù)組表示無向圖的數(shù)組表示(1) 無權(quán)圖的鄰接矩陣無權(quán)圖的鄰接矩陣 無向無權(quán)圖無向無權(quán)圖G=(V，E)有有n(n1)個(gè)頂點(diǎn)，其鄰接矩陣是個(gè)頂點(diǎn)，其鄰接矩陣是n階對稱方陣階對稱方陣，其元素的定義如下：，其元素的定義如下：1 若若(vi , vj) E，即，即vi , vj鄰接鄰

50、接0 若若(vi , vj) E，即，即vi , vj不鄰接不鄰接Aij=(a) 無向圖無向圖 abcd(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣vexsabcd0 1 1 11 0 1 11 1 0 11 1 1 0(c) 鄰接矩陣鄰接矩陣(2) 帶權(quán)圖（網(wǎng)）的鄰接矩陣帶權(quán)圖（網(wǎng)）的鄰接矩陣 無向帶權(quán)圖無向帶權(quán)圖G=(V，E) 的鄰接矩陣元素的定義如下：的鄰接矩陣元素的定義如下：帶權(quán)無向圖帶權(quán)無向圖 鄰接矩陣鄰接矩陣354126abcde3vexsabcde 6 2 6 3 4 32 3 1 4 3 5 3 5 Wij 若若(vi , vj) E，即，即vi , vj鄰接，權(quán)值為鄰接，權(quán)值為wij 若若(vi

51、 , vj) E，即，即vi , vj不鄰接時(shí)不鄰接時(shí)Aij=特點(diǎn)：特點(diǎn)：1、無向圖的鄰接矩陣是、無向圖的鄰接矩陣是對稱方陣對稱方陣；2、頂點(diǎn)、頂點(diǎn)vi的度數(shù)的度數(shù)是第是第i行的行的非非0元素的個(gè)數(shù)元素的個(gè)數(shù)；3 3、無向圖的邊數(shù)是上無向圖的邊數(shù)是上(或下或下)三角形矩陣中三角形矩陣中非非0元元素個(gè)數(shù)素個(gè)數(shù)。952 有向圖的數(shù)組表示有向圖的數(shù)組表示(1) 無權(quán)圖的鄰接矩陣無權(quán)圖的鄰接矩陣 有向無權(quán)圖有向無權(quán)圖G=(V，E)有有n(n1)個(gè)頂點(diǎn)，則其鄰接矩個(gè)頂點(diǎn)，則其鄰接矩陣是陣是n階對稱方陣階對稱方陣元素定義如下：元素定義如下：1 若若 E，從，從vi到到vj有弧有弧Aij=0 若若 E 從從

52、vi到到vj 沒有弧沒有弧(a) 有向圖有向圖acbde(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣abcde(c) 鄰接矩陣鄰接矩陣0 1 1 0 10 0 0 0 00 0 0 1 11 1 0 0 00 0 0 1 0(2) 帶權(quán)圖的鄰接矩陣帶權(quán)圖的鄰接矩陣 有向帶權(quán)圖有向帶權(quán)圖G=(V，E)的鄰接矩陣元素的定義如下：的鄰接矩陣元素的定義如下：wij 若若 E，即，即vi , vj鄰接，權(quán)值為鄰接，權(quán)值為wij 若若 E，即，即vi , vj不鄰接時(shí)不鄰接時(shí)Aij=(b) 頂點(diǎn)矩陣頂點(diǎn)矩陣abcde(c) 鄰接矩陣鄰接矩陣 6 2 3 3 1 4 5 (a) 帶權(quán)有向圖帶權(quán)有向圖 354126abcde3特

53、點(diǎn)：特點(diǎn)：1 1、對于頂點(diǎn)對于頂點(diǎn)vi，第第i行行的非的非0元素的個(gè)數(shù)是其出度元素的個(gè)數(shù)是其出度OD(vi)；第第i列列的非的非0元素的個(gè)數(shù)是其入度元素的個(gè)數(shù)是其入度ID(vi) 。2、鄰接矩陣中、鄰接矩陣中非非0元素的個(gè)數(shù)就是圖的元素的個(gè)數(shù)就是圖的弧的數(shù)目弧的數(shù)目。7.2.2 鄰接鏈表法鄰接鏈表法 基本基本思想思想：n 對圖對圖的的每個(gè)頂點(diǎn)每個(gè)頂點(diǎn)建立一個(gè)建立一個(gè)單鏈表單鏈表，存儲該頂點(diǎn)所有，存儲該頂點(diǎn)所有鄰接頂點(diǎn)及其相關(guān)信息鄰接頂點(diǎn)及其相關(guān)信息。n 每一個(gè)單鏈表設(shè)一個(gè)每一個(gè)單鏈表設(shè)一個(gè)表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)。n 第第i個(gè)單鏈表個(gè)單鏈表: 表示依附于頂點(diǎn)表示依附于頂點(diǎn)Vi的邊的邊 (對有向圖是以對

54、有向圖是以頂點(diǎn)頂點(diǎn)Vi為尾的為尾的弧弧)。1 結(jié)點(diǎn)結(jié)構(gòu)與鄰接鏈表示例結(jié)點(diǎn)結(jié)構(gòu)與鄰接鏈表示例n 鏈表中的結(jié)點(diǎn)稱為鏈表中的結(jié)點(diǎn)稱為表結(jié)點(diǎn)表結(jié)點(diǎn)，表結(jié)點(diǎn)由三個(gè)域組，表結(jié)點(diǎn)由三個(gè)域組成：成：p 鄰鄰接點(diǎn)域：指示與頂點(diǎn)接點(diǎn)域：指示與頂點(diǎn)Vi鄰接的頂點(diǎn)在圖鄰接的頂點(diǎn)在圖中的位置中的位置p 鏈域：指向下一個(gè)與頂點(diǎn)鏈域：指向下一個(gè)與頂點(diǎn)Vi鄰接的表結(jié)點(diǎn)，鄰接的表結(jié)點(diǎn)，p 數(shù)據(jù)域：存儲和邊或弧相關(guān)數(shù)據(jù)域：存儲和邊或弧相關(guān)的信息，如權(quán)值等。的信息，如權(quán)值等。n表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)(稱為稱為頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn))，由兩個(gè)域組成：，由兩個(gè)域組成：p 鏈域：指向鏈表鏈域：指向鏈表中的第一個(gè)結(jié)點(diǎn)中的第一個(gè)結(jié)點(diǎn)p 數(shù)據(jù)域數(shù)據(jù)域：

55、存儲頂點(diǎn)名或其他信息。存儲頂點(diǎn)名或其他信息。adjvex info nextarc表結(jié)點(diǎn)表結(jié)點(diǎn)：data firstarc表頭結(jié)點(diǎn)表頭結(jié)點(diǎn)：n 所有所有頂點(diǎn)結(jié)點(diǎn)頂點(diǎn)結(jié)點(diǎn)用一個(gè)向量以順序結(jié)構(gòu)形式存儲，可用一個(gè)向量以順序結(jié)構(gòu)形式存儲，可以隨機(jī)訪問任意頂點(diǎn)的鏈表，該向量稱為以隨機(jī)訪問任意頂點(diǎn)的鏈表，該向量稱為表頭向量表頭向量n 向向量的下標(biāo)指示量的下標(biāo)指示頂點(diǎn)的位置頂點(diǎn)的位置？v1v2v3v4v501234v1 v2v3 v4 v5 213 02 0314 204 23 無向圖鄰接表無向圖鄰接表有向圖有向圖v1v2v3v4v513 014 2 3 01234v1v2 v3v4 v5正鄰接鏈表正鄰接鏈

56、表出度直觀出度直觀2 02 2 01234MAX_VEX-1v1 v2 v3 v4 v53 04 逆鄰接鏈表逆鄰接鏈表入度直觀入度直觀有向圖鄰接表有向圖鄰接表n 有向圖的鄰接表有兩有向圖的鄰接表有兩種：種：正鄰接表正鄰接表和和逆鄰逆鄰接表接表n 正鄰接表正鄰接表是以頂點(diǎn)是以頂點(diǎn)Vi為出為出度而度而建立的鄰接表建立的鄰接表；n 逆鄰接表逆鄰接表是以頂點(diǎn)是以頂點(diǎn)Vi為入為入度而度而建立的鄰接表；建立的鄰接表；2 鄰接表法的特點(diǎn)鄰接表法的特點(diǎn)n 表頭向量中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)，表頭向量中每個(gè)分量就是一個(gè)單鏈表的頭結(jié)點(diǎn)，分量個(gè)數(shù)分量個(gè)數(shù)就是圖中的頂點(diǎn)數(shù)目就是圖中的頂點(diǎn)數(shù)目；n 在在邊或弧稀疏

57、邊或弧稀疏的情況下的情況下，用鄰接表表示比用鄰接矩陣表示，用鄰接表表示比用鄰接矩陣表示節(jié)省存儲空間；節(jié)省存儲空間；n 在無向圖，在無向圖，頂點(diǎn)頂點(diǎn)Vi的度是第的度是第i個(gè)鏈表的結(jié)點(diǎn)數(shù)個(gè)鏈表的結(jié)點(diǎn)數(shù)；n 在有向圖中在有向圖中，第，第i個(gè)鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)個(gè)鏈表中的結(jié)點(diǎn)數(shù)是頂點(diǎn)Vi的出的出 (或入或入)度；度；求入求入 (或出或出)度，須遍歷整個(gè)鄰接表；度，須遍歷整個(gè)鄰接表；n 在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰在鄰接表上容易找出任一頂點(diǎn)的第一個(gè)鄰接點(diǎn)和下一個(gè)鄰接點(diǎn)接點(diǎn)；n 要判定兩個(gè)頂點(diǎn)要判定兩個(gè)頂點(diǎn)Vi和和Vj之間是否有邊，需要搜索第之間是否有邊，需要搜索第i個(gè)或第個(gè)或第j個(gè)

58、鏈表個(gè)鏈表7.3 圖的遍歷圖的遍歷n 圖圖的遍歷的遍歷(Travering Graph)：從圖的某一頂點(diǎn)出：從圖的某一頂點(diǎn)出發(fā)，訪遍圖中的其余頂點(diǎn)，發(fā)，訪遍圖中的其余頂點(diǎn)，且每個(gè)頂點(diǎn)僅被訪問且每個(gè)頂點(diǎn)僅被訪問一次一次。圖。圖的遍歷算法是各種圖操作的基礎(chǔ)的遍歷算法是各種圖操作的基礎(chǔ)。 復(fù)雜性：復(fù)雜性：圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，圖的任意頂點(diǎn)可能和其余的頂點(diǎn)相鄰接，可能在訪問了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原可能在訪問了某個(gè)頂點(diǎn)后，沿某條路徑搜索后又回到原頂點(diǎn)。頂點(diǎn)。 解決辦法解決辦法：在遍歷過程中記下已被訪問過的頂點(diǎn)。在遍歷過程中記下已被訪問過的頂點(diǎn)。設(shè)置一個(gè)輔助向量設(shè)置一個(gè)輔助向量

59、Visited1n(n為頂點(diǎn)數(shù)為頂點(diǎn)數(shù))，其初值為，其初值為0，一旦訪問了頂點(diǎn)一旦訪問了頂點(diǎn)vi后，使后，使Visitedi為為1或?yàn)樵L問的次序號或?yàn)樵L問的次序號。 n 圖圖的遍歷算法有的遍歷算法有深度優(yōu)先搜索算法深度優(yōu)先搜索算法和和廣度優(yōu)先搜廣度優(yōu)先搜索算法索算法。n 采用的數(shù)據(jù)結(jié)構(gòu)采用的數(shù)據(jù)結(jié)構(gòu)是是( (正正) )鄰接鏈表鄰接鏈表。7.3.1 深度優(yōu)先搜索算法深度優(yōu)先搜索算法 深度優(yōu)先搜索深度優(yōu)先搜索(Depth First Search-DFS)遍歷類似遍歷類似樹的先序遍歷樹的先序遍歷，是，是樹的先序遍歷的推廣樹的先序遍歷的推廣。1 算法思想算法思想設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問，則

60、：設(shè)初始狀態(tài)時(shí)圖中的所有頂點(diǎn)未被訪問，則： 從圖中某個(gè)頂點(diǎn)從圖中某個(gè)頂點(diǎn)vi出發(fā)出發(fā)，訪問，訪問vi；然后找到；然后找到vi的的一個(gè)鄰接一個(gè)鄰接頂點(diǎn)頂點(diǎn)vi1 ； 從從vi1出發(fā)，深度優(yōu)先搜索訪問和出發(fā)，深度優(yōu)先搜索訪問和vi1相相鄰接鄰接且且未被訪問未被訪問的的所有頂點(diǎn)；所有頂點(diǎn)； 轉(zhuǎn)轉(zhuǎn) ，直到和，直到和vi相相鄰接的所有頂點(diǎn)都被訪問為止鄰接的所有頂點(diǎn)都被訪問為止 繼續(xù)選取圖中未被訪問頂點(diǎn)繼續(xù)選取圖中未被訪問頂點(diǎn)vj作為起始頂點(diǎn)，轉(zhuǎn)作為起始頂點(diǎn)，轉(zhuǎn)(1)，直到，直到圖中所有頂點(diǎn)都被訪問為止。圖中所有頂點(diǎn)都被訪問為止。(a) 無向圖無向圖Gv1v2v3v4v5(b) G的鄰接鏈表的鄰接鏈表01234v1 v2v3