數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)

（a1,a2,…ai-1，ai,ai+1

，…,an）2.1

線性表的邏輯結(jié)構(gòu)1.線性表的定義：是n個(gè)數(shù)據(jù)元素的有限序列n=0時(shí)稱為數(shù)據(jù)元素線性起點(diǎn)ai的直接前趨ai的直接后繼下標(biāo)，是元素的序號(hào)，表示元素在表中的位置n為元素總個(gè)數(shù)，即表長空表線性終點(diǎn)線性表的抽象數(shù)據(jù)類型的定義：

ADTList{

數(shù)據(jù)對(duì)象：D={ai|ai∈Elemset,i=1,2,…,n,n≥0}

數(shù)據(jù)關(guān)系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}

基本操作：

InitList(&L)

操作結(jié)果：構(gòu)造一個(gè)空的線性表LDestroyList(&L)

初始條件：線性表已存在操作結(jié)果：銷毀線性表L

2.2.1順序表的表示用一組地址連續(xù)的存儲(chǔ)單元依次存儲(chǔ)線性表的元素，可通過數(shù)組來實(shí)現(xiàn)。把邏輯上相鄰的數(shù)據(jù)元素存儲(chǔ)在物理上相鄰的存儲(chǔ)單元中的存儲(chǔ)結(jié)構(gòu)。線性表的順序表示又稱為順序存儲(chǔ)結(jié)構(gòu)或順序映像。順序存儲(chǔ)定義：順序存儲(chǔ)方法：簡言之，邏輯上相鄰，物理上也相鄰線性表順序存儲(chǔ)特點(diǎn)邏輯上相鄰的數(shù)據(jù)元素，其物理上也相鄰；若已知表中首元素在存儲(chǔ)器中的位置，則其他元素存放位置亦可求出（利用數(shù)組下標(biāo)）。計(jì)算方法是（參見存儲(chǔ)結(jié)構(gòu)示意圖）：設(shè)首元素a1的存放地址為LOC(a1)（稱為首地址），設(shè)每個(gè)元素占用存儲(chǔ)空間（地址長度）為L字節(jié)，則表中任一數(shù)據(jù)元素的存放地址為：

LOC(ai)=LOC(a1)+L*（i-1）

LOC(ai+1)=LOC(ai)+L線性表的順序存儲(chǔ)結(jié)構(gòu)示意圖a1a2……aiai+1……an

地址內(nèi)容元素在表中的位序1i2n空閑區(qū)i+1Lb=LOC(a1)b+Lb+(i-1)Lb+(n-1)Lb+(max-1)L例4：一個(gè)一維數(shù)組Ｍ，下標(biāo)的范圍是０到９，每個(gè)數(shù)組元素用相鄰的５個(gè)字節(jié)存儲(chǔ)。存儲(chǔ)器按字節(jié)編址，設(shè)存儲(chǔ)數(shù)組元素Ｍ[０]的第一個(gè)字節(jié)的地址是98，則Ｍ[３]的第一個(gè)字節(jié)的地址是113因此：LOC(M[3])=98+5×(3-0)=113解：地址計(jì)算通式為：LOC(ai)=LOC(a1)+L*（i-1）線性表的順序存儲(chǔ)結(jié)構(gòu)定義（靜態(tài)）#defineMAXSIZE100typedefstruct{ElemTypeelem[MAXSIZE];//元素?cái)?shù)組intlength;//當(dāng)前表長}SqList;…….elemlengthSqListL;//聲明L順序表L:inta;a:本節(jié)小結(jié)線性表順序存儲(chǔ)結(jié)構(gòu)特點(diǎn)：邏輯關(guān)系上相鄰的兩個(gè)元素在物理存儲(chǔ)位置上也相鄰；優(yōu)點(diǎn)：可以隨機(jī)存取表中任一元素O(1)；存儲(chǔ)空間使用緊湊缺點(diǎn)：在插入，刪除某一元素時(shí)，需要移動(dòng)大量元素O(n);預(yù)先分配空間需按最大空間分配，利用不充分;表容量難以擴(kuò)充為克服這一缺點(diǎn)，我們引入另一種存儲(chǔ)形式：鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)見2.3節(jié)2.3線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.3.1鏈表的表示2.3.2鏈表的實(shí)現(xiàn)2.3.3鏈表的運(yùn)算效率分析本節(jié)小結(jié)2.3.1鏈表的表示用一組任意的存儲(chǔ)單元存儲(chǔ)線性表的數(shù)據(jù)元素利用指針實(shí)現(xiàn)了用不相鄰的存儲(chǔ)單元存放邏輯上相鄰的元素每個(gè)數(shù)據(jù)元素ai，除存儲(chǔ)本身信息外，還需存儲(chǔ)其直接后繼的信息結(jié)點(diǎn)

數(shù)據(jù)域：元素本身信息指針域：指示直接后繼的存儲(chǔ)位置數(shù)據(jù)域指針域結(jié)點(diǎn)與鏈?zhǔn)酱鎯?chǔ)有關(guān)的術(shù)語：1、結(jié)點(diǎn)：數(shù)據(jù)元素的存儲(chǔ)映像。由數(shù)據(jù)域和指針域兩部分組成；2、鏈表：n個(gè)結(jié)點(diǎn)由指針鏈組成一個(gè)鏈表。它是線性表的鏈?zhǔn)酱鎯?chǔ)映像，稱為線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：

結(jié)點(diǎn)只有一個(gè)指針域的鏈表，稱為單鏈表或線性鏈表；有兩個(gè)指針域的鏈表，稱為雙鏈表；有多個(gè)指針域的鏈表，稱為多鏈表；首尾相接的鏈表稱為循環(huán)鏈表。a1heada2an……h(huán)ead循環(huán)鏈表示意圖：1.單鏈表的建立和輸出頭插法建單鏈表的演示尾插法建單鏈表的演示1.單鏈表的建立和輸出實(shí)例：用單鏈表結(jié)構(gòu)來存放26個(gè)英文字母組成的線性表(A，B，C，…，Z),請(qǐng)寫出C語言程序。難點(diǎn)分析：每個(gè)數(shù)據(jù)元素在內(nèi)存中是“零散”存放的，其首地址怎么找？又怎么一一鏈接？實(shí)現(xiàn)思路：先開辟頭指針，然后陸續(xù)為每個(gè)數(shù)據(jù)元素開辟存儲(chǔ)空間并賦值，并及時(shí)將地址送給前面的指針。將全局變量及函數(shù)提前說明：#include<stdio.h>#include<stdlib.h>typedefstructnode{chardata;structnode*next;}LinkNode,*LinkList;LinkNode*p,*q,*head;intn;intm=sizeof(LinkNode);/*結(jié)構(gòu)類型定義好之后，每個(gè)變量的長度就固定了，m求一次即可*///等價(jià)于：LinkListp,q,head;//尾插法建立單鏈表LinkLists;head=(LinkList)malloc(m);p=head;s=(LinkList)malloc(m);//為第i個(gè)結(jié)點(diǎn)開新空間！s->data=‘A’+i-1;//為第i個(gè)結(jié)點(diǎn)值域賦值p->next=s;//讓p指向的結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)sp=s;//讓指針變量p改為指向新結(jié)點(diǎn)s（p后移）p->next=NULL;returnhead;//head是全局變量，此語句可省LinkListbuild()//字母鏈表的生成。帶頭結(jié)點(diǎn)的單鏈表{inti;LinkLists;head=(LinkList)malloc(m);//m=sizeof(LinkNode)if(head==0)returnOVERFLOW;p=head;for(i=1;i<=26;i++){s=(LinkList)malloc(m);//為第i個(gè)結(jié)點(diǎn)開新空間！s->data=i+‘A’-1;//為第i個(gè)結(jié)點(diǎn)值域賦值p->next=s；//讓p指向的結(jié)點(diǎn)的指針域指向新結(jié)點(diǎn)sp=s;//讓指針變量p改為指向新結(jié)點(diǎn)s（p后移）}p->next=NULL;//最后一個(gè)結(jié)點(diǎn)的next為空returnhead;}3.單鏈表的插入在鏈表中插入一個(gè)元素的示意圖如下：xsbapabpp->nexts->next(1)元素x結(jié)點(diǎn)應(yīng)預(yù)先生成：(2)結(jié)點(diǎn)b做x的后繼(即把結(jié)點(diǎn)b的地址存入s的next域)(3)結(jié)點(diǎn)x作為a的后繼（即把結(jié)點(diǎn)x的地址s存入P的next域）s=(LinkList)malloc(m);s->data=x;s->next=p->next(p->next的值即b的地址）p->next=s；問3：在什么情況下用順序表比鏈表好？

