bitset.h

清华大学计算机系数据结构课程教材《数据结构 用面向对象方法和C++描述》（殷人昆主编）的类库（书中程序的源代码）

//集合类，用位向量实现
#ifndef BITSET_H
#define BITSET_H

#include <assert.h>
#include <iostream>
using namespace std;
const int DefaultSize = 100;

template<class T>
class bitSet {
	//用位向量来存储集合元素, 集合元素的范围在0到
	//setSize-1之间。数组采用16位无符号短整数实现
public:
	bitSet (int sz = DefaultSize);	//构造函数
	bitSet (const bitSet<T>& R);	//复制构造函数
	~bitSet () { delete [ ]bitVector; }	//析构函数
	bool getMember (const T x);		//取集合元素x
	void putMember (const T x, int v);  //改集合元素x
	void makeEmpty () { 			//置空集合
		for (int i = 0; i < vectorSize; i++)
			bitVector[i] = 0;
	}
	bool addMember (const T x);	//加入新成员x
	bool delMember (const T x);	//删除老成员x
	bitSet<T>& operator = (const bitSet<T>& R);	
	bitSet<T> operator + (const bitSet<T>& R);
	bitSet<T> operator * (const bitSet<T>& R);
	bitSet<T> operator - (const bitSet<T>& R);
	bool Contains (const T x);						                      //判x是否集合this的成员
	bool subSet (bitSet<T>& R);   //判this是否R的子集
	bool operator == (bitSet<T>& R);				   			   //判集合this与R相等
	friend istream& operator >> (istream& in,  
		bitSet<T>& R);		   //输入
	friend ostream& operator << (ostream& out, //输出
		bitSet<T>& R){
			for (T i=0; i<R.setSize; ++i)
				if (R.getMember(i))
					out<<i<<"   ";
			out<<endl;
			return out;
	}		   
private:
	int setSize;		//集合大小
	int vectorSize;		//位数组大小
	unsigned short *bitVector;						                    //存储集合元素的位数组
};

template <class T>
bitSet<T>::bitSet (int sz) : setSize (sz) {    //构造函数
	assert (setSize > 0);		   //检查参数的合理性
	vectorSize = (setSize+15) >> 4;	//存储数组大小
	bitVector = new unsigned short [vectorSize];	//分配空间
	assert (bitVector != NULL);						//检查存储分配是否成功
	for (int i = 0; i < vectorSize; i++)
		bitVector[i] = 0;			//初始化
};
template <class T>
bitSet<T>::bitSet (const bitSet<T>& R) {
	//复制构造函数
	setSize = R.setSize;		    //集合元素个数
	vectorSize = R.vectorSize; 	    //存储数组大小
	bitVector = new unsigned short  [vectorSize];	  //分配空间
	assert (bitVector != NULL);						        //检查存储分配是否成功
	for (int i = 0; i < vectorSize; i++)   //初始化
		bitVector[i] = R.bitVector[i];	
};


template <class T>
bool bitSet<T>::Contains (const T x){
	return getMember(x);
}


template <class T>
bool bitSet<T>::getMember (const T x) {
	//读取集合元素x
	int ad = x/16,  id = x%16;	 //计算数组元素下标 
	unsigned short elem = bitVector [ad];			//取x所在数组元素
	return ((elem >> (15-id)) & 1);			//取第id位的值
};

template <class T>
void bitSet<T>::putMember (const T x, int v) {
	//将值v送入集合元素x
	int ad = x/16,  id = x%16;	  //计算数组元素下标
	unsigned short elem = bitVector [ad];
	//取x所在数组元素
	int temp = elem >> (15-id);	  //右移,该位移至末尾
	if (temp%2 == 0 && v == 1) temp = temp+1;		                                         //根据v的值,修改该位
	else if (temp%2 == 1 && v == 0) temp = temp-1;
	bitVector[ad] =(temp<<(15-id)) | (((1<<(15-id)) - 1) & elem) ;		//送回
};

template <class T>
bool bitSet<T>::addMember (const T x) {
	assert (x >= 0 && x < setSize);
	if (getMember(x) == 0) {
		putMember(x, 1);
		return true;
	}
	return false;
};

template <class T>
bool bitSet<T>::delMember (const T x) {
	assert (x >= 0 && x < setSize);
	if (getMember(x) == 1) {
		putMember(x, 0);
		return true;
	}
	return false;
};

template<class T>
bitSet<T> & bitSet<T>::operator =(const bitSet<T> & R){
	if (this !=&R){
		setSize = R.setSize;		    //集合元素个数
		vectorSize = R.vectorSize; 	    //存储数组大小
		delete [] bitVector;
		bitVector = new unsigned short  [vectorSize];	  //分配空间
		assert (bitVector != NULL);						        //检查存储分配是否成功
		for (int i = 0; i < vectorSize; i++)   //初始化
			bitVector[i] = R.bitVector[i];
	}
	return *this;
}



template<class T>
bitSet<T> bitSet<T>::          //求集合this与R的并
operator + (const bitSet<T>& R) {
	assert (vectorSize == R.vectorSize); 
	bitSet<T> temp (setSize);

	for (int i = 0; i < vectorSize; i++)
		temp.bitVector[i] = bitVector[i] | R.bitVector[i];	
	return temp;  //按位求"或", 由第三个集合返回
};

template <class T>
bitSet<T> bitSet<T>::                //求集合this与R的交
operator * (const bitSet<T>& R) {	
	assert (vectorSize == R.vectorSize);
	bitSet<T> temp (setSize);
	for (int i = 0; i < vectorSize; i++)
		temp.bitVector[i] = bitVector[i] & R.bitVector[i];
	return temp;  //按位求“与”, 由第三个集合返回
};

template <class T>
bitSet<T> bitSet<T>::		//求集合this与R的差
operator - (const bitSet<T>& R) {	
	assert (vectorSize == R.vectorSize); 
	bitSet<T> temp (setSize);
	for (int i = 0; i < vectorSize; i++)
		temp.bitVector[i] = 	bitVector[i] & ~R.bitVector[i];
	return temp;			//由第三个集合返回
};
template <class T>
bool bitSet<T>::subSet (bitSet<T>& R) {
	//判this是否R的子集
	assert (setSize == R.setSize);
	for (int i = 0; i < vectorSize; i++)   //按位判断
		if (bitVector[i] & ~R.bitVector[i]) return false;
	return true;	
};
template <class T>
bool bitSet<T>::operator == (bitSet<T>& R) {
	//判集合this与R相等
	if (vectorSize != R.vectorSize) return false;
	for (int i = 0; i < vectorSize; i++)
		if (bitVector[i] != R.bitVector[i]) return false;
	return true;			//对应位全部相等
};





#endif