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

数据结构课程设计题目：城市通信网络建设系统班级：*姓名：*学号：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函数：使用户更清晰看到程序的主体，使得程序界面更为直观。程序如下： void interface() /初始界面 printf(" _n");printf(" 最小生成树的应用n");printf(" 通信网络建设问题n");printf(" MadeBy董卓琴 Version1.0n");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(" ttt请输入您要选择的选项(1-5):n"); （2） choice函数：为用户提供了方便，用户可以通过按数字键来选择相应的功能。程序如下： void choice() /控制选项函数MGraph G = MGraph();int c;interface();std:cin>>c;while(c)switch(c)case 1:system("cls");system("color 1b");printf(" n");printf(" ntt*欢迎使用*");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 1c");printf(" n");printf(" ntt*欢迎使用*");printf(" n_Welcom_to_Use");printf("n*_*");printf(" n");printf(" ttt下面显示的是通信网络的基本信息n");printf(" n");G=SaveGraph(G);G=print(G);printf(" nttt按任意键返回n");c=getchar();/c=getchar();system("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(" n");printf(" n");G=SaveGraph(G);prim(G,G.vexs0);printf(" tt*结果存入KruskalResult.dat中，按任意键返回*n");c=getchar();c=getchar();system("cls");interface();system("PAUSE");std:cin>>c;continue;case 4:system("cls");system("color 1d");printf(" n");printf(" ntt*欢迎使用*");printf(" n_Welcom_to_Use");printf("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();system("PAUSE");std:cin>>c;continue;case 5:return; 3模块设计3.1 模块设计系统主要包含主程序模块和其它操作模块。其调用关系如下图所示。choice函数interface函数开始 3.2 系统子模块及其功能设计本系统共设计了5个子模块，各程序的函数名及功能说明如下：(1) CreateGraph(G); /创建图模块(2) SaveGraph(G); /存储图模块(3) Print(G); /输出图模块(4) Kruskal(G); /kruskal算法求最小生成树模块 Kruskal算法的基本思想是： 1、若网络G的边数en1,则G即为所求的最小生成树，否则，一定有e>n-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个子模块之间的主要调用关系如下图所示：开始SaveGraph函数将图存储到文件Print函数输出网络信息Kruskal函数算出最小生成树Prim函数算出最小生成树CreateGraph函数建立网络信息SaveGraph函数将图存储到文件中SaveGraph函数将图存储到文件SaveGraph函数将图存储到文件结束Choice函数选择相应功能Interface函数显示菜单，等待选择 4详细设计 4.1 数据结构设计 系统采用邻接矩阵存储信息,定义如下: / 图的数据结构typedef struct MGraph /建立图MGraph()memset(vexs, 0, MAX_VERTEX_NUM);Vertex vexsMAX_VERTEX_NUM;/ 城市名称intAdjMatrix arcs;/ 网络条数int vexnum; / 图的当前顶点数(城市总数)int arcnum; / 图的当前弧数(网络总数) MGraph;/ 记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef struct Temp /辅助数组Temp()lowcost = 0;Vertex adjvex; /当前点int lowcost;/权值closedgeMAX_VERTEX_NUM;typedef struct CityNumberCityNumber()memset(cityNam, 0, 1024);char cityNam1024;CityNum;CityNum* Hometown = new CityNum20;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-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; 4.2 系统主要模块设计 4.2.1 CreateGraph函数 1）创建邻接矩阵以存储图的内容。 2）填充矩阵，即输入城市间网络的状况，以方便使用prim算法或kruskal算法求 出最经济的架设方法。 程序如下： / 采用数组(邻接矩阵)表示法,构造无向网G。 MGraph CreateGraph(MGraph &G)int i = 0, j = 0, k = 0, w = 0; Vertex va,vb; /路径的两个节点 printf("nntt*建立城市间网络信息*"); printf("请输入城市的总数:n"); scanf("%d",&G.vexnum ); printf("请输入城市间的网络数:n"); scanf("%d",&G.arcnum); printf("请输入%d个城市的名称(<%d个字符):n",G.vexnum); for(i=0;i<G.vexnum;+i) / 构造顶点向量 scanf("%s",G.vexsi); for(i=0;i<G.vexnum;+i) / 初始化邻接矩阵 for(j=0;j<G.vexnum;+j) G.arcsij=65535; / 65535为无穷大 printf("请输入%d条网络的两个城市信息城市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);/定位权值位置 j=LocateVex( G, vb); G.arcsij=G.arcsji=w; /对称 return G; 4.2.2 SaveGraph函数1）为了避免每次都重复输入信息，用文件存储图的内容。 2）如果没有文件则建立文件，并把图的内容存储到文件中。 3）如果文件存在，则从文件中读取图的内容到内存，以便完成其他操作。程序如下： MGraph SaveGraph(MGraph G) /输入内容存储在smalltree.dat int 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); /存网络数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; /到它自己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 /从文件中读取网的信息存到内存中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, 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.arcnum;+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+;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':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':intkeynum = 9;break;Lenth += intkeynum*X;X = X*10;G.arcsij = Lenth;printf("tt*读取成功.t*n");fclose(fp);return G; 4.2.3 print函数Print函数完成输出功能，将内存中图的内容输出到屏幕上程序如下：MGraph print(MGraph G)/将输入的网络基本信息打到屏幕上int i,j;printf("城市总数:%dt", G.vexnum);printf("网络条数:%dn", G.arcnum);printf("城市名称:tn");for(i=0; i<G.vexnum; i+)/printf("%s_",G.vexsi);std:cout<<Hometowni.cityNam;printf("n");printf("各个城市间的距离: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.vexsi+G.vexnum,G.vexsj+G.vexnum,G.arcsij);std:cout<<"输入任意键返回."<<std:endl;char c = getchar();return G; 4.2.4 kruskal函数用kruskal算法求出最小生成树，即最经济的假设方案程序如下：MGraph kruskal(MGraph G) /结果存储在KruskalResult.datint setMAX_VERTEX_NUM,i,j;int k=0,a=0,b=0,min=G.arcsab;FILE*ffp;ffp=fopen("KruskaiResult.dat","wt");for(i=0;i<G.vexnum;i+)seti=i;printf("最短网络路径为:n");while(k<G.vexnum-1)for(i=0;i<G.vexnum;+i) /从G.arcsij中找到权值最小的for(j=i+1;j<G.vexnum;+j)if(G.arcsij<min)min=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;i<G.vexnum;i+) /输出后变成相同值，下次将不会输出if(seti=setb)seti=seta; min=G.arcsab=G.arcsba=65535; /输出过的权值变为最大值rewind(ffp);fclose(ffp);return G; 4.2.5 prim函数用prim算法求出最小生成树，即最经济的假设方案程序如下：/ 用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边void prim(MGraph G,Vertex u) /结果存储在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) / 辅助数组初始化 strcpy(closej.adjvex,u);closej.lowcost=G.arcskj;closek.lowcost=0; / 初始,U=u printf("最短网络路径为:n");for(i=1;i<G.vexnum;+i) / 选择其余G.vexnum-1个顶点 k=minimum(G,close); / 求出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;j<G.vexnum;+j)if(G.arcskj<closej.lowcost) / 新顶点并入U集后重新选择最小边strcpy(closej.adjvex,G.vexsk);closej.lowcost=G.arcskj;rewind(fpp);fclose(fpp);5调试分析系统主界面运行如图1所示。各子功能测试运行结果如下:运行程序，出现欢迎界面，见下图：5.1 城市间网络信息的建立5.2显示通信网络的基本信息 5.3 查询最短网络路径 6用户使用说明 1、运行程序，出现欢迎界面； 2、按1进入输入系统，如果文件没有存储城市网络内容，则由用户从键盘读入，读入后自动保存到文件中，按任意键即可返回欢迎界面； 3、如果文件内已经存储了城市网络内容，则显示文件已保存到文件中，按任意键返回； 4、输入2可以在屏幕上输出存储在文件内的城市间网络信息，显示完毕后按任意键可返 回欢迎见面； 5、按3和4分别可实现kruskal算法和prim算法求出最小生成树，即最低经济代价建设通信网络（距离最短的最经济），显示完毕后按任意键返回欢迎界面； 6、按5退出程序。7参考文献 数据结构理论与实践 杨永斌 （核心算法prim算法以及kruskal算法来源于此） 数据结构（C语言）实践教程 胡元义 数据结构 严蔚敏、吴伟民 Visual C+课程设计案例精选与编程指导 陈清华、朱红8 对所设计的软件进行自我评价，如创新点、未解决的问题等情况说明： 1、对图的逻辑结构及存储结构有了更深刻的认识； 2、对prim算法和kruskal算法亦有了更深刻的认识； 3、了解并掌握数据结构与算法的设计方法，具备初步的独立分析和设计能力，深入了解了模块化的程序设计步骤； 4、kruskal算法应该用堆排序然后再找路径，但未能实现； 5、输入方面如果没有将网络信息存入文件，由键盘输入信息时，如果手误输错了无法更改，只能重新输入，而且如果输入中文，最后显示时会出现乱码，只能用英文输入； 6、kruskal算法的实现仍有问题，结果存在错误，而且只能实行到第三步，到第四步时会出现程序关闭的提醒；9、程序源代码： #include<stdlib.h>#include<string.h>#include <iostream>#define MAX_VERTEX_NUM20/ 最大顶点个数#define MAX_NAME3 / 顶点字符串的最大长度+1 typedef int intAdjMatrixMAX_VERTEX_NUMMAX_VERTEX_NUM;typedef char VertexMAX_NAME;/ 邻接矩阵的数据结构/ 图的数据结构typedef struct MGraph /建立图MGraph()memset(vexs, 0, MAX_VERTEX_NUM);Vertex vexsMAX_VERTEX_NUM;/ 城市名称intAdjMatrix arcs;/ 网络条数int vexnum; / 图的当前顶点数(城市总数)int arcnum; / 图的当前弧数(网络总数) MGraph;/ 记录从顶点集U到V-U的代价最小的边的辅助数组定义typedef struct Temp /辅助数组Temp()lowcost = 0;Vertex adjvex; /当前点int lowcost;/权值closedgeMAX_VERTEX_NUM;typedef struct CityNumberCityNumber()memset(cityNam, 0, 1024);char cityNam1024;CityNum;CityNum* Hometown = new CityNum20;/ 若G中存在顶点u,则返回该顶点在图中位置;否则返回-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;/ 采用数组(邻接矩阵)表示法,构造无向网G。MGraph CreateGraph(MGraph &G)int i = 0, j = 0, k = 0, w = 0;Vertex va,vb; /路径的两个节点printf("nntt*建立城市间网络信息*");printf("请输入城市的总数:n");scanf("%d",&G.vexnum ); printf("请输入城市间的网络数:n");scanf("%d",&G.arcnum); printf("请输入%d个城市的名称(<%d个字符):n",G.vexnum);for(i=0;i<G.vexnum;+i) / 构造顶点向量 scanf("%s",G.vexsi);for(i=0;i<G.vexnum;+i) / 初始化邻接矩阵 for(j=0;j<G.vexnum;+j)G.arcsij=65535; / 65535为无穷大 printf("请输入%d条网络的两个城市信息城市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);/定位权值位置j=LocateV