城市通信网络建设系统

整理文档很辛苦,赏杯茶钱您下走!

免费阅读已结束,点击下载阅读编辑剩下 ...

阅读已结束,您可以下载文档离线阅读编辑

资源描述

..《数据结构》课程设计题目:城市通信网络建设系统班级:********姓名:********学号:1111111111指导教师:^^^^^^^^^完成日期:2015年6月13日..1.需求分析1.1问题描述通信设施的安全保障是安全生产管理工作的一项重要内容。随着通信网络的不断扩大和各种先进的通信方式日益增多相应的通信设施也在快速扩展,在不同的环境、不同的地域受到各种客观条件的影响和破坏(包括自然因素和人为因素)以及通信设施在使用过程中的老化都会对全程全网的通信质量造成不同程度的影响。因此,采用通信设施安全保障计算机管理系统实现全区通信设施的集中管理,对保障通信设施安全,提高维护工作效率,及时发现与处理隐患问题,增强抵抗灾害能力,特别是在实现管理工作的系统化、正规化、规范化方面是非常必要的。如何在最小的经济条件下达到利益最大化,是所有公司、企业已经政府部门一直所探讨和解决的问题。对于城市通信管理系统来说,若要在n个城市之间建设通信网络,只需要架设n-1条通信线路即可,建立最小生成树即能实现以最低的经济代价建设这个通信网。1.2基本任务通过用户调查分析及实际需求,系统需要实现如下基本任务:(1)在纸上模拟设计n个城市的网络平面图,城市数不少于20个,相同的的城市数不少于2(n-1),顶点表示各城市,边表示城市间的距离;(2)编写算法,求解最小代价通信网络;(3)输出该通信网络中各边及其权值;n个城市间的线路连接属于图的结构,要构建最经济的通信网络,即是构建图的生成树。把城市间的线路关系看成是图。城市间的距离即是图的权值。利用prim算法或kruskal算法即可求出最小生成树。2.概要设计为了完成需求分析的基本任务,主要从以下3个方面进行设计:2.1主界面设计为了使程序界面更加友好,建立了interface函数和choice函数,即欢迎界面以及实现用户可以按数字键选择相应的功能。欢迎界面如下图:..2.2数据结构设计若要在n个城市之间建设通信网络,只需要架设n-1条通信线路即可。所以,将一个现实的经济问题,转变为一个求最小生成树的问题。本系统软件采用经典算法prim算法和kruskal算法实现求最小生成树,从而获取最经济的通信路径。2.3系统功能设计系统建立了interface函数和choice函数,其功能如下:(1)interface函数:使用户更清晰看到程序的主体,使得程序界面更为直观。程序如下:voidinterface()//初始界面{printf(____________________________________________\n);printf(…………最小生成树的应用…………\n);printf(…………通信网络建设问题………\n);printf(…………Made…By…董卓琴Version1.0\n);printf(_______________________________________________________\n);printf(\n);printf(\n);printf(___________________________________________________________\n;printf(\n);printf(___________1.输入通信网络基本信息并将信息存储到文件中\n);printf(___________2.将网络基本信息显示到屏幕上\n);printf(___________3.用kruskal算法算出最短路径,并将结果存储到文件中\n);printf(___________4.用prim算法算出最短路径,并将结果存储到文件中\n);printf(___________5.退出\n);printf(\n);printf(\n);printf(\t\t\t请输入您要选择的选项(1-5):\n);}(2)choice函数:为用户提供了方便,用户可以通过按数字键来选择相应的功能。程序如下:voidchoice()//控制选项函数{MGraphG=MGraph();intc;interface();std::cinc;while(c){switch(c){case1:..system(cls);system(color1b);printf(\n);printf(\n\t\t*****************欢迎使用**********************);printf(\n__________________Welcom_to_Use);printf(\n********************************************_____________*************************************);printf(\n);printf(\n);printf(\n);G=SaveGraph(G);system(cls);interface();//system(PAUSE);std::cinc;continue;case2:system(cls);system(color1c);printf(\n);printf(\n\t\t*****************欢迎使用**********************);printf(\n__________________Welcom_to_Use);printf(\n********************************************_____________*************************************);printf(\n);printf(\t\t\t下面显示的是通信网络的基本信息\n);printf(\n);G=SaveGraph(G);G=print(G);printf(\n\t\t\t按任意键返回\n);c=getchar();//c=getchar();system(cls);interface();//system(PAUSE);std::cinc;continue;case3:system(cls);..system(color1e);printf(\n);printf(\n\t\t*****************欢迎使用**********************);printf(\n__________________Welcom_to_Use);printf(\n********************************************_____________*************************************);printf(\n);printf(\n);printf(\n);G=SaveGraph(G);prim(G,G.vexs[0]);printf(\t\t*******结果存入KruskalResult.dat中,按任意键返回***********\n);c=getchar();c=getchar();system(cls);interface();system(PAUSE);std::cinc;continue;case4:system(cls);system(color1d);printf(\n);printf(\n\t\t*****************欢迎使用**********************);printf(\n__________________Welcom_to_Use);printf(\n********************************************_____________*************************************);printf(\n);printf(\n);printf(\n);G=SaveGraph(G);G=kruskal(G);printf(\t\t*******结果存入PrimResult.dat中,按任意键返回***********\n);c=getchar();c=getchar();system(cls);interface();system(PAUSE);std::cinc;..continue;case5:return;}}}3.模块设计3.1模块设计系统主要包含主程序模块和其它操作模块。其调用关系如下图所示。3.2系统子模块及其功能设计本系统共设计了5个子模块,各程序的函数名及功能说明如下:(1)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,再按边的排放顺序逐个考察,若与当前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(T)已满n个顶点,则算法终止,否则转步骤(3)。3.3系统模块之间的调用关系系统的5个子模块之间的主要调用关系如下图所示:开始interface函数choice函数..4.详细设计4.1数据结构设计系统采用邻接矩阵存储信息,定义如下://图的数据结构typedefstructMGraph//建立图{MGraph(){memset(vexs,0,MAX_VERTEX_NUM);}Vertexvexs[MAX_VERTEX_NUM];//城市名称intAdjMatrixarcs;//网络条数intvexnum;//图的当前顶点数(城市总数)intarcnum;//图的当前弧数(网络总数)}MGraph;//记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstructTemp//辅助数组{Temp(){lowcost=0;}Vertexadjvex;//当前点开始Interface函数显示菜单,等待选择Choice函数选择相应功能CreateGraph函数建立网络信息SaveGraph函数将图存储到文件中SaveGraph函数将图存储到文件SaveGraph函数将图存储到文件结束Prim函数算出最小生成树Print函数输出网络信息Kruskal函数算出最小生成树SaveGraph函数将图存储到文件..intlowcost;//权值}closedge[MAX_VERTEX_NUM];typedefstructCityNumber{CityNumber(){memset(cityNam,0,1024);}charcityNam[1024];}CityNum;CityNum*Hometown=newCityNum[20];//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。#includestdio.hintLocateVex(MGraphG,Vertexu){inti;for(i=0;iG.vexnum;++i)if(strcmp(u,G.vexs[i])==0)returni;return-1;}4.2系统主要模块设计4.2.1CreateGraph函数1)创建邻接矩阵以存储图的内容。2)填充

1 / 28
下载文档,编辑使用

©2015-2020 m.777doc.com 三七文档.

备案号:鲁ICP备2024069028号-1 客服联系 QQ:2149211541

×
保存成功