【文章內(nèi)容簡介】 break。 case 39。139。: intkeynum = 1。 break。 case 39。239。: intkeynum = 2。 break。 case 39。339。: intkeynum = 3。 break。 case 39。439。: intkeynum = 4。 break。 case 39。539。: intkeynum = 5。 break。 case 39。639。: intkeynum = 6。 break。 case 39。739。: intkeynum = 7。 break。 case 39。839。: intkeynum = 8。 break。 case 39。939。: intkeynum = 9。 break。 } Lenth += intkeynum*X。 X = X*10。 } [i][j] = Lenth。 } printf(\t\t*******讀取成功...\t***********\n)。 } fclose(fp)。 return G。} print函數(shù) Print函數(shù)完成輸出功能，將內(nèi)存中圖的內(nèi)容輸出到屏幕上程序如下：MGraph print(MGraph G)//將輸入的網(wǎng)絡(luò)基本信息打到屏幕上{ int i,j。 printf(城市總數(shù):%d\t, )。 printf(網(wǎng)絡(luò)條數(shù):%d\n, )。 printf(城市名稱:\t\n)。 for(i=0。 i。 i++) { //printf(%s_,[i])。 std::coutHometown[i].cityNam。 } printf(\n)。 printf(各個城市間的距離:\n)。 printf(\n)。 printf(\n)。 for(i=0。i。++i) for(j=0。j。++j) printf(%s__%s_距離:%d公里\n,[i+],[j+],[i][j])。 std::cout輸入任意鍵返回.std::endl。 char c = getchar()。 return G。} kruskal函數(shù) 用kruskal算法求出最小生成樹，即最經(jīng)濟的假設(shè)方案程序如下：MGraph kruskal(MGraph G) //{ int set[MAX_VERTEX_NUM],i,j。 int k=0,a=0,b=0,min=[a][b]。 FILE*ffp。 ffp=fopen(,wt)。 for(i=0。i。i++) set[i]=i。 printf(最短網(wǎng)絡(luò)路徑為:\n)。 while(k) { for(i=0。i。++i) //[i][j]中找到權(quán)值最小的 for(j=i+1。j。++j) if([i][j]min) { min=[i][j]。//min中存最小權(quán)值 a=i。 b=j。 } if(set[a]!=set[b]) //如果a和b值不同則輸出 { printf(%s%s\t距離:%d\n,[a],[b],[a][b])。//輸出生成樹各邊 fprintf(ffp,%s%s\n,[a],[b])。 k++。 for(i=0。i。i++) //輸出后變成相同值，下次將不會輸出 if(set[i]==set[b]) set[i]=set[a]。 } min=[a][b]=[b][a]=65535。 //輸出過的權(quán)值變?yōu)樽畲笾?} rewind(ffp)。 fclose(ffp)。 return G。} prim函數(shù) 用prim算法求出最小生成樹，即最經(jīng)濟的假設(shè)方案程序如下：// 用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊void prim(MGraph G,Vertex u) //{ int i,j,k=0。 closedge close。 FILE*fpp。 fpp=fopen(,wt)。 k=LocateVex(G,u)。 for(j=0。j。++j) // 輔助數(shù)組初始化 { strcpy(close[j].adjvex,u)。 close[j].lowcost=[k][j]。 } close[k].lowcost=0。 // 初始,U={u} printf(最短網(wǎng)絡(luò)路徑為:\n)。 for(i=1。i。++i) // { k=minimum(G,close)。 // 求出T的下一個結(jié)點：第K頂點 printf((%s%s)\n,close[k].adjvex,[k])。 fprintf(fpp,%s%s\n,close[k].adjvex,[k])。 // 輸出生成樹的邊 close[k].lowcost=0。 // 第K頂點并入U集 for(j=0。j。++j) if([k][j]close[j].lowcost) // 新頂點并入U集后重新選擇最小邊 { strcpy(close[j].adjvex,[k])。 close[j].lowcost=[k][j]。 } } rewind(fpp)。 fclose(fpp)。}5．調(diào)試分析系統(tǒng)主界面運行如圖1所示。各子功能測試運行結(jié)果如下:運行程序，出現(xiàn)歡迎界面，見下圖： 城市間網(wǎng)絡(luò)信息的建立 查詢最短網(wǎng)絡(luò)路徑 6．用戶使用說明 運行程序，出現(xiàn)歡迎界面； 按1進入輸入系統(tǒng)，如果文件沒有存儲城市網(wǎng)絡(luò)內(nèi)容，則由用戶從鍵盤讀入，讀入后自動保存到文件中，按任意鍵即可返回歡迎界面； 如果文件內(nèi)已經(jīng)存儲了城市網(wǎng)絡(luò)內(nèi)容，則顯示文件已保存到文件中，按任意鍵返回； 輸入2可以在屏幕上輸出存儲在文件內(nèi)的城市間網(wǎng)絡(luò)信息，顯示完畢后按任意鍵可返 回歡迎見面； 按3和4分別可實現(xiàn)kruskal算法和prim算法求出最小生成樹，即最低經(jīng)濟代價建設(shè)通信網(wǎng)絡(luò)（距離最短的最經(jīng)濟），顯示完畢后按任意鍵返回歡迎界面； 按5退出程序。7．參考文獻 《數(shù)據(jù)結(jié)構(gòu)理論與實踐》 楊永斌 （核心算法prim算法以及kruskal算法來源于此） 《數(shù)據(jù)結(jié)構(gòu)（C語言）實踐教程》 胡元義 《數(shù)據(jù)結(jié)構(gòu)》 嚴蔚敏、吳偉民 《Visual C++課程設(shè)計案例精選與編程指導》 陳清華、朱紅8． 對所設(shè)計的軟件進行自我評價，如創(chuàng)新點、未解決的問題等情況說明： 對圖的邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)有了更深刻的認識； 對prim算法和kruskal算法亦有了更深刻的認識； 了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力，深入了解了模塊化的程序設(shè)計步驟； kruskal算法應(yīng)該用堆排序然后再找路徑，但未能實現(xiàn)； 輸入方面如果沒有將網(wǎng)絡(luò)信息存入文件，由鍵盤輸入信息時，如果手誤輸錯了無法更改，只能重新輸入，而且如果輸入中文，最后顯示時會出現(xiàn)亂碼，只能用英文輸入； kruskal算法的實現(xiàn)仍有問題，結(jié)果存在錯誤，而且只能實行到第三步，到第四步時會出現(xiàn)程序關(guān)閉的提醒；程序源代碼： includeincludeinclude iostreamdefine MAX_VERTEX_NUM 20// 最大頂點個數(shù)define MAX_NAME 3 // 頂點字符串的最大長度+1 typedef int intAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]。typedef char Vertex[MAX_NAME]。// 鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)// 圖的數(shù)據(jù)結(jié)構(gòu)typedef struct MGraph //建立圖{ MGraph() { memset(vexs, 0, MAX_VERTEX_NUM)。 } Vertex vexs[MAX_VERTEX_NUM]。// 城市名稱 intAdjMatrix arcs。// 網(wǎng)絡(luò)條數(shù) int vexnum。 // 圖的當前頂點數(shù)(城市總數(shù)) int arum。 // 圖的當前弧數(shù)(網(wǎng)絡(luò)總數(shù))} MGraph。// 記錄從頂點集U到VU的代價最小的邊的輔助數(shù)組定義typedef struct Temp //輔助數(shù)組{ Temp() { lowcost = 0。 } Vertex adjvex。 //當前點 int lowcost。 //權(quán)值}closedge[MAX_VERTEX_NUM]。typedef struct CityNumber{ CityNumber() { memset(cityNam, 0, 1024)。 } char cityNam[1024]。}CityNum。CityNum* Hometown = new CityNum[20]。// 若G中存在頂點u,則返回該頂點在圖中位置。否則返