城市通信网络建设系统方案.docx

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

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

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

4、e 3:system(cls);case 4:*prin tf( n);prin tf( n);prin tf( n);G=SaveGraph(G); G=kruskal(G);结果存入 PrimResult.dat 中，按任意键返回prin tf( tt*n)c=getchar();c=getchar();system(cls); in terface(); system(PAUSE);std:ci nc;con ti nue;case 5: return;3 .模块设计3.1模块设计系统主要包含主程序模块和其它操作模块。其调用关系如下图所示。CreateGraph(G); / 创建图模块S

5、aveGraph(G); / 存储图模块(3)Pri nt(G); II 输出图模块(4)Kruskal(G); I/kruskal 算法求最小生成树模块Kruskal 算法的基本思想是：1、若网络G的边数enl,则G即为所求的最小生成树，否则，一定有 en-1.2、将网络的e条边按权值自小到大顺序排列。3、将网络G中的边都去掉，只留下 n个孤立顶点作为初始的最小生成树 T,再按边的排放顺序逐个考察，若与当前 E( T)中的边不构成圈，便将它加入到边集 E( T)，直至E( T)中边数满n-1为止。(5)Prim(G); I/prim 算法求最小生成树模块Prim 算法是另一种求最小生成树的方

6、法， 它的基本思想是按权值局部最小逐次将顶点和边加入到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 (T)已满n个顶点，则算法终止，否则转步骤( 3)。3.3 系统模块之间的调用关系系统的5个子模块之间的主要调用关系如下图所示：建立图系统采用邻接矩阵存储信息，

7、定义如下： / 图的数据结构typedef struct MGraph / MGraph()memset(vexs, 0, MAX_VERTEX_NUM);Vertex vexsMAX_VERTEX_NUM;/ 城市名称in tAdjMatrix arcs;/ int vexnum; /int arcnum; /网络条数图的当前顶点数（城市总数） 图的当前弧数（网络总数） MGraph;/记录从顶点集 U到V-U的代价最小的边的辅助数组定义 typedef struct Temp / 辅助数组Temp()lowcost = 0;Vertex adjvex; / 当前点int lowcost;

8、/ 权值closedgeMAX_VERTEX_NUM; typedef struct CityNumberCityNumber()memset(cityNam, 0, 1024);char cityNam1024;CityNum;CityNum* Hometow n = new CityNum20;/若G中存在顶点u,则返回该顶点在图中位置 ；否则返回-1。#in clude int LocateVex(MGraph G,Vertex u)int i;for(i = 0; i G.vex num; +i)if( strcmp(u, G.vexsi) = 0)return i;return -1

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

10、);scan f(%d, &G.arcnum);printf( 请输入d个城市的名称(%d个字符):n,G.vexnum);for(i=0;iG.vex nu m;+i) / scan f(%s,G.vexsi); for(i=0;iG.vex nu m;+i) / for(j=0;jG.vex nu m;+j) G.arcsij=65535; / 65535构造顶点向量初始化邻接矩阵为无穷大printf(” 请输入d条网络的两个城市信息城市 1和城市2的距离(以空格作为间隔):n,G.arcnum);for(k=0;kG.arc nu m;+k)scanf(%s %s %d,va,vb,&w

11、); /输入城市1城市2名称及其距离i=LocateVex( G, va); j=LocateVex( G, vb);/定位权值位置G.arcsij=G.arcsji=w; / 对称return G;4.2.2SaveGraph 函数1 ）为了避免每次都重复输入信息，用文件存储图的内容。2）如果没有文件则建立文件，并把图的内容存储到文件中。3）如果文件存在，则从文件中读取图的内容到内存，以便完成其他操作。 程序如下：MGraph SaveGraph（MGraph G） / 输入内容存储在 smalltree.datint i,j;FILE*fp;fp=fope n( smalltree.dat

12、,rt);if(fp=NULL)G=CreateGraph(G);fp=fope n( smalltree.dat,wt);fprin tf(fp,%dn,G.vex nu m); / 存城市树fprin tf(fp,%dn,G.arcnum); / 存网络数for(i=0;iG.vex nu m;+i)fprin tf(fp,%stn,G.vexsi); 存城市名称for(i=0;iG.vex nu m;+i) 存储邻接矩阵for(j=0;jG.vex num; +j)if(G.vexsi = G.vexsj)G.arcsij = 0; / 到它自己fprin tf(fp,%s_%s_%dn

13、,G.vexsi,G.vexsj, G.arcsij);elsefprin tf(fp,%s_%s_%dn,G.vexsi,G.vexsj, G.arcsij);rewi nd(fp);std:cout 存储成功！。输入任意键返回.std:endl;char c = getchar();else II从文件中读取网的信息存到内存中*正在读取文件中*fsca nf(fp,%dn, & G.vex num);fsca nf(fp,%din, & G.arcnum);char tempBuffer1024;memset(tempBuffer, 0, 1024);for(i=0; iG.vex num

14、; +i)fgets(tempBuffer, 1023, fp);strcpy(Hometow ni.cityNam,tempBuffer); char CityA1024;int Lenth = 0; memset(CityA, 0, 1024);for(i=0; iG.vex num; +i)for(j=0;j=0; n-)int in tke ynum = 0; switch(tempCityName n)case 0:in tke ynum = 0;break;case 1:in tke ynum = 1;break;case 2:in tke ynum = 2; break;case

