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

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

2、的系統(tǒng)化、正規(guī)化、規(guī)范化方面是非常必要的。如何在最小的經(jīng)濟(jì)條件下達(dá)到利益最大化，是所有公司、企業(yè)已經(jīng)政府部門一直所探討和解決的問題。對于城市通信管理系統(tǒng)來說，若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條通信線路即可，建立最小生成樹即能實(shí)現(xiàn)以最低的經(jīng)濟(jì)代價(jià)建設(shè)這個(gè)通信網(wǎng)。1.2 基本任務(wù)通過用戶調(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）編寫算法，求解最小代價(jià)通信網(wǎng)絡(luò)；（3）輸出該通信網(wǎng)絡(luò)中各邊及其權(quán)值；n個(gè)城市間的線路連接屬于圖的結(jié)構(gòu)，要構(gòu)建最經(jīng)濟(jì)的

3、通信網(wǎng)絡(luò)，即是構(gòu)建圖的生成樹。把城市間的線路關(guān)系看成是圖。城市間的距離即是圖的權(quán)值。利用prim算法或kruskal算法即可求出最小生成樹。2概要設(shè)計(jì)為了完成需求分析的基本任務(wù)，主要從以下3個(gè)方面進(jìn)行設(shè)計(jì)：2.1 主界面設(shè)計(jì)為了使程序界面更加友好，建立了interface函數(shù)和choice函數(shù)，即歡迎界面以及實(shí)現(xiàn)用戶可以按數(shù)字鍵選擇相應(yīng)的功能。歡迎界面如下圖： 2.2 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì)若要在n個(gè)城市之間建設(shè)通信網(wǎng)絡(luò)，只需要架設(shè)n-1條通信線路即可。所以，將一個(gè)現(xiàn)實(shí)的經(jīng)濟(jì)問題，轉(zhuǎn)變?yōu)橐粋€(gè)求最小生成樹的問題。本系統(tǒng)軟件采用經(jīng)典算法prim算法和kruskal算法實(shí)現(xiàn)求最小生成樹，從而獲取最經(jīng)濟(jì)的通信路

