【数据结构讲解】集合和搜索

【数据结构讲解】集合和搜索

ID:40124581

大小:814.00 KB

页数:176页

时间:2019-07-22

【数据结构讲解】集合和搜索_第1页
【数据结构讲解】集合和搜索_第2页
【数据结构讲解】集合和搜索_第3页
【数据结构讲解】集合和搜索_第4页
【数据结构讲解】集合和搜索_第5页
资源描述:

《【数据结构讲解】集合和搜索》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、集合及其表示等价类与并查集静态搜索表二叉搜索树最优二叉搜索树AVL树小结第七章集合与搜索集合基本概念集合及其表示集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素),也可以是集合。集合的成员必须互不相同。在算法与数据结构中所遇到的集合,其单元素通常是整数、字符、字符串或指针,且同一集合中所有成员具有相同的数据类型。colour={red,orange,yellow,green,black,blue,purple,white}name={“An”,“Cao”,“Liu”,“Ma”,“Peng”,“Wang”,“zhang”}集合中的成员一般是无序的,

2、没有先后次序关系。但在表示它时,常常写在一个序列里。我们常设定集合中的单元素具有线性有序关系,此关系可记作“<”,表示“优先于”。若a,b是集合中的两个单元素,则ab三者必居其一;若a,b,c是集合中的三个单元素,且a>b,b>c,则a>c。(传递性)整数、字符和字符串都有一个自然的线性顺序。而指针也可以依据其在序列中安排的位置给予一个线性顺序。集合操作有求集合的并、交、差、判存在等。集合运算的文氏(Venn)图集合(Set)的抽象数据类型TemplateclassSet{Set(intMaxSetSize):MaxSiz

3、e(MaxSetSize);voidMakeEmpty(Set&s);intAddMember(Set&s,constTypex);intDelMember(Set&s,constType&x);voidAssign(Set&s1,Set&s2);voidUnion(Set&s1,Set&s2);voidIntersection(Set&s1,Set&s2);voidDifference(Set&s1,Set&s2);intContains(Set&s,constType&x);intEqual(Set&s1,Set&s2);intSubSet(Set&s1,Se

4、t&s2);}用位向量实现集合抽象数据类型集合的位向量(bitVector)类的定义#includeconstintDefaultSize=100;classSet{当集合是全集合{0,1,2,…,n}的一个子集,且n是不大的整数时,可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时,可建立全集合成员与整数0,1,2,…的一一对应关系,用位向量来表示该集合的子集。private:int*bitVector;intMaxSize;public:Set(intMaxSetSize=DefaultSize);~Set(){de

5、lete[]bitVector;}voidMakeEmpty(){for(inti=0;i

6、ight);};使用示例Sets1,s2,s3,s4,s5;intindex,equal;//构造集合for(intk=0;k<10;k++)//集合赋值{s1.AddMember(k);s2.AddMember(k+7);}//s1:{0,1,2,…,9},s2:{7,8,9,…,16}s3=s1+s2;//求s1与s2的并{0,1,…,16}s4=s1*s2;//求s1与s2的交{7,8,9}s5=s1-s2;//求s1与s2的差{0,1,2,3,4,5,6}index=s1.SubSet(s4);//求s4在s1中首次匹配cout<

7、//位置,index=7equal=s1==s2;//集合s1与s2比较相等cout<0);bitVector=newint[MaxSize];assert(bitVector!=0);for(inti=0;i=0&&x

8、ize);

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

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

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