自考02331數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié)(最終修訂)

1、自考 02331 數(shù)據(jù)結(jié)構(gòu)重點(diǎn)總結(jié) ( 最終修訂 )第一章 概論1. 瑞士計(jì)算機(jī)科學(xué)家沃思提出：算法 +數(shù)據(jù)結(jié)構(gòu) =程序。算法是對數(shù)據(jù)運(yùn)算的描述，而數(shù)據(jù)結(jié)構(gòu)包括邏輯結(jié)構(gòu)和存儲(chǔ) 結(jié)構(gòu)。由此可見，程序設(shè)計(jì)的實(shí)質(zhì)是針對實(shí)際問題選擇一種好的數(shù)據(jù)結(jié)構(gòu)和設(shè)計(jì)一個(gè)好的算法，而好的算法在很大 程度上取決于描述實(shí)際問題的數(shù)據(jù)結(jié)構(gòu)。2. 數(shù)據(jù) 是信息的載體。 數(shù)據(jù)元素 是數(shù)據(jù)的根本單位。一個(gè)數(shù)據(jù)元素可以由假設(shè)干個(gè)數(shù)據(jù)項(xiàng) 組成， 數(shù)據(jù)項(xiàng) 是具有獨(dú)立含義的最小標(biāo)識(shí)單位。 數(shù)據(jù)對象 是具有相同性質(zhì)的數(shù)據(jù)元素的集合。3. 數(shù)據(jù)結(jié)構(gòu) 指的是數(shù)據(jù)元素之間的相互關(guān)系，即數(shù)據(jù)的組織形式。 數(shù)據(jù)結(jié)構(gòu)一般包括以下三方面內(nèi)容：數(shù)據(jù)的邏

2、輯結(jié)構(gòu)、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)、數(shù)據(jù)的運(yùn)算 數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，與數(shù)據(jù)元素的存儲(chǔ)結(jié)構(gòu)無關(guān)，是獨(dú)立于計(jì)算機(jī)的。 數(shù)據(jù)的邏輯結(jié)構(gòu)分類 : 線性結(jié)構(gòu)和非線性結(jié)構(gòu)。線性表 是一個(gè)典型的線性結(jié)構(gòu)。棧、隊(duì)列、串等都是線性結(jié)構(gòu)。數(shù)組、廣義表、樹和圖等數(shù)據(jù)結(jié)構(gòu)都是非線性結(jié)構(gòu)。 數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)內(nèi)的存儲(chǔ)方式，稱為數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)(物理結(jié)構(gòu))。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是邏輯結(jié)構(gòu)用計(jì)算機(jī)語言的實(shí)現(xiàn)，它依賴于計(jì)算機(jī)語言。 數(shù)據(jù)的運(yùn)算 。最常用的檢索、插入、刪除、更新、排序等。4. 數(shù)據(jù)的四種根本存儲(chǔ)方法 : 順序存儲(chǔ)、鏈接存儲(chǔ)、索引存儲(chǔ)、散列存儲(chǔ)( 1 )( 2 )( 3 ) ( 4 )順序存儲(chǔ) 鏈接存儲(chǔ) 索引

3、存儲(chǔ) 散列存儲(chǔ)通常借助程序設(shè)計(jì)語言的 數(shù)組 描述。 通常借助于程序語言的指針來描述。 索引表由假設(shè)干索引項(xiàng)組成。關(guān)鍵字是能唯一標(biāo)識(shí)一個(gè)元素的一個(gè)或多個(gè)數(shù)據(jù)項(xiàng)的組合。 該方法的根本思想是：根據(jù)元素的關(guān)鍵字直接計(jì)算出該元素的存儲(chǔ)地址。5 個(gè)準(zhǔn)那么： 輸入 ， 0 個(gè)或多個(gè)數(shù)據(jù)作為輸入； 輸出 ，產(chǎn)生一個(gè)或多個(gè)輸出； 有窮性 ，算法執(zhí)行有限 可行性 ，算法是可行的。5. 算法必須滿足 步后結(jié)束； 確定性 ，每一條指令的含義都明確；算法與程序的區(qū)別：程序必須依賴于計(jì)算機(jī)程序語言，而一個(gè)算法可用自然語言、計(jì)算機(jī)程序語言、數(shù)學(xué)語言或約定的符號(hào)語言來描述。目前常用的描述算法語言有兩類：類Pascal 和類

4、C。6. 評(píng)價(jià)算法的優(yōu)劣：算法的 "正確性 "是首先要考慮的。此外，主要考慮如下三點(diǎn)： 執(zhí)行算法所消耗的時(shí)間，即時(shí)間復(fù)雜性； 執(zhí)行算法所消耗的存儲(chǔ)空間，主要是輔助空間，即空間復(fù)雜性； 算法應(yīng)易于理解、易于編程，易于調(diào)試等，即可讀性和可操作性。以上幾點(diǎn)最主要的是時(shí)間復(fù)雜性，時(shí)間復(fù)雜度常用漸進(jìn)時(shí)間復(fù)雜度表示。7. 算法求解問題的 輸入量稱為問題的規(guī)模，用一個(gè)正整數(shù)n表示。8. 常見的時(shí)間復(fù)雜度按數(shù)量級(jí)遞增排列依次為： 常數(shù)階 0(1) 、對數(shù)階 0(log 2n) 、線性階 0(n) 、線性對數(shù)階 0(nlog 2n) 、 平方階0(n2)立方階0(n3)、k次方階0(nk)、

5、指數(shù)階0(2)和階乘階0(n!)。9. 一個(gè)算法的空間復(fù)雜度 S(n) 定義為該算法所消耗的存儲(chǔ)空間，它是問題規(guī)模 n 的函數(shù) ， 它包括存儲(chǔ)算法本身所占 的存儲(chǔ)空間、算法的輸入輸出數(shù)據(jù)所占的存儲(chǔ)空間和算法在運(yùn)行過程中臨時(shí)占用的存儲(chǔ)空間。第二章 線性表1. 數(shù)據(jù)的運(yùn)算是定義在邏輯結(jié)構(gòu)上的，而運(yùn)算的具體實(shí)現(xiàn)是在存儲(chǔ)結(jié)構(gòu)上進(jìn)行的。2. 只要確定了線性表存儲(chǔ)的起始位置，線性表中任意一個(gè)元素都可隨機(jī)存取，所以順序表是一種隨機(jī)存取結(jié)構(gòu)。3. 常見的線性表的根本運(yùn)算 :(1) 置空表 InitList ( L) 構(gòu)造一個(gè)空的線性表 L。 求表長ListLength ( L)求線性表L中的結(jié)點(diǎn)個(gè)數(shù)，即求表長

6、。(3)GetNode ( L， i ) 取線性表 L 中的第 i 個(gè)元素。LocateNode ( L, x)在L中查找第一個(gè)值為x的元素，并返回該元素在L中的位置。假設(shè)L中沒有元素的值為 x ,那么返回 0 值。InsertList( L, i , x)在線性表L的第i個(gè)元素之前插入一個(gè)值為 x的新元素，表L的長度加1。(6)DeleteList( L， i )刪除線性表 L 的第 i 個(gè)元素，刪除后表 L 的長度減 1。4. 順序存儲(chǔ)方法：把線性表的數(shù)據(jù)元素按邏輯次序依次存放在一組地址連續(xù)的存儲(chǔ)單元里的方法。順序表( Sequential List )：用順序存儲(chǔ)方法存儲(chǔ)的線性表稱為順序

