十三、集合及其表示.pptVIP

十三、集合及其表示 1、集合的表示 2、集合的运算 3、Union-Find 1、集合的表示 集合的基本概念 集合是从一个被称为全集的群体中挑选出来的一组对象 。集合中 对象可以是原子(或称单元素)，也可以是集合。集合中的成员必 须互不相同，但应是同一类型。单元素通常是整数、字符、字符 串或指针。 整型集合：定义整型为所有用整数值表示的数据类型，如整数类 型、字符类型、枚举类型。 静态数组表示 Set类定义 设全集为0～499范围内的整数 Const int Setrange = 500； Const int False = 0，True = 1； Class Set { private： // 集合的元素 int member[Setrange－1]； public： Set(void); // 创建空集 Set(int a[ ], int n); // 创建含有初始元素的集合 Set operator + (Set x) const; // 并集 Set operator * (Set x) const; // 交集 friend int operator ^ (int elt, Set x); // elt 属于x吗？ void Insert(int n); // 往集合中加入元素n void Delete(int n); //从集合中删除元素 n friend ostream operator (ostream istr, const Set x); } 例 X = {1，4，5，7} SetArray[1] = True， SetArray[4] = True， SetArray[5] = True， SetArray[7] = True 其他各单元值为False 位运算 逻辑运算符或“‖”，与“”，非“!”对整型操作数运算。类似地， 对整型操作数的每一位有算术运算符： 或“︱”，与“”，非“～”，以及异或“^”。 X =Y =或 与 异或 非 除此之外有移位运算符，左移“”和右移“” 整数a乘以2n可用左移n位处理，除以2n可用右移n位处理。 10110 = 101×16 = 1616 = 110010100002 用位向量表示 利用C + + 位运算表示集合 member[0] member[1] …… 用位向量表示(续) 集合说明 template class T class Set { private: int setrange; // 集合中元素个数的最大值 int arraysize; // 位数组的字节数 unsigned short *member; // 数组指针 // 出错处理函数 void Error(ErrorType n) const; // 实现集合元素在16位短整数中的映象 int ArrayIndex(const T elt) const; unsigned short BitMask(const T elt) const; 用位向量表示(续) public: Set(int setrange); // 构造函数，创建空集 Set(const SetT x); // 复制构造函数