并查集实验报告.docx

2017-2018学年第一学期数据结构课程设计报告题目：并查集专业：数字媒体技术班级：数字151姓名：学号：指导教师：成绩：目录1问题描述22问题分析33程序设计34程序代码45参考文献56程序测试与运行结果6附：源程序61问题描述1.问题描述假设某个城市住着n个人，如果两个人是认识的则这两个人属于同一个单位的，现给定n个人的m条关系(即某两个人认识)，问这个城市共有多少个单位。例如有10个人编号分别是1-10,有11条关系:(5,4)(4.9)>(7.6X10.5X3.2).10)<6,1)(8.3>(7.2)(2.1>(7.8)其中.(5.4)表示编号5和编号4的人是认识的,其余一样。可以得出(1.2.3.6.7.8)这6个人是同一个单位的，(4,5.9,10)这4个人是同一个单位的，整个城市共两个单位，2问题分析很显然，他们之间的关系是满足传递性的，例如编号为5和4的人属于同一个单位，编号为4和9的人属于同-一个单位,则编号为5和9的人也属于同一个单位。另外，还有两个关系是隐藏的，每个人跟自己是认识的(自反)；如果编号为5的人和编号为4的人是认识的,那么编号为4的人和编号为5的人也是认识的(对称)。加上这两条关系可以得出属于同一个单位的人有自反、对称、传递3个性质，他们是属于同一个等价类的。上面问题中，初始时有n个人，每个人都属于-一个独立的等价类，每加入一个关系(x,y)先要查X和y是属于哪个等价类,假设用Find(X)和Find(y)表示，如果X和y属F同个等价类则不用处理,否则将他们合并在同一个等价类中，假设用Union(x,y)表示。可以将每个等价类描述为一棵树，树中每个非根结点都指向其父结点，用根元素作为等价类的标识符，则上面定义的Find(X)即找到X所在树的根结点;Union(X.y>)中，如果属于同一棵树，不处理，否则格他们所在的树合并为一棵树通过面的分析可知对每个元素只需要记录他的父结点即可。3程序设计采用树的双亲表示法作为树的存储结构，用数组father1记录父结点的编号,初始时每个令吉点的father是其本身，输人设计第一行给定两个整数n和m.n表示人数,m表示关系数目：接下来是m行.每行两个整数工、y表示工和y是认识的。输出设计：这个城市共有多少个单位。基本操作：voidlnit(itt)每个元素都将自己作为父结点。itFind(int);查找输人结点所属树的根结点。VoidUuion分别在找输人两个结点所在树的根，如不同则合并为同一棵树。intmain();主函数。4程序代码、ttinclude<stdio.h> define MAX 100 int fatherMAX; void Init(int N) int i;for(i=l;i<=N;i+) fatheri=i; 点*/ *Init*/ int Find(int x) int r=x;while(fatherr!=r) 点的父节点是其本身*/r=fatherr;*初始时每个元素都将自己作为父结/*查找X所属树的根节点*/*向上查找根节点，结束条件是根节returnr;*Find*/*分别查找a、b所在树的根，如不同voidUnion(inta,intb)则合并为同一棵树*/intX,y;x=Find(a);y=Find(b);if(x!=y)fatherx=y;*Union*/intmainOintn,m,i,x,y,count-0;Printf(请输入人数和关系树)；scanf(/,%d%d,z,&n,&m);Init(n);printf(请输入%d个关系n,m);for(i=l;i<=m;i+)scanf(,%d%dz,&x,&y);Union(x,y);*for*/for(i=l;i<=n;i+)if(i=fatheri)count+;*for*/printfn该城市共有%d个单位。r,count);*main*/5、参考文献1刘晓华著数据结构与算法.北京：清华大学出版社，20156程序测试与运行结果