城通信网络建设系统

1、数据结构课程设计题目：城市通信网络建设系统班级:*姓名:*指导教师:AAAAAAAAA完成日期：2015年6月13日1 .需求分析1.1 问题描述通信设施的安全保障是安全生产管理工作的一项重要内容。随着通信网络的不断扩大和各种先进的通信方式日益增多相应的通信设施也在快速扩展，在不同的环境、不同的地域受到各种客观条件的影响和破坏(包括自然因素和人为因素)以及通信设施在使用过程中的老化都会对全程全网的通信质量造成不同程度的影响。因此，采用通信设施安全保障计算机管理系统实现全区通信设施的集中管理，对保障通信设施安全，提高维护工作效率，及时发现与处理隐患问题，增强抵抗灾害能力，特别是在实现管理工作的系

2、统化、正规化、规范化方面是非常必要的。如何在最小的经济条件下达到利益最大化，是所有公司、企业已经政府部门一直所探讨和解决的问题。对于城市通信管理系统来说，若要在n个城市之间建设通信网络，只需要架设n-1条通信线路即可，建立最小生成树即能实现以最低的经济代价建设这个通信网。1.2 基本任务通过用户调查分析及实际需求，系统需要实现如下基本任务：(1)在纸上模拟设计n个城市的网络平面图，城市数不少于20个，相同的的城市数不少于2(n-1),顶点表示各城市，边表示城市间的距离；(2)编写算法，求解最小代价通信网络；(3)输出该通信网络中各边及其权值；n个城市间的线路连接属于图的结构，要构建最经济的通信

