數據結構期末復習

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

，…,an）2.1

線性表的邏輯結構1.線性表的定義：是n個數據元素的有限序列n=0時稱為數據元素線性起點ai的直接前趨ai的直接后繼下標，是元素的序號，表示元素在表中的位置n為元素總個數，即表長空表線性終點線性表的抽象數據類型的定義：

ADTList{

數據對象：D={ai|ai∈Elemset,i=1,2,…,n,n≥0}

數據關系：R1={<ai-1,ai>|ai-1,ai∈D,i=2,…,n}

基本操作：

InitList(&L)

操作結果：構造一個空的線性表LDestroyList(&L)

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

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

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

LOC(ai+1)=LOC(ai)+L線性表的順序存儲結構示意圖a1a2……aiai+1……an

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

數據域：元素本身信息指針域：指示直接后繼的存儲位置數據域指針域結點與鏈式存儲有關的術語：1、結點：數據元素的存儲映像。由數據域和指針域兩部分組成；2、鏈表：n個結點由指針鏈組成一個鏈表。它是線性表的鏈式存儲映像，稱為線性表的鏈式存儲結構。3、單鏈表、雙鏈表、多鏈表、循環(huán)鏈表：

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

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

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

12345的輸出可以實現，只需壓入一個立即彈出一個即可。

435612中到了12順序不能實現；

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

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

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

，也就是說隊列的修改是依先進先出的原則進行的。

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

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

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

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

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

一般記作S=“a1a2a3…an”，其中S是串名，雙引號括起來的字符序列是串值；ai(1≦i≦n)可以是字母、數字或其它字符；串中所包含的字符個數稱為該串的長度。長度為零的串稱為空串(EmptyString)，它不包含任何字符。空白串：通常將僅由一個或多個空格組成的串稱為空白串(BlankString)

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

A=“Thisisastring”B=“is”則B是A的子串，A為主串。B在A中出現了兩次，其中首次出現所對應的主串位置是3。因此，稱B在A中的序號（或位置）為3。特別地，空串是任意串的子串，任意串是其自身的子串。

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

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

刪除串S中從第i個字符開始連續(xù)len個字符。5.2數組的順序表示和實現由于計算機的內存結構是一維的，因此用一維內存來表示多維數組，就必須按某種次序將數組元素排成一列序列，然后將這個線性序列存放在存儲器中。又由于對數組一般不做插入和刪除操作，也就是說，數組一旦建立，結構中的元素個數和元素間的關系就不再發(fā)生變化。因此，一般都是采用順序存儲的方法來表示數組。通常有兩種順序存儲方式：按行序為主序存儲a11a12……..a1n

a21a22……..a2n

am1am2……..amn

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

按行序為主序存放amn……..

am2am1……….a2n……..

a22a21a1n

…….a12

a1101n-1m*n-1n通常有兩種順序存儲方式：按列序為主序存儲

按列序為主序存放01m-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

計算二維數組元素地址的通式

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

ad1,c2…ad1,d2

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

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

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

個字節(jié)。288例3：設數組a[1…60,1…70]的基地址為2048，每個元素占2個存儲單元，若以列序為主序順序存儲，則元素a[32,58]的存儲地址為

。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答：請注意審題！利用列優(yōu)先通式：答：

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

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

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

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

若i<j，則aij是在上三角矩陣中。因為aij=aji，所以只要交換上述對應關系式中的i和j即可得到：

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

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

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

(b,c)),B是長度為2的廣義表，第一項為原子，第二項為子表。C=(x,y,z)，C是長度為3的廣義表，每一項都是原子。D=(B,C)，D是長度為2的廣義表，每一項都是上面提到的子表。E=(a,E)是長度為2的廣義表，第一項為原子，第二項為它本身。3．廣義表的深度一個廣義表的深度是指該廣義表展開后所含括號的層數。例如，A=(b,c)的深度為1，B=(A,d)的深度為2，C=(f,B,h)的深度為3。4．取表頭運算head若廣義表LS=(a1,a2,…,an)，則head(LS)=a1。取表頭運算得到的結果可以是原子，也可以是一個子表。例如，head((a1,a2,a3,a4))=a1head(((a1,a2),(a3,a4),a5))=(a1,a2)5．取表尾運算tail若廣義表LS=(a1,a2,…,an)，則tail(LS)=(a2,a3,…,an)。即取表尾運算得到的結果是除表頭以外的所有元素，取表尾運算得到的結果一定是一個子表。值得注意的是廣義表()和(())是不同的，前者為空表，長度為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))】】＝

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

