用位向量实现集合抽象数据类型 当集合是全集合{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[ 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 1=0 int GetMember( const int x i 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 ) int SubSet( Set& right ) int operator=-( Set& right ) 使用示例 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;1求s1与2的交{7,8,9 s5=s1-s2;/s1与S2的差{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} 4:{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, 两集合不等