城市通信网络建设系统.docx
《城市通信网络建设系统.docx》由会员分享，可在线阅读，更多相关《城市通信网络建设系统.docx（52页珍藏版）》请在冰点文库上搜索。
城市通信网络建设系统
《数据结构》课程设计
题目：
城市通信网络建设系统
班级：
********
姓名：
********
学号：
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函数：
使用户更清晰看到程序的主体，使得程序界面更为直观。
程序如下：
voidinterface（）//初始界面
{
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函数：
为用户提供了方便，用户可以通过按数字键来选择相应的功能。
程序如下：
voidchoice（）//控制选项函数
{
MGraphG=MGraph（）;
intc;
interface（）;
std:
:
cin>>c;
while（c）
{
switch（c）
{
case1:
2
system（cls）;
system（color1b）;
printf（\n）;
printf（\n\t\t*****************欢迎使用**********************）;
printf（\n__________________Welcom_to_Use）;
printf（\
********************************************_____________*************************************）;
printf（\n）;
printf（\n）;
printf（\n）;
G=SaveGraph（G）;
system（cls）;
interface（）;
//system（PAUSE）;
std:
:
cin>>c;
continue;
case2:
system（cls）;
system（color1c）;
printf（\n）;
printf（\n\t\t*****************欢迎使用**********************）;
printf（\n__________________Welcom_to_Use）;
printf（\
********************************************_____________*************************************）;
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;
case3:
system（cls）;
3
system（color1e）;
printf（\n）;
printf（\n\t\t*****************欢迎使用**********************）;
printf（\n__________________Welcom_to_Use）;
printf（\
********************************************_____________*************************************）;
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;
case4:
system（cls）;
system（color1d）;
printf（\n）;
printf（\n\t\t*****************欢迎使用**********************）;
printf（\n__________________Welcom_to_Use）;
printf（\
********************************************_____________*************************************）;
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;
case5:
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
开
Interfac函显示菜单等待选
Choic函结选择相应功
CreateGrap函函SaveGrap函SaveGraphSaveGrap函
建立网络信将图存储到文文将图存储到文
SaveGrap函Kruska函Prin函数Pri函将图存储到文输出网络信算出最小生成算出最小生成
．详细设
4.1数据结构设计
系统采用邻接矩阵存储信息,定义如下:
//图的数据结构
typedefstructMGraph//建立图
{
MGraph（）
{
memset（vexs,0,MAX_VERTEX_NUM）;
}
Vertexvexs[MAX_VERTEX_NUM];//城市名称
intAdjMatrixarcs;//网络条数
intvexnum;//图的当前顶点数（城市总数）
intarcnum;//图的当前弧数（网络总数）
}MGraph;
//记录从顶点集U到V-U的代价最小的边的辅助数组定义
typedefstructTemp//辅助数组
{
Temp（）
{
lowcost=0;
}
Vertexadjvex;//当前点
6
intlowcost;//权值
}closedge[MAX_VERTEX_NUM];
typedefstructCityNumber
{
CityNumber（）
{
memset（cityNam,0,1024）;
}
charcityNam[1024];
}CityNum;
CityNum*Hometown=newCityNum[20];
//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
#include
intLocateVex（MGraphG,Vertexu）
{
inti;
for（i=0;iif（strcmp（u,G.vexs[i]）==0）
returni;
return-1;
}
4.2系统主要模块设计
4.2.1CreateGraph函数
1）创建邻接矩阵以存储图的内容。
2）填充矩阵，即输入城市间网络的状况，以方便使用prim算法或kruskal算法求
出最经济的架设方法。
程序如下：
//采用数组（邻接矩阵）表示法,构造无向网G。
MGraphCreateGraph（MGraph&G）
{
inti=0,j=0,k=0,w=0;
Vertexva,vb;//路径的两个节点
printf（\
\n\t\t*************建立城市间网络信息**********）;
牰湩晴尨请输入城市的总数:
\n）;
scanf（%d,&G.vexnum）;
牰湩晴尨请输入城市间的网络数:
\n）;
scanf（%d,&G.arcnum）;
牰湩晴尨请输入%d个城市的名称（<%d个字符）:
\n,G.vexnum）;
for（i=0;iscanf（%s,G.vexs[i]）;
for（i=0;ifor（j=0;jG.arcs[i][j]=65535;//65535为无穷大
牰湩晴尨请输入%d条网络的两个城市信息城市1和城市2
7
的距离（以空格作为间隔）:
\n,G.arcnum）;
for（k=0;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;//对称
}
returnG;
}
4.2.2SaveGraph函数
1）为了避免每次都重复输入信息，用文件存储图的内容。
2）如果没有文件则建立文件，并把图的内容存储到文件中。
3）如果文件存在，则从文件中读取图的内容到内存，以便完成其他操作。
程序如下：
MGraphSaveGraph（MGraphG）//输入内容存储在smalltree.dat
{
inti,j;
FILE*fp;
fp=fopen（smalltree.dat,
t）;
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;ifprintf（fp,%s\t\n,G.vexs[i]）;//存城市名称
for（i=0;ifor（j=0;jif（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
瑳?
挺畯?
尼存储成功！
。
。
。
输入任意键返回.<:
endl;
charc=getchar（）;
}
else//从文件中读取网的信息存到内存中
{
printf（\\t*******正在读取文件中....***********\n）;
fscanf（fp,%d\n,&G.vexnum）;
fscanf（fp,%d\n,&G.arcnum）;
chartempBuffer[1024];
memset（tempBuffer,0,1024）;
for（i=0;i{
fgets（tempBuffer,1023,fp）;
strcpy（Hometown[i].cityNam,tempBuffer）;
}
charCityA[1024];
intLenth=0;
memset（CityA,0,1024）;
for（i=0;ifor（j=0;j{
fscanf（fp,%s,&CityA）;
intn=0;
chartempCityName[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）;
intnum=0;
while（CityA[n]!
='_'）
{
tempCityName[num]=CityA[n];
n++;
num++;
}
strcpy（G.vexs[i+G.vexnum+1],tempCityName）;
intnumint=0;
n++;
9
memset（tempCityName,0,1024）;
while（CityA[n]!
='\0'）
{
tempCityName[numint]=CityA[n];
n++;
numint++;
}
intX=1;
Lenth=0;
for（n=numint-1;n>=0;n--）
{
intintkeynum=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***********\n）;
}
fclose（fp）;
returnG;
}
4.2.3print函数
Print函数完成输出功能，将内存中图的内容输出到屏幕上
程序如下：
MGraphprint（MGraphG）//将输入的网络基本信息打到屏幕上
{
inti,j;
牰湩晴尨城市总数:
%d\t,G.vexnum）;
牰湩晴尨网络条数:
%d\n,G.arcnum）;
牰湩晴尨城市名称:
\t\n）;
for（i=0;i{
//printf（%s_,G.vexs[i]）;
std:
:
cout<}
printf（\
）;
牰湩晴尨各个城市间的距离:
\n）;
printf（\
）;
printf（\
）;
for（i=0;ifor（j=0;jprintf（%s__%s_距离:
%d公里\n,G.vexs[i+G.vexnum],G.vexs[j+G.vexnum],G.arcs[i][j]）;
瑳?
挺畯?
尼输入任意键返回.<:
end
升级会员 