15、 3:in tke ynum = 3;break;case 4:in tke ynum = 4; break;case 5:in tke ynum = 5; break;case 6:in tke ynum = 6; break;case 7:in tke ynum = 7; break;case 8:in tke ynum = 8;break;case 9:in tke ynum = 9;break;Lenth += in tke ynu m*X;X = X*10;G.arcsij = Le nth;prin tf(tt* fclose(fp); return G;4.2.3print 函数

16、Print函数完成输出功能，将内存中图的内容输出到屏幕上 程序如下：MGraph prin t(MGraph G) 将输入的网络基本信息打到屏幕上int i,j;printf(城市总数:%dt, G.vexnum);printf(网络条数：dn, G.arcnum);printf(城市名称:tn);for(i=0; iG.vex num; i+)/prin tf(%s_,G.vexsi);std:coutHometow ni.cityNam;prin tf(n);printf( 各个城市间的距离:n);prin tf(n);prin tf(n);for(i=0;iG.vex nu m;+i)f

17、or(j=0;jG.vex nu m;+j)printf(%s_%s_ 距离:%d 公里n,G.vexsi+G.vex nu m,G.vexsj+G.vex nu m,G.arcsij); std:cout输入任意键返回.std:endl; char c = getchar();return G;4.2.4kruskal 函数用kruskal算法求出最小生成树，即最经济的假设方案程序如下：MGraph kruskal(MGraph G) / 结果存储在 KruskalResult.datint setMAX_VERTEX_NUM,i,j;int k=O,a=O,b=O ,min=G.arcsa

18、b;FILE*ffp;ffp=fope n( KruskaiResult.dat,wt);for(i=0;iG.vex nu m;i+)seti=i;prin tf( 最短网络路径为:n);while(kG.vex nu m-1)for(i=0;iG.vexnum;+i)/ 从 G.arcsij 中找到权值最小的for(j=i+1;jG.vex nu m;+j)if(G.arcsijmi n)min=G.arcsij;/mi n 中存最小权值a=i;b=j;if(seta!=setb) / 如果a和b值不同则输出prin tf(%s-%st 距离:%dn,G.vexsa,G.vexsb,G.a

19、rcsab); 输出生成树各边fprin tf(ffp,%s-%sn,G.vexsa,G.vexsb);k+;for(i=0;iG.vex num;i+) / 输出后变成相同值，下次将不会输出if(se ti=setb)seti=seta;min=G.arcsab=G.arcsba=65535; / 输出过的权值变为最大值rewin d(ffp);fclose(ffp);return G;4.2.5prim 函数用prim算法求出最小生成树，即最经济的假设方案程序如下:/用普里姆算法从第 u个顶点出发构造网 G的最小生成树T,输出T的各条边int i,j,k=O;closedge close;

20、FILE*fpp;fpp=fope n(PrimResult.dat,wt); k=LocateVex(G,u);for(j=0;jG.vex nu m;+j) / 辅助数组初始化strcpy(closej.adjvex,u);closej .lo wcost=G.arcskj;初始,U=u:n);选择其余G.vexnum-1个顶点求出T的下一个结点：第 K顶点closek.lowcost=0; / prin tf( 最短网络路径为for(i=1;iG.vex nu m;+i) / k=mi nimu m(G,close); / prin tf(%s_%s)n,closek.adjvex,G.

21、vexsk);fprin tf(fpp,%s-%sn,closek.adjvex,G.vexsk); / 输出生成树的边closek.lowcost=0; / 第 K 顶点并入 U 集for(j=0;jG.vex nu m;+j)if(G.arcskjclosej.lowcost) / 新顶点并入U集后重新选择最小边strcpy(closej.adjvex,G.vexsk); closej.lowcost=G.arcskj;rewin d(fpp);fclose(fpp);5 调试分析系统主界面运行如图1所示。各子功能测试运行结果如下 运行程序，出现欢迎界面，见下图：Jerc ionl .0:

22、關曬+ +-*rtadepByppiJHSAffi选择的选项=5.1城市间网络信息的建立I C:;U se rsAd mi n i strato rDeskto pkcsj exe We lcom_to_Use*建立城市间网络信息 mu 请输入城市的总数:慎输入城市间的网络数：;青输入吕个城市的名称心0个字符：NJ UX SH SZ C2125468523256154296信输入疏网络的两个城市信息城市1和城市2的距离浪空格作为间隔:凹UXSH品匕5.2显示通信网络的基本信息F面显示的是通信网络的基本信息恪个城帀间的距离:I C:U5er5Ad mi n istratorDeskto pkcs

23、jj.exe意键返回5.3查询最短网络路径6用户使用说明1、 运行程序，出现欢迎界面；2、 按1进入输入系统，如果文件没有存储城市网络内容，则由用户从键盘读入，读入后 自动保存到文件中，按任意键即可返回欢迎界面；3、 如果文件内已经存储了城市网络内容，则显示文件已保存到文件中，按任意键返回；4、 输入2可以在屏幕上输出存储在文件内的城市间网络信息，显示完毕后按任意键可返 回欢迎见面；5、 按3和4分别可实现kruskal算法和prim算法求出最小生成树， 即最低经济代价建设 通信网络（距离最短的最经济），显示完毕后按任意键返回欢迎界面；6、 按5退出程序。7.参考文献数据结构理论与实践 杨永斌（核心算法prim算法以及kruskal算法来源于此）数据结构（C语言）实践教程 胡元义数据结构 严蔚敏、吴伟民Visual C+课程设计案例精选与编程指导 陈清华、朱红&对所设计的软件进行自我评价，如创新点、未解决的问题等情况说明：1、对图的逻辑结构及存储结构有了更深刻的认识；2、 对prim算法和kruskal算法亦有了更