欢迎来到天天文库
浏览记录
ID:49613300
大小:134.50 KB
页数:9页
时间:2020-03-02
《数据结构课程设计报告-最小生成树.doc》由会员上传分享,免费在线阅读,更多相关内容在行业资料-天天文库。
1、.《数据结构》期末课程设计题目第8题:最小生成树问题学院计算机学院专业班别学号姓名陈聪2015年7月6日word范文.一、需求分析1、问题描述若要在n个城市之间建设通讯网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网,是一个网的最小生成树问题。2、基本要求(1)利用克鲁斯卡尔算法求网的最小生成树。(2)实现并查集。以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中各条边以及他们的权值。3、实现提示通讯线路一旦建立,必然是双向的。因此,构造最小生成树的网一定是无向网。设图的顶点数不超过30个,并为简单起见
2、,网中边的权值设成小于100的整数,可利用C语言提供的随机数函数产生。图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边,此题的存储结构既不选用邻接矩阵的数组表示法,也不选用邻接表,而是以存储边(带权)的数组即边集数组表示图。二、详细设计根据课设题目要求,拟将整体程序分为三大模块,分别是:图的存储结构,并查集的实现,克鲁斯卡尔算法的实现。1、边集数组的类型定义:typedefstruct{intx,y;intw;}edge;x表示起点,y表示终点,w为权值。2、并查集功能的实现由以下函数实现:Make_Set(intx)初始
3、化集合;Find_Set(intx)查找x元素所在的集合,回溯时压缩路径;Union(intx,inty,intw)合并x,y所在的集合。word范文.3、克鲁斯卡尔算法的实现该算法的实现位于主函数中:qsort(e,n,sizeof(edge),cmp);//将边排序printf("最小生成树的各条边及权值为:");for(i=0;i4、].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语言提供的随机数函5、数srand(unsignedintseed);使用随机数函数如下:word范文.srand((unsigned)time(NULL));for(i=0;i6、储边升序排序判断是否回路,不回路则输出结束三、调试分析调试过程中遇到的问题:随机产生权值时,通过边数不能确定起点和终点。解决:通过顶点数对所有边取随机数。word范文.四、用户使用说明及测试结果1、打开界面:(1)人为输入权值,输入1,回车:输入7,回车:输入边的信息及结果如下:word范文.(2)随机生成权值,输入0:输入顶点数5,结果如下:五、经验和体会通过本次课程设计,我学会了利用克鲁斯卡尔算法求最小生成树。另外学会了利用随机函数产生随机数,以及课本没有提到的边集数组的定义和使用。六、附录源代码#include#7、include#include"time.h"#defineMAX435/*定义边(x,y),权为w*/typedefstruct{intx,y;intw;word范文.}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){retu8、rn(*(edge*)a).x-(*(edge*)b).x;}return(*(edge*)a).w-(*(edge*)b).w;}/*初始化集合*/voidMake_Set(intx){father[x]
4、].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语言提供的随机数函
5、数srand(unsignedintseed);使用随机数函数如下:word范文.srand((unsigned)time(NULL));for(i=0;i6、储边升序排序判断是否回路,不回路则输出结束三、调试分析调试过程中遇到的问题:随机产生权值时,通过边数不能确定起点和终点。解决:通过顶点数对所有边取随机数。word范文.四、用户使用说明及测试结果1、打开界面:(1)人为输入权值,输入1,回车:输入7,回车:输入边的信息及结果如下:word范文.(2)随机生成权值,输入0:输入顶点数5,结果如下:五、经验和体会通过本次课程设计,我学会了利用克鲁斯卡尔算法求最小生成树。另外学会了利用随机函数产生随机数,以及课本没有提到的边集数组的定义和使用。六、附录源代码#include#7、include#include"time.h"#defineMAX435/*定义边(x,y),权为w*/typedefstruct{intx,y;intw;word范文.}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){retu8、rn(*(edge*)a).x-(*(edge*)b).x;}return(*(edge*)a).w-(*(edge*)b).w;}/*初始化集合*/voidMake_Set(intx){father[x]
6、储边升序排序判断是否回路,不回路则输出结束三、调试分析调试过程中遇到的问题:随机产生权值时,通过边数不能确定起点和终点。解决:通过顶点数对所有边取随机数。word范文.四、用户使用说明及测试结果1、打开界面:(1)人为输入权值,输入1,回车:输入7,回车:输入边的信息及结果如下:word范文.(2)随机生成权值,输入0:输入顶点数5,结果如下:五、经验和体会通过本次课程设计,我学会了利用克鲁斯卡尔算法求最小生成树。另外学会了利用随机函数产生随机数,以及课本没有提到的边集数组的定义和使用。六、附录源代码#include#
7、include#include"time.h"#defineMAX435/*定义边(x,y),权为w*/typedefstruct{intx,y;intw;word范文.}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){retu
8、rn(*(edge*)a).x-(*(edge*)b).x;}return(*(edge*)a).w-(*(edge*)b).w;}/*初始化集合*/voidMake_Set(intx){father[x]
此文档下载收益归作者所有