3、网络，即是构建图的生成树。把城市间的线路关系看成是图。城市间的距离即是图的权值。利用prim算法或kruskal算法即可求出最小生成树。2 .概要设计为了完成需求分析的基本任务，主要从以下3个方面进行设计：2.1 主界面设计为了使程序界面更加友好，建立了interface函数和choice函数，即欢迎界面以及实现用户可以按数字键选择相应的功能。欢迎界面如下图:CAUwrc;while(c)switch(c)case1:system(cls);system(color1b);printf(n);printf(ntt*欢迎使用*);Welcom_to_Use);printf(n*);printf(

4、n);printf(n);printf(n);G=SaveGraph(G);system(cls);interface();/system(PAUSE);std:cinc;continue;case2:system(cls);system(color1c);printf(n);printf(ntt*欢迎使用*);printf(nWelcom_to_Use);printf(n*printf(n*);printf(n);printf(ttt下面显示的是通信网络的基本信息n);printf(n);G=SaveGraph(G);G=print(G);printf(nttt按任意键返回n);c=getc

5、har();c=getchar();system(cls);interface();/system(PAUSE);std:cinc;continue;case 3:system(cls);system(color1e);欢迎使用*);Welcom_to_Use);printf(n);printf(ntt*printf(nprintf(n*);printf(n);printf(n);printf(n);G=SaveGraph(G);prim(G,G.vexs0);printf(tt*结果存入KruskalResult.dat中，按任意键返回*n);c=getchar();c=getchar();

6、system(cls);interface();system(PAUSE);std:cinc;continue;case 4:system(cls);system(color1d);欢迎使用*);Welcom_to_Use);printf(n);printf(ntt*printf(nprintf(n*);printf(n);printf(n);printf(n);G=SaveGraph(G);G=kruskal(G);printf(tt*结果存入PrimResult.dat中，按任意键返回*n);c=getchar();c=getchar();system(cls);interface();s

7、ystem(PAUSE);std:cinc;continue;case 5:return;)3.模块设计3.1 模块设计系统主要包含主程序模块和其它操作模块。其调用关系如下图所示。(l)CreateGraph(G);/创建图模块(2)SaveGraph(G);/存储图模块(3)Print(G);/输出图模块(4)Kruskal(G);/kruskal算法求最小生成树模块Kruskal算法的基本思想是：1 、若网络G的边数en1,则G即为所求的最小生成树，否则，一定有en-1.2 、将网络的e条边按权值自小到大顺序排列。3 、将网络G中的边都去掉，只留下n个孤立顶点作为初始的最小生成树T,再按边

8、的排放顺序逐个考察，若与当前E(T)中的边不构成圈，便将它加入到边集E(T),直至E(T)中边数满n-1为止。(5)Prim(G);/prim算法求最小生成树模块Prim算法是另一种求最小生成树的方法，它的基本思想是按权值局部最小逐次将顶点和边加入到T中，直至V(T)，黄n个顶点为止。Prim算法步骤为：1、设最小生成树T的V(T)和E(T)均为空。2、从顶点集V(G)中任取一顶点加到顶点集V(T)中。3、在与V(T)中各顶点相关的所有边中，取一条权值最小的边(Vi,Vj)，其中，Vi包含于V(T),Vj包含于V(T)。4、(Vi,Vj)加入到E(T)中，将顶点Vj加入到V(T)中。5、若V(

9、T)已满n个顶点，则算法终止，否则转步骤(3)。3.3系统模块之间的调用关系系统的5个子模块之间的主要调用关系如下图所示:系统采用邻接矩阵存储信息，定义如下：/图的数据结构typedefstructMGraph/建立图(MGraph()(memset(vexs,0,MAX_VERTEX_NUM);)VertexvexsMAX_VERTEX_NUM;/城市名称intAdjMatrixarcs;/网络条数intvexnum;/图的当前顶点数(城市总数)intarcnum;/图的当前弧数(网络总数)MGraph;/记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstructTemp/

10、辅助数组(Temp()(lowcost=0;Vertexadjvex;/当前点intlowcost;/权值closedgeMAX_VERTEX_NUM;typedefstructCityNumberCityNumber()memset(cityNam,0,1024);charcityNam1024;CityNum;CityNum*Hometown=newCityNum20;/若G中存在顶点u,则返回该顶点在图中位置；否则返回-1。#includeintLocateVex(MGraphG,Vertexu)inti;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)

11、=0)returni;return-1;4.2系统主要模块设计4.2.1 CreateGraph函数1)创建邻接矩阵以存储图的内容。4.2.2 )填充矩阵，即输入城市间网络的状况，以方便使用prim算法或kruskal算法求出最经济的架设方法。程序如下：/采用数组(邻接矩阵)表示法，构造无向网GoMGraphCreateGraph(MGraph&G)inti=0,j=0,k=0,w=0;Vertexva,vb;/路径的两个节点printf(nntt*建立城市间网络信息*);printf(请输入城市的总数：n);scanf(%d,&G.vexnum);printf(请输入城市间的网络数：n);s

12、canf(%d,&G.arcnum);printf(请输入d个城市的名称(%d个字符):n,G.vexnum);for(i=0;iG.vexnum;+i)/构造顶点向量scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i)/初始化邻接矩阵for(j=0;jG.vexnum;+j)G.arcsij=65535;/65535为无穷大printf(请输入d条网络的两个城市信息城市1和城市2的距离（以空格作为间隔）:n,G.arcnum）;/输入城市1城市2名称及其距离/定位权值位置对称for(k=0;kG.arcnum;+k)(scanf(%s%s%d,va,vb,&w);i

13、=LocateVex(G,va);j=LocateVex(G,vb);G.arcsij=G.arcsji=w;/returnG;4.2.3 SaveGraph函数1)为了避免每次都重复输入信息，用文件存储图的内容。2 )如果没有文件则建立文件，并把图的内容存储到文件中。3 )如果文件存在，则从文件中读取图的内容到内存，以便完成其他操作。程序如下：MGraphSaveGraph(MGraphG)/输入内容存储在smalltree.dat(inti,j;FILE*fp;fp=fopen(smalltree.dat,rt);if(fp=NULL)(G=CreateGraph(G);fp=fopen(

14、smalltree.dat,wt);fprintf(fp,%dn,G.vexnum);/存城市树fprintf(fp,%dn,G.arcnum);/存网络数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;/到它自己fprintf(fp,%s_%s_%dn,G.vexsi,G.vexsj,G.arcsij);else(fprintf(fp,%s_%s_%dn,G.vexsi,G.vexs

15、j,G.arcsij);rewind(fp);std:cout存储成功！。输入任意键返回.std:endl;charc=getchar();)else/从文件中读取网的信息存到内存中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);)charCit

16、yA1024;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;break;case4:intkeynum=4;break;case5:intkeynum=5;break;case6:intkeynum=6;break;case7:intkeynum=7;b

17、reak;case8:intkeynum=8;break;case9:intkeynum=9;break;)Lenth+=intkeynum*X;X=X*10;)G.arcsij=Lenth;printf(tt*读取成功.t*n);)fclose(fp);returnG;4.2.3 print函数Print函数完成输出功能，将内存中图的内容输出到屏幕上程序如下：MGraphprint(MGraphG)/将输入的网络基本信息打到屏幕上inti,j;printf(城市总数：dt,G.vexnum);printf(网络条数：dn,G.arcnum);printf(城市名称：tn);for(i=0;i

18、G.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.vexsj+G.vexnum,G.arcsij);std:cout输入任意键返回.std:endl;charc=getchar();returnG;4.2.4 kruskal函数用kruskal算法求出最小生成树，即

