SetNode<T>*pb =R.first->link; R扫描指针 SetNode<T>*pa first->link; /his扫描指针 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; 3 26
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->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; 3 pc->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≡乙，则x≡乙。 28
等价类与并查集 • 在求解实际应用问题时常会遇到等价类问题。 • 从数学上看，等价类是对象（或成员）的集合， 在此集合中所有对象应满足等价关系。 • 若用符号“ ”表示集合上的等价关系，则对 于该集合中的任意对象x, y, z，下列性质成立： ◆ 自反性：x x (即等于自身)。 ◆ 对称性：若 x y, 则 y x。 ◆ 传递性：若 x y且 y z, 则 x z。 28 等价关系与等价类(Equivalence Class)
因此，等价关系是集合上的一个自反、对称、 传递的关系。 “相等”(=)就是一种等价关系，它满足上述 的三个特性。 一个集合S中的所有对象可以通过等价关系划 分为若干个互不相交的子集S1,S2,S3,·,它 们的并就是S。这些子集即为等价类。 29
• 因此，等价关系是集合上的一个自反、对称、 传递的关系。 • “相等”(=)就是一种等价关系，它满足上述 的三个特性。 • 一个集合 S 中的所有对象可以通过等价关系划 分为若干个互不相交的子集 S1 , S2 , S3 , …，它 们的并就是 S。这些子集即为等价类。 29
确定等价类的方法 确定等价类的方法分两步走： 1.读入并存储所有的等价对(i,): 2.标记和输出所有的等价类。 30
确定等价类的方法 确定等价类的方法分两步走： 1. 读入并存储所有的等价对( i, j )； 2. 标记和输出所有的等价类。 30