順序表適宜于做查找這樣的靜態(tài)操作；鏈表宜于做插入、刪除這樣的動(dòng)態(tài)操作。若線性表的長度變化不大，且其主要操作是查找，則采用順序表；若線性表的長度變化較大，且其主要操作是插入、刪除操作，則采用鏈表。答：3.1棧（Stack）

棧的定義：限定僅在表尾進(jìn)行插入或刪除操作的線性表，表尾—棧頂，表頭—棧底，不含元素的空表稱空棧特點(diǎn)：先進(jìn)后出（FILO）或后進(jìn)先出（LIFO）ana1a2……...棧底棧頂...出棧進(jìn)棧棧s=(a1,a2,……,an)例1：對(duì)于一個(gè)棧，給出輸入項(xiàng)A、B、C，如果輸入項(xiàng)序列由ABC組成，試給出所有可能的輸出序列。A進(jìn)B進(jìn)C進(jìn)C出B出A出CBAA進(jìn)A出B進(jìn)B出C進(jìn)C出ABCA進(jìn)A出B進(jìn)C進(jìn)C出B出ACBA進(jìn)B進(jìn)B出A出C進(jìn)C出BACA進(jìn)B進(jìn)B出C進(jìn)C出A出BCA不可能產(chǎn)生輸出序列CAB例2：一個(gè)棧的輸入序列是12345，若在入棧的過程中允許出棧，則棧的輸出序列43512可能實(shí)現(xiàn)嗎？12345的輸出呢？43512不可能實(shí)現(xiàn)，主要是其中的12順序不能實(shí)現(xiàn)；

12345的輸出可以實(shí)現(xiàn)，只需壓入一個(gè)立即彈出一個(gè)即可。

435612中到了12順序不能實(shí)現(xiàn)；

135426可以實(shí)現(xiàn)。例3：如果一個(gè)棧的輸入序列為123456，能否得到435612和135426的出棧序列？答：答：例4：計(jì)算機(jī)系2001年考研題設(shè)依次進(jìn)入一個(gè)棧的元素序列為c，a，b，d，則可得到出棧的元素序列是：

Ａ）a，b，c，dＢ）c，d，a，bＣ）b，c，d，aＤ）a，c，d，bA、D答：3.4隊(duì)列3.4.1抽象數(shù)據(jù)類型隊(duì)列的定義

隊(duì)列(Queue)也是一種運(yùn)算受限的線性表。它只允許在表的一端進(jìn)行插入，而在另一端進(jìn)行刪除。允許刪除的一端稱為隊(duì)頭(front)，允許插入的一端稱為隊(duì)尾(rear)。例如：排隊(duì)購物。操作系統(tǒng)中的作業(yè)排隊(duì)。先進(jìn)入隊(duì)列的成員總是先離開隊(duì)列。因此隊(duì)列亦稱作先進(jìn)先出(FirstInFirstOut)的線性表，簡稱FIFO表。當(dāng)隊(duì)列中沒有元素時(shí)稱為空隊(duì)列。在空隊(duì)列中依次加入元素a1,a2,…an之后，a1是隊(duì)頭元素，an是隊(duì)尾元素。顯然退出隊(duì)列的次序也只能是a1,a2,…an

，也就是說隊(duì)列的修改是依先進(jìn)先出的原則進(jìn)行的。

為克服上述假上溢現(xiàn)象，可以將向量空間想象為一個(gè)首尾相接的圓環(huán)，并稱這種向量為循環(huán)向量，存儲(chǔ)在其中的隊(duì)列稱為循環(huán)隊(duì)列（CircularQueue)。只不過當(dāng)頭尾指針指向向量上界時(shí)，其加1操作的結(jié)果是指向向量的下界0。解決假溢出問題——循環(huán)隊(duì)列J4J5J6012345rearfront入隊(duì)出隊(duì)操作時(shí)，頭尾指針仍要加1，朝前移動(dòng)。由于入隊(duì)時(shí)尾指針向前追趕頭指針，出隊(duì)時(shí)頭指針向前追趕尾指針，故隊(duì)空和隊(duì)滿時(shí)頭尾指針均相等。

因此，我們無法通過Q.front=Q.rear來判斷隊(duì)列“空”還是“滿”。存在隊(duì)空隊(duì)滿的判斷問題012345rearfrontrearfrontJ5J6J7012345J4J9J8尾指針rear指向J9的后一位置空隊(duì)列解決此問題的方法至少有兩種：(1)另設(shè)一個(gè)布爾變量以區(qū)別隊(duì)列的空和滿；(2)少用一個(gè)元素的空間，約定入隊(duì)前，測試尾指針在循環(huán)意義下加1后是否等于頭指針，若相等則認(rèn)為隊(duì)滿（注意：rear所指的單元始終為空）解決辦法frontJ5J6J7012345J4J8rear在這種情況下我們認(rèn)為隊(duì)列已滿！012345rearfrontfrontJ5J6J7012345J4J8rearJ4J5J6012345rearfront初始狀態(tài)J4,J5,J6出隊(duì)J7,J8入隊(duì)隊(duì)空：front==rear隊(duì)滿：front==(rear+1)%MaxSize頭尾指針的加1都是在循環(huán)意義下加1frontJ5012345J4rear此時(shí)，rear的值是5，rear+1之后應(yīng)該是0（在循環(huán)意義下），即:(rear+1)%MaxSize此時(shí)front的值是3，front+1之后是4，當(dāng)值小于MaxSize時(shí)，對(duì)MaxSize取模，值不變，故還可以寫成

(front+1)%MaxSize此循環(huán)隊(duì)列的MaxSize是6隊(duì)空：Q.front==Q.rear隊(duì)滿：Q.front==(Q.rear+1)%maxSize入隊(duì)：Q.rear=(Q.rear+1)%maxSize出隊(duì)：Q.front=(front+1)%maxSize;求隊(duì)長：(Q.rear-Q.front+maxSize)%maxSize循環(huán)隊(duì)列

4.1串類型的定義一、串和基本概念

串(String)是零個(gè)或多個(gè)字符組成的有限序列。

一般記作S=“a1a2a3…an”，其中S是串名，雙引號(hào)括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數(shù)字或其它字符；串中所包含的字符個(gè)數(shù)稱為該串的長度。長度為零的串稱為空串(EmptyString)，它不包含任何字符?？瞻状和ǔH由一個(gè)或多個(gè)空格組成的串稱為空白串(BlankString)

