当前位置:首页 >> 信息与通信 >>

城市通信网络建设系统


《数据结构》课程设计

题目:城市通信网络建设系统

班级:********

姓名:********

学号: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 函数,即欢迎界面以及实 现用户可以按数字键选择相应的功能。 欢迎界面如下图:

1

2.2 数据结构设计 若要在 n 个城市之间建设通信网络,只需要架设 n-1 条通信线路即可。所以,将一个现 实的经济问题,转变为一个求最小生成树的问题。本系统软件采用经典算法 prim 算法和 kruskal 算法实现求最小生成树,从而获取最经济的通信路径。 2.3 系统功能设计 系统建立了 interface 函数和 choice 函数,其功能如下: (1)interface 函数:使用户更清晰看到程序的主体,使得程序界面更为直观。程序 如下: void interface() //初始界面 { 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 函数:为用户提供了方便,用户可以通过按数字键来选择相应的功能。程 序如下: void choice() //控制选项函数 { MGraph G = MGraph(); int c; interface(); std::cin>>c; while(c) { switch(c) { case 1:
2

system("cls"); system("color 1b"); 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::cin>>c; continue; case 2: system("cls"); system("color 1c"); 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::cin>>c; continue; case 3: system("cls");
3

system("color 1e"); 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::cin>>c; continue; case 4: system("cls"); system("color 1d"); 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::cin>>c;
4

continue; case 5: return; } } }

3.模块设计 3.1 模块设计 系统主要包含主程序模块和其它操作模块。其调用关系如下图所示。

开始 interface 函数 3.2 系统子模块及其功能设计 choice 函数 本系统共设计了 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 个子模块之间的主要调用关系如下图所示:

5

开始

Interface 函数 显示菜单, 等待选择

Choice 函数 选择相应功能

结束

CreateGraph 函数 建立网络信息

SaveGraph 函数 将图存储到文件 中

SaveGraph 函数 将图存储到文 件

SaveGraph 函数 将图存储到文件

SaveGraph 函数 将图存储到文件

Print 函数 输出网络信息

Kruskal 函数 算出最小生成树

Prim 函数 算出最小生成树

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; //当前点
6

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。 #include<stdio.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 算法求 出最经济的架设方法。 程序如下: // 采用数组(邻接矩阵)表示法,构造无向网 G。 MGraph CreateGraph(MGraph &G) { int i = 0, j = 0, k = 0, w = 0; Vertex va,vb; //路径的两个节点 printf("\n\n\t\t*************建立城市间网络信息**********"); 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.vexs[i]); for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵 for(j=0;j<G.vexnum;++j) G.arcs[i][j]=65535; // 65535 为无穷大 printf("请输入%d 条网络的两个城市信息城市 1 和城市 2
7

的距离(以空格作为间隔): \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.arcs[i][j]=G.arcs[j][i]=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,"%d\n",G.vexnum); //存城市树 fprintf(fp,"%d\n",G.arcnum); //存网络数 for(i=0;i<G.vexnum;++i) fprintf(fp,"%s\t\n",G.vexs[i]);//存城市名称 for(i=0;i<G.vexnum;++i)//存储邻接矩阵 for(j=0;j<G.vexnum; ++j) if(G.vexs[i] == G.vexs[j]) { G.arcs[i][j] = 0; ///到它自己 fprintf(fp,"%s_%s_%d\n",G.vexs[i], G.vexs[j], G.arcs[i][j]); } else { fprintf(fp,"%s_%s_%d\n",G.vexs[i], G.vexs[j], G.arcs[i][j]); } rewind(fp);
8

std::cout<<"存储成功! 。 。 。输入任意键返回."<<std::endl; char c = getchar(); } else //从文件中读取网的信息存到内存中 { printf("\t\t*******正在读取文件中....***********\n"); fscanf(fp,"%d\n", &G.vexnum); fscanf(fp,"%d\n", &G.arcnum); char tempBuffer[1024]; memset(tempBuffer, 0, 1024); for(i=0; i<G.vexnum; ++i) { fgets(tempBuffer, 1023, fp); strcpy(Hometown[i].cityNam,tempBuffer); } char CityA[1024]; 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 tempCityName[1024]; memset(tempCityName, 0, 1024); while(CityA[n] != '_') { tempCityName[n] = CityA[n]; n++; } strcpy(G.vexs[i+G.vexnum], tempCityName); n++; memset(tempCityName, 0, 1024); int num = 0; while(CityA[n] != '_') { tempCityName[num] = CityA[n]; n++; num++; } strcpy(G.vexs[i+G.vexnum+1], tempCityName); int numint = 0; n++;
9

