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

1作業(yè)：1、簡述邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)的聯(lián)系？2、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型有什么區(qū)別？3、分析以下算法的時間復(fù)雜度

voidfunc(intn){inti=0,s=0;while(s<n){i++;s=s+i;}}22023/10/1順序表算法設(shè)計練習(xí)：

已知一個順序表L，其中的元素遞增有序排列，設(shè)計一個算法插入一個元素x后保持該順序表仍遞增有序排列。32023/10/1參考算法：Voidinsert(Sqlist&L,ElemTypex){inti=0,j;if(L.length+1>L.listsize)p24while(i<L.length&&x>=L.elem[i])i++;for(j=L.length-1;j>=i;j--)L.elem[j+1]=L.elem[j];L.elem[i]=x;L.length++;}42023/10/1順序表算法設(shè)計練習(xí)：試寫一個算法，實現(xiàn)順序表的就地逆置，即利用原表的存儲空間將線性表。（a1,a2,…,an）逆置為（an,an-1,…,a1）。52023/10/1參考算法：Voidreverse(Sqlist&L){inti=0,j=L.length-1;while(i<j){L.elem[i]<->L.elem[j];i++;j--;}}62023/10/1順序表算法設(shè)計練習(xí)：試設(shè)計一個高效的算法，刪除線性表L中所有值為x的元素。72023/10/1參考算法：Voiddeletelist(Sqlist&L,ElemTypex){intcount=0;for(i=0;i<=L.length-1;i++)if(L.elem[i]==x)count++;elseL.elem[i-count]=L.elem[i];}82023/10/1鏈表算法設(shè)計練習(xí)：設(shè)計一個算法刪除帶頭結(jié)點的單鏈表L中值為x的結(jié)點的直接前驅(qū)結(jié)點。92023/10/1參考算法：Intdelx(Linklist&L,ElemTypex){LinkListp=L,q=p->next,r;If(q!=Null)r=q->next;Elsereturn0;While(r!=Null&&r->data!=x){p=q;q=r;r=r->next;}if(r!=Null){p->next=q->next;free(q);}elsereturn0;return1;}102023/10/1鏈表算法設(shè)計練習(xí)：設(shè)計一個算法，在帶頭結(jié)點的單鏈表head中刪除一個data域值最小的結(jié)點，假設(shè)該結(jié)點唯一。112023/10/1參考算法：VoidDelMinNode(Linklisthead){Linklistp=head->next,pre=head;Linklistminp,minpre;Elemtypemin=p->data;minp=p;minpre=pre;While(p!=NULL){If(p->data<minp->data){min=p->data;minp=p;minpre=pre;}pre=p;p=p->next;}minpre->next=minp->next;Free(minp);}122023/10/11、假設(shè)表達(dá)式中允許包含3種括號：圓括號、方括號和大括號。設(shè)計一個算法采用順序棧判斷表達(dá)式中的括號是否正確配對。Intmatch(charexp[],intn){charst[Maxsize];inttop=-1;inti=0,tag=1;while(i<n&&tag==1){if(exp[i]==‘(’||exp[i]==‘[‘||exp[i]==‘{’){top++;st[top]=exp[i];}if(exp[i]==‘)’)if(st[top]==‘(’top--;elsetag=0;if(exp[i]==‘]’)if(st[top]==‘[’top--;elsetag=0;if(exp[i]==‘}’)if(st[top]==‘{’top--;elsetag=0;132023/10/12、假設(shè)用一個循環(huán)單鏈表表示隊列，并且只設(shè)一個指針rear指向隊尾結(jié)點，但不設(shè)頭指針，設(shè)計出相應(yīng)的隊初始化、入隊算法。VoidinitQu(Qnode*&rear){rear=NULL;}VoldEnQu(Qnode*&rear,ElemTypex){Qnode*s;s=(Qnode*)mallaoc(sizeof(Qnode));s->data=x;if(rear==NULL){s->next=s;rear=s;}else{s->next=rear->next;rear->next=s;rear=s}}142023/10/1作業(yè)：1、設(shè)一系列正整數(shù)存放在一個數(shù)組中，試設(shè)計算法，將所有奇數(shù)存放在數(shù)組的前半部分，將所有的偶數(shù)放在數(shù)組的后半部分。要求盡可能少用臨時存儲單元并使時間最少。2、設(shè)計一個算法，計算一個三元組表表示的稀疏矩陣的對角線元素之和。15例：設(shè)樹T的度為4，其中度為1，2，3和4的結(jié)點個數(shù)分別為4，2，1，1則T中的葉子數(shù)為（）A．5B．6C．7D．8提示：因為每個結(jié)點都有一條枝指向它，分支數(shù)為1*4+2*2+3*1+4*1所有結(jié)點數(shù)為分支數(shù)+1，所以1*4+2*2+3*1+4*1=4+2+1+1+xx=8例：若一棵二叉樹具有10個度為2的結(jié)點，5個度為1的結(jié)點，則度為0的結(jié)點個數(shù)是（）A．9B．11C．15D．不確定提示：

n0=n2+116例3：已知某二叉樹先序序列{ABHFDECKG}和中序序列{HBDFAEKCG},畫出該二叉樹。HBDFEKCGAEKCGABHDFEKCGABHFDEABHFDCKGAKCGEBHFDA17例1：統(tǒng)計二叉樹中葉子結(jié)點的個數(shù)StatusCountLeaf(BiTreeT,int&count){if(T){if((T->lchild==NULL)&&(T->rchild==NULL)){count++;returnOK;}CountLeaf(T->lchild,count);//統(tǒng)計左子樹中葉子結(jié)點個數(shù)

CountLeaf(T->rchild,count);//統(tǒng)計右子樹中葉子結(jié)點個數(shù)

}elsereturnERROR;}18例2：求二叉樹的深度intDepth(BiTreeT){if(!T)depthval=0;else{depthLeft=Depth(T->lchild);depthRight=Depth(T->rchild);depthval=1+max(depthLeft,depthRight);}returndepthval;}19例3：按先序序列建立二叉樹的二叉鏈表已知先序序列：ABC00DE0G00F000（其中0表示空格字符,空指針）建立相應(yīng)的二叉鏈表ABCDEFG20例：對于前序遍歷與中序遍歷結(jié)果相同的二叉樹（）;對于前序遍歷和后序遍歷結(jié)果相同的二叉樹為（）。A．一般二叉樹B．只有根結(jié)點的二叉樹C．根結(jié)點無左孩子的二叉樹D．根結(jié)點無右孩子的二叉樹E．所有結(jié)點只有左子數(shù)的二叉樹F．所有結(jié)點只有右子樹的二叉樹例：某二叉樹的前序序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。A．空或只有一個結(jié)點B．任一結(jié)點無左子樹C．高度等于其結(jié)點數(shù)D．任一結(jié)點無右子樹FB√21例：一棵左子樹為空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：()A．不確定B.0C.1D.2例：一棵左右子樹均不空的二叉樹在先序線索化后，其中空的鏈域的個數(shù)是：()。A.0B.1C.2D.不確定√左子樹為空的二叉樹的根結(jié)點的左線索為空（無前驅(qū)），先序序列的最后結(jié)點的右線索為空（無后繼），共2個空鏈域√只有最后一個葉結(jié)點沒有后繼22例：線索二叉樹是一種（）結(jié)構(gòu)。A．邏輯B．邏輯和存儲C．物理D．線性例：n個結(jié)點的線索二叉樹上含有的線索數(shù)為（）A．2nB．n－1C．n＋1D．n√√N(yùn)個結(jié)點共有2n個指針域，二叉鏈表用了n-1個，剩下n+1個23練習(xí)：寫出下圖所示樹的先序和后序遍歷序列并將之轉(zhuǎn)換成一棵二叉樹ABCDEFHGI先根遍歷：ABDEGHICF后根遍歷：DGHIEBFCAABGDCFHEI246.4.2森林和二叉樹的轉(zhuǎn)換－規(guī)則設(shè)森林F={T1,T2,……Tm}，二叉樹B=（root，LB，RB）(1)森林轉(zhuǎn)化成二叉樹的規(guī)則

若F為空(m=0)，B為空;

若F不空(m≠0)，B的根root(B)是F中第一棵樹T1的根root(T1)；左子樹LB從T1根結(jié)點的子樹森林(T11,T12,…,T1m)轉(zhuǎn)換來；右子樹RB是從森林F’={T2,T3,…,Tm}轉(zhuǎn)換而來。(2)二叉樹轉(zhuǎn)換為森林的規(guī)則若B為空，F(xiàn)為空；

若B非空，則F中第一棵樹T1的根為二叉樹的根root(B)；

T1根的子樹森林F1由B的左子樹LB轉(zhuǎn)換而來；

F中除T1外其余樹組成的森林F’={T2,T3,…,Tn}由B的右子樹RB轉(zhuǎn)換而來。25森林轉(zhuǎn)換成二叉樹步驟1：轉(zhuǎn)換－將各棵樹分別轉(zhuǎn)換成二叉樹步驟2：加線－將每棵樹的根結(jié)點用線相連步驟3：旋轉(zhuǎn)－以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹ABCDEFGHIJ森林FABCDEFGHIJF中每棵樹對應(yīng)的二叉樹26森林轉(zhuǎn)換成二叉樹步驟1：轉(zhuǎn)換－將各棵樹分別轉(zhuǎn)換成二叉樹步驟2：加線－將每棵樹的根結(jié)點用線相連步驟3：旋轉(zhuǎn)－以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹ABCDEFGHIJABCDEFGHIJ森林F27森林轉(zhuǎn)換成二叉樹步驟1：轉(zhuǎn)換－將各棵樹分別轉(zhuǎn)換成二叉樹步驟2：加線－將每棵樹的根結(jié)點用線相連步驟3：旋轉(zhuǎn)－以第一棵樹根結(jié)點為二叉樹的根，再以根結(jié)點為軸心，順時針旋轉(zhuǎn)，構(gòu)成二叉樹ABCDEFGHIJABCDEFGHIJ森林FF轉(zhuǎn)換的二叉樹BABCDEFGHIJ28二叉樹轉(zhuǎn)換成森林步驟1：抹線－將二叉樹根結(jié)點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成多棵二叉樹步驟2：還原－將孤立的二叉樹還原成樹二叉樹BABCDEFGHIJ29二叉樹轉(zhuǎn)換成森林步驟1：抹線－將二叉樹根結(jié)點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成多棵二叉樹步驟2：還原－將孤立的二叉樹還原成樹二叉樹BABCDEFGHIJABCDEFGHIJ30二叉樹轉(zhuǎn)換成森林步驟1：抹線－將二叉樹根結(jié)點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成多棵二叉樹步驟2：還原－將孤立的二叉樹還原成樹ABCDEFGHIJ二叉樹BABCDEFGHIJABCDEFGHIJ31二叉樹轉(zhuǎn)換成森林步驟1：抹線－將二叉樹根結(jié)點與其右孩子連線、沿右分支搜索到的所有右孩子間連線全部抹掉，使之變成多棵二叉樹步驟2：還原－將孤立的二叉樹還原成樹B轉(zhuǎn)換成的森林F二叉樹BABCDEFGHIJABCDEFGHIJABCDEFGHIJABCDEFGHIJ32練習(xí)：寫出下圖所示森林的先序和中序遍歷序列并將之轉(zhuǎn)換成一棵二叉樹EABCDFIJHGK先序遍歷：中序遍歷：ABCDEFIKJGHBEFDCIAJGHK33例：設(shè)F是一個森林，B是由F變換得的二叉樹。若中有n個非終端結(jié)點，則B中右指針域為空的結(jié)點有（）個。A．n-1B．nC．n+1D．n+2每一個非終端結(jié)點的孩子中都會貢獻(xiàn)出一個空的右指針√例：設(shè)F是由T1,T2,T3三棵樹組成的森林,與F對應(yīng)的二叉樹為B,已知T1,T2,T3的結(jié)點數(shù)分別為n1,n2和n3則二叉樹B的左子樹中有

個結(jié)點，右子樹中有

個結(jié)點。n1-1n2+n334構(gòu)造最優(yōu)二叉樹的說明1在選取兩棵根結(jié)點權(quán)值為最小和次小的二叉樹時，如果出現(xiàn)權(quán)值相同的情況，可以在相同權(quán)值的二叉樹中任選一棵。2當(dāng)兩棵根結(jié)點權(quán)值為最小和次小的二叉樹組成新的二叉樹的左右子樹時，誰是左子樹誰是右子樹沒有特殊規(guī)定。3在最優(yōu)二叉樹中沒有度為1的結(jié)點，根據(jù)二叉樹的性質(zhì)3可知有n個葉子結(jié)點的二叉樹有n-1個非終端結(jié)點共有2*n-1個結(jié)點。a7b5c2d461118a7b5d4c26111835如何得到最短的二進(jìn)制前綴碼（赫夫曼編碼）？為了設(shè)計電文總長最短的二進(jìn)制前綴編碼，以n種字符出現(xiàn)的頻率作權(quán)，設(shè)計一棵赫夫曼樹，從根節(jié)點至即所有葉子節(jié)點，按左分支為0，右分支為1的原則即可得到最短二進(jìn)制前綴編碼即赫夫曼編碼。例：已知某系統(tǒng)在通信聯(lián)絡(luò)中只可能出現(xiàn)8種字符，其概率為0.05,0.29,0.07,0.08,0.14,0.23,0.03,0.11,設(shè)計赫夫曼編碼。解：設(shè)權(quán)w=(5，29，7，8，14，23，3，11)360231411529378000000111111110058428291519編碼：3（0111）5（0110）7（1110）

8（1111）11（010）14（110）

23（00）29（10）37練習(xí)：用于通信的電文由8個字母c1,c2,c3,c4,c5,c6,c7,c8組成,各字母在電文中出現(xiàn)的頻率分別為5,25,3,6,10,11,36,4。試設(shè)計不等長Huffman編碼,并給出該電文的總碼數(shù)。00000001001010001010111011電文總碼數(shù)=4*5+2*25+4*3+4*6+3*10+3*11+2*36+4*4=257382023/10/1練習(xí)（1）設(shè)無向圖的頂點個數(shù)為n，則該圖最多有（）條邊。（2）一個有n個結(jié)點的圖，最少有（）個連通分量，最多有（）個連通分量。（3）在一個無向圖中，所有頂點的度數(shù)之和等于所有邊數(shù)的____倍。（4）要連通具有n個頂點的有向圖，至少需要（）條邊。（5）若無向圖G=（V，E）中含7個頂點，則保證圖G在任何情況下都是連通的，則需要的邊數(shù)最少是（）。392023/10/1無向圖鄰接表表示V1V2

V4

V5

V3

頂點的度：該頂點所在單鏈表中表結(jié)點個數(shù)V1V2V3V4V50123413∧04∧202∧12∧14∧3與頂點V1相鄰接的頂點在數(shù)組中的下標(biāo)402023/10/1V1V2

V4

V5

V3

254311鄰接表表示V1V2V3V4V501234123∧4024∧521114∧133042∧3152∧1權(quán)值無向網(wǎng)412023/10/1V1V2

V3

V4

鄰接表表示12∧V1V2∧V3V401233∧0∧以頂點V1為始點的弧的終點頂點在數(shù)組中的下標(biāo)頂點的出度該頂點所在單鏈表中表結(jié)點個數(shù)頂點的入度查詢整個鄰接表中的表結(jié)點，與該頂點的序號（數(shù)組下標(biāo)）一致的表結(jié)點個數(shù)有向圖422023/10/1圖的鄰接表表示問題：具有n個頂點e條邊的無向圖的鄰接表中有多少個表頭結(jié)點？有多個表結(jié)點（邊結(jié)點）？

有向圖呢？432023/10/1練習(xí):

請畫出下圖的鄰接矩陣和鄰接表442023/10/17.3.1深度優(yōu)先搜索-舉例1234V1V3V4V2datafirstarc2783^^^adjvexnextarc5V5641^51282^V6V7V8678736354^^^V1V2V4V5V3V7V6V8深度遍歷：V1

V3V7V6V2V5V8V4給定存儲結(jié)構(gòu)，圖的遍歷序列唯一452023/10/17.3.2廣度優(yōu)先搜索-舉例廣度遍歷：V1V3V2V7V6V5V4V81234V1V3V4V2datafirstarc2783^^^adjvexnextarc5V5641^51282^V6V7V8678736354^^^V1V2V4V5V3V7V6V8給定存儲結(jié)構(gòu)，圖的遍歷序列唯一462023/10/1下列有關(guān)圖遍歷的說法中不正確的是（）A．連通圖的深度優(yōu)先搜索是一個遞歸過程B．圖的廣度優(yōu)先搜索中鄰接點的尋找具有“先進(jìn)先出”的特征C.圖的遍歷要求每一頂點僅被訪問一次D．對圖進(jìn)行一次深度優(yōu)先遍歷可以訪問圖中所有頂點472023/10/1給定有向圖如下：

給出其鄰接表存儲結(jié)構(gòu)基于鄰接表，給出DFS序列和BFS序列482023/10/1練習(xí)：已知一個圖的頂點集V和邊集E分別為：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克魯斯卡爾算法得到最小生成樹，試寫出在最小生成樹中依次得到的各條邊。

【答】用克魯斯卡爾算法得到的最小生成樹為：

(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)20492023/10/1練習(xí)：設(shè)有無向圖G，要求給出用普里姆算法構(gòu)造最小生成樹所走過的邊的集合。

【答】E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}502023/10/17.5.1拓?fù)渑判?實現(xiàn)步驟C1C3C2C7C5C6C4編號課程名稱C1數(shù)學(xué)C2程序設(shè)計C3離散數(shù)學(xué)C4匯編程序設(shè)計C5數(shù)據(jù)結(jié)構(gòu)C6結(jié)構(gòu)程序設(shè)計C7編譯原理C1C3C2C7C5C6C4拓?fù)溆行蛐蛄校篊1=>C3=>C2=>C4=>C6=>C5=>C7邏輯結(jié)構(gòu)上：拓?fù)湫蛄胁晃ㄒ?12023/10/17.5.2關(guān)鍵路徑AOE-網(wǎng)(ActiveOnEdge)：在帶權(quán)的有向無環(huán)圖中，頂點表示事件，弧表示工程的一個活動，弧上權(quán)值表示活動持續(xù)的時間。用來估算工程完成時間。源點：入度為0的頂點。匯點：出度為0的頂點。路徑長度：AOE網(wǎng)中路徑上各活動持續(xù)時間之和。關(guān)鍵路徑：路徑長度最長的路徑。V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7說明：（1）完成工程的最短時間是從開始點到完成點的最長路徑的長度。（2）關(guān)鍵路徑的改變會影響整個工期。522023/10/1設(shè)活動ai在有向無環(huán)圖G的有向邊<j,k>上：事件vj的最早發(fā)生時間ve(j):從源點v0到vj的最長路徑長度。ve(0)=0;ve(j)=從源點到頂點j的最長的路徑長度。ve(k)=Max{ve(j)+dut(<j,k>)}事件vj的最遲開始時間vl(j)：保證匯點vn-1在ve(n-1)時刻完成的前提下，事件vj最遲允許開始的時間。vl(n-1)=ve(n-1)＝從源點到匯點的最長路徑長度;vl(k)=從匯點到頂點k的最短的路徑長度。vl(j)=Min{vl(k)-dut(<j,k>)}kjdut(<j,k>)ai7.5.2關(guān)鍵路徑—定義和術(shù)語532023/10/17.5.2關(guān)鍵路徑—定義和術(shù)語設(shè)活動ai在有向邊<j,k>上,有：活動ai的最早開始時間e(i)：從源點v0到vj的最長路徑長度。e(i)=ve(j);活動ai的最遲開始時間l(i)：是不推遲工程完成的前提下，該活動允許的最遲開始時間。l(i)=vl(k)-dut(<j,k>)活動ai時間余量：l(i)-e(i)關(guān)鍵活動：滿足l(i)=e(i)的活動。關(guān)鍵路徑上的活動都是關(guān)鍵活動。kjdut(<j,k>)ai542023/10/17.5.2關(guān)鍵路徑—求關(guān)鍵活動關(guān)鍵活動e(i)=l(i)e(i)=ve(j)l(i)=vl(k)-dut(<j,k>)ve(j)、vl(j)求頂點（事件）vk的最早開始時間：從ve(0)=0向匯點方向遞推

求頂點（事件）vj的最遲開始時間：從vl(n-1)=ve(n-1)向源點遞推

V1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7ve(k)=Max{ve(j)+dut(<j,k>)}vl(j)=Min{vl(k)-dut(<i,j>)}在拓?fù)溆行虻那疤嵯逻M(jìn)行在逆拓?fù)溆行蚯疤嵯逻M(jìn)行552023/10/1由匯點至源點由源點至匯點1814161078660vl(i)181416775460ve(i)V9V8V7V6V5V4V3V2V1iV1V3V4V6V5V8V2V7V9a1=6a7=9a5=1a2=4a4=1a10=2a3=5a6=2a9=4a11=4a8=7關(guān)鍵路徑是V1,V2,V5,V7,

V9和V1,V2,V5,V8,V9ve(k)=Max{ve(j)+dut(<j,k>)}vl(j)=Min{vl(k)-dut(<j,k>)}e(i)=ve(j);l(i)=vl(k)–dut(<j,k>)14161077866320l(i)000000差1416777546000e(i)a11a10a9a8a7a6a5a4a3a2a1注意：關(guān)鍵路徑可有多條?？s短工期必須縮短關(guān)鍵活動所需的時間562023/10/1如何求關(guān)鍵路徑？(算法思想)（1）輸入e條弧<j,k>，建立AOE網(wǎng)的存儲結(jié)構(gòu)；（2）從源點v0出發(fā)，令ve[0]=0，按拓?fù)溆行蚯笃溆喔黜旤c的最早發(fā)生時間ve[i](1

i

n-1)。如果得到的拓?fù)溆行蛐蛄兄许旤c個數(shù)小于網(wǎng)中頂點數(shù)n，則說明網(wǎng)中存在環(huán)，不能求關(guān)鍵路徑，算法終止，否則執(zhí)行步驟（3）；（3）從匯點vn出發(fā)，令vl[n-1]=ve[n-1]，按逆拓?fù)溆行蚯笥喔黜旤c的最遲發(fā)生時間vl[i](n-2

i

2)（4）根據(jù)各頂點的ve和vl值，求每條弧s的最早開始時間e(s)和最遲開始時間l(s).若某條弧滿足條件e(s)=l(s),則為關(guān)鍵活動。572023/10/1下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（）

