数据结构chapter树及二叉树等价问题.ppt

上堂课要点回顾;第 十二 次 课;数据结构课程内容;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：——按秩求并