memset(tempCityName, 0, 1024); while(CityA[n] != '\0') { tempCityName[numint] = CityA[n]; n++; numint++; } int X = 1; Lenth = 0; for(n = numint-1; n>=0; n--) { int intkeynum = 0; switch(tempCityName[n]) { 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;
10

} Lenth += intkeynum*X; X = X*10; } G.arcs[i][j] = Lenth; } printf("\t\t*******读取成功...\t***********\n"); } fclose(fp); return G; }

4.2.3 print 函数 Print 函数完成输出功能,将内存中图的内容输出到屏幕上 程序如下: MGraph print(MGraph G)//将输入的网络基本信息打到屏幕上 { int i,j; printf("城市总数:%d\t", G.vexnum); printf("网络条数:%d\n", G.arcnum); printf("城市名称:\t\n"); for(i=0; i<G.vexnum; i++) { //printf("%s_",G.vexs[i]); std::cout<<Hometown[i].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.vexs[i+G.vexnum],G.vexs[j+G.vexnum],G.arcs[i][j]); std::cout<<"输入任意键返回."<<std::endl; char c = getchar(); return G; }

11

4.2.4 kruskal 函数 用 kruskal 算法求出最小生成树,即最经济的假设方案 程序如下: MGraph kruskal(MGraph G) //结果存储在 KruskalResult.dat { int set[MAX_VERTEX_NUM],i,j; int k=0,a=0,b=0,min=G.arcs[a][b]; FILE*ffp; ffp=fopen("KruskaiResult.dat","wt"); for(i=0;i<G.vexnum;i++) set[i]=i; printf("最短网络路径为:\n"); while(k<G.vexnum-1) { for(i=0;i<G.vexnum;++i) //从 G.arcs[i][j]中找到权值最小的 for(j=i+1;j<G.vexnum;++j) if(G.arcs[i][j]<min) { min=G.arcs[i][j];//min 中存最小权值 a=i; b=j; } if(set[a]!=set[b]) //如果 a 和 b 值不同则输出 { printf("%s--%s\t 距离:%d\n",G.vexs[a],G.vexs[b],G.arcs[a][b]);//输出生 成树各边 fprintf(ffp,"%s--%s\n",G.vexs[a],G.vexs[b]); k++; for(i=0;i<G.vexnum;i++) //输出后变成相同值,下次将不会输出 if(set[i]==set[b]) set[i]=set[a]; } min=G.arcs[a][b]=G.arcs[b][a]=65535; //输出过的权值变为最大值 } rewind(ffp); fclose(ffp); return G; }

12

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(close[j].adjvex,u); close[j].lowcost=G.arcs[k][j]; } close[k].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",close[k].adjvex,G.vexs[k]); fprintf(fpp,"%s--%s\n",close[k].adjvex,G.vexs[k]); // 输出生成树的边 close[k].lowcost=0; // 第 K 顶点并入 U 集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j]<close[j].lowcost) // 新顶点并入 U 集后重新选择最小边 { strcpy(close[j].adjvex,G.vexs[k]); close[j].lowcost=G.arcs[k][j]; } } rewind(fpp); fclose(fpp); }

5.调试分析 系统主界面运行如图 1 所示。各子功能测试运行结果如下: 运行程序,出现欢迎界面,见下图:

13

5.1 城市间网络信息的建立

14

5.2 显示通信网络的基本信息

15

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、输入方面如果没有将网络信息存入文件,由键盘输入信息时,如果手误输错了无法更
16

改,只能重新输入,而且如果输入中文,最后显示时会出现乱码,只能用英文输入; 6、kruskal 算法的实现仍有问题,结果存在错误,而且只能实行到第三步,到第四步时 会出现程序关闭的提醒; 9、程序源代码: #include<stdlib.h> #include<string.h> #include <iostream> #define MAX_VERTEX_NUM 20// 最大顶点个数 #define MAX_NAME 3 // 顶点字符串的最大长度+1 typedef int intAdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; typedef char Vertex[MAX_NAME];// 邻接矩阵的数据结构 // 图的数据结构 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];
17

// 若 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.vexs[i]) == 0) return i; return -1; } // 采用数组(邻接矩阵)表示法,构造无向网 G。 MGraph CreateGraph(MGraph &G) { int i = 0, j = 0, k = 0, w = 0; Vertex va,vb; //路径的两个节点 printf("\n\n\t\t*************建立城市间网络信息**********"); 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.vexs[i]); for(i=0;i<G.vexnum;++i) // 初始化邻接矩阵 for(j=0;j<G.vexnum;++j) G.arcs[i][j]=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.arcs[i][j]=G.arcs[j][i]=w; //对称 } return G; }