7、表。 順序表 是一種 隨機(jī)存取結(jié)構(gòu) ， 順序表的特 點(diǎn)是邏輯上相鄰的結(jié)點(diǎn)其物理位置亦相鄰。順序表中結(jié)點(diǎn) ai的存儲(chǔ)地址：LOC ( a) = LOC (a) + (i-1 ) *c Ki <n,5順序表上實(shí)現(xiàn)的根本運(yùn)算：(1) 插入：該算法的平均時(shí)間復(fù)雜度是0(n),即在順序表上進(jìn)行插入運(yùn)算，平均要移動(dòng)一半結(jié)點(diǎn)(n/2 )。在第i個(gè)位置插入一個(gè)結(jié)點(diǎn)的移動(dòng)次數(shù)為n-i+1(2) 刪除：順序表上做刪除運(yùn)算，平均要移動(dòng)表中約一半的結(jié)點(diǎn)(n-1)/2，平均時(shí)間復(fù)雜度也是 0(n)。刪除第i個(gè)結(jié)點(diǎn)移動(dòng)次數(shù)為n-i6. 采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)可以防止頻繁移動(dòng)大量元素。一個(gè)單鏈表可由頭指針唯一確定，因此單鏈

8、表可以用頭指針的名 字來命名。 生成結(jié)點(diǎn)變量的標(biāo)準(zhǔn)函數(shù)p=( ListNode *)malloc(sizeof(ListNode) ； /函數(shù)malloc分配一個(gè)類型為 ListNode的結(jié)點(diǎn)變量的空間，并將其首地址放入指針變量p中 釋放結(jié)點(diǎn)變量空間的標(biāo)準(zhǔn)函數(shù)free(p) ； /釋放p所指的結(jié)點(diǎn)變量空間 結(jié)點(diǎn)分量的訪問方法二：p- > data和p- > next 指針變量p和結(jié)點(diǎn)變量*p的關(guān)系：指針變量p的值一一結(jié)點(diǎn)地址，結(jié)點(diǎn)變量*p的值一一結(jié)點(diǎn)內(nèi)容7. 建立單鏈表：(1) 頭插法建表：算法：p=(ListNode *)malloc(sizeof(ListNode);/ 生成新

9、結(jié)點(diǎn)(2) 尾插法建表： 算法： p=(ListNode *)malloc(sizeof(ListNode);/ 生成新結(jié)點(diǎn)p->data=ch; II將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中if (head=NULL) head=p;/ 新結(jié)點(diǎn)插入空表else rear-next=p;/將新結(jié)點(diǎn)插到*r之后rear=p;/尾指針指向新表尾hmil(3) 尾插法建帶頭結(jié)點(diǎn)的單鏈表： 頭結(jié)點(diǎn)及作用：頭結(jié)點(diǎn)是在鏈表的開始結(jié)點(diǎn)之前附加一個(gè)結(jié)點(diǎn)。它具有兩個(gè)優(yōu)點(diǎn)：1由于開始結(jié)點(diǎn)的位置被存放在頭結(jié)點(diǎn)的指針域中，所以在鏈表的第一個(gè)位置上的操作就和在表的其它位置上操作一致，無須進(jìn)行特殊處理；2無論鏈表是否為空，

10、其頭指針都是指向頭結(jié)點(diǎn)的非空指針(空表中頭結(jié)點(diǎn)的指針域空)，因此空表和非空表的處理也就統(tǒng)一了。heiid 生站開檢絡(luò)點(diǎn)I I1卡II.P1 4 帀I，頭結(jié)點(diǎn)數(shù)據(jù)域的陰影表示該局部不存儲(chǔ)信息。 中可用于存放表長等附加信息。在有的應(yīng)用PH I(M fflR希軋站點(diǎn)的單儺左具體算法：r=head;/尾指針初值也指向頭結(jié)點(diǎn)while(ch=getchar()!='n')s=(ListNode *)malloc(sizeof(ListNode);/生成新結(jié)點(diǎn)s->data=ch;/將讀入的數(shù)據(jù)放入新結(jié)點(diǎn)的數(shù)據(jù)域中r->n ext=s;r=s;r-> next=NULL;

11、 終端結(jié)點(diǎn)的指針域置空，或空表的頭結(jié)點(diǎn)指針域置空 以上三個(gè)算法的時(shí)間復(fù)雜度均為0(n)。8. 單鏈表上的查找：(帶頭結(jié)點(diǎn))(1)按結(jié)點(diǎn)序號(hào)查找：序號(hào)為 0的是頭結(jié)點(diǎn)。算法：p=head;j=0;/ 從頭結(jié)點(diǎn)開始掃描順指針向后掃描，直到while(p-> next&&j<i)p=p->n ext;j+；if(i=j) return p; else return NULL;/p->next 為 NULL或 i=j 為止找到了第i個(gè)結(jié)點(diǎn)當(dāng)i<0或i>0時(shí)，找不到第時(shí)間復(fù)雜度：在等概率假設(shè)下，平均時(shí)間復(fù)雜度為：為 (2 )按結(jié)點(diǎn)值查找：具體算法：Li

12、stNode *p=head-> next;/while(p&&p->data!=key)i個(gè)結(jié)點(diǎn)n/2=0( n)表非空，p初始值指向開始結(jié)點(diǎn)從開始結(jié)點(diǎn)比擬。直到p為NULL或p->data 為key為止p=p-> next;/掃描下一結(jié)點(diǎn)return p;/ 假設(shè)p=NULL那么查找失敗，否那么p指向值為key的結(jié)點(diǎn)時(shí)間復(fù)雜度為：O(n)9.插入運(yùn)算：插入運(yùn)算是將值為x的新結(jié)點(diǎn)插入到表的第i個(gè)結(jié)點(diǎn)的位置上，即插入到an與a之間。曲單璉喪上桶入昴點(diǎn)示總自s=(ListNode *)malloc(sizeof(ListNode); s->data=

13、x; s->n ext=p->n ext; p->n ext=s;算法的時(shí)間主要消耗在查找結(jié)點(diǎn)上，故時(shí)間復(fù)雜度亦為0(n)。10. 刪除運(yùn)算r=p->next;/使r指向被刪除的結(jié)點(diǎn) ai p->next=r->next;將ai從鏈上摘下free(r);/釋放結(jié)點(diǎn)ai的空間給存儲(chǔ)池算法的時(shí)間復(fù)雜度也是O(n) .p指向被刪除的前一個(gè)結(jié)點(diǎn)。鏈表上實(shí)現(xiàn)的插入和刪除運(yùn)算，無須移動(dòng)結(jié)點(diǎn)，僅需修改指針。11. 單循環(huán)鏈表一在單鏈表中，將終端結(jié)點(diǎn)的指針域NULL改為指向表頭結(jié)點(diǎn)或開始結(jié)點(diǎn)即可。判斷空鏈表的條件是head=head->n ext;12. 僅設(shè)尾指針的

14、單循環(huán)鏈表：用尾指針rear表示的單循環(huán)鏈表對開始結(jié)點(diǎn)a1和終端結(jié)點(diǎn)an查找時(shí)間都是 O(1)。而表的操作常常是在表的首尾位置上進(jìn)行，因此，實(shí)用中多采用尾指針表示單循環(huán)鏈表。判斷空鏈表的條件為rear=rear- >n ext;僅訛甩抒訂的申忡(代農(nóng)13. 循環(huán)鏈表：循環(huán)鏈表的特點(diǎn)是無須增加存儲(chǔ)量，僅對表的鏈接方式稍作改變，即可使得表處理更加方便靈活。假設(shè) 在尾指針表示的單循環(huán)鏈表上實(shí)現(xiàn)，那么只需修改指針，無須遍歷，其執(zhí)行時(shí)間是O(1)。卜W訃H悩代怙押馥氓fl .:汕具體算法：LinkList Connect(LinkList A,LinkList B)/ 假設(shè) A, B為非空循環(huán)鏈表

15、的尾指針LinkList p=A->next;/保存A表的頭結(jié)點(diǎn)位置A->n ext=B-> next-next;/B表的開始結(jié)點(diǎn)鏈接到 A表尾free(B->next);/釋放B表的頭結(jié)點(diǎn)B-> next=p;return B;/返回新循環(huán)鏈表的尾指針循環(huán)鏈表中沒有NULL指針。涉及遍歷操作時(shí)，其終止條件就不再是像非循環(huán)鏈表那樣判別p或p- > next是否為空，而是判別它們是否等于某一指定指針，如頭指針或尾指針等。在單鏈表中，從一結(jié)點(diǎn)出發(fā)，只能訪問到該結(jié)點(diǎn)及其后續(xù)結(jié)點(diǎn)，無法找到該結(jié)點(diǎn)之前的其它結(jié)點(diǎn)。而在單 循環(huán)鏈表中，從任一結(jié)點(diǎn)出發(fā)都可訪問到表中所有結(jié)點(diǎn)

16、，這一優(yōu)點(diǎn)使某些運(yùn)算在單循環(huán)鏈表上易于實(shí)現(xiàn)。14. 雙向鏈表：雙(向)鏈表中有兩條方向不同的鏈，即每個(gè)結(jié)點(diǎn)中除next域存放后繼結(jié)點(diǎn)地址外，還增加一個(gè)指向其直接刖趨的指針域prior。 雙鏈表由頭指針 head惟一確定的。 帶頭結(jié)點(diǎn)的雙鏈表的某些運(yùn)算變得方便。 將頭結(jié)點(diǎn)和尾結(jié)點(diǎn)鏈接起來，為雙(向)循環(huán)鏈表。15. 雙向鏈表的前插和刪除本結(jié)點(diǎn)操作 雙鏈表的前插操作void DinsertBefore(DListNode *p,DataType x)/在帶頭結(jié)點(diǎn)的雙鏈表中，將值為 x的新結(jié)點(diǎn)插入*p之前，設(shè)pz NULLDListNode *s=malloc(sizeof(DListNode);s

17、->data=x;/ s->prior=p->prior;/ s->n ext=p;/p->prior- >n ext=s;/p->prior=s;/mI雙鏈表上刪除結(jié)點(diǎn) *p自身的操作void DDeleteNode(DListNode *p)/在帶頭結(jié)點(diǎn)的雙鏈表中，刪除結(jié)點(diǎn)*p，設(shè)*p為非終端結(jié)點(diǎn)p->prior- >n ext=p->n ext;/p_>n ext->prior=p->prior;free(p); /data ilclI與單鏈表上的插入和刪除操作不同的是，在雙鏈表中插入和刪除必須同時(shí)修改兩個(gè)方向

18、上的指針。上述兩個(gè)算法的時(shí)間復(fù)雜度均為16.順序表和鏈表比擬0(1)。時(shí)間性能：a、線性表：經(jīng)常性的查找；b、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)：經(jīng)常插入刪除操作；空間性能：a、對數(shù)據(jù)量大小事先能夠知道的用線性表；b、數(shù)據(jù)量變化較大的用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。存儲(chǔ)密度越大，存儲(chǔ)空間的利用率越高。顯然，順序表的存儲(chǔ)密度是1,鏈表的存儲(chǔ)密度肯定小于1。第三章棧和隊(duì)列1. 棧稱為后進(jìn)先出Last In First Out的線性表，簡稱為 LIFO表。棧是運(yùn)算受限的線性表，順序棧也是用數(shù)組表示的。進(jìn)棧操作：進(jìn)棧時(shí)，需要將 S- > top加1,S- > top=StackSize-1 表示棧滿 "上溢"

19、;現(xiàn)象-當(dāng)棧滿時(shí)，再做進(jìn)棧運(yùn)算產(chǎn)生空間溢出的現(xiàn)象。Fitnekl 中有 4亍天幸5- iki (J)退棧操作：退棧時(shí)，需將 S- > top減1,S- >top<0表示空棧下溢現(xiàn)象-當(dāng)?？諘r(shí)，做退棧運(yùn)算產(chǎn)生的 溢出現(xiàn)象。下溢是正?，F(xiàn)象，常用作程序控制轉(zhuǎn)移的條件。空棧時(shí)棧頂指針不能是0，只能是-1。兩個(gè)棧共享同一存儲(chǔ)空間：當(dāng)程序中同時(shí)使用兩個(gè)棧時(shí)，可以將兩個(gè)棧的棧底分別設(shè)在順序存儲(chǔ)空間的兩端，讓兩個(gè)棧頂各自向中間延伸。當(dāng)一個(gè)棧中的元素較多 而棧使用的空間超過共享空間的一半時(shí)，只要另一個(gè)棧的元素不多，那么前者就可以占用后者的局部存儲(chǔ)空間。當(dāng)Top 1=Top2-1時(shí)，棧滿2. 為

20、了克服順序存儲(chǔ)分配固定空間所產(chǎn)生的溢出和空間浪費(fèi)問題?？刹捎面?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來存儲(chǔ)棧。鏈棧是沒有附加頭結(jié)點(diǎn)的運(yùn)算受限的單鏈表。棧頂指針就是鏈表的頭指針。順序隊(duì)列的根本操作鏈棧中的結(jié)點(diǎn)是動(dòng)態(tài)分配的，所以可以不考慮上溢，無須定義StackFull 運(yùn)算棧的一個(gè)重要應(yīng)用是實(shí)現(xiàn)遞歸，直接調(diào)用自己或間接調(diào)用自己的函數(shù)。3. 隊(duì)列Queue是只允許在一端進(jìn)行插入，而在另一端進(jìn)行刪除 的運(yùn)算受限的線性表。允許刪除的一端稱為隊(duì)頭Front ,允許插入的一端稱為 隊(duì)尾Rear,當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列，隊(duì)列亦稱作先進(jìn)先出First In First Out的線性表，簡稱為FIFO表。隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)稱為順序隊(duì)

21、列，順序隊(duì)列實(shí)際上是一個(gè)受限的線性表。 入隊(duì)時(shí)：將新元素插入 rear所指的位置，然后將 rear加1。 出隊(duì)時(shí)：刪去front所指的元素，然后將 front加1并返回被刪元素。當(dāng)頭尾指針相等時(shí)，隊(duì)列為空。在非空隊(duì)列里，頭指針始終指向隊(duì)頭元素，而隊(duì)尾指針始終指向隊(duì)尾元素的下一位置。而棧頂指針指向棧頂元素。4. 循環(huán)隊(duì)列：為充分利用數(shù)組空間，克服上溢，可將數(shù)組空間想象為一個(gè)環(huán)狀空間，并稱這種環(huán)狀數(shù)組表示的隊(duì)列 為循環(huán)隊(duì)列。循環(huán)隊(duì)列中進(jìn)行出隊(duì)、入隊(duì)操作時(shí)，頭尾指針仍要加1朝前移動(dòng)。只不過當(dāng)頭尾指針指向向量上界( QueueSize-1)時(shí)，其加1操作的結(jié)果是指向向量的下界0。這種循環(huán)意義下的加1操

22、作可以描述為： 方法一：if(i+1=QueueSize) i=0;/i表示 front 或 rearelse i+; 方法二-利用"模運(yùn)算i=(i+1)%QueueSize ；循環(huán)隊(duì)列中，由于入隊(duì)時(shí)尾指針向前追趕頭指針；出隊(duì)時(shí)頭指針向前追趕尾指針，造成隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。因此，無法通過條件Q.front=Q.rear來判別隊(duì)列是"空還是滿。解決這個(gè)問題的方法至少有三種： 另設(shè)一個(gè)標(biāo)志位以區(qū)別隊(duì)列是空還是滿； 設(shè)置一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素的總數(shù)(即隊(duì)列長度)。 少用一個(gè)元素的空間。約定入隊(duì)前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，假設(shè)相等那么認(rèn)為隊(duì)列滿即尾指針

23、Q.rear所指的單元始終為空。5. 循環(huán)隊(duì)列的根本運(yùn)算： 置隊(duì)空：Q->front=Q->rear=0; 判隊(duì)空：return Q->rear=Q->front; 判隊(duì)滿：return (Q->rear+1)%QueueSize=Q->front; 入隊(duì) Q->dataQ->rear=x;/新元素插入隊(duì)尾Q->rear=(Q->rear+1)%QueueSize; 出隊(duì) temp=Q->dataQ->front;Q->front=(Q->front+1)%QueueSize;/ 循環(huán)意義下的頭指針加1retu

24、rn temp; 取隊(duì)頭元素return Q->dataQ->fro nt;6. 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡稱為鏈隊(duì)列。它是限制僅在表頭刪除和表尾插入的單鏈表。為了簡化處理，在隊(duì)頭結(jié)點(diǎn)之前附加一個(gè)頭結(jié)點(diǎn)，并設(shè)隊(duì)頭指針指向此結(jié)點(diǎn)。UHfroTl AQf如N |-H.卜H1H<b)那空盤列i.i :川小心計(jì)鏈隊(duì)列的根本運(yùn)算：(帶頭結(jié)點(diǎn))(1) 構(gòu)造空隊(duì)：Q->rear=Q->front ； Q->rear->next=NULL;(2) 判隊(duì)空：return Q->rear=Q->fro nt;( 3 ) 入隊(duì)： QueueNode *p=(Queue

25、Node *)malloc(sizeof(QueueNode);/申請新結(jié)點(diǎn)p->data=x; p->next=NULL;Q->rear->next=p; /*p 鏈到原隊(duì)尾結(jié)點(diǎn)后 Q->rear=p; / 隊(duì)尾指針指向新的尾(4) 出隊(duì)：當(dāng)隊(duì)列長度大于 1 時(shí)，只需修改頭結(jié)點(diǎn)指針，尾指針不變 s=Q->front->next; Q->front->next=s->next;x=s->data; free(s); return x; 當(dāng)隊(duì)列長度等于 1 時(shí)，不僅要修改頭結(jié)點(diǎn)指針，還要修改尾指針 s=Q->front-&g

26、t;next; Q->front->next=NULL; Q->rear=Q->front;x=s->data; free(s); return x;( 5) 取隊(duì)頭元素： return Q->front->next->data;因?yàn)橛蓄^結(jié)點(diǎn)，所以用了 next 和鏈棧類似，無須考慮判隊(duì)滿的運(yùn)算及上溢。 在出隊(duì)算法中，一般只需修改隊(duì)頭指針。但當(dāng)原隊(duì)中只有一個(gè)結(jié)點(diǎn)時(shí)，該結(jié)點(diǎn)既是隊(duì)頭也是隊(duì)尾，故刪去此結(jié)點(diǎn) 時(shí)亦需修改尾指針，且刪去此結(jié)點(diǎn)后隊(duì)列變空。7. 用計(jì)算機(jī)來處理計(jì)算算術(shù)表達(dá)式問題，首先要解決的問題是如何將人們習(xí)慣書寫的中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式

27、。第四章 多維數(shù)組和廣義表1. 數(shù)組的順序存儲(chǔ)方式 : 一般采用順序存儲(chǔ)方法表示數(shù)組。1行優(yōu)先順序a 11 ,a 12,a in,a 21 ,a 22,a2n,ami,am2,，amn2列優(yōu)先順序a 11,a 21,a m1,a 12,a 22,am2,a1 n,a2n,，amnPascal和C語言是按行優(yōu)先順序存儲(chǔ)的，而Fortran語言是按列優(yōu)先順序存儲(chǔ)的。按行優(yōu)先順序存儲(chǔ)的二維數(shù)組Amn地址計(jì)算公式LOC(aj )=L0C(a11)+(i-1) x n +j -1 xd (注：此公式下界為 1，如下界為0，那么公式變?yōu)閕 x n +j )按列優(yōu)先順序存儲(chǔ)的二維數(shù)組Amn地址計(jì)算公式LOC

28、(a )=LOC(an)+(j-1) x m+i-1 xd(注：此公式下界為 1，如下界為0，那么公式變?yōu)閖 x m+i)按行優(yōu)先順序存儲(chǔ)的三維數(shù)組Amnp地址計(jì)算公式LOC(aijk)=LOC(a111)+(i-1)xnxp+(j -1)xp+k-1xd (注： 此公式下界為 1， 如下界為 0， 那么公式變?yōu)閕 x nx p+j x p+k)2. 為了節(jié)省存儲(chǔ)空間，可以對矩陣中有許多值相同或值為零的元素的矩陣，采用壓縮存儲(chǔ)。 特殊矩陣是指相同值的元素或零元素在矩陣中的分布有一定的規(guī)律。常見的有對稱矩陣、三角矩陣。(1 )對稱矩陣 在一個(gè)n階方陣A中，假設(shè)元素滿足下述性質(zhì)：a ij =aji

29、 0< i , j <n -1稱為 n 階對稱矩陣，它的元素是關(guān)于主對角線對稱的，所以只需要存儲(chǔ)矩陣上三角或下三角元素即可，讓兩個(gè) 對稱的元素共享一個(gè)存儲(chǔ)空間。矩陣元素a。和數(shù)組元素sa【k】之間的關(guān)系是k=i x(i+1)/2+j i >j 0<k<n(n+1) /2-1k=jx(j+1)/2+i i vj 0<k<n(n+1) /2-1對稱矩陣的地址計(jì)算公式：LOC(aj )=LOC(sa0)+l x (I+1) /2+J x d,其中 l=max(i,j) , J=min(i,j)(2) 三角矩陣： 以主對角線劃分，三角矩陣有上三角和下三角兩種。

30、上三角矩陣是指它的下三角(不包括主角線 )中的元素均為常數(shù) c或零；下三角矩陣的主對角線上方均為常數(shù)c或零。一般情況，三角矩陣的常數(shù)c均為零。三角矩陣的壓縮存儲(chǔ)：三角矩陣中的重復(fù)元素c可共享一個(gè)存儲(chǔ)空間，其余的元素正好有nx(n+1) /2個(gè)，因此，三角矩陣可壓縮存儲(chǔ)在一維數(shù)組san(n+1)/2+1中，其中c存放在數(shù)組的最后一個(gè)元素中。 上三角矩陣中 aij 和 sak 之間的對應(yīng)關(guān)系k=i x (2n -i+1)/2+j-i 當(dāng) i wj k=nx(n+1)/2 當(dāng) i >j 下三角矩陣中 aij 和 sak 之間的對應(yīng)關(guān)系k=i x (i+1) /2+j 當(dāng) i >j k=n

31、x(n+1)/2 當(dāng) i v j三角矩陣的壓縮存儲(chǔ)結(jié)構(gòu)是隨機(jī)存取結(jié)構(gòu) 。3. 稀疏矩陣：設(shè)矩陣Am沖有s個(gè)非零元素，假設(shè)s遠(yuǎn)遠(yuǎn)小于矩陣元素的總數(shù)，那么稱A為稀疏矩陣。為了節(jié)省存儲(chǔ)單元，可用壓縮存儲(chǔ)方法只存儲(chǔ)非零元素。由于非零元素的分布一般是沒有規(guī)律的,因此在存儲(chǔ)非零元素的同時(shí),還必須 存儲(chǔ)非零元素所在的行、列位置,所以可用三元組 (i , j, aij )來確定非零元素。稀疏矩陣進(jìn)行壓縮存儲(chǔ)通常有兩類方法： 順序存儲(chǔ) (三元組表 )和鏈?zhǔn)酱鎯?chǔ) (十字鏈表 )。稀疏矩陣的壓縮存儲(chǔ)會(huì)失去 隨機(jī)存取功能。稀吹艇曲*審曲三冗釧醫(yī)舸4. 廣義表是線性表的推廣，又稱列表。廣義表是n(n >0)個(gè)元素

32、ai, a2,，a,，an的有限序列。其中 ai或者是原子或者是一個(gè)廣義表。 廣義表通常用圓括號(hào)括起來，用逗號(hào)分隔其中的元素。 為了區(qū)分原子和廣義表，書寫時(shí)用大寫字母表示廣義表，用小寫字母表示 原子。 假設(shè)廣義表Ls非空(n > 1)，貝U ai是LS的表頭，其余元素組成的表(ai, a2,，an)稱為Ls的表尾。 廣義表具有遞歸和共享的性質(zhì)廣義表的深度：一個(gè)表展開后所含括號(hào)的層數(shù)稱為廣義表的深度。19.廣義表是一種多層次的線性結(jié)構(gòu)，實(shí)際上這就是一種樹形結(jié)構(gòu)。廣義表的兩個(gè)特殊的根本運(yùn)算：取表頭head(Ls)和取表尾tail(Ls).任何一個(gè)非空廣義表的表頭可以是原子，也可以是子表，而其

33、表尾必定是子表。head=(a , b)=a , tail(a , b)=(b)對非空表 A和(y)，也可繼續(xù)分解。注意：廣義表()和()不同。前者是長度為0的空表，對其不能做求表頭和表尾的運(yùn)算；而后者是長度為I的由空表作元素的廣義表，可以分解得到的表頭和表尾均是空表()。廣義表是一種有層次的非線性結(jié)構(gòu)，通常采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，每個(gè)元素用一個(gè)結(jié)點(diǎn)表示，結(jié)點(diǎn)由3個(gè)域構(gòu)成，其中一個(gè)是tag標(biāo)志位，用來區(qū)分結(jié)點(diǎn)是原子還是子表，當(dāng)tag為零時(shí)結(jié)點(diǎn)是子表，第二個(gè)域?yàn)?slink，用以存放子表的地址；當(dāng)tag為1時(shí)結(jié)點(diǎn)是原子，第二個(gè)域?yàn)?data，用以存放元素值。第五章樹和二叉樹1. 樹的表示法：最常用的是

34、樹形圖表示法；還有3種嵌套集合、凹形、廣義表。樹結(jié)構(gòu)的根本術(shù)語(1 )結(jié)點(diǎn)的度(Degree)樹中的一個(gè)結(jié)點(diǎn)擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度(Degree)。一棵樹的度是指該樹中結(jié)點(diǎn)的最大度數(shù)。度為零的結(jié)點(diǎn)稱為 葉子(Leaf)或終端結(jié)點(diǎn)。度不為零的結(jié)點(diǎn)稱 分支結(jié)點(diǎn)或非終端結(jié)點(diǎn)。 除根結(jié)點(diǎn)之外的分支結(jié)點(diǎn)統(tǒng)稱為內(nèi)部結(jié)點(diǎn)。根結(jié)點(diǎn)又稱為開始結(jié)點(diǎn)。(2)路徑(path )假設(shè)樹中存在一個(gè)結(jié)點(diǎn)序列k1,k2,，ki,使得ki是ki+1的雙親(1 <i<j)，那么稱該結(jié)點(diǎn)序列是從kl到kj的一條路徑(Path)。一個(gè)結(jié)點(diǎn)的祖先是從根結(jié)點(diǎn)到該結(jié)點(diǎn)路徑上所經(jīng)過的所有結(jié)點(diǎn)，而一個(gè)結(jié)點(diǎn)的子孫那么是以該結(jié)點(diǎn)為

35、根的子樹中的所 有結(jié)點(diǎn)。結(jié)點(diǎn)的層數(shù)(Level)從根起算：根的層數(shù)為1,其余結(jié)點(diǎn)的層數(shù)等于其雙親結(jié)點(diǎn)的層數(shù)加1。雙親在同一層的結(jié)點(diǎn)互為堂兄弟。樹中結(jié)點(diǎn)的最大層數(shù)稱為樹的高度(Height)或深度(Depth)。假設(shè)將樹中每個(gè)結(jié)點(diǎn)的各子樹看成是從左到右有次序的(即不能互換)，那么稱該樹為有序樹(OrderedTree);否那么稱為無序樹(UnoderedTree)。假設(shè)不特別指明，一般討論的樹都是有序樹。森林(Forest)是m(詳0)棵互不相交的樹的集合。樹和森林的概念相近。刪去一棵樹的根， 就得到一個(gè)森林；反之，加上一個(gè)結(jié)點(diǎn)作樹根，森林就變?yōu)橐豢脴洹?. 二叉樹與度數(shù)為 2的有序樹不同：在有

36、序樹中，雖然一個(gè)結(jié)點(diǎn)的孩子之間是有左右次序的，但是假設(shè)該結(jié)點(diǎn)只有一 個(gè)孩子，就無須區(qū)分其左右次序。而在二叉樹中，即使是一個(gè)孩子也有左右之分。二叉樹的性質(zhì)：性質(zhì)1二叉樹第i層上的結(jié)點(diǎn)數(shù)目最多為 2i-1 (i > 1)。例如5層的二叉樹，第5層上的結(jié)點(diǎn)數(shù)目最多為24=16k5性質(zhì)2深度為k的二叉樹至多有2 -1個(gè)結(jié)點(diǎn)(k > 1)。例如深度為 5的二叉樹，至多有 2 -仁31個(gè)結(jié)點(diǎn)性質(zhì)3在任意-棵二叉樹中，假設(shè)終端結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)數(shù)為n2,那么no=n?+1。例如一棵深度為4的二叉樹(a),其終端結(jié)點(diǎn)數(shù)no為8,度為2的結(jié)點(diǎn)樹為7,那么8=7+1, n°=n2

37、+1成立(b)其終端結(jié)點(diǎn)數(shù)no為6,度為2的結(jié)點(diǎn)樹為5,那么6=5+1, n°=n2+1成立1'和冷勺KMIh-kiltd-ImI «1 '"線索，這種加上線索的二叉鏈表稱為線索線索鏈表的結(jié)點(diǎn)結(jié)構(gòu):滿二叉樹：一棵深度為k且有2k-1個(gè)結(jié)點(diǎn)的二又樹稱為滿二叉樹。滿二叉樹的特點(diǎn):(1)每一層上的結(jié)點(diǎn)數(shù)都到達(dá)最大值。即對給定的高度，它是具有最多結(jié)點(diǎn)數(shù)的二叉樹。(2)滿二叉樹中不存在度數(shù)為1的結(jié)點(diǎn)，每個(gè)分支結(jié)點(diǎn)均有兩棵高度相同的子樹，且樹葉都在最下一層上。完全二叉樹：假設(shè)一棵深度為k的二叉樹，其前 k-1層是一棵滿二叉樹，而最下面一層上的結(jié)點(diǎn)都集中在該層最

38、左邊的假設(shè)干位置上，那么此二叉樹稱為完全二叉樹。特點(diǎn)：(1) 滿二叉樹是完全二叉樹，完全二叉樹不一定是滿二叉樹。(2) 在滿二叉樹的最下一層上，從最右邊開始連續(xù)刪去假設(shè)干結(jié)點(diǎn)后得到的二叉樹仍然是一棵完全二叉樹。(3) 在完全二叉樹中，假設(shè)某個(gè)結(jié)點(diǎn)沒有左孩子，那么它一定沒有右孩子，即該結(jié)點(diǎn)必是葉結(jié)點(diǎn)。性質(zhì)4具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為。？logn ?+1或？log(n+1) ?例，具有 100 個(gè)結(jié)點(diǎn)的完全二叉樹的深度為：？lg100 ?+1=7,26=64 2 7=128 所以？lg100 ?=6,?lg(100+1) ?=74. 完全二叉樹的編號(hào)特點(diǎn)：完全二叉樹中除最下面一層外，各層都充

39、滿了結(jié)點(diǎn)。每一層的結(jié)點(diǎn)個(gè)數(shù)恰好是上一層結(jié) 點(diǎn)個(gè)數(shù)的2倍。從一個(gè)結(jié)點(diǎn)的編號(hào)就可推得其雙親，左、右孩子等結(jié)點(diǎn)的編號(hào)。編號(hào)從0開始 假設(shè)i=0，貝U q為根結(jié)點(diǎn)，無雙親；否那么，qi的雙親編號(hào)為？(i-1)/2 ?。 假設(shè)2i+1<n，那么qi的左孩子的編號(hào)是 2i+1 ;否那么，qi無左孩子，即q必定是葉子。 假設(shè)2i+2<n，那么qi的右孩子的編號(hào)是 2i+2 ;否那么，q無右孩子。對于完全二叉樹而言，使用順序存儲(chǔ)結(jié)構(gòu)既簡單又節(jié)省存儲(chǔ)空間。但對于一般二叉樹來說，采用順序存儲(chǔ)時(shí)，為了 使用結(jié)點(diǎn)在數(shù)組中的相對位置來表示結(jié)點(diǎn)之間的邏輯關(guān)系，就必須增加一些虛結(jié)點(diǎn)使其成為完全二叉樹的形式。5鏈

40、式存儲(chǔ)結(jié)構(gòu)：二叉樹的每個(gè)結(jié)點(diǎn)最多有兩個(gè)孩子。用鏈接方式存儲(chǔ)二叉樹時(shí)，每個(gè)結(jié)點(diǎn)除了存儲(chǔ)結(jié)點(diǎn)本身的數(shù)據(jù)外，還應(yīng)設(shè)置兩個(gè)指針域lchild和rchild，分別指向該結(jié)點(diǎn)的左孩子和右孩子。結(jié)點(diǎn)的結(jié)構(gòu)為:二叉鏈表是一種常用的二叉樹存儲(chǔ)結(jié)構(gòu)。建立二叉鏈表方法：a、按廣義表方法，靠近左括號(hào)的結(jié)點(diǎn)是在左子樹上，而逗號(hào)右邊結(jié)點(diǎn)是在右子樹上。b、按完全二叉樹的層次順序建立結(jié)點(diǎn)。具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有 2n個(gè)指針域。其中有 n-1個(gè)用來指示結(jié)點(diǎn)的左、右孩子，其余的n+1個(gè)為空。二叉樹遍歷算法中的遞歸終止條件是二叉樹為空。中序遍歷的遞歸算法定義：(1)遍歷左子樹；(2)訪問根結(jié)點(diǎn)；遍歷右子樹。先序遍歷的遞歸算

41、法定義：(1)訪問根結(jié)點(diǎn)；(2)遍歷左子樹；遍歷右子樹。后序遍歷得遞歸算法定義：(1)遍歷左子樹；(2)遍歷右子樹；訪問根結(jié)點(diǎn)。遞歸工作棧中包括兩項(xiàng)：一項(xiàng)為哪一項(xiàng)遞歸調(diào)用的語句編號(hào)，另一項(xiàng)那么是指向根結(jié)點(diǎn)的指針。一棵二叉樹的前序和中序遍歷序列或中序和后序遍歷序列，可唯一確定一棵二叉樹。具體方法如下： 首先根據(jù)前序或后序遍歷序列確定二叉樹的各子樹的的根，然后根據(jù)中序遍歷序列確定各子樹根的左右子樹。6. 線索二叉樹：n個(gè)結(jié)點(diǎn)的二叉鏈表必定存在n+1個(gè)空指針域，可以利用這些空指針域，存放指向結(jié)點(diǎn)在某種遍歷次序下的前趨和后繼結(jié)點(diǎn)的指針，這種指向前驅(qū)和后繼結(jié)點(diǎn)的指針稱為鏈表，相應(yīng)的二叉樹稱為 線索二叉樹

42、(ThreadedBinaryTree)其中:ltag 和rtag是增加的兩個(gè)標(biāo)志域，用來區(qū)分結(jié)點(diǎn)的左、右指針 域是指向其左、右孩子的指針，還是指向其前趨或后繼的線索。圖中的實(shí)線表示指針，虛線表示線索。線索二叉樹中，一個(gè)結(jié)點(diǎn)是葉結(jié)點(diǎn)的充要條件為：左、右標(biāo)志均是1。7. 二叉樹的線索化：把對一棵二叉線索鏈表結(jié)構(gòu)中所有結(jié)點(diǎn)的空指針域按照某種遍歷次序加線索的過程稱為線索化。n個(gè)結(jié)點(diǎn)的二叉樹，線索化的算法時(shí)間復(fù)雜度和中序遍歷算法一樣，遞歸過程中對每結(jié)點(diǎn)僅做一次訪問。因此對于 為 0(n)。-,丨B0/ r11 |D1* k0E000| -、1H1丄11 r r8. 樹、森林到二叉樹的轉(zhuǎn)換：樹中每個(gè)結(jié)點(diǎn)

43、最多只有一個(gè)最左邊的孩子(長子)和一個(gè)右鄰的兄弟。將樹轉(zhuǎn)換成二叉樹：在所有兄弟結(jié)點(diǎn)之間加一道連線；對每個(gè)結(jié)點(diǎn)，除了保存與其長子的連線外，去掉該結(jié)點(diǎn) 與其它孩子的連線。由于樹根沒有兄弟，故樹轉(zhuǎn)化為二叉樹后，二叉樹的根結(jié)點(diǎn)的右子樹必為空。樹到二叉樹的轉(zhuǎn)換h罰A；D|1 J對*汁皓點(diǎn)，除了保S'jJC的長子的連錢外.點(diǎn)可用他孫子的將一個(gè)森林轉(zhuǎn)換為二叉樹將森林中的每棵樹轉(zhuǎn)化成二叉樹，然后再將二叉樹的根節(jié)點(diǎn)看做兄弟連在一起，形成一棵二叉樹講一涉；九豺飲樸中的何棵 樹箜沖二叉榔第二步為兄弟從左住右連在 起.就形脈丁一棵一義9.二叉樹到樹、森林的轉(zhuǎn)換方式是：假設(shè)二叉樹中結(jié)點(diǎn) x是雙親y的左孩子，那么

44、把 x的右孩子，右孩子的右孩子，都與y用連線連起來，最后去掉所有雙親到右孩子的連線。下標(biāo)JeLnpotent.ABCDFGIIIJ(J00113012 3 I S 6 7 « 910. 樹的存儲(chǔ)結(jié)構(gòu)：1. 雙親表示法：雙親鏈表表示法利用樹中每個(gè)結(jié)點(diǎn)的雙親唯一性， 在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，為每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指向其雙親的指針 pare nt ,惟一地表示任何-棵樹。1 雙親鏈表表示法的實(shí)現(xiàn)分析：E和F所在結(jié)點(diǎn)的雙親域是 1，它們的雙親結(jié)點(diǎn)在向量中的位 置是1，即卩B是它們的雙親。注意： 根無雙親，其pare nt域?yàn)?1。雙親鏈表表示法中指針 pare nt向上鏈接，適合求指定結(jié) 點(diǎn)的雙親

45、或祖先包括根；求指定結(jié)點(diǎn)的孩子或其它后代時(shí)，可能 要遍歷整個(gè)數(shù)組。2. 孩子鏈表法：孩子鏈表表示法是為樹中每個(gè)結(jié)點(diǎn)設(shè)置一個(gè)孩子鏈 表，并將這些結(jié)點(diǎn)及相應(yīng)的孩子鏈表的頭指針存放在一個(gè)向量中。roo t =*OukiA I riithili2十Annr"4181 -j-rirrTh、："：嘰'J «(1 'i'l-Jl. .''L-bd孩子兄弟鏈表表示。注意： 孩子結(jié)點(diǎn)的數(shù)據(jù)域僅存放了它們在向量空間的序號(hào)。 與雙親鏈表表示法相反，孩子鏈表表示便于實(shí)現(xiàn)涉及孩子及其子孫的運(yùn)算，但不便于實(shí)現(xiàn)與雙親有關(guān)的運(yùn)算。 將雙親鏈表表示法和孩子鏈

46、表表示法結(jié)合起來，可形成雙親孩子鏈表表示法。3. 孩子兄弟表示法：在存儲(chǔ)結(jié)點(diǎn)信息的同時(shí)，附加兩個(gè)分別指向該結(jié)點(diǎn)最左孩子和右鄰兄弟的指針域，即可得樹的這種存儲(chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是：它和二叉樹的二叉鏈 表表示完全一樣?？衫枚鏄涞乃惴▉韺?shí)現(xiàn)對樹的操 作。11. 樹的遍歷:般都只給出兩種次序遍歷樹的方法：前序先根次序遍歷和后序后根次序遍歷。前序遍歷一棵樹等價(jià)于前序遍歷該樹對應(yīng)的二叉樹 后序遍歷一棵樹等價(jià)于中序遍歷該樹對應(yīng)的二叉樹。對下面a圖中所示的森林進(jìn)行前序遍歷和后序遍歷，那么得到該森林的前序序列和后序序列分別為ABCDEFIGJH和BDCAIFJGHE而b圖所示二叉樹的前序序列和中序序列也分別為A

47、BCDEFIGJH BDCAIFJGHE 前序遍歷森林等同于前序遍歷該森林對應(yīng)的二叉樹 后序遍歷森林等同于中序遍歷該森林對應(yīng)的二叉樹12. 從根結(jié)點(diǎn)到某結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積稱為該結(jié)點(diǎn)的帶權(quán)路徑長度，樹種所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和稱為樹的帶權(quán)路徑長度。帶權(quán)路徑長度WPL最小的二叉樹稱為哈夫曼樹或最優(yōu)二叉樹。哈夫曼樹不一定是二叉樹。哈夫曼樹又稱為最優(yōu)樹，是一類帶權(quán)路徑長度最短 的樹。完全二叉樹就是這種 路徑長度最短的二叉樹。 只有葉結(jié)點(diǎn)上的權(quán)值均相同時(shí)，完全二叉樹一定是最優(yōu)二叉樹，否那么完全二叉樹不一定是最優(yōu)二叉樹。 最優(yōu)二叉樹中，權(quán)越大的葉子離根越近。 最優(yōu)二叉樹的 形態(tài)不唯

48、一， WPL最小。13哈夫曼算法：根本思想是：(1)根據(jù)給定的n個(gè)權(quán)值w ,wz,，wn構(gòu)成n棵二叉樹的森林F=Ti,T2,，Tn，其中每棵二叉樹T中都只有一個(gè)權(quán)值為 w的根結(jié)點(diǎn)，其左右子樹均空。(2) 在森林F中選出兩棵根結(jié)點(diǎn)權(quán)值最小的樹 (當(dāng)這樣的樹不止兩棵樹時(shí)，可以從中任選兩棵)，將這兩棵樹合并成一棵新樹，為了保證新樹仍是二叉樹，需要增加一個(gè)新結(jié)點(diǎn)作為新樹的根，并將所選的兩棵樹的根分別作為新根的左右孩子(誰左，誰右無關(guān)緊要)，將這兩個(gè)孩子的權(quán)值之和作為新樹根的權(quán)值。(3) 對新的森林F重復(fù)，直到森林F中只剩下一棵樹為止。這棵樹便是哈夫曼樹。 注意： 初始森林中的n棵二叉樹，每棵樹有一個(gè)孤

49、立的結(jié)點(diǎn)，它們既是根，又是葉子 n個(gè)葉子的哈夫曼樹要經(jīng)過n-1次合并，產(chǎn)生n-1個(gè)新結(jié)點(diǎn)。最終求得的哈夫曼樹中共有2n-1個(gè)結(jié)點(diǎn)。 哈夫曼樹是嚴(yán)格的二叉樹，沒有度數(shù)為1的分支結(jié)點(diǎn)。14哈夫曼編碼：數(shù)據(jù)壓縮過程稱為編碼，反之，解壓縮的過程稱為解碼。設(shè)計(jì)一種長短不等的編碼，那么必須保證任一字符的編碼都不是另一個(gè)字符編碼的前綴，這種編碼稱為前綴編碼?？梢岳枚鏄鋪碓O(shè)計(jì)二進(jìn)制的前綴編碼，其左分支表示字符0，右分支表示字符1,那么以根結(jié)點(diǎn)到葉結(jié)點(diǎn)路徑上的分支字符組成的串作為該葉節(jié)點(diǎn)的字符編碼。因此設(shè)計(jì)電文總長最短的二進(jìn)制前綴編碼，就是以n種字符出現(xiàn)的頻率作為權(quán)構(gòu)造一棵哈夫曼樹，由哈夫曼樹求得的編碼就是

50、哈夫曼編碼。譯碼過程是從樹根結(jié)點(diǎn)出發(fā)，逐個(gè)讀入電文中的二進(jìn)制碼。第六章圖1. 圖G由兩個(gè)集合構(gòu)成，頂點(diǎn)集合和邊集合，也可以圖G只有頂點(diǎn)而沒有邊。用尖括號(hào)表示圖的有向邊<Vi,Vj>,有向邊又稱為弧，起點(diǎn)稱為弧尾，終點(diǎn)稱為弧頭。無向圖的頂點(diǎn)對用圓括號(hào)表示(Vi,V j)。在無向圖中，稱 Vi和Vj相鄰接，在有向圖中稱頂點(diǎn)Vi鄰接到Vj，頂點(diǎn)Vj鄰接于Vi在無向圖中，n的取值范圍是0-n(n-1)/2 ，將具有n(n-1)/2 條邊的無向圖稱為無向完全圖。 在有向圖中，n的取值范圍是0-n(n-1)，將具有n(n-1)條邊的有向圖稱為有向完全圖。無向圖中，頂點(diǎn)的度定義為以該頂點(diǎn)為一個(gè)端

51、點(diǎn)的邊的數(shù)目，有向圖的度等于出度和入度之和。在無向圖中，任意兩頂點(diǎn)都有路徑，那么稱兩頂點(diǎn)連通。假設(shè)圖G中的任意兩個(gè)頂點(diǎn)都連通，稱G為連通圖。無向圖的極大連通子圖稱為連通分量，顯然，任何連通圖的連通分量只有一個(gè)，即其自身，而非連通的無向圖有多個(gè)連通分量。在有向圖中，圖 G中任意兩頂點(diǎn)連通，稱為強(qiáng)連通圖，極大連通子圖稱為強(qiáng)連通分量。假設(shè)在一個(gè)圖的每條邊上標(biāo)上某種數(shù)值，該數(shù)值稱為該邊的權(quán)。邊上帶權(quán)的圖稱為帶權(quán)圖，帶權(quán)的連通圖稱為網(wǎng)絡(luò)。2. 圖的存儲(chǔ)結(jié)構(gòu)：鄰接矩陣和鄰接表表示法。圖的頂點(diǎn)編號(hào)從0開始。鄰接矩陣表示法：<Vi ,v j>或(v i ,v j)是邊，那么值為1，不是邊那么值為

52、0。無向圖的鄰接矩陣是按主對角線對稱的。假設(shè)G是帶權(quán)圖，只要把 1換成相應(yīng)邊上的權(quán)值即可，0的位置上可以不動(dòng)或?qū)⑵鋼Q成無窮大表示。無向圖的鄰接矩陣表示法可以僅存儲(chǔ)主對角線以下的元素，時(shí)間復(fù)雜度為0( n2)鄰接表表示法： 鄰接表是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。將無向圖的鄰接表稱為邊表，將有向圖的鄰接表稱為出邊表， 將鄰接表的表頭向量稱為頂點(diǎn)表。假設(shè)無向圖有n個(gè)頂點(diǎn)和e條邊，那么它的鄰接表共有n個(gè)頭結(jié)點(diǎn)和2e個(gè)表結(jié)點(diǎn)。建立鄰接表的時(shí)間復(fù)雜度是0(n+e)。圖的鄰接表表示不是唯一的，這是因?yàn)樵诿總€(gè)頂點(diǎn)的鄰接表中，各邊結(jié)點(diǎn)的鏈接次序可以是任意的，其具體鏈接次序與邊的輸入次序和生成算法有關(guān)。3. 圖的遍歷：遍

53、歷圖的算法是求解圖的連通性、圖的拓?fù)渑判虻人惴ǖ母住?圖的遍歷常用的是深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷兩種方法。深度優(yōu)先搜索遍歷(DFS)類似于前序(先根)遍歷。按訪問頂點(diǎn)的先后次序得到的頂點(diǎn)序列稱為圖的深度優(yōu)先遍歷序 列，或簡稱為 DFS序列。共需要搜索 n2個(gè)矩陣元素，時(shí)間復(fù)雜度為鄰接矩陣0(n2)或鄰接表0(n+e)。1無梅圖仃:C起點(diǎn)仃湖涇度此先搜常和力過呻示總廣度優(yōu)先搜索遍歷(BFS)類似于樹的按層次遍歷，先被訪問的頂點(diǎn)，其鄰接點(diǎn)也先被訪問，就是先進(jìn)先出。 時(shí)間復(fù)雜度為鄰接矩陣 0(n2)或鄰接表0(n+e)，空間復(fù)雜度都是 0(n)。fl *第1屈;轉(zhuǎn)"慮f攀西宗*4

54、. 生成樹是連通圖的包含圖中所有頂點(diǎn)的一個(gè)極小連通子圖，一個(gè)圖的極小連通子圖恰為一個(gè)無回路的連通圖，也 就是說，假設(shè)圖中任意添加一條邊，就會(huì)出現(xiàn)回路，假設(shè)去掉任意一條邊，都會(huì)使之成為非連通圖。因此，一個(gè)具有 n個(gè)頂點(diǎn)的生成樹有且僅有n-1條邊，但有n-1條邊的圖不一定是生成樹，同一個(gè)圖可以有不同的生成樹。生成樹定義為：假設(shè)從圖的某頂點(diǎn)出發(fā)，可以系統(tǒng)的訪問到圖的所有頂點(diǎn)，那么遍歷時(shí)經(jīng)過的邊和圖的所有頂點(diǎn)所構(gòu) 成的子圖，稱為該圖的生成樹。最小生成樹：圖的生成樹不唯一，把權(quán)值最小的生成樹稱為最小生成樹(MST。構(gòu)造最小生成樹的算法：普里姆Prim算法的時(shí)間復(fù)雜度為0( n2)與網(wǎng)中邊數(shù)無關(guān)適于稠密圖

55、?？唆斔箍朘ruskal算法的時(shí)間復(fù)雜度為 0( eloge )，主要取決于邊數(shù)，較適合于稀疏圖?！纠?3】利用艸里姆算達(dá)給山求圖6J7(a所示的無向網(wǎng)絡(luò)的最小生成樹的過程。5. 最短路徑：Dijkstra 迪杰斯特拉算法，提出了按路徑長度遞增的順序產(chǎn)生諸頂點(diǎn)的最短路徑算法。拓?fù)渑判颍鹤庸こ谭Q為活動(dòng)，頂點(diǎn)代表活動(dòng)，有向邊代表活動(dòng)的先后關(guān)系。這樣的有向無環(huán)圖DAG稱為頂點(diǎn)活動(dòng)網(wǎng)，簡稱為AOV網(wǎng)。將有向無環(huán)圖G中所有頂點(diǎn)排成一個(gè)線性序列，假設(shè)<u, v> E (G)，那么在線性序列u在v之前，這種線性序列稱為拓?fù)湫蛄小Ｓ葾OV網(wǎng)構(gòu)造拓?fù)湫蛄械倪^程稱為拓?fù)渑判?。檢測的方法是：對有向圖構(gòu)造其頂點(diǎn)的拓?fù)湫蛄?，假設(shè)網(wǎng)中所有頂點(diǎn)都在他的拓?fù)湫蛄兄校敲碅OV網(wǎng)必定不存在環(huán)。AOV網(wǎng)的拓?fù)湫蛄胁皇俏ㄒ坏摹Ｍ負(fù)渑判虻拿枋鏊枷耄篴、在有向圖中選一個(gè)沒有前趨 (入度為零)的頂點(diǎn)，且輸出之。b、從有向圖中刪除該頂點(diǎn) 及其與該頂點(diǎn)有關(guān)的所有邊。c、重復(fù)上述步驟，直到全部頂點(diǎn)都已輸出或圖中剩余的頂點(diǎn)中沒有前趨頂點(diǎn)為止。d、輸出剩余的無前趨結(jié)點(diǎn)。拓?fù)渑判驅(qū)嶋H上是對鄰接表表示的圖G