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