城通信網(wǎng)絡(luò)建設(shè)系統(tǒng)方案

1、專業(yè)資料數(shù)據(jù)結(jié)構(gòu)課程設(shè)計題目：城市通信網(wǎng)絡(luò)建設(shè)系統(tǒng)班級:*姓名:*指導(dǎo)教師:AAAAAAAAA完成日期：2015年6月13日word完美格式專業(yè)資料1 .需求分析1.1 問題描述通信設(shè)施的安全保障是安全生產(chǎn)管理工作的一項重要內(nèi)容。隨著通信網(wǎng)絡(luò)的不斷擴大和各種先進的通信方式日益增多相應(yīng)的通信設(shè)施也在快速擴展，在不同的環(huán)境、不同的地域受到各種客觀條件的影響和破壞(包括自然因素和人為因素)以及通信設(shè)施在使用過程中的老化都會對全程全網(wǎng)的通信質(zhì)量造成不同程度的影響。因此，采用通信設(shè)施安全保障計算機管理系統(tǒng)實現(xiàn)全區(qū)通信設(shè)施的集中管理，對保障通信設(shè)施安全，提高維護工作效率，及時發(fā)現(xiàn)與處理隱患問題，增強抵抗災(zāi)

2、害能力，特別是在實現(xiàn)管理工作的系統(tǒng)化、正規(guī)化、規(guī)范化方面是非常必要的。如何在最小的經(jīng)濟條件下達到利益最大化，是所有公司、企業(yè)已經(jīng)政府部門一直所探討和解決的問題。對于城市通信管理系統(tǒng)來說，若要在n個城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條通信線路即可，建立最小生成樹即能實現(xiàn)以最低的經(jīng)濟代價建設(shè)這個通信網(wǎng)。1.2 基本任務(wù)通過用戶調(diào)查分析及實際需求，系統(tǒng)需要實現(xiàn)如下基本任務(wù)：(1)在紙上模擬設(shè)計n個城市的網(wǎng)絡(luò)平面圖，城市數(shù)不少于20個，相同的的城市數(shù)不少于2(n-1),頂點表示各城市，邊表示城市間的距離；(2)編寫算法，求解最小代價通信網(wǎng)絡(luò)；(3)輸出該通信網(wǎng)絡(luò)中各邊及其權(quán)值；n個城市間的線路連接

3、屬于圖的結(jié)構(gòu)，要構(gòu)建最經(jīng)濟的通信網(wǎng)絡(luò)，即是構(gòu)建圖的生成樹。把城市間的線路關(guān)系看成是圖。城市間的距離即是圖的權(quán)值。利用prim算法或kruskal算法即可求出最小生成樹。2 .概要設(shè)計為了完成需求分析的基本任務(wù)，主要從以下3個方面進行設(shè)計：2.1 主界面設(shè)計為了使程序界面更加友好，建立了interface函數(shù)和choice函數(shù)，即歡迎界面以及實現(xiàn)用戶可以按數(shù)字鍵選擇相應(yīng)的功能。歡迎界面如下圖:CAUwrc;while(c)switch(c)case 1:word完美格式專業(yè)資料歡迎使用*);Welcom_to_Use);system(cls);system(color1b);printf(n);