注意：空串和空白串的不同，例如“”和“”分別表示長度為1的空白串和長度為0的空串。子串、主串：串中任意個(gè)連續(xù)字符組成的子序列稱為該串的子串，包含子串的串相應(yīng)地稱為主串。通常將子串在主串中首次出現(xiàn)時(shí)的該子串的首字符對(duì)應(yīng)的主串中的序號(hào)，定義為子串在主串中的序號(hào)（或位置）。例如，設(shè)A和B分別為

A=“Thisisastring”B=“is”則B是A的子串，A為主串。B在A中出現(xiàn)了兩次，其中首次出現(xiàn)所對(duì)應(yīng)的主串位置是3。因此，稱B在A中的序號(hào)（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。

4.子串substring(&S,T,i,len)表示截取S串中從第i個(gè)字符開始連續(xù)len個(gè)字符，作為S的一個(gè)子串，存入T串。5.串比較大小StrCmp(S,T)比較S串和T串的大小，若S<T，函數(shù)值為負(fù)，若S=T，函數(shù)值為零，若S>T，函數(shù)值為正。6.插入SInsert(&S,i,T)

在S串的第i個(gè)位置插入T串。7.串刪除SDelete(&S,i,len)

刪除串S中從第i個(gè)字符開始連續(xù)len個(gè)字符。5.2數(shù)組的順序表示和實(shí)現(xiàn)由于計(jì)算機(jī)的內(nèi)存結(jié)構(gòu)是一維的，因此用一維內(nèi)存來表示多維數(shù)組，就必須按某種次序?qū)?shù)組元素排成一列序列，然后將這個(gè)線性序列存放在存儲(chǔ)器中。又由于對(duì)數(shù)組一般不做插入和刪除操作，也就是說，數(shù)組一旦建立，結(jié)構(gòu)中的元素個(gè)數(shù)和元素間的關(guān)系就不再發(fā)生變化。因此，一般都是采用順序存儲(chǔ)的方法來表示數(shù)組。通常有兩種順序存儲(chǔ)方式：按行序?yàn)橹餍虼鎯?chǔ)a11a12……..a1n

a21a22……..a2n

am1am2……..amn

….Loc(aij)=Loc(a11)+[(i-1)n+(j-1)]*l

按行序?yàn)橹餍虼娣臿mn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n通常有兩種順序存儲(chǔ)方式：按列序?yàn)橹餍虼鎯?chǔ)

按列序?yàn)橹餍虼娣?1m-1m*n-1mamn……..

a2na1n……….am2……..

a22a12am1

…….a21

a11a11

a12

……..

a1n

a21

a22……..

a2n

am1

am2

……..amn

….Loc(aij)=Loc(a11)+[(j-1)m+(i-1)]*l

計(jì)算二維數(shù)組元素地址的通式

設(shè)一般的二維數(shù)組是A[c1..d1,c2..d2]，這里c1,c2不一定是0。無論規(guī)定行優(yōu)先或列優(yōu)先，只要知道以下三要素便可隨時(shí)求出任一元素的地址（這樣數(shù)組中的任一元素便可以隨機(jī)存取?。憾S數(shù)組列優(yōu)先存儲(chǔ)的通式為：LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*Lac1,c2…ac1,d2…aij…

ad1,c2…ad1,d2

Amn=單個(gè)元素長度aij之前的行數(shù)數(shù)組基址總列數(shù)，即第2維長度aij本行前面的元素個(gè)數(shù)①開始結(jié)點(diǎn)的存放地址（即基地址）②維數(shù)和每維的上、下界；③每個(gè)數(shù)組元素所占用的單元數(shù)則行優(yōu)先存儲(chǔ)時(shí)的地址公式為：

LOC(aij)=LOC(ac1，c2)+[(i-c1)*(d2-c2+1)+j-c2)]*L例2：已知二維數(shù)組Am,m按行存儲(chǔ)的元素地址公式是：

Loc(aij)=Loc(a11)+[(i-1)*m+(j-1)]*K,按列存儲(chǔ)的公式是？Loc(aij)=Loc(a11)+[(j-1)*m+(i-1)]*K（盡管是方陣，但公式仍不同）例1：一個(gè)二維數(shù)組A，行下標(biāo)的范圍是1到6，列下標(biāo)的范圍是0到7，每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。那么，這個(gè)數(shù)組的體積是

個(gè)字節(jié)。288例3：設(shè)數(shù)組a[1…60,1…70]的基地址為2048，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以列序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[32,58]的存儲(chǔ)地址為

。8950LOC(aij)=LOC(ac1，c2)+[(j-c2)*(d1-c1+1)+i-c1)]*L得：LOC(a32,58)=2048+[(58-1)*(60-1+1)+32-1)]*2＝8950答：請(qǐng)注意審題！利用列優(yōu)先通式：答：

Volume=m*n*L=(6-1+1)*(7-0+1)*6=48*6=2885.3矩陣的壓縮存儲(chǔ)在科學(xué)與工程計(jì)算問題中，矩陣是一種常用的數(shù)學(xué)對(duì)象，在高級(jí)語言編制程序時(shí)，簡單而又自然的方法，就是將一個(gè)矩陣描述為一個(gè)二維數(shù)組。矩陣在這種存儲(chǔ)表示之下，可以對(duì)其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡單，并且存儲(chǔ)的密度為1。但是在矩陣中非零元素呈某種規(guī)律分布或者矩陣中出現(xiàn)大量的零元素的情況下，看起來存儲(chǔ)密度仍為1，但實(shí)際上占用了許多單元去存儲(chǔ)重復(fù)的非零元素或零元素，這對(duì)高階矩陣會(huì)造成極大的浪費(fèi)。為了節(jié)省存儲(chǔ)空間，我們可以對(duì)這類矩陣進(jìn)行壓縮存儲(chǔ)：即為多個(gè)相同的非零元素只分配一個(gè)存儲(chǔ)空間；對(duì)零元素不分配空間。不失一般性，我們按“行優(yōu)先順序”存儲(chǔ)主對(duì)角線（包括對(duì)角線）以下的元素，其存儲(chǔ)形式如圖所示。在這個(gè)下三角矩陣中，第i行恰有i+1個(gè)元素，元素總數(shù)為：n(n+1)/2因此，我們可以按從上到下、從左到右將這些元素存放在一個(gè)向量sa[0..n(n+1)/2-1]中。為了便于訪問對(duì)稱矩陣A中的元素，我們必須在aij和sa[k]之間找一個(gè)對(duì)應(yīng)關(guān)系。

a00a10a11a20a21a22………………..an-10an-11an-12…an-1n-1

若i≥j，則aij在下三角形中。aij之前的i行（從第0行到第i-1行）一共有1+2+…+i=i(i+1)/2個(gè)元素，在第i行上，aij之前恰有j個(gè)元素（即ai0,ai1,ai2,…,aij-1），因此有：

k=i*(i+1)/2+j0≤k<n(n+1)/2

若i<j，則aij是在上三角矩陣中。因?yàn)閍ij=aji，所以只要交換上述對(duì)應(yīng)關(guān)系式中的i和j即可得到：

k=j*(j+1)/2+i0≤k<n(n+1)/2

一、基本概念廣義表是線性表的推廣。線性表中的元素僅限于原子項(xiàng)(單個(gè)數(shù)據(jù)元素)，即不可以再分，而廣義表中的元素既可以是原子項(xiàng)，也可以是子表(另一個(gè)線性表)。

