最小生成树问题综合程序设计_数据结构

1、目 录摘要11 引言22系统分析52.1总体设计方案32.2程序思路流程图43源代码53.1程序演示8总结10致谢11参考文献12附录12- 11 -摘 要假设在n个城市之间建立通信联络网，则连通n个城市只需要n-1条线路。这时，自然会考虑这样一个问题，如何在最节约经费的前提下建立这个通信网。此课题便是研究这样一个问题，要在n(n-1)/2条线路中选择n-1条，以使得总的耗费最少。我们可以用连通网来表示n个城市以及n个城市可能设置的通信线路，其中网的顶点表示城市，边表示线路，赋予边的权值表示相应的代价，对于n个顶点的联通网可以建立许多不同的生成树，每一棵生成树都可以是一个通信网。现在，我们要选

2、择这样一课生成树，也就是使得总的耗费最少。我们用克鲁斯卡尔算法来寻找这样一棵树。关键词：耗费最少，最小生成树，克鲁斯卡尔算法1 引 言 1. 1问题的提出以前的操作系统等系统软件主要是由汇编语言编写的（包括操作系统在内）。由于汇编语言依赖于计算机硬件，程序的可读性和可移植性都比较差。为了提高可读性和可移植性，最好改用高级语言，但一般高级语言难以实现汇编语言的某些功能（汇编语言可以直接对硬件进行操作，例如，对内存地址的操作、位操作等）。人们设想能否找到一种既具有一般高级语言特性，又具有低级语言特性的语言，集它们的优点于一身。于是，语言就在这种情况下应运而生了。1.2 C语言C语言既有高级语言的特

3、点，又具有汇编语言的特点；既是一个成功的系统设计语言，有时一个使用的程序设计语言；既能用来编写不依赖计算机硬件的应用程序，又能用来编写各种系统程序；是一种受欢迎、应用广泛的程序设计语言。1.3 C语言发展过程1973年，美国贝尔实验室的D.M.RITCHIE在B语言的基础上最终设计出了一种新的语言，他取了BCPL的第二个字母作为这种语言的名字，这就是C语言。1977年Dennis M.Ritchie 发表了不依赖于具体机器系统的C语言编译文本可移植的C语言编译程序。1978年Brian W.Kernighian和Dennis M.Ritchie出版了名著The C Programming La

4、nguage，从而使C语言成为目前世界上流行最广泛的高级程序设计语言。1.4任务与分析 本任务是属于图的应用，最小生成树问题。对于具有N个顶点的加权无向图，设计一个利用Kruskal算法找出最小生成树的程序。要求使用链表将所有邻接边按加权值递增顺序连接起来（直到产生N-1个邻接边）。链表结点包含两个顶点、权值、指针。2 系统分析2. 1整体设计方案 假设 WN=(V,E) 是一个含有n个顶点的连通网，则按照克鲁斯卡尔算法构造最小生成树的过程为：先构造一个只含 n个顶点，而边集为空的子图，若将该子图中各个顶点看成是各棵树上的根结点，则它是一个含有n棵树的一个森林。之后，从网的边集E中选取一条权值

5、最小的边，若该条边的两个顶点分属不同的树，则将其加入子图，也就是说，将这两个顶点分别所在的两棵树合成一棵树；反之，若该条边的两个顶点已落在同一棵树上，则不可取，而应该取下一条权值最小的边再试之。依次类推，直至森林中只有一棵树，也即子图中含有n-1条边为止.。加入子图 2.2思路流程图建立n个顶点边集为空的子图选取一条权值最小的边分属不同的树？属于加入子图不属于不可取合成新的一棵树结束程序思路流程图3程序源代码#include<stdio.h> #include<stdlib.h> /边结点 typedef struct char v1; char v2; int wei

