用位向量实现集合抽象数据类型 当集合是全集合{0,1,2，，n}的一个子集 且n是不大的整数时，可用位(0,1)向量来实 现集合。 当全集合是由有限个可枚举的成员组成时，可 建立全集合成员与整数0,1,2，..的一一对应 关系，用位向量来表示该集合的子集。 一个二进位有两个取值1或0，分别表示在集合 与不在集合。如果采用16位无符号短整数数组 bit Vector[作为集合的存储，就要考虑如何求 出元素i在bit Vector数组中的相应位置。 6
用位向量实现集合抽象数据类型 • 当集合是全集合 { 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 川用位向量来存储集合元素，集合元素的范围在0到 /setSize-1之间。数组采用16位无符号短整数实现 public: bitSet (int sz DefaultSize); /构造函数 bitSet (const bitSet<T>&R); /复制构造函数 bitSet ()delete ]bit Vector; /析构丞数 unsigned short getMember(const Tx);/读取集合 元素X 7
集合的位向量(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送入集合元素X void makeEmpty () 川置空集合 for (int i=0;i<vectorSize;++ bit Vector[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 Tx); /判x是否集合this的成员
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(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; /集合大小N int vectorSize; /位数组大小 unsigned short *bit Vector; /存储集合元素的位数组 9
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>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; 1/求s1与s2的并{0,1，，16} s4=S1*s2; 1/求s1与s2的交{7,8,9} s5=s1-s2; /求s1与s2的差{0,1，，6 10
使用示例 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