4、徑。2.3 系統(tǒng)功能設(shè)計(jì)系統(tǒng)建立了interface函數(shù)和choice函數(shù)，其功能如下：（1） interface函數(shù)：使用戶更清晰看到程序的主體，使得程序界面更為直觀。程序如下： void interface() /初始界面 printf(" _n");printf(" 最小生成樹的應(yīng)用n");printf(" 通信網(wǎng)絡(luò)建設(shè)問題n");printf(" MadeBy董卓琴 Version1.0n");printf("_n");printf(" n");printf(&quo

5、t; n");printf("_n"printf(" n");printf("_1.輸入通信網(wǎng)絡(luò)基本信息并將信息存儲到文件中n"); printf("_2.將網(wǎng)絡(luò)基本信息顯示到屏幕上n"); printf("_3.用kruskal算法算出最短路徑，并將結(jié)果存儲 到文件中n"); printf("_4.用prim算法算出最短路徑，并將結(jié)果存儲到文件中n"); printf("_5.退出n"); printf(" n");prin

6、tf(" n");printf(" ttt請輸入您要選擇的選項(xiàng)(1-5):n"); （2） choice函數(shù)：為用戶提供了方便，用戶可以通過按數(shù)字鍵來選擇相應(yīng)的功能。程序如下： void choice() /控制選項(xiàng)函數(shù)MGraph G = MGraph();int c;interface();std:cin>>c;while(c)switch(c)case 1:system("cls");system("color 1b");printf(" n");printf(" n

7、tt*歡迎使用*");printf(" n_Welcom_to_Use");printf("n*_*");printf(" n");printf(" n");printf(" n");G=SaveGraph(G);system("cls");interface();/system("PAUSE");std:cin>>c;continue;case 2:system("cls");system("color

8、 1c");printf(" n");printf(" ntt*歡迎使用*");printf(" n_Welcom_to_Use");printf("n*_*");printf(" n");printf(" ttt下面顯示的是通信網(wǎng)絡(luò)的基本信息n");printf(" n");G=SaveGraph(G);G=print(G);printf(" nttt按任意鍵返回n");c=getchar();/c=getchar();sy

9、stem("cls");interface();/system("PAUSE");std:cin>>c;continue;case 3:system("cls");system("color 1e");printf(" n");printf(" ntt*歡迎使用*");printf(" n_Welcom_to_Use");printf("n*_*");printf(" n");printf("

10、n");printf(" n");G=SaveGraph(G);prim(G,G.vexs0);printf(" tt*結(jié)果存入KruskalResult.dat中，按任意鍵返回*n");c=getchar();c=getchar();system("cls");interface();system("PAUSE");std:cin>>c;continue;case 4:system("cls");system("color 1d");printf(&q

11、uot; 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=getchar();c=getchar();system("cls&qu

12、ot;);interface();system("PAUSE");std:cin>>c;continue;case 5:return; 3模塊設(shè)計(jì)3.1 模塊設(shè)計(jì)系統(tǒng)主要包含主程序模塊和其它操作模塊。其調(diào)用關(guān)系如下圖所示。choice函數(shù)interface函數(shù)開始 3.2 系統(tǒng)子模塊及其功能設(shè)計(jì)本系統(tǒng)共設(shè)計(jì)了5個(gè)子模塊，各程序的函數(shù)名及功能說明如下：(1) CreateGraph(G); /創(chuàng)建圖模塊(2) SaveGraph(G); /存儲圖模塊(3) Print(G); /輸出圖模塊(4) Kruskal(G); /kruskal算法求最小生成樹模塊 Kru

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

14、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）已滿n個(gè)頂點(diǎn)，則算法終止，否則轉(zhuǎn)步驟（3）。 3.3 系統(tǒng)模塊之間的調(diào)用關(guān)系系統(tǒng)的5個(gè)子模塊之間的主要調(diào)用關(guān)系如下圖所示：開始SaveGraph函數(shù)將圖存儲到文件Print函數(shù)輸出網(wǎng)絡(luò)信息Kruskal函數(shù)算出最小生成樹Prim函數(shù)算出最小生成樹CreateGraph函數(shù)建立網(wǎng)絡(luò)信息SaveGraph函數(shù)將圖存儲到文件中SaveGraph函數(shù)將圖存儲到

15、文件SaveGraph函數(shù)將圖存儲到文件結(jié)束Choice函數(shù)選擇相應(yīng)功能Interface函數(shù)顯示菜單，等待選擇 4詳細(xì)設(shè)計(jì) 4.1 數(shù)據(jù)結(jié)構(gòu)設(shè)計(jì) 系統(tǒng)采用鄰接矩陣存儲信息,定義如下: / 圖的數(shù)據(jù)結(jié)構(gòu)typedef struct MGraph /建立圖MGraph()memset(vexs, 0, MAX_VERTEX_NUM);Vertex vexsMAX_VERTEX_NUM;/ 城市名稱intAdjMatrix arcs;/ 網(wǎng)絡(luò)條數(shù)int vexnum; / 圖的當(dāng)前頂點(diǎn)數(shù)(城市總數(shù))int arcnum; / 圖的當(dāng)前弧數(shù)(網(wǎng)絡(luò)總數(shù)) MGraph;/ 記錄從頂點(diǎn)集U到V-U的代價(jià)

16、最小的邊的輔助數(shù)組定義typedef struct Temp /輔助數(shù)組Temp()lowcost = 0;Vertex adjvex; /當(dāng)前點(diǎn)int lowcost;/權(quán)值closedgeMAX_VERTEX_NUM;typedef struct CityNumberCityNumber()memset(cityNam, 0, 1024);char cityNam1024;CityNum;CityNum* Hometown = new CityNum20;/ 若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1。#include<stdio.h>int LocateVex(M

17、Graph G,Vertex u) int i;for(i = 0; i < G.vexnum; +i)if( strcmp(u, G.vexsi) = 0)return i;return -1; 4.2 系統(tǒng)主要模塊設(shè)計(jì) 4.2.1 CreateGraph函數(shù) 1）創(chuàng)建鄰接矩陣以存儲圖的內(nèi)容。 2）填充矩陣，即輸入城市間網(wǎng)絡(luò)的狀況，以方便使用prim算法或kruskal算法求 出最經(jīng)濟(jì)的架設(shè)方法。 程序如下： / 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng)G。 MGraph CreateGraph(MGraph &G)int i = 0, j = 0, k = 0, w = 0;

18、Vertex va,vb; /路徑的兩個(gè)節(jié)點(diǎn) printf("nntt*建立城市間網(wǎng)絡(luò)信息*"); printf("請輸入城市的總數(shù):n"); scanf("%d",&G.vexnum ); printf("請輸入城市間的網(wǎng)絡(luò)數(shù):n"); scanf("%d",&G.arcnum); printf("請輸入%d個(gè)城市的名稱(<%d個(gè)字符):n",G.vexnum); for(i=0;i<G.vexnum;+i) / 構(gòu)造頂點(diǎn)向量 scanf(&qu

19、ot;%s",G.vexsi); for(i=0;i<G.vexnum;+i) / 初始化鄰接矩陣 for(j=0;j<G.vexnum;+j) G.arcsij=65535; / 65535為無窮大 printf("請輸入%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名稱及其距離 i=LocateVex( G, va);/定位權(quán)值位置 j=Locate

20、Vex( G, vb); G.arcsij=G.arcsji=w; /對稱 return G; 4.2.2 SaveGraph函數(shù)1）為了避免每次都重復(fù)輸入信息，用文件存儲圖的內(nèi)容。 2）如果沒有文件則建立文件，并把圖的內(nèi)容存儲到文件中。 3）如果文件存在，則從文件中讀取圖的內(nèi)容到內(nèi)存，以便完成其他操作。程序如下： MGraph SaveGraph(MGraph G) /輸入內(nèi)容存儲在smalltree.dat int i,j;FILE*fp;fp=fopen("smalltree.dat","rt");if(fp=NULL)G=CreateGraph(

21、G);fp=fopen("smalltree.dat","wt");fprintf(fp,"%dn",G.vexnum); /存城市樹fprintf(fp,"%dn",G.arcnum); /存網(wǎng)絡(luò)數(shù)for(i=0;i<G.vexnum;+i)fprintf(fp,"%stn",G.vexsi);/存城市名稱for(i=0;i<G.vexnum;+i)/存儲鄰接矩陣for(j=0;j<G.vexnum; +j)if(G.vexsi = G.vexsj)G.arcsij = 0;

22、 /到它自己fprintf(fp,"%s_%s_%dn",G.vexsi, G.vexsj, G.arcsij);elsefprintf(fp,"%s_%s_%dn",G.vexsi, G.vexsj, G.arcsij);rewind(fp);std:cout<<"存儲成功！。輸入任意鍵返回."<<std:endl;char c = getchar();else /從文件中讀取網(wǎng)的信息存到內(nèi)存中printf("tt*正在讀取文件中.*n");fscanf(fp,"%dn"

23、;, &G.vexnum); fscanf(fp,"%dn", &G.arcnum);char tempBuffer1024;memset(tempBuffer, 0, 1024);for(i=0; i<G.vexnum; +i)fgets(tempBuffer, 1023, fp);strcpy(Hometowni.cityNam,tempBuffer);char CityA1024;int Lenth = 0;memset(CityA, 0, 1024); for(i=0; i<G.vexnum; +i) for(j=0;j<G.arc

24、num;+j)fscanf(fp, "%s", &CityA);int n = 0;char tempCityName1024;memset(tempCityName, 0, 1024);while(CityAn != '_')tempCityNamen = CityAn;n+;strcpy(G.vexsi+G.vexnum, tempCityName);n+;memset(tempCityName, 0, 1024);int num = 0;while(CityAn != '_')tempCityNamenum = CityAn;n

25、+;num+;strcpy(G.vexsi+G.vexnum+1, tempCityName);int numint = 0;n+;memset(tempCityName, 0, 1024);while(CityAn != '0')tempCityNamenumint = CityAn;n+;numint+;int X = 1;Lenth = 0;for(n = numint-1; n>=0; n-)int intkeynum = 0;switch(tempCityNamen)case '0':intkeynum = 0;break;case '1

26、':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'

27、;:intkeynum = 9;break;Lenth += intkeynum*X;X = X*10;G.arcsij = Lenth;printf("tt*讀取成功.t*n");fclose(fp);return G; 4.2.3 print函數(shù)Print函數(shù)完成輸出功能，將內(nèi)存中圖的內(nèi)容輸出到屏幕上程序如下：MGraph print(MGraph G)/將輸入的網(wǎng)絡(luò)基本信息打到屏幕上int i,j;printf("城市總數(shù):%dt", G.vexnum);printf("網(wǎng)絡(luò)條數(shù):%dn", G.arcnum);printf(&

28、quot;城市名稱:tn");for(i=0; i<G.vexnum; i+)/printf("%s_",G.vexsi);std:cout<<Hometowni.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.vex

29、si+G.vexnum,G.vexsj+G.vexnum,G.arcsij);std:cout<<"輸入任意鍵返回."<<std:endl;char c = getchar();return G; 4.2.4 kruskal函數(shù)用kruskal算法求出最小生成樹，即最經(jīng)濟(jì)的假設(shè)方案程序如下：MGraph kruskal(MGraph G) /結(jié)果存儲在KruskalResult.datint setMAX_VERTEX_NUM,i,j;int k=0,a=0,b=0,min=G.arcsab;FILE*ffp;ffp=fopen("Krus

30、kaiResult.dat","wt");for(i=0;i<G.vexnum;i+)seti=i;printf("最短網(wǎng)絡(luò)路徑為:n");while(k<G.vexnum-1)for(i=0;i<G.vexnum;+i) /從G.arcsij中找到權(quán)值最小的for(j=i+1;j<G.vexnum;+j)if(G.arcsij<min)min=G.arcsij;/min中存最小權(quán)值a=i;b=j;if(seta!=setb) /如果a和b值不同則輸出printf("%s-%st距離:%dn",

31、G.vexsa,G.vexsb,G.arcsab);/輸出生成樹各邊f(xié)printf(ffp,"%s-%sn",G.vexsa,G.vexsb);k+;for(i=0;i<G.vexnum;i+) /輸出后變成相同值，下次將不會輸出if(seti=setb)seti=seta; min=G.arcsab=G.arcsba=65535; /輸出過的權(quán)值變?yōu)樽畲笾祌ewind(ffp);fclose(ffp);return G; 4.2.5 prim函數(shù)用prim算法求出最小生成樹，即最經(jīng)濟(jì)的假設(shè)方案程序如下：/ 用普里姆算法從第u個(gè)頂點(diǎn)出發(fā)構(gòu)造網(wǎng)G的最小生成樹T,輸出T的

32、各條邊void prim(MGraph G,Vertex u) /結(jié)果存儲在PrimResult.dat中int i,j,k=0;closedge close;FILE*fpp;fpp=fopen("PrimResult.dat","wt");k=LocateVex(G,u);for(j=0;j<G.vexnum;+j) / 輔助數(shù)組初始化 strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;closek.lowcost=0; / 初始,U=u printf("最短網(wǎng)絡(luò)路徑為:n");

33、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",closek.adjvex,G.vexsk);fprintf(fpp,"%s-%sn",closek.adjvex,G.vexsk); / 輸出生成樹的邊 closek.lowcost=0; / 第K頂點(diǎn)并入U(xiǎn)集 for(j=0;j<G.vexnum;+j)if(G.arcskj<closej.lowcost) / 新頂點(diǎn)并入U(xiǎn)集后重新選擇最小

34、邊strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp);5調(diào)試分析系統(tǒng)主界面運(yùn)行如圖1所示。各子功能測試運(yùn)行結(jié)果如下:運(yùn)行程序，出現(xiàn)歡迎界面，見下圖：5.1 城市間網(wǎng)絡(luò)信息的建立5.2顯示通信網(wǎng)絡(luò)的基本信息 5.3 查詢最短網(wǎng)絡(luò)路徑 6用戶使用說明 1、運(yùn)行程序，出現(xiàn)歡迎界面； 2、按1進(jìn)入輸入系統(tǒng)，如果文件沒有存儲城市網(wǎng)絡(luò)內(nèi)容，則由用戶從鍵盤讀入，讀入后自動保存到文件中，按任意鍵即可返回歡迎界面； 3、如果文件內(nèi)已經(jīng)存儲了城市網(wǎng)絡(luò)內(nèi)容，則顯示文件已保存到文件中，按任意鍵返回； 4、輸入2可以

