《集合与查找》PPT课件

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

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

2、”}集合中的成员一般是无序的，但在表示它时，常写在一个序列里。常设定集合中的单元素具有线性有序关系，此关系可记作“<”，表示“优先于”。整数、字符和字符串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。3集合运算AB或A+BABABAB或ABABA-B4用位向量实现集合抽象数据类型当集合是全集合{0,1,2,…,n}的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数0,1,2,…的一一对应关系，用位

3、向量来表示该集合的子集。5集合的位向量(bitVector)类的定义#includeconstintDefaultSize=100;classSet{private:int*bitVector;//集合的位向量数组intMaxSize;//最大元素个数public:Set(intMaxSetSize=DefaultSize);~Set(){delete[]bitVector;}6voidMakeEmpty(){//置空for(inti=0;i

4、i]=0;}intAddMember(constintx);//加intDelMember(constintx);//删Set&operator=(Set&right);//赋值Set&operator+(Set&right);//并Set&operator*(Set&right);//交Set&operator-(Set&right);//差intContains(constintx);//判存在intSubSet(Set&right);//判子集intoperator==(Set&right);//判相

5、等};7用位向量实现集合时部分操作的实现Set::Set(intMaxSetSize):MaxSize(MaxSetSize){assert(MaxSize>0);//判参数合理否bitVector=newint[MaxSize];//分配空间assert(bitVector!=NULL);for(inti=0;i=0&&x

6、itVector[x]=1;return1;}return0;}00000000000919010000000009intSet::DelMember(constintx){if(x>=0&&x

7、t.bitVector[i];}this01110000000right0111000011011Set&Set::operator+(Set&right){//求并assert(MaxSize==right.MaxSize);for(inti=0;i

8、

9、right.bitVector[i];return*this;}thisrightthis01110000110001001010100111010111012Set&Set::o

10、perator*(Set&right){//求交assert(MaxSize==right.MaxSize);for(inti=0;i