7集合和搜索.ppt

文档介绍：集合及其表示
等价类与并查集
静态搜索表
二叉搜索树
最优二叉搜索树
AVL树
小结
第七章集合与搜索
集合基本概念
集合及其表示
集合是成员(对象或元素)的一个群集。集合中的成员可以是原子(单元素),也可以是集合。
集合的成员必须互不相同。
在算法与数据结构中所遇到的集合,其单元素通常是整数、字符、字符串或指针,且同一集合中所有成员具有相同的数据类型。
colour = { red, orange, yellow, green, black, blue, purple, white } name = { “An”, “Cao”, “Liu”, “Ma”, “Peng”, “Wang”, “zhang”}
集合中的成员一般是无序的,没有先后次序关系。但在表示它时,常常写在一个序列里。
我们常设定集合中的单元素具有线性有序关系,此关系可记作“<”,表示“优先于”。
若a, b是集合中的两个单元素,则a<b, a==b, a>b三者必居其一;
若a, b, c是集合中的三个单元素,且a>b, b>c,则a>c。(传递性)
整数、字符和字符串都有一个自然的线性顺序。而指针也可以依据其在序列中安排的位置给予一个线性顺序。
集合操作有求集合的并、交、差、判存在等。
集合运算的文氏(Venn)图
集合(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 );
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 );
}
用位向量实现集合抽象数据类型
集合的位向量(bit Vector)类的定义
#include <>
const int DefaultSize = 100;
class Set {
当集合是全集合{ 0, 1, 2, …, n }的一个子集,且 n是不大的整数时,可用位(0, 1)向量来实现集合。
当全集合是由有限的可枚举的成员组成的集合时,可建立全集合成员与整数 0, 1, 2, …的一一对应关系,用位向量来表示该集合的子集。
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 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, …, 1