Setnode<T>*pb=R.frst->lnk;/R扫描指针 Setnode<T>*pa= first->lnk;/this扫描指针 LinkedSet<t> temp ∥创建空链表 Setnode<T>*p,pc= temp. first;结果存放指针 while(pa!=null & pb !=nULl( if(pa->data=pb->data){∥集合共有 pc->link =new SetNode<t>(pa->data) pa= pa->link; pb=pb->link; else if(pa->data≤pb->data){/thi元素值小 pc->link=new SetNode<t>(pa->data) pa pa->link
SetNode<T> *pb = R.first->link; //R扫描指针 SetNode<T> *pa = first->link; //this扫描指针 LinkedSet<T> temp; //创建空链表 SetNode<T> *p, *pc = temp.first; //结果存放指针 while (pa != NULL && pb != NULL) { if (pa->data == pb->data) { //两集合共有 pc->link = new SetNode<T>(pa->data); pa = pa->link; pb = pb->link; } else if (pa->data < pb->data) { //this元素值小 pc->link = new SetNode<T>(pa->data); pa = pa->link; } 26
else //R集合元素值小 pc->link=new SetNode<t>(pb->data); pb=pb->link pc=pc->ink; f(pa!=NULL)p=pa;/thi集合未扫完 else p=pb /或R集合未扫完 while(p null)( 结果链逐个复制 pc->link =new SetNode<t>(p->data) pc=pc->link; p=p->link p->link=NULL; temp. last=pc;∥链表收尾 return temp; 27
else { //R集合元素值小 pc->link = new SetNode<T>(pb->data); pb = pb->link; } pc = pc->link; } if (pa != NULL) p = pa; //this集合未扫完 else p = pb; //或R集合未扫完 while (p != NULL) { //向结果链逐个复制 pc->link = new SetNode<T>(p->data); pc = pc->link; p = p->link; } pc->link = NULL; temp.last = pc; //链表收尾 return temp; }； 27
等价类与并查集 等价关糸与等价类( Equivalence Class) 在求解实际应用问题时常会遇到等价类问题。 从数学上看,等价类是对象(或成员)的集合, 在此集合中所有对象应满足等价关系。 若用符号“=”表示集合上的等价关系,则对 于该集合中的任意对象x,y,z,下列性质成立: ◆自反性:x≡x(即等于自身 ◆对称性:若x=y,则y≡x ◆传递性:若x≡y且y≡z,则x≡z
等价类与并查集 • 在求解实际应用问题时常会遇到等价类问题。 • 从数学上看，等价类是对象（或成员）的集合， 在此集合中所有对象应满足等价关系。 • 若用符号“ ”表示集合上的等价关系，则对 于该集合中的任意对象x, y, z，下列性质成立： ◆ 自反性：x x (即等于自身)。 ◆ 对称性：若 x y, 则 y x。 ◆ 传递性：若 x y且 y z, 则 x z。 28 等价关系与等价类(Equivalence Class)
因此,等价关系是集合上的一个自反、对称、 传递的关系。 相等”(=)就是一种等价关系,它满足上述 的三个特性。 个集合S中的所有对象可以通过等价关系划 分为若干个互不相交的子集S1,S2,S3,…,它 们的并就是S这些子集即为等价类
• 因此，等价关系是集合上的一个自反、对称、 传递的关系。 • “相等”(=)就是一种等价关系，它满足上述 的三个特性。 • 一个集合 S 中的所有对象可以通过等价关系划 分为若干个互不相交的子集 S1 , S2 , S3 , …，它 们的并就是 S。这些子集即为等价类。 29
确定等价类的方法 确定等价类的方法分两步走: 1读入并存储所有的等价对(ij) 2标记和输出所有的等价类
确定等价类的方法 确定等价类的方法分两步走： 1. 读入并存储所有的等价对( i, j )； 2. 标记和输出所有的等价类。 30