;6.GetHead【(())】＝

.7.GetTail【(())】＝

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

具有n個結點的完全二叉樹的深度k為log2n+1。證明：根據性質2，對于有n個結點的深度為k的完全二叉樹有

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

2k-1≤n<2k于是，有k-1≤log2n<k，因為k必須是整數，所以k=log2n+1

。證畢。2.鏈式存儲結構對于任意的二叉樹來說，每個結點只有兩個孩子，一個雙親結點。我們可以設計每個結點至少包括三個域：數據域、左孩子域和右孩子：leftChilddatarightChild其中，leftChild域指向該結點的左孩子，data域記錄該結點的信息，rightChild域指向該結點的右孩子。用C語言可以這樣聲明二叉樹的二叉鏈表結點的結構：typedefstructbtNode{TElemTypedata;structbtNode*leftChild;structbtNode*rightChild;}BiTNode,*BiTree;有時，為了便于找到父結點，可以增加一個parent域，parent域指向該結點的父結點。該結點結構如下：leftChilddataparentrightChild6.3.1二叉樹的遍歷

遍歷是各種數據結構最基本的操作，許多其他的操作可以在遍歷基礎上實現。二叉樹的遍歷：沿某條路徑周游二叉樹，對樹中的每個結點訪問一次且僅訪問一次?！霸L問”的含義很廣，可以是對結點的各種處理，如修改結點數據、輸出結點數據。一、遍歷的基本概念二、兩種基本策略：廣度遍歷深度遍歷

如何訪問二叉樹的每個結點，而且每個結點僅被訪問一次？？

A

F

E

D

C

B廣度遍歷策略層次遍歷方法：從上到下、從左到右訪問各結點適用于順序存儲結構012345678ABCDφEφφF存儲結構遍歷結果：ABCDEF

A

F

E

D

C

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

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

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

A

F

G

E

D

C

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

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

A

F

G

E

D

C

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

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

A

F

G

E

D

C

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

。

A）ABCDEFGHIJB）ABDEGHJCFIC）ABDEGHJFICD）ABDEGJHCFIABDEGHJCFI

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

。

A.PBCDE

B.DECBP

C.EBDCP

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

–1B.2k-1

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