35、在屏幕上輸出存儲在文件內(nèi)的城市間網(wǎng)絡(luò)信息，顯示完畢后按任意鍵可返 回歡迎見面； 5、按3和4分別可實(shí)現(xiàn)kruskal算法和prim算法求出最小生成樹，即最低經(jīng)濟(jì)代價(jià)建設(shè)通信網(wǎng)絡(luò)（距離最短的最經(jīng)濟(jì)），顯示完畢后按任意鍵返回歡迎界面； 6、按5退出程序。7參考文獻(xiàn) 數(shù)據(jù)結(jié)構(gòu)理論與實(shí)踐 楊永斌 （核心算法prim算法以及kruskal算法來源于此） 數(shù)據(jù)結(jié)構(gòu)（C語言）實(shí)踐教程 胡元義 數(shù)據(jù)結(jié)構(gòu) 嚴(yán)蔚敏、吳偉民 Visual C+課程設(shè)計(jì)案例精選與編程指導(dǎo) 陳清華、朱紅8 對所設(shè)計(jì)的軟件進(jìn)行自我評價(jià)，如創(chuàng)新點(diǎn)、未解決的問題等情況說明： 1、對圖的邏輯結(jié)構(gòu)及存儲結(jié)構(gòu)有了更深刻的認(rèn)識； 2、對prim算法