如果ai是單個(gè)數(shù)據(jù)元素，則稱ai為廣義表的原子。2．廣義表舉例A=(),A為空表，長度為0。B=(a,

(b,c)),B是長度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為子表。C=(x,y,z)，C是長度為3的廣義表，每一項(xiàng)都是原子。D=(B,C)，D是長度為2的廣義表，每一項(xiàng)都是上面提到的子表。E=(a,E)是長度為2的廣義表，第一項(xiàng)為原子，第二項(xiàng)為它本身。3．廣義表的深度一個(gè)廣義表的深度是指該廣義表展開后所含括號(hào)的層數(shù)。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。4．取表頭運(yùn)算head若廣義表LS=(a1,a2,…,an)，則head(LS)=a1。取表頭運(yùn)算得到的結(jié)果可以是原子，也可以是一個(gè)子表。例如，head((a1,a2,a3,a4))=a1head(((a1,a2),(a3,a4),a5))=(a1,a2)5．取表尾運(yùn)算tail若廣義表LS=(a1,a2,…,an)，則tail(LS)=(a2,a3,…,an)。即取表尾運(yùn)算得到的結(jié)果是除表頭以外的所有元素，取表尾運(yùn)算得到的結(jié)果一定是一個(gè)子表。值得注意的是廣義表()和(())是不同的，前者為空表，長度為0，后者的長度為1，可得到表頭、表尾均為空表，即head((()))=()，tail((()))=()。1.GetTail【(b,k,p,h)】＝

;2.GetHead【((a,b),(c,d))】＝

;3.GetTail【((a,b),(c,d))】＝

;4.GetTail【GetHead【((a,b),(c,d))】】＝

;求下列廣義表操作的結(jié)果(k,p,h)（b）(a,b)5.GetTail【（e）】＝

;6.GetHead【(())】＝

.7.GetTail【(())】＝

.()(a,b)()()((c,d))BACEDFGHIJKLMNO(a)滿二叉樹BACEDFGHIJ(b)完全二叉樹問題:一個(gè)高度為h的完全二叉樹最多有多少個(gè)結(jié)點(diǎn)?最少有多少個(gè)結(jié)點(diǎn)?2h-1個(gè)2h-1個(gè)6.2.2二叉樹的性質(zhì)性質(zhì)1:在一棵非空二叉樹的第i層上至多有2i-1個(gè)結(jié)點(diǎn)（i≥1）。性質(zhì)2:深度為k的二叉樹至多有2k-1個(gè)結(jié)點(diǎn)。說明：深度k=0，表示沒有一個(gè)結(jié)點(diǎn)；深度k=1，表示只有一個(gè)根結(jié)點(diǎn)。性質(zhì)3:

具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度k為log2n+1。證明：根據(jù)性質(zhì)2，對(duì)于有n個(gè)結(jié)點(diǎn)的深度為k的完全二叉樹有

2k-1-1<n≤2k-1，或者，有

2k-1≤n<2k于是，有k-1≤log2n<k，因?yàn)閗必須是整數(shù)，所以k=log2n+1

。證畢。2.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)對(duì)于任意的二叉樹來說，每個(gè)結(jié)點(diǎn)只有兩個(gè)孩子，一個(gè)雙親結(jié)點(diǎn)。我們可以設(shè)計(jì)每個(gè)結(jié)點(diǎn)至少包括三個(gè)域：數(shù)據(jù)域、左孩子域和右孩子：leftChilddatarightChild其中，leftChild域指向該結(jié)點(diǎn)的左孩子，data域記錄該結(jié)點(diǎn)的信息，rightChild域指向該結(jié)點(diǎn)的右孩子。用C語言可以這樣聲明二叉樹的二叉鏈表結(jié)點(diǎn)的結(jié)構(gòu)：typedefstructbtNode{TElemTypedata;structbtNode*leftChild;structbtNode*rightChild;}BiTNode,*BiTree;有時(shí)，為了便于找到父結(jié)點(diǎn)，可以增加一個(gè)parent域，parent域指向該結(jié)點(diǎn)的父結(jié)點(diǎn)。該結(jié)點(diǎn)結(jié)構(gòu)如下：leftChilddataparentrightChild6.3.1二叉樹的遍歷

遍歷是各種數(shù)據(jù)結(jié)構(gòu)最基本的操作，許多其他的操作可以在遍歷基礎(chǔ)上實(shí)現(xiàn)。二叉樹的遍歷：沿某條路徑周游二叉樹，對(duì)樹中的每個(gè)結(jié)點(diǎn)訪問一次且僅訪問一次。“訪問”的含義很廣，可以是對(duì)結(jié)點(diǎn)的各種處理，如修改結(jié)點(diǎn)數(shù)據(jù)、輸出結(jié)點(diǎn)數(shù)據(jù)。一、遍歷的基本概念二、兩種基本策略：廣度遍歷深度遍歷

如何訪問二叉樹的每個(gè)結(jié)點(diǎn)，而且每個(gè)結(jié)點(diǎn)僅被訪問一次？？

A

F

E

D

C

B廣度遍歷策略層次遍歷方法：從上到下、從左到右訪問各結(jié)點(diǎn)適用于順序存儲(chǔ)結(jié)構(gòu)012345678ABCDφEφφF存儲(chǔ)結(jié)構(gòu)遍歷結(jié)果：ABCDEF

A

F

E

D

C

B各種遍歷的思想1.先序遍歷（DLR）2.中序遍歷（LDR）3.后序遍歷（LRD）

例：先序遍歷右圖所示的二叉樹，所得先序遍歷序列：

A,B,D,E,G,C,F1.先序遍歷（DLR）先序遍歷（DLR）思想若二叉樹非空，則依次進(jìn)行以下操作（1）訪問根結(jié)點(diǎn)；（2）先序遍歷左子樹；（3）先序遍歷右子樹；

A

F

G

E

D

C

BFlash演示例：中序遍歷右圖所示的二叉樹，所得中序遍歷序列：

D,B,G,E,A,C,F2.中序遍歷（LDR）中序遍歷（LDR）思想：若二叉樹非空，則依次進(jìn)行以下操作（1）中序遍歷左子樹；（2）訪問根結(jié)點(diǎn)；（3）中序遍歷右子樹；

A

F

G

E

D

C

BFlash演示3.后序遍歷（LRD）后序遍歷（LRD）思想若二叉樹非空，則依次進(jìn)行以下操作（1）后序遍歷左子樹；（2）后序遍歷右子樹；（3）訪問根結(jié)點(diǎn)；例：后序遍歷右圖所示的二叉樹，所得后序遍歷序列：

D,G,E,B,F,C,A

A

F

G

E

D

C

BFlash演示練習(xí)1給出下圖所示的二叉樹進(jìn)行先序、中序、后序遍歷的結(jié)果。BACDEGFHX先序:ABDEFGCHX中序:DBFEGACXH后序:DFGEBXHCA2、假設(shè)一棵二叉樹的后序遍歷序列為DGJHEBIFCA，中序遍歷序列為DBGEHJACIF，則其前序遍歷序列為

。

A）ABCDEFGHIJB）ABDEGHJCFIC）ABDEGHJFICD）ABDEGJHCFIABDEGHJCFI

3、若某二叉樹的先序遍歷序列和中序遍歷序列分別為PBECD、BEPDC，則該二叉樹的后序遍歷序列為

。

A.PBCDE

B.DECBP

C.EBDCP

