数据结构课程设计-最小生成树讲述.docx

《数据结构》期末课程设计 题 目 第8题：最小生成树问题 学 院 计算机学院 专 业 班 别 学 号 姓 名 陈聪 2015年7月6日 一、需求分析 1、问题描述 若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。 2、基本要求 （1）利用克鲁斯卡尔算法求网的最小生成树。 （2）实现并查集。以此表示构造生成树过程中的连通分量。 （3）以文本形式输出生成树中各条边以及他们的权值。 3、实现提示 通讯线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用C语言提供的随机数函数产生。 图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边(带权)的数组即边集数组表示图。 二、详细设计 根据课设题目要求，拟将整体程序分为三大模块，分别是：图的存储结构，并查集的实现，克鲁斯卡尔算法的实现。 1、边集数组的类型定义： typedef struct { int x, y; int w; }edge; x表示起点，y表示终点，w为权值。 2、并查集功能的实现由以下函数实现： Make_Set(int x)初始化集合； Find_Set(int x) 查找x元素所在的集合,回溯时压缩路径； Union(int x, int y, int w)合并x,y所在的集合。 3、克鲁斯卡尔算法的实现 该算法的实现位于主函数中： qsort(e, n, sizeof(edge), cmp); //将边排序 printf(最小生成树的各条边及权值为：\n); for (i = 0; i n; i++) { x = Find_Set(e[i].x); y = Find_Set(e[i].y); if (x != y ) { printf(%c - %c : %d\n, e[i].x + A, e[i].y + A, e[i].w); Union(x, y, e[i].w); } } 4、设计中还包含以下函数： （1）/* 比较函数，按权值(相同则按x坐标)非降序排序 */ int cmp(const void *a, const void *b) { if ((*(edge *)a).w == (*(edge *)b).w) { return (*(edge *)a).x - (*(edge *)b).x; } return (*(edge *)a).w - (*(edge *)b).w; } （2）快排函数qsort,包含在stdlib.h头文件里 qsort(e, n, sizeof(edge), cmp); （3）C语言提供的随机数函数srand( unsigned int seed ); 使用随机数函数如下： srand( (unsigned)time( NULL ) ); for( i = 0; i n;i++ ) { e[i].w=rand()%100+1; e[i].x = chx - A;if(chy==h+48) chx++; e[i].y = (chy++) - A; if(chy==h+49) chy=chx+1; Make_Set(i); } 输出1～100之间的随机数，使用rand()%100+1。 5、主程序的流程图 三、调试分析 调试过程中遇到的问题： 随机产生权值时，通过边数不能确定起点和终点。 解决：通过顶点数对所有边取随机数。 四、用户使用说明及测试结果 1、打开界面： （1）人为输入权值，输入1，回车： 输入7，回车： 输入边的信息及结果如下： （2）随机生成权值，输入0： 输入顶点数5，结果如下： 五、经验和体会 通过本次课程设计，我学会了利用克鲁斯卡尔算法求最小生成树。另外学会了利用随机函数产生随机数，以及课本没有提到的边集数组的定义和使用。 六、附录源代码 #include stdio.h #include stdlib.h #include time.h #define MAX