【正文】 1^ 1 G 1 bitree *search(bitree *p)// 查找前序線索二叉樹上給定結(jié)點(diǎn)p的前序后繼 { if (pltag==1) return(prchild)； // 左標(biāo)記為1時，若p的右子樹非空，p的右子樹的根prchild為p的后繼；若右子樹為空，prchild指向后繼 else return(plchild)。 // 左標(biāo)記為0時，p的左子女plchild為p的后繼 .} // 算法結(jié)束 bitree *search（b：tree *p） //在后序線索二叉樹中查找給定結(jié)點(diǎn)的后序前驅(qū)的算法{ if(prtag==0) return(prchild)。 //p有右子女時，其右子女prchild是p的后序前驅(qū)else return(plchild)。 //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。 哈夫曼編碼：a：0010b：10c：00000d：0001e：01f：00001g：11h：0011第七章圖（參考答案）7．1（1）鄰接矩陣中非零元素的個數(shù)的一半為無向圖的邊數(shù)；（2）A[i][j]= =0為頂點(diǎn)，I 和j無邊，否則j和j有邊相通；（3）任一頂點(diǎn)I的度是第I行非0元素的個數(shù)。7．2（1）任一頂點(diǎn)間均有通路，故是強(qiáng)連通；（2）簡單路徑 V4 V3 V1 V2。（3） 0 1 ∞ 1∞ 0 1 ∞1 ∞ 0 ∞∞ ∞ 1 0鄰接矩陣V1V4 ||\V2 | ^|\V2V3 |^|\V1 | ^|\V3V4V3 |^|\鄰接表V1V3 |^|\V2V1 |^|\V2 | ^|\V4 | ^|\V3V4V1 |^|\逆鄰接表7．3（1）鄰接表V14 |2 | ^6 |5 |3 |V21 | ^6 |V31 | ^4 |5 |V41 | ^6 |3 |5 |V55 | ^4 |1 |3 |V61 | ^2 |4 |5 |（2）從頂點(diǎn)4開始的DFS序列：V5,V3,V4,V6,V2,V1（3）從頂點(diǎn)4開始的BFS序列：V4,V5,V3,V6,V1,V27．4（1）① adjlisttp g。 vtxptr i,j。 //全程變量② void dfs(vtxptr x)//從頂點(diǎn)x開始深度優(yōu)先遍歷圖g。在遍歷中若發(fā)現(xiàn)頂點(diǎn)j，則說明頂點(diǎn)i和j間有路徑。{ visited[x]=1。 //置訪問標(biāo)記 if (y= =j){ found=1。exit(0)。}//有通路，退出else { p=g[x].firstarc。//找x的第一鄰接點(diǎn) while (p!=null) { k=padjvex。 if （!visited[k]）dfs(k)。 p=pnextarc。//下一鄰接點(diǎn) }}③ void connect_DFS (adjlisttp g) //基于圖的深度優(yōu)先遍歷策略，本算法判斷一鄰接表為存儲結(jié)構(gòu)的圖g種，是否存在頂點(diǎn)i//到頂點(diǎn)j的路徑。設(shè) 1=i ,j=n,ij. { visited[1..n]=0。found=0。 scanf (amp。i,amp。j)。 dfs (i)。 if (found) printf （” 頂點(diǎn)”,i,”和頂點(diǎn) ”,j,”有路徑 ”）；else printf （” 頂點(diǎn)”,i,”和頂點(diǎn) ”,j,”無路徑 ”）；}// void connect_DFS(2)寬度優(yōu)先遍歷全程變量，調(diào)用函數(shù)與（1）相同，下面僅寫寬度優(yōu)先遍歷部分。void bfs(vtxptr x)//{ initqueue(q)。enqueue(q,x)。 while (!empty(q))。{ y=delqueue(q)。 if (y= =j) 　{ found=1。exit(0)。}//有通路，退出 else {p=g[x].firstarc。//第一鄰接點(diǎn) while (p!=null) {k=padjvex。 if (! Visted[k]) enqueue(q,k)。 p=pnextarc }}// if(y= =j) }//while(!empty(q))7．5。假定該有向圖以鄰接表存儲，各頂點(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)相同的簡單路徑。算法基本思想是利用圖的遍歷，以頂點(diǎn)VK開始，若遍歷中再通到VK，則存在簡單回路，否則不存在簡單回路。Adjlisttp g 。 visited[1..n]=0。Int found =0。//全程變量Int dfs(btxptr x)//從k頂點(diǎn)深度優(yōu)先遍歷圖g，看是否存在k的簡單回路{ visited[x]=1。 p=g[x].firstarc。 while(p!=null) { w=padjvex。 if(w= =k) { found=1。exit(0)。}//有簡單回路，退出 if (!visited[k] ) dfs(w )。 p=pnextarc。}//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時無優(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.用鄰接表存儲結(jié)構(gòu)，鄰接點(diǎn)逆序即編號大的排在前面。入度為0頂點(diǎn)用棧結(jié)構(gòu)存儲，初始時從頂點(diǎn)1到頂點(diǎn)N掃描，入度為0的頂點(diǎn)進(jìn)棧，得V5在棧頂。7．11 void toposort_dfs （graph g；vtptr v） //從頂點(diǎn)v開始，利用深度優(yōu)先遍歷對圖g進(jìn)行拓?fù)渑判颉?/基本思想是利用棧s存放頂點(diǎn)，首先出棧的頂點(diǎn)是出度為0的頂點(diǎn)，是拓?fù)湫蛄兄凶詈笠粋€頂//點(diǎn)。若出棧元素個數(shù)等于頂點(diǎn)數(shù)，則拓?fù)渑判虺晒Γ敵龅氖悄嫱負(fù)渑判蛐蛄?。{ visited[1..n]=0。top=0。num=0。//初始化；top為棧頂指針，num記出棧元素數(shù) s[++top]=v。//頂點(diǎn)入棧 while (top!=0) {w=firstadj(g,v)。//求頂點(diǎn)v的第一鄰接點(diǎn) while (w！=0) // w!=0的含義是w存在 { if ( !visited[w]) s[++top]=w。 w=nextadj(g,v,w)。//求下一個鄰接點(diǎn) } if (top!=0) {v=s[top]。 num++。 printf(v)。}//輸出頂點(diǎn) }printf(“\n”)。if (numn) printf(“ 從”,”v”,”頂點(diǎn)開始拓?fù)渑判虿荒茼樌瓿?”)； else printf(“拓?fù)渑判虺晒?，輸出的是一個逆拓?fù)湫蛄?\n”)。} V2 V4 V6 a2=3 a9=4 a12=4 a1=5 a7=5 a11=5 V9 V10 V1 a4=6 V7 a14=2 a3=6 a13=2 a5=3 a10=4 V3 V5 V8頂點(diǎn) Ve Vl活動 e l leV1 0 0V2 5 9V3 6 6V4 12 12V5 15 16V6 16 20V7 17 17V8 19 20V9 22 22V10 24 24a1 0 0 0a2 5 9 4a3 0 0 0a4 6 6 0a5 6 13 7a6 12 13 1a7 12 12 4a8 15 16 0a9 12 16 4a10 15 16 1a11 17 17 0a12 16 20 4a13 19 20 1a14 22 22 0關(guān)鍵路徑 V1V3V4V7V9V10 長 22關(guān)鍵活動 a3,a4,a7,a11,a14頂點(diǎn) Ve Vl活動