A.關(guān)鍵活動不按期完成就會影響整個工程的完成時間

B.某些關(guān)鍵活動提前完成，那么整個工程將會提前完成

C.所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成

D.任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成582023/10/19.2.1二叉排序樹二叉排序樹(二叉查找樹）(BinarySortTree,BST)：空樹或具有下列性質(zhì)的二叉樹:根的左子樹若非空，則左子樹上的所有結(jié)點的關(guān)鍵字值均小于根結(jié)點的值。根的右子樹若非空，則右子樹上的所有結(jié)點的關(guān)鍵字值均大于根結(jié)點的值。它的左右子樹同樣是二叉排序樹。中序遍歷二叉排序樹可得到一個關(guān)鍵字的有序序列592023/10/19.2.1二叉排序樹的插入例：序列45、24、53、12、90構(gòu)成一棵二叉排序樹建BST樹過程：一個無序序列可以構(gòu)造二叉排序樹前提：查找失敗插入的結(jié)點是一個葉子結(jié)點，且是查找失敗時查找路徑上訪問的最后一個結(jié)點的左孩子或右孩子。插入算法：二叉排序樹的存儲結(jié)構(gòu)使用鏈表首先執(zhí)行查找算法，找出被插入結(jié)點的父親結(jié)點。若二叉樹為空。則首先單獨生成根結(jié)點。判斷被插結(jié)點是其父親結(jié)點的左、右孩子。將結(jié)點插入4553902412602023/10/19.2.1二叉排序樹-刪除設(shè)二叉排序樹上被刪除結(jié)點是p，PL是p的左子樹，PR是p的右子樹，p的雙親結(jié)點是f，不失一般性，設(shè)p是f的左孩子。有三種情況：被刪除的結(jié)點p是葉子結(jié)點；被刪除的結(jié)點p只有左子樹或者只有右子樹；被刪除的結(jié)點既有左子樹，也有右子樹。對二叉排序樹，刪去一個結(jié)點相當(dāng)于刪去有序序列中的一個記錄。612023/10/19.2.1二叉排序樹-刪除1）被刪除的結(jié)點p是葉子結(jié)點：修改雙親結(jié)點的指針，令

f->lchild=NULL4553902412pf45539024f例：刪除葉子結(jié)點12622023/10/19.2.1二叉排序樹-刪除2）被刪除的結(jié)點p只有左子樹或者只有右子樹：令PL或PR直接為其雙親結(jié)點f的左子樹即可，f->lchild=p->lchild||p->rchild。4553902412pf45539012f例：刪除結(jié)點24632023/10/19.2.1二叉排序樹-刪除3）被刪除的結(jié)點既有左子樹，也有右子樹。在刪去p結(jié)點前，中序遍歷該二叉樹得到的序列為{…CLC…QLQSLSPPRF…}，即S是中序遍歷序列中被刪結(jié)點p的直接前驅(qū)結(jié)點。方法一：令P的左子樹為F的左子樹，P的右子樹為S的右子樹FPPLPRFPCQSPRCLQLSLFCQSPRCLQLSL642023/10/19.2.1二叉排序樹-刪除3）被刪除的結(jié)點既有左子樹，也有右子樹。在刪去p結(jié)點前，中序遍歷該二叉樹得到的序列為{…CLC…QLQSLSPPRF…}，即S是中序遍歷序列中被刪結(jié)點p的直接前驅(qū)結(jié)點。方法二：令p的直接前驅(qū)S替代p，再從二叉排序樹中刪去S。FPPLPRFPCQSPRCLQLSLFSCQPRCLQLSL652023/10/19.2.1二叉排序樹-刪除舉例刪除454553123732410061907845123732453100619078662023/10/19.2.1二叉排序樹-刪除舉例刪除45451233724531006190783745531237324100619078672023/10/1練習(xí)：假定一棵二叉排序樹采用二叉鏈表存儲結(jié)構(gòu)，其根結(jié)點指針為T,設(shè)計一個算法輸出該二叉排序樹中最大的鍵值和最小的鍵值。682023/10/1statusmaxmindata(){if(!T)returnerror;p=q=T;while(p->lchild!=NULL)p=p->lchild;printf(“Theminimumdatais:%d”,p->data);while(q->rchild!=NULL)q=q->rchild;printf(“Theminimumdatais:%d”,q->data);}692023/10/19.3哈希表查找表的特點：記錄的關(guān)鍵字和在結(jié)構(gòu)中的位置之間無確定關(guān)系查找過程是給定值依次和關(guān)鍵字集合中各個關(guān)鍵字的比較查找效率取決于和給定值進(jìn)行比較的關(guān)鍵字個數(shù)。希望不經(jīng)比較，直接可以找到所查記錄哈希函數(shù)：在記錄的關(guān)鍵字和其在表中位置之間建立一種函數(shù)關(guān)系，即以f(key)作為關(guān)鍵字為key的記錄在表中的位置。702023/10/19.3哈希表定義和術(shù)語沖突：不同關(guān)鍵字得到同一哈希地址，key1

key2，f(key1)=f(key2)同義詞：在一個哈希函數(shù)中具有相同函數(shù)值的不同關(guān)鍵字。

哈希表：根據(jù)設(shè)定的哈希函數(shù)H(key)和所選中的處理沖突的方法，將一組關(guān)鍵字映象到一個有限的、地址連續(xù)的地址集(區(qū)間)上，并以關(guān)鍵字在地址集中的“象”作為相應(yīng)記錄在表中的存儲位置，這種表被稱為哈希表。哈希造表或散列：映象過程。哈希地址或散列地址：所得的存儲位置。構(gòu)造哈希表要注意的問題：考慮選擇一個“好”的哈希函數(shù);

選擇一種處理沖突的方法。712023/10/19.3.3處理沖突的方法1開放定址法：Hi=(H(key)+di)MODmi=1,2,…,k(k≤m-1)，H(key)為哈希函數(shù)；m：哈希表長，di是增量序列，有三種取法di=1,2,…m-1，稱為線性探測再散列di=12,-12,22,-22,…,±k2(k≤m/2)稱為二次探測再散列di=偽隨機(jī)數(shù)列，稱為隨機(jī)探測再散列722023/10/1處理沖突方法舉例例：一組關(guān)鍵字19,14,23,01,68,20,84,27,55,11,10,79；按H(key)=keymod13和線性探測再散列方法處理沖突構(gòu)造表長為16的哈希表。0123456789101112131415311931134121比較次數(shù)200820023010沖突次數(shù)ASLss=1/12（1*6+2+3*3+4+9）=2.5

14

0168275519208479231110732023/10/19.3.3處理沖突的方法例：用哈希函數(shù)H(key)=keyMOD13和鏈地址法處理沖突求一組關(guān)鍵字19,14,23,01,68,20,84,27,55,11,10,79的哈希表：0123456789101112∧∧∧∧∧∧∧01142779∧5568∧1984∧∧1023∧11∧20∧ASLss=1/12(1*6+2*4+3+4)=1.75742023/10/1練習(xí)：已知關(guān)鍵字序列為：（75,33,52,41,12,88,66,27），哈希表長為10，哈希函數(shù)為：H(k)＝k%9，解決沖突用線性探測法，請：（1）構(gòu)造出哈希表；（2）計算等概率下查找成功的平均查找長度。752023/10/1TypedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域

}LNode,*LinkList;二、結(jié)點和單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針762023/10/1TypedefstructLNode{ElemTypedata;//數(shù)據(jù)域

structLnode*next;//指針域

}LNode,*LinkList;二、結(jié)點和單鏈表的C語言描述LinkListL；//L為單鏈表的頭指針772023/10/1三、單鏈表操作的實現(xiàn)GetElem(L,i,&e)//取第i個數(shù)據(jù)元素ListInsert(&L,i,e)//插入數(shù)據(jù)元素ListDelete(&L,i,e)//刪除數(shù)據(jù)元素ClearList(&L)//重置線性表為空表CreateList(&L,n)//生成含n個數(shù)據(jù)元素的鏈表782023/10/1L