D.EBPDC答案：C10二叉樹的第I層上最多含有結(jié)點(diǎn)數(shù)為（）A．2IB．2I-1-1C．2I-1D．2I-111.一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹的高h(yuǎn)為（）A．11B．10C．11至1025之間D．10至1024之間12．一棵二叉樹高度為h,所有結(jié)點(diǎn)的度或?yàn)?，或?yàn)?，則這棵二叉樹最少有()結(jié)點(diǎn)A．2hB．2h-1C．2h+1D．h+113．對(duì)于有n個(gè)結(jié)點(diǎn)的二叉樹,其高度為（）A．nlog2nB．log2nC．log2n|+1D．不確定14.一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹的樹高度（深度）是（）A．logn+1B．logn+1C．lognD．logn-115．深度為h的滿m叉樹的第k層有（）個(gè)結(jié)點(diǎn)。(1=<k=<h)A．mk-1B．mk-1C．mh-1D．mh-116．高度為K的二叉樹最大的結(jié)點(diǎn)數(shù)為（）。A．2kB．2k-1C．2k-1D．2k-1-117.一棵樹高為K的完全二叉樹至少有（）個(gè)結(jié)點(diǎn)A．2k

–1B.2k-1

–1C.2k-1D.2k18.將有關(guān)二叉樹的概念推廣到三叉樹，則一棵有244個(gè)結(jié)點(diǎn)的完全三叉樹的高度（）A．4B．5C．6D．719．在下列存儲(chǔ)形式中，哪一個(gè)不是樹的存儲(chǔ)形式？A．雙親表示法B．孩子鏈表表示法C．孩子兄弟表示法D．順序存儲(chǔ)表示法20．一棵二叉樹的前序遍歷序列為ABCDEFG，它的中序遍歷序列可能是（）A．CABDEFGB．ABCDEFGC．DACEFBGD．ADCFEG21．已知一棵二叉樹的前序遍歷結(jié)果為ABCDEF,中序遍歷結(jié)果為CBAEDF,則后序遍歷的結(jié)果為（）。A．CBEFDAB．FEDCBAC．CBEDFAD．不定22．已知某二叉樹的后序遍歷序列是dabec,中序遍歷序列是debac,它的前序遍歷是（）。

A．a(chǎn)cbedB．decabC．deabcD．cedba23.某二叉樹中序序列為A,B,C,D,E,F,G，后序序列為B,D,C,A,F,G,E則前序序列是：A．E,G,F,A,C,D,BB．E,A,C,B,D,G,FC．E,A,G,C,F,B,DD．上面的都不對(duì)2.輸出二叉樹中的葉子結(jié)點(diǎn)輸出二叉樹中的葉子結(jié)點(diǎn)與輸出二叉樹中的結(jié)點(diǎn)相比，它是一個(gè)有條件的輸出問題，即在遍歷過程中走到每一個(gè)結(jié)點(diǎn)時(shí)需進(jìn)行測試，看是否有滿足葉子結(jié)點(diǎn)的條件。/*先序遍歷輸出二叉樹中的葉子結(jié)點(diǎn),*/voidpreOrder(btreeroot){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL)printf(root->data);/*輸出葉子結(jié)點(diǎn)*/

preOrder(root->lchild);/*先序遍歷左子樹*/preOrder(root->rchild);/*先序遍歷右子樹*/}}3.統(tǒng)計(jì)葉子結(jié)點(diǎn)數(shù)目/*采用遞歸算法，如果是空樹，返回0；如果只有一個(gè)結(jié)點(diǎn)，返回1；否則為左右子樹的葉子結(jié)點(diǎn)數(shù)之和*/intleaf(btreeroot){ intLeafCount; if(root==NULL) LeafCount=0; else if((root->lchild==NULL)&&(root->rchild==NULL)) LeafCount=1; else/*葉子數(shù)為左右子樹的葉子數(shù)目之和*/ LeafCount=leaf(root->lchild)+leaf(root->rchild); returnLeafCount;}6.3.4線索二叉樹1、問題的提出當(dāng)以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到結(jié)點(diǎn)的左右孩子的信息，而不能在結(jié)點(diǎn)的任一序列的前驅(qū)與后繼信息，這種信息只有在遍歷的動(dòng)態(tài)過程中才能得到。解決辦法：利用二叉鏈表中的空指針增加標(biāo)志域效果：為二叉樹建立了一個(gè)雙向線索鏈表前驅(qū)與后繼：在二叉樹的先序、中序或后序遍歷序列中兩個(gè)相鄰的結(jié)點(diǎn)互稱為~線索：指向前驅(qū)或后繼結(jié)點(diǎn)的指針稱為~線索二叉樹：加上線索的二叉鏈表表示的二叉樹叫~線索化：對(duì)二叉樹按某種遍歷次序使其變?yōu)榫€索二叉樹的過程叫~2、線索二叉樹的定義2、線索二叉樹的實(shí)現(xiàn)在有n個(gè)結(jié)點(diǎn)的二叉鏈表中必定有n+1個(gè)空鏈域在線索二叉樹的結(jié)點(diǎn)中增加兩個(gè)標(biāo)志域lchildltagdatartagrchildABCDEABDCET先序序列：ABCDE先序線索二叉樹00001111^11typedefstructnode{intdata;intltag,rtag;structnode*lchild,*rchild;}TNODE;lchildltagdatartagrchild前序線索化ABCDEABDCET中序序列：BCAED中序線索二叉樹00001111^11^中序線索化ABCDEABDCET后序序列：CBEDA后序線索二叉樹0000111111^后序線索化ABCDE0A01B00D11C11E1T(指向頭結(jié)點(diǎn))中序序列：BCAED帶頭結(jié)點(diǎn)的中序線索二叉樹

0

1頭結(jié)點(diǎn)：ltag=0,lchild指向根結(jié)點(diǎn)rtag=1,rchild指向遍歷序列中最后一個(gè)結(jié)點(diǎn)遍歷序列中第一個(gè)結(jié)點(diǎn)的lchild域和最后一個(gè)結(jié)點(diǎn)的rchild域都指向頭結(jié)點(diǎn)ABDCET中序序列：BCAED中序線索二叉樹00001111^11^帶頭結(jié)點(diǎn)的中序線索二叉樹課堂練習(xí)1．已知一棵二叉樹的中序（或中根）遍歷結(jié)點(diǎn)排列為DGBAECF，后序（或后根）遍歷結(jié)點(diǎn)排列為GDBEFCA，（1）試畫出該二叉樹；（2）試畫出該二叉樹的先序線索樹；（3）試畫出該二叉樹的中序線索樹；（4）試畫出該二叉樹的后序線索樹；ADGECF（1）二叉樹B0A00B10C01D01E11F11G1(2)中序線索二叉樹0A00B10C01D01E11F11G1(3)先序線索二叉樹0A00B10C01D01E11F11G1(d)后序線索二叉樹4、樹與二叉樹轉(zhuǎn)換ACBED樹ABCDE二叉樹A^^BC^D^^E^A^^BC^D^^E^（1）將樹轉(zhuǎn)換成二叉樹加線：在兄弟之間加一連線抹線：對(duì)每個(gè)結(jié)點(diǎn)，除了其左孩子外，去除其與其余孩子之間的關(guān)系旋轉(zhuǎn)：以樹的根結(jié)點(diǎn)為軸心，將整樹順時(shí)針轉(zhuǎn)45°ABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHIABCDEFGHI樹轉(zhuǎn)換成的二叉樹其右子樹一定為空課堂練習(xí)ABCDEFG(a)1、將下圖表示的樹轉(zhuǎn)化為二叉樹ABFCGED二、構(gòu)造哈夫曼樹1．哈夫曼樹的定義

