福州大学：《数据结构》课程教学资源（PPT课件讲稿）第七章 集合与搜索

第七章集合与搜索 集合及其表示 渣集 静态搜索表 u二叉搜索树 AVL树

◼ 集合及其表示 ◼ 并查集 ◼ 静态搜索表 ◼ 二叉搜索树 ◼ AVL树

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

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

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

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

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

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

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

集合的位向量 bit Vector)类的定义 #include const int Defaultsize =100 class set i private int* bit Vector int maxsize public. Set( int MaxSetsize= DefaultSize ) Seti delete[ bit vector;)

集合的位向量(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;} 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 ) 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与2的并{0,1,…,16} s4=s1*s2;1求s1与2的交{7,8,9 s5=s1-s2;/s1与S2的差{0,1,……,6} ∥s1:{0,1,2,…,9} index=sl. Subset(s4);/4在s1中首次匹配 cout<< index<<end;∥置, index=7 ∥s1:{0,1,2,3,4,5,6,7,8,9} 4:{7,8,9} equal=Sl== s2 集合S1与s2比较相等 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 ); //s4在s1中首次匹配 cout << index << endl; //位置，index = 7 // s1 : { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 } // s4 : { 7, 8, 9 } equal = s1 == s2; //集合s1与s2比较相等 cout << equal << endl; //为0, 两集合不等