線性表的操作

GetElem(L,i,&e)

在單鏈表中的實現(xiàn):211830754256∧pppj123792023/10/1

因此，查找第i個數(shù)據(jù)元素的基本操作為：移動指針，比較j和i。

單鏈表是一種順序存取的結(jié)構(gòu)，為找第i個數(shù)據(jù)元素，必須先找到第i-1個數(shù)據(jù)元素。

令指針p始終指向線性表中第j個數(shù)據(jù)元素。802023/10/1StatusGetElem_L(LinkListL,inti,ElemType&e){//L是帶頭結(jié)點的鏈表的頭指針，以e返回第i個元素}//GetElem_L算法時間復(fù)雜度為:O(ListLength(L))p=L->next;j=1;//p指向第一個結(jié)點，j為計數(shù)器while(p&&j<i){p=p->next;++j;}//

順指針向后查找，直到p指向第i個元素

//

或p為空if(!p||j>i)

returnERROR;//第i個元素不存在e=p->data;//取得第i個元素returnOK;812023/10/1ai-1

線性表的操作ListInsert(&L,i,e)

在單鏈表中的實現(xiàn)：

有序?qū)?lt;ai-1,ai>

改變?yōu)?lt;ai-1,e>和<e,ai>eaiai-1822023/10/1