假設(shè)有n個(gè)權(quán)值，試構(gòu)造一個(gè)有n個(gè)葉子結(jié)點(diǎn)的二叉樹，每個(gè)葉子結(jié)點(diǎn)帶權(quán)為wi，則其中帶權(quán)路徑長度WPL最小的二叉樹稱作最優(yōu)二叉樹或哈夫曼樹。例：有4個(gè)結(jié)點(diǎn)a、b、c、d，權(quán)值分別為7，5，2，4，構(gòu)造有4個(gè)葉子結(jié)點(diǎn)的二叉樹abcd7524(a)WPL=7*2+5*2+2*2+4*2=36dcab2475(b)WPL=7*3+5*3+2*1+4*2=46abcd7524(c)WPL=7*1+5*2+2*3+4*3=35圖（c）的二叉樹是一棵哈夫曼樹。1357(a)7135(b)練習(xí)：下圖所示二叉樹帶權(quán)路徑長度？（a）WPL=1×2+3×2+5×2+7×2=32（b）WPL=7×3+5×3+3×2+1×1=43（c）WPL=1×3+3×3+5×2+7×1=29圖（c）的二叉樹是一棵哈夫曼樹。5(c)7132．哈夫曼樹的構(gòu)造假設(shè)有n個(gè)權(quán)值，則構(gòu)造出的哈夫曼樹有n個(gè)葉子結(jié)點(diǎn)。n個(gè)權(quán)值分別設(shè)為w1,w2,…,wn，則哈夫曼樹的構(gòu)造規(guī)則為：(1)根據(jù)給定的n個(gè)權(quán)值{w1,w2,…wn}構(gòu)成n棵二叉樹的集合F={T1,T2,…,Tn}(2)每次選擇兩個(gè)權(quán)值最小的二叉樹做子樹合并為一個(gè)新的二叉樹，新二叉樹的權(quán)值為兩個(gè)子樹的和。直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。下面給出哈夫曼樹的構(gòu)造過程，假設(shè)給定的葉子結(jié)點(diǎn)的權(quán)分別為1,5,7,3，則構(gòu)造哈夫曼樹過程如圖所示。

(a)初始森林

3

7

51

(b)一次合并后的森林5

7

134

591347(c)二次合并后的森林哈夫曼樹的構(gòu)造過程59134716(d)三合并后的森林例：給定一組數(shù)列（15，8，10，21，6，19，3）分別代表字符A、B、C、D、E、F、G出現(xiàn)的頻度。構(gòu)造哈夫曼樹，計(jì)算其WPL值。WPL=19*2+21*2+8*3+10*3+15*3+3*4+6*4=215

在遠(yuǎn)程通訊中，要將待傳字符轉(zhuǎn)換成由二進(jìn)制組成的字符串。對(duì)字符的編碼可以采用定長編碼，也可以采用不定長編碼。定長編碼：每個(gè)字符的編碼都用固定長度。不定長編碼：出現(xiàn)頻率高的字符用短編碼，出現(xiàn)頻率低的字符用長編碼。

三、哈夫曼樹的應(yīng)用（哈夫曼編碼）求Huffman編碼：由葉子→根，若：（1）從左分支下去，則分支為“0”；（2）從右分支下去，則分支為“1”。

ACBD000111哈夫曼樹及其編碼實(shí)現(xiàn)算法演示例：已知某系統(tǒng)在通訊時(shí)，只出現(xiàn)C，A，S，T，B五種字符，它們出現(xiàn)的頻率依次為2，4，2，3，3，試設(shè)計(jì)Huffman編碼。W(權(quán))={2，4，2，3，3}，葉子結(jié)點(diǎn)個(gè)數(shù)n=5構(gòu)造的Huffman樹1484642233TBACS第一步：構(gòu)造Huffman樹TBACS000110110111出現(xiàn)頻率越大的字符，其Huffman編碼越短。148464220001113301TBACS第二步：由Huffman樹得Huffman編碼為：編碼過程：電文是{CASCATSATAT}

其編碼“11010111110100011110001000”114846422000113301TBACS譯碼過程：電文為“1101000”

譯文只能是“CAT”例：給定一組數(shù)列（15，8，10，21，6，19，3）分別代表字符A、B、C、D、E、F、G出現(xiàn)的頻度。（1）構(gòu)造哈夫曼樹，計(jì)算其WPL值；（2）給出各字符的哈夫曼編碼；WPL=19*2+21*2+8*3+10*3+15*3+3*4+6*4=215A：111B：000C：110D：10E：0011F：01G：00101000000111114.度、入度和出度對(duì)于無向圖而言，頂點(diǎn)v的度是指和v相關(guān)聯(lián)邊的數(shù)目，記作TD(v)。在有向圖中頂點(diǎn)v的度有出度和入度兩部分，其中以頂點(diǎn)v為弧頭的弧的數(shù)目成為該頂點(diǎn)的入度，記作ID(v)，以頂點(diǎn)v為弧尾的弧的數(shù)目稱為該頂點(diǎn)的出度，記作OD(v)，則頂點(diǎn)v的度為TD(v)=ID(v)+OD(v)。一般地，若圖G中有n個(gè)頂點(diǎn)，e條邊或弧，則圖中頂點(diǎn)的度與邊的關(guān)系如下：

V0

V4

V3

V1

V2

V0

V1

V2

V37.2.2.鄰接表表示圖的鄰接矩陣表示雖然有其自身的優(yōu)點(diǎn)，但對(duì)于稀疏圖來講，用鄰接矩陣的表示方法會(huì)造成存儲(chǔ)空間的很大浪費(fèi)。鄰接表（AdjacencyList）表示法實(shí)際上是圖的一種鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。它克服了鄰接矩陣的弊病，基本思想是只存有關(guān)聯(lián)的信息，對(duì)于圖中存在的邊信息則存儲(chǔ)，而對(duì)于不相鄰接的頂點(diǎn)則不保留信息。在鄰接表中，對(duì)圖中的每個(gè)頂點(diǎn)建立一個(gè)單鏈表，如第i個(gè)單鏈表中的結(jié)點(diǎn)則表示依附于頂點(diǎn)vi的邊（若是有向圖，則表示以vi為弧尾的?。?。頭結(jié)點(diǎn)datafirstarcadjvexnextarcinfo表結(jié)點(diǎn)頭結(jié)點(diǎn)datafirstarcadjvexnextarcinfo表結(jié)點(diǎn)data:數(shù)據(jù)域，頂點(diǎn)數(shù)據(jù)firstarc:指針，指向第一條依附于該頂點(diǎn)的邊(弧)的指針adjvex:鄰接點(diǎn)域，指示域定點(diǎn)vi鄰接的點(diǎn)在圖中的位置

nextarc:指針域，指示下一條邊或弧的結(jié)點(diǎn)info:存儲(chǔ)和邊或弧相關(guān)的信息，如權(quán)值等。201234m-1ABCD標(biāo)data

firstarc1.無向圖的鄰接表表示

AED

B

C286435鄰接鏈表？？A

E

DB

C

采用怎樣的策略進(jìn)行圖的遍歷？有兩種遍歷方法：深度優(yōu)先遍歷（DFS：Depth

First

Search）廣度優(yōu)先遍歷（BFS：Breadth

First

