数据结构课程设计实验报告(并查集

1、华南农业大学信息学院课程设计实验 学院数学与信息学院班级14网工1学号4姓名赖文杰实验题目设计性 综合性自我评价代码直观，有调理，按时完成，独立完成，实验报告详细，还添加了其他功能，不过注释不过详细，表达能力不好，部分代码直接照抄网上，总体良好。教师评语能够实现实验要求的功能 全部 部分算法有新意 有 一般程序运行通过 全部 部分 算法注释说明 完善 仅有功能说明接口参数说明 有 无按期上交文档资料及源程序 所有 部分独立完成实验 能 不能体现团队合作精神。 能够 不能成绩实验题目：并查集班级：14网络工程一班姓名：赖文杰学号：4完成日期：2015/9/30一 题目要求：1. 实验的要求：本次

2、实验题目要求是实现并查集的初始化、合并集合、查找节点所在集合和与并查集相关的应用的实现。2. 并查集的简介：在一些问题中，我们需要划分个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元集合，然后按一定顺序将属于同一组的元素所在的集合合并。期间要反复用到查找一个元素属于哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-findsets)3. 代码简介：（1） Find函数，用来查找某节点所在的集合，需要一个整形参数（节点的编号），返回一个整形值。（所在集合的头节点的编号）（2） min函数，用来连接输入的两个节点所在

3、的集合，需要两个整形参数（两个节点的编号），无返回值。（3） chushihua函数，用来创建新的并查集，需要两个整形参数（分别是节点的个数和连接节点的通道的数目），无返回值。（4） count函数，用来计算并查集含有集合的个数，需要一个整形参数（节点的个数），返回一个整形值。（并查集含有集合的个数）（5） 代码能实现并查集的创建，初始化，合并集合，查找节点所在集合和计算并查集中所含集合的数目。二 解题思路：1.创建两个数组pre和t，pre数组下标用于表示节点的编号，数组内容表示节点的上级。t用于标记独立块的根结点 2.首先定义出主函数的基本框架流程，用while和switch函数来实习功能

4、的选择3.由主函数中接收到参数N、M给chushihua函数，然后函数用for循环给pre数组赋值，使得并查集中每个节点都编好号而且每个节点自己成为一个集合，然后用mix函数把需要连接的节点连起来，创建出一个新的并查集。 4由主函数中接受到参数x给Find函数，函数通过对pre数组的下标是否和数组的内容相等，从而判断该节点是否是根节点，找到后根节点的编号返回给主函数。5.由主函数接受到参数x，y给mix函数，函数通过Find函数分别找到x和y的根节点，然后通过把y所在集合的根节点的数组值改成x所在集合根节点的数组下标，从而使得x所在集合的根节点成为y所在集合的根结点的上级。从而把两个集合合并。

5、 6.由主函数接受到参数N给count函数，用for循环把各个节点遍历，如果第i个节点是根节点，就把第i个节点所在的t数组的值赋值为1，否则为0，然后用ans标志t数组中1的个数。最后把ans返回给主函数。 该代码用了线性表的数据结构。三 调试分析：1 代码演示：生成的并查集图为：合并后并查集图为：初始化后并查集的图：合并后并查集的图：2. 调试遇到的问题：基本没遇到什么大问题，只是有很多输入语句后面没加分号，输入语句没加取地址之类的小错误。 3. 经验体会：这是第一次自己在没有人指点的情况下自己去学习一种数据结构，刚刚开始会觉得可能会很难，抱着恐惧的心情去上网查找资料，不过在找到资料后，认真

6、阅读了一遍，发现没有想象中恐怖和困难，挺简单的，看了几遍就懂了并查集是什么和并查集的基本操作，觉得自己还是挺厉害的（自夸）。在我们计算机类，自学是很重要的，计算机专业知识更新快，书本上的知识只是基础而且很微不足道，我们要学会自己查找资料自学，不要恐惧自学，没试过就不知道难易程度，不要被听起来很可怕名字吓到，就像这次，自学了才发现原来并查集没有自己想象的那么困难。四 相关应用：题目表述：设地图中有若干做城镇，每个城镇可以看作一个点，城镇间有若干条路，试求还需要多少条路才能使全地图联通。 输入格式 第一行输入两个整数个n，m，表述有n个城镇，m条路。 接下来m行，每行输入每条路联通的城镇。 输出格

7、式 输出联通全地图所需路的条数。 输入样例 5 3 1 2 2 3 4 5 输出样例 1 解题代码：#include #include #include int pre1000 ;using namespace std;int find(int x) int r=x; while (prer !=r) r=prer ; int i=x; int j; while(i!=r) j=prei ; prei =r; i=j; return r;int main() int n,m,p1,p2,i,total,f1,f2; while(scanf(%d,&n) & n) /读入n，如果n为0，结束 /

8、刚开始的时候，有n个城镇，一条路都没有 /那么要修n-1条路才能把它们连起来 total=n-1; /每个点互相独立，自成一个集合，从1编号到n /所以每个点的上级都是自己 for(i=1;i=n;i+) prei =i; /共有m条路 scanf(%d,&m); while(m-) /下面这段代码，其实就是join函数，只是稍作改动以适应题目要求 /每读入一条路，看它的端点p1，p2是否已经在一个连通分支里了 scanf(%d %d,&p1,&p2); f1=find(p1); f2=find(p2); /如果是不连通的，那么把这两个分支连起来 /分支的总数就减少了1，还需建的路也就减了1

9、if(f1!=f2) pref2 =f1; total-; /如果两点已经连通了，那么这条路只是在图上增加了一个环 /对连通性没有任何影响，无视掉 /最后输出还要修的路条数 printf(%dn,total); return 0;五 附录：源代码：#include#include #include #includeusing namespace std;int pre1050; /用于存储节点bool t1050; /t 用于标记独立块的根结点int Find(int x) /查找节点所在集合int r=x;while(r!=prer)r=prer;int i=x,j;while(prei!=

10、r)j=prei;prei=r;i=j;return r;void mix(int x,int y) /合并结合int fx=Find(x),fy=Find(y);if(fx!=fy)prefy=fx;int chushihua(int N,int M) /初始化int a,b,i; /N节点的个数 M连接通道的数目for(i=1;i=N;i+)prei=i;for(i=1;i=M;i+) /吸收并整理数据 printf(输入第%d条通道连接的两个个节点：,i);scanf(%d%d,&a,&b);mix(a,b);int count(int N) /有多少个集合 int ans,i;mems

11、et(t,0,sizeof(t);for(i=1;i=N;i+) /标记根结点tFind(i)=1;for(ans=0,i=1;i=N;i+)if(ti)ans+; return ans;int main() int a,b,c,d,N,M,e,f; printf(首先创建一个并查集n); printf(输入并查集的节点个数：); scanf(%d,&N); printf(输入并查集中连接节点的通道的个数：); scanf(%d,&M); chushihua(N,M); printf(创建完毕n); while(d!=0) printf(n请输入要执行的功能n1.初始化n2.合并结合n); p

12、rintf(3.找节点所在集合n4.并查集中集合的个数n0.退出nn); scanf(%d,&d); switch(d) case 1:printf(n); printf(输入并查集的节点个数：); scanf(%d,&N); printf(输入并查集中连接节点的通道的个数：); scanf(%d,&M); chushihua(N,M);break; case 2:printf(n); printf(输入通道连接的两个个节点：); scanf(%d%d,&a,&b); mix(a,b); printf(合并成功n);break; case 3:printf(n); while(c!=0) printf(请输入要查找的节点,输入0退出查找：);