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

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

ID:58677184

大小:553.50 KB

页数:105页

时间:2020-10-05

第六章集合与字典ppt课件.ppt_第1页
第六章集合与字典ppt课件.ppt_第2页
第六章集合与字典ppt课件.ppt_第3页
第六章集合与字典ppt课件.ppt_第4页
第六章集合与字典ppt课件.ppt_第5页
资源描述:

《第六章集合与字典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

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。