因此，在單鏈表中第i個結(jié)點之前進(jìn)行插入的基本操作為:

找到線性表中第i-1個結(jié)點，然后修改其指向后繼的指針。

可見，在鏈表中插入結(jié)點只需要修改指針。但同時，若要在第i個結(jié)點之前插入元素，修改的是第i-1個結(jié)點的指針。832023/10/1StatusListInsert_L(LinkListL,inti,ElemTypee){

//L為帶頭結(jié)點的單鏈表的頭指針，本算法

//在鏈表中第i個結(jié)點之前插入新的元素e

}//LinstInsert_L算法的時間復(fù)雜度為:O(ListLength(L))……p=L;j=0;while(p&&j<i-1)

{p=p->next;++j;}

//

尋找第i-1個結(jié)點if(!p||j>i-1)

returnERROR;//

i大于表長或者小于1842023/10/1s=(LinkList)malloc(sizeof(LNode));

//生成新結(jié)點s->data=e;s->next=p->next;p->next=s;//插入returnOK;eai-1aiai-1sp852023/10/1線性表的操作ListDelete(&L,i,&e)在鏈表中的實現(xiàn):有序?qū)?lt;ai-1,ai>和<ai,ai+1>

改變?yōu)?lt;ai-1,ai+1>ai-1aiai+1ai-1862023/10/1

