清华大学：《C++数据结构》第七章 集合与搜索

第七章集合与搜索 合及其表示 价类与并查集 静态搜索表 二叉搜索 最佳二又搜索树 ⊥AVL树

集合及其表示 集合基本概念 集合是成员(对象或元素)的一个群集。 集合中的成员可以是原子(单元素),也 可以是集合。 集合的成员必须互不相同。 在算法与数据结构中所遇到的集合,其 单元素通常是整数、字符、字符串或指 针,且同一集合中所有成员具有相同的 数据类型

colour= red, orange, yellow, green. black, blue, purple, white 3 name={“An”,“Cao”,“Liu”,“Ma”, Peng? Wang",“ zhang” 集合中的成员一般是无序的,但在表示 它时,常写在一个序列里。 常设定集合中的单元素具有线性有序关 系,此关系可记作“<”,表示“优先 于” 整数、字符和字符串都有一个自然线性 顺序。指针也可依据其在序列中安排的 位置给予一个线性顺序

A B B A B AUB或A+B A∩B或A×B A-B 集合(Se的抽象数据类型 template class Set i Set (int MaxSetsize): MaxSize(Max Setsize) void MakeEmpty(Set& s); int AddMember(Set& S, const Type x) int DelMember (Set& S, const Type& x);

template class Set { Set (int MaxSetSize) : MaxSize(MaxSetSize); void MakeEmpty (Set& s); int AddMember (Set& s, const Type x); int DelMember (Set& s, const Type& x); AB 或 A+B AB 或 AB A-B A B A B A B

void Assign (Set& sl, Set& s2) void Union(Set& sl, Set& s2) void Intersection(Set& sl, set& S2); void Difference(Set& sl, set& s2); int Contains(Set& S, const Type& x); int Equal(Set&sl, Set& S2); int SubSet(Set& sl, set& s2);

void Assign (Set& s1, Set& s2); void Union (Set& s1, Set& s2); void Intersection (Set& s1, Set& s2); void Difference (Set& s1, Set& s2); int Contains (Set& s, const Type& x); int Equal (Set& s1, Set& s2); int SubSet (Set& s1, Set& s2); }

用位向量实现集合抽象数据类型 口当集合是全集合{0,1,2,…,m}的一个子 集,且m是不大的整数时,可用位(0,1)向量 来实现集合。 当全集合是由有限的可枚举的成员组成的 集合时,可建立全集合成员与整数0 2,…的一一对应关系,用位向量来表示该 集合的子集

集合的位向量 bit vector)类的定义 include assert.h> const int Defaultsize =100 class set i pl rivate int bit Vector; int max size. public Set int Max Setsize =Defaultsize ) Set oi delete l bit vector;)

#include const int DefaultSize = 100; class Set { private: int * bitVector; int MaxSize; public: Set ( int MaxSetSize = DefaultSize ); ~Set ( ) { delete [ ] bitVector; }

void MakeEmpty (i for( int 1=0; 1=o&&x< maxSize bit Vector[x:1;j int AddMember( const int x) int DelMember( const int x ) Set operator=( Set& right ) Set operator + Set& right )

void MakeEmpty ( ) { for ( int i = 0; i = 0 && x < MaxSize ? bitVector[x] : -1; } int AddMember ( const int x ); int DelMember ( const int x ); Set operator = ( Set& right ); Set operator + ( Set& right );

Set operator( Set& right Set operator-( Set& right ) int Contains( const int x )3 int SubSet( Set& right ) int operator -- Set& right 使用示例 Set sl s2 s3 s4. s5: int index, equal for(intk=0;k<10;k++)∥集合赋值 &sl. AddMember(k ) S2 AddMember(k +7);) ∥s1:{0,1,2,…,9},s2:{7,8,9,…,16}

Set operator * ( Set& right ); Set operator - ( Set& right ); int Contains ( const int x ); int SubSet ( Set& right ); int operator == ( Set& right ); }; Set s1, s2, s3, s4, s5; int index, equal; for ( int k = 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与2的交{7,8,9} s5=s1-s2;求s1与S2的差{0,1,,6} ∥s1:{0,1,2,……,9} index=sl. Subset(s4);.断s1是否为s4子集 cout<< index<<end;∥结果, index=0 ∥s1:{0,1,2,3,4,5,6,7,8,9} / s4:{7,8,9 equal=sl=s2;∥/合1与2比软相等 cout<< equal<<endl;∥为0,两集合不等

s3 = s1+s2; //求s1与s2的并 { 0, 1, …, 16 } s4 = s1*s2; //求s1与s2的交 { 7, 8, 9 } s5 = s1-s2; //求s1与s2的差 { 0, 1, …, 6 } // s1 : { 0, 1, 2, …, 9 } index = s1.SubSet ( s4 ); //判断s1是否为s4子集 cout << index << endl; //结果，index = 0 // s1 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } // s4 : { 7, 8, 9 } equal = s1 == s2; //集合s1与s2比较相等 cout << equal << endl; //为0, 两集合不等