【正文】 R={VR} VR={（ v， w） | v , w∈ V, (v , w)表示 v 和 w 之間存在路徑 } 基本操作 P： CreatGraph(amp。G, V, VR) 初始條件： V 是圖的頂點(diǎn)集， VR 是圖中邊的集合。 操作結(jié)果： 按定義 (V, VR) 構(gòu)造圖 G。 Show(amp。G) 初始條件：圖 G 已存在。 操作結(jié)果：顯示圖 G 中的所有路徑關(guān)系。 } 算法分析 1. 定義結(jié)構(gòu)體 Algraph：定義一個(gè)既簡單又符合題目設(shè)計(jì)要求的結(jié)構(gòu) 體 ，采用鄰接矩陣來作為圖的 存儲(chǔ) 結(jié)構(gòu) ； 2. 構(gòu)建圖 的結(jié)構(gòu)（ creatgraph 函數(shù) ） ：首先 , 建立 文本 文件， 利用程序 打開文件，從文件中讀取圖的信息，把圖的基本信息存入鄰接矩陣中， 然后 關(guān)閉文件。借助鄰接矩陣 就 容易判斷 出 任意兩個(gè)點(diǎn)之間是否有路徑 ，并且可以存儲(chǔ) 弧 的帶權(quán)長度值 。 3. 顯示收費(fèi)站結(jié)構(gòu)的 （ show 函數(shù) ） ： 在鄰接矩陣中，判斷兩點(diǎn)之間的距離 是否 小于無窮大 ， 小于無窮大， 就說明 該兩點(diǎn)之間有路徑，便能 將收費(fèi)站的結(jié)構(gòu)輸出。 4. 求最短路徑 （ floyd 算法） ：定義兩個(gè)數(shù)組 length 和 path， path 用來存儲(chǔ)路徑， length用來保存兩點(diǎn)之間的最短 路徑。求兩點(diǎn)之間的最短路徑，首先要判斷這兩點(diǎn)是否有路徑可走，如果有，但那不一定是最短的路徑，需要進(jìn)行 n 次試探。若（ vi， ? ， vk）和（ vk， ? ， vj）分別是從 vi 到 vk 和從 vk 到 vj的中間頂點(diǎn)的序號(hào)不大于 k1 的最短路徑，則將（ vi， ? ，vk,? ,vj）和已經(jīng)得到的從 vi 到 vj 且中間頂點(diǎn)序號(hào)不大于 k1 的最短路徑相比較，其較長度短者是從 vi 到 vj 的中間頂點(diǎn)的序號(hào)不大于 k 的最短路徑。這樣，經(jīng)過 n 次的比較后，最后求得的必是從 vi 到 vj 的最短路徑。按此方法，可以同時(shí)求得各對(duì)頂點(diǎn)之間的最短路徑。 的最短路徑 （ minist 函數(shù) ） ：在調(diào)用 floyd 算法后，函數(shù)中有 返回 length的值，只要將任意兩收費(fèi)站在數(shù)組中的下標(biāo)找到 并 帶入到 length 中就可以輸出兩收費(fèi)站之間的最短路徑。 (mmoney 函數(shù) )：調(diào)用 foyld 函數(shù)求得各收費(fèi)站之間的最短路徑，輸入車輛的類型，根據(jù)類型的不同，來計(jì)算路費(fèi)。 （ menu） ，采用分支函數(shù)，列舉出菜單，可以任意選擇程序的功能， 進(jìn) 4 入相應(yīng)的函數(shù)，得到所需要的結(jié)果 。 4 詳細(xì)設(shè)計(jì) 繪出計(jì)算機(jī)程序框圖 圖 41 程序框圖 程序的實(shí)現(xiàn) 預(yù)編命令，定義結(jié)構(gòu)體和 全局變量 /////////////////////////////////////////////////////////////////////////////// ///// 交通路費(fèi)系統(tǒng) //////////////////////////// ///// 2020年 6月 17日 //////////////////////////// ////////////////////////////////////////////////////////////////////////////// include include define M 100 typedef int Path[M][M]。 typedef struct{ char vex[M]。 //保存頂點(diǎn)信息 int n。 // 定義頂點(diǎn)數(shù) int edges[M][M]。 //保存每條邊的權(quán)值 }Algraph。 //定義圖的結(jié)構(gòu)體 /*定義全局變量 */ int path[M][M],length[M][M]。 //path 保存最短路徑的結(jié)點(diǎn)， length 是保存最短路徑距離 Algraph G。 從文件中讀入圖的結(jié)構(gòu) //////////////////////////////////////////////////////////////////// /*利用文件函數(shù)打開文本文件 ， 將收費(fèi)站的名稱先存儲(chǔ)到結(jié)構(gòu)體的數(shù)組中，關(guān)閉文本文件 ,再打開文本文件 ,將弧的信息存儲(chǔ)到結(jié)構(gòu)體的二維數(shù)組中， 構(gòu)建出 收費(fèi)站的基本 結(jié)構(gòu) */ void creatgraph(Algraph amp。G) 利用鄰接矩陣構(gòu)建圖的結(jié)構(gòu) 輸出函數(shù) （輸出圖的結(jié)構(gòu)） 用 flyod算法求最短路徑 求任意兩點(diǎn)之間的最短路徑 根據(jù)車類型來計(jì)算路費(fèi) 輸出任意兩 點(diǎn)之間最短路徑 所經(jīng)過的路徑 5 { int i,m,n,k。 FILE *fp1,*fp2。 /*定義文件名 */ fp1 = fopen(,r)。 /*39。r39。為讀取文件 */ if(fp1 == NULL){ /*打開文件并判斷文件是否存在 */ printf(File open error!\n)。 exit(0)。 } i = 1。 = 0。 while(!feof(fp1)){ /*從文件中讀取信息并存入數(shù)組中 */ ++。 fscanf(fp1,%c,amp。[i])。 i++。 } 。 if(fclose(fp1)) { /*關(guān)閉文件 */ printf(Can not close the file!\n)。 exit(0)。 } for(int h = 1。h=。h++) for(int j = 1。j=。j++) [h][j] = 10000。 /*給每條邊附帶權(quán)長度初值 */ fp2=fopen(,r)。 if(fp2==NULL) { printf(File open error!\n)。 exit(0)。 } while(!feof(fp2)) { fscanf(fp2,%d%d%d,amp。m,amp。n,amp。k)。 /*從文件中讀取邊的權(quán)值并存入二維數(shù) */ [m][n] = k。 [n][m]=k。 } if(fclose(fp1)) { printf(Can not close the file!\n)。 /*關(guān)閉文件 */ exit(0)。 } } 顯示出收費(fèi)站的結(jié)構(gòu) /////////////////////////////////////////////////////////////////////////////// 6 /*利用函數(shù)輸出構(gòu)建的圖的存儲(chǔ)結(jié)構(gòu)顯示出每個(gè)站點(diǎn)的距離 */ void show(Algraph G) { int i,j。 creatgraph(G)。 printf(請(qǐng)輸出收費(fèi)站的結(jié)構(gòu)： \n)。 for(i=1。i=。i++) for(j=1。j=。j++) if([i][j]!=10000amp。amp。i!=j) printf( %c%c %d\n,[i],[j],[i][j])。 } 弗洛伊德算法 //////////////////////////////////////////////////////////////////// /*首先將收費(fèi)站之間的路徑存儲(chǔ)到 length 中，然后將有路徑的收費(fèi)站名稱的下標(biāo)存儲(chǔ)到 path中，再用三重循環(huán) 往中間加點(diǎn)， 分別將 每兩 收費(fèi)站之間的最短路徑存儲(chǔ)到 length 中 */ void shortpath(Algraph amp。G,Path path,Path length) { int i,j,k。 for(i = 1。i=。i++) for(j = 1。j=。j++) { if(i==j) [i][j]=0。 length[i][j] = [i][j]。 if(i==j) path[i][j] = 1。 else if(length[i][j]10000) path[i][j] = i。 //保存每條邊的弧頭 else path[i][j] = 1。 } for(k=1。k=。k++) for(i=1。i=。i++) for(j=1。j=。j++) if(length[i][k]+length[k][j]length[i][j]) /*判斷兩點(diǎn)之間最短距離 */ { length[i][j]=length[i][k]+length[k][j]。 path[i][j]=path[k][j]。 } } 求 最短路徑的長度 /////////////////////////////////////////////////////////////////////////////// 7 /*先調(diào)用 弗洛伊德算法， 算法中有返回 length 的值，輸入兩個(gè)收費(fèi)站的名稱， 即可求出兩收費(fèi)站之間的 最短路徑長度 */ void minist(Algraph amp。G) { int i,j。 char ch1,ch2。 creatgraph(G)。 int path[M][M],length[M][M]。 shortpath(G,path,length)。 //調(diào)用函數(shù)求得各點(diǎn)之間的最短路徑 printf(請(qǐng)輸入兩個(gè)收費(fèi)站的名稱 :\n)。 getchar()。 scanf(%c%c,amp。ch1,amp。ch2)。 for(i=0。i。i++){ if([i]==ch1) //在數(shù)組中查找所輸 入的值 break。 } for(j=0。j。j++){ if([j]==ch2) break。 } printf(收費(fèi)站 %c 到收費(fèi)站 %c 的最短路徑長度為： \n,ch1,ch2)。 printf(%d 公里 ,length[i][j])。 return。 } 判斷車型函數(shù) /////////////////////////////////////////////////////////////////////////////// /*利用 分 支語句 判斷車輛類型，不同類型的車收費(fèi)不同 ，并計(jì)算路費(fèi) */ void Shape(int amp。money,Path length,int i,int j) { char shape。 printf(車輛類型 (l,m,s)分別代表大，中，小 ):\n)。 getchar()。 shape=getchar()。 switch(shape) { case 39。l39。: money=15*length[i][j]。 printf(該車為大型車輛 \n)。 break。 case 39。m39。: money=10*length[i][j]。 printf(該車為中型車輛 \n)。 break。 case 39。s39。: 8 money=5*length[i][j]。 printf(該車為小型車輛 \n)。 break。 default: break。 } } 計(jì)算路費(fèi)的函數(shù) /////////////////////////////////////////////////////////////////////////////// /*先 調(diào)用弗洛伊德函數(shù) ，輸入兩個(gè)收費(fèi)站名稱并 判斷車型 ，依據(jù)車型的大小 來實(shí)現(xiàn)收費(fèi)的計(jì)算 ，并輸出 計(jì)算的結(jié)果 和所經(jīng)過的路徑 */ void mmoney(Algraph amp。G) { int i,j,money。 char ch1,ch2。 creatgraph(G)。 int path[M][M],length[M][M]。 printf(大型車輛每公里收費(fèi)為 15 元 /每公里 \n)。 printf(中型車輛每公里收費(fèi)為 10 元 /每公里 \n)。 printf(小型車輛每公里收費(fèi)為 5 元 /每公里 \n)。