在單鏈表中刪除第

i個結(jié)點的基本操作為:找到線性表中第i-1個結(jié)點，修改其指向后繼的指針。ai-1aiai+1ai-1q=p->next;p->next=q->next;

e=q->data;free(q);pq872023/10/1StatusListDelete_L(LinkListL,inti,ElemType&e){

//刪除以L為頭指針(帶頭結(jié)點)的單鏈表中第i個結(jié)點

}//ListDelete_L算法的時間復(fù)雜度為:O(ListLength(L))p=L;j=0;while(p->next&&j<i-1){p=p->next;++j;}

//尋找第i個結(jié)點，并令p指向其前趨if(!(p->next)||j>i-1)

returnERROR;//刪除位置不合理q=p->next;p->next=q->next;//刪除并釋放結(jié)點e=q->data;free(q);returnOK;882023/10/1操作ClearList(&L)在鏈表中的實現(xiàn):voidClearList(&L){//將單鏈表重新置為一個空表

while(L->next){

p=L->next;L->next=p->next;

}}//ClearListfree(p);算法時間復(fù)雜度：O(ListLength(L))892023/10/1逆位序輸入n個數(shù)據(jù)元素的值，建立帶頭結(jié)點的單鏈表。操作步驟：一、建立一個“空表”；二、輸入數(shù)據(jù)元素an，建立結(jié)點并插入；三、輸入數(shù)據(jù)元素an-1，建立結(jié)點并插入；ananan-1四、依次類推，直至輸入a1為止。902023/10/1voidCreateList_L(LinkList&L,intn){//逆序輸入n個數(shù)據(jù)元素，建立帶頭結(jié)點的單鏈表}//CreateList_L算法的時間復(fù)雜度為:O(Listlength(L))L=(LinkList)malloc(sizeof(LNode));L->next=NULL;//先建立一個帶頭結(jié)點的單鏈表for(i=n;i>0;--i){p=(LinkList)malloc(sizeof(LNode));

