第六章集合与字典ppt课件.ppt

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

1、第六章集合与字典集合及其表示并查集与等价类字典散列1集合及其表示集合是成员(元素)的一个群集。集合中的成员可以是原子(单元素)，也可以是集合。集合的成员必须互不相同。在算法与数据结构中所遇到的集合，其单元素通常是整数、字符、字符串或指针，且同一集合中所有成员具有相同的数据类型。例：colour={red,orange,yellow,green,black,blue,purple,white}集合基本概念2集合中的成员一般是无序的，但在表示它时，常写在一个序列里。常设定集合中的单元素具有线性有序关系，此关系可记作“<”，表示

2、“优先于”。整数、字符和字符串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。3集合（Set）的抽象数据类型templateclassSet{public:virtualSet()=0;//构造函数virtualmakeEmpty()=0;//置空集合virtualbooladdMember(constTx)=0;AB或A+BAB或ABA-BAAABBB4virtualbooldelMember(constTx)=0;virtualSetintersectWith(Set

3、&R)=0;//集合的交运算virtualSetunionWith(Set&R)=0;//集合的并运算virtualSetdifferenceFrom(Set&R)=0;//集合的差运算virtualboolContains(Tx)=0;virtualboolsubSet(Set&R)=0;virtualbooloperator==(Set&R)=0;//判集合是否相等};5用位向量实现集合抽象数据类型当集合是全集合{0,1,2,…,n}的一个子集，且n是不大的整数时，可用位(0,

4、1)向量来实现集合。当全集合是由有限个可枚举的成员组成时，可建立全集合成员与整数0,1,2,…的一一对应关系，用位向量来表示该集合的子集。一个二进位有两个取值1或0，分别表示在集合与不在集合。如果采用16位无符号短整数数组bitVector[]作为集合的存储，就要考虑如何求出元素i在bitVector数组中的相应位置。6集合的位向量(bitVector)类的定义#include#includeconstintDefaultSize=50;templateclass

5、bitSet{//用位向量来存储集合元素,集合元素的范围在0到//setSize-1之间。数组采用16位无符号短整数实现public:bitSet(intsz=DefaultSize);//构造函数bitSet(constbitSet&R);//复制构造函数～bitSet(){delete[]bitVector;}//析构函数unsignedshortgetMember(constTx);//读取集合元素x7voidputMember(constTx,unsignedshortv);//将值v送入集合元素xvoidm

6、akeEmpty(){//置空集合for(inti=0;i&operator=(constbitSet&R);bitSet&operator+(constbitSet&R);bitSet&operator*(constbitSet&R);bitSet&operator-(constbi

7、tSet&R);boolContains(constTx);//判x是否集合this的成员8boolsubSet(bitSet&R);//判this是否R的子集booloperator==(bitSet&R);//判集合this与R相等friendistream&operator>>(istream&in,bitSet&R);//输入friendostream&operator<<(ostream&out,bitSet&R);//输出private:intsetSize;//集合大小intve

8、ctorSize;//位数组大小unsignedshort*bitVector;//存储集合元素的位数组};9使用示例bitSets1,s2,s3,s4,s5;boolindex,equal;for(intk=0;k<10;k++){//集合赋值s1.addMember(k);s2.addMe