内容集合的基本概念一些说明集合的运算集合（Set）的抽象数据类型集合的位向量实现位向量集合的类定义位向量集合的类定义（二）位向量集合的类定义（三）构造函数的实现复制构造函数getMemberputMemberAdd/deletemember另一种实现位集合的方法集合的并运算集合的交运算集合的差运算集合的子集判断判断集合相等集合的有序链表类的定义（链表结点）集合的有序链表类的定义（链表）加入一个元素的操作删除一个元素集合的合并（1）集合的合并（2）集合并运算的例子判断集合相等内容等价关系/等价类并查集（disjointset）用途等价关系建立的例子并查集(Union-FindSets)S={0,1,2,3,4,5,6,7,8,9}S1={0,6,7,8},S2={1,4,9},S3={2,3,5}初始时,用构造函数UFSets(s)构造一个森林,每棵树只有一个结点,表示集合中各元素自成一个子集合。Find(i)：寻找集合元素i所在子树的根。Find(i)==Find(j)表明i和j在同一个子集中Union(i,j)：将i和j所在的子集合并S1用双亲表示实现并查集的类定义UFSets::UFSets(intsz){//构造函数：sz是集合元素个数，双亲数组的//范围为parent[0]～parent[size-1]。size=sz;//集合元素个数parent=newint[size];//创建双亲数组for(inti=0;i<size;i++)parent[i]=-1;//每个自成单元素集合};并查集操作的算法查找-50123Find的非递归版本Union的实现下标parent退化情况及其改进按树结点个数合并结点个数多的树的根结点作根voidUFSets::WeightedUnion(intRoot1,intRoot2){//按Union的加权规则改进的算法inttemp=parent[Root1]+parent[Root2];if(parent[Root2]<parent[Root1]){parent[Root1]=Root2;//Root2中结点数多parent[Root2]=temp;//Root1指向Root2}else{parent[Root2]=Root1;//Root1中结点数多parent[Root1]=temp;//Root2指向Root1}};按树高度合并高度高的树的根结点作根按高度合并Find操作的折叠规则intUFSets::CollapsingFind(inti){//使用折叠规则的搜索算法for(intj=i;parent[j]>=0;j=parent[j]);//让j循双亲指针走到根while(parent[i]!=j){//换parent[i]到jinttemp=parent[i];parent[i]=j;i=temp;}returnj;}实际例子内容字典（Dictionary）字典的典型操作字典的抽象数据类型字典的抽象数据类型（续）索引项具有重复元素的字典字典的线性表描述#include<iostream.h>#include“SeqList.h”constintdefaultSize=50;template<classE,classK>classSortedList:publicSeqList{public:intSearch(Kk1)const;//搜索voidInsert(constKk1,E&e1);//插入boolRemove(constKk1,E&e1);//删除};基于有序顺序表的顺序搜索算法有序顺序表顺序搜索的时间代价在顺序搜索情形，搜索第i(1≤i≤n)个元素需要比较i次，假定按等概率搜索各元素：这与一般顺序表情形相同。但搜索不成功时不需一直比较到表尾，只要发现下一个元素的值比给定值大，就可断定搜索不成功。基于有序顺序表的折半搜索搜索成功的例子搜索失败的例子template<classE,classK>intSortedList<E,K>::BinarySearch(Kk1,constintlow,constinthigh)const{//折半搜索的递归算法，用到E的重载操作“<”和“>”intmid=0;//元素序号从1开始if(low<=high){mid=(low+high)/2;if(data[mid-1]<k1)//元素序号与下标差一mid=BinarySearch(k1,mid+1,high);elseif(data[mid-1]>k1)mid=BinarySearch(k1,low,mid-1);}retur