《数据结构》课程设计
题目：城市通信网络建设系统
班级：********
姓名：********
学号：1111111111
指导教师：^^^^^^^^^
完成日期：2015 年 6 月 13 日
0
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;