A．acbedB．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．上面的都不對2.輸出二叉樹中的葉子結點輸出二叉樹中的葉子結點與輸出二叉樹中的結點相比，它是一個有條件的輸出問題，即在遍歷過程中走到每一個結點時需進行測試，看是否有滿足葉子結點的條件。/*先序遍歷輸出二叉樹中的葉子結點,*/voidpreOrder(btreeroot){if(root!=NULL){if(root->lchild==NULL&&root->rchild==NULL)printf(root->data);/*輸出葉子結點*/

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

0

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

假設有n個權值，試構造一個有n個葉子結點的二叉樹，每個葉子結點帶權為wi，則其中帶權路徑長度WPL最小的二叉樹稱作最優(yōu)二叉樹或哈夫曼樹。例：有4個結點a、b、c、d，權值分別為7，5，2，4，構造有4個葉子結點的二叉樹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)練習：下圖所示二叉樹帶權路徑長度？（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．哈夫曼樹的構造假設有n個權值，則構造出的哈夫曼樹有n個葉子結點。n個權值分別設為w1,w2,…,wn，則哈夫曼樹的構造規(guī)則為：(1)根據給定的n個權值{w1,w2,…wn}構成n棵二叉樹的集合F={T1,T2,…,Tn}(2)每次選擇兩個權值最小的二叉樹做子樹合并為一個新的二叉樹，新二叉樹的權值為兩個子樹的和。直到森林中只剩一棵樹為止，該樹即為我們所求得的哈夫曼樹。下面給出哈夫曼樹的構造過程，假設給定的葉子結點的權分別為1,5,7,3，則構造哈夫曼樹過程如圖所示。

(a)初始森林

3

7

51

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

7

134

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

在遠程通訊中，要將待傳字符轉換成由二進制組成的字符串。對字符的編碼可以采用定長編碼，也可以采用不定長編碼。定長編碼：每個字符的編碼都用固定長度。不定長編碼：出現頻率高的字符用短編碼，出現頻率低的字符用長編碼。

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

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

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

譯文只能是“CAT”例：給定一組數列（15，8，10，21，6，19，3）分別代表字符A、B、C、D、E、F、G出現的頻度。（1）構造哈夫曼樹，計算其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.度、入度和出度對于無向圖而言，頂點v的度是指和v相關聯邊的數目，記作TD(v)。在有向圖中頂點v的度有出度和入度兩部分，其中以頂點v為弧頭的弧的數目成為該頂點的入度，記作ID(v)，以頂點v為弧尾的弧的數目稱為該頂點的出度，記作OD(v)，則頂點v的度為TD(v)=ID(v)+OD(v)。一般地，若圖G中有n個頂點，e條邊或弧，則圖中頂點的度與邊的關系如下：

V0

V4

V3

V1

V2

V0

V1

V2

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

nextarc:指針域，指示下一條邊或弧的結點info:存儲和邊或弧相關的信息，如權值等。201234m-1ABCD標data

firstarc1.無向圖的鄰接表表示

AED

B

C286435鄰接鏈表？？A

E

DB

C

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

First

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

First

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

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

V0

V7

V6

V5

V4

V3

V2

V1深度優(yōu)先遍歷（DFS）課堂練習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)}，對該圖進行深度優(yōu)先遍歷，得到的頂點序列正確的是（）。A．a,b,e,c,d,fB．a,c,f,e,b,dC．a,e,b,c,f,dD．a,e,d,f,c,b2、設下圖如右所示，在下面的5個序列中，符合深度優(yōu)先遍歷的序列有多少？（）aebdfcacfdebaedfcbaefdcbaefdbcA．5個B．4個C．3個D．2個

7.4

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

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

∞

∞0611∞

∞60911∞

∞119073∞

∞13704∞

∞

∞34062111965432174133(1)初始狀態(tài)：任選一點加入U,U={1}，T={}；62111965432174133(2)在U外的頂點中選擇離頂點1最近的點加入U。選頂點2(d(1,2)=1)加入U：U={1，2}將邊（1，2）加入T，T={（1，2）}；262111965432174133(3)在U外的頂點中選擇離集合U（頂點1或2）最近的點加入U。選頂點3(d(1,3)=2)加入U：U={1，2，3}將邊（1，3）加入T，T={(1,2)，(1,3)}；362111965432174133(4)在U外的頂點中選擇離集合U（頂點1或2或3）最近的點加入U。選頂點4(d(3,4)=9)加入U：U={1，2，3，4}將邊（3，4）加入T，T={(1,2),(1,3),(3,4)}；462111965432174133(5)在U外的頂點中選擇離集合U（頂點1或2或3或4）最近的點加入U。選頂點6(d(4,6)=3)加入U：U={1，2，3，4，6}將邊（4，6）加入T，T={(1,2),(1,3),(3,4),(4,6)}；662111965432174133(6)在U外的頂點中選擇離集合U（頂點1或2或3或4）最近的點加入U。選頂點5(d(6,5)=4)加入U：U={1，2，3，4，6}將邊（6，5）加入T，T={(1,2),(1,3),(3,4),(4,6),(6,5)}；5圖7.18普里姆算法構造最小生成樹的過程16543271317918127524101256759410313課堂練習1.用Prim算法畫出下圖的最小生成樹16543265135664252.用Prim算法畫出下圖的最小生成．拓撲排序1.定義給出有向圖G=(V,E)，對于V中的頂點的線性序列(vi1,vi2,...,vin)，如果滿足如下條件：若在G中從頂點vi到vj有一條路經，則在序列中頂點vi必在頂點vj之前；則稱該序列為G的一個拓撲序列（Topologicalorder）。構造有向圖的一個拓撲序列的過程稱為拓撲排序（Topologicalsort）。2.說明(1)在AOV網中,若不存在回路,則所有活動可排成一個線性序列,使得每個活動的所有前驅活動都排在該活動的前面,那么該序列為拓撲序列。(2)拓撲序列不是唯一的。8.6.2拓撲排序算法一、拓撲排序方法下面將介紹怎樣實現拓撲排序，實現步驟如下：(1)在AOV網中選一個入度為0的頂點（沒有前驅）且輸出之；(2)從AOV網中刪除此頂點及該頂點發(fā)出來的所有有向邊；(3)重復(1)、(2)兩步，直到AOV網中所有頂點都被輸出或網中不存在入度為0的頂點。從拓撲排序步驟可知，若在第(3)步中，網中所有頂點都被輸出，則表明網中無有向環(huán)，拓撲排序成功。

