基于最小生成树的小区网线铺设问题的实现Word格式.docx
- 文档编号:5901828
- 上传时间:2023-05-05
- 格式:DOCX
- 页数:18
- 大小:77.95KB
基于最小生成树的小区网线铺设问题的实现Word格式.docx
《基于最小生成树的小区网线铺设问题的实现Word格式.docx》由会员分享,可在线阅读,更多相关《基于最小生成树的小区网线铺设问题的实现Word格式.docx(18页珍藏版)》请在冰点文库上搜索。
这门课程实践性非常强,为了让我们能够掌握所学的知识,并能够灵活的运用,我们进行了此次课程设计。
该设计要求掌握数据结构的内容,也需要一定的c语言基础。
课程设计的目的是:
熟练掌握基本的数据结构,熟练掌握各种算法,运用高级语言编写质
量高、风格好的应用程序。
对于“基于最小生成树的小区网线铺设问题的实现”这个题目
来说,要求掌握的主要有:
最小生成树的生成原理和算法,查找的相关算法等等。
通过此次课程设计,能够进一步的加深对数据结构的理解,同时也提高动手实践能力,进一步熟练了对visualC++平台的使用。
关键字:
网线铺设,最小生成树,生成,prim算法,kruskal算法
引言:
可以用联通网来表示n个住户间的可能网线铺设路线,其中网的顶点表示住户,边表示住户之间的线路,赋予边的权值表示相应的代价。
对于n个顶点的联通网可以建立许多不同的生成树,现在我们要选择的就是这样一颗生成树,使得代价最小
需求分析:
①铺设人员能将住户个数输入程序中②铺设人员能将住户和住户之间的代价输入程序中③程序能输出最小代价的树
数据结构设计
StructMGraph:
图的相关信息
Structedge:
记录权值
算法设计
#include<
stdio.h>
stdlib.h>
#defineM20
#defineMAX20
/*采用数组表示法表示图*/
typedefstruct{
unsignedintadj;
/*用01记录边是否存在*/
unsignedintweight;
/*边的权值*/
}AdjMatrix[MAX][MAX];
AdjMatrixarc;
/*邻接矩阵*/
unsignedintvexnum,arcnum;
/*图的当前顶点数和边数*/
}MGraph;
/*Kruskal算法中用于堆排序的辅助数组定义*/
typedefstruct{
unsignedintbegin;
unsignedintend;
/*邻接点*/
/*邻接点之间边的权值*/
}edge;
/*prim算法中记录从顶点集U到V-U的代价最小的边的辅助数组定义*/
unsignedintadjvex;
/*记录顶点*/
unsignedintlowcost;
/*记录权值*/
}closedge;
/*函数申明*/
voidCreatGraph(MGraph*);
voidConnected(MGraph*G);
voidSort(edge*,MGraph*);
voidSift(edge*edges,unsignedinti,unsignedintm);
voidSwapn(edge*,unsignedint,unsignedint);
voidReset(edge*edges,unsignedinti,unsignedintj);
voidMiniSpanTree_Krus(MGraph*);
unsignedintFindCircle(unsignedint*,unsignedint);
voidMiniSpanTree_Prim(MGraph*G,unsignedintu);
unsignedintminimum(MGraph*G,closedgeclosedges[]);
/*Creatangraph.*/
/*创建图*/
voidCreatGraph(MGraph*G){
unsignedinti,j,n,m;
restart:
printf("
Pleaseenterthenumberofedge(s)andvertex(s)inthegraph.\n"
);
请输入边数和顶点数:
"
scanf("
%d%d"
&
G->
arcnum,&
vexnum);
if(G->
vexnum>
=MAX||G->
vexnum<
=0){
Invalidinput!
!
Pleasereinput!
\n"
越界,请重新输入!
gotorestart;
}
for(i=1;
i<
=G->
vexnum;
i++){/*Initiatethisgraph*//*初始化图*/
for(j=1;
j<
j++){
G->
arc[i][j].adj=G->
arc[j][i].adj=0;
arc[i][j].weight=G->
arc[j][i].weight=65535;
●}
for(i=1;
arcnum;
i++){/*entertheweightoftheedge*//*输入边和权值*/
re:
printf("
\nPleaseentertwoadjacentvertexsthathaveanedge."
\n请输入有边的2个顶点(unsignedint):
scanf("
n,&
m);
if(G->
arc[n][m].adj==1||G->
arc[m][n].adj==1){
printf("
Thisedgeyouhavebeeninput,pleaseinputanother!
这条边已经输入啦,请输入其它的!
gotore;
}
elseif(m==n){
非法输入!
while(n<
0||n>
G->
vexnum||m<
0||m>
vexnum){
输入的数字不符合要求,顶点越界,请重新输入:
scanf("
%d%d"
G->
arc[n][m].adj=G->
arc[m][n].adj=1;
getchar();
\nPleaseentertheweightoftheedgethatisbetweenvertex(s)%dand%d."
n,m);
\n请输入%d与%d之间的权值:
%d"
arc[n][m].weight);
while(G->
arc[n][m].weight<
输入的数字不符合要求,请重新输入:
arc[m][n].weight=G->
arc[n][m].weight;
}
/*Thisfuncationcouldtelluswhetherthegraphisconnectedornot.*/
/*判断该图是否连通*/
voidConnected(MGraph*G){
unsignedinti,j;
i++){
if(G->
arc[i][j].adj!
=0){
break;
}
elseif(j==G->
printf("
Wecannotdealwithit,becausethegraphisnotconnected!
exit(0);
ThefollowingistheAdjacencyMatrix.\n"
邻接矩阵为:
i++){
%d"
G->
arc[i][j].adj);
/*Sortinarrangeoftheedges'
Weight*/
/*按权值进行堆排序*/
voidSort(edgeedges[],MGraph*G){
for(j=G->
arcnum/2;
j>
=1;
j--)
Sift(edges,j,G->
arcnum);
/*建堆,得最大值edges[1].weight*/
=2;
j--){
Swapn(edges,1,j);
/*堆顶(根)结点与最后结点的值对换*/
Sift(edges,1,j-1);
/*调整堆*/
Aftersortedinarrangeoftheedges'
Weight.\n"
权排序之后的为:
<
%d,%d>
>
%d\n"
edges[i].begin,edges[i].end,edges[i].weight);
/*筛选算法*/
voidSift(edge*edges,unsignedinti,unsignedintm){
/*把以t为根的完全二叉树edges[i].weight..edges[m].weight调整成一个堆*/
/*初值:
i的左右子树均是堆*/
unsignedintj=i*2;
/*j指向左孩子*/
Reset(edges,0,i);
/*将edges[i]暂存到edges[0]中*/
while(j<
=m){
if(j<
m&
&
edges[j].weight<
edges[j+1].weight)j++;
/*左孩子与右孩子进行比较,找较大孩子,确定筛选的方向*/
if(edges[0].weight<
edges[j].weight){
Reset(edges,i,j);
/*将edges[j]的权值,头和尾赋给edges[i]*/
i=j;
j=2*i;
}/*继续筛选*/
elsej=m+1;
/*筛选完毕*/
Reset(edges,i,0);
/*将edges[0]的权值,头和尾赋给edges[i]*/
}
/*edges[i]和edges[j]交换权值以及头和尾*/
voidSwapn(edge*edges,unsignedinti,unsignedintj){
unsignedinttemp;
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp;
voidReset(edge*edges,unsignedinti,unsignedintj){
/*FindCircle*/
/*找尾*/
unsignedintFindCircle(unsignedint*parent,unsignedintf){
while(parent[f]>
0){
f=parent[f];
returnf;
/*GettheMinimunCostSpanningTree*/
/*生成最小生成树*/
voidMiniSpanTree_Krus(MGraph*G){
unsignedinti,j,n,m;
unsignedintk=1;
unsignedintparent[M];
edgeedges[M];
for(j=i+1;
if(G->
arc[i][j].adj==1){
edges[k].begin=i;
edges[k].end=j;
edges[k].weight=G->
arc[i][j].weight;
k++;
Sort(edges,G);
parent[i]=0;
ThefollowingistheMinimunCostSpanningTree.\n"
最小生成树为:
n=FindCircle(parent,edges[i].begin);
m=FindCircle(parent,edges[i].end);
if(n!
parent[n]=m;
unsignedintMinimum(MGraph*G,closedgeclosedges[]){/*选择最小的边*/
unsignedinttemp,k,i,p;
temp=65535,p=0;
for(i=1;
i<
++i){
if(closedges[i].lowcost!
if(closedges[i].lowcost<
temp){
temp=closedges[i].lowcost;
k=i;
p=1;
if(p==0)
/*printf("
k);
*/
return(k);
voidMiniSpanTree_Prim(MGraph*G,unsignedintu){
/*用普里姆算法从第u个顶点出发构造网G的最小生成树T,输出T的各条边*/
unsignedinti,j,k;
closedgeclosedges[M];
for(j=1;
++j){/*辅助数组初始化*/
if(j!
=u){
closedges[j].adjvex=u;
closedges[j].lowcost=G->
arc[u][j].weight;
closedges[u].lowcost=0;
/*初始,U={u}*/
vexnum-1;
++i){/*选择其余G.vexnum-1个顶点*/
k=Minimum(G,closedges);
/*k=最小边所在下标位置*/
closedges[k].adjvex,k,G->
arc[k][closedges[k].adjvex].weight);
closedges[k].lowcost=0;
/*第k顶点并入U集*/
for(j=1;
++j){
if(G->
arc[k][j].adj==1&
arc[k][j].weight<
closedges[j].lowcost){
closedges[j].lowcost=G->
arc[k][j].weight;
closedges[j].adjvex=k;
}
/*Mainfuncation*/
/*主函数*/
unsignedintmain(void){
MGraph*G;
intcord;
unsignedintt;
G=(MGraph*)malloc(sizeof(MGraph));
if(G==NULL)
{
memoryallcationfailed,goodbye"
exit(0);
do{
Mainmenu\n"
1BasedonalgorithmofKruskal\n"
2BasedonalgorithmofPrim\n"
3Clean\n"
4Exit\n"
-------------------------------\n"
Pleaseinputyourchoice:
(1,2,3,4)"
cord);
switch(cord){
case1:
{
/*BasedonalgorithmofKruskal*/
CreatGraph(G);
Connected(G);
MiniSpanTree_Krus(G);
}break;
case2:
/*BasedonalgorithmofPrim*/
start:
Pleaseenterthenumberofvertex(s)inthegraphthatyouwanttobeginwith.\n"
请输入起始顶点:
t);
if(t>
vexnum||t<
gotostart;
MiniSpanTree_Prim(G,t);
case3:
system("
cls"
case4:
exit(0);
}while(cord<
=4);
程序运行结果
1启动界面
2kruskal算法计算最小生成树
3.prim算法计算最小生成树
4clean和exit功能
略
不足之处
本程序虽然能有效地计算出n个住户之间的最小代价的网线铺设路线,但是当用户过多的时候,输入数据过于繁琐,不合实际,只能运用于小型小区中
设计体会
做这个程序真的体会很深,虽然以前也写过一些程序,但是这次遇到的困难最大。
如结构体的运用,本程序结构体运用次数比较多,容易出错。
为此查阅了好多资料,但是都没能解决,最后和同学深刻讨论之后,终于解决,总而言之,在设计的过程中遇到了好多困难,虽然面对困难的时候觉得很难受,甚至想过放弃,但是随着问题的解决,渐渐有了成就感。
同时,通过这个星期的课程设计,我懂得了不少,首先,结构体的运用能力进一步加强了,对类的理解也比以前深刻了。
对prim和kruskal算法和最小生成树的认识也是进一步深刻,prim和kruskal算法各有千秋。
最后,也是最重要的一点,那就是自己对计算机和编程的兴趣也更浓厚了,为以后的计算机学习打下了良好的基础。
这段时间的经历很宝贵,不仅可以让自己对编程更加了解,而且可以培养自己刻苦耐劳,勇敢面对困难的精神。
结束语:
本程序是运用c语言中编程实现的以下功能:
:
①铺设人员输入住户的信息程序输出最小
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基于 最小 生成 小区 网线 铺设 问题 实现