scanf(&p->data);//輸入元素值

p->next=L->next;L->next=p;//插入}912023/10/1時間復(fù)雜度為O（La.length+Lb.length）。兩個有序線性表合并為一個有序線性表的算法：voidMergeList_L(LinkList&La,LinkList&Lb,LinkList&Lc){ pa=La->next;pb=Lb->next;

Lc=pc=La; while(pa&&pb){ if(pa->data<=pb->data){ pc->next=pa;pc=pa;pa=pa->next;} else{pc->next=pb;pc=pb;pb=pb->next;} } pc->next=pa?pa:pb; free(Lb);}922023/10/15.3.2稀疏矩陣稀疏矩陣：設(shè)m行n列的矩陣含t個非零元素，則δ=t/(m*n)稱為稀疏因子，通常認(rèn)為

0.05的矩陣為稀疏矩陣。抽象數(shù)據(jù)類型稀疏矩陣的定義：書96頁稀疏矩陣的壓縮存儲稀疏矩陣中非零元素位置無規(guī)律記住非零元素的行i，列j，值aij稀疏矩陣中存在多個非零元素三元組的C語言描述

typedefstruct{inti,j;ElemTypee;}Triple三元組順序表的C語言描述#defineMAXSIZE125000typedefstruct{Tripledata[MAXSIZE+1];intmu,nu,tu;}TSMatrix932023/10/1三元組表表示的稀疏矩陣的轉(zhuǎn)置設(shè)M和T分別是MM和TT的三元組表，如何由M得到T？將矩陣行列值(即m和n)相互交換將每個三元組中的i和j對換重排三元組的次序942023/10/1StatusTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){q=1;for(col=1;col<=M.nu;++col)for(p=1;p<=M.tu;++p)

