北京师范大学数据结构教学资料 第6章集合与字典ppt课件.ppt

《北京师范大学数据结构教学资料 第6章集合与字典ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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

2、”，表示“优先于”。整数、字符和串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。在某些集合中保存实际数据值，某些集合中保存标示元素是否在集合中的指示信息。如学校开设的所有课程的编码属于前者，一个学期开设的课程构成的集合属于后者。3AB或A+BAB或ABA-BAAABBB集合（Set）的抽象数据类型templateclassSet{public:virtualSet()=0;//构造函数virtualmakeEmpty()=0;//置空集合virtualbooladdMem

3、ber(constTx)=0;4virtualbooldelMember(constTx)=0;virtualSetintersectWith(Set&R)=0;//集合的交运算virtualSetunionWith(Set&R)=0;//集合的并运算virtualSetdifferenceFrom(Set&R)=0;//集合的差运算virtualboolContains(Tx)=0;virtualboolsubSet(Set&R)=0;virtualbooloperator=

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

5、include#includeconstintDefaultSize=50;classbitSet{//用位向量来存储集合元素,集合元素的范围在0到//setSize-1之间。数组采用16位无符号短整数实现public:bitSet(intsz=DefaultSize);//构造函数bitSet(constbitSet&R);//复制构造函数～bitSet(){delete[]bitVector;}//析构函数intgetMember(constTx);//取集合元素x

6、7voidputMember(constTx,intv);//改集合元素xvoidmakeEmpty(){//置空集合for(inti=0;i&operator=(constbitSet&R);bitSetoperator+(constbitSet&R);bitSetoperator*(con

7、stbitSet&R);bitSetoperator-(constbitSet&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,bitS

8、et&R);//输出private:intsetSize;//集合大小intvecterSize;//位数组大小unsignedshort*bitVector;//存储集合元素的位数组};9使用示例Sets1,s2,s3,s4,s5;intindex,equal;for(intk=0;k<10;k++){//集合赋值s1.A