考研計(jì)算機(jī)基礎(chǔ)講義數(shù)據(jù)結(jié)構(gòu)版

考研計(jì)算機(jī)基礎(chǔ)班講 數(shù)據(jù)結(jié) 主講：..........................................................................................................................................數(shù)據(jù)結(jié) 緒 基本概 習(xí) 第一章線性 習(xí) 第二章棧、隊(duì)列和數(shù) 隊(duì) 數(shù) 習(xí) 第三章樹與二叉 1樹的概 二叉 樹和森 樹的結(jié) （Huffman）樹和編 習(xí) 第四章 圖的概 鄰接 圖的遍 習(xí) 第五章查 B樹及其基本操作、B+樹的基本概 散列 處理的方 習(xí) 第六章排 插入排 冒泡排 排 快速排 堆排 基數(shù)排 習(xí) 基本概＝（D，R針反映數(shù)據(jù)元素間的邏輯關(guān)系。這種方式不要求空間連續(xù)，便于動態(tài)操作（如插入、刪間內(nèi)，并將散列函數(shù)的值解釋成關(guān)鍵字所在元素的地址。其特點(diǎn)是存取速度快，只能按算法和算法的衡T(n)n（輸入量的多少，稱之為問題規(guī)模）的某個函數(shù)T(n)＝增大，算法執(zhí)行時間T(n)的增長率和f(n)的增長率相同。常見的漸進(jìn)時間復(fù)雜度有：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜Ο(2n)＜O(n!)＜O(nn)間復(fù)雜度為O(1)。習(xí) voidfn){intx=1;while} B. C. D.解答：A2、以下算法的時間復(fù)雜度是 voidf(intwhile(d>0){if(d%2==1) f=f*f;d=d2;}} B. C. D.whileifp=p*f語句可以不考慮，因?yàn)樗鼒?zhí)行的次數(shù)不超過d=d/2語句的執(zhí)行次數(shù)。f=f*f2T(n)≤n，即T(n)≤log2n=O(log2n)。解答：A比較同一簡單類型的兩個數(shù)據(jù)x1和x2的大小，對于x1>x2,x1=x2和x1<x2這三種不同情 charcompare(SimpleTypex1,SimpleTypex2){if(x1>x2)elseif(x1==x2)return‘=’;elsereturn‘<’;}voidReverse(char{intfor(inti=0;i<n/2;{charch;}}從二維整型數(shù)組a[m][n]voidFind(inta[M][N],intm,intn,int&Lin,int {//MNM>=n和N>=n的條件，Lin和Col為形參，它是對應(yīng)實(shí)參的別名，其值由實(shí)參帶 for(intfor(intif}}voidfunc(int inty=while(y*yy}線性表的定

第一(a1，a2，…ai-其中nn＝0需要說明的是：ai為序號為 線性表的實(shí)線性表的順序結(jié)用這種形式的線性表稱其為順序表。因?yàn)閮?nèi)存中的地址空間是線性的，因此，用物理上的相鄰實(shí)現(xiàn)數(shù)據(jù)元間的邏輯相鄰關(guān)系是既簡單又自然的。設(shè)a１的地址為Loc(a１)，每個數(shù)據(jù)元素占d個地址，則第i個數(shù)據(jù)元素的地址為Loc(ai)=Loc(a１)+(i- #defineLIST_INIT_SIZE100 #defineLISTINCREMENT10 intInit_SqList(SqListL.elem(ElemType*malloc(LIST_INIT_SIZE*sizeof(ElemType));if(!L.elem)exit(OVERFLOW); L.listsize= //初始容return}插入后使原表長為n的表:(a1，a2，...，ai-1，ai，ai+1，...，an)成為表長為n+1表:(a1，a2，...，ai-1，x，ai，ai+1，...，an)。ai～an順序向下移動，為新元素讓出位置；（注意數(shù)據(jù)的移動方向：從后往前依次x置入空出的第iintInsert_SqList(SqList&L，inti，ElemTypeifi1||iL.length+1)return //if(L.length>=L.listsize)returnOVERFLOW;//當(dāng)前空間已滿,不能插q&(L.elem[i- qfor(p=&(L.elem[L.length-1]);p>=q;--*(p+1) //插入位置及之后的元素右*q //插入 //表長增return}ann－i＋1i（i1≤i≤n）個元素從線性表中去掉，刪除后使原表長為n的線性表：(a1，a2，，ai-1，ai，ai+1，...，an)成為表長為n－1的線性表：(a1，a2，...，ai-1ai+1，...，an)。ai+1～an順序向上移動；（注意數(shù)據(jù)的移動方向：從前往后依次前移一個元素intDelete_SqList(SqList&L;inti)ifi1)||(i return //p&(L.elem[i- pe //被刪除元素的值賦給qL.elem+L.length- //for(++p;p<=q;*(p-1)= //被刪除元后的元素左 //表長減return}素時，其后面的元素ai+1～an都要向上移動一個位置，共移動了n-i個元素，線性表的鏈?zhǔn)浇Y(jié)鏈表是通過一組任意的單元來線性表中的數(shù)據(jù)元素的。為建立起數(shù)據(jù)元間的線性關(guān)系，對每個數(shù)據(jù)元素ai，除了存放數(shù)據(jù)元素的自身的信息ai之外，還需要和ai一起存放其后繼ai+1所在的單元的地址，這兩部分信息組成一個“結(jié)點(diǎn)”，結(jié)點(diǎn)的結(jié)構(gòu)如圖所單鏈表結(jié)點(diǎn)typedefstruct//struct//LinkListL的地址放在了指針變量L、H中，頭指針為“NULL”則表示一個空表。鏈表與順序表不同，它是一種動態(tài)管理的結(jié)構(gòu)，鏈表中的每個結(jié)點(diǎn)占用的空間 (){LinkListL=NULL；空表LNodeintx; while(x!=flag) }return}希望次序一致，則用入的方法。因?yàn)槊看问菍⑿陆Y(jié)點(diǎn)插入到鏈表的尾部，所以需加入一個指針r用來始終指向鏈表中的尾結(jié)點(diǎn)，以便能夠?qū)⑿陆Y(jié)點(diǎn)插入到鏈表的尾部。rr指向新結(jié)點(diǎn)（注意 Crea(){LinkList intx; while(x!=flag) //r}if return} 為了方便操作，有時在鏈表的頭部加入一個頭結(jié)點(diǎn)”，頭結(jié)點(diǎn)的類型與數(shù)據(jù)結(jié)點(diǎn)一致，標(biāo)識鏈表的頭指針變量L中存放該結(jié)點(diǎn)的地址，這樣即使是空表，頭指針變量L也不為空了。頭結(jié)點(diǎn)的加入使得第一個結(jié)點(diǎn)”的問題不再存在，也使得空表”和” istR2(){ intx; while(x!=flag)r- //r}returnL;} * L, i); while(p->next!=NULL&&j<i){p=p->next;j++;}if(j==i)returnp;elsereturn}pp×②①s×②①在*p之后插入①s->next=p-q①q①p×②while(q- 單鏈表不具有按序號隨機(jī)的特點(diǎn)，只能從頭指針開始一個個順序進(jìn)行R來標(biāo)識，可以使得操作效率其后繼結(jié)點(diǎn)的指針則為p->next，而找其前驅(qū)則只能從該鏈表的頭指針開始，順著各結(jié)點(diǎn)的nextO(1)O(n)，如果也希望找前驅(qū)的時間性能達(dá)到O(1)，則只能付出空間的代價(jià)：每個結(jié)點(diǎn)再加一個指向前驅(qū)的指針域，typedefElemTypedata;structDuLNodep ②①④③sp指向雙向鏈表中某結(jié)點(diǎn)，sp ②①④③s圖雙向鏈表中的結(jié)①s->prior=p-②p->prior-③s-④p-否則*p的前驅(qū)結(jié)點(diǎn)的指針就丟掉了。 ① 雙向鏈表中刪除結(jié)O(n)(位置習(xí)1、循環(huán)鏈表的主要優(yōu)點(diǎn)是（AD若線性表最常用的運(yùn)算是查找第i個元素及其前驅(qū)的值，則采用（）方式節(jié)省時間單鏈 C．單循環(huán)鏈 D．順序用（）方式最節(jié)省運(yùn)算時間。單鏈 B.僅有頭指針的單循環(huán)鏈C．雙鏈 D.僅有尾指針的單循環(huán)鏈在具有n個結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)（）的操作，其算法的時間復(fù)雜度都是O(n)D．刪除地址為p在n個結(jié)點(diǎn)的順序表，算法的時間復(fù)雜度是O(1)的操作是（）D．將n個結(jié)點(diǎn)從大到小排q->prior=p；（）；A．q-B．q->prior->next=p；C．p->prior->next=p；7A=(a1,a2,am)，B=(b1,b2,bn)均為順序表，試編寫一個比較A?Bintcompare(SqListLa,SqListLb){while(i<La.Length&&{if(La.elem[i]==Lb.elem[i])i++;elseif(La.elem[i]<Lb.elem[i])return-elsereturn}if(i>La.length&&i>Lb.Length) if(i>Lb.Length) return1; return-}mink且小于maxkvoiddelete(LinkList&L,intmink,int{p=L-while(p&&p-{ p=p->next;查找第一個值>minkif(p)while(p&&p- p=p-//≥maxk //whiles=q delete q=s;}//}//}//voidinverse(LinkList&L)//逆置結(jié)點(diǎn)的單鏈表Lp=L->next;L->next=NULL;while(p){ p=succ;}}voidunion(LinkList&Lc,LinkList&La,LinkList&Lb)//La和Lb歸并為非遞增的有序表Lc,歸并之后，La和Lb//上述三個表均為結(jié)點(diǎn)的單鏈表，Lc表中的結(jié)點(diǎn)即為原La或Lb表中的結(jié)點(diǎn)Lc=new Lc->next=paLa pbLb //while(pa||pb) (!pa) {q=pb; pb=pb->next;}elseif (!pb) {q=pa; pa=pa->next;} if(pa->data<=pb->data){q= pa=pa->next; {q= pb=pb->next;q->nextLc Lc->next //}delete delete //釋放La和Lb}//voidDifference_L(LinkList&La,LinkListLb,LinkListLc){La,LbLcLaLcpre=pa; while(pa&&pb&&pc){if(pa->data<pb-{pre=pa; elseif(pb->data<pc->data)else deletepa;pa=pre-}//pbpc}//p=L->next;//L為雙向鏈表的頭指針while(p!=L&&p->data!=x) p=p->next;//搜索元素值為x的結(jié)點(diǎn)*pif(p==L) returnNULL;q=p-while(q!=L&&q->freq<p->freq) q=q->prior;//搜索頻度不小于它的結(jié)點(diǎn)*q將結(jié)點(diǎn)*p從當(dāng)前位置上刪除;*p*q之后;returnp;符可能是英文字母字符或數(shù)字字符或其它字符，編寫算法構(gòu)造三個以結(jié)點(diǎn)的單循環(huán)鏈表voidOneToThree（LinkedList&L，LinkedList&la，LinkedList&ld，LinkedList&{la=（LinkedList）malloc（sizeof（LNode））； r=L;L=L {r->next=la->next；la- ∥處理字母字符elseif（r->data>=‘0’&&r-{r->next=ld->next；ld ∥處理數(shù)字elser->next=lo->next；lo->next=r；}}}第二章棧、隊(duì)列和數(shù)棧棧的實(shí)現(xiàn)和運(yùn)算實(shí) #defineSTACK_INIT_SIZE100 #defineSTACKINCREMENT10 需要注意，在棧的動態(tài)分配順序結(jié)構(gòu)中，base始終指向棧底元素，非空棧中的eintPush(SqStack&S,SElemType{if(S.top- *Stop+ return}SeOK，否則返回intPop(SqStack&S,SElemType ERROR;e=*--S.top;return}N=(Ndivd)×d+Nmodd (其中：div為整除運(yùn)算，mod為求余運(yùn)算）例如：（1348)10=(2504)8，其運(yùn)算過程如下： Ndiv Nmod 出與其等值的八進(jìn)制數(shù)。由于上述計(jì)算過程是從低位到順序產(chǎn)生八進(jìn)制數(shù)的各個數(shù)位，而打印輸出，一般來說應(yīng)從到低位進(jìn)行，恰好和計(jì)算過程相反。因此，若將計(jì)算過程中N≠0Nrs（2）;N=0s的內(nèi)容依次出棧，NrN。voidconversion(){ //構(gòu)造while(N){N=N/8;}while{printf("%d",e}}+、*、/、%、^（乘方）和括號（。（） +、 表達(dá)式作為一個滿足表達(dá)式語則的串，如表達(dá)式3*2^（4-１3）”,它的3*2133#*32^^(433#*32^^(4+2*2- -１*#*^(-3#*^(-)(出-#5#96-5,91圖中綴表達(dá)式3*2^（4+2*2-1*3）-5嚴(yán)格從左向右進(jìn)行，而不用再考慮運(yùn)算規(guī)則和級別。中綴表達(dá)式“3*2^（4+2*2-1*3）-5”的后 charSElemType calcul_exp(char //本函數(shù)返回由后綴表達(dá)式A表示的表達(dá)式運(yùn)算結(jié) swhile(ch!=’#’){ Push(s,ch);else{Pop(s,&a); Pops&b)取出兩個運(yùn)算量switch(ch).{casech==’+’： c=a+b;break;casech==’-’： c=a-b;break;casech==’*’：c=a*b;break;casech==’/’：c=a/b;break;casech==’%’：c=a%b;break;}Push(s,c)}ch=*A++}Pop(s,result); result;} 運(yùn)算符出棧后不是進(jìn)行相應(yīng)的運(yùn)算，而是將其送入B中存放。具體算法在此不再贅述。在高級語言編制的程序中，調(diào)用函數(shù)與被調(diào)用函數(shù)之間的和信息交換必須通過棧進(jìn)從被調(diào)用函數(shù)返回調(diào)用函數(shù)之前，應(yīng)該完成（Activaon統(tǒng)的“遞歸工作?！标?duì)棧是一種后進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)在實(shí)際問題中還經(jīng)常使用一種“先進(jìn)先出”的數(shù)據(jù)結(jié)構(gòu)：入的一端叫隊(duì)尾(rear)，把允許刪除的一端叫隊(duì)頭(front)。隊(duì)列的實(shí)現(xiàn)及運(yùn)算實(shí)#defineMAXQSIZE typedefstruct{ }intEnQueue(SqQueue&Q,QElemType{if((Q.rear+1)%MAXQSIZE==Q.front)returnERROR;Q.base[Q.rear]=e;Q.rear=(Q.rear+1)%return}intDeQueue(SqQueue&Q,QElemType{if(Q.front==Q.rear)returnERROR;e=Q.base[Q.front];Q.front=(Q.front+1)%MAXQSIZE;returnOK;}intQueueLength（SqQueue}typedefstructQNode{//QElemTypedata;structQNode}QNode,typedefstruct{ QueuePtrfront;隊(duì)頭指針QueuePtrrear;//隊(duì)尾指針}定義一個指向鏈隊(duì)列的指針 intEnQueue(LinkQueue&Q,QElemType{QNode*）allocsizeof（QNode）;p->data=e;p->next=Q.rear=p;returnOK;}intDeQueue(LinkQueue&Q,QElemType&e)if(Q.front==Q.rear) p=Q.front->next;ep Q.front->next=p- Q.rear=Q.front; return}特殊矩陣的壓縮數(shù)一個數(shù)據(jù)元素有唯一的一組下標(biāo)來標(biāo)識，因此，在數(shù)組上不能做插入、刪除數(shù)據(jù)元素的操作。現(xiàn)在來討論數(shù)組在計(jì)算機(jī)中的表示。通常，數(shù)組在內(nèi)存被映象為向量，即用向量作為數(shù)組的一種結(jié)構(gòu)，這是因?yàn)閮?nèi)存的地址空間是一維的，數(shù)組的行列固定后，通過一個對于一維數(shù)組按下標(biāo)順序分配即可。對數(shù)組分配時，要把它的元素映象在一維器中，一般有兩種方式：一是以行為主序（或先行后列）的順序存放，即一行分配元，那么aij的物理地址可用一線性尋址函數(shù)計(jì)算：LOC(aij)=LOC(a11)+((i-1)*n+j-1)*LOC(aij)=LOC(a00)+(i*n+j)*d推廣到一般的二維數(shù)組：A[c1..d1][c2..d2]，則aij的物理地址計(jì)算函數(shù)為LOC(aij)=LOC(ac1c2)+((i-c1)*(d2-c2+1)+(j-c2)可以對其元素進(jìn)行隨機(jī)存取，各種矩陣運(yùn)算也非常簡單，并且的密度為1。但是在矩陣陣，如三角矩陣、對稱矩陣、對角矩陣、稀疏矩陣等，從節(jié)約空間的角度考慮，這種存儲是不太合適的，看起來密度仍為1，但實(shí)際上占用了許多單元去重復(fù)的非零元素壓縮：即為多個相同的非零元素只分配一個空間；對零元素不分配空間。線對稱，因此只需上三角或下三角部分即可，比如，我們只下三角中的元素aij，其特點(diǎn)是中j≤i且1≤i≤n，對于上三角中的元素aij，它和對應(yīng)的aji相等，因此當(dāng)?shù)脑卦谏先菚r，直接去和它對應(yīng)的下三角元素即可，這樣，原來需要n*n個單元，現(xiàn)在只需要n(n+1)/2個單元了，節(jié)約了n(n-1)/2個單元。對下三角部分以行為主序順序到一個向量中去，在下三角中共有n*(n+1)/2個元素，角中的某一個元素aij則具體對應(yīng)一個sak，下面的問題是要找到k與i、j之間的關(guān)系。 n(n+1)/2-……a1

第2 第3 第n對稱矩陣的對于下三角中的元素aij，其特點(diǎn)是：i≥j且1≤i≤n，到SA中后，根據(jù)原則，它前i-11+2+…+i-1=i*(i-1)/2aijj個，所以在上面的排列順序中，aiji*(i-1)/2+j個元素，因此它在SA中的下標(biāo)k與i、j的關(guān)系為： (０≤k<n*(n+1)/2若i<j，則aij是上三角中的元素，因?yàn)閍ij=aji，這樣，上三角中的元素aij時則去訪ajiSA

(０≤k<n*(n+1)/2k=I*(I-1)/2+J-1與對稱矩陣類似，不同之處在于存完下三角中的元后，緊接著對角線上方的常SA[n*(n+1)+1]中，這種的方式可節(jié)約n*(n-1)-1個單元，sak與aji的對應(yīng)關(guān)系為： 當(dāng) ……ac1

項(xiàng)第2 第3 第n 項(xiàng)

下三角矩陣的壓縮i個元素，aij的前面有i-1行，共：n+(n-1)+…+(n- (np)p

=(i-1)*(2n-i+2)/2元素，而 綜上，sakaji的對應(yīng)關(guān)系為：(i-1)*(2n-i+2)/2+j- 當(dāng) ……a…c第1 第2

第n行常上三角矩陣為零(或同一個常數(shù)c)。sakaji00000 000000 習(xí)1、若循環(huán)隊(duì)列以數(shù)組Q[0..m-1]作為其結(jié)構(gòu)，變量rear表示循環(huán)隊(duì)列中的隊(duì)尾元素的實(shí)rear=(rear+1)Modmlength表示當(dāng)前循環(huán)隊(duì)列中的元素個數(shù)，則循環(huán)隊(duì)列的隊(duì)首元素的實(shí)際位置是（）.A.rear-B．(rear-length+m)Modm用方式的隊(duì)列，在進(jìn)行刪除運(yùn)算時（A. B. C. D.intsymmetry(charCh[])//若Ch[]為稱字符序列，則返回1,否則返回0。p=Ch;InitStack(S);while(*p!=‘&’){Push(S,*p);p++;}state=1;p++;//濾去字符‘&’while(*p!=‘@’&&state){if(NOTStackEmpty(S)&&GetTop(S)==*p{Pop(S,e);p++;elsestate=}Statusex() // Push(S,ch); }{{Pop(S); elsestate=FALSE;}return}6.下列程序段的功能是什么voiddemo1(sqstack&s){inti;arr[64];n=0;for(i=0;<n;i++)push(s,arr[i]);}voiddemo2(sqstack&s,intm){sqstackt;inti;while(!stackempty(s))while(!{i=pop(t);}}i=66，j=65A. B. C. D.將元素A[k](0≦k﹤m*n)表示成矩陣的第i行、第j列的元素(0≦i﹤m,0≦j﹤n)。A.i=k/n, B.i=k/m,C.i=k/n, D.i=k/m,第三與二叉樹的概樹T中：n>1m（m>0）T1，0的結(jié)點(diǎn)稱為分支結(jié)點(diǎn)，或者稱為非終端結(jié)點(diǎn)。一棵樹的結(jié)點(diǎn)父結(jié)點(diǎn)（1≤i<k）,就把n1,n2,…,nk稱為一條由n1至nk的路徑。這條路徑的長度是k-1。先，而N稱為M的子孫。1 二叉的元素及兩個不相交的、被分別稱為左和右的二叉樹組成。當(dāng)集合為空時，稱該二點(diǎn)只有一棵，也要區(qū)分它是左還是 kn個結(jié)點(diǎn)的二叉樹，對樹中的結(jié)點(diǎn)按從上至下、從左到右的順序進(jìn)行編號，如果編號為i（1≤i≤n）的結(jié)點(diǎn)與滿二叉樹中編號為i的結(jié)點(diǎn)在二叉樹中的位置相同，則性質(zhì) （i≥1性質(zhì) 一棵深度為k的二叉樹中，最多具有2k－1個結(jié)點(diǎn)x（1≤i≤kkM＝

∑2＝2 性質(zhì) 對于一棵非空的二叉樹，如果葉子結(jié)點(diǎn)數(shù)為n0，度數(shù)為2的結(jié)點(diǎn)數(shù)為n2，則有 12性質(zhì) 具有n個結(jié)點(diǎn)的完全二叉樹的深度k為log2n+1或log2(n1)2k、結(jié)點(diǎn)個數(shù)為n時，有2k－1－1<n≤2k- k是整數(shù)，所以有k＝log2n+15n個結(jié)點(diǎn)的完全二叉樹，如果按照從上至下和從左到右的順序?qū)Χ鏄渲械乃薪Y(jié)點(diǎn)從1開始順序編號，則對于任意的序號為i的結(jié)點(diǎn)，有：序號為i的結(jié)點(diǎn)無右孩子。此外，若對二叉樹的根結(jié)點(diǎn)從0開始編號，則相應(yīng)的i(i12，左孩子的編號為2i＋1，右孩子的編2i＋2。二叉樹的所謂二叉樹的順序，就是用一組連續(xù)的單元存放二叉樹中的結(jié)點(diǎn)。一般是按照二叉樹結(jié)點(diǎn)從上至下、從左到右的順序。這樣結(jié)點(diǎn)在位置上的前驅(qū)后繼關(guān)系并不一依據(jù)二叉樹的性質(zhì)，完全二叉樹和滿二叉樹采用順序比較合適，樹中結(jié)點(diǎn)的序號可以唯一地反映出結(jié)點(diǎn)之間的邏輯關(guān)系，這樣既能夠最大可能地節(jié)省空間，又可以利用數(shù)對于一般的二叉樹，如果仍按從上至下和從左到右的順序?qū)渲械慕Y(jié)點(diǎn)順序在一維這種對于需增加許多空結(jié)點(diǎn)才能將一棵二叉樹改造成為一棵完全二叉樹的時，會造成空間的大量浪費(fèi)，不宜用順序結(jié)構(gòu)。的情況是右單支樹，一棵深度為k的右單支樹，只有k個結(jié)點(diǎn)，卻需分配2k－1個單元。#defineMAX_TREE_SIZE100 typedefemTypeSqBiTree[MAX_TREE_SIZE]//0號單元存放根結(jié)點(diǎn)SqBiTree //將b定義為含有MAX_TREE_SIZE個emType類型元素的一維數(shù)其中，daa域存放某結(jié)點(diǎn)的數(shù)據(jù)信息；lchildrchild ypedata;structBiTNode //左右孩子指其中，data、lchildrchild三個域的意義與二叉鏈表結(jié)構(gòu)相同；parent域?yàn)橹赶蛟摻Y(jié)點(diǎn)雙親結(jié)點(diǎn)的指針。這種結(jié)構(gòu)既便于查找孩子結(jié)點(diǎn)，又便于查找雙親結(jié)點(diǎn)；但是，相對因此，二叉鏈表是最常用的二叉樹方式，本書后面所涉及到的二叉樹的鏈?zhǔn)浇Y(jié)構(gòu)不voidPreOrder（BiTree{ifVisit（b- PreOrder（b- //先序遞歸b的左PreOrder（b- }}（1）中序遍歷根結(jié)點(diǎn)的左（3）中序遍歷根結(jié)點(diǎn)的右{if //中序遞歸遍歷b的左 //結(jié)點(diǎn)的數(shù)據(jù)域 //中序遞歸遍歷b的右}}voidPostOrder（BiTree{ifPostOrder（b->lchild）;//后序遞歸遍歷b的左PostOrder（b->rchild）;//后序遞歸遍歷b的右 }}voidLevelOrder（BiTree{BiTreeQueue[MAX_TREE_SIZE];intVisit(Queue[++front]- if(Queue[front]->lchild!=NULL) Queue[++rear]=Queue[front]->lchild;if(Queue[front]->rchild!=NULL) Queue[++rear]=Queue[front]->rchild;}}三種遍歷路線正是從根結(jié)點(diǎn)開始沿左深入下去，當(dāng)深入到最左端，無法再深入下去時，則返回，再逐一進(jìn)入剛才深入時遇到結(jié)點(diǎn)的右，再進(jìn)行如此的深入和返回，直到最后從根結(jié)點(diǎn)的右返回到根結(jié)點(diǎn)為止。先序遍歷是在深入時（第一次經(jīng)過）遇到結(jié)點(diǎn)就訪問，中序遍歷是在從左返回時（第二次經(jīng)過）遇到結(jié)點(diǎn)，后序遍歷是在從右返結(jié)構(gòu)后進(jìn)先出的特點(diǎn)。因此，可以用棧來幫助實(shí)現(xiàn)這一遍歷路線。其過程如下：在沿左后從該結(jié)點(diǎn)的右繼續(xù)深入；若為后序遍歷，則將此結(jié)點(diǎn)再次入棧，然后從該結(jié)點(diǎn)的右子次從棧里彈出該結(jié)點(diǎn)，才之。 inttop=0;{while(p!=NULL)Visit(p- else{} }if(top<=0)return; else{ //從棧出棧頂元 //指針指向p}}}只需將先序遍歷的非遞歸算法中的Visit(p->data)移到p=Stack[--top]和p=p->rchild叉樹中每個結(jié)點(diǎn)在這個序列中的直接前驅(qū)結(jié)點(diǎn)和直接后繼結(jié)點(diǎn)是什么，二叉樹的結(jié)構(gòu)中n個結(jié)點(diǎn)的二叉樹中的葉子結(jié)點(diǎn)和一個具有n個結(jié)點(diǎn)的二叉樹若采用二叉鏈表結(jié)構(gòu)，在2n個指針域中只有n－1個指針域是用來結(jié)點(diǎn)孩子的地址，而另外n＋1個指針域存放的都是NULL。因此，可以利用通常為每個結(jié)點(diǎn)增設(shè)兩個標(biāo)志位域ltag和rtag，令：

typedefstructBiThrNode{ structBiThrNode }BiThrNode,為了將二叉樹中所有空指針域都利用上，以及操作便利的需要，在線索二叉樹時往實(shí)質(zhì)上就是遍歷一棵二叉樹。在遍歷過程中，Visit操作是檢查當(dāng)前結(jié)點(diǎn)的左、右指針域針pre始終指向剛剛過的結(jié)點(diǎn)，即若指針p指向當(dāng)前結(jié)點(diǎn)，則pre指向它的前驅(qū)，以便增intInOrderThr(BiThrTree&head,BiThrTreeT)if(!(head=(BiThrNode*)malloc(sizeof(BiThrNode)))) if(!T)head->lchild=head; pre=head; }return}p){if(p){InThreading(p- //左線索if(!p->lchild){ }if(!pre->rchild){ pre-}InThreading(p- //右線索}}②如果該結(jié)點(diǎn)的左標(biāo)志為0，表明該結(jié)點(diǎn)有左孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的左孩子為根結(jié)點(diǎn)的的最右結(jié)點(diǎn)，即沿著其左的右指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的右標(biāo)志為1時，它就是所要找的前驅(qū)結(jié)點(diǎn)。{BiThrTreepre;if(p-while(pre->rtag==0)pre=pre-}②如果該結(jié)點(diǎn)的右標(biāo)志為0，表明該結(jié)點(diǎn)有右孩子，根據(jù)中序遍歷的定義，它的前驅(qū)結(jié)點(diǎn)是以該結(jié)點(diǎn)的右孩子為根結(jié)點(diǎn)的的最左結(jié)點(diǎn)，即沿著其右的左指針鏈向下查找，當(dāng)某結(jié)點(diǎn)的左標(biāo)志為1時，它就是所要找的后繼結(jié)點(diǎn)。BiThrTreeInPostNode（BiThrTree{BiThrTreepost;if(p-}以上給出的僅是在中序線索二叉樹中尋找某結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)的算法。序樹和森樹的結(jié)在計(jì)算機(jī)中，樹的有多種方式，既可以采用順序結(jié)構(gòu)，也可以采用鏈?zhǔn)浇Y(jié)構(gòu)，但無論采用何種方式，都要求結(jié)構(gòu)不但能各結(jié)點(diǎn)本身的數(shù)據(jù)信息，還要能唯一地反映樹中各結(jié)點(diǎn)之間的邏輯關(guān)系。下面介紹幾種基本的樹的方式。一組連續(xù)的空間（一維數(shù)組）樹中的各個結(jié)點(diǎn)，數(shù)組中的一個元素表示樹中的一個號，樹的這種方法稱為雙親表示法。其表示可描述為：#define 100//typedefstruct #defineMAXNODE100 typedefstructChildNode{intstructChildNode}typedefstruct structChildNode emTypedata;structTreeNode*son;structTreeNode 這樣，對樹的操作實(shí)現(xiàn)就可以借助二叉樹，利用二叉樹上的操作來實(shí)現(xiàn)。（詳見PPT）①根結(jié)點(diǎn)②根結(jié)點(diǎn)（Huffman）樹和編1.樹的基本概n個帶權(quán)值的葉結(jié)點(diǎn)，那么 WPL＝∑W k和不同的帶權(quán)路徑長度，那么如何找到帶權(quán)路徑長度最小的二叉樹（即樹）呢？根據(jù)而權(quán)值越小的葉結(jié)點(diǎn)越遠(yuǎn)離根結(jié)點(diǎn)。（Haffman）依據(jù)這一特點(diǎn)提出了法，這種n個權(quán)值{W1，W2，…，Wn}n棵只有一個葉結(jié)點(diǎn)的二叉樹，從而得到一個二叉樹的集合F＝{T1，T2，…，Tn}；在F中選取根結(jié)點(diǎn)的權(quán)值最小和次小的兩棵二叉樹作為左、右構(gòu)造一棵新的二叉樹，在集合F中刪除作為左、右的兩棵二叉樹，并將新建立的二叉樹加入到集合F中（2（3）2.編然而，采用樹進(jìn)行編碼，則不會產(chǎn)生上述二義性問題。因?yàn)?，在樹中，每夫曼編碼不可能是另一個字符的編碼的前綴，從而保證了譯碼的非二義性。求編碼，實(shí)質(zhì)上就是在已建立的樹中，從葉結(jié)點(diǎn)開始，沿結(jié)點(diǎn)的雙親鏈域回退到根結(jié)點(diǎn)，每回退一步，就走過了樹的一個分支，從而得到一位碼值，由于一個字符的編碼是從根結(jié)點(diǎn)到相應(yīng)葉結(jié)點(diǎn)所經(jīng)過的路徑上各分支所組成的0，1序列，因此先得到的分支代碼為所求編碼的低位碼，后得到的分支代碼為所求編碼的碼。習(xí) AD2、已知某二叉樹的中序、層序序列為DBAFCE、FDEBCA，則該二叉樹的后序序列為（A. B.C. D.后序遍歷序列中x在y之后，則x和y的關(guān)系是（。A．x是y的左兄 B.x是y的右兄 D.x是y的后 A.n在m的右 B.n是m的祖C.n在m的左 D.n是m的子答：構(gòu)造的樹如下a:b:c:d:e:f:g:平均長度2*4+3*4+6*3+7*3+8*3+10*2+14*2)/50131/50 node*fch,*nsib;intLeaves(Tree if(t=null)return elsereturn(Leaves(t->fch)+Leaves(t-}第四圖的概VRADTGraph數(shù)據(jù)關(guān)系R：VR＝{<v,w>|v,w∈VP(v,w)，<v,w>v到w的弧，謂詞P(v,w)定義了弧<v,w>的意義或信息}無向圖：在一個圖中，如果任意兩個頂點(diǎn)構(gòu)成的偶對（v,w）∈E是無序的，即頂有向圖：在一個圖中，如果任意兩個頂點(diǎn)構(gòu)成的偶對（v,w）∈E是有序的即頂為無向完全圖。在一個含有n個頂點(diǎn)的無向完全圖中，有n(n-1)/2條邊。連接，則稱該圖為有向完全圖。在一個含有n個頂點(diǎn)的有向完全圖中，有n(n-1)條邊。ID(v)vv為始點(diǎn)的弧的數(shù)目，記為OD(v)。TD(v)=ID(v)＋ODv)n（weight（networkvim,vq（vp,vi1，(vi1,vi2)，…,(vim,.vq)分別為圖中的邊。子圖：對于G=（V，E，G’=（V’，E’V’V的子E’E的子集，則稱圖G’是G的一個子圖。vivj是連通的。如果圖中任意兩頂點(diǎn)都是連通的，則稱該圖是連通圖。無向圖的vivj(i≠j)均有從一個頂vi到另一個頂vj有路徑vjvi的路徑，則稱該有向圖是強(qiáng)連通圖。有GGn個頂點(diǎn)的一個極小連通Gn-1條邊。在生成樹中添加任意一條屬于原圖中的邊必定會圖的及基本操系為一個n×n的矩陣，矩陣的元素為：

若(vi,vj)或<vi,vj>是E(G)中的{ 若(v,v或<vv不是E(G){i i

若(vi,vj)或<vi,vj>是E(G)中的邊0或∞若(vv或<vvE(G)中的邊{i i{其中，wij表示邊(vi,vj)或<vi,vj>上的權(quán)值；∞表示一個計(jì)算機(jī)允許的、大于所有邊上權(quán)值i行（i列）非零元素（或非∞元素）的個數(shù)正好是第i個頂點(diǎn)的度TD(vi)。i行（i列）非零元素（或非∞元素）的個數(shù)正好i個頂點(diǎn)的出度OD(vi)（或入度ID(vi)。在用鄰接矩陣圖時，除了用一個二維數(shù)組用于表示頂點(diǎn)間相鄰關(guān)系的鄰接矩陣外，還需用一個一維數(shù)組來頂點(diǎn)信息，另外還有圖的頂點(diǎn)數(shù)和邊數(shù)。故可將其形式描述#defineMAX_VERTEX_NUM20 //最大頂點(diǎn)數(shù)設(shè)為20typedefcharVertexType; typedefintVRType; typedefstruct{ //VRTypeedges[MAX_VERTEX_NUM][MAX_VERTEX_NUM];//鄰接矩陣，即邊表 //MGragh是鄰接矩陣的圖類鄰接表(AdjacencyList)是圖的一種順序與鏈?zhǔn)浇Y(jié)合的方法。鄰接表表示法類似于樹的孩子鏈表表示法。就是對于圖G中的每個頂點(diǎn)vi，將所有鄰接于vi的頂點(diǎn)vj鏈成vi的鄰接表，再將所有點(diǎn)的鄰接表表頭放到數(shù)組中，就頂點(diǎn) 邊鄰接矩陣表(nextarc)構(gòu)成。對于網(wǎng)圖的邊表需再增設(shè)一個邊上信息（如權(quán)值等）的域（info。＃definetypedef ode typedefstruct typedefAdjList //ALGraph是以鄰接表方式的圖類型而在有向圖中，第i個鏈表中的結(jié)點(diǎn)個數(shù)只是頂點(diǎn)vi的出度，為求入度，必須遍歷整個鄰接表。在所有鏈表中其鄰接點(diǎn)域的值為i的結(jié)點(diǎn)的個數(shù)是頂點(diǎn)vi的入度。對每個頂點(diǎn)vi建立一個以vi為頭的弧的鏈表。O（n+eO（n·e頂點(diǎn)（vi和vj）ij個鏈表，因此，不及鄰接矩陣圖的遍圖的遍歷是指從圖中的任一頂點(diǎn)出發(fā)，對圖中的所有頂點(diǎn)一次且只一次。圖的此頂點(diǎn)，然后依次從v的未被的鄰接點(diǎn)出發(fā)深度優(yōu)先遍歷圖，直至圖中所有和v有路徑相通的頂點(diǎn)都被到；若此時圖中尚有頂點(diǎn)未被，則另選圖中一個未曾被的頂點(diǎn)作起始點(diǎn)重復(fù)上述過程，直至圖中所有頂點(diǎn)都被到為止。顯然，這是一個遞歸的過程。為了在遍歷過程中便于區(qū)分頂點(diǎn)是否已被，需附設(shè)訪問標(biāo)志數(shù)組visited[0:n-1],，其初值為FALSE，一旦某個頂點(diǎn)被，則其相應(yīng)的分量置為voidDFSTraverse(GraphG){ for(v=0;v<G.vexnum;++v)visited[v]= for(v=0;v<G.vexnum;if(!visited[v]) }voidDFS(GraphG,intv){ //第v個頂點(diǎn)if(!visited[w]) }被標(biāo)志成已被，就不再從它出發(fā)進(jìn)行搜索。因此，遍歷圖的過程實(shí)質(zhì)上是對每個頂點(diǎn)查找其鄰接點(diǎn)的過程。其耗費(fèi)的時間則取決于所采用的結(jié)構(gòu)。當(dāng)用二維數(shù)組表示鄰接矩陣圖的結(jié)構(gòu)時，查找每個頂點(diǎn)的鄰接點(diǎn)所需時間為O(n2)，其中n為圖中頂點(diǎn)數(shù)。而當(dāng)以鄰接表作圖的結(jié)構(gòu)時，找鄰接點(diǎn)所需時間為O(e)，其中e為無向圖中邊的數(shù)或有向圖中弧的數(shù)。由此，當(dāng)以鄰接表作結(jié)構(gòu)時，深度優(yōu)先搜索遍歷圖的時間復(fù)雜度為O(n+e)。假設(shè)從圖中某頂點(diǎn)v出發(fā)，在了v之后依次v的各個未曾過和鄰接點(diǎn)，然后分別從這些鄰接點(diǎn)出發(fā)依次它們的鄰接點(diǎn)，并使“先被的頂點(diǎn)的鄰接點(diǎn)”先于“后被中尚有頂點(diǎn)未被，則另選圖中一個未曾被的頂點(diǎn)作起始點(diǎn)，重復(fù)上述過程，直至圖中所有頂點(diǎn)都被到為止。換句話說，廣度優(yōu)先搜索遍歷圖的過程中以v為起始點(diǎn)，由近至遠(yuǎn)，依次和v有路徑相通且路徑長度為1,2,…的頂點(diǎn)。廣度優(yōu)先搜索和深度優(yōu)先搜索類似，在遍歷的過程中也需要一個標(biāo)志數(shù)組。并且，voidBFSTraverse(GraphG){ for(v=0;v<G.vexnum;++v)visited[v]= for(v=0;v<G.vexnum;if }voidBFS(GraphG,intv) visited[v]=TRUE;Visit(v); //v //v入隊(duì)列while(!QueueEmpty(Q)) //uif(!visited[w]){ }}}圖的基本應(yīng)n個頂點(diǎn)的無向連通圖，無論其生成樹的形態(tài)如何，所有生成樹中都有且僅有n－1條邊。G＝（V，E）為一網(wǎng)圖，其中V為網(wǎng)圖中所有頂點(diǎn)的集合，E為網(wǎng)圖中所有帶權(quán)邊的集合。設(shè)置兩個新的集UT，其中集U用于存G的最小生成樹中的頂點(diǎn)，集T存放G的最小生成樹中的邊。令集合U的初值為U＝{u1}（假設(shè)構(gòu)造最小生成樹時，從頂點(diǎn)u1出發(fā)T的初值為T＝{}。u，vvU中，將邊（u，v）加入集T中，如此不斷重復(fù)U＝V時，最小生成樹構(gòu)造完畢，這時集合T中包含了最小生成樹的所有邊。while(u，v)＝min{wuv；u∈U，v∈V－U}T＝T＋{(u，Kruskal算法是一種按照網(wǎng)中邊的權(quán)值遞增的順序構(gòu)造最小生成樹的方法。其基本思想是：設(shè)無向連通網(wǎng)為G＝（V，E，令G的最小生成樹為T，其初態(tài)為T＝（V，{}，即開構(gòu)成通分量。然后，按照邊的權(quán)值由小到大的順序，G的邊集E中的各條邊。若被的邊的兩個頂點(diǎn)屬于T的兩個不同的連通分量，則將此邊作為最小生成樹的邊加入到T中，同時把兩個連通分量連接為通分量；若被邊的兩個頂點(diǎn)屬于同通分T1時，此連通分量便為G的一棵最小生成樹。此適用邊稀疏的網(wǎng)的最小生成樹。V長度最短者。其中，從源點(diǎn)到頂點(diǎn)vV例④再下一條路徑長度次短的最短路徑的特點(diǎn)（2）（Dijkstra）算ST＝V－SS中存放已找到最短路個新的頂點(diǎn)u，都要修改頂點(diǎn)v0到集合T中剩余頂點(diǎn)的最短路徑長度值，集合T中各頂點(diǎn)新uu到該頂點(diǎn)的路徑長度值中的較小值。此過程不斷重復(fù)，直到集合T的頂點(diǎn)全部加入到S中為止。（v0，xxS中，那么必然存在另外的終點(diǎn)S中而路徑長度比此路徑還短的路徑，這與我們按路徑長度遞增的順序產(chǎn)生最短路徑的下面介紹Dijkstra算法的實(shí)現(xiàn)vivviD[i]為弧上的權(quán)值；否D[i]D[j]=Min{D[i]|,是D[j]和從vj到vk的弧上的權(quán)值之和。其中，D[i]或者弧（v,vi）D[k](vk∈S和弧（vkvi）上的權(quán)值之和。若〈vivjedges[i][j]為∞（在計(jì)算機(jī)上可用允許的最大值代替。S為已找到從v出發(fā)的最短路徑的終點(diǎn)的集合，它的初始狀態(tài)為空集。那么，從v出發(fā)到圖上其余各頂點(diǎn)D[i]=edges[LocateVex(G,v)][i]②選擇vjD[j]+則修D(zhuǎn)[k]D[k]=D[j]+Dijkstra算法的時間復(fù)雜度為O(n2)n,,（即判別弧（vi,v0）和(v0,vj)是否存在。如果存在，則比較（vi,vj）和（vi,v0,vj）的路徑長vivj0的最短路徑。假如在路徑上再增加v1（viv1）和（v1vj）分別是當(dāng)前找到的中間頂點(diǎn)的序號1vivj0的最短路徑相比較，從中1v2，繼續(xù)進(jìn)行試探。依次類k-1的最短路徑，則將（vivkvj）vivj且中間頂點(diǎn)序號k-1vivjk的最D(-1)，D(0)，D(1)，…，D(k)，D(n-D(- 0≦k≦n-從上述計(jì)算可見，D(1)[i][j]是從vi到vj的中間頂點(diǎn)的序號不大于1的最短路徑的長度；Dk)[i][j]vi到vjk的最短路徑的長度；Dn-1)[i][j]就是vi到vj的最短路徑的長度。AOV的有向圖稱為AOV網(wǎng)。AOV網(wǎng)中，若從頂點(diǎn)i到頂點(diǎn)j之間存在一條有向路徑，稱頂點(diǎn)ijji的后繼。若<i,j>ij的直接前驅(qū)，頂點(diǎn)j是頂點(diǎn)i的直接后驅(qū)。AOV網(wǎng)所代表的一項(xiàng)工程中活動的集合顯然是一個偏序集合。為了保證該項(xiàng)工程得以測試AOV網(wǎng)是否具有回路（即是否是一個有向無環(huán)圖）的方法，就是在AOVijji。若某個AOV網(wǎng)中所有頂點(diǎn)都在它的拓?fù)湫蛄兄?，則說明該AOV網(wǎng)不會存在回路，這時O（e+nAOE銷（如該活動持續(xù)的時間AOE網(wǎng)。AOEvk的所有活動vj,vk>都結(jié)束時，vk代表的才能發(fā)生；而活動<vj,vk>的最早結(jié)束時間為ve[j]+dut(<ve[k]=Max{ve[j]+dutvj, vj, <發(fā)的所有活動<vk，vj>的終點(diǎn)vj的最遲時間vl[j]。vl[k]的計(jì)算方法如下：vl[k]=Min{vl[j]-dut(< vk, (1-4-始。也就是說，活動ai的最早開始時間應(yīng)等于vk的最早發(fā)生時間。因此，有： 由弧<vk,vj>>表示，則ai的最晚開始時間要保證vj的最遲發(fā)生時間不拖后。因此，應(yīng)該 l[i]=e[i]l[i]>e[i]的活動則不是關(guān)鍵活動，l[i]-e[i]的輸入e條弧<j,k>,建立AOE-網(wǎng)的結(jié)構(gòu)如果得到的拓?fù)溆行蛐蛄兄许旤c(diǎn)個數(shù)小于網(wǎng)中頂點(diǎn)數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路vnvl[n-1]=ve[n-1],按逆拓?fù)溆行蚯笃溆喔黜旤c(diǎn)的最遲發(fā)生時間若某條弧滿足條件e(s)=l(s),則為關(guān)鍵活動。習(xí)接矩陣為A[1…n,1…n]，且壓縮在B[1…k]，則k的值至少為（。 B.C.(n- D.n(n-分析：簡單無向圖的鄰接矩陣是對稱的，且對角線元素均是0，故壓縮只 2n個結(jié)點(diǎn)、k條邊的非連通無向圖是一個森林（n>k，則該森林中必有（） B. C.n- D.3G36條邊的非連通無向圖（不含自回路和多重邊G至少有（） B. C. D.通，則n=10。 【分析】當(dāng)有向圖中無回路時，從某頂點(diǎn)出發(fā)進(jìn)行深度優(yōu)先遍歷時，出棧的順序（第五查找的基本概nASLP1C1P2C2 Pii個數(shù)據(jù)元素的概率，Cii個數(shù)據(jù)元素時，已經(jīng)typedefstruct}//順序查找某個記錄的關(guān)鍵字值與給定值相等，則查找成功，返回該記錄的位置，反之，若直 structElemType*elem;//數(shù)據(jù)元素空間基址，建表時按實(shí)際長度分配，0號單元留 //}intSearch_Seq(SSTableST,KeyTypekey)ST.elem[0].key=key; //設(shè)置“哨兵” //從后往前return //找不到時，i}nASL=∑Pi（n-Pi=

n ｎA(yù)SL=∑─（n-i+1）=i=1 度，其為O(n)。折半查找折半查找要求查找表用順序結(jié)構(gòu)存放且各數(shù)據(jù)元素按關(guān)鍵字有序（升序或降序）排intSearch_Bin(SSTableST,KeyTypekey)low high //while(low<=high)mid=(low+high)/if（key mid;// if(key<ST.elem[mid].key)high=mid- //繼續(xù)半?yún)^(qū)間進(jìn)行查 lowmid //}return //}可以看到，查找表中任一元素的過程，即是判定樹中從根到該元素結(jié)點(diǎn)路徑上各結(jié)點(diǎn)關(guān)nk2k-1-1<n≤2k-1k-1<log2n+1)所進(jìn)行的關(guān)鍵碼比較次數(shù)至多為log2(n+1)ｎ假設(shè)表中每個元素的查找是等概率的，即Pi=i2i-1ｎnASL=∑— —ｎ=ｎ＋１log(n+1)-1≈log(n+1)- n動態(tài)查找樹 KeyTypekey)if(!b)return elseif(b->data.key==key)returnb; elseif(key＜b->data.key) //在左中繼續(xù)查 //在右中繼續(xù)查}key，為將其插入，先voidInsertBST(BiTree KeyType{BiTreeif(bt==NULL){//遞歸結(jié)束條件s->data.key=key;}elseif(key＜bdata.key)InsertBST(b //s插入左elseif(key＞b InsertBST(b->rchild,keys}intDeleteBST(BiTree KeyTypekey)if return if(EQ(key,b->data.key))Delete //keyelseif(LT(key,b->data.key))DeleteBST(b->lchild,key); DeleteBST(b->rchild,key);return}}voidDelete(BiTree&p// //右空則只需重接它的左q=}elseifp->lchild) //只需重接它的右q=}else //左右均不q=s=p-while(!s->rchild){ q=s;s=s-}p->datas if(q!=p)q->rchild=s- //重接*q的右elseq->lchilds- //重接*q的左}}對給定序列建立二叉排序樹，若左右均勻分布，則其查找過程類似于有序表的折半n個關(guān)鍵字，構(gòu)造所得的不同形態(tài)的各棵二叉排序樹的平均查找長度的由關(guān)鍵字序列1，2，3，4，5構(gòu)造而得的二叉排序樹，ASL=（1+2+3+4+5）/5=3。3，1，2，5，4構(gòu)造而得的二叉排序樹，ASL（1+2+3+2+3）52.2。 和 行平衡化調(diào)整。設(shè)a結(jié)點(diǎn)為失去平衡的最小根結(jié)點(diǎn)，對該進(jìn)行平衡化調(diào)整歸納起來cBDa0BDah

圖RR型 在圖(a)所示的樹上插入結(jié)點(diǎn)x，如圖(b)所示。結(jié)點(diǎn)x插入在結(jié)點(diǎn)c的右 E上，導(dǎo)致結(jié)點(diǎn)a的平衡因子絕對值大于1，以結(jié)點(diǎn)a為根的失去平衡。由于結(jié)點(diǎn)c的左D可作為結(jié)點(diǎn)a的右，將結(jié)點(diǎn)a為根的 調(diào)整為左是B，右是D，再將結(jié)點(diǎn)a為根的調(diào)整為結(jié)點(diǎn)c的左 ，結(jié)點(diǎn)c為新的根結(jié)點(diǎn)，如圖(c)。方向，則要作左單旋轉(zhuǎn)，即以結(jié)點(diǎn)c為軸逆時針旋轉(zhuǎn)。一個方向，則要作右單旋轉(zhuǎn)，即以結(jié)點(diǎn)c為軸順時針旋轉(zhuǎn)，如圖所示。h

cB aBD D 圖LL型點(diǎn)b的右上，并使結(jié)點(diǎn)b的右高度增1，從而使結(jié)點(diǎn)a的平衡因子的絕對值大EEhF-GhhF-GhLR型插入EGhGhEGhGhxF xFh c.再右旋EGhhEGh xhx

c EDFhEDFh- f.再右旋LR型調(diào)整過沿插入路徑檢查三個點(diǎn)直線上的同一個方向，則要作右單旋轉(zhuǎn)，即以結(jié)點(diǎn)c為軸順時針旋轉(zhuǎn)，如圖(c、f)。的關(guān)鍵碼個數(shù)不超過樹的深度。在平衡樹上進(jìn)行查找的時間復(fù)雜度為O(logn)。 樹及其基本操作、B+⑶除根結(jié)點(diǎn)之外的所有非終端結(jié)點(diǎn)至少有m/2棵鍵碼均大于Kn，m/21≤n≤m1，n為關(guān)鍵碼的個數(shù)。息指向的中去查找，當(dāng)?shù)竭_(dá)葉子結(jié)點(diǎn)時，則說明樹中沒有對應(yīng)的關(guān)鍵碼，查找失敗。即B-樹上的查找過程是一個順指針查找結(jié)點(diǎn)和在結(jié)點(diǎn)中查找關(guān)鍵碼交叉進(jìn)行的過程。結(jié)點(diǎn)信息比在內(nèi)存中進(jìn)行關(guān)鍵碼查找耗時多，所以，在磁盤上結(jié)點(diǎn)信息的次數(shù)，即B-樹的層次樹是決定B-樹查找效率的首要因素。那么，對含有n個關(guān)鍵碼的m階B-樹，情況下達(dá)到多深呢？可按二叉平衡樹進(jìn)行類似分析。首先，討論m階B-數(shù)各層上的最少結(jié)點(diǎn)數(shù)。B-12個結(jié)點(diǎn)；由于除根結(jié)點(diǎn)外的每個非終端結(jié)點(diǎn)至少有m2棵，則第三層至少有2(m2)個結(jié)點(diǎn)；……；以樹有n個關(guān)鍵碼，則葉子結(jié)點(diǎn)即查找不成功的結(jié)點(diǎn)為n+1，由此有：nn+1≥2*（m/2n即klogm2

12n上涉及的結(jié)點(diǎn)數(shù)不超過logm/22.B+

2⑴有n棵的結(jié)點(diǎn)中含有n個關(guān)鍵碼值≤Ki，則應(yīng)繼續(xù)在Ai所指中進(jìn)行查找。B+樹查找的分析類似于B-樹。散列散列表與散列方法：選取某個函數(shù)，依該函數(shù)按關(guān)鍵碼計(jì)算元素的位置并按此存keykey與地址單元中元素關(guān)鍵碼進(jìn)行比n個數(shù)據(jù)元素的集合，總能找到關(guān)鍵碼與存放地址一一對應(yīng)的函數(shù)。若最大關(guān)鍵為m，可以分配m個數(shù)據(jù)元素存放單元，選取函數(shù)f(key)=key即可，但這樣會造成空間的很大浪費(fèi)，甚至不可能分配這么大的空間。通常關(guān)鍵碼的集合比散列地址集合大得多，H(key) 或者H(key)akey此法僅適合于：地址集合的大小==關(guān)鍵字集合的大小s位數(shù)字組成(k1,k2,kn)，分析關(guān)鍵字集中的H(key)keyMOD p≤m表長pp很重要，若散列表表長為m，則要p≤m，且接近m或等于m。p一般選取質(zhì)數(shù)，也可以是不包含小于20H(key)=Random(key)，其中，Random為偽隨機(jī)函數(shù)。的范圍和形態(tài))，總的原則是使產(chǎn)生的可能性降到盡可能地小。處理的方所謂開放定址法，即是由關(guān)鍵碼得到的散列地址一旦產(chǎn)生了，也就是說，該地址已 (1≤i<mHash(key)為散列函數(shù)，m為散列表長度，di1，2，……，m-1，且線性探測法可能使第i個散列地址的同義詞存入第i+1個散列地址，這樣本應(yīng)存入第i+1個散列地址的元素變成了第i+2個散列地址的同義詞，……，因此，可能出現(xiàn)很多元素在相鄰的散列地址上“堆積”起來，大大降低了查找效率。為此，可采用二次探測法改善“堆積”問題。其中：Hash(key)為散列函數(shù)，m為散列表長度，m4k+3的質(zhì)數(shù)(k是整數(shù)d12，-12，22，-22，……，q2，-q2i

q≤1m2（行。鏈地址法適用于經(jīng)常進(jìn)行插入和刪除的情況。對于給定值K,計(jì)算散列地址i=H(K)，r[i]NULL，則查找不成功若r[i].key=K，則查找成功否則求下一地址Hi，直至r[Hi]= 或r[Hi]key= 介紹的處理的方法中，產(chǎn)生后的查找仍然是給定值與關(guān)鍵碼進(jìn)行比較的過程。所以，查找過程中，關(guān)鍵碼的比較次數(shù)，取決于產(chǎn)生的多少，產(chǎn)生的少，查找效率就高，產(chǎn)生的多，查找效率就低。因此，影響產(chǎn)生多少的因素，也就是影響查找效率散列表的裝填因子定義為：α=────────────α是散列表裝滿程度的標(biāo)志因子。由于表長是定值，α與“填入表中的元素個數(shù)”成正比，所以，α越大，填入表中的元素較多，產(chǎn)生的可能性就越大；α越小，填入表中的元素較少，產(chǎn)生的可能性就越小。處理的方1(1 1 1處理的方1(1 1 1U1(1 (11ln(1 12Unc)習(xí)1、利用逐點(diǎn)插入建立序列（50，72，43，85，75，2035，45，65，30）對應(yīng)的二叉排序樹以后，要查找元素30要進(jìn)行（）次元素間的比較。 B. D. （即離插入結(jié)點(diǎn)最近且平衡因子的絕對值為2的結(jié)點(diǎn)）為 A．27 D.4、在常用的描述二叉排序樹的結(jié)構(gòu)中，關(guān)鍵字值最大的結(jié)點(diǎn)（左指針一定為空B.C．左右指針均為空D.5、設(shè)順序的某線性表共有123個元素，按分塊查找的要求等分為3塊。若對索引表采用分塊查找成功的平均查找長度為（。 B. C. D.平均查找長度為23。 C．二叉 D．散列的平均探查次數(shù)不超過1.5，則散列表能夠至少容納（）個表項(xiàng)。 8n2n的遞增有序表，最少需要進(jìn)行關(guān)鍵字比較（）次。 突。假設(shè)裝填因子α=0.75，散列函數(shù)的形式為H(K)=KMODP，回答下列問題：解答：由α=0.75，得表長m=11/0.75=15.排序的基本概

第六n個記錄的序列{R1，R2，…，Rn}，其相應(yīng)關(guān)鍵字的序列是{K1，K2，…，Kn}，相應(yīng)p2，…，pn，使得相應(yīng)關(guān)鍵字滿足如下的非遞減（或非遞增）關(guān)系，即：Kp1≤Kp2≤…≤Kpn，插入排n個記nnR[0]=R[i]; //設(shè)置“哨兵”for(j=i-1;R[0].key<R[j].key; //從后往return //R[j+1]=R[j]（3）i2，3，n,voidInsertionSort(ElemR[ int{for(i=2;i<=n;++i)R[0]= //為監(jiān)視for(j=i-1;R[0].key< --jR[j+1] //R[j+1] //}}記錄按關(guān)鍵碼逐個比較得到的。平均情況下總比較次數(shù)約為n2/4。既然是在有序表中確定插中查找冒泡排R[n-R[n-無序序列R[1..n-序序列中關(guān)鍵字最大的記錄“交換”R[n-i+1]的位置上。voidBubbleSort(ElemR[],inti iwhile(i>1)for(j=1;j<i;j++) (A[j+1]<A[j])lastExchangeIndex=}i=}} 2總比較次數(shù)(j1) n(n2j簡單選擇排i趟簡單選擇排序是，從無序序列R[i..n]的n-i+1記錄中選出關(guān)鍵字最小的記錄加入有序序列。n1個記錄交換；第二趟，n-12i趟，則從第i個記錄開始的n-i+1個記錄中選出關(guān)鍵碼最小的記錄與第i個記錄交換，直到整voidSelectSort(ElemR[],intn){ //對記錄序列R[1..n]作簡單選擇排序。for(i=1;i<n;++i){ //選擇第i小的記錄，并交換到位kSelectMinKey(R, //R[i..n]keyif(i!=j) //i個記錄交}}【性能分析穩(wěn)定性：不同對簡單選擇排序的穩(wěn)定性有爭議，一般認(rèn)為，若是從前往后比較來選擇第ii小的記錄則該算法是不穩(wěn)排效率依然較高，其時間效率可提高到O(n)。排序即是從這兩點(diǎn)出發(fā)，給出插入排序的改進(jìn)方法。排序的基本思想是：先將待排序記錄序列分割成若干個“較稀疏的”子序列，分d1的記錄分成一組，進(jìn)行組內(nèi)直接插入排序，然后再取兩個記錄間的距離因子序列的選取，特定情況下可以準(zhǔn)確估算出關(guān)鍵碼的比較次數(shù)和記錄的移動次數(shù)。目前還沒有人給出選取最好的步長因子序列的方法。步長因子序列可以有各種取法，有取奇數(shù)的，也11。快速排intPartition1(ElemR[],intlow,inthigh)pivotkey while(low<high) while(low<high&& //while(low<h