Search）7.3圖的遍歷圖的遍歷：從圖的某頂點(diǎn)出發(fā)，訪問圖中所有頂點(diǎn)，并且每個(gè)頂點(diǎn)僅訪問一次。V0V1V2V3V4V5V6V7一、深度優(yōu)先遍歷（DFS）深度優(yōu)先搜索遍歷類似于樹的先序遍歷。假定給定圖G的初態(tài)是所有頂點(diǎn)均未被訪問過，在G中任選一個(gè)頂點(diǎn)i作為遍歷的初始點(diǎn)，則深度優(yōu)先搜索遍歷可定義如下：首先訪問頂點(diǎn)i，并將其訪問標(biāo)記置為訪問過，即visited[i]=1；然后搜索與頂點(diǎn)i有邊相連的下一個(gè)頂點(diǎn)j，若j未被訪問過，則訪問它，并將j的訪問標(biāo)記置為訪問過，visited[j]=1，然后從j開始重復(fù)此過程，若j已訪問，再看與i有邊相連的其它頂點(diǎn)；若與i有邊相連的頂點(diǎn)都被訪問過，則退回到前一個(gè)訪問頂點(diǎn)并重復(fù)剛才過程，直到圖中所有頂點(diǎn)都被訪問完為止。7.3.1兩種遍歷思想

V0,V1,V3,V7,V4,V2,V5,V6,由于沒有規(guī)定訪問鄰接點(diǎn)的順序，DFS序列不唯一例求圖G以V0起點(diǎn)的的深度優(yōu)先序列：V0,V1,V4,V7,V3,V2,V5,V6

V0

V7

V6

V5

V4

V3

V2

V1深度優(yōu)先遍歷（DFS）課堂練習(xí)1．無向圖G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，對(duì)該圖進(jìn)行深度優(yōu)先遍歷，得到的頂點(diǎn)序列正確的是（）。A．a(chǎn),b,e,c,d,fB．a(chǎn),c,f,e,b,dC．a(chǎn),e,b,c,f,dD．a(chǎn),e,d,f,c,b2、設(shè)下圖如右所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？（）aebdfcacfdebaedfcbaefdcbaefdbcA．5個(gè)B．4個(gè)C．3個(gè)D．2個(gè)

7.4

生成樹和最小生成樹1.Prim算法假設(shè)N=(V,{E})是連通網(wǎng)，T為最小生成樹中邊的集合。(1)初始U={u0}(u0∈V),T={}；(2)所有u∈U,v∈V-U的邊中選一條代價(jià)最小的邊(u0,

v0),并入集合T，同時(shí)將v0并入U(xiǎn)；(3)重復(fù)(2)，直到U=V為止。此時(shí)，T中必含有n-1條邊，則T=(V,{T})為N的最小生成樹?？梢钥闯?，普利姆算法逐步增加U中的頂點(diǎn)，可稱為“加點(diǎn)法”。例如，對(duì)于下圖中的帶權(quán)圖，按Prim算法選取邊的過程如下頁圖所示。62111965432174133L=012∞

∞

∞0611∞

∞60911∞

∞119073∞

∞13704∞

∞

∞34062111965432174133(1)初始狀態(tài)：任選一點(diǎn)加入U(xiǎn),U={1}，T={}；62111965432174133(2)在U外的頂點(diǎn)中選擇離頂點(diǎn)1最近的點(diǎn)加入U(xiǎn)。選頂點(diǎn)2(d(1,2)=1)加入U(xiǎn)：U={1，2}將邊（1，2）加入T，T={（1，2）}；262111965432174133(3)在U外的頂點(diǎn)中選擇離集合U（頂點(diǎn)1或2）最近的點(diǎn)加入U(xiǎn)。選頂點(diǎn)3(d(1,3)=2)加入U(xiǎn)：U={1，2，3}將邊（1，3）加入T，T={(1,2)，(1,3)}；362111965432174133(4)在U外的頂點(diǎn)中選擇離集合U（頂點(diǎn)1或2或3）最近的點(diǎn)加入U(xiǎn)。選頂點(diǎn)4(d(3,4)=9)加入U(xiǎn)：U={1，2，3，4}將邊（3，4）加入T，T={(1,2),(1,3),(3,4)}；462111965432174133(5)在U外的頂點(diǎn)中選擇離集合U（頂點(diǎn)1或2或3或4）最近的點(diǎn)加入U(xiǎn)。選頂點(diǎn)6(d(4,6)=3)加入U(xiǎn)：U={1，2，3，4，6}將邊（4，6）加入T，T={(1,2),(1,3),(3,4),(4,6)}；662111965432174133(6)在U外的頂點(diǎn)中選擇離集合U（頂點(diǎn)1或2或3或4）最近的點(diǎn)加入U(xiǎn)。選頂點(diǎn)5(d(6,5)=4)加入U(xiǎn)：U={1，2，3，4，6}將邊（6，5）加入T，T={(1,2),(1,3),(3,4),(4,6),(6,5)}；5圖7.18普里姆算法構(gòu)造最小生成樹的過程16543271317918127524101256759410313課堂練習(xí)1.用Prim算法畫出下圖的最小生成樹16543265135664252.用Prim算法畫出下圖的最小生成．拓?fù)渑判?.定義給出有向圖G=(V,E)，對(duì)于V中的頂點(diǎn)的線性序列(vi1,vi2,...,vin)，如果滿足如下條件：若在G中從頂點(diǎn)vi到vj有一條路經(jīng)，則在序列中頂點(diǎn)vi必在頂點(diǎn)vj之前；則稱該序列為G的一個(gè)拓?fù)湫蛄校═opologicalorder）。構(gòu)造有向圖的一個(gè)拓?fù)湫蛄械倪^程稱為拓?fù)渑判颍═opologicalsort）。2.說明(1)在AOV網(wǎng)中,若不存在回路,則所有活動(dòng)可排成一個(gè)線性序列,使得每個(gè)活動(dòng)的所有前驅(qū)活動(dòng)都排在該活動(dòng)的前面,那么該序列為拓?fù)湫蛄小?2)拓?fù)湫蛄胁皇俏ㄒ坏摹?.6.2拓?fù)渑判蛩惴ㄒ?、拓?fù)渑判蚍椒ㄏ旅鎸⒔榻B怎樣實(shí)現(xiàn)拓?fù)渑判颍瑢?shí)現(xiàn)步驟如下：(1)在AOV網(wǎng)中選一個(gè)入度為0的頂點(diǎn)（沒有前驅(qū)）且輸出之；(2)從AOV網(wǎng)中刪除此頂點(diǎn)及該頂點(diǎn)發(fā)出來的所有有向邊；(3)重復(fù)(1)、(2)兩步，直到AOV網(wǎng)中所有頂點(diǎn)都被輸出或網(wǎng)中不存在入度為0的頂點(diǎn)。從拓?fù)渑判虿襟E可知，若在第(3)步中，網(wǎng)中所有頂點(diǎn)都被輸出，則表明網(wǎng)中無有向環(huán)，拓?fù)渑判虺晒Α?/p>

若僅輸出部分頂點(diǎn)，網(wǎng)中已不存在入度為0的頂點(diǎn)，則表明網(wǎng)中有有向環(huán)，拓?fù)渑判虿怀晒?。因此，一個(gè)AOV網(wǎng)的拓?fù)湫蛄惺遣晃ㄒ坏摹?.5.2關(guān)鍵路徑

有向圖在工程計(jì)劃和經(jīng)營管理中有著廣泛的應(yīng)用。通常用有向圖來表示工程計(jì)劃時(shí)有兩種方法：

·用頂點(diǎn)表示活動(dòng)，用有向弧表示活動(dòng)間的優(yōu)先關(guān)系，即上節(jié)所討論的AOV-網(wǎng)。

