数据结构电子教案_深圳大学_自动化课件_ds_06.ppt

第六章 集合与字典 ;集合及其表示 并查集与等价类 字典 跳表 散列;集合及其表示;集合中的成员一般是无序的，但在表示它时，常写在一个序列里。 常设定集合中的单元素具有线性有序关系，此关系可记作“”，表示“优先于”。 整数、字符和串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。 在某些集合中保存实际数据值，某些集合中保存标示元素是否在集合中的指示信息。如学校开设的所有课程的编码属于前者，一个学期开设的课程构成的集合属于后者。;; virtual bool delMember (const T x) = 0; virtual SetT intersectWith (SetT R) = 0; //集合的交运算 virtual SetT unionWith (SetT R) = 0; //集合的并运算 virtual SetT differenceFrom (SetT R) = 0; //集合的差运算 virtual bool Contains (T x) = 0; virtual bool subSet (SetT R) = 0; virtual bool operator == (SetT R) = 0; //判集合是否相等 };;用位向量实现集合抽象数据类型;集合的位向量(bit Vector)类的定义; 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 bitSetT operator = (const bitSetT R); bitSetT operator + (const bitSetT R); bitSetT operator * (const bitSetT R); bitSetT operator - (const bitSetT R); bool Contains (const T x); //判x是否集合this的成员; bool subSet (bitSetT R); //判this是否R的子集 bool operator == (bitSetT R); //判集合this与R相等 friend istream operator (istream in, bitSetT R); //输入 friend ostream operator (ostream out, bitSetT R); //输出 private: int setSize; //集合大小 int vecterSize; //位数组大小 unsigned short *bitVector; //存储集合元素的位数组 };;使用示例;//s1: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} index = s1.SubSet (s4); //判断s1是否为s4子集 cout index endl; //结果，index = 0 //s1: {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} //s4: {7, 8, 9} equal = s1 == s2; //集合s1与s2比较相等 cout equal endl; //为0, 两集合不等;构造函数的实现;template class T bitSetT::bitSet (const bitSetT R) { //复制构造函数 setSize = R.setSize; //集合元素个数 vectorSize