《数据结构》课程设计报告建立通信网络

PAGE24-《数据结构》课程设计报告建立通信网络在n个城市建设通信网络，只需架设n-1条线路即可。设计算法，求出如果以最低的经济代价建设这个通信网络。要求如下：至少包含10个城市；城市数n由键盘录入；城市坐标由随机函数产生小于100的整数；输出生成树中各条边以及它们的权值；一、课程设计题目对任意给定的网和起点，用PRIM算法的基本思想求解出所有的最小生成树。在n个城市建设通信网络，只需架设n-1条线路即可。设计算法，求出如果以最低的经济代价建设这个通信网络。二、问题分析和任务定义本课程设计重在使用prim算法实现任意给定的网和起点的图的所有最小生成树的求解，实现本课程设计的关键即是能够掌握prim算法的思想，并能够灵活使用。首先我们必须对prim算法有个清晰地认识，prim算法是普利姆（Prime）于1957年提出了一种构造最小生成树的算法，算法的主要思想如下：按照将顶点逐个连通的步骤，把顶点加入到已经连通的顶点集合U中，最后使得U成为最小生成树。PRIM思路：1）初始化顶点集合U为空集。2）任意选取一个顶点v加入U。3）选取一条权值最小的边（u,v），其中u∈U，v∈（V-U），将该边假如到生成树，v加入到U中。4）重复步骤3），直到所有顶点均加入到U中构成一颗最小生成树。为了实现这一算法需要附设一个辅助数组closedge[v]用来存储从U到V-U之间具有最小代价的边。对于每个顶点v∈（V-U），在closedge，树组中都存在一个分量closedge[v]，它有两个域组成。其中一个是权值，即：closedge[v].lowcost=MIN{cost（u,v）|u∈U}，另外一个是顶点域vexs，存储依附于该边在U中的顶点。其次，针对本课程设计的题目要求，我们需要考虑到五个问题：如何选择、设计一个合适的算法来建立图，用以实现接下来的操作。如何正确的在本实验中使用prim算法。对于本课程设计中的需要，求出对于给定任意给定的网和结点，得出所有的最小生成树，关键在于需要求出所有的最小生成树，需要灵活使用prim算法实现。对于一些细节也是需要考虑斟酌的，比如，当所输入的顶点不存在时，需要一个示语句警示，并能够重新输入。当算法设计完成后，还需对于整个运行程序的运行界面，提示语句以及如何完美、清楚的输出各个最小生成树设计一番。最后，在课程设计过程中，自己需要做好充足的准备工作，吃透课本中关于prim算法的解释说明，同时把握好时间，掌握整个课程设计的进度，做好整体规划，保证本次课程设计可以及时的、成功的设计出来。概要设计对于本次设计，在prim算法中使用的图均为无向图，对于各顶点之间的权值以及连通关系是采用邻接矩阵来实现的。同时在prim算法中采用了辅助数组closedge[v]，主要用来存储到顶点的最小边权值。建立图的数据结构类型如下：typedefstruct{ intvexs[MAX];//顶点信息集合 intarcs[MAX][MAX];//各边的权值 intvexnum;//顶点数 intarcnum;//边数}MGraph;//图类型建立辅助数组结构类型如下：structclosed{ intadjvex;//依附于最小权值边在顶点集合U中的顶点 intlowcost;//存储最小边的权值};closedclosedge[MAX];3.1整个算法概要设计主要在于图的初始化如何求出所有最小生成树。下面我们可以通过相应的流程图来清楚的理解。刚开始时初始化各顶点的顶点域、权值域赋值的算法流程:开始开始把1赋给j把1赋给j 判断j是否等于输入的顶点数值判断j是否等于输入的顶点数值 j不等于I把I的值赋给j的顶点域里；把I的值赋给j的顶点域里；把邻接矩阵中处于[j][I]位置的值赋给j的权值域中。 j等于I把j+1赋给j把j+1赋给j判断j是否小于等于图的顶点数判断j是否小于等于图的顶点数 小于等于 大于把0赋给顶点I的权值域把0赋给顶点I的权值域3.1.1求出最小代价的边的算法流程把1赋给把1赋给j把1赋给i把1赋给i把邻接矩阵中处于[1][i]位置的值赋给i的权值域中;把邻接矩阵中处于[1][i]位置的值赋给i的权值域中;把1赋给i的顶点域中把i+1赋给i把i+1赋给i判断i是否小于图的顶点数判断i是否小于图的顶点数 小于 大于等于把0赋给1的顶点域中，把0赋给1的顶点域中，把1赋给j此时j的权值域是否小于minj的顶点域是否等于0j的顶点域是否等于0把1赋给j把100赋给min,把i的值赋给k.把1赋给i

有一个条件不满足都是肯定的回答此时j的权值域是否小于minj的顶点域是否等于0j的顶点域是否等于0把1赋给j把100赋给min,把i的值赋给k.把1赋给i把顶点j里的权值域中的值赋给最小值min，把j赋给k 把顶点j里的权值域中的值赋给最小值min，把j赋给k把j+1赋给j把j+1赋给j判断j是否小于等于图的顶点数判断j是否小于等于图的顶点数 是 否用两个顶点的集合输出边。用两个顶点的集合输出边。 将顶点k加入到U中，表示k顶点已拿走了，把0赋给k的权值域中，这是标志性的赋值。将顶点k加入到U中，表示k顶点已拿走了，把0赋给k的权值域中，这是标志性的赋值。对于上述流程图可简单解释如下，首先通过对其它顶点依次判断，找出相连的顶点，然后得到顶点序号，再通过for循环，进行循环判断，找出边权值最小的，并赋值进入closedge[]中。3.2重新调整各顶点中的顶点域和权值域的流程:把1赋给m把1赋给m在邻接矩阵中[k][m]存的值是否小于顶点m权值域中的值，m不等于k在邻接矩阵中[k][m]存的值是否小于顶点m权值域中的值，m不等于k 有一个不满足 答案是肯定的把邻接矩阵[k][m]存的值给顶点m的权值域，把顶点k给m的顶点域把邻接矩阵[k][m]存的值给顶点m的权值域，把顶点k给m的顶点域 把m+1赋给m把m+1赋给mm是否小于等于图mg的顶点数m是否小于等于图mg的顶点数 是的否循环到求最小代价边的算法中.循环到求最小代价边的算法中.3.3普利姆算法的总流程将各顶点的顶点域、权值域赋值。将各顶点的顶点域、权值域赋值。求出最小代价的边。重新调整各顶点中的顶点域和权值域。输出边的顶点信息结束开始j小于图的顶点数 是 否 3.4主函数的流程开始开始定义g为邻接矩阵数据类型定义g为邻接矩阵数据类型输入顶点数，边数。输入顶点数，边数。把顶点数和边数赋给邻接矩阵g把顶点数和边数赋给邻接矩阵g把0赋给i把0赋给i输入第i个顶点的信息。循环输入所有顶点的信息输入第i个顶点的信息。循环输入所有顶点的信息循环输入边的起点和终点循环输入边的起点和终点如果超出编号范围，则重新输入。如果超出编号范围，则重新输入。循环输出各边的权值。循环输出各边的权值。调用邻接矩阵的初始化函数、创建函数、PRIM函数。调用邻接矩阵的初始化函数、创建函数、PRIM函数。结束结束详细设计4.1图的建立MGraphCreateMarph(MGraph&G){ intv1,v2,weight,i,j,k; printf("●●请输入无向图的顶点数和边数："); scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i<G.vexnum;i++){//初始化邻接矩阵 for(j=0;j<G.vexnum;j++){ G.arcs[i][j]=0; }} for(i=0;i<G.vexnum;i++){ printf("第%d个顶点的序号：",i+1); scanf("%d",&G.vexs[i]); } printf("\n请你确定各条弧的信息\n"); for(k=0;k<G.arcnum;k++) {printf("●●请输入第%d弧的两个起始顶点和其权值为：",k+1);//输入一条边及依附的顶点及权值 for(;;){scanf("%d%d%d",&v1,&v2,&weight); if((v1>0&&v1<=G.vexnum)&&(v2>0&&v2<=G.vexnum)) break; else printf("输入有误，不存在该顶点，请重新输入^_^\n"); } i=LocateVex(G.vexs,v1);//找到两个结点在邻接矩阵中的位置 j=LocateVex(G.vexs,v2); G.arcs[i][j]=weight;//边的权值 G.arcs[j][i]=G.arcs[i][j];//置(v1,v2)成(v2,v1) } printf("\n"); returnG; }本子函数是用来建立图，其中用到了邻接矩阵用以存储各边的权值以及判断是否连通，其中所调用的LocateVex()是用来指出该顶点在邻接矩阵中所在的位置，其子函数定义如下：intLocateVex(intvexs[],intv){//确定结点是否存在intt; for(inti=0;i<MAX;i++)if(vexs[i]==v)t=i; returnt;}4.2使用Prim算法实现找出图中的最小生成树voidMiniTree_PRIM(MGraphG,intu){ intk=u; inti,j; for(i=0;i<G.vexnum;i++)//初始化closedge数组，v={u} if(i!=k)//两个顶点不重合 {closedge[i].adjvex=u+1;//首先将u视为第一条边的第一个依附顶点 if(!G.arcs[k][i])//两点之间不连通 closedge[i].lowcost=-1; else closedge[i].lowcost=G.arcs[k][i];//调整closedge数组的最小代价lowcost为边上的权值 } closedge[k].lowcost=0; for(i=0;i<G.vexnum-1;i++){//★取其余G.vexnum-1个顶点，循环从此处开始，i无任何意义 for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0){//求出T的下一个结点，第K结点 k=j; break;} for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0) if(closedge[j].lowcost<closedge[k].lowcost)//比较权值大小,从中找出权值最小的边 k=j; printf("%d>%d(%d)\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost); closedge[k].lowcost=0;//将此第k个顶点并入U集中 for(j=0;j<G.vexnum;j++)////在顶点k并入U之后，更新closedge[i]，新顶点并入U后重新选择最小边 if(G.arcs[k][j]>0){ if(closedge[j].lowcost==-1){//如果先前时此两个顶点之间是不连通的 closedge[j].lowcost=G.arcs[k][j];//新的权值域改成新加入顶点与该顶点的权值 closedge[j].adjvex=G.vexs[k];} else//如果此前两顶点本已连通 if(G.arcs[k][j]<closedge[j].lowcost){//调整closedge数组中各边的最小权值 closedge[j].adjvex=G.vexs[k];//依附于最小权值边在U中的顶点 closedge[j].lowcost=G.arcs[k][j];//边的权值赋给closedge数组的最小权值域 } } }}其中要说明的是其中使用了一个辅助数组，其定义如下：structclosed{ intadjvex;//依附于最小权值边在顶点集合U中的顶点 intlowcost;//存储最小边的权值};此数组对PRIM中产生的顶点和边的权值进行临时存储的数组，因此结构体中设计两个变量，顶点名adjvex，边的权值lowcost。定义次数组名为closedclosedge[MAX]在用PRIM算法计算图的最小生成树过程中，这里是整个算法的核心之所在。先要指定点u最为最小生成树的起点，并以次来构成最小生成树，子函数中用k来作为u的载体，同时它也是u在图中的位置，后对辅助数组closedge进行初始化，首先将u视为第一条边的第一个依附顶点，从零开始，所以u+1。如果两点间不连通则给边的权值lowcost赋值-1；否则将选择的边的权值adj赋给loecost，即将起存储在辅助数组中。而后开始寻找下一个结点，进行边的权值的比较，选择出最小权值的边。将该边的顶点和权值存储入辅助数组中，然后重新选择最小边，如此重复直至结束。将在次过程中选择的边的顶点和权值全部存储进辅助数组中。而后开始调整辅助数组中各个边的最小权值，在辅助数组中生成最小生成树。最后将存储在辅助数组中的最小生成树输出。其中，使用多个FOR的套嵌来实现最小权值边的选择。数组在这过程中始终作为临时存储空间，将筛选出的边的信息存储着，最后将其输出来。4.3可建立由五点构建的图如下邻接矩阵邻接矩阵414132656665552134普利姆算法中closedge数组的变化Vclosedge23456UV-UVexLowcostV1 V1V16 15 1 2,3,4,5,6VexLowcostV3 V1V3V305 5 6 41,32,4,5,6VexLowcostV3V6V300526 1,3,62,4,5VexLowcostV3V3000561,3,6,42,5VexLowcostV2000031,2,3,4,65VexLowcost00 0001,2,3,4,5,6 最后以顶点1开始所生成的最小生成树如下：441326552134五、调试通过调试分析，发现此程序中的closedge数组变化是一个难点，其中的数值变化时整个课程设计的关键，或多或少有点繁琐，不容易掌握清楚。对一些特殊情况没有考虑到，从而造成本设计出来的程序不全面，如在输入图中顶点信息时，没有考虑到输入的顶点不存在的情况。如果数据之间的类型不同，会引发数据间交换紊乱。指针空间未分配而导致系统随机给出个错误数据。地址相冲突导致的程序错误。这些都没有语法错误但是在调试中将引起乱码，是个重要的问题，而且会频繁出现。因此要多调试，思考以解决这些问题。在寻找下一结点时，寻找到最小权值边，将其两端的顶点信息及变的权值存储到辅助树组中。在设计解决这些问题的时候用多个for进行套嵌实现查找、判断。因为本程序使用的是prim算法，for循环的使用套嵌较复杂，因此在设计时要理清思路。时间、空间性能分析。根据程序中的循环语句可以判断出普利姆算法的时间复杂度为O(n2)。算法和图中边的数目无关，因此普利姆算法适合于求稠密网的最小生成树。因为在算法中运用了邻接矩阵的存储结构，在无向图中，邻接矩阵是对称的。所以仅需要存储上三角(下三角)的元素，因此需要n(n+1)个存储空间。六、测试441326566655521346.1对于上图测试结果如下所示：七、心得体会本程序是在MicrosoftVisualC++环境下运行，经过本人调试运行成功。运行过程时带有提示性语句。由于是求解图的最小生成树，因此先进行图的顶点数和边数的输入。然后对各个顶点进行顶点信息的输入。接着对各个边的起点、终点、权值进行输入。在其过程中若输入不存在的顶点时会有语句提示，并且重新输入。然后是选择是否输出所建图的的邻接矩阵，若输入有错误时会有提示语句，并重新选择。最后输出的是按各顶点为起点输出所有的最小生成树。八、附录（源程序）#include"stdio.h"#include"stdlib.h"#include"malloc.h"#defineMAX20typedefstruct{ intvexs[MAX];//顶点信息集合 intarcs[MAX][MAX];//各边的权值 intvexnum;//顶点数 intarcnum;//边数}MGraph;intLocateVex(intvexs[],intv){//确定结点是否存在intt; for(inti=0;i<MAX;i++)if(vexs[i]==v)t=i; returnt;}MGraphCreateMarph(MGraph&G){ intv1,v2,weight,i,j,k; printf("请输入无向图的顶点数和边数："); scanf("%d%d",&G.vexnum,&G.arcnum); for(i=0;i<G.vexnum;i++){//初始化邻接矩阵 for(j=0;j<G.vexnum;j++){ G.arcs[i][j]=0; }} for(i=0;i<G.vexnum;i++){ printf("第%d个顶点的序号：",i+1); scanf("%d",&G.vexs[i]); } printf("\n请你确定各条弧的信息\n"); for(k=0;k<G.arcnum;k++) {printf("请输入第%d弧的两个起始顶点和其权值为：",k+1);//输入一条边及依附的顶点及权值 for(;;){scanf("%d%d%d",&v1,&v2,&weight); if((v1>0&&v1<=G.vexnum)&&(v2>0&&v2<=G.vexnum)) break; else printf("输入有误，不存在该顶点，请重新输入^_^\n"); } i=LocateVex(G.vexs,v1);//找到两个结点在邻接矩阵中的位置 j=LocateVex(G.vexs,v2); G.arcs[i][j]=weight;//边的权值 G.arcs[j][i]=G.arcs[i][j];//置(v1,v2)成(v2,v1) } printf("\n"); returnG; }structclosed{ intadjvex;//依附于最小权值边在顶点集合U中的顶点 intlowcost;//存储最小边的权值};closedclosedge[MAX];voidMiniTree_PRIM(MGraphG,intu){ intk=u; inti,j; for(i=0;i<G.vexnum;i++)//初始化closedge数组，v={u} if(i!=k)//两个顶点不重合 {closedge[i].adjvex=u+1;//首先将u视为第一条边的第一个依附顶点 if(!G.arcs[k][i])//两点之间不连通 closedge[i].lowcost=-1; else closedge[i].lowcost=G.arcs[k][i];//调整closedge数组的最小代价lowcost为边上的权值 } closedge[k].lowcost=0; for(i=0;i<G.vexnum-1;i++){//★取其余G.vexnum-1个顶点，循环从此处开始，i无任何意义 for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0){//求出T的下一个结点，第K结点 k=j; break;} for(j=0;j<G.vexnum;j++) if(closedge[j].lowcost>0) if(closedge[j].lowcost<closedge[k].lowcost)//比较权值大小,从中找出权值最小的边 k=j; printf("%d>%d(%d)\n",closedge[k].adjvex,G.vexs[k],closedge[k].lowcost); closedge[k].lowcost=0;//将此第k个顶点并入U集中 for(j=0;j<G.vexnum;j++)////在顶点k并入U之后，更新closedge[i]，新顶点并入U后重新选择最小边 if(G.arcs[k][j]>0){ if(closedge[j].lowcost==-1){