36、和kruskal算法亦有了更深刻的認(rèn)識； 3、了解并掌握數(shù)據(jù)結(jié)構(gòu)與算法的設(shè)計(jì)方法，具備初步的獨(dú)立分析和設(shè)計(jì)能力，深入了解了模塊化的程序設(shè)計(jì)步驟； 4、kruskal算法應(yīng)該用堆排序然后再找路徑，但未能實(shí)現(xiàn)； 5、輸入方面如果沒有將網(wǎng)絡(luò)信息存入文件，由鍵盤輸入信息時(shí)，如果手誤輸錯(cuò)了無法更改，只能重新輸入，而且如果輸入中文，最后顯示時(shí)會出現(xiàn)亂碼，只能用英文輸入； 6、kruskal算法的實(shí)現(xiàn)仍有問題，結(jié)果存在錯(cuò)誤，而且只能實(shí)行到第三步，到第四步時(shí)會出現(xiàn)程序關(guān)閉的提醒；9、程序源代碼： #include<stdlib.h>#include<string.h>#include

37、<iostream>#define MAX_VERTEX_NUM20/ 最大頂點(diǎn)個(gè)數(shù)#define MAX_NAME3 / 頂點(diǎn)字符串的最大長度+1 typedef int intAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef char VertexMAX_NAME;/ 鄰接矩陣的數(shù)據(jù)結(jié)構(gòu)/ 圖的數(shù)據(jù)結(jié)構(gòu)typedef struct MGraph /建立圖MGraph()memset(vexs, 0, MAX_VERTEX_NUM);Vertex vexsMAX_VERTEX_NUM;/ 城市名稱intAdjMatrix arcs;/ 網(wǎng)