4、printf(ntt*printf(nprintf(n*);printf(n);printf(n);printf(n);G=SaveGraph(G);system(cls);interface();/system(PAUSE);std:cinc;continue;case 2:system(cls);system(color1c);printf(n);printf(ntt*歡迎使用*);printf(nWelcom_to_Use);printf(n*);printf(n);printf(ttt下面顯示的是通信網(wǎng)絡(luò)的基本信息n);printf(n);G=SaveGraph(G);G=print(

5、G);printf(nttt按任意鍵返回n);c=getchar();c=getchar();system(cls);interface();/system(PAUSE);std:cinc;continue;case 3:system(cls);word完美格式專業(yè)資料system(color1e);printf(n);printf(ntt*printf(n歡迎使用*);Welcom_to_Use);printf(n*);printf(n);printf(n);printf(n);G=SaveGraph(G);prim(G,G.vexs0);*printf(tt*結(jié)果存入KruskalResu

6、lt.dat中，按任意鍵返回*n);c=getchar();c=getchar();system(cls);interface();system(PAUSE);std:cinc;continue;case4:system(cls);system(color1d);printf(n);printf(ntt*printf(n歡迎使用*);Welcom_to_Use);printf(n*);printf(n);printf(n);printf(n);G=SaveGraph(G);G=kruskal(G);printf(tt*結(jié)果存入PrimResult.dat中，按任意鍵返回*n);c=getcha

7、r();c=getchar();system(cls);interface();system(PAUSE);std:cinc;word完美格式專業(yè)資料continue;case5:return;)3.模塊設(shè)計3.1 模塊設(shè)計系統(tǒng)主要包含主程序模塊和其它操作模塊。其調(diào)用關(guān)系如下圖所示。(l)CreateGraph(G);/創(chuàng)建圖模塊(2)SaveGraph(G);/存儲圖模塊(3)Print(G);/輸出圖模塊(4)Kruskal(G);/kruskal算法求最小生成樹模塊Kruskal算法的基本思想是：1 、若網(wǎng)絡(luò)G的邊數(shù)en1,則G即為所求的最小生成樹，否則，一定有en-1.2 、將網(wǎng)絡(luò)的e

8、條邊按權(quán)值自小到大順序排列。3 、將網(wǎng)絡(luò)G中的邊都去掉，只留下n個孤立頂點作為初始的最小生成樹T,再按邊的排放順序逐個考察，若與當前E(T)中的邊不構(gòu)成圈，便將它加入到邊集E(T),直至E(T)中邊數(shù)滿n-1為止。(5)Prim(G);/prim算法求最小生成樹模塊Prim算法是另一種求最小生成樹的方法，它的基本思想是按權(quán)值局部最小逐次將頂點和邊加入到T中，直至V(T)，黃n個頂點為止。Prim算法步驟為：1、設(shè)最小生成樹T的V(T)和E(T)均為空。2、從頂點集V(G)中任取一頂點加到頂點集V(T)中。3、在與V(T)中各頂點相關(guān)的所有邊中，取一條權(quán)值最小的邊(Vi,Vj)，其中，Vi包含于

9、V(T),Vj包含于V(T)。4、(Vi,Vj)加入到E(T)中，將頂點Vj加入到V(T)中。5、若V(T)已滿n個頂點，則算法終止，否則轉(zhuǎn)步驟(3)。3.3系統(tǒng)模塊之間的調(diào)用關(guān)系系統(tǒng)的5個子模塊之間的主要調(diào)用關(guān)系如下圖所示：word完美格式專業(yè)資料系統(tǒng)采用鄰接矩陣存儲信息，定義如下：/圖的數(shù)據(jù)結(jié)構(gòu)typedefstructMGraph/建立圖MGraph()memset(vexs,0,MAX_VERTEX_NUM);VertexvexsMAX_VERTEX_NUM;/城市名稱intAdjMatrixarcs;/intvexnum;/intarcnum;/網(wǎng)絡(luò)條數(shù)圖的當前頂點數(shù)（城市總數(shù)）圖的

10、當前弧數(shù)（網(wǎng)絡(luò)總數(shù)）MGraph;/記錄從頂點集U到V-U的代價最小的邊的輔助數(shù)組定義typedefstructTemp/Temp()lowcost=0;Vertexadjvex;/輔助數(shù)組當前點word完美格式專業(yè)資料intlowcost;/權(quán)值closedgeMAX_VERTEX_NUM;typedefstructCityNumberCityNumber()memset(cityNam,0,1024);charcityNam1024;CityNum;CityNum*Hometown=newCityNum20;/若G中存在頂點u,則返回該頂點在圖中位置；否則返回-1。#includeintL

11、ocateVex(MGraphG,Vertexu)inti;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;4.2系統(tǒng)主要模塊設(shè)計4.2.1 CreateGraph函數(shù)1)創(chuàng)建鄰接矩陣以存儲圖的內(nèi)容。4.2.2 )填充矩陣，即輸入城市間網(wǎng)絡(luò)的狀況，以方便使用prim算法或kruskal算法求出最經(jīng)濟的架設(shè)方法。程序如下：/采用數(shù)組(鄰接矩陣)表示法，構(gòu)造無向網(wǎng)GoMGraphCreateGraph(MGraph&G)inti=0,j=0,k=0,w=0;Vertexva,vb;/路徑的兩個節(jié)點printf(nntt*建立

12、城市間網(wǎng)絡(luò)信息*);printf(請輸入城市的總數(shù)：n);scanf(%d,&G.vexnum);printf(請輸入城市間的網(wǎng)絡(luò)數(shù)：n);scanf(%d,&G.arcnum);printf(請輸入d個城市的名稱(%d個字符):n,G.vexnum);for(i=0;iG.vexnum;+i)/構(gòu)造頂點向量scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i)/初始化鄰接矩陣for(j=0;jG.vexnum;+j)G.arcsij=65535;/65535為無窮大printf(請輸入d條網(wǎng)絡(luò)的兩個城市信息城市1和城市2word完美格式專業(yè)資料的距離（以空格作為間隔）

13、:n,G.arcnum）;for(k=0;kG.arcnum;+k)/輸入城市1城市2名稱及其距離/定位權(quán)值位置對稱(scanf(%s%s%d,va,vb,&w);i=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij=G.arcsji=w;/returnG;4.2.3 SaveGraph函數(shù)1)為了避免每次都重復(fù)輸入信息，用文件存儲圖的內(nèi)容。2 )如果沒有文件則建立文件，并把圖的內(nèi)容存儲到文件中。3 )如果文件存在，則從文件中讀取圖的內(nèi)容到內(nèi)存，以便完成其他操作。程序如下：MGraphSaveGraph(MGraphG)/輸入內(nèi)容存儲在smalltree.d

