《集合与字典》ppt课件

《《集合与字典》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第六章集合与字典赵建华南京大学计算机系内容集合及其表示并查集与等价类字典跳表散列集合的基本概念具有某种共同性质”的若干不同的对象合在一起构成集合。在算法与数据结构中所遇到的集合中所有成员具有相同的数据类型。例如：colour={red,orange,yellow,green,black,blue,purple,white}一些说明作为数据结构中的集合在概念上讲，元素之间是无序的。但是可能为了效率，在实现中将元素之间的某个序关系和元素的存储方式对应起来；不同的表示方法：保存实际数据值保存下标或者reference在父集中存放指示信息，表示是否在

2、子集合内。允许相同元素多次出现的称为多重集合或者包。集合的运算还包括：判断一个元素是否在集合中集合是否为空A是否为B的子集以及添加/删除元素等操作遍历所以元素求满足某个条件的所有元素组成的子集AB或A+BAB或ABA-BAAABBB集合（Set）的抽象数据类型templateclassSet{public:virtualSet()=0;//构造函数virtualmakeEmpty()=0;//置空集合virtualbooladdMember(constTx)=0;virtualbooldelMember(constTx)

3、=0;virtualSetintersectWith(Set&R)=0;//集合的交运算virtualSetunionWith(Set&R)=0;//集合的并运算virtualSetdifferenceFrom(Set&R)=0;//集合的差运算virtualboolContains(Tx)=0;virtualboolsubSet(Set&R)=0;virtualbooloperator==(Set&R)=0;//判集合是否相等};集合的位向量实现当集合是全集合{0,1,2,…,n}的一个子集，

4、且n是不大的整数时，可用位(0,1)向量来实现集合。对于每个i，有一个二进位；取值1或0分别表示在集合与不在集合中。如果n小于32，可以直接用32位整数表示；否则可以使用整数数组表示。当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数0,1,2,…的一一对应关系，然后用位向量来表示该集合的子集。如果全集用数组表示，那么其子集也可以用位向量表示。但是，此时需要保证全集不改变。位向量集合的类定义#include#includeconstintDefaultSize=50;classbitSet

5、{//用位向量来存储集合元素,集合元素的范围在0到//setSize-1之间。数组采用16位无符号短整数实现intsetSize;//集合大小intvecterSize;//位数组大小unsignedshort*bitVector;//bitVector[i]的第j位为0/1表示第i*16+j个元素是否在此集合内。位向量集合的类定义（二）public:bitSet(intsz=DefaultSize);//构造函数bitSet(constbitSet&R);//复制构造函数～bitSet(){delete[]bitVector;}//析构函数

6、intgetMember(constintx);//取集合元素xvoidputMember(constintx,intv);//改集合元素xvoidmakeEmpty(){//置空集合for(inti=0;i&operator=(constbitSet&R);bitSetoperator+(constb

7、itSet&R);bitSetoperator*(constbitSet&R);bitSetoperator-(constbitSet&R);boolContains(constintx);boolsubSet(bitSet&R);//判this是否R的子集booloperator==(bitSet&R);//判集合this与R相等friendistream&operator>>(istream&in,bitSet&R);//输入friendostream&operator<<(ostream&out,bitSet&R);//输出

8、}构造函数的实现bitSet::bitSet(intsz):setSize(sz){//构造函数assert(setSize>0);//检查参数的合理性vector