清华大学：《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 Type> 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 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 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); }