6.5树与等价问题.doc

6.5树与等价问题 下图中，等价关系的一个有序对为(6,8),则s1和s2需要合并。1396S12810S221108S3=s1s2396等价关系的一个有序对为(6,8),则s1和s2需要合并。/-树的双亲表存储表示-#define MAX_TREE_SIZE 100Typedef struct PTNode TElemType data; Int parent; /双亲位置域。PTNode;Typedef struct PTNode nodesMAX_TREE_SIZE; int n; /结点数。PTree; /-ADT MFSet的树的双亲表存储表示-typedef PTree MFSet;int find_mfset(MFSet S,int i)/找集合S中i所在子集的根。if(iS.n) return -1; /i不属S中任一子集。 for(j=i;S.nodesj.parent0;j=S.nodesj.parent); return j;/ find_mfset Status merge_mfset(MFSet &S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个子集Si和Sj的根结点。/求并集SiSj. if(iS.n | jS.n) reurn ERROR; S.nodesi.parent=j; return OK;/merge_mfset/为解决下图并操作结果树过深，修改并函数。/修改存储结构：根节点的parent域存储子集中所含成员数目的负值。void mix_mfset(MFSet &S,int i,int j)/S.nodesi和S.nodesj分别为S的互不相交的两个子集Si和Sj的根结点。/求并集SiSj. if(iS.n | jS.n) return ERROR; if(S.nodesi.parentS.nodesj.parent) /Si所含成员数比Sj少。 S.nodesj.parent+=S.nodesi.parent; S.nodesi.parent=j; /if(S.nodesi.parentS.nodesj.parent) else S.nodesi.parent+=S.nodesj.parent; S.nodesj.parent=i;/ else_if(S.nodesi.parentS.nodesj.parent)return OK;/ mix_mfset1S121s1s22S23S3.nSn32s1s2s31nn-1s1s2.sn1. . . . .n个集合“并”操作例6-1：假设集合S=x|1xn是正整数，R是S上的一个等价关系。 R=（1,2），（3,4），（5,6），（7,8），（1,3），（5,7），（1,5），. 现求S的等价类。1-1S.nodesMIX(S,7,8)MIX(S,5,6)MIX(S,3,4)MIX(S,1,2)23456789n-1-1-1-1-1-1-1-1-11-2S.nodesMIX(S,5,7)MIX(S,1,3)23456789n1-23-25-27-1-1MIX(S,1,5)1-4S.nodes23456789n113-4557-1-11-8S.nodes23456789n1131557-1-1求等价类的过程树形状如下图6.21a/修改find_mfset函数,查找同时压缩路径。int fix_mfset(MFSet &S,int i)/确定i所在子集,并将从i至根路径上所有节点都变成根的孩子节点。 if(iS.n) return -1; /i不是S中任一子集的成员。 for(j=i;S.nodesj.parent0;j=S.nodesj.parent); for(k=i;k!=j;k=t) t=S.nodesk.parent;S.nodesk.parent=j; return j;/ fix_