城市通信网络建设系统

《数据结构》课程设计

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

班级：********

姓名：********

学号：**********

指导教师：^^^^^^^^^

完成日期：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(\" \\\请输入您要选择的选项(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\\*****************欢迎使用**********************\"); 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\\*****************欢迎使用**********************\"); printf(\" \\n__________________Welcom_to_Use\");

printf(\"\\n********************************************_____________*************************************\"); printf(\" \\n\");

printf(\" \\\下面显示的是通信网络的基本信息\\n\"); printf(\" \\n\"); G=SaveGraph(G); G=print(G);

printf(\" \\n\\\按任意键返回\\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\\*****************欢迎使用**********************\"); printf(\" \\n__________________Welcom_to_Use\");

printf(\"\\n********************************************_____________*************************************\"); printf(\" \\n\"); printf(\" \\n\"); printf(\" \\n\"); G=SaveGraph(G); prim(G,G.vexs[0]);

printf(\" \\*******结果存入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\\*****************欢迎使用**********************\"); printf(\" \\n__________________Welcom_to_Use\");

printf(\"\\n********************************************_____________*************************************\"); printf(\" \\n\"); printf(\" \\n\"); printf(\" \\n\"); G=SaveGraph(G); G=kruskal(G);

printf(\" \\*******结果存入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函数 结束 选择相应功能

SaveGraph函数 SaveGraph函数 CreateGraph函数 SaveGraph函数 建立网络信息 将图存储到文件将图存储到文 将图存储到文件

Print函数 Kruskal函数 SaveGraph函数 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

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\\*************建立城市间网络信息**********\"); printf(\"请输入城市的总数:\\n\"); scanf(\"%d\.vexnum );

printf(\"请输入城市间的网络数:\\n\"); scanf(\"%d\.arcnum);

printf(\"请输入%d个城市的名称(<%d个字符):\\n\.vexnum); for(i=0;ifor(i=0;iG.arcs[i][j]=65535; // 65535为无穷大

printf(\"请输入%d条网络的两个城市信息城市1和城市2

7

的距离(以空格作为间隔): \\n\.arcnum); for(k=0;kscanf(\"%s %s %d\输入城市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\ if(fp==NULL) { G=CreateGraph(G); fp=fopen(\"smalltree.dat\ fprintf(fp,\"%d\\n\.vexnum); //存城市树 fprintf(fp,\"%d\\n\.arcnum); //存网络数 for(i=0;i} else { fprintf(fp,\"%s_%s_%d\\n\.vexs[j], G.arcs[i][j]);

} rewind(fp);

8

std::cout<<\"存储成功！。。。输入任意键返回.\"<else //从文件中读取网的信息存到内存中 {

printf(\"\\*******正在读取文件中....***********\\n\"); fscanf(fp,\"%d\\n\.vexnum); fscanf(fp,\"%d\\n\.arcnum); char tempBuffer[1024];

memset(tempBuffer, 0, 1024); for(i=0; ichar CityA[1024]; int Lenth = 0;

memset(CityA, 0, 1024);

for(i=0; i9

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(\"\\*******读取成功...\***********\\n\"); } fclose(fp); return G; }

4.2.3 print函数 Print函数完成输出功能，将内存中图的内容输出到屏幕上

程序如下：

MGraph print(MGraph G)//将输入的网络基本信息打到屏幕上 {

int i,j;

printf(\"城市总数:%d\\ printf(\"网络条数:%d\\n\.arcnum); printf(\"城市名称:\\\n\"); for(i=0; i//printf(\"%s_\.vexs[i]);

std::cout<printf(\"\\n\");

printf(\"各个城市间的距离:\\n\"); printf(\"\\n\"); printf(\"\\n\");

for(i=0;i\\n\.vexs[i+G.vexnum],G.vexs[j+G.vexnum],G.arcs[i][j]);

std::cout<<\"输入任意键返回.\"<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\ for(i=0;iprintf(\"最短网络路径为:\\n\"); while(kfor(i=0;ifprintf(ffp,\"%s--%s\\n\ k++; for(i=0;irewind(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\ k=LocateVex(G,u);

for(j=0;jstrcpy(close[j].adjvex,u); close[j].lowcost=G.arcs[k][j]; }

close[k].lowcost=0; // 初始,U={u} printf(\"最短网络路径为:\\n\");

for(i=1;ik=minimum(G,close); // 求出T的下一个结点：第K顶点 printf(\"(%s-%s)\\n\.vexs[k]);

fprintf(fpp,\"%s--%s\\n\.vexs[k]); // 输出生成树的边 close[k].lowcost=0; // 第K顶点并入U集 for(j=0;jrewind(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 #include #include

#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

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\\*************建立城市间网络信息**********\"); printf(\"请输入城市的总数:\\n\"); scanf(\"%d\

printf(\"请输入城市间的网络数:\\n\"); scanf(\"%d\

printf(\"请输入%d个城市的名称(<%d个字符):\\n\ for(i=0;ifor(i=0;iG.arcs[i][j]=65535; // 65535为无穷大

printf(\"请输入%d条网络的两个城市信息城市1和城市2的距离(以空格作为间隔): \\n\

for(k=0;kscanf(\"%s %s %d\输入城市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\if(fp==NULL) {

G=CreateGraph(G);

fp=fopen(\"smalltree.dat\

fprintf(fp,\"%d\\n\存城市树 fprintf(fp,\"%d\\n\存网络数 for(i=0;ifprintf(fp,\"%s\\\n\存城市名称 for(i=0;iif(G.vexs[i] == G.vexs[j]) {

G.arcs[i][j] = 0; ///到它自己

fprintf(fp,\"%s_%s_%d\\n\G.vexs[j], G.arcs[i][j]); } else {

fprintf(fp,\"%s_%s_%d\\n\G.vexs[j], G.arcs[i][j]); } rewind(fp);

std::cout<<\"存储成功！。。。输入任意键返回.\"<else //从文件中读取网的信息存到内存中 {

printf(\"\\*******正在读取文件中....***********\\n\"); fscanf(fp,\"%d\\n\ fscanf(fp,\"%d\\n\ char tempBuffer[1024];

memset(tempBuffer, 0, 1024); for(i=0; ifgets(tempBuffer, 1023, fp);

strcpy(Hometown[i].cityNam,tempBuffer); }

char CityA[1024]; int Lenth = 0;

memset(CityA, 0, 1024);

for(i=0; i19

fscanf(fp, \"%s\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 = 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.arcs[i][j] = Lenth; }

printf(\"\\*******读取成功...\***********\\n\"); }

fclose(fp); return G;

}MGraph print(MGraph G)//将输入的网络基本信息打到屏幕上 {

int i,j;

printf(\"城市总数:%d\\ printf(\"网络条数:%d\\n\ printf(\"城市名称:\\\n\"); for(i=0; i//printf(\"%s_\

std::cout<21

printf(\"\\n\");

printf(\"各个城市间的距离:\\n\"); printf(\"\\n\"); printf(\"\\n\");

for(i=0;iprintf(\"%s__%s_距离:%d公里

\\n\ std::cout<<\"输入任意键返回.\"<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\ for(i=0;iprintf(\"最短网络路径为:\\n\"); while(kfor(i=0;imin=G.arcs[i][j];//min中存最小权值 a=i; b=j; }

if(set[a]!=set[b]) //如果a和b值不同则输出 {

printf(\"%s--%s\距

离:%d\\n\输出生成树各边

fprintf(ffp,\"%s--%s\\n\ k++;

for(i=0;i22

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;jif(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\ k=LocateVex(G,u);

for(j=0;jstrcpy(close[j].adjvex,u); close[j].lowcost=G.arcs[k][j]; }

close[k].lowcost=0; // 初始,U={u} printf(\"最短网络路径为:\\n\");

for(i=1;ik=minimum(G,close); // 求出T的下一个结点：第K顶点 printf(\"(%s-%s)\\n\

23

fprintf(fpp,\"%s--%s\\n\输出生成树的边 close[k].lowcost=0; // 第K顶点并入U集 for(j=0;jif(G.arcs[k][j]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(\" \\\请输入您要选择的选项(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\\*****************欢迎使用**********************\"); 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\\*****************欢迎使用**********************\"); printf(\" \\n__________________Welcom_to_Use\");

printf(\"\\n********************************************_____________*************************************\"); printf(\" \\n\");

printf(\" \\\下面显示的是通信网络的基本信息\\n\"); printf(\" \\n\"); G=SaveGraph(G); G=print(G);

printf(\" \\n\\\按任意键返回\\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\\*****************欢迎使用**********************\"); printf(\" \\n__________________Welcom_to_Use\");

printf(\"\\n********************************************_____________*************************************\"); printf(\" \\n\"); printf(\" \\n\"); printf(\" \\n\"); G=SaveGraph(G); prim(G,G.vexs[0]);

printf(\" \\*******结果存入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\\*****************欢迎使用**********************\"); printf(\" \\n__________________Welcom_to_Use\");

printf(\"\\n********************************************_____________*************************************\"); printf(\" \\n\"); printf(\" \\n\"); printf(\" \\n\"); G=SaveGraph(G); G=kruskal(G);

printf(\" \\*******结果存入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