清华大学：《C++数据结构》第七章 集合与搜索

用位向量实现集合时部分操作的实现 Set:: Set(int MaxSetsize) MaxSize(MaxSetsize)i assert( MaxSize >0); bit Vector= new int [MaxSize; assert( bit Vector=0); for( int 1=0; 1< MaxSize; 1++) bit Vector[=0;

Set :: Set (int MaxSetSize) : MaxSize (MaxSetSize) { assert ( MaxSize > 0 ); bitVector = new int [MaxSize]; assert ( bitVector != 0 ); for ( int i = 0; i < MaxSize; i++ ) bitVector[i] = 0; }

int Set : Addmember( const int x)t assert(x>=0 & x< MaxSize ) if(! bit Vector)) i bit vector x =l; return l; 3 return O int Set: DelMember( const int x)( assert(x>=0 &&x< MaxSize ) if( bit Vector[x]) i bit vector[x=0; return 1; return o

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; }

Set& Set operator=( Set& right i assert( MaxSize - right MaxSize ) for( int 1-0; 1< MaxSize; 1++) bit Vector[1-right bit Vector[i] return *this, int Set: Contains( const int)( assert(x>=0 &&x< MaxSize ) return bit Vector;

Set& Set :: operator = ( Set& right ) { assert ( MaxSize == right.MaxSize ); for ( int i = 0; i < MaxSize; i++ ) bitVector[i] = right.bitVector[i]; return *this; } int Set :: Contains ( const int x ) { assert ( x >= 0 && x < MaxSize ); return bitVector[x]; }

Set Set : operator + Set& right )i assert( MaxSize = right MaxSize )i Set temp( MaxSize ) for( int i=0; 1< MaxSize; 1++) temp. bit Vector[i bit Vector[i right. bit Vector[i return temp; tion0000110 rights10010100 temp01110101110

Set Set :: operator + ( Set& right ) { assert ( MaxSize == right.MaxSize ); Set temp ( MaxSize ); for ( int i = 0; i < MaxSize; i++ ) temp.bitVector[i] = bitVector[i] || right.bitVector[i]; return temp; } this right temp 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 0 1 1 1 0 1 0 1 1 1 0

SetSet operator *( Set right ) t assert( MaxSize=- right. MaxSize )i Set temp( MaxSize ) for( int 1=0; 1< MaxSize; 1++) temp. bit Vector[i bit Vector & right bit vectors; return temp this01110000110 rights10010100 tempo100000010

Set Set :: operator * ( Set & right ) { assert ( MaxSize == right.MaxSize ); Set temp ( MaxSize ); for ( int i = 0; i < MaxSize; i++) temp.bitVector[i] = bitVector[i] && right.bitVector[i]; return temp; } this right temp 0 1 1 1 0 0 0 0 1 1 0 0 0 1 0 0 1 0 1 0 1 0 0 0 1 0 0 0 0 0 0 1 0