数据结构--集合与搜索

《数据结构--集合与搜索》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

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

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

3、plateclassSet{Set(intMaxSetSize):MaxSize(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)

4、;intContains(Set&s,constType&x);intEqual(Set&s1,Set&s2);intSubSet(Set&s1,Set&s2);}用位向量实现集合抽象数据类型集合的位向量(bitVector)类的定义#includeconstintDefaultSize=100;classSet{当集合是全集合{0,1,2,…,n}的一个子集，且n是不大的整数时，可用位(0,1)向量来实现集合。当全集合是由有限的可枚举的成员组成的集合时，可建立全集合成员与整数0,1,2,…的一

5、一对应关系，用位向量来表示该集合的子集。private:int*bitVector;intMaxSize;public:Set(intMaxSetSize=DefaultSize);~Set(){delete[]bitVector;}voidMakeEmpty(){for(inti=0;i

6、(Set&right);Set&operator*(Set&right);Set&operator-(Set&right);intContains(constintx);intSubSet(Set&right);intoperator==(Set&right);};使用示例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

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<

8、:MaxSize(MaxSetSize){assert(MaxSize>0);bitVector=newint[MaxSize];assert(bitVector!=0);for(inti=0;i=0&&x