38、絡(luò)條數(shù)int vexnum; / 圖的當(dāng)前頂點(diǎn)數(shù)(城市總數(shù))int arcnum; / 圖的當(dāng)前弧數(shù)(網(wǎng)絡(luò)總數(shù)) MGraph;/ 記錄從頂點(diǎn)集U到V-U的代價(jià)最小的邊的輔助數(shù)組定義typedef struct Temp /輔助數(shù)組Temp()lowcost = 0;Vertex adjvex; /當(dāng)前點(diǎn)int lowcost;/權(quán)值closedgeMAX_VERTEX_NUM;typedef struct CityNumberCityNumber()memset(cityNam, 0, 1024);char cityNam1024;CityNum;CityNum* Hometown = ne

39、w CityNum20;/ 若G中存在頂點(diǎn)u,則返回該頂點(diǎn)在圖中位置;否則返回-1。#include<stdio.h>int LocateVex(MGraph G,Vertex u) int i;for(i = 0; i < G.vexnum; +i)if( strcmp(u, G.vexsi) = 0)return i;return -1;/ 采用數(shù)組(鄰接矩陣)表示法,構(gòu)造無向網(wǎng)G。MGraph CreateGraph(MGraph &G)int i = 0, j = 0, k = 0, w = 0;Vertex va,vb; /路徑的兩個(gè)節(jié)點(diǎn)printf(&qu