·用頂點(diǎn)表示事件，用弧表示活動(dòng)，弧的權(quán)值表示活動(dòng)所需要的時(shí)間。我們把用第二種方法構(gòu)造的有向無環(huán)圖叫做邊表示活動(dòng)的網(wǎng)（ActivityOnEdgeNetwork）,簡稱AOE-網(wǎng)。

圖7.24AOE-網(wǎng)

事件vi的最早發(fā)生時(shí)間ve(i)：從源點(diǎn)到頂點(diǎn)vi的最長路徑的長度，叫做事件vi的最早發(fā)生時(shí)間。求ve(i)時(shí)可從源點(diǎn)開始，按拓?fù)漤樞蛳騾R點(diǎn)遞推：

ve(0)=0；

ve(i)=Max{ve(k)＋dut(<k,i>)}，<k,i>∈T,1≤i≤n-1；

其中，T為所有以i為頭的弧<k,i>的集合，dut(<k,i>)表示與弧<k,i>對(duì)應(yīng)的活動(dòng)的持續(xù)時(shí)間。事件vi的最晚發(fā)生時(shí)間vl(i)：在保證匯點(diǎn)按其最早發(fā)生時(shí)間發(fā)生這一前提下，求事件vi的最晚發(fā)生時(shí)間。在求出ve(i)的基礎(chǔ)上，可從匯點(diǎn)開始，按逆拓?fù)漤樞蛳蛟袋c(diǎn)遞推，求出vl(i)：vl(n)=ve(n)；vl(i)=Min{vl(j)-dut(<i,j>)}<i,j>∈S,0≤i≤n-2;

其中，S為所有以i為尾的弧<i,j>的集合，dut(<i,j>)表示與弧<i,j>對(duì)應(yīng)的活動(dòng)的持續(xù)時(shí)間。活動(dòng)ai的最早開始時(shí)間e(i)：如果活動(dòng)ai對(duì)應(yīng)的弧為<j,k>，則e(i)等于從源點(diǎn)到頂點(diǎn)j的最長路徑的長度，即：e(i)=ve(j)?；顒?dòng)ai的最晚開始時(shí)間l(i)：如果活動(dòng)ai對(duì)應(yīng)的弧為<j,k>，其持續(xù)時(shí)間為dut(<j,k>),則有：l(i)=vl(k)-dut(<j,k>)，即在保證事件vk的最晚發(fā)生時(shí)間為vl(k)的前提下，活動(dòng)ai的最晚開始時(shí)間為l(i)?；顒?dòng)ai的松弛時(shí)間（時(shí)間余量）：ai的最晚開始時(shí)間與ai的最早開始時(shí)間之差：{l(i)-e(i)}。顯然，松弛時(shí)間（時(shí)間余量）為0的活動(dòng)為關(guān)鍵活動(dòng)。求關(guān)鍵路徑的基本步驟如下：對(duì)圖中頂點(diǎn)進(jìn)行拓?fù)渑判?，在排序過程中按拓?fù)湫蛄星蟪雒總€(gè)事件的最早發(fā)生時(shí)間ve(i)；按逆拓?fù)湫蛄星竺總€(gè)事件的最晚發(fā)生時(shí)間vl(i)；求出每個(gè)活動(dòng)ai的最早開始時(shí)間e(i)和最晚發(fā)生時(shí)間l(i)；找出e(i)=l(i)的活動(dòng)ai，即為關(guān)鍵活動(dòng)。例如，對(duì)圖7.24所示的AOE-網(wǎng)計(jì)算關(guān)鍵路徑的過程如下:(1)計(jì)算各頂點(diǎn)（事件）的最早發(fā)生時(shí)間：ve(0)=0ve(1)=max{ve(0)+dut(<0,1>)}=6ve(2)=max{ve(0)+dut(<0,2>)}=4ve(3)=max{ve(0)+dut(<0,3>)}=5ve(4)=max{ve(1)+dut(<1,4>),ve(2)+dut(<2,4>)}=7ve(5)=max{ve(3)+dut(<3,5>)}=7ve(6)=max{ve(4)=dut(<4,6>)}=16ve(7)=max{ve(4)+dut(<4,7>)}=14ve(8)=max{ve(6)+dut(<6,8>),ve(7)+dut(<7,8>)}=18(2)計(jì)算各頂點(diǎn)（事件）的最遲發(fā)生時(shí)間：vl(8)=ve(8)=18vl(7)=min{vl(8)-dut(<7,8>)}=14vl(6)=min{vl(8)-dut(<6,8>)}=16vl(5)=min{vl(7)-dut(<5,7>)}=10vl(4)=min{vl(6)-dut(<4,6>),vl(7)-dut(<4,7>)}=7vl(3)=min{vl(5)-dut(<3,5>)}=8vl(2)=min{vl(4)-dut(<2,4>)}=6vl(1)=min{vl(4)-dut(<1,4>)}=6vl(0)=min{vl(1)-dut(<0,1>),vl(2)-dut(<0,2>),vl(3)-dut(<0,3>)}=0(3)計(jì)算各活動(dòng)的最早開始時(shí)間：e(a1)=ve(0)=0e(a2)=ve(0)=0e(a3)=ve(0)=0e(a4)=ve(1)=6e(a5)=ve(2)=4e(a6)=ve(3)=5e(a7)=ve(4)=7e(a8)=ve(4)=7e(a9)=ve(5)=7e(a10)=ve(6)=16e(a11)=ve(7)=14(4)計(jì)算各活動(dòng)的最遲開始時(shí)間：l(a11)=vl(8)-dut(<7,8>)=14l(a10)=vl(8)-dut(<6,8>)=16l(a9)=vl(7)-dut(<5,7>)=10l(a8)=vl(7)-dut(<4,7>)=7l(a7)=vl(6)-dut(<4,6>)=7l(a6)=vl(5)-dut(<3,5>)=8l(a5)=vl(4)-dut(<2,4>)=6l(a4)=vl(4)-dut(<1,4>)=6l(a3)=vl(3)-dut(<0,3>)=3l(a2)=vl(2)-dut(<0,2>)=2l(a1)=vl(1)-dut(<0,1>)=0對(duì)圖7.24所示網(wǎng)的計(jì)算結(jié)果如下所示。圖7.25關(guān)鍵路徑7.6.1單源點(diǎn)最短路徑單源點(diǎn)最短路徑是指：給定一個(gè)出發(fā)點(diǎn)(單源點(diǎn))和一個(gè)有向網(wǎng)G=(V，E)，求出源點(diǎn)到其它各頂點(diǎn)之間的最短路徑。迪杰斯特拉(Dijkstra)在做了大量觀察后，首先提出了按路徑長度遞增的次序產(chǎn)生從一個(gè)頂點(diǎn)到其余各頂點(diǎn)的最短路徑算法，我們稱之為迪杰斯特拉算法。首先，引入一個(gè)輔助向量dist，它的每個(gè)分量dist[i]表示當(dāng)前所找到的從始點(diǎn)v到每個(gè)終點(diǎn)vi的最短路徑長度。它的初態(tài)為：或者為從v到vi弧上的權(quán)值，或者為無窮大，顯然長度為dist[j]=Min{dist[i]|vi∈V}的路徑就是從v出發(fā)最短的一條最短路徑，此路徑為<v,vj>。那么，下一條次短的最短路徑是哪一條呢？假設(shè)該次短路徑的終點(diǎn)是vk，則這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權(quán)值，或者是dist[