【文章內容簡介】 間復雜度是O(m2*n2)。（4）define MaxSize 線性表可能的最大長度typedef struct { int row, column。} elementtypedef struct { element elem[MaxSize]。int listlength。} SeqList。void GetSaddle(int A[]，int m，int n, SeqlList s[]) /*求矩陣Amn中的鞍點，鞍點的位置存放在順序表s中*/{=0。for(i=0。 im。 i++){for(min=A[i][0], j=0。 jn。 j++)if(A[i][j]min) min=A[i][j]。 /*求一行中的最小值*/for(j=0。 jn。 j++)if(A[i][j]==min) /*判斷這個(些)最小值是否鞍點*/{for(flag=1, k=0。 km。 k++) if(minA[k][j]) flag=0。 /*不是鞍點*/if(flag) /*是鞍點*/ { [listlength].row=i。[listlength].column=j。 ++。}}}} （5）[題目分析]矩陣中元素按行和按列都已排序，要求比較次數不超過m+n，因此不能采用常規(guī)的二層循環(huán)的查找?？梢韵葟挠疑辖牵╥=0,j=n）元素與x比較，只有三種情況：一是A[i,j]x， 這情況下向j 小的方向繼續(xù)查找；二是A[i,j]x，下步應向i大的方向查找；三是A[i,j]=x，查找成功。否則，若下標已超出范圍，則查找失敗。void search(ElementType A[][],int m,int n,ElementType x,int *row,int *column) /* m*n的矩陣b,本算法查找x在矩陣b中的位置（*row,*column）*/ { i=0。 j=n。 flag=0。 /*flag是成功查到x的標志*/while(i=m amp。amp。 j=0 amp。amp。 !flag)if(b[i][j]==x) flag=1。 else if (b[i][j]x) j。 else i++。if(flag) { *row=i。*column=j。}else { *row=1。*column=1。} }[算法討論]算法中查找x的路線從右上角開始，向下（當xb[i,j]）或向左（當xb[i,j]）。向下最多是m，向左最多是n。最佳情況是在右上角比較一次成功，最差是在左下角（b[m,0]），比較m+n次。（6）void TSMatrix_Addto(TSMatrix amp。A,TSMatrix B)//將三元組矩陣B加到A上{for(i=0。i。i++)/*把A的所有元素都移到尾部以騰出位置*/[+i]=[i]。pa=。 pb=0。 pc=0。for(x=0。 x。 x++) /*對矩陣的每一行進行加法*/{while([pa].rx) pa++。while([pb].rx) pb++。while([pa].r==x amp。amp。 [pb].r==x)/*行值相等的元素*/{if([pa].c==[pb].c) /*列值也相等*/{ne=[pa].d+[pb].d。if(ne) /*和不為0*/{[pc].r=x。[pc].c=[pa].c。[pc].d=ne。pa++。 pb++。 pc++。} }else if([pa].c[pb].c) {[pc].r=x。[pc].c=[pb].c。[pc].d=[pb].d。pb++。 pc++。}else{[pc].r=x。[pc].c=[pa].c。[pc].d=[pa].dpa++。 pc++。}}while([pa]==x) /*插入A中剩余的元素(第x行)*/{[pc].r=x。[pc].c=[pa].c。[pc].d=[pa].dpa++。 pc++。}while([pb]==x) /*插入B中剩余的元素(第x行)*/{ [pc].r=x。[pc].c=[pb].c。[pc].d=[pb].d。pb++。 pc++。}}=pc。for(i=。 iMaxSize。 i++) /*清除原來A中的元素*/{ [i].r=1。 [i].c=1。 [i].d=nil。 }}第5章 習題答案(1) cbdeifghmnaljk a m,n,d,j,k,l,f c a,c j,k i,m,n d g,h 2 5 5 3 3(2)非線性 根 雙親(3)5(4)n2+1 (5)完全 log2n +1 最大 n(6)2k1 2k1 2k1(7)2n n1 n+1(8)a在b的左邊(9)2m1(10)58（1）（2）（3）（4）√（5）√（6）√（7）√（8）√（9）√（10）√（1）雙親數組表示法：dataparent0a11b02c03d14e15f26g27h28i49j610k611l712m813n8 孩子鏈表表示法：12Λ0a1b2c3dΛ4e5fΛ6g7h8i9jΛ10kΛ11lΛ12mΛ13Λn34Λ567Λ8Λ910Λ1213Λ11Λ 孩子兄弟表示法：aΛbcΛrootΛdeΛiΛΛmΛnΛΛfghΛΛjΛlΛΛkΛ（2）能唯一確定這棵二叉樹。二叉樹為：ACBDEIFGHJ若給定先序序列和后序序列無法唯一確定一棵二叉樹，因為根據先序序列雖可以確定根，但不可以根據后序序列確定左子樹和右子樹。如下面兩棵二叉樹，它們的先序序列和后序序列相同，但卻確定了兩棵不同的二叉樹。ABBACC（3）總結點數n= n0+ n1+ n2+…+ nm1+ nm ①因為度為1的結點發(fā)出1個分支，度為2的結點發(fā)出2個分支，…，度為m的結點發(fā)出m個分支，葉結點不發(fā)出分支，所以，總分支數B為：B= n1+ 2n2+…+ m* nm ②又因除根之外，其它結點有且僅有一個分支進入，因此，總分支數應等于總結點數減1，即B=n1 ③由②③得：n= n1+ 2n2+…+ m* nm+1 ④由①④得葉結點數：n0= n2+2n3…+ （m1）*nm非終端結點數為：n1+ n2+…+ nm1+ nm（4）①； ②； ③； （5）①第i層的結點數為ki1（其中i=1，2，…，h） ②當i不等于1時，i的雙親為 （i2）/k +1（其中k=2） ③編號為i的非葉子結點的第j個孩子結點的編號是(i1)*k+j+1。 ④編號為i的結點有右兄弟的條件是(i1)%k0，其右兄弟的編號是i+1。（6）（a）先序序列：12345 中序序列：24531 后序序列：54321 （b）先序序列：12345 中序序列：13542 后序序列：54321（c）先序序列：123578624 中序序列：17583624 后序序列：78563421（d）先序序列：124735689 中序序列：472153869 后序序列：742589631先序線索樹：中序線索樹：后序線索樹：132476598132476598NULL132476598NULLNULLNULL先序線索樹中序線索樹后序線索樹（7）①a的先序序列：ABCDEF a的后序序列：BDEFCAb的先序序列：GHIJK b的后序序列：IJKHGc的先序序列：LMPQRNO c的后序序列：QRPMNOL ②森林的先序序列：ABCDEFGHIJKLMPQRNO 森林的后序序列：BDEFCAIJKHGQRPMNOL ③轉換后的二叉樹：AGBDCMLENFHIJKOPQR ④題中圖535改為536 雙親數組表示： 易于求祖先dataparent0A11B02C03D24E25F2孩子鏈表表示法：易于求子孫12Λ0A1BΛ2C3DΛ4EΛ5FΛ345Λ孩子兄弟表示法：易于求子孫AΛΛBCΛrootΛDΛEΛFΛ（8）哈夫曼樹為：72423026161511987642 帶權路徑長度WPL=30*1+16*2+5*4+7*4+8*4+2*5+4*5=172（9）CABCDFAB6EABDFCEGHFHIJKE(a)(b)(c)DG（10）AEBCDFHIGJKLOMN（11）哈夫曼樹及編碼為：