MGraph SaveGraph(MGraph G) //输入内容存储在 smalltree.dat { int i,j;
18

FILE*fp; fp=fopen("smalltree.dat","rt"); if(fp==NULL) { G=CreateGraph(G); fp=fopen("smalltree.dat","wt"); fprintf(fp,"%d\n",G.vexnum); //存城市树 fprintf(fp,"%d\n",G.arcnum); //存网络数 for(i=0;i<G.vexnum;++i) fprintf(fp,"%s\t\n",G.vexs[i]);//存城市名称 for(i=0;i<G.vexnum;++i)//存储邻接矩阵 for(j=0;j<G.vexnum; ++j) if(G.vexs[i] == G.vexs[j]) { G.arcs[i][j] = 0; ///到它自己 fprintf(fp,"%s_%s_%d\n",G.vexs[i], G.vexs[j], G.arcs[i][j]); } else { fprintf(fp,"%s_%s_%d\n",G.vexs[i], G.vexs[j], G.arcs[i][j]); } rewind(fp); std::cout<<"存储成功! 。 。 。输入任意键返回."<<std::endl; char c = getchar(); } else //从文件中读取网的信息存到内存中 { printf("\t\t*******正在读取文件中....***********\n"); fscanf(fp,"%d\n", &G.vexnum); fscanf(fp,"%d\n", &G.arcnum); char tempBuffer[1024]; memset(tempBuffer, 0, 1024); for(i=0; i<G.vexnum; ++i) { fgets(tempBuffer, 1023, fp); strcpy(Hometown[i].cityNam,tempBuffer); } char CityA[1024]; int Lenth = 0; memset(CityA, 0, 1024); for(i=0; i<G.vexnum; ++i) for(j=0;j<G.arcnum;++j) {
19

fscanf(fp, "%s", &CityA); int n = 0; char tempCityName[1024]; memset(tempCityName, 0, 1024); while(CityA[n] != '_') { tempCityName[n] = CityA[n]; n++; } strcpy(G.vexs[i+G.vexnum], tempCityName); n++; memset(tempCityName, 0, 1024); int num = 0; while(CityA[n] != '_') { tempCityName[num] = CityA[n]; n++; num++; } strcpy(G.vexs[i+G.vexnum+1], tempCityName); int numint = 0; n++; memset(tempCityName, 0, 1024); while(CityA[n] != '\0') { tempCityName[numint] = CityA[n]; n++; numint++; } int X = 1; Lenth = 0; for(n = numint-1; n>=0; n--) { int intkeynum = 0; switch(tempCityName[n]) { case '0': intkeynum = 0; break; case '1': intkeynum = 1; break; case '2': intkeynum = 2;
20

break; case '3': intkeynum break; case '4': intkeynum break; case '5': intkeynum break; case '6': intkeynum break; case '7': intkeynum break; case '8': intkeynum break; case '9': intkeynum break;

= 3;

= 4;

= 5;

= 6;

= 7;

= 8;

= 9;

} Lenth += intkeynum*X; X = X*10; } G.arcs[i][j] = Lenth; } printf("\t\t*******读取成功...\t***********\n"); } fclose(fp); return G; }MGraph print(MGraph G)//将输入的网络基本信息打到屏幕上 { int i,j; printf("城市总数:%d\t", G.vexnum); printf("网络条数:%d\n", G.arcnum); printf("城市名称:\t\n"); for(i=0; i<G.vexnum; i++) { //printf("%s_",G.vexs[i]); std::cout<<Hometown[i].cityNam; }
21

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.vexs[i+G.vexnum],G.vexs[j+G.vexnum],G.arcs[i][j]); std::cout<<"输入任意键返回."<<std::endl; char c = getchar(); return G; }

MGraph kruskal(MGraph G) //结果存储在 KruskalResult.dat { int set[MAX_VERTEX_NUM],i,j; int k=0,a=0,b=0,min=G.arcs[a][b]; FILE*ffp; ffp=fopen("KruskaiResult.dat","wt"); for(i=0;i<G.vexnum;i++) set[i]=i; printf("最短网络路径为:\n"); while(k<G.vexnum-1) { for(i=0;i<G.vexnum;++i) //从 G.arcs[i][j]中找到权值最小的 for(j=i+1;j<G.vexnum;++j) if(G.arcs[i][j]<min) { min=G.arcs[i][j];//min 中存最小权值 a=i; b=j; } if(set[a]!=set[b]) //如果 a 和 b 值不同则输出 { printf("%s--%s\t 距 离:%d\n",G.vexs[a],G.vexs[b],G.arcs[a][b]);//输出生成树各边 fprintf(ffp,"%s--%s\n",G.vexs[a],G.vexs[b]); k++; for(i=0;i<G.vexnum;i++) //输出后变成相同值,下次将不会输出 if(set[i]==set[b]) set[i]=set[a]; }
22

