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

华南农业大学信息学院
课程设计实验
学院
数学与信息学院
班级
14网工1
学号
201430350114
姓名
赖文杰
实
验
题
目

■设计性 □综合性

自
我
评
价

代码直观，有调理，按时完成，独立完成，实验报告详细，还添加了其他功能，不过注释不过详细，表达能力不好，部分代码直接照抄网上，总体良好。
教
师
评
语
能够实现实验要求的功能 √全部 □部分
算法有新意 √有 □一般
程序运行通过 √全部 □部分
算法注释说明 √完善 □仅有功能说明
接口参数说明 √有 □无
按期上交文档资料及源程序 √所有 □部分
独立完成实验 √能 □不能
体现团队合作精神。 √能够 □不能
成绩

实验题目：并查集
班级：14网络工程一班
姓名：赖文杰
学号：201430350114
完成日期：2015/9/30

一． 题目要求：
1. 实验的要求：
本次实验题目要求是实现并查集的初始化、合并集合、查找节点所在集合和与并查集相关的应用的实现。

2. 并查集的简介：
在一些问题中，我们需要划分ｎ个不同的元素成若干组，每一组的元素构成一个集合。这种问题的一个解决办法是，在开始时，让每个元素自成一个单元集合，然后按一定顺序将属于同一组的元素所在的集合合并。期间要反复用到查找一个元素属于哪一个集合的运算。适合于描述这类问题的抽象数据类型称为并查集(union-find sets)

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行，每行输入每条路联通的城镇。
输出格式
输出联通全地图所需路的条数。
输入样例
5 3
1 2
2 3
4 5
输出样例
1

解题代码：
#include <iostream>
#include <stdio.h>
#include <stdlib.h>
int pre[1000 ];

using namespace std;

int find(int x)
{
int r=x;
while (pre[r ]!=r)
r=pre[r ];
int i=x; int j;
while(i!=r)
{
j=pre[i ];
pre[i ]=r;
i=j;
}
return r;
}
int main()
{
int n,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，还需建的路也就减了1
if(f1!=f2)
{
pre[f2 ]=f1;
total--;
}
//如果两点已经连通了，那么这条路只是在图上增加了一个环 //对连通性没有任何影响，无视掉
}
//最后输出还要修的路条数
printf("%d\n",total);
}
return 0;
}

五． 附录：
源代码：#include<iostream>
#include <stdio.h>
#include <stdlib.h>
#include<cstring>
using namespace std;

int pre[1050]; //用于存储节点
bool t[1050]; //t 用于标记独立块的根结点

int Find(int x) //查找节点所在集合
{
int r=x;
while(r!=pre[r])
r=pre[r];

int i=x,j;
while(pre[i]!=r)
{
j=pre[i];
pre[i]=r;
i=j;
}
return r;
}

void mix(int x,int y) // 合并结合
{
int fx=Find(x),fy=Find(y);
if(fx!=fy)
{
pre[fy]=fx;
}
}

int chushihua(int N,int M) //初始化
{
int a,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);
}
}

int count(int N) //有多少个集合
{

int ans,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++;

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");
printf("3.找节点所在集合\n4.并查集中集合的个数\n0.退出\n\n");
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退出查找：");
scanf("%d",&c);
e=Find(c);
printf("节点所在集合为%d\n",e);}c=100;break;
case 4:printf("\n");
f=count(N);
printf("并查集中集合的个数为：%d\n",f);break;
case 0:break;
default:printf("\n");
printf("请输入正确的选项");break;
}
}

return 0;
}

。