if(M.data[p].j==col)

{T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;

T.data[q].e=M.data[p].e;++q;}}returnOK;}//TransposeSMatrix三元組表表示的稀疏矩陣轉(zhuǎn)置算法1評價：O(nu*tu)，優(yōu)點:節(jié)省空間，tu<<mu*nu適用對MM的每一列掃描一遍所有非零元952023/10/1三元組表表示的稀疏矩陣轉(zhuǎn)置方法2思想：按M.data的三元組次序轉(zhuǎn)置，再將三元組置入T中適當(dāng)?shù)奈恢谩栴}：轉(zhuǎn)置前需知MM的每列中非零元素個數(shù)及第一個非零元素在T.data中的位置。解決方案：設(shè)num和cpot兩個向量，num[col]：矩陣MM的第col列中非零元素的個數(shù)，cpot[col]:矩陣MM第col列第一個非零元在T.data中的位置cpot[1]=1;cpot[col]=cpot[col-1]+num[col-1](2<=col<=M.nu)StatusFastTransposeSMatrix(TSMatrixM,TSMatrix&T){T.mu=M.nu;T.nu=M.mu;T.tu=M.tu;if(T.tu){for(col=1;col<=M.nu;++col)num[col]=0;for(t=1;t<=M.tu;++t)++num[M.data[t].j];cpot[1]=1;for(col=2;col<=M.nu;++col)cpot[col]=cpot[col-1]+num[col-1];for(p=1;p<=M.tu;++p){col=M.data[p].j;q=cpot[col];T.data[q].i=M.data[p].j;T.data[q].j=M.data[p].i;T.data[q].e=M.data[p].e;++cpot[col];}}returnOK;}//TransposeSMatrix

