用位向量实现集合抽象数据类型 当集合是全集合{0,1,2,…,n}的一个子集 且n是不大的整数时,可用位(0,1)向量来实现 集合。 a当全集合是由有限的可枚举的成员组成的集 合时,可建立全集合成员与整数0,1,2,.一 对应关系,用位向量来表示该集合的子集。 集合的位向量 bit vector)类的定义 include <assert. h> const int Defaultsize= 100 class set i
用位向量实现集合抽象数据类型 集合的位向量(bit Vector)类的定义 #include <assert.h> const int DefaultSize = 100; class Set { ◼ 当集合是全集合{ 0, 1, 2, …, n }的一个子集， 且 n是不大的整数时，可用位(0, 1)向量来实现 集合。 ◼ 当全集合是由有限的可枚举的成员组成的集 合时，可建立全集合成员与整数0, 1, 2, …的一 一对应关系，用位向量来表示该集合的子集
private int bitvector int Max size public Set( int Max Setsize= Defaultsize ) set oi delete l bitvector;) void Makeempty ot for (int i=0; i< MaxSize; i++) bivector=0 int AddMember( const int x); int DelMember( const int x ) Set& operator =( Set right )
private: int * bitVector; int MaxSize; public: Set ( int MaxSetSize = DefaultSize ); ~Set ( ) { delete [ ] bitVector; } void MakeEmpty ( ) { for ( int i = 0; i < MaxSize; i++ ) bitVector[i] = 0; } 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 ) 使用示例 Sets1,s2,s3,s4,s5; int index, equal;/构造集合 for( int k=0; k< 10; k++) 集合赋值 &sl. AddMember(k); s2. AddMember(k+7); ∥ls1:{0,1,2,…,9},s2:{7,8,9,,,16}
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 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与s2的并{0,1,…,16} s4=s1*s2;/求s1与s2的交{7,8,9} s5=s1-s2;/求1与s2的差{0,1,2,3,4,5,6} ndex=s1. Subset(s4);/求s4在s1中首次匹配 cout<< index<<endl;/位置 inaex 7 eqal=s1==s2;集合s1与s2比较相等 cout<< equal<endl;/equm为0,两集合不等 用位向量实现集合时部分操作的实现 Set Set (int MaxSetsize): Max Size(MaxSetsizei assert( MaxSize>0) bitvector= new int [MaxSizeli assert( bit Vector!=0);
s3 = s1 + s2; //求s1与s2的并{ 0, 1, …, 16 } s4 = s1 * s2; //求s1与s2的交{ 7, 8, 9 } s5 = s1 - s2; //求s1与s2的差 { 0, 1, 2, 3, 4, 5, 6 } index = s1.SubSet ( s4 ); //求s4在s1中首次匹配 cout << index << endl; //位置， index = 7 equal = s1 == s2; //集合s1与s2比较相等 cout << equal << endl; //equal为0, 两集合不等 用位向量实现集合时部分操作的实现 Set :: Set (int MaxSetSize) : MaxSize (MaxSetSize) { assert ( MaxSize > 0 ); bitVector = new int [MaxSize]; assert ( bitVector != 0 );
for( int i=0; i< Max Size; i++)bitvector]=0; int Set Addmember( const int x)i assert(x>=0 & x< Max Size ) if (! bitvectorlx])( bit vector=l; return 1;) return 0, int Set DelMember( const intx)( assert(x>=0&&x< MaxSize ) if bitvectorlx)( bitvectorkx=0; return 1;) return o
for ( int i = 0; i < MaxSize; i++ ) bitVector[i] = 0; } int Set :: Addmember ( const int x ) { assert ( x >= 0 && x < MaxSize ); if ( ! bitVector[x] ) { bitVector[x] = 1; return 1; } return 0; } int Set :: DelMember ( const int x ) { assert ( x >= 0 && x < MaxSize ); if ( bitVector[x] ) { bitVector[x] = 0; return 1; } return 0; }