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

《数据结构课程设计实验报告(并查集).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、本次实验题目要求是实现并查集的初始化、合并集合、查找节点所在集合和与并查集相关的应用的实现。2.并查集的简介：在一些问题中，我们需要划分ｎ个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元集合，然后按一定顺序将属于同一组的元素所在的集合合并。期间要反复用到查找一个元素属于哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find sets)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．代码演示：生成的并查集图为：合并后并查集图为：初始化后并查集的图：合并后并查集的图：1.调试遇到的问题：基本没遇到什么大问题，只是有很多输入语句后面没加分号，输入语句没加取地址之类的小错误。2.经验体会：这是第一次自己在没有人指点的情况下自己去学习一种数据结构，刚刚开始会觉得可能会很难，抱着恐惧的心情去上网查找资料，不过在找

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

7、的城镇。输出格式输出联通全地图所需路的条数。输入样例53122345输出样例1解题代码：#include#include#includeintpre[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;}ret