城市通信网络建系统.doc

《数据结构》课程设计 题目：城市通信网络建设系统 班级：******** 姓名：******** 学号：1111111111 指导教师：^^^^^^^^^ 完成日期：2015年6月13日 1．需求分析 1.1 问题描述 通信设施的安全保障是安全生产管理工作的一项重要内容。随着通信网络的不断扩大和各种先进的通信方式日益增多相应的通信设施也在快速扩展,在不同的环境、不同的地域受到各种客观条件的影响和破坏(包括自然因素和人为因素)以及通信设施在使用过程中的老化都会对全程全网的通信质量造成不同程度的影响。因此,采用通信设施安全保障计算机管理系统实现全区通信设施的集中管理,对保障通信设施安全,提高维护工作效率,及时发现与处理隐患问题,增强抵抗灾害能力,特别是在实现管理工作的系统化、正规化、规范化方面是非常必要的。 3.2 系统子模块及其功能设计 本系统共设计了5个子模块，各程序的函数名及功能说明如下： CreateGraph(G); //创建图模块 SaveGraph(G); //存储图模块 Print(G); //输出图模块 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个子模块之间的主要调用关系如下图所示： 4．详细设计 4.1 数据结构设计 系统采用邻接矩阵存储信息,定义如下: // 图的数据结构 typedef struct MGraph //建立图 { MGraph() { memset(vexs, 0, MAX_VERTEX_NUM); } Vertex vexs[MAX_VERTEX_NUM];// 城市名称 intAdjMatrix arcs;// 网络条数 int vexnum; // 图的当前顶点数(城市总数) int arcnum; // 图的当前弧数(网络总数) } MGraph; // 记录从顶点集U到V-U的代价最小的边的辅助数组定义 typedef struct Temp //辅助数组 { Temp() { lowcost = 0; } Vertex adjvex; //当前点 int lowcost; //权值 }closedge[MAX_VERTEX_NUM]; typedef struct CityNumber { CityNumber() { memset(cityNam, 0, 1024); } char cityNam[1024]; }CityNum; CityNum* Hometown = new CityNum[20]; // 若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。 #includestdio.h int LocateVex(MGraph G,Vertex u) { int i; for(i = 0; i G.vexnum; ++i) if( strcmp(u, G.vexs[i]) == 0) return i; return -1; } 4.2 系统主要模块设计 4.2.1 CreateGraph函数 1）创建邻接矩阵以存储图的内容。 2）填充矩阵，即输入城市间网络的状况，以方便使用prim算法或kruskal