数据结构课程设计报告-最小生成树

wordword范文《数据结构》期末课程设计题目第8题：最小生成树问题学 院计算机学院TOC\o"1-5"\h\z专 业班 另I学 号姓 名—陈聪2015年7月6日一、需求分析1、问题描述若要在n个城市之间建设通讯网络，只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网，是一个网的最小生成树问题。2、基本要求（1）利用克鲁斯卡尔算法求网的最小生成树。（2）实现并查集。以此表示构造生成树过程中的连通分量。（3）以文本形式输出生成树中各条边以及他们的权值。3、实现提示通讯线路一旦建立，必然是双向的。因此，构造最小生成树的网一定是无向网。设图的顶点数不超过30个，并为简单起见，网中边的权值设成小于100的整数，可利用。语言提供的随机数函数产生。图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边，此题的存储结构既不选用邻接矩阵的数组表示法，也不选用邻接表，而是以存储边（带权）的数组即边集数组表示图。二、详细设计根据课设题目要求，拟将整体程序分为三大模块，分别是：图的存储结构，并查集的实现，克鲁斯卡尔算法的实现。1、边集数组的类型定义：typedefstruct{intx,y;intw;}edge;x表示起点，y表示终点，w为权值。2、并查集功能的实现由以下函数实现：Make_Set(intx)初始化集合；Find_Set(intx)查找x元素所在的集合，回溯时压缩路径；Union(intx,inty,intw)合并x,y所在的集合。3、克鲁斯卡尔算法的实现该算法的实现位于主函数中：qsort(e,n,sizeof(edge),cmp);//将边排序口「皿{式"最小生成树的各条边及权值为：\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坐标)非降序排序*/intcmp(constvoid*a,constvoid*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(unsignedintseed);使用随机数函数如下：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、打开界面：F最小生成树问题:人为输入权值请输入工，随机生成权值请输入目：（1）人为输入权值，输入1，回车：产最小生成树问题:人为输入权值请输入工，随机生成权值请输入目：请输入边的条数（小于436）：输入7，回车：座：；卜生成杈寸句题:人为输入权值请输入工,随机生成极值请输入。.请输入边的余数〔小于436）=皤输入边的信息〔起点,终点,权值（弋骸〉）分别用空格隔开二输入边的信息及结果如下：:最小生成树问题：1为输入权值请输入1,随机生成权值请输入用：1,输入边的条数（小于吧6）：卷揄入边的信息（起点，终点，板值y则）分别用空格隔开二kb3kd8ke10bd6de9bc15pe12最小生成树的各条边及权值为：a—b：3b-d：6d-e=9c—e=12Processexitedwitlireturnvalue0Pressanykeytocontinue・・・・（2）随机生成权值，输入0：，最小生成树问题:1为输入权值请输入L随机生成权值请输入乱*输入顶点数t<=30）=输入顶点数5，结果如下：人为输入权值请输入3随机生成权值请输入目:0常输入顶点数(<=30)=露机生成的各条边及权值为：-2：27-3：44-4：40-5：792-3:9-4：57-5：87-4：38-5：84-5：100最小生成树的各条边及权值为.2-3:91-2：273-4：381-5：79Processexitedwithreturnualue0五、经验和体会通过本次课程设计，我学会了利用克鲁斯卡尔算法求最小生成树。另外学会了利用随机函数产生随机数，以及课本没有提到的边集数组的定义和使用。六、附录源代码#include<stdio.h>#include<stdlib.h>#include"time.h"#defineMAX435/*定义边(x,y)，权为w*/typedefstruct{intx,y;intw;}edge;edgee[MAX];/*rank[x]表示x的秩*/intrank[MAX];/*father[x]表示x的父节点*/intfather[MAX];/*比较函数，按权值(相同则按x坐标)非降序排序*/intcmp(constvoid*a,constvoid*b){if((*(edge*)a).w==(*(edge*)b).w){return(*(edge*)a).x-(*(edge*)b).x;}return(*(edge*)a).w-(*(edge*)b).w;}/*初始化集合*/voidMake_Set(intx){father[x]=x;rank[x]=0;}/*查找x元素所在的集合，回溯时压缩路径*/intFind_Set(intx){while(father[x]){x=father[x];}returnx;}/*合并x,y所在的集合*/voidUnion(intx,inty,intw){if(x==y)return;/*将秩较小的树连接到秩较大的树后*/if(rank[x]>rank[y]){father[y]=x;}else{if(rank[x]==rank[y]){rank[y]++;}father[x]=y;}}/*主函数*/intmain(){口「皿t式"*最小生成树问题：\n");inti,n,h,k=0;intx,y;charchx,chy;printf("\n人为输入权值请输入1，随机生成权值请输入0:\n");scanf("%d",&k);if(k==1){/*读取边的数目*/printf("请输入边的条数(小于436):\n");scanf("%d",&n);getchar();/*读取边信息并初始化集合*/printf("请输入边的信息(起点，终点，权值(<100))分别用空格隔开：\n");for(i=0;i<n;i++){scanf("%c%c%d",&chx,&chy,&e[i].w);getchar();e[i].x=chx-'A';e[i].y=chy-'A';Make_Set(i);}}else{printf("请输入顶点数(<=30):\n");scanf("%d",&h);getchar();srand((unsigned)time(NULL));n=(h-1)*h/2;chx=49;chy=50;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);}printf("随机生成的各条边及权值为：\n");for(i=0;i<n;i++){printf("%c-%c:%d\n",e[i].x+'A',e[i].y+'A',e[i].w);}}/*将边排序*/qsort(e,n,sizeof(edge),