40、ot;nntt*建立城市間網(wǎng)絡(luò)信息*");printf("請輸入城市的總數(shù):n");scanf("%d",&G.vexnum ); printf("請輸入城市間的網(wǎng)絡(luò)數(shù):n");scanf("%d",&G.arcnum); printf("請輸入%d個(gè)城市的名稱(<%d個(gè)字符):n",G.vexnum);for(i=0;i<G.vexnum;+i) / 構(gòu)造頂點(diǎn)向量 scanf("%s",G.vexsi);for(i=0;i<G.v

41、exnum;+i) / 初始化鄰接矩陣 for(j=0;j<G.vexnum;+j)G.arcsij=65535; / 65535為無窮大 printf("請輸入%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名稱及其距離 i=LocateVex( G, va);/定位權(quán)值位置j=LocateVex( G, vb);G.arcsij=G.arcsji=w; /對稱return

42、 G;MGraph SaveGraph(MGraph G) /輸入內(nèi)容存儲在smalltree.datint i,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;i<G.ve

43、xnum;+i)fprintf(fp,"%stn",G.vexsi);/存城市名稱for(i=0;i<G.vexnum;+i)/存儲鄰接矩陣for(j=0;j<G.vexnum; +j)if(G.vexsi = G.vexsj)G.arcsij = 0; /到它自己fprintf(fp,"%s_%s_%dn",G.vexsi, G.vexsj, G.arcsij);elsefprintf(fp,"%s_%s_%dn",G.vexsi, G.vexsj, G.arcsij);rewind(fp);std:cout<&l

44、t;"存儲成功！。輸入任意鍵返回."<<std:endl;char c = getchar();else /從文件中讀取網(wǎng)的信息存到內(nèi)存中printf("tt*正在讀取文件中.*n");fscanf(fp,"%dn", &G.vexnum); fscanf(fp,"%dn", &G.arcnum);char tempBuffer1024;memset(tempBuffer, 0, 1024);for(i=0; i<G.vexnum; +i)fgets(tempBuffer, 102

45、3, fp);strcpy(Hometowni.cityNam,tempBuffer);char CityA1024;int Lenth = 0;memset(CityA, 0, 1024); for(i=0; i<G.vexnum; +i) for(j=0;j<G.arcnum;+j)fscanf(fp, "%s", &CityA);int n = 0;char tempCityName1024;memset(tempCityName, 0, 1024);while(CityAn != '_')tempCityNamen = CityA

46、n;n+;strcpy(G.vexsi+G.vexnum, tempCityName);n+;memset(tempCityName, 0, 1024);int num = 0;while(CityAn != '_')tempCityNamenum = CityAn;n+;num+;strcpy(G.vexsi+G.vexnum+1, tempCityName);int numint = 0;n+;memset(tempCityName, 0, 1024);while(CityAn != '0')tempCityNamenumint = CityAn;n+;nu

47、mint+;int X = 1;Lenth = 0;for(n = numint-1; n>=0; n-)int intkeynum = 0;switch(tempCityNamen)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':int

48、keynum = 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.arcsij = Lenth;printf("tt*讀取成功.t*n");fclose(fp);return G;MGraph print(MGraph G)/將輸入的網(wǎng)絡(luò)基本信息打到屏

49、幕上int i,j;printf("城市總數(shù):%dt", G.vexnum);printf("網(wǎng)絡(luò)條數(shù):%dn", G.arcnum);printf("城市名稱:tn");for(i=0; i<G.vexnum; i+)/printf("%s_",G.vexsi);std:cout<<Hometowni.cityNam;printf("n");printf("各個(gè)城市間的距離:n");printf("n");printf("n");for(i=0;i<G.vexnum;+i)for(j=0;j&l