14、at(inti,j;FILE*fp;fp=fopen(smalltree.dat,rt);if(fp=NULL)(G=CreateGraph(G);fp=fopen(smalltree.dat,wt);fprintf(fp,%dn,G.vexnum);/存城市樹fprintf(fp,%dn,G.arcnum);/存網(wǎng)絡(luò)數(shù)for(i=0;iG.vexnum;+i)fprintf(fp,%stn,G.vexsi);存城市名稱for(i=0;iG.vexnum;+i)/存儲鄰接矩陣for(j=0;jG.vexnum;+j)if(G.vexsi=G.vexsj)(G.arcsij=0;/到它自己fpr

15、intf(fp,%s_%s_%dn,G.vexsi,G.vexsj,G.arcsij);else(fprintf(fp,%s_%s_%dn,G.vexsi,G.vexsj,G.arcsij);rewind(fp);word完美格式專業(yè)資料std:cout存儲成功！輸入任意鍵返回.std:endl;charc=getchar();)else/從文件中讀取網(wǎng)的信息存到內(nèi)存中(printf(tt*正在讀取文件中.*n);fscanf(fp,%dn,&G.vexnum);fscanf(fp,%dn,&G.arcnum);chartempBuffer1024;memset(tempBuffer,0,10

16、24);for(i=0;iG.vexnum;+i)(fgets(tempBuffer,1023,fp);strcpy(Hometowni.cityNam,tempBuffer);)charCityA1024;intLenth=0;memset(CityA,0,1024);for(i=0;iG.vexnum;+i)for(j=0;j=0;n-)(intintkeynum=0;switch(tempCityNamen)(case0:intkeynum=0;break;case1:intkeynum=1;break;case2:intkeynum=2;break;case3:intkeynum=3;

17、break;case4:intkeynum=4;break;case5:intkeynum=5;break;case6:intkeynum=6;break;case7:intkeynum=7;break;case8:intkeynum=8;break;case9:intkeynum=9;break;word完美格式專業(yè)資料Lenth+=intkeynum*X;X=X*10;)G.arcsij=Lenth;printf(tt*讀取成功.t*n);)fclose(fp);returnG;4.2.3 print函數(shù)Print函數(shù)完成輸出功能，將內(nèi)存中圖的內(nèi)容輸出到屏幕上程序如下：MGraphprin

18、t(MGraphG)/將輸入的網(wǎng)絡(luò)基本信息打到屏幕上inti,j;printf(城市總數(shù)：dt,G.vexnum);printf(網(wǎng)絡(luò)條數(shù)：dn,G.arcnum);printf(城市名稱：tn);for(i=0;iG.vexnum;i+)printf(%s_,G.vexsi);std:coutHometowni.cityNam;)printf(n);printf(各個城市間的距離：n);printf(n);printf(n);for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)printf(%s_%s_距離:%d公里n,G.vexsi+G.vexnum,G.v

19、exsj+G.vexnum,G.arcsij);std:cout輸入任意鍵返回.std:endl;charc=getchar();returnG;)word完美格式專業(yè)資料4.2.4 kruskal函數(shù)用kruskal算法求出最小生成樹，即最經(jīng)濟的假設(shè)方案程序如下：MGraphkruskal(MGraphG)/結(jié)果存儲在KruskalResult.dat(intsetMAX_VERTEX_NUM,i,j;intk=0,a=0,b=0,min=G.arcsab;FILE*ffp;ffp=fopen(KruskaiResult.dat,wt);for(i=0;iG.vexnum;i+)seti=i

20、;printf(最短網(wǎng)絡(luò)路徑為：n);while(kG.vexnum-1)(for(i=0;iG.vexnum;+i)/從G.arcsij中找到權(quán)值最小的for(j=i+1;jG.vexnum;+j)if(G.arcsijmin)(min=G.arcsij;/min中存最小權(quán)值a=i;b=j;if(seta!=setb)/如果a和b值不同則輸出(printf(%s-%st距離:dn,G.vexsa,G.vexsb,G.arcsab);輸出生成樹各邊f(xié)printf(ffp,%s-%sn,G.vexsa,G.vexsb);k+;for(i=0;iG.vexnum;i+)/輸出后變成相同值，下次將不

21、會輸出if(seti=setb)seti=seta;min=G.arcsab=G.arcsba=65535;輸出過的權(quán)值變?yōu)樽畲笾祌ewind(ffp);fclose(ffp);returnG;word完美格式專業(yè)資料4.2.5 prim函數(shù)用prim算法求出最小生成樹，即最經(jīng)濟的假設(shè)方案程序如下:/用普里姆算法從第u個頂點出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的各條邊voidprim(MGraphG,Vertexu)/結(jié)果存儲在PrimResult.dat中(inti,j,k=0;closedgeclose;FILE*fpp;fpp=fopen(PrimResult.dat,wt);k=Loca

22、teVex(G,u);for(j=0;jG.vexnum;+j)/輔助數(shù)組初始化(strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;初始,U=u:n);選擇其余G.vexnum-1個頂點求出T的下一個結(jié)點：第K頂點closek.lowcost=0;/printf(最短網(wǎng)絡(luò)路徑為for(i=1;iG.vexnum;+i)/(k=minimum(G,close);/printf(%s-%s)n,closek.adjvex,G.vexsk);fprintf(fpp,%s-%sn,closek.adjvex,G.vexsk);輸出生成樹的邊closek.l

23、owcost=0;/第K頂點并入U集for(j=0;jG.vexnum;+j)if(G.arcskjclosej.lowcost)/新頂點并入U集后重新選擇最小邊strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp);5.調(diào)試分析系統(tǒng)主界面運行如圖1所示。各子功能測試運行結(jié)果如下運行程序，出現(xiàn)歡迎界面，見下圖：word完美格式專業(yè)資料文F重小生成樹的應(yīng)用通信網(wǎng)蔣建遨回色rtadcByJefeionl.0請輸入您要選擇的選項ar=印回nw5.1 城市間網(wǎng)絡(luò)信息的建立C:UsersAdministr

24、ataktcjpkcsj.exeWelcon_to_Use*建立城市間網(wǎng)絡(luò)信息*請輸入城市的總數(shù):多輸入城市間的網(wǎng)絡(luò)數(shù);，輸入5個城市的名稱10個字符）：NJUXSHSZCZ核輸入6條網(wǎng)絡(luò)的兩個城市信息城市1和城市2的距離以空格作為間隔,：JUX125UXSH468SHSZ523兔CZ256tzNJ154MxSZ296word完美格式專業(yè)資料5.2顯示通信網(wǎng)絡(luò)的基本信息*用*Md*Welcon_to_UseF面顯示的是通信網(wǎng)絡(luò)的基本信息*正tt讀取文件中.一tHHHHHHHHHM*讀取成功，-網(wǎng)絡(luò)條數(shù):6CZ層-個城市間的距離;Btp-Ujrj耳一月J24fnljTs5竺433ISA555ZA

25、2550166Be-離離離離0=n-n-n_J二二DLXHzzw-s-s-c-jl-.C:UsersAdministratorDesktopkcsj.exeB-TA1Atnrl/-z/zlA8-6-Z469042B二B-OHRHB二b-iia1tKTHIZAZA.-Tl-A5-5nF-nidnF-nid3-_Z.V.Z33HR3R3R3R3645sIM-A-lMlAlA555s，/d7-z/-z216600000離離離離離離離離離離離離離離離離離離離離離離ti巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨隹sssssssssssssssssssssS音U意鍵返回word完美格式專業(yè)資料5.3查詢

26、最短網(wǎng)絡(luò)路徑6.用戶使用說明1、運行程序，出現(xiàn)歡迎界面；2、按1進入輸入系統(tǒng)，如果文件沒有存儲城市網(wǎng)絡(luò)內(nèi)容，則由用戶從鍵盤讀入，讀入后自動保存到文件中，按任意鍵即可返回歡迎界面；3、如果文件內(nèi)已經(jīng)存儲了城市網(wǎng)絡(luò)內(nèi)容，則顯示文件已保存到文件中，按任意鍵返回；4、輸入2可以在屏幕上輸出存儲在文件內(nèi)的城市間網(wǎng)絡(luò)信息，顯示完畢后按任意鍵可返回歡迎見面；5、按3和4分別可實現(xiàn)kruskal算法和prim算法求出最小生成樹，即最低經(jīng)濟代價建設(shè)通信網(wǎng)絡(luò)（距離最短的最經(jīng)濟），顯示完畢后按任意鍵返回歡迎界面；6、按5退出程序。7 .參考文獻數(shù)據(jù)結(jié)構(gòu)理論與實踐楊永斌（核心算法prim算法以及kruskal算法來源

27、于此）數(shù)據(jù)結(jié)構(gòu)（C語言）實踐教程胡元義數(shù)據(jù)結(jié)構(gòu)嚴蔚敏、吳偉民VisualC+課程設(shè)計案例精選與編程指導(dǎo)陳清華、朱紅8 .對所設(shè)計的軟件進行自我評價，如創(chuàng)新點、未解決的問題等情況說明：1、對圖的邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)有了更深刻的認識；2、對prim算法和kruskal算法亦有了更深刻的認識；3、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計方法，具備初步的獨立分析和設(shè)計能力，深入了解了模塊化的程序設(shè)計步驟；4、kruskal算法應(yīng)該用堆排序然后再找路徑，但未能實現(xiàn)；5、輸入方面如果沒有將網(wǎng)絡(luò)信息存入文件，由鍵盤輸入信息時，如果手誤輸錯了無法更word完美格式專業(yè)資料改，只能重新輸入，而且如果輸入中文，最后顯示時會出

28、現(xiàn)亂碼，只能用英文輸入；6、kruskal算法的實現(xiàn)仍有問題，結(jié)果存在錯誤，而且只能實行到第三步，到第四步時會出現(xiàn)程序關(guān)閉的提醒；9、程序源代碼：#include#include#include#defineMAX_VERTEX_NUM20最大頂點個數(shù)#defineMAX_NAME3/頂點字符串的最大長度+1typedefintintAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefcharVertexMAX_NAME;鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)/圖的數(shù)據(jù)結(jié)構(gòu)typedefstructMGraph/建立圖MGraph()memset(vexs,0,MAX_VER

29、TEX_NUM);VertexvexsMAX_VERTEX_NUM;/城市名稱intAdjMatrixarcs;/網(wǎng)絡(luò)條數(shù)intvexnum;/圖的當前頂點數(shù)(城市總數(shù))intarcnum;/圖的當前弧數(shù)(網(wǎng)絡(luò)總數(shù))MGraph;/記錄從頂點集U到V-U的代價最小的邊的輔助數(shù)組定義typedefstructTemp/輔助數(shù)組Temp()lowcost=0;Vertexadjvex;/當前點intlowcost;/權(quán)值closedgeMAX_VERTEX_NUM;typedefstructCityNumberCityNumber()memset(cityNam,0,1024);charcityN

30、am1024;CityNum;CityNum*Hometown=newCityNum20;word完美格式專業(yè)資料/若G中存在頂點u,則返回該頂點在圖中位置；否則返回-1。#includeintLocateVex(MGraphG,Vertexu)inti;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;/采用數(shù)組(鄰接矩陣)表示法，構(gòu)造無向網(wǎng)GoMGraphCreateGraph(MGraph&G)inti=0,j=0,k=0,w=0;Vertexva,vb;/路徑的兩個節(jié)點printf(nntt*建立城市間網(wǎng)絡(luò)信息*)

31、;printf(請輸入城市的總數(shù)：n);scanf(%d,&G.vexnum);printf(請輸入城市間的網(wǎng)絡(luò)數(shù)：n);scanf(%d,&G.arcnum);printf(請輸入d個城市的名稱(%d個字符):n,G.vexnum);for(i=0;iG.vexnum;+i)/構(gòu)造頂點向量scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i)/初始化鄰接矩陣for(j=0;jG.vexnum;+j)G.arcsij=65535;/65535為無窮大printf(請輸入d條網(wǎng)絡(luò)的兩個城市信息城市1和城市2的距離(以空格作為間隔):n,G.arcnum);for(k=0;

32、kG.arcnum;+k)scanf(%s%s%d,va,vb,&w);/輸入城市1城市2名稱及其距離i=LocateVex(G,va);/定位權(quán)值位置j=LocateVex(G,vb);G.arcsij=G.arcsji=w;/對稱returnG;MGraphSaveGraph(MGraphG)/輸入內(nèi)容存儲在smalltree.datinti,j;word完美格式專業(yè)資料FILE*fp;fp=fopen(smalltree.dat,rt);if(fp=NULL)(G=CreateGraph(G);fp=fopen(smalltree.dat,wt);fprintf(fp,%dn,G.vex

33、num);/存城市樹fprintf(fp,%dn,G.arcnum);存網(wǎng)絡(luò)數(shù)for(i=0;iG.vexnum;+i)fprintf(fp,%stn,G.vexsi);/存城市名稱for(i=0;iG.vexnum;+i)/存儲鄰接矩陣for(j=0;jG.vexnum;+j)if(G.vexsi=G.vexsj)(G.arcsij=0;/到它自己G.arcsij);G.arcsij);fprintf(fp,%s_%s_%dn,G.vexsi,G.vexsj,else(fprintf(fp,%s_%s_%dn,G.vexsi,G.vexsj,rewind(fp);std:cout存儲成功！。

34、輸入任意鍵返回.std:endl;charc=getchar();else/從文件中讀取網(wǎng)的信息存到內(nèi)存中printf(tt*正在讀取文件中*n);fscanf(fp,%dn,&G.vexnum);fscanf(fp,%dn,&G.arcnum);chartempBuffer1024;memset(tempBuffer,0,1024);for(i=0;iG.vexnum;+i)(fgets(tempBuffer,1023,fp);strcpy(Hometowni.cityNam,tempBuffer);charCityA1024;intLenth=0;memset(CityA,0,1024);

35、for(i=0;iG.vexnum;+i)for(j=0;j=0;n-)intintkeynum=0;switch(tempCityNamen)case0:intkeynum=0;break;case1:intkeynum=1;break;case2:intkeynum=2;word完美格式專業(yè)資料break;case3:intkeynum=3;break;case4:intkeynum=4;break;case5:intkeynum=5;break;case6:intkeynum=6;break;case7:intkeynum=7;break;case8:intkeynum=8;break;

36、case9:intkeynum=9;break;Lenth+=intkeynum*X;X=X*10;G.arcsij=Lenth;printf(tt*讀取成功t*n);fclose(fp);returnG;將輸入的網(wǎng)絡(luò)基本信息打到屏幕上MGraphprint(MGraphG)/inti,j;printf(城市總數(shù):%dt,G.vexnum);printf(網(wǎng)絡(luò)條數(shù):%dn,G.arcnum);printf(城市名稱:tn);for(i=0;iG.vexnum;i+)printf(%s_,G.vexsi);std:coutHometowni.cityNam;word完美格式專業(yè)資料printf(

37、n);printf(各個城市間的距離:n);printf(n);printf(n);for(i=0;iG.vexnum;+i)for(j=0;jG.vexnum;+j)printf(%s_%s_距離：d公里n,G.vexsi+G.vexnum,G.vexsj+G.vexnum,G.arcsij);std:cout輸入任意鍵返回.std:endl;charc=getchar();returnG;MGraphkruskal(MGraphG)/結(jié)果存儲在KruskalResult.datintsetMAX_VERTEX_NUM,i,j;intk=0,a=0,b=0,min=G.arcsab;FILE

38、*ffp;ffp=fopen(KruskaiResult.dat,wt);for(i=0;iG.vexnum;i+)seti=i;printf(最短網(wǎng)絡(luò)路徑為:n);while(kG.vexnum-1)for(i=0;iG.vexnum;+i)/從G.arcsij中找到權(quán)值最小的for(j=i+1;jG.vexnum;+j)if(G.arcsijmin)min=G.arcsij;/min中存最小權(quán)值a=i;b=j;if(seta!=setb)/如果a和b值不同則輸出printf(%s-%st距離:dn,G.vexsa,G.vexsb,G.arcsab);輸出生成樹各邊f(xié)printf(ffp,%s-%sn,G.vexsa,G.vexsb);k+;for(i=0;iG.vexnum;i+)/輸出后變成相同值，下次將不會輸出if(seti=setb)seti=seta;word完美格式專業(yè)資料min=G.arcsab=G.arcsba=65535;/輸出過的權(quán)值變?yōu)樽畲笾?rewind(ffp);fclose(ffp);returnG;)/求closedge結(jié)構(gòu)體中l(wèi)owcost的最小正值intminimum(MGraphG,closedgeclose)inti=0,j,k,min;while(!closei.