若僅輸出部分頂點，網中已不存在入度為0的頂點，則表明網中有有向環(huán)，拓撲排序不成功。因此，一個AOV網的拓撲序列是不唯一的。7.5.2關鍵路徑

有向圖在工程計劃和經營管理中有著廣泛的應用。通常用有向圖來表示工程計劃時有兩種方法：

·用頂點表示活動，用有向弧表示活動間的優(yōu)先關系，即上節(jié)所討論的AOV-網。

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

圖7.24AOE-網

事件vi的最早發(fā)生時間ve(i)：從源點到頂點vi的最長路徑的長度，叫做事件vi的最早發(fā)生時間。求ve(i)時可從源點開始，按拓撲順序向匯點遞推：

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>對應的活動的持續(xù)時間。事件vi的最晚發(fā)生時間vl(i)：在保證匯點按其最早發(fā)生時間發(fā)生這一前提下，求事件vi的最晚發(fā)生時間。在求出ve(i)的基礎上，可從匯點開始，按逆拓撲順序向源點遞推，求出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>對應的活動的持續(xù)時間?；顒觓i的最早開始時間e(i)：如果活動ai對應的弧為<j,k>，則e(i)等于從源點到頂點j的最長路徑的長度，即：e(i)=ve(j)?；顒觓i的最晚開始時間l(i)：如果活動ai對應的弧為<j,k>，其持續(xù)時間為dut(<j,k>),則有：l(i)=vl(k)-dut(<j,k>)，即在保證事件vk的最晚發(fā)生時間為vl(k)的前提下，活動ai的最晚開始時間為l(i)?；顒觓i的松弛時間（時間余量）：ai的最晚開始時間與ai的最早開始時間之差：{l(i)-e(i)}。顯然，松弛時間（時間余量）為0的活動為關鍵活動。求關鍵路徑的基本步驟如下：對圖中頂點進行拓撲排序，在排序過程中按拓撲序列求出每個事件的最早發(fā)生時間ve(i)；按逆拓撲序列求每個事件的最晚發(fā)生時間vl(i)；求出每個活動ai的最早開始時間e(i)和最晚發(fā)生時間l(i)；找出e(i)=l(i)的活動ai，即為關鍵活動。例如，對圖7.24所示的AOE-網計算關鍵路徑的過程如下:(1)計算各頂點（事件）的最早發(fā)生時間：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)計算各頂點（事件）的最遲發(fā)生時間：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)計算各活動的最早開始時間：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)計算各活動的最遲開始時間：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對圖7.24所示網的計算結果如下所示。圖7.25關鍵路徑7.6.1單源點最短路徑單源點最短路徑是指：給定一個出發(fā)點(單源點)和一個有向網G=(V，E)，求出源點到其它各頂點之間的最短路徑。迪杰斯特拉(Dijkstra)在做了大量觀察后，首先提出了按路徑長度遞增的次序產生從一個頂點到其余各頂點的最短路徑算法，我們稱之為迪杰斯特拉算法。首先，引入一個輔助向量dist，它的每個分量dist[i]表示當前所找到的從始點v到每個終點vi的最短路徑長度。它的初態(tài)為：或者為從v到vi弧上的權值，或者為無窮大，顯然長度為dist[j]=Min{dist[i]|vi∈V}的路徑就是從v出發(fā)最短的一條最短路徑，此路徑為<v,vj>。那么，下一條次短的最短路徑是哪一條呢？假設該次短路徑的終點是vk，則這條路徑或者是(v,vk)，或者是(v,vj,vk)。它的長度或者是從v到vk的弧上的權值，或者是dist[