《数据结构》期末课程设计题目第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 Array三、调试分析调试过程中遇到的问题：随机产生权值时，通过边数不能确定起点和终点。
解决：通过顶点数对所有边取随机数。
四、用户使用说明及测试结果1、打开界面：（1）人为输入权值，输入1，回车：输入7，回车：输入边的信息及结果如下：（2）随机生成权值，输入0：输入顶点数5，结果如下：五、经验和体会通过本次课程设计，我学会了利用克鲁斯卡尔算法求最小生成树。
另外学会了利用随机函数产生随机数，以及课本没有提到的边集数组的定义和使用。
六、附录源代码#include <stdio.h>#include <stdlib.h>#include "time.h"#define MAX 435/* 定义边(x,y)，权为w */typedef struct{int x, y;int w;}edge;edge e[MAX];/* rank[x]表示x的秩*/int rank[MAX];/* father[x]表示x的父节点*/int father[MAX];/* 比较函数，按权值(相同则按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){father[x] = x;rank[x] = 0;}/* 查找x元素所在的集合,回溯时压缩路径*/int Find_Set(int x){while(father[x]){x=father[x];}return x;}/* 合并x,y所在的集合*/void Union(int x, int y, int w){if (x == y) return;/* 将秩较小的树连接到秩较大的树后*/if (rank[x] > rank[y]){father[y] = x;}else{if (rank[x] == rank[y]){rank[y]++;}father[x] = 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, &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), 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);}}return 0;}。