19、最经济的假设方案程序如下：MGraphkruskal(MGraphG)/结果存储在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;printf(最短网络路径为：n);while(kG.vexnum-1)(for(i=0;iG.vexnum;+i)/从G.arcsij中找到权值最小的for(j=i+1;jG.vexnum;+j)if(G.arcsijmin)(min=

20、G.arcsij;/min中存最小权值a=i;b=j;if(seta!=setb)/如果a和b值不同则输出(printf(%s-%st距离:dn,G.vexsa,G.vexsb,G.arcsab);输出生成树各边fprintf(ffp,%s-%sn,G.vexsa,G.vexsb);k+;for(i=0;iG.vexnum;i+)/输出后变成相同值，下次将不会输出if(seti=setb)seti=seta;min=G.arcsab=G.arcsba=65535;输出过的权值变为最大值rewind(ffp);fclose(ffp);returnG;4.2.5prim函数用prim算法求出最小生

21、成树，即最经济的假设方案程序如下：/用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边voidprim(MGraphG,Vertexu)/inti,j,k=0;closedgeclose;FILE*fpp;fpp=fopen(PrimResult.dat,wt);k=LocateVex(G,u);for(j=0;jG.vexnum;+j)/strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;结果存储在PrimResult.dat辅助数组初始化)closek.lowcost=0;/printf(最短网络路径为for(i=1;iG.vex

22、num;+i)k=minimum(G,close);/初始,U=u:n);选择其余G.vexnum-1个顶点求出T的下一个结点：第K顶点printf(%s-%s)n,closek.adjvex,G.vexsk);fprintf(fpp,%s-%sn,closek.adjvex,G.vexsk);/closek.lowcost=0;/第K顶点并入U集for(j=0;jG.vexnum;+j)if(G.arcskjclosej.lowcost)/strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp)

23、;输出生成树的边新顶点并入U集后重新选择最小边5 .调试分析系统主界面运行如图1所示。各子功能测试运行结果如下运行程序，出现欢迎界面，见下图：_C:UsersAdrri4nirfltorDktcpl;可.。算。S小生防树的应用信网落履逸回墨ttAdcBy”：JereLonl保皿W出鲁由退一.二屏可径明想一住军手翻更储存名金币中5.1城市间网络信息的建立Welcon_to_Use*建立城市间网络信息*请输入城市的总数:多输入城市间的网络数;请输入5个城市的名称TnH耳ZJ7-Z5B-B-B-B-B二3mrlmrlmrlmrlmrl51.-TlALAlA-l-A5*1za124-b0flu-0nu

24、0离离离离离离离离离离离离离离离离离离离离离离III巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨巨隹sssssssssssssssssssssS音U意键返回6 .用户使用说明1、运行程序，出现欢迎界面；2、按1进入输入系统，如果文件没有存储城市网络内容，则由用户从键盘读入，读入后自动保存到文件中，按任意键即可返回欢迎界面；3、如果文件内已经存储了城市网络内容，则显示文件已保存到文件中，按任意键返回；4、输入2可以在屏幕上输出存储在文件内的城市间网络信息，显示完毕后按任意键可返回欢迎见面；5、按3和4分别可实现kruskal算法和prim算法求出最小生成树，即最低经济代价建设通信网络（距离最短的最

25、经济），显示完毕后按任意键返回欢迎界面；6、按5退出程序。7 .参考文献数据结构理论与实践杨永斌（核心算法prim算法以及kruskal算法来源于此）数据结构（C语言）实践教程胡元义数据结构严蔚敏、吴伟民VisualC+课程设计案例精选与编程指导陈清华、朱红8 .对所设计的软件进行自我评价，如创新点、未解决的问题等情况说明：1、对图的逻辑结构及存储结构有了更深刻的认识；2、对prim算法和kruskal算法亦有了更深刻的认识；3、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力，深入了解了模块化的程序设计步骤；4、kruskal算法应该用堆排序然后再找路径，但未能实现；5、输入

26、方面如果没有将网络信息存入文件，由键盘输入信息时，如果手误输错了无法更改，只能重新输入，而且如果输入中文，最后显示时会出现乱码，只能用英文输入；6、kruskal算法的实现仍有问题，结果存在错误，而且只能实行到第三步，到第四步时会出现程序关闭的提醒；9、程序源代码：#include#include#include#defineMAX_VERTEX_NUM20最大顶点个数#defineMAX_NAME3/顶点字符串的最大长度+1typedefintintAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedefcharVertexMAX_NAME;邻接矩阵的数据结

27、构/图的数据结构typedefstructMGraph/建立图MGraph()memset(vexs,0,MAX_VERTEX_NUM);VertexvexsMAX_VERTEX_NUM;/城市名称intAdjMatrixarcs;/网络条数intvexnum;/图的当前顶点数(城市总数)intarcnum;/图的当前弧数(网络总数)MGraph;/记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstructTemp/辅助数组Temp()lowcost=0;Vertexadjvex;/当前点intlowcost;/权值closedgeMAX_VERTEX_NUM;typedef