時間復(fù)雜度為O(nu+tu),若tu~mu*nu則為O(mu*nu)，與經(jīng)典算法相同，多用了兩個輔助向量。三元組表表示的稀疏矩陣轉(zhuǎn)置方法2統(tǒng)計M中每一列的非零元個數(shù)初始化M中每一列第一個非零元應(yīng)該在T中的位置M中col列下一個非零元應(yīng)該在T中的位置972023/10/1稀疏矩陣的壓縮存儲—行邏輯鏈接順序表需求：隨機(jī)存取任一行的非0元方法：記住矩陣每一行第一個非0元在三元組表中的位置設(shè)數(shù)組rpos[1..n]:矩陣中的每行第一個非零元素的起始位置。

rpos[1]=1;rpos[row]=rpos[row-1]+第row-1行的非零元素個數(shù)行邏輯鏈接順序表:在稀疏矩陣存儲結(jié)構(gòu)中固定指示行信息的輔助數(shù)組rpos行邏輯鏈接表存儲結(jié)構(gòu)的Ｃ語言描述：typedefstruct{Tripledata[MAXSIZE+1];

intrpos[MAXRC+1];//各行第一個非零元素位置表

intmu,nu,tu;}RLSMatrix

982023/10/1

0210-2400N=ijv22111-2324行邏輯鏈接表舉例row1234rpos[row]1235N的三元組表

N的rpos向量992023/10/1基于行邏輯鏈接表表示的稀疏矩陣相乘（1）對于每個元素M.data[p](p=1,2……,M.tu)，找到N中滿足條件的N.data[q]，在查找過程中，用到rpos數(shù)組，rpos數(shù)組的含義是稀疏矩陣中每行第一個非零元素在三元組當(dāng)中位置的數(shù)組，rpos[row]：第row行第一個非零元素在N.data中的序號，rpos[row+1]-1：第row行最后一個非零元素在N.data中的序號，最后一個非零元素在N.data中的位置序號是N.tu。求乘積M.data[p].v

N.data[q].v，然后累加。為操作方便，應(yīng)對每個元素設(shè)一個乘積和的變量數(shù)組c