城市通信网络建设系统方案.docx
《城市通信网络建设系统方案.docx》由会员分享,可在线阅读,更多相关《城市通信网络建设系统方案.docx(39页珍藏版)》请在冰点文库上搜索。
城市通信网络建设系统方案
《数据结构》课程设计
题目:
城市通信网络建设系统
姓名:
********
学号:
1111111111
指导教师:
AAAAAAAAA
完成日期:
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函数,即欢迎界面以及实
现用户可以按数字键选择相应的功能。
欢迎界面如下图:
•CAUt*r<\Adminiitop'k
:
:
檢曬
iS5P?
i入倉.蓉哦择的选烦“5>:
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");
输入通信网络基本信息并将信息存储到文件中将网络基本信息显示到屏幕上\n");
用kruskal算法算出最短路径,并将结果存储
用prim算法算出最短路径,并将结果存储到文件中退出\n");
printf(”\n");
printf("\n");
请输入您要选择的选项(1-5):
\n");
printf("\t\t\t
}
(2)choice函数:
为用户提供了方便,用户可以通过按数字键来选择相应的功能。
程序如下:
voidchoice。
//控制选项函数
{
MGraphG=MGraph();
intc;
interface();
std:
:
cin>>c;
while(c)
{
switch(c)
{
case1:
system("cls");
system("color1b");
printf("\n");
case2:
case3:
system("cls");
case4:
*****************************"'
printf("\n");
printf("\n");
printf("\n");
G=SaveGraph(G);G=kruskal(G);
结果存入PrimResult.dat中,按任意键返回
printf("\t\t*******
***********\n")・
c=getchar();
c=getchar();
system("cls");interface();system("PAUSE");
std:
:
cin»c;
continue;
case5:
return;
}
}
}
3.模块设计
3.1模块设计
系统主要包含主程序模块和其它操作模块。
其调用关系如下图所示。
⑴CreateGraph(G);//创建图模块
⑵SaveGraph(G);//存储图模块
(3)Print(G);II输出图模块
(4)Kruskal(G);I/kruskal算法求最小生成树模块
Kruskal算法的基本思想是:
1、若网络G的边数enl,则G即为所求的最小生成树,否则,一定有e>n-1.
2、将网络的e条边按权值自小到大顺序排列。
3、将网络G中的边都去掉,只留下n个孤立顶点作为初始的最小生成树T,再按边
的排放顺序逐个考察,若与当前E(T)中的边不构成圈,便将它加入到边集E(T),直至
E(T)中边数满n-1为止。
(5)Prim(G);I/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个子模块之间的主要调用关系如下图所示:
建立图
系统采用邻接矩阵存储信息,定义如下:
//图的数据结构
typedefstructMGraph//{
MGraph()
{
memset(vexs,0,MAX_VERTEX_NUM);
}
Vertexvexs[MAX_VERTEX_NUM];//城市名称
intAdjMatrixarcs;//intvexnum;//
intarcnum;//
网络条数
图的当前顶点数(城市总数)图的当前弧数(网络总数)
}MGraph;
//记录从顶点集U到V-U的代价最小的边的辅助数组定义typedefstructTemp//辅助数组
{
Temp()
{
lowcost=0;
}
Vertexadjvex;//当前点
intlowcost;//权值
}closedge[MAX_VERTEX_NUM];typedefstructCityNumber
{
CityNumber()
{
memset(cityNam,0,1024);
}
charcityNam[1024];
}CityNum;
CityNum*Hometown=newCityNum[20];
//若G中存在顶点u,则返回该顶点在图中位置;否则返回-1。
#includeintLocateVex(MGraphG,Vertexu)
{
inti;
for(i=0;iif(strcmp(u,G.vexs[i])==0)
returni;
return-1;
}
4.2系统主要模块设计
4.2.1CreateGraph函数
以方便使用prim算法或kruskal算法求
1)创建邻接矩阵以存储图的内容。
2)填充矩阵,即输入城市间网络的状况,
出最经济的架设方法。
程序如下:
//采用数组(邻接矩阵)表示法,构造无向网G
MGraphCreateGraph(MGraph&G)
{
inti=0,j=0,k=0,w=0;
Vertexva,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构造顶点向量
初始化邻接矩阵
为无穷大
printf(”请输入%d条网络的两个城市信息城市1和城市2
的距离(以空格作为间隔):
\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","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;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);
std:
:
cout<<"存储成功!
。
。
输入任意键返回."<:
endl;
charc=getchar();
}
elseII从文件中读取网的信息存到内存中
******
正在读取文件中
*********
fscanf(fp,"%d\n",&G.vexnum);
fscanf(fp,"%d\in",&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++;
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;
case3:
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("\t\t*******}fclose(fp);returnG;
4.2.3print函数
Print函数完成输出功能,将内存中图的内容输出到屏幕上程序如下:
MGraphprint(MGraphG)〃将输入的网络基本信息打到屏幕上
{
inti,j;
printf("城市总数:
%d\t",G.vexnum);
printf("网络条数:
%d\n",G.arcnum);
printf("城市名称:
\t\n");
for(i=0;i{
//printf("%s_",G.vexs[i]);
std:
:
cout<}
printf("\n");
printf("各个城市间的距离:
\n");
printf("\n");
printf("\n");
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]);std:
:
cout<<"输入任意键返回."<:
endl;charc=getchar();
returnG;
}
4.2.4kruskal函数
用kruskal算法求出最小生成树,即最经济的假设方案
程序如下:
MGraphkruskal(MGraphG)//结果存储在KruskalResult.dat
{
intset[MAX_VERTEX_NUM],i,j;
intk=O,a=O,b=O,min=G.arcs[a][b];
FILE*ffp;
ffp=fopen("KruskaiResult.dat","wt");
for(i=0;iset[i]=i;
printf("最短网络路径为:
\n");
while(k{
for(i=0;ifor(j=i+1;jif(G.arcs[i][j]{
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;iif(set[i]==set[b])
set[i]=set[a];
}
min=G.arcs[a][b]=G.arcs[b][a]=65535;//输出过的权值变为最大值
}
rewind(ffp);
fclose(ffp);
returnG;
}
4.2.5prim函数
用prim算法求出最小生成树,即最经济的假设方案
程序如下:
//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边
{
inti,j,k=O;
closedgeclose;
FILE*fpp;
fpp=fopen("PrimResult.dat","wt");k=LocateVex(G,u);
for(j=0;j{
strcpy(close[j].adjvex,u);
close[j].lowcost=G.arcs[k][j];
初始,U={u}
:
\n");
选择其余G.vexnum-1个顶点
求出T的下一个结点:
第K顶点
}
close[k].lowcost=0;//printf("最短网络路径为
for(i=1;ik=minimum(G,close);//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;jif(G.arcs[k][j]{
strcpy(close[j].adjvex,G.vexs[k]);close[j].lowcost=G.arcs[k][j];
}
}
rewind(fpp);
fclose(fpp);
}
5•调试分析
系统主界面运行如图1所示。
各子功能测试运行结果如下运行程序,出现欢迎界面,见下图:
Jercionl.0
:
:
:
:
:
:
:
:
:
:
關曬
+++-***"rtadep"Byp'p
iJHSAffi®选择的选项<一£>=
5.1城市间网络信息的建立
IC:
;\Users\Administrator\Desktop\kcsj・exe
Welcom__to_Use
*************建立城市间网络信息mu请输入城市的总数:
慎输入城市间的网络数:
;青输入吕个城市的名称心0个字符〉:
NJUXSHSZC2
125
468
523
256
154
296
信输入疏网络的两个城市信息城市1和城市2的距离浪空格作为间隔〉:
凹
UX
SH
品
匕£
5.2显示通信网络的基本信息
F面显示的是通信网络的基本信息
恪■个城帀间的距离:
IC:
\U5er5\Administrator\Desktop\kcsjj..exe
意键返回
5.3查询最短网络路径
6•用户使用说明
1、运行程序,出现欢迎界面;
2、按1进入输入系统,如果文件没有存储城市网络内容,则由用户从键盘读入,读入后自动保存到文件中,按任意键即可返回欢迎界面;
3、如果文件内已经存储了城市网络内容,则显示文件已保存到文件中,按任意键返回;
4、输入2可以在屏幕上输出存储在文件内的城市间网络信息,显示完毕后按任意键可返回欢迎见面;
5、按3和4分别可实现kruskal算法和prim算法求出最小生成树,即最低经济代价建设通信网络(距离最短的最经济),显示完毕后按任意键返回欢迎界面;
6、按5退出程序。
7.参考文献
《数据结构理论与实践》杨永斌(核心算法prim算法以及kruskal算法来源于此)
《数据结构(C语言)实践教程》胡元义
《数据结构》严蔚敏、吴伟民
《VisualC++课程设计案例精选与编程指导》陈清华、朱红
&对所设计的软件进行自我评价,如创新点、未解决的问题等情况说明:
1、对图的逻辑结构及存储结构有了更深刻的认识;
2、对prim算法和kruskal算法亦有了更