并查集实验报告.docx

上传人:王** 文档编号:237106 上传时间:2023-04-18 格式:DOCX 页数:6 大小:41.78KB
下载 相关 举报
并查集实验报告.docx_第1页
第1页 / 共6页
并查集实验报告.docx_第2页
第2页 / 共6页
并查集实验报告.docx_第3页
第3页 / 共6页
并查集实验报告.docx_第4页
第4页 / 共6页
并查集实验报告.docx_第5页
第5页 / 共6页
并查集实验报告.docx_第6页
第6页 / 共6页
亲,该文档总共6页,全部预览完了,如果喜欢就下载吧!
资源描述

《并查集实验报告.docx》由会员分享,可在线阅读,更多相关《并查集实验报告.docx(6页珍藏版)》请在优知文库上搜索。

1、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)(7.2)(2.1(7.8)其中.(5.4)表示编号5和编号4的人是认识的,其余一样。可以得出(1.2.3.6.7

2、.8)这6个人是同一个单位的,(4,5.9,10)这4个人是同一个单位的,整个城市共两个单位,2问题分析很显然,他们之间的关系是满足传递性的,例如编号为5和4的人属于同一个单位,编号为4和9的人属于同-一个单位,则编号为5和9的人也属于同一个单位。另外,还有两个关系是隐藏的,每个人跟自己是认识的(自反);如果编号为5的人和编号为4的人是认识的,那么编号为4的人和编号为5的人也是认识的(对称)。加上这两条关系可以得出属于同一个单位的人有自反、对称、传递3个性质,他们是属于同一个等价类的。上面问题中,初始时有n个人,每个人都属于-一个独立的等价类,每加入一个关系(x,y)先要查X和y是属于哪个等价

3、类,假设用Find(X)和Find(y)表示,如果X和y属F同个等价类则不用处理,否则将他们合并在同一个等价类中,假设用Union(x,y)表示。可以将每个等价类描述为一棵树,树中每个非根结点都指向其父结点,用根元素作为等价类的标识符,则上面定义的Find(X)即找到X所在树的根结点;Union(X.y)中,如果属于同一棵树,不处理,否则格他们所在的树合并为一棵树通过面的分析可知对每个元素只需要记录他的父结点即可。3程序设计采用树的双亲表示法作为树的存储结构,用数组father1记录父结点的编号,初始时每个令吉点的father是其本身,输人设计第一行给定两个整数n和m.n表示人数,m表示关系数

4、目:接下来是m行.每行两个整数工、y表示工和y是认识的。输出设计:这个城市共有多少个单位。基本操作:voidlnit(itt)每个元素都将自己作为父结点。itFind(int);查找输人结点所属树的根结点。VoidUuion分别在找输人两个结点所在树的根,如不同则合并为同一棵树。intmain();主函数。4程序代码、ttinclude 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!

5、=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程序测试与运行结果

展开阅读全文
相关资源
猜你喜欢
相关搜索

当前位置:首页 > 研究报告 > 商业贸易

copyright@ 2008-2023 yzwku网站版权所有

经营许可证编号:宁ICP备2022001189号-2

本站为文档C2C交易模式,即用户上传的文档直接被用户下载,本站只是中间服务平台,本站所有文档下载所得的收益归上传人(含作者)所有。装配图网仅提供信息存储空间,仅对用户上传内容的表现方式做保护处理,对上载内容本身不做任何修改或编辑。若文档所含内容侵犯了您的版权或隐私,请立即通知装配图网,我们立即给予删除!