7 集合与搜索.ppt

文档介绍：集合及其表示
并查集
静态搜索表
二叉搜索树
AVL树
第七章集合与搜索
集合基本概念
集合及其表示
集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素),也可以是集合。
集合的成员必须互不相同。
在算法与数据结构中所遇到的集合,其单元素通常是整数、字符、字符串或指针,且同一集合中所有成员具有相同的数据类型。
colour = { red, orange, yellow, green, black, blue, purple, white }
name = { “An”, “Cao”, “Liu”, “Ma”, “Peng”, “Wang”, “zhang”}
集合中的成员一般是无序的,但在表示它时,常写在一个序列里。
常设定集合中的单元素具有线性有序关系,此关系可记作“<”,表示“优先于”。
整数、字符和字符串都有一个自然线性顺序。指针也可依据其在序列中安排的位置给予一个线性顺序。
集合(Set)的抽象数据类型
template <class Type> 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
A
A
B
B
B
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, …的一一对应关系,用位向量来表示该集合的子集。
集合的位向量(bit Vector)类的定义
#include <>
const int DefaultSize = 100;
class Set {
private:
int * bitVector;
int MaxSize;
public:
Set ( int MaxSetSize = DefaultSize );
~Set ( ) { delete [ ] bitVector; }
void MakeEmpty ( ) {
for ( int i = 0; i < MaxSize; i++ )
bitVector[i] = 0;
}
int GetMember ( const int x ) {
return x >= 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 s1, s2, s3, s4, s5; int index, equal;
for ( int k = 0; k < 10; k++ ) //集合赋值
{ ( k ); ( 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