用位向量实现集合抽象数据类型 当集合是全集合{0,1,2,…,n}的一个子集 且n是不大的整数时,可用位(,1)向量来实 现集合。 当全集合是由有限个可枚举的成员组成时,可 建立全集合成员与整数0,1,2,的一一对应 关系,用位向量来表示该集合的子集。 一个二进位有两个取值0,分别表示在集合 与不在集合。如果采用16位无符号短整数数组 bit vector作为集合的存储,就要考虑如何求 出元素i在 bit vector数组中的相应位置
用位向量实现集合抽象数据类型 • 当集合是全集合 { 0, 1, 2, …, n } 的一个子集， 且 n 是不大的整数时，可用位(0, 1)向量来实 现集合。 • 当全集合是由有限个可枚举的成员组成时，可 建立全集合成员与整数 0, 1, 2, …的一一对应 关系，用位向量来表示该集合的子集。 • 一个二进位有两个取值1或0，分别表示在集合 与不在集合。如果采用16位无符号短整数数组 bitVector[ ]作为集合的存储，就要考虑如何求 出元素 i 在bitVector数组中的相应位置。 6
集合的位向量( bit vector)类的定义 #include <assert.h> #include <iostream . h> const int defaultsize =50 template <class t> class bitset i 用位向量來存储集合元素.集合元素的范围在0到 setSize-1之间。数组采用16位无符号短整数实现 public bitSet(int Sz= DefaultSize) 构造函数 bitset( const bitset<T>&R);∥复制构造函数 bitset0{ delete[ Bit vector;}∥析构函数 unsigned short getmember( const tx);∥读取集合 元素ⅹ
集合的位向量(bit Vector)类的定义 #include <assert.h> #include <iostream.h> const int DefaultSize = 50; template <class T> class bitSet { //用位向量来存储集合元素, 集合元素的范围在0到 //setSize-1之间。数组采用16位无符号短整数实现 public: bitSet (int sz = DefaultSize); //构造函数 bitSet (const bitSet<T>& R); //复制构造函数 ～bitSet () { delete [ ]bitVector; } //析构函数 unsigned short getMember (const T x); //读取集合 元素x 7
void putMember(const Tx, unsigned short v);// 将值V送入集合元素ⅹ void make Empty ( i /置空集合 for (int 1=0; 1< vector Size; 1++) bit Vector[1=0; bool addMember(const tx);∥加入新成员x bool delMember( const tx);删除老成员x bitSet <T>& operator=(const bitSet<T>& ri; bitset<t>& operator +(const bitSet<T>& r bitset>& operator *(const bitSet< >&R) bitset<T>& operator-(const bitset<T>& r) bool Contains(const Tx); /x是否集合this的成员8
void putMember (const T x, unsigned short v); // 将值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的成员 8
bool subset( bitsets<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) 出 private: int setsize /集合大小 int vector Size. ∥1位数组大小 unsigned short *bit vector /存储集合元素的位数组
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); //输出 private: int setSize; //集合大小 int vectorSize; //位数组大小 unsigned short *bitVector; //存储集合元素的位数组 }; 9
使用示例 bitSet<int>sl, S2, S3, S4, s5; bool index, equal for(intk=0;k<10;k++){/集合赋值 Sl. addMember(k) S2. addMember(k+7) s:④0,1,2,…,9},s2:{7,8,9,…,16} s3=sl+s2;/求s1与S2的并{0,1,…,16 s4=sls2;1求S1与S2的交{7,8,9} s5=s1-s2;/s1与S2的差{0,1,…,6}
使用示例 bitSet<int> s1, s2, s3, s4, s5; bool 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; //求s1与s2的差 {0, 1, …, 6} 10