城市通信网络建设系统方案Word文档下载推荐.docx
《城市通信网络建设系统方案Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《城市通信网络建设系统方案Word文档下载推荐.docx（39页珍藏版）》请在冰点文库上搜索。
若要在n个城市之间建设通信网络，只需要架设n-1条通信线路即可。
所以，将一个现
实的经济问题，转变为一个求最小生成树的问题。
本系统软件采用经典算法prim算法和
kruskal算法实现求最小生成树，从而获取最经济的通信路径。
2.3系统功能设计
系统建立了interface函数和choice函数，其功能如下：
（1）interface函数：
使用户更清晰看到程序的主体，使得程序界面更为直观。
程序
如下：
voidinterface（）//初始界面
{
printf（”\n"
）;
printf（"
最小生成树的应用\n"
通信网络建设问题\n"
printf（"
Made…By…董卓琴Version1.0\n"
\n"
printf（”\n"
;
输入通信网络基本信息并将信息存储到文件中将网络基本信息显示到屏幕上\n"
用kruskal算法算出最短路径，并将结果存储
用prim算法算出最短路径，并将结果存储到文件中退出\n"
请输入您要选择的选项（1-5）:
\n"
\t\t\t
}
（2）choice函数：
为用户提供了方便，用户可以通过按数字键来选择相应的功能。
程序如下：
voidchoice。
//控制选项函数
MGraphG=MGraph（）;
intc;
interface（）;
std:
cin>
>
c;
while（c）
switch（c）
case1:
system（"
cls"
color1b"
case2:
case3:
case4:
*****************************"
'
\n"
G=SaveGraph（G）;
G=kruskal（G）;
结果存入PrimResult.dat中，按任意键返回
\t\t*******
***********\n"
）・
c=getchar（）;
interface（）;
system（"
PAUSE"
cin»
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。
#include<
stdio.h>
intLocateVex（MGraphG,Vertexu）
inti;
for（i=0;
i<
G.vexnum;
++i）
if（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;
//路径的两个节点
\n\n\t\t*************建立城市间网络信息**********"
printf（”请输入城市的总数:
scanf（"
%d"
&
G.vexnum）;
printf（”请输入城市间的网络数:
scanf（"
&
G.arcnum）;
请输入％d个城市的名称（<
%d个字符）:
G.vexnum）;
for（i=0;
i<
G.vexnum;
++i）//scanf（"
%s"
G.vexs[i]）;
for（i=0;
++i）//for（j=0;
j<
++j）G.arcs[i][j]=65535;
//65535
构造顶点向量
初始化邻接矩阵
为无穷大
printf（”请输入％d条网络的两个城市信息城市1和城市2
的距离（以空格作为间隔）:
G.arcnum）;
for（k=0;
k<
G.arcnum;
++k）
%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）;
wt"
fprintf（fp,"
%d\n"
G.vexnum）;
//存城市树
//存网络数
++i）
%s\t\n"
〃存城市名称
++i）〃存储邻接矩阵
for（j=0;
G.vexnum;
++j）
if（G.vexs[i]==G.vexs[j]）
G.arcs[i][j]=0;
///到它自己
%s_%s_%d\n"
G.vexs[i],
G.vexs[j],G.arcs[i][j]）;
else
rewind（fp）;
cout<
<
"
存储成功！
。
输入任意键返回."
endl;
charc=getchar（）;
elseII从文件中读取网的信息存到内存中
******
正在读取文件中
*********
fscanf（fp,"
G.vexnum）;
%d\in"
G.arcnum）;
chartempBuffer[1024];
memset（tempBuffer,0,1024）;
i<
fgets（tempBuffer,1023,fp）;
strcpy（Hometown[i].cityNam,tempBuffer）;
}
charCityA[1024];
intLenth=0;
memset（CityA,0,1024）;
G.arcnum;
++j）
fscanf（fp,"
CityA）;
intn=0;
chartempCityName[1024];
memset（tempCityName,0,1024）;
while（CityA[n]!
='
_'
）
tempCityName[n]=CityA[n];
n++;
strcpy（G.vexs[i+G.vexnum],tempCityName）;
intnum=0;
tempCityName[num]=CityA[n];
num++;
strcpy（G.vexs[i+G.vexnum+1],tempCityName）;
intnumint=0;
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;
1'
intkeynum=1;
2'
intkeynum=2;
break;
intkeynum=3;
4'
intkeynum=4;
5'
intkeynum=5;
6'
intkeynum=6;
7'
intkeynum=7;
8'
intkeynum=8;
9'
intkeynum=9;
Lenth+=intkeynum*X;
X=X*10;
G.arcs[i][j]=Lenth;
\t\t*******}fclose（fp）;
returnG;
4.2.3print函数
Print函数完成输出功能，将内存中图的内容输出到屏幕上程序如下：
MGraphprint（MGraphG）〃将输入的网络基本信息打到屏幕上
城市总数:
%d\t"
G.vexnum）;
网络条数：
％d\n"
G.arcnum）;
城市名称:
\t\n"
i++）
//printf（"
%s_"
Hometown[i].cityNam;
各个城市间的距离:
%s__%s_距离:
%d公里
G.vexs[i+G.vexnum],G.vexs[j+G.vexnum],G.arcs[i][j]）;
std:
charc=getchar（）;
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"
i++）
set[i]=i;
最短网络路径为:
while（k<
G.vexnum-1）
G.vexnum;
++i）//从G.arcs[i][j]中找到权值最小的
for（j=i+1;
if（G.arcs[i][j]<
min）
min=G.arcs[i][j];
//min中存最小权值
a=i;
b=j;
if（set[a]!
=set[b]）//如果a和b值不同则输出
%s--%s\t距
离:
G.vexs[a],G.vexs[b],G.arcs[a][b]）;
〃输出生成树各边
fprintf（ffp,"
%s--%s\n"
G.vexs[a],G.vexs[b]）;
k++;
i++）//输出后变成相同值，下次将不会输出
if（set[i]==set[b]）
set[i]=set[a];
min=G.arcs[a][b]=G.arcs[b][a]=65535;
//输出过的权值变为最大值
rewind（ffp）;
fclose（ffp）;
4.2.5prim函数
用prim算法求出最小生成树，即最经济的假设方案
程序如下:
//用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边
inti,j,k=O;
closedgeclose;
FILE*fpp;
fpp=fopen（"
PrimResult.dat"
k=LocateVex（G,u）;
++j）//辅助数组初始化
strcpy（close[j].adjvex,u）;
close[j].lowcost=G.arcs[k][j];
初始,U={u}
选择其余G.vexnum-1个顶点
求出T的下一个结点：
第K顶点
close[k].lowcost=0;
//printf（"
最短网络路径为
for（i=1;
++i）//{
k=minimum（G,close）;
（%s_%s）\n"
close[k].adjvex,G.vexs[k]）;
fprintf（fpp,"
//输出生成树的边
//第K顶点并入U集
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所示。
各子功能测试运行结果如下运行程序，出现欢迎界面，见下图：
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面显示的是通信网络的基本信息
恪■个城帀间的距离:
\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算法亦有了更
升级会员 