用位向量实现集合抽象数据类型 当集合是全集合{0,1,2,…,n}的一个子集, 且n是不大的整数时,可用位(0,1)向量来实 现集合。 当全集合是由有限的可枚举的成员组成的 集合时,可建立全集合成员与整数0,1, 2,.一一对应关系,用位向量来表示该集 合的子集
用位向量实现集合抽象数据类型 ◼ 当集合是全集合{ 0, 1, 2, …, n }的一个子集， 且 n是不大的整数时，可用位(0, 1)向量来实 现集合。 ◼ 当全集合是由有限的可枚举的成员组成的 集合时，可建立全集合成员与整数 0, 1, 2, …的一一对应关系，用位向量来表示该集 合的子集
集合的位向量 bit Vector)类的定义 #include <assert.h> const int Defaultsize=100 class set i private int* bit Vector int maxSize public. Set( int MaxSetsize= DefaultSize ) Seti delete[i bit vector;)
集合的位向量(bit Vector)类的定义 #include <assert.h> const int DefaultSize = 100; class Set { private: int * bitVector; int MaxSize; public: Set ( int MaxSetSize = DefaultSize ); ~Set ( ) { delete [ ] bitVector; }
void MakeEmpty (i for( int 1=0; 1< MaxSize; 1++) bit Vector[=0 int GetMember( const int x t return x>=o&&x< maxSize bit vector区x]:-1;} int AddMember( const int x ) int DelMember( const int x ) Set& operator =( Set& right ) Set& operator + Set& right )
void MakeEmpty ( ) { for ( int i = 0; i < MaxSize; i++ ) bitVector[i] = 0; } int GetMember ( const int x ) { return x >= 0 && x < MaxSize ? bitVector[x] : -1; } int AddMember ( const int x ); int DelMember ( const int x ); Set& operator = ( Set& right ); Set& operator + ( Set& right );
Set& operator*( Set& right ) Set& operator-( Set& right ) int Contains( const int x )3 int SubSet( Set& right ) int operator =-( Set& right )3 使用示例 Set sl s2. s3 s4.s5: int index, equal for(intk=0;k<10;k++)/集合赋值 &sl. AddMember( k); s2. AddMember(k+7);) ∥s1:{0,1,2,…,9},s2:{7,8,9,…,16}
Set& operator * ( Set& right ); Set& operator - ( Set& right ); int Contains ( const int x ); int SubSet ( Set& right ); int operator == ( Set& right ); }; 使用示例 Set s1, s2, s3, s4, s5; int index, equal; for ( int k = 0; k < 10; k++ ) //集合赋值 { s1.AddMember( k ); s2.AddMember( k +7 ); } // s1 : { 0, 1, 2, …, 9 }, s2 : { 7, 8, 9, …, 16 }
s3=s1+s2;∥求s1与2的并{0,1,,16} s4=s1*s2;求s1与S2的交{7,8,9 s5=s1-s2;/s1与2的差{0,1,……,6} ∥s1:{0,1,2,…,9} index=sl. Subset(s4);/4在s1中首次匹配 cout<< index<<end;∥置, index=7 ∥s1:{0,1,2,3,4,5,6,7,8,9} s4:{7,8,9} equal=Sl== S2 ∥集合s1与s2比较相等 cout<< equal<<endl;∥0,两集合不等
s3 = s1+s2; //求s1与s2的并 { 0, 1, …, 16 } s4 = s1*s2; //求s1与s2的交{ 7, 8, 9 } s5 = s1-s2; //求s1与s2的差{ 0, 1, …, 6 } // s1 : { 0, 1, 2, …, 9 } index = s1.SubSet ( s4 ); //s4在s1中首次匹配 cout << index << endl; //位置，index = 7 // s1 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } // s4 : { 7, 8, 9 } equal = s1 == s2; //集合s1与s2比较相等 cout << equal << endl; //为0, 两集合不等