数据结构课程设计-最小生成树.doc_第1页
数据结构课程设计-最小生成树.doc_第2页
数据结构课程设计-最小生成树.doc_第3页
数据结构课程设计-最小生成树.doc_第4页
数据结构课程设计-最小生成树.doc_第5页
已阅读5页,还剩4页未读 继续免费阅读

下载本文档

版权说明:本文档由用户提供并上传,收益归属内容提供方,若内容存在侵权,请进行举报或认领

文档简介

数据结构期末课程设计题 目 第8题:最小生成树问题 学 院 计算机学院 专 业 班 别 学 号 姓 名 陈聪 2015年7月6日一、需求分析 1、问题描述 若要在n个城市之间建设通讯网络,只需要架设n-1条线路即可。如何以最低的经济代价建设这个通讯网,是一个网的最小生成树问题。 2、基本要求(1)利用克鲁斯卡尔算法求网的最小生成树。(2)实现并查集。以此表示构造生成树过程中的连通分量。(3)以文本形式输出生成树中各条边以及他们的权值。 3、实现提示通讯线路一旦建立,必然是双向的。因此,构造最小生成树的网一定是无向网。设图的顶点数不超过30个,并为简单起见,网中边的权值设成小于100的整数,可利用C语言提供的随机数函数产生。图的存储结构的选取应和所作操作向适应。为了便于选择权值最小的边,此题的存储结构既不选用邻接矩阵的数组表示法,也不选用邻接表,而是以存储边(带权)的数组即边集数组表示图。2、 详细设计根据课设题目要求,拟将整体程序分为三大模块,分别是:图的存储结构,并查集的实现,克鲁斯卡尔算法的实现。1、边集数组的类型定义:typedef structint 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(ei.x);y = Find_Set(ei.y);if (x != y ) printf(%c - %c : %dn, ei.x + A, ei.y + A, ei.w);Union(x, y, ei.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+ ) ei.w=rand()%100+1; ei.x = chx - A;if(chy=h+48) chx+;ei.y = (chy+) - A;if(chy=h+49) chy=chx+1;Make_Set(i); 输出1100之间的随机数,使用rand()%100+1。开始5、 主程序的流程图 选择手动或随机输入权值 输入顶点数输入边的信息存储边的信息随机产生权值并存储边升序排序判断是否回路,不回路则输出结束三、调试分析调试过程中遇到的问题:随机产生权值时,通过边数不能确定起点和终点。解决:通过顶点数对所有边取随机数。四、用户使用说明及测试结果1、打开界面:(1) 人为输入权值,输入1,回车:输入7,回车:输入边的信息及结果如下:(2)随机生成权值,输入0:输入顶点数5,结果如下:五、经验和体会通过本次课程设计,我学会了利用克鲁斯卡尔算法求最小生成树。另外学会了利用随机函数产生随机数,以及课本没有提到的边集数组的定义和使用。六、附录源代码#include #include #include time.h #define MAX 435 /* 定义边(x,y),权为w */typedef structint x, y;int w;edge; edge eMAX;/* rankx表示x的秩 */int rankMAX;/* fatherx表示x的父节点 */int fatherMAX; /* 比较函数,按权值(相同则按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; /* 初始化集合 */void Make_Set(int x)fatherx = x;rankx = 0; /* 查找x元素所在的集合,回溯时压缩路径 */int Find_Set(int x)while(fatherx)x=fatherx;return x; /* 合并x,y所在的集合 */void Union(int x, int y, int w)if (x = y) return;/* 将秩较小的树连接到秩较大的树后 */if (rankx ranky)fathery = x;elseif (rankx = ranky)ranky+;fatherx = y; /* 主函数 */int main()printf(*最小生成树问题:n); int i, n,h,k=0;int x, y;char chx, 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, &ei.w);getchar();ei.x = chx - A;ei.y = chy - A;Make_Set(i); elseprintf(请输入顶点数(=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+ ) ei.w=rand()%100+1; ei.x = chx - A;if(chy=h+48) chx+;ei.y = (chy+) - A;if(chy=h+49) chy=chx+1;Make_Set(i); printf(随机生成的各条边及权值为:n); for (i = 0; i n; i+) printf(%c - %c : %dn, ei.x + A, ei.y + A, ei.w); /* 将边排序 */qsort(e, n, sizeof(edge), cmp); printf(最小生

温馨提示

  • 1. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等,如果需要附件,请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸,网页内容里面会有图纸预览,若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对用户上传分享的文档内容本身不做任何修改或编辑,并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容,请与我们联系,我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论