【正文】 符prenext=sp。 min=a[i][j]。i++) {row[i]=a[i][0]。 // a是m行n列的二維數(shù)組,本算法求所有馬鞍點(diǎn) { int max[]=0,min[]=0。cb=Bnext。} preright=ptriht。amp。 br=height(btrchild)。 preorder(bt,n,2*i)。 //若左子女非空，則左子女入隊(duì)列 if (prchild!=null) enqueue (q,prchild)； //若右子女非空，則右子女入隊(duì)列 }}} // 算法結(jié)束 6．12void preorder (bitree *t)。 tag:0..1 } stack。(*t)lchild),x)。 t=tlchild。 //p的左標(biāo)記為0，左子女plchild是后序前驅(qū), 否則，線索plchild指向p的后序前驅(qū) }AGBLHCMIDNPJEOQKFR前序序列：ABCDEFGHIJKLMPQRNO后序序列：BDEFCAIJKHGQRPMNOL 7,19,2,6,32,3,21,10其對應(yīng)字母分別為a,b,c,e,f,g,h。found=0。假定該有向圖以鄰接表存儲(chǔ)，各頂點(diǎn)的鄰接點(diǎn)按增序排列DFS序列：V1,V3,V6,V7,V4,V2,V5,V8BFS序列：V1,V3,V4,V6,V7,V2,V5,V8DFS森林 BFS森林V1 V2 V1 V2 V3 V4 V3 V4 V5 V5 V6 V7V6 V8 V8V77．6簡單回路指起點(diǎn)和終點(diǎn)相同的簡單路徑。若出棧元素個(gè)數(shù)等于頂點(diǎn)數(shù)，則拓?fù)渑判虺晒?，輸出的是逆拓?fù)渑判蛐蛄?。if (numn) printf(“ 從”,”v”,”頂點(diǎn)開始拓?fù)渑判虿荒茼樌瓿?”)； else printf(“拓?fù)渑判虺晒Γ敵龅氖且粋€(gè)逆拓?fù)湫蛄?\n”)。}//while(p!=null)}// dfs7．7 （1）PRIM算法的最小生成樹 bbbeb 2 2 2 2 2 2addadaa 1ccbebgeeb 2 2 2 2 2 2dada 2 2 2da 1 1 1 1 1 1 1hacfc 1hfc 1 1 1 1（2）KRUSKAL算法的最小生成樹dbggee 1 2 2cda 2 1 1 1 1 1hac hf 1 1 1（權(quán)值相同的邊選取無順序）7．8所選頂點(diǎn)已選定點(diǎn)的集合尚未被選頂點(diǎn)的集合DIST[2] [3] [4] [5] [6]初態(tài){1}{2，3，4，5，6}20 15 ∞ ∞ ∞3{1，3}{2，4，5，6}19 ∞ ∞ 252{1，3，2}{4，5，6} ∞ 29 256{1，3，2，6}{4，5} 29 294{1，3，2，6，4}{5} 295{1，3，2，6，4，5}{}注：選定點(diǎn)4和5時(shí)無優(yōu)先順序，二者最短路徑均為297．9 0 8 ∞ 1 2 0 0:11A0= 3 0 ∞ path0 = 1 2 0 1:12 5 2 0 1 2 3 ∞:1到3沒有直接通路 0 8 ∞ path1同path0,加入頂點(diǎn)1后無變化A1= 3 0 ∞ 5 2 0 0 8 ∞A2= 3 0 ∞ path2同path1 5 2 ∞ 0 8 ∞A3= 3 0 ∞ 本題不好，終態(tài)和初態(tài)無變化V4V6V3 5 2 0V27．10V1V5V6V6V3V4V2V3V4V6V4V6V5V3V1V6V1V2V6V4V2V3V3V2V4V4V3共七種用TOPOSORT算法求得第七種，即V5,V6,V1,V2,V3,V4.用鄰接表存儲(chǔ)結(jié)構(gòu)，鄰接點(diǎn)逆序即編號(hào)大的排在前面。}//有通路，退出 else {p=g[x].firstarc。 if （!visited[k]）dfs(k)。 // 沒有值為x的結(jié)點(diǎn) } // 算法結(jié)束 中序序列BDCEAFHGA后序序列DECBHGFAFBGCDHE前序序列 ABCDEFGHA 后序線索樹： BCDEFHE null只有空指針處才能加線索。 tdata !=x || top){ while (t amp。 if (*t!=null) { if ((*t)data==x) // 根結(jié)點(diǎn)數(shù)據(jù)域?yàn)閤 {p=*t。 visit(*t)。 {處始化隊(duì)列，隊(duì)列元素為二叉樹結(jié)點(diǎn)的指針} enqueue(q,ht)。i是數(shù) // 組下標(biāo)，初始調(diào)用時(shí)為1。 } (1) head((p,h,w))=p(2) tail((b,k,p,h))=(k,p,h)(3) head(((a,b),(c,d)))=(a,b)(4) tail(((a,b),(c,d)))=((c,d))(5) head(tail(((a,b),(c,d)))=(c,d)(6) tail(head(((a,b),(c,d))))=(b) (1) (2) (1) 第6章 樹和二叉樹（參考答案）(1)根結(jié)點(diǎn)a 三個(gè)結(jié)點(diǎn)的樹的形態(tài)： 三個(gè)結(jié)點(diǎn)的二叉樹的形態(tài)： （2） （3） （1） （1） （2） （4） （5）6．3 設(shè)樹的結(jié)點(diǎn)數(shù)是n，則n=n0+n1+n2+……+nm+ (1)設(shè)樹的分支數(shù)為B，有n=B+1n=1n1+2n2+……+mnm+1 (2)由（1）和（2）有：n0=n2+2n3+……+(m1)nm+1(1) ki1 (i為層數(shù))(2) (n2)/k+1(3) (n1)*k+i+1(4) (n1)%k !=0。 //以下是將pbt插入A表相應(yīng)行鏈表中 i=pbtright。pt=chb[i]。 // a[i][j]是否是馬鞍點(diǎn) if( max[j]==i) printf(“馬鞍點(diǎn) A[%d][%d]=%d”,i,j,a[i][j])。i++) for (j=1。 if(kk=m)printf(“馬鞍點(diǎn) i=%d,j=%d,a[i][j]=%d”,i,j,a[i][j])。 k=1。 sp=prenext。else if (sch[i]==’\0’amp。 // 和Y中字符比較 if (!q) return(ch)。 strcat（A,B）=”mule”（b） （b）typedef struct node{char data。 // rear指向隊(duì)尾元素,quelen為元素個(gè)數(shù)}sequeue。 // 修改隊(duì)尾指針 return (q)。 default: printf(“棧編號(hào)輸入錯(cuò)誤”)。//?？誩lse x=sv[stop]。typedef struct // 兩棧共享一向量空間 { ElemType v[m]。 p=pnext。 // 將p結(jié)點(diǎn)從鏈表上摘下。 Bnext=p。// p為工作指針，指向A表的當(dāng)前元素，r為當(dāng)前元素的后繼指針,使表避免斷開。 // 保留后繼結(jié)點(diǎn)的指針 pbnext=Cnext。//頭結(jié)點(diǎn)摘下，指針域置空。 int i=0。} // 查找插入位置 prenext=s。 A[ni]=temp。 // 計(jì)算新右移元素的下標(biāo) } A[empty]=temp。 // 查找插入位置 for (j= elenum1。}node。習(xí)題解答(唐策善版)(其他版本在上面)第一章 緒論（參考答案） (1) O(n)(2) (2)node sa[MAXSIZE]。j=i。 // 把一輪右移中最后一個(gè)元素放到合適位置 num++。 }for(i=0。 snext=p。// p為工作指針，指向當(dāng)前元素，i 表示鏈表的長度 while (p) { i++。算法中頭指針C始終不變 while (pa amp。 // 逆置 Cnext=pb。 //算法思想是取出當(dāng)前元素，根據(jù)是字母、數(shù)字或其它符號(hào)，分別插入相應(yīng)表中。} // 將數(shù)字字符插入B 表 else {pnext=Cnext。 ppriornext=pnext。 }if (n % 2 !==0) p=pnext。 // ?？捎每臻g0—m1 int top[2] // 棧頂指針}twostack。break。return(0)。} // 算法結(jié)束 (3) linklist *delqueue(linklist *q)//q是以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示的隊(duì)列的尾指針，這是出隊(duì)算法{ if (q==qnext) return (null)。(1) int empty(sequeue *cq) // cq為循環(huán)隊(duì)列，本算法判斷隊(duì)列是否為空 { return (cqquelen==0 ? 1: 0)。struct node *next ；}linkstring。 insert(B,1,A)=”mule”（l） （l） // 找到Y(jié)中沒有的字符 else { pre=pnext。amp。 tp=Tnext。 // b數(shù)組記最小值的列號(hào)，k記最小值的個(gè)數(shù) for(j=1。 } // END OF for jj } // END OF for i 最壞時(shí)間復(fù)雜度為O(m*(n+n*m)). (最壞時(shí)所有元素相同，都是馬鞍點(diǎn)) 解法2: 若矩陣中元素值互不相同,則用一維數(shù)組row記下各行最小值，再用一維數(shù)組col記下各列最大值， 相等者為馬鞍點(diǎn)。jn。 } // END OF for jj } 時(shí)間復(fù)雜度為O(m*n+m). （1）三元組表（行號(hào) 0—5，列號(hào) 0—5）S=（（0，0，15），（0，3，22），（0，5，15），（1，1，11），（1，2，3），（2，3，6），（4，0，91），（5，2，28））（2）：兩矩陣A和B相加的結(jié)果是一矩陣C，其元素Cij有三種情況；（1）Cij=Aij（Bij =0）；（2）Cij=Bij（Aij =0）；（3）Cij=Aij+Bij 。pre=pt。pt=cha[i]。 其右兄弟的編號(hào) n+1（1）順序存儲(chǔ)結(jié)構(gòu) 1 2 3 4 5 6 7 8 9 10 11 12 13 14ABCDEFGH注：為空結(jié)點(diǎn) A C B ^^ E ^ F ^ ^ D^ H ^^ G ^(1) 前序 ABDGCEFH(2) 中序 DGBAECHF(3) 后序 GDBEHFC