【正文】 參考文獻(xiàn) 1 譚浩強(qiáng)主編， C程序設(shè)計(jì)題解與上機(jī)指導(dǎo)（第 3版），清華大學(xué)出版社， . 2 [美 ]Harvey M. Deitel, Paul J. Deitel 著，聶雪軍，賀軍譯， C 程序設(shè)計(jì)經(jīng)典教程 (第 4版 )，清華大學(xué)出版社， 3 李春葆，張植民，肖忠付編， C語(yǔ)言程序設(shè)計(jì)題典，清華大學(xué)出版社， 4 [美 ]科漢 /著，張小潘譯， C 語(yǔ)言編程（第 3版），電子工業(yè)出版社， 5 [美 ]Brian W. Kernighan, Dennis M. Ritchie 著，徐寶文，李志譯， C 程序設(shè)計(jì)語(yǔ)言 (第 2版在選用存儲(chǔ)方法是，要盡量選用時(shí)間復(fù)雜度較小的方法，這樣能夠節(jié)省程序執(zhí)行時(shí)間，提高查詢效率。比較這兩種算法的復(fù)雜度，盡量選用復(fù)雜度小。當(dāng)然在課程設(shè)計(jì)期間，也遇到了大大小小的一些問(wèn)題，使我看到了自己的不足之處，讓我認(rèn)識(shí)到在以后的學(xué)習(xí)中要善于發(fā)現(xiàn)自己的不足，找出自己的薄弱環(huán)節(jié)，以便能夠更好 的去鞏固所學(xué)的。 系統(tǒng)運(yùn)行主界面如圖 1所示。本功能由遞歸 函數(shù)實(shí)現(xiàn)，所以當(dāng)圖中的邊數(shù)過(guò)多時(shí)，可能造成死循環(huán)而得不到正確結(jié)果。 //將找到的路徑上頂點(diǎn)的訪問(wèn)標(biāo)志重新設(shè)置為 0，以用于試探新的路徑 } s++。 //存儲(chǔ)頂點(diǎn)編號(hào) s 至 d[k+1]中 path(c,m,n,t)。 (visited[s]==0)) //初態(tài)：頂點(diǎn) m到頂點(diǎn) s有邊，且未被訪問(wèn) { visited[s]=1。 while(s) //從第 m個(gè)頂點(diǎn)，試探至所有頂點(diǎn)是否有路徑 { if(([d[k]][s].adjInfinity) amp。 s=0 時(shí)為起點(diǎn) m printf(%s\n\n,[d[s]].name)。s++) printf(%s,[d[s]].name)。 若 d[k]是終點(diǎn) n且景點(diǎn)個(gè)數(shù) =8，則輸出該路徑 { for(s=0。amp。 //d[ ]數(shù)組存儲(chǔ)由 m出發(fā)到景點(diǎn) n的路徑上的頂點(diǎn)編號(hào)， visited[ ]數(shù)組用于存放頂點(diǎn)是否被訪問(wèn)的標(biāo)志 int s, x=0, t=k+1。若頂點(diǎn) s是由 m出發(fā)到景點(diǎn) n的路徑上的頂點(diǎn)，則調(diào)用自身，求由 s 出發(fā)的所 //有可能到達(dá)頂點(diǎn) n 的路徑。 //找到，返回頂點(diǎn)序號(hào) i return 1。i 。 }//browsepus 查找景點(diǎn)在圖中的序號(hào) int locatevex(mgraph c,int v) { int i。i++) printf(%10d%25s%80s\n,[i].position,[i].name,[i].introduction)。 for(i=0。 printf( \n\n編號(hào) 景點(diǎn)名稱 簡(jiǎn)介 \n)。 printf(\n\n介 紹： %80s\n\n,[k].introduction )。 } printf(\n\n編號(hào)： %4d\n,[k].position )。 scanf(%d,amp。 while(k0||k) { printf(\n你所輸入的景點(diǎn)編號(hào)不存在！ )。 scanf(%d,amp。 }//shortestpath_floyd 查詢景點(diǎn)的信息 void seeabout(mgraph c) { int k。 printf(%s,[j].name )。amp。amp。u 。 } printf(%s,[k].name )。j)。 scanf(%d%d,amp。 while(k0||k||j0||j) { printf(\n你所輸入的景點(diǎn)編號(hào)不存在！ )。j)。 scanf(%d%d,amp。 p[v][w][i] = p[v][u][i] || p[u][w][i]。i 。w++) if(d[v][u]+d[u][w]d[v][w]) //從 v 經(jīng) u 到 w 的一條路徑更 短 { d[v][w]=d[v][u]+d[u][w]。v++) for(w=0。 {// 對(duì)任意頂點(diǎn) u，試探其是否為 v至 w最短路徑上的頂點(diǎn) for(v=0。u 。 // v 是 v 至 w 最短路徑上的頂點(diǎn) p[v][w][w]=1。u++) //初始化最短路徑 p[v][w][ ] 數(shù)組，第 3 分量全部清 0 p[v][w][u]=0。 //d[v][w] 中存放 v 至 w 間初始權(quán)值 for(u=0。w 。v 。 }//for }//shortestpath_dij 用弗洛伊德（ floyd）算法，求兩景點(diǎn)間的最短路徑并打印 void shortestpath_floyd(mgraph c) { // 用 floyd 算法，求各對(duì)頂點(diǎn) v 和 w 間的最短路經(jīng) p[ ][ ]及其帶權(quán)長(zhǎng)度 d[v][w] // 若 p[v][w][u]= =1；則 u是 v到 w的當(dāng)前求得的最短路經(jīng)上的頂點(diǎn) int i, j, k, v, u, w, d[35][35], p[35][35][35]。 } printf(%s,[v].name)。amp。amp。w 。v++) //輸出 v0 到其它頂點(diǎn) v 的最短路徑 { if(v!=v0) printf(%s,[v0].name)。 }//if }//for for(v=0。x++) //所有 v0 到 v 的最短路徑上的頂點(diǎn) x，都是 v0 到 w 的 p[w][x]=p[v][x]。 //修改 v0 到 w 的權(quán)值 d[w] for(x=0。amp。w 。 }//if final[v]=1。w++) //在未被訪問(wèn)的頂點(diǎn)中，查找與 v0 最近的頂點(diǎn) v if(!final[w]) if(d[w]min) // v0 到 w (有邊 )的權(quán)值 min { v=w。 for(w=0。i 。 //自 己到自己的權(quán)值設(shè)為 0 final[v0]=1。 p[v][v]=1。w++) //初始化 p[ ][ ]數(shù)組，各頂點(diǎn)間的路徑全部設(shè)置為空路徑 0 p[v][w]=0。 //v0 到各頂點(diǎn) v 的權(quán)值賦值給 d[v] for(w=0。v++) { final[v]=0。 }//while for(v=0。 scanf(%d,amp。 while(v00||v0) { printf(\n你所輸入的景點(diǎn)編號(hào)不存在 \n)。v0)。 printf(\n請(qǐng)輸入一個(gè)起始景點(diǎn)的編號(hào)： )。 int v, w, i, min, t=0, x, flag=1, v0。若 p[v][w]= =1，則 w是從 v0 到 v的最短路經(jīng)上的頂點(diǎn)。 //將找到的路徑上頂點(diǎn)的訪問(wèn)標(biāo)志重新設(shè)置為 0，以用于 試探新的路徑 } s++。 //存儲(chǔ)頂點(diǎn)編號(hào) s 至 d[k+1]中