28、structCityNumberCityNumber()memset(cityNam,0,1024);charcityNam1024;CityNum;CityNum*Hometown=newCityNum20;/若G中存在顶点u,则返回该顶点在图中位置；否则返回-1。#includeintLocateVex(MGraphG,Vertexu)inti;for(i=0;iG.vexnum;+i)if(strcmp(u,G.vexsi)=0)returni;return-1;/采用数组(邻接矩阵)表示法，构造无向网GoMGraphCreateGraph(MGraph&G)inti=0,j=0,k=0

29、,w=0;Vertexva,vb;/路径的两个节点printf(nntt*建立城市间网络信息*);printf(请输入城市的总数：n);scanf(%d,&G.vexnum);printf(请输入城市间的网络数：n);scanf(%d,&G.arcnum);printf(请输入d个城市的名称(%d个字符):n,G.vexnum);for(i=0;iG.vexnum;+i)/构造顶点向量scanf(%s,G.vexsi);for(i=0;iG.vexnum;+i)/初始化邻接矩阵for(j=0;jG.vexnum;+j)G.arcsij=65535;/65535为无穷大printf(请输入d条网

30、络的两个城市信息城市1和城市2的距离(以空格作为间隔):n,G.arcnum);for(k=0;kG.arcnum;+k)scanf(%s%s%d,va,vb,&w);/输入城市1城市2名称及其距离i=LocateVex(G,va);/定位权值位置j=LocateVex(G,vb);G.arcsij=G.arcsji=w;/对称returnG;MGraphSaveGraph(MGraphG)/输入内容存储在smalltree.datinti,j;FILE*fp;fp=fopen(smalltree.dat,rt);if(fp=NULL)(G=CreateGraph(G);fp=fopen(sm

31、alltree.dat,wt);fprintf(fp,%dn,G.vexnum);/存城市树fprintf(fp,%dn,G.arcnum);存网络数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.vex

32、si,G.vexsj,rewind(fp);std:cout存储成功！。输入任意键返回.std:endl;charc=getchar();else/从文件中读取网的信息存到内存中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);charCityA1

33、024;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;break;case4:intkeynum=4;break;case5:intkeynum=5;break;case6:intkeynum=6;break;case7:intkeynum=7;break;

34、case8:intkeynum=8;break;case9:intkeynum=9;break;Lenth+=intkeynum*X;X=X*10;G.arcsij=Lenth;printf(tt*读取成功t*n);fclose(fp);将输入的网络基本信息打到屏幕上returnG;MGraphprint(MGraphG)/inti,j;printf(城市总数：dt,G.vexnum);printf(网络条数：dn,G.arcnum);printf(城市名称：tn);for(i=0;iG.vexnum;i+)/printf(%s_,G.vexsi);std:coutHometowni.city

35、Nam;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.vexsj+G.vexnum,G.arcsij);std:cout输入任意键返回.std:endl;charc=getchar();returnG;MGraphkruskal(MGraphG)/结果存储在KruskalResult.datintsetMAX_VERTEX_NUM,i,j;intk=0,a=0,b=0,min=G.

36、arcsab;FILE*ffp;ffp=fopen(KruskaiResult.dat,wt);for(i=0;iG.vexnum;i+)seti=i;printf(最短网络路径为:n);while(kG.vexnum-1)for(i=0;iG.vexnum;+i)/从G.arcsij中找到权值最小的for(j=i+1;jG.vexnum;+j)if(G.arcsijmin)min=G.arcsij;/min中存最小权值a=i;b=j;if(seta!=setb)/如果a和b值不同则输出printf(%s-%st距离:dn,G.vexsa,G.vexsb,G.arcsab);输出生成树各边fp

37、rintf(ffp,%s-%sn,G.vexsa,G.vexsb);k+;for(i=0;iG.vexnum;i+)/输出后变成相同值，下次将不会输出if(seti=setb)seti=seta;输出过的权值变为最大值min=G.arcsab=G.arcsba=65535;/)rewind(ffp);fclose(ffp);returnG;)/求closedge结构体中lowcost的最小正值intminimum(MGraphG,closedgeclose)inti=0,j,k,min;while(!closei.lowcost)i+;min=closei.lowcost;/第一个不为0的值k=i;for(j=i+1;j0&minclosej.lowcost)min=closej.lowcost;k=j;)returnk;)/用普里姆算法从第u个顶点出发构造网G的最小生成树输出T的各条边voidprim(MGraphG,Vertexu)/结果存储在PrimResult.dat中inti,j,k=0;closedgeclose;FILE*fpp;fpp=fop