《集合等价类与并查集》由会员分享，可在线阅读，更多相关《集合等价类与并查集（49页珍藏版）》请在金锄头文库上搜索。
1、集合 等价类与并查集,第七章 集合,一、集合,若干个同一类型互不相同的以一定次序排 列的元素 整形集合（整数，字符，枚举，记录） 若干离散有序元素组成的集合 每个元素可以对应唯一一个整数 int(a)； /a对应的整数,A=a,b,c, B=b,d,集合的运算 aA AB=a,b,c,d AB=b A-B=a,c,集合的实现,用数组实现 用指针实现 用链表实现 用位运算实现整形集合,位运算 或 | 与& 非 异或 右移位 左移位, x y x x|y x&y xy 0 0 1 0 0 0 0 1 1 1 0 1 1 0 0 1 0 1 1 1 0 1 1 0,x=11100011 y=0111
2、0110,x|y 11100011 01110110 11110111 x&y 11100011 01110110 01100010,x = 00011100,xy 11100011 01110110 10010101,unsigned short x=10, y=13,z;/2字节16位 /x=1010, y=1101,z=x|y; /z=15 z=x /z=3,将n个元素固定成一列，每个下标代表一个元素 每个元素elt的下标可以由int(elt)或用一个公式算出 用一个01数组存储集合 每一位写0或1 0代表某个元素不在集合中， 1代表某个元素在集合中， n个元素最少用多长的数组呢？,用0
3、1数组存储n个整形元素的集合,一个unsigned short 整数占两个字节16位 k个unsigned short 整数占两个字节k*16位,k*16=n, k=(n+15)/16, k=(n+15)4. 存储n个元素只要k个unsigned short 整数,只要一个二进制位就可以存储0，1,unsigned short *member; member=new unsigned shortk;,15,31,1 1 1 1 1,A=a1,a7,a13,a18,a25,确定一个元素在哪一个字节第几位 第18号元素a18, 在member1 2号位 设第s号元素,在memberi j号位 i=
4、s/16=s4; j=s%16=1 (s ,两集合A,B的并 按对应字节求或 | for(i=0;ik;i+) C.memberi= A.memberi | B.memberi； 两集合的交 按对应字节求与 /x在memberi j号位,#ifndef SET_CLASS #define SET_CLASS #include #include enum ErrorType InvalidMember, ExpectRightBrace, MissingValue, MissingComma, InvalidChar, MissingLeftBrace, InvalidInputData, En
5、dOfFile, OutOfMemory, InvalidMemberRef, SetsDifferentSize ;,template class Set private: int setrange; / max number of elements in the set int arraysize; unsigned short *member; void Error(ErrorType n) const; int ArrayIndex(const T,Set(void); Set,template void Set:Error (ErrorType n) const cout endl;
6、 switch(n) case InvalidMember: cerr “Invalid set member“; break; case ExpectRightBrace: cerr “Expect right brace “; break; case MissingValue: cerr “Missing a value after a comma“; break; case MissingComma: cerr “Separate members with a comma“;break; case InvalidChar: cerr “Invalid set character“; br
7、eak;,case MissingLeftBrace: cerr “Missing left brace “; break; case InvalidInputData: cerr “Invalid input data element“; break; case EndOfFile: cerr “Premature end of file“; break; case OutOfMemory: cerr “Memory allocation failure“; break; case InvalidMemberRef: cerr “Invalid member reference“; brea
8、k; case SetsDifferentSize: cerr “Sets are not the same size“; break; cout endl; exit(1); ,template int Set:ArrayIndex(const T ,/ constructor. create an empty set template Set:Set(int sz): setrange(sz) / number of unsigned shorts needed to hold set elements arraysize = (setrange+15) 4; / allocate the
9、 array member = new unsigned short arraysize; if (member = NULL) Error(OutOfMemory); / create an empty set by setting all bits to 0 for (int i = 0; i arraysize; i+) memberi = 0; ,template Set:Set(const Set ,template Set:Set(void) delete member; template Set ,/ determine whether elt is in the set tem
10、plate int Set:IsMember(const T ,template int Set:operator= = (const Set ,template Set Set:operator+ (const Set ,template Set Set:operator* (const Set ,/ insert elt into the set template void Set:Insert(const T ,/ delete elt from the set template void Set:Delete(const T ,template istream,while (c !=
11、) switch(c) case : case t: case n: break; case : x.Error(ExpectRightBrace); break; case ,: if (haveComma = 1) x.Error(MissingValue); else haveComma = 1; needComma = 0; break;,default: if (needComma) x.Error(MissingComma); istr.putback(c); if(istr elt = 0) x.Error(InvalidInputData); if (int(elt) = x.
12、setrange) x.Error(InvalidInputData); x.memberx.ArrayIndex(elt) |= x.BitMask(elt); needComma = 1; haveComma = 0; break; ,if (istr.get(c) = 0) x.Error(EndOfFile); if (haveComma = 1) x.Error(MissingValue); return istr; ,template ostream ,#endif / SET_CLASS,打印素数,#include #include #pragma hdrstop #includ
13、e “set.h“ / use the Set class,void PrintPrimes(int n) Set S(n+1); int m, k, count; for(m=2; m = n; m+) S.Insert(m); for( m=2;m*m = n; m+) if( S.IsMember(m) for( k=m+m; k= n; k += m) if (S.IsMember(k) S.Delete(k); count = 1; for(m=2;m = n;m+) if (S.IsMember(m) cout setw(3) m “ “; if (count+ % 10 = 0)
14、 cout endl; cout endl; ,void main(void) int n; cout n; cout endl; PrintPrimes(n); ,二、等价类和并查集,一个等价关系把一个集合划分成互不相交的等价类 设 S=0,1,2,3,4,5,6,7,8,9,10,11 04，31，610，89，74，68，35，211，110 则S=0,2,4,7,111,3,56,8,9,10 怎样用一个算法实现,用集合运算,先把S的每个元素都做成单点集 再把有关系的集合做并: 每读入一对等价元素ab 查找a,b所在的集合，如不同则做并。,用双亲表示法的树结构表示集合,双亲表示法树表示
15、集合 树根同时作集合名,A,B,C,D,E,F,不交集合的并只要连接两颗树,A,B,C,D,E,F,G,H,I,J,G,H,I,J,双亲表示法结点定义,#define MAX_TREE_SIZE 100 template class PNode T data; int Parent; public: PNode(T item, int pr); T GetData( ); int GetParent( ); ,const int defaultsize=15; template class UFSet /并查集的类 PNode *nodes; int size; int Find(int i);/找结点i所在集合的根 public: UFset(int sz=defaultsize ); UFSet( )delete nodes; void Union(T item1, T item2); int Find(T item);/找item所在集合的根 void WeightedUnion(T item1, T item2); int CollapsingFind(T item); ;,