min=G.arcs[a][b]=G.arcs[b][a]=65535; //输出过的权值变为最大值 } rewind(ffp); fclose(ffp); return G; }

// 求 closedge 结构体中 lowcost 的最小正值 int minimum( MGraph G,closedge close) { int i=0,j,k,min; while(!close[i].lowcost) i++ ; min=close[i].lowcost; // 第一个不为 0 的值 k=i; for(j=i+1;j<G.vexnum;j++) if(close[j].lowcost>0&&min>close[j].lowcost) { min=close[j].lowcost; k=j; } return k; } // 用普里姆算法从第 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(close[j].adjvex,u); close[j].lowcost=G.arcs[k][j]; } close[k].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",close[k].adjvex,G.vexs[k]);
23

fprintf(fpp,"%s--%s\n",close[k].adjvex,G.vexs[k]); // 输出生成树的边 close[k].lowcost=0; // 第 K 顶点并入 U 集 for(j=0;j<G.vexnum;++j) if(G.arcs[k][j]<close[j].lowcost) // 新顶点并入 U 集后重新选择最小边 { strcpy(close[j].adjvex,G.vexs[k]); close[j].lowcost=G.arcs[k][j]; } } rewind(fpp); fclose(fpp); }

void interface() //初始界面 { 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"); } void choice() //控制选项函数 { MGraph G = MGraph(); int c; interface(); std::cin>>c; while(c)
24

{ switch(c) { case 1: system("cls"); system("color 1b"); 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::cin>>c; continue; case 2: system("cls"); system("color 1c"); 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::cin>>c;
25

continue; case 3: system("cls"); system("color 1e"); 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::cin>>c; continue; case 4: system("cls"); system("color 1d"); 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();
26

system("cls"); interface(); system("PAUSE"); std::cin>>c; continue; case 5: return; } } }

int main(void) { choice(); return 0; }

27


相关文章:
某城市商业银行网络系统规划与设计
3 第一章 需求分析 一、 某城市商业银行网络系统规划背景与设计需求某城市商业...在全市范围内建设一个商业银行专用通讯子网,一个多协议的数 据网络, 并在...
通信网络技术服务行业分析
通信设备供应商、 系统集成商和其他专业技术服 务提供商在通信运营商网络建设...意见指出: 加快高速宽带网络建设,加快推进全光纤网络城市和第四代移动通信( 4G)...
关于加快通信信息网络基础设施建设的意见
通信信息网络基础设施建设;着力实施“数字河南”、 “智慧中原”、 “无线城市”...系统集成等相关产业创新发展,促进信息服务、软件服务等新兴业态发展, 形成基于基础...
基于混合组网的城市配网通信网络研究与设计
伴随着城市配网自动化的发展,国内配网通信网络建设和发展在近年来取得了一 ...本文在分析配网自动化系统结构以及配网二次系统逻辑结构的基础上,提出一套基于...
关于城市轨道通信系统关键技术研究
二、WLAN 网络在城市轨道交通中的应用 因为现代社会科学的发展,城市轨道通信系统的发展也必须跟上脚步,所以,提高 WLAN 无线网络建设城市轨道交通中的应用,是促进...
浅谈新时期铁路通信网络的建设
铁路网大规模建设,铁路自动化、信息化、智能化 发展的要求促进了铁路通信系统的...一般情况下位置适中且能保证安全可靠的运行环境,基本满足铁路建 设城市规划要求...
数字化城市管理系统建设方案
“数字城管”业务是基于移动通信网络、移动终端(终端应用软件)和政府内部办公系 ...标准化原则 本项目将遵循建设部关于数字化城市管理系统建设规范和计算机系统建设...
现代城市地铁无线通信系统的应用研究
龙源期刊网 http://www.qikan.com.cn 现代城市地铁无线通信系统的应用研究 作者:韩月 来源:《城市建设理论研究》2013 年第 06 期 摘要:近年来,地铁通信工程在...
浅析城市轨道通信系统总体构成
城市轨道交通通信系统的任务是建立一个 视听链路网,提高现代化管理水平和传递语音...应考虑近期建设和远期发展的需求,确保系统性 能可靠,容量可扩,系统构建相对灵活...
城市系统工程
城市系统工程_信息与通信_工程科技_专业资料。城市系统工程 程建权 武汉测绘科技大学出版社,1999。6 系统的描述或表达,主要从以下四个方面入手: (1) 系统结构:...
更多相关标签: