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

《數(shù)據(jù)結(jié)構(gòu)》課程設(shè)計(jì)題目：城市通信網(wǎng)絡(luò)建設(shè)系統(tǒng)班級(jí)：********姓名：********學(xué)號(hào)：1111111111指導(dǎo)教師：^^^^^^^^^完成日期：2015年6月13日．需求分析1.1問(wèn)題描述通信設(shè)施的安全保障是安全生產(chǎn)管理工作的一項(xiàng)重要內(nèi)容。隨著通信網(wǎng)絡(luò)的不斷擴(kuò)大和各種先進(jìn)的通信方式日益增多相應(yīng)的通信設(shè)施也在快速擴(kuò)展,在不同的環(huán)境、不同的地域受到各種客觀(guān)條件的影響和破壞(包括自然因素和人為因素)以及通信設(shè)施在使用過(guò)程中的老化都會(huì)對(duì)全程全網(wǎng)的通信質(zhì)量造成不同程度的影響。因此,采用通信設(shè)施安全保障計(jì)算機(jī)管理系統(tǒng)實(shí)現(xiàn)全區(qū)通信設(shè)施的集中管理,對(duì)保障通信設(shè)施安全,提高維護(hù)工作效率,及時(shí)發(fā)現(xiàn)與處理隱患問(wèn)題,增強(qiáng)抵抗災(zāi)害能力,特別是在實(shí)現(xiàn)管理工作的系統(tǒng)化、正規(guī)化、規(guī)范化方面是非常必要的。如何在最小的經(jīng)濟(jì)條件下達(dá)到利益最大化，是所有公司、企業(yè)已經(jīng)政府部門(mén)一直所探討和解決的問(wèn)題。對(duì)于城市通信管理系統(tǒng)來(lái)說(shuō)，若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條通信線(xiàn)路即可，建立最小生成樹(shù)即能實(shí)現(xiàn)以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)。1.2基本任務(wù)通過(guò)用戶(hù)調(diào)查分析及實(shí)際需求，系統(tǒng)需要實(shí)現(xiàn)如下基本任務(wù)：（1）在紙上模擬設(shè)計(jì)n個(gè)城市的網(wǎng)絡(luò)平面圖，城市數(shù)不少于20個(gè)，相同的的城市數(shù)不少于2(n-1)，頂點(diǎn)表示各城市，邊表示城市間的距離；（2）編寫(xiě)算法，求解最小代價(jià)通信網(wǎng)絡(luò)；（3）輸出該通信網(wǎng)絡(luò)中各邊及其權(quán)值；n個(gè)城市間的線(xiàn)路連接屬于圖的結(jié)構(gòu)，要構(gòu)建最經(jīng)濟(jì)的通信網(wǎng)絡(luò)，即是構(gòu)建圖的生成樹(shù)。把城市間的線(xiàn)路關(guān)系看成是圖。城市間的距離即是圖的權(quán)值。利用prim算法或kruskal算法即可求出最小生成樹(shù)。2．概要設(shè)計(jì)為了完成需求分析的基本任務(wù)，主要從以下3個(gè)方面進(jìn)行設(shè)計(jì)：2.1主界面設(shè)計(jì)為了使程序界面更加友好，建立了interface函數(shù)和choice函數(shù)，即歡迎界面以及實(shí)現(xiàn)用戶(hù)可以按數(shù)字鍵選擇相應(yīng)的功能。歡迎界面如下圖： continue; case5: return; } }}3．模塊設(shè)計(jì)3.1模塊設(shè)計(jì)系統(tǒng)主要包含主程序模塊和其它操作模塊。其調(diào)用關(guān)系如下圖所示。choice函數(shù)interface函數(shù)開(kāi)始choice函數(shù)interface函數(shù)開(kāi)始3.2系統(tǒng)子模塊及其功能設(shè)計(jì)本系統(tǒng)共設(shè)計(jì)了5個(gè)子模塊，各程序的函數(shù)名及功能說(shuō)明如下：CreateGraph(G);//創(chuàng)建圖模塊SaveGraph(G);//存儲(chǔ)圖模塊Print(G);//輸出圖模塊Kruskal(G);//kruskal算法求最小生成樹(shù)模塊Kruskal算法的基本思想是：1、若網(wǎng)絡(luò)G的邊數(shù)en1,則G即為所求的最小生成樹(shù)，否則，一定有e>n-1.2、將網(wǎng)絡(luò)的e條邊按權(quán)值自小到大順序排列。3、將網(wǎng)絡(luò)G中的邊都去掉，只留下n個(gè)孤立頂點(diǎn)作為初始的最小生成樹(shù)T，再按邊的排放順序逐個(gè)考察，若與當(dāng)前E（T）中的邊不構(gòu)成圈，便將它加入到邊集E（T），直至E（T）中邊數(shù)滿(mǎn)n-1為止。(5)Prim(G);//prim算法求最小生成樹(shù)模塊Prim算法是另一種求最小生成樹(shù)的方法，它的基本思想是按權(quán)值局部最小逐次將頂點(diǎn)和邊加入到T中，直至V（T）滿(mǎn)n個(gè)頂點(diǎn)為止。Prim算法步驟為：1、設(shè)最小生成樹(shù)T的V（T）和E（T）均為空。2、從頂點(diǎn)集V（G）中任取一頂點(diǎn)加到頂點(diǎn)集V（T）中。3、在與V（T）中各頂點(diǎn)相關(guān)的所有邊中，取一條權(quán)值最小的邊（Vi,Vj），其中，Vi包含于V（T），Vj包含于V（T）。4、（Vi,Vj）加入到E（T）中，將頂點(diǎn)Vj加入到V（T）中。5、若V（T）已滿(mǎn)n個(gè)頂點(diǎn)，則算法終止，否則轉(zhuǎn)步驟（3）。3.3系統(tǒng)模塊之間的調(diào)用關(guān)系系統(tǒng)的5個(gè)子模塊之間的主要調(diào)用關(guān)系如下圖所示：開(kāi)始開(kāi)始SaveGraph函數(shù)將圖存儲(chǔ)到文件Print函數(shù)輸出網(wǎng)絡(luò)信息Kruskal函數(shù)算出最小生成樹(shù)Prim函數(shù)算出最小生成樹(shù)CreateGraph函數(shù)建立網(wǎng)絡(luò)信息SaveGraph函數(shù)將圖存儲(chǔ)到文件中SaveGraph函數(shù)將圖存儲(chǔ)到文件SaveGraph函數(shù)將圖存儲(chǔ)到文件結(jié)束Choice函數(shù)選擇相應(yīng)功能Interface函數(shù)顯示菜單，等待選擇SaveGraph函數(shù)將圖存儲(chǔ)到文件Print函數(shù)輸出網(wǎng)絡(luò)信息Kruskal函數(shù)算出最小生成樹(shù)Prim函數(shù)算出最小生成樹(shù)CreateGraph函數(shù)建立網(wǎng)絡(luò)信息SaveGraph函數(shù)將圖存儲(chǔ)到文件中SaveGraph函數(shù)將圖存儲(chǔ)到文件SaveGraph函數(shù)將圖存儲(chǔ)到文件結(jié)束Choice函數(shù)選擇相應(yīng)功能Interface函數(shù)顯示菜單，等待選擇4．詳細(xì)設(shè)計(jì)4.1數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)系統(tǒng)采用鄰接矩陣存儲(chǔ)信息,定義如下://圖的數(shù)據(jù)結(jié)構(gòu)typedefstructMGraph//建立圖{ MGraph() { memset(vexs,0,MAX_VERTEX_NUM); } Vertexvexs[MAX_VERTEX_NUM];//城市名稱(chēng) intAdjMatrixarcs;//網(wǎng)絡(luò)條數(shù) intvexnum;//圖的當(dāng)前頂點(diǎn)數(shù)(城市總數(shù)) intarcnum;//圖的當(dāng)前弧數(shù)(網(wǎng)絡(luò)總數(shù))}MGraph;//記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義typedefstructTemp//輔助數(shù)組{ Temp() { lowcost=0; } Vertexadjvex;//當(dāng)前點(diǎn) intlowcost; //權(quán)值}closedge[MAX_VERTEX_NUM];typedefstructCityNumber{ CityNumber() { memset(cityNam,0,1024); } charcityNam[1024];}CityNum;CityNum*Hometown=newCityNum[20];//若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1。#include<stdio.h>intLocateVex(MGraphG,Vertexu){ inti; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) returni; return-1;}4.2系統(tǒng)主要模塊設(shè)計(jì)4.2.1CreateGraph函數(shù)1）創(chuàng)建鄰接矩陣以存儲(chǔ)圖的內(nèi)容。2）填充矩陣，即輸入城市間網(wǎng)絡(luò)的狀況，以方便使用prim算法或kruskal算法求出最經(jīng)濟(jì)的架設(shè)方法。程序如下：//采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無(wú)向網(wǎng)G。MGraphCreateGraph(MGraph&G){inti=0,j=0,k=0,w=0;Vertexva,vb;//路徑的兩個(gè)節(jié)點(diǎn)printf("\n\n\t\t*************建立城市間網(wǎng)絡(luò)信息**********");printf("請(qǐng)輸入城市的總數(shù):\n");scanf("%d",&G.vexnum);printf("請(qǐng)輸入城市間的網(wǎng)絡(luò)數(shù):\n");scanf("%d",&G.arcnum);printf("請(qǐng)輸入%d個(gè)城市的名稱(chēng)(<%d個(gè)字符):\n",G.vexnum);for(i=0;i<G.vexnum;++i)//構(gòu)造頂點(diǎn)向量scanf("%s",G.vexs[i]);for(i=0;i<G.vexnum;++i)//初始化鄰接矩陣for(j=0;j<G.vexnum;++j)G.arcs[i][j]=65535;//65535為無(wú)窮大printf("請(qǐng)輸入%d條網(wǎng)絡(luò)的兩個(gè)城市信息城市1和城市2的距離(以空格作為間隔):\n",G.arcnum);for(k=0;k<G.arcnum;++k){ scanf("%s%s%d",va,vb,&w); //輸入城市1城市2名稱(chēng)及其距離i=LocateVex(G,va); //定位權(quán)值位置j=LocateVex(G,vb);G.arcs[i][j]=G.arcs[j][i]=w;//對(duì)稱(chēng)}returnG;}4.2.2SaveGraph函數(shù) 1）為了避免每次都重復(fù)輸入信息，用文件存儲(chǔ)圖的內(nèi)容。2）如果沒(méi)有文件則建立文件，并把圖的內(nèi)容存儲(chǔ)到文件中。3）如果文件存在，則從文件中讀取圖的內(nèi)容到內(nèi)存，以便完成其他操作。程序如下：MGraphSaveGraph(MGraphG)//輸入內(nèi)容存儲(chǔ)在smalltree.dat{ inti,j; FILE*fp; fp=fopen("smalltree.dat","rt"); if(fp==NULL) { G=CreateGraph(G); fp=fopen("smalltree.dat","wt"); fprintf(fp,"%d\n",G.vexnum);//存城市樹(shù) fprintf(fp,"%d\n",G.arcnum);//存網(wǎng)絡(luò)數(shù) for(i=0;i<G.vexnum;++i) fprintf(fp,"%s\t\n",G.vexs[i]);//存城市名稱(chēng) for(i=0;i<G.vexnum;++i)//存儲(chǔ)鄰接矩陣 for(j=0;j<G.vexnum;++j) if(G.vexs[i]==G.vexs[j]) { G.arcs[i][j]=0;///到它自己 fprintf(fp,"%s_%s_%d\n",G.vexs[i],G.vexs[j],G.arcs[i][j]); } else { fprintf(fp,"%s_%s_%d\n",G.vexs[i],G.vexs[j],G.arcs[i][j]); } rewind(fp); std::cout<<"存儲(chǔ)成功！。。。輸入任意鍵返回."<<std::endl; charc=getchar(); } else//從文件中讀取網(wǎng)的信息存到內(nèi)存中 { printf("\t\t*******正在讀取文件中***********\n"); fscanf(fp,"%d\n",&G.vexnum); fscanf(fp,"%d\n",&G.arcnum); chartempBuffer[1024]; memset(tempBuffer,0,1024); for(i=0;i<G.vexnum;++i) { fgets(tempBuffer,1023,fp); strcpy(Hometown[i].cityNam,tempBuffer); } charCityA[1024]; intLenth=0; memset(CityA,0,1024); for(i=0;i<G.vexnum;++i) for(j=0;j<G.arcnum;++j) { fscanf(fp,"%s",&CityA); intn=0; chartempCityName[1024]; memset(tempCityName,0,1024); while(CityA[n]!='_') { tempCityName[n]=CityA[n]; n++; } strcpy(G.vexs[i+G.vexnum],tempCityName); n++; memset(tempCityName,0,1024); intnum=0; while(CityA[n]!='_') { tempCityName[num]=CityA[n]; n++; num++; } strcpy(G.vexs[i+G.vexnum+1],tempCityName); intnumint=0; n++; memset(tempCityName,0,1024); while(CityA[n]!='\0') { tempCityName[numint]=CityA[n]; n++; numint++; } intX=1; Lenth=0; for(n=numint-1;n>=0;n--) { intintkeynum=0; switch(tempCityName[n]) { case'0': intkeynum=0; break; case'1': intkeynum=1; break; case'2': intkeynum=2; break; case'3': intkeynum=3; break; case'4': intkeynum=4; break; case'5': intkeynum=5; break; case'6': intkeynum=6; break; case'7': intkeynum=7; break; case'8': intkeynum=8; break; case'9': intkeynum=9; break; } Lenth+=intkeynum*X; X=X*10; } G.arcs[i][j]=Lenth; } printf("\t\t*******讀取成功...\t***********\n"); } fclose(fp); returnG;}4.2.3print函數(shù) Print函數(shù)完成輸出功能，將內(nèi)存中圖的內(nèi)容輸出到屏幕上程序如下：MGraphprint(MGraphG)//將輸入的網(wǎng)絡(luò)基本信息打到屏幕上{ inti,j; printf("城市總數(shù):%d\t",G.vexnum); printf("網(wǎng)絡(luò)條數(shù):%d\n",G.arcnum); printf("城市名稱(chēng):\t\n"); for(i=0;i<G.vexnum;i++) { //printf("%s_",G.vexs[i]); std::cout<<Hometown[i].cityNam; } printf("\n"); printf("各個(gè)城市間的距離:\n"); printf("\n"); printf("\n"); for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) printf("%s__%s_距離:%d公里\n",G.vexs[i+G.vexnum],G.vexs[j+G.vexnum],G.arcs[i][j]); std::cout<<"輸入任意鍵返回."<<std::endl; charc=getchar(); returnG;}4.2.4kruskal函數(shù) 用kruskal算法求出最小生成樹(shù)，即最經(jīng)濟(jì)的假設(shè)方案程序如下：MGraphkruskal(MGraphG)//結(jié)果存儲(chǔ)在KruskalResult.dat{ intset[MAX_VERTEX_NUM],i,j; intk=0,a=0,b=0,min=G.arcs[a][b]; FILE*ffp; ffp=fopen("KruskaiResult.dat","wt"); for(i=0;i<G.vexnum;i++) set[i]=i; printf("最短網(wǎng)絡(luò)路徑為:\n"); while(k<G.vexnum-1) { for(i=0;i<G.vexnum;++i)//從G.arcs[i][j]中找到權(quán)值最小的 for(j=i+1;j<G.vexnum;++j) if(G.arcs[i][j]<min) { min=G.arcs[i][j];//min中存最小權(quán)值 a=i; b=j; } if(set[a]!=set[b])//如果a和b值不同則輸出 { printf("%s--%s\t距離:%d\n",G.vexs[a],G.vexs[b],G.arcs[a][b]);//輸出生成樹(shù)各邊 fprintf(ffp,"%s--%s\n",G.vexs[a],G.vexs[b]); k++; for(i=0;i<G.vexnum;i++)//輸出后變成相同值，下次將不會(huì)輸出 if(set[i]==set[b]) set[i]=set[a]; } min=G.arcs[a][b]=G.arcs[b][a]=65535;//輸出過(guò)的權(quán)值變?yōu)樽畲笾?} rewind(ffp); fclose(ffp); returnG;}4.2.5prim函數(shù) 用prim算法求出最小生成樹(shù)，即最經(jīng)濟(jì)的假設(shè)方案程序如下：//用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)T,輸出T的各條邊voidprim(MGraphG,Vertexu)//結(jié)果存儲(chǔ)在PrimResult.dat中{ inti,j,k=0; closedgeclose; FILE*fpp; fpp=fopen("PrimResult.dat","wt"); k=LocateVex(G,u); for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化 { strcpy(close[j].adjvex,u); close[j].lowcost=G.arcs[k][j]; } close[k].lowcost=0;//初始,U={u} printf("最短網(wǎng)絡(luò)路徑為:\n"); for(i=1;i<G.vexnum;++i)//選擇其余G.vexnum-1個(gè)頂點(diǎn) { k=minimum(G,close);//求出T的下一個(gè)結(jié)點(diǎn)：第K頂點(diǎn) printf("(%s-%s)\n",close[k].adjvex,G.vexs[k]); fprintf(fpp,"%s--%s\n",close[k].adjvex,G.vexs[k]);//輸出生成樹(shù)的邊 close[k].lowcost=0;//第K頂點(diǎn)并入U(xiǎn)集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j]<close[j].lowcost)//新頂點(diǎn)并入U(xiǎn)集后重新選擇最小邊 { strcpy(close[j].adjvex,G.vexs[k]); close[j].lowcost=G.arcs[k][j]; } } rewind(fpp); fclose(fpp);}5．調(diào)試分析系統(tǒng)主界面運(yùn)行如圖1所示。各子功能測(cè)試運(yùn)行結(jié)果如下:運(yùn)行程序，出現(xiàn)歡迎界面，見(jiàn)下圖：5.1城市間網(wǎng)絡(luò)信息的建立5.2顯示通信網(wǎng)絡(luò)的基本信息5.3查詢(xún)最短網(wǎng)絡(luò)路徑6．用戶(hù)使用說(shuō)明1、運(yùn)行程序，出現(xiàn)歡迎界面；2、按1進(jìn)入輸入系統(tǒng)，如果文件沒(méi)有存儲(chǔ)城市網(wǎng)絡(luò)內(nèi)容，則由用戶(hù)從鍵盤(pán)讀入，讀入后自動(dòng)保存到文件中，按任意鍵即可返回歡迎界面；3、如果文件內(nèi)已經(jīng)存儲(chǔ)了城市網(wǎng)絡(luò)內(nèi)容，則顯示文件已保存到文件中，按任意鍵返回；4、輸入2可以在屏幕上輸出存儲(chǔ)在文件內(nèi)的城市間網(wǎng)絡(luò)信息，顯示完畢后按任意鍵可返回歡迎見(jiàn)面；5、按3和4分別可實(shí)現(xiàn)kruskal算法和prim算法求出最小生成樹(shù)，即最低經(jīng)濟(jì)代價(jià)建設(shè)通信網(wǎng)絡(luò)（距離最短的最經(jīng)濟(jì)），顯示完畢后按任意鍵返回歡迎界面；6、按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)蔚敏、吳偉民《VisualC++課程設(shè)計(jì)案例精選與編程指導(dǎo)》陳清華、朱紅對(duì)所設(shè)計(jì)的軟件進(jìn)行自我評(píng)價(jià)，如創(chuàng)新點(diǎn)、未解決的問(wèn)題等情況說(shuō)明：1、對(duì)圖的邏輯結(jié)構(gòu)及存儲(chǔ)結(jié)構(gòu)有了更深刻的認(rèn)識(shí)；2、對(duì)prim算法和kruskal算法亦有了更深刻的認(rèn)識(shí)；3、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力，深入了解了模塊化的程序設(shè)計(jì)步驟；4、kruskal算法應(yīng)該用堆排序然后再找路徑，但未能實(shí)現(xiàn)；5、輸入方面如果沒(méi)有將網(wǎng)絡(luò)信息存入文件，由鍵盤(pán)輸入信息時(shí)，如果手誤輸錯(cuò)了無(wú)法更改，只能重新輸入，而且如果輸入中文，最后顯示時(shí)會(huì)出現(xiàn)亂碼，只能用英文輸入；6、kruskal算法的實(shí)現(xiàn)仍有問(wèn)題，結(jié)果存在錯(cuò)誤，而且只能實(shí)行到第三步，到第四步時(shí)會(huì)出現(xiàn)程序關(guān)閉的提醒；9、程序源代碼：#include<stdlib.h>#include<string.h>#include<iostream>#defineMAX_VERTEX_NUM 20//最大頂點(diǎn)個(gè)數(shù)#defineMAX_NAME 3//頂點(diǎn)字符串的最大長(zhǎng)度+1typedefintintAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];typedefcharVertex[MAX_NAME];//鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)//圖的數(shù)據(jù)結(jié)構(gòu)typedefstructMGraph//建立圖{ MGraph() { memset(vexs,0,MAX_VERTEX_NUM); } Vertexvexs[MAX_VERTEX_NUM];//城市名稱(chēng) intAdjMatrixarcs;//網(wǎng)絡(luò)條數(shù) intvexnum;//圖的當(dāng)前頂點(diǎn)數(shù)(城市總數(shù)) intarcnum;//圖的當(dāng)前弧數(shù)(網(wǎng)絡(luò)總數(shù))}MGraph;//記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義typedefstructTemp//輔助數(shù)組{ Temp() { lowcost=0; } Vertexadjvex;//當(dāng)前點(diǎn) intlowcost; //權(quán)值}closedge[MAX_VERTEX_NUM];typedefstructCityNumber{ CityNumber() { memset(cityNam,0,1024); } charcityNam[1024];}CityNum;CityNum*Hometown=newCityNum[20];//若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1。#include<stdio.h>intLocateVex(MGraphG,Vertexu){ inti; for(i=0;i<G.vexnum;++i) if(strcmp(u,G.vexs[i])==0) returni; return-1;}//采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無(wú)向網(wǎng)G。MGraphCreateGraph(MGraph&G){ inti=0,j=0,k=0,w=0; Vertexva,vb;//路徑的兩個(gè)節(jié)點(diǎn) printf("\n\n\t\t*************建立城市間網(wǎng)絡(luò)信息**********"); printf("請(qǐng)輸入城市的總數(shù):\n"); scanf("%d",&G.vexnum); printf("請(qǐng)輸入城市間的網(wǎng)絡(luò)數(shù):\n"); scanf("%d",&G.arcnum); printf("請(qǐng)輸入%d個(gè)城市的名稱(chēng)(<%d個(gè)字符):\n",G.vexnum); for(i=0;i<G.vexnum;++i)//構(gòu)造頂點(diǎn)向量 scanf("%s",G.vexs[i]); for(i=0;i<G.vexnum;++i)//初始化鄰接矩陣 for(j=0;j<G.vexnum;++j) G.arcs[i][j]=65535;//65535為無(wú)窮大 printf("請(qǐng)輸入%d條網(wǎng)絡(luò)的兩個(gè)城市信息城市1和城市2的距離(以空格作為間隔):\n",G.arcnum); for(k=0;k<G.arcnum;++k) { scanf("%s%s%d",va,vb,&w); //輸入城市1城市2名稱(chēng)及其距離 i=LocateVex(G,va); //定位權(quán)值位置 j=LocateVex(G,vb); G.arcs[i][j]=G.arcs[j][i]=w;//對(duì)稱(chēng) } returnG;}MGraphSaveGraph(MGraphG)//輸入內(nèi)容存儲(chǔ)在smalltree.dat{ inti,j; FILE*fp; fp=fopen("smalltree.dat","rt"); if(fp==NULL) { G=CreateGraph(G); fp=fopen("smalltree.dat","wt"); fprintf(fp,"%d\n",G.vexnum);//存城市樹(shù) fprintf(fp,"%d\n",G.arcnum);//存網(wǎng)絡(luò)數(shù) for(i=0;i<G.vexnum;++i) fprintf(fp,"%s\t\n",G.vexs[i]);//存城市名稱(chēng) for(i=0;i<G.vexnum;++i)//存儲(chǔ)鄰接矩陣 for(j=0;j<G.vexnum;++j) if(G.vexs[i]==G.vexs[j]) { G.arcs[i][j]=0;///到它自己 fprintf(fp,"%s_%s_%d\n",G.vexs[i],G.vexs[j],G.arcs[i][j]); } else { fprintf(fp,"%s_%s_%d\n",G.vexs[i],G.vexs[j],G.arcs[i][j]); } rewind(fp); std::cout<<"存儲(chǔ)成功！。。。輸入任意鍵返回."<<std::endl; charc=getchar(); } else//從文件中讀取網(wǎng)的信息存到內(nèi)存中 { printf("\t\t*******正在讀取文件中***********\n"); fscanf(fp,"%d\n",&G.vexnum); fscanf(fp,"%d\n",&G.arcnum); chartempBuffer[1024]; memset(tempBuffer,0,1024); for(i=0;i<G.vexnum;++i) { fgets(tempBuffer,1023,fp); strcpy(Hometown[i].cityNam,tempBuffer); } charCityA[1024]; intLenth=0; memset(CityA,0,1024); for(i=0;i<G.vexnum;++i) for(j=0;j<G.arcnum;++j) { fscanf(fp,"%s",&CityA); intn=0; chartempCityName[1024]; memset(tempCityName,0,1024); while(CityA[n]!='_') { tempCityName[n]=CityA[n]; n++; } strcpy(G.vexs[i+G.vexnum],tempCityName); n++; memset(tempCityName,0,1024); intnum=0; while(CityA[n]!='_') { tempCityName[num]=CityA[n]; n++; num++; } strcpy(G.vexs[i+G.vexnum+1],tempCityName); intnumint=0; n++; memset(tempCityName,0,1024); while(CityA[n]!='\0') { tempCityName[numint]=CityA[n]; n++; numint++; } intX=1; Lenth=0; for(n=numint-1;n>=0;n--) { intintkeynum=0; switch(tempCityName[n]) { case'0': intkeynum=0; break; case'1': intkeynum=1; break; case'2': intkeynum=2; break; case'3': intkeynum=3; break; case'4': intkeynum=4; break; case'5': intkeynum=5; break; case'6': intkeynum=6; break; case'7': intkeynum=7; break; case'8': intkeynum=8; break; case'9': intkeynum=9; break; } Lenth+=intkeynum*X; X=X*10; } G.arcs[i][j]=Lenth; } printf("\t\t*******讀取成功...\t***********\n"); } fclose(fp); returnG;}MGraphprint(MGraphG)//將輸入的網(wǎng)絡(luò)基本信息打到屏幕上{ inti,j; printf("城市總數(shù):%d\t",G.vexnum); printf("網(wǎng)絡(luò)條數(shù):%d\n",G.arcnum); printf("城市名稱(chēng):\t\n"); for(i=0;i<G.vexnum;i++) { //printf("%s_",G.vexs[i]); std::cout<<Hometown[i].cityNam; } printf("\n"); printf("各個(gè)城市間的距離:\n"); printf("\n"); printf("\n"); for(i=0;i<G.vexnum;++i) for(j=0;j<G.vexnum;++j) printf("%s__%s_距離:%d公里\n",G.vexs[i+G.vexnum],G.vexs[j+G.vexnum],G.arcs[i][j]); std::cout<<"輸入任意鍵返回."<<std::endl; charc=getchar(); returnG;}MGraphkruskal(MGraphG)//結(jié)果存儲(chǔ)在KruskalResult.dat{ intset[MAX_VERTEX_NUM],i,j; intk=0,a=0,b=0,min=G.arcs[a][b]; FILE*ffp; ffp=fopen("KruskaiResult.dat","wt"); for(i=0;i<G.vexnum;i++) set[i]=i; printf("最短網(wǎng)絡(luò)路徑為:\n"); while(k<G.vexnum-1) { for(i=0;i<G.vexnum;++i)//從G.arcs[i][j]中找到權(quán)值最小的 for(j=i+1;j<G.vexnum;++j) if(G.arcs[i][j]<min) { min=G.arcs[i][j];//min中存最小權(quán)值 a=i; b=j; } if(set[a]!=set[b])//如果a和b值不同則輸出 { printf("%s--%s\t距離:%d\n",G.vexs[a],G.vexs[b],G.arcs[a][b]);//輸出生成樹(shù)各邊 fprintf(ffp,"%s--%s\n",G.vexs[a],G.vexs[b]); k++; for(i=0;i<G.vexnum;i++)//輸出后變成相同值，下次將不會(huì)輸出 if(set[i]==set[b]) set[i]=set[a]; } min=G.arcs[a][b]=G.arcs[b][a]=65535;//輸出過(guò)的權(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(!close[i].lowcost) i++; min=close[i].lowcost;//第一個(gè)不為0的值 k=i; for(j=i+1;j<G.vexnum;j++) if(close[j].lowcost>0&&min>close[j].lowcost) { min=close[j].lowcost; k=j; } returnk;}//用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹(shù)T,輸出T的各條邊voidprim(MGraphG,Vertexu)//結(jié)果存儲(chǔ)在PrimResult.dat中{ inti,j,k=0; closedgeclose; FILE*fpp; fpp=fopen("PrimResult.dat","wt"); k=LocateVex(G,u); for(j=0;j<G.vexnum;++j)//輔助數(shù)組初始化 { strcpy(close[j].adjvex,u); close[j].lowcost=G.arcs[k][j]; } close[k].lowcost=0;//初始,U={u} printf("最短網(wǎng)絡(luò)路徑為:\n"); for(i=1;i<G.vexnum;++i)//選擇其余G.vexnum-1個(gè)頂點(diǎn) { k=minimum(G,close);//求出T的下一個(gè)結(jié)點(diǎn)：第K頂點(diǎn) printf("(%s-%s)\n",close[k].adjvex,G.vexs[k]); fprintf(fpp,"%s--%s\n",close[k].adjvex,G.vexs[k]);//輸出生成樹(shù)的邊 close[k].lowcost=0;//第K頂點(diǎn)并入U(xiǎn)集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j]<close[j].lowcost)//新頂點(diǎn)并入U(xiǎn)集后重新選擇最小邊 { strcpy(close[j].adjvex,G.vexs[k]); close[j].lowcost=G.arcs[k][j]; } } rewind(fpp); fclose(fpp);}voidinterface()//初始界面{ printf("____________________________________________\n"); printf("…………最小生成樹(shù)的應(yīng)用…………\n"); printf("…………通信網(wǎng)絡(luò)建設(shè)問(wèn)題………\n"); printf("…………Made…By…啦啦啦Version1.0\n"); printf("_______________________________________________________\n"); printf("\n"); printf("\n"); printf("___________________________________________________________________________________\n"); printf("\n"); printf("___________1.輸入通信網(wǎng)絡(luò)基本信息并將信息存儲(chǔ)到文件中\(zhòng)n"); printf("___________2.將網(wǎng)絡(luò)基本信息顯示到屏幕上\n"); printf("___________3.用kruskal算法算出最短路徑，并將結(jié)果存儲(chǔ)到文件中\(zhòng)n"); printf("___________4.用prim算法算出最短路徑，并將結(jié)果存儲(chǔ)到文件中\(zhòng)n"); printf("___________5.退出\n"); printf("\n"); printf("\n"); printf("\t\t\t請(qǐng)輸入您要選擇的選項(xiàng)(1-5):\n");}voidchoice()//控制選項(xiàng)函數(shù){ MGraphG=MGraph(); intc; interface(); std::cin>>c; while(c) { switch(c) { case1: system("cls"); system("color1b"); printf("\n"); printf("\n\t\t*****************歡迎使用**********************"); printf("\n__________________Welcom_to_Use"); printf("\n********************************************_____________*************************************"); printf("\n