- 1、本文档共34页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
- 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
- 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
数据结构chapter树及二叉树等价问题
上堂课要点回顾;第 十二 次 课;数据结构课程内容;8.7 等价问题(并查集);2、等价类(equivalence classes):设R是定义在非空集合S上的一个的等价关系,
称 是x的等价类。R可产生集合S的唯一划分,即可以按R将S划分为若干不相交的子集S1,S2,…,这些子集Si称为S的R等价类。简言之,等价类是集合中相互等价的元素的最大子集合。
;;例如:亲戚
或许你并不知道,你的某个朋友是你的亲戚。他可能是你的曾祖父的外公的女婿的外甥女的表姐的孙子。如果能得到完整的家谱,判断两个人是否是亲戚应该是可行的,但如果两个人的最近公共祖先与他们相隔好几代,使得家谱十分庞大,那么检验亲戚关系实非人力所能及。在这种情况下,最好的帮手是计算机。 为了将问题简化,你将得到一些亲戚关系的信息,如同Xuebin和Grant是亲戚,Grant和Tension是亲戚等,从这些信息中,你可以推出Xuebin和Tension是亲戚。请写一个程序,对于我们的关于亲戚关系的提问,以最快的速度给出答案。 ;设初始有一集合S={0,1,2,3,4,5,6,7,8,9,10,11},依次读若干事先定义的等价对0?4,3?1,6?10,8?9,7?4,6?8,3?5,2?11,11?0.
每次读入一个等价对后,把等价集合union起来,则每读入一个等价对后集合的状态是:
初始 {0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}
0 ? 4 {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}
3 ? 1 {0,4}, {1,3},{2},{5},{6},{7},{8},{9},{10},{11}
6 ? 10 {0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}
8 ? 9 {0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}
7 ? 4 {0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}
6 ? 8 {0,4,7},{1,3},{2},{5},{6,8,9,10},{11}
3 ? 5 {0,4,7},{1,3,5},{2},{6,8,9,10},{11}
2 ? 11 {0,4,7},{1,3,5},{2,11},{6,8,9,10}
11 ? 0 {0,2,4,7,11},{1,3,5},{6,8,9,10};ADT UnionFindSet
数据元素:seti={aj}, i=0,1,…,n-1, j=0,1,…,ni-1 (n≥0, ni≥0)。其中ai∈{0,1,2,……,n}
结构:
逻辑操作:设S为UnionFindSet型
Initiate(S,n):建立n个新集合,每个集合有唯一元素。要求各集合不相交的
Find(S,x):返回x的等价类名
Union(S,x,y):如果Find(S,x)!=find(S,y),则把分别含有x和y的两个等价类合并成到一个等价类。每一次union操作使得集合的个数减少1;;并查集实现方法1:数组表示法
建立一大小为n的数组,其中每个元素是等价类名
;数组法算法分析;并查集实现方法2:链表表示法
每个等价类用一个链表表示,
第一个结点作其代表,初始n个链表
;链表法算法分析;链表表示法的改进:——按秩合并启发式策略;改进后的链表法算法分析;并查集实现方法3:森林表示法
每一个等价类用一棵树表示,树中每个结点是集合的一个成员,根是代表。如果两个结点在同一棵树中,则认为它们在同一个等价类中
每个成员仅指向其父结点
Find操作实现:沿着双亲结点指针一直向上找直至根结点
Union操作实现:将一棵树的根指向另一棵树的根
;;10个结点A、B、C、D、E、F、G、H、J、K和它们的等价关系(A,B)、(C,K) 、(F,J) 、(E, H) 、(D,G) 、(A, K) 、(G, E) 、(H,J)
初始状态: ;对(A,B)、(C,K) 、(F, J) 、(E,H) 、(D,G)这5个等价对的处理结果;对两个等价对(A, K)和(G, E )的处理结果: ;并查集类型定义
#define MaxTreeNode 20
typedef struct
{ int data;
int parent;//双亲结点在数组的下标,根的parent为-1
} UFSTreeNode;
UFSTreeNode Forest[MaxTreeNode];/*存储森林结点的数组*/
;【并查集初始化算法】;【并查集查找算法】;【并查集合并算法】;森林法算法分析;森林表示法的改进1:——按秩求并
您可能关注的文档
最近下载
- 2024年04月江苏盐城大丰区新丰镇村级后备干部选拔11人笔试历年典型考题(历年真题考点)解题思路附带答案详解.doc VIP
- 部编二下语文识字2传统节日课件.PPT VIP
- 2013款长安福特新福克斯_汽车使用手册用户操作图解驾驶指南车主车辆说明书电子版.pdf VIP
- 2024年步进电动机及控制系统项目创业投资方案.docx
- 2024年度党建工作汇报总结及2025年党建计划PPT模板课件.pptx VIP
- 中医治疗放化疗后课件.pptx VIP
- 民间房产抵押借款合同范本(2024版).docx VIP
- 装配式建筑结构设计 课件 第6章 装配式混凝土剪力墙结构 .pptx
- 《住院患者身体约束的护理》团体标准解读PPT.pptx VIP
- 2025年武汉市中考语文试卷真题(含答案)精校版.pdf
文档评论(0)