6、ght; /权 Edge;/ 边表结构 typedef struct Edge space100; int Elength;/边条数 Headtype; /顶点结构 typedef struct char v; int flag; Dgree;/顶点表结构typedef struct Dgree biao20; int Glength; /点个数Mark; /输入顶点 void InitMark(Mark &M,int x)int j; M.Glength=x; printf("请依次输入这些点:n"); for(j=1;j<=x;j+) scanf(&quo

7、t;%s",&M.biaoj.v); M.biaoj.flag=-1; /初始化顶点标志 /输入边关系 void InitHeadType(Headtype &H,int y)int k; H.Elength=y; for(k=1;k<=y;k+) printf("请输入边的关系:n"); scanf("%s%s%d",&H.spacek.v1,&H.spacek.v2,&H.spacek.weight); /建立顶点表 void HeadAdjust(Headtype &H,int s,i

8、nt m) Edge rc; int p; rc=H.spaces; for(p=2*s;p<=m;p*=2) if(p<m&&(H.spacep.weight<H.spacep+1.weight) +p; if(rc.weight>H.spacep.weight) break; H.spaces=H.spacep; s=p; H.spaces=rc; /建立边表 void HeadSort(Headtype &H) int q; Edge rb; for(q=H.Elength/2;q>0;-q) HeadAdjust(H,q,H.Ele

9、ngth); for(q=H.Elength;q>1;-q) rb=H.space1; H.space1=H.spaceq; H.spaceq=rb; HeadAdjust(H,1,q-1); void main () int Gnumber,Enumber,a,b,c; printf("请输入点的个数:n"); scanf("%d",&Gnumber); printf("请输入边数:n"); scanf("%d",&Enumber); Headtype H; Mark M; Dgree e1

10、,e2; InitMark(M,Gnumber); InitHeadType(H,Enumber); HeadSort(H); printf("输出最小生成树;n"); for(a=1;a<=Enumber;a+) for(b=1;b<=Gnumber;b+) if(M.biaob.v=H.spacea.v1) e1=M.biaob; break; for(c=1;c<=Gnumber;c+) if(M.biaoc.v=H.spacea.v2) e2=M.biaoc; break; while(e1.flag!=-1) b=e1.flag; e1=M.bi

11、aoe1.flag; while(e2.flag!=-1) c=e2.flag; e2=M.biaoe2.flag; if(e2.v!=e1.v) M.biaob.flag=c; printf("(%c,%c):%dn",H.spacea.v1,H.spacea.v2,H.spacea.weight); 31程序演示：对于所有执行过程，通过图片最好说明问题了：程序开始如 图2 所示：图2 把每个城市当成一个点，要在几个城市之间建立通信连通就输入几个点，如现在我们输入6个点。 图3现在输入这些点之间有多少条边，即各个城市之间有几条线路，现在我们输入10条边。图4现在我们依次输

12、入这些点，即这些城市。图5现在我们输入这些边的关系，也就是权值问题，在通信连通中就是代价的多少了，还有就是这些点之间知否连通。如：图6生成的最小生成树如下：图7结 论 课程设计做完了，一个多星期的时间花在了上面，刚看题目还觉得没有什么问题，可是这正做了才知道问题大了。细节等各方面没有考虑到的问题都出现了。做课程设计的过程就是一个不断调试不断改进程序的过程。经过一个多星期的上机实践学习，加上自己课外的时间，使我对C语言有了更进一步的认识和了解，要想学好它要重在实践，要通过不断的上机操作才能更好地学习它，通过实践，我也发现我的好多不足之处，对C语言学习平时只是马马虎虎的过去了，真正自己去解决实际问题的时候才会发现自己学的多么糟糕，通过课程设计对自己的编程能力也有所提高；再有对C语言的一些标准库函数不太了解，还有对函数调用的正确使用不够熟悉，还有对C语言中经常出现的错误也不了解，通过实践，使我在这几个方面的认识有所提高。通过实践的学习，我认到学好计算机要重视实践操作，不仅仅是学习C语言，还是其它的语言，以及其它的计算机方面的知识都要重在实践，所以后在学习过程中，我会更加注重实践操作能力的培养，无论学习什么，亲自动手去做了才能得到最深刻的体会。致 谢首先需要感谢的是指导老师严长龙老师，在他的督促下才能按时完成这个课程设计，并且对于各种提出的问题很热情的解答。再者需要感谢的