搜索
华南农业大学信息学院课程设计实验学院数学与信息学院班级14网工1学号201430350114姓名赖文杰实验题目■设计性□综合性自我评价代码直观，有调理，按时完成，独立完成，实验报告详细，还添加了其他功能，不过注释不过详细，表达能力不好，部分代码直接照抄网上，总体良好。教师评语能够实现实验要求的功能√全部□部分算法有新意√有□一般程序运行通过√全部□部分算法注释说明√完善□仅有功能说明接口参数说明√有□无按期上交文档资料及源程序√所有□部分独立完成实验√能□不能体现团队合作精神。√能够□不能成绩实验题目：并查集班级：14网络工程一班姓名：赖文杰学号：201430350114完成日期：2015/9/30一．题目要求：1.实验的要求：本次实验题目要求是实现并查集的初始化、合并集合、查找节点所在集合和与并查集相关的应用的实现。2.并查集的简介：在一些问题中，我们需要划分ｎ个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元集合，然后按一定顺序将属于同一组的元素所在的集合合并。期间要反复用到查找一个元素属于哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-findsets)3.代码简介：（1）Find函数，用来查找某节点所在的集合，需要一个整形参数（节点的编号），返回一个整形值。（所在集合的头节点的编号）（2）min函数，用来连接输入的两个节点所在的集合，需要两个整形参数（两个节点的编号），无返回值。（3）chushihua函数，用来创建新的并查集，需要两个整形参数（分别是节点的个数和连接节点的通道的数目），无返回值。（4）count函数，用来计算并查集含有集合的个数，需要一个整形参数（节点的个数），返回一个整形值。（并查集含有集合的个数）（5）代码能实现并查集的创建，初始化，合并集合，查找节点所在集合和计算并查集中所含集合的数目。二．解题思路：1.创建两个数组pre和t，pre数组下标用于表示节点的编号，数组内容表示节点的上级。t用于标记独立块的根结点2.首先定义出主函数的基本框架流程，用while和switch函数来实习功能的选择3.由主函数中接收到参数N、M给chushihua函数，然后函数用for循环给pre数组赋值，使得并查集中每个节点都编好号而且每个节点自己成为一个集合，然后用mix函数把需要连接的节点连起来，创建出一个新的并查集。4．由主函数中接受到参数x给Find函数，函数通过对pre数组的下标是否和数组的内容相等，从而判断该节点是否是根节点，找到后根节点的编号返回给主函数。5.由主函数接受到参数x，y给mix函数，函数通过Find函数分别找到x和y的根节点，然后通过把y所在集合的根节点的数组值改成x所在集合根节点的数组下标，从而使得x所在集合的根节点成为y所在集合的根结点的上级。从而把两个集合合并。6.由主函数接受到参数N给count函数，用for循环把各个节点遍历，如果第i个节点是根节点，就把第i个节点所在的t数组的值赋值为1，否则为0，然后用ans标志t数组中1的个数。最后把ans返回给主函数。该代码用了线性表的数据结构。三．调试分析：1．代码演示：生成的并查集图为：合并后并查集图为：初始化后并查集的图：合并后并查集的图：2.调试遇到的问题：基本没遇到什么大问题，只是有很多输入语句后面没加分号，输入语句没加取地址之类的小错误。3.经验体会：这是第一次自己在没有人指点的情况下自己去学习一种数据结构，刚刚开始会觉得可能会很难，抱着恐惧的心情去上网查找资料，不过在找到资料后，认真阅读了一遍，发现没有想象中恐怖和困难，挺简单的，看了几遍就懂了并查集是什么和并查集的基本操作，觉得自己还是挺厉害的（自夸）。在我们计算机类，自学是很重要的，计算机专业知识更新快，书本上的知识只是基础而且很微不足道，我们要学会自己查找资料自学，不要恐惧自学，没试过就不知道难易程度，不要被听起来很可怕名字吓到，就像这次，自学了才发现原来并查集没有自己想象的那么困难。四．相关应用：题目表述：设地图中有若干做城镇，每个城镇可以看作一个点，城镇间有若干条路，试求还需要多少条路才能使全地图联通。输入格式第一行输入两个整数个n，m，表述有n个城镇，m条路。接下来m行，每行输入每条路联通的城镇。输出格式输出联通全地图所需路的条数。输入样例53122345输出样例1解题代码：#includeiostream#includestdio.h#includestdlib.hintpre[1000];usingnamespacestd;intfind(intx){intr=x;while(pre[r]!=r)r=pre[r];inti=x;intj;while(i!=r){j=pre[i];pre[i]=r;i=j;}returnr;}intmain(){intn,m,p1,p2,i,total,f1,f2;while(scanf(%d,&n)&&n)//读入n，如果n为0，结束{//刚开始的时候，有n个城镇，一条路都没有//那么要修n-1条路才能把它们连起来total=n-1;//每个点互相独立，自成一个集合，从1编号到n//所以每个点的上级都是自己for(i=1;i=n;i++){pre[i]=i;}//共有m条路scanf(%d,&m);while(m--){//下面这段代码，其实就是join函数，只是稍作改动以适应题目要求//每读入一条路，看它的端点p1，p2是否已经在一个连通分支里了scanf(%d%d,&p1,&p2);f1=find(p1);f2=find(p2);//如果是不连通的，那么把这两个分支连起来//分支的总数就减少了1，还需建的路也就减了1if(f1!=f2){pre[f2]=f1;total--;}//如果两点已经连通了，那么这条路只是在图上增加了一个环//对连通性没有任何影响，无视掉}//最后输出还要修的路条数printf(%d\n,total);}return0;}五．附录：源代码：#includeiostream#includestdio.h#includestdlib.h#includecstringusingnamespacestd;intpre[1050];//用于存储节点boolt[1050];//t用于标记独立块的根结点intFind(intx)//查找节点所在集合{intr=x;while(r!=pre[r])r=pre[r];inti=x,j;while(pre[i]!=r){j=pre[i];pre[i]=r;i=j;}returnr;}voidmix(intx,inty)//合并结合{intfx=Find(x),fy=Find(y);if(fx!=fy){pre[fy]=fx;}}intchushihua(intN,intM)//初始化{inta,b,i;//N节点的个数M连接通道的数目for(i=1;i=N;i++)pre[i]=i;for(i=1;i=M;i++)//吸收并整理数据{printf(输入第%d条通道连接的两个个节点：,i);scanf(%d%d,&a,&b);mix(a,b);}}intcount(intN)//有多少个集合{intans,i;memset(t,0,sizeof(t));for(i=1;i=N;i++)//标记根结点{t[Find(i)]=1;}for(ans=0,i=1;i=N;i++)if(t[i])ans++;returnans;}intmain(){inta,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);printf(3.找节点所在集合\n4.并查集中集合的个数\n0.退出\n\n);scanf(%d,&d);switch(d){case1:printf(\n);printf(输入并查集的节点个数：);scanf(%d,&N);printf(输入并查集中连接节点的通道的个数：);scanf(%d,&M);chushihua(N,M);break;case2:printf(\n);printf(输入通道连接的两个个节点：);scanf(%d%d,&a,&b);mix(a,b);printf(合并成功\n);break;case3:printf(\n);while(c!=0){printf(请输入要查找的节点,输入0退出查找：);scanf(%d,&c);e=Find(c);printf(节点所在集合为%d\n,e);}c=100;break;case4:printf(\n);f=count(N);printf(并查集中集合的个数为：%d\n,f);break;case0:break;default:printf(\n);printf(请输入正确的选项);break;}}return0;}。