中国药科大学：《数据结构》课程PPT教学课件（讲稿）第七章 集合与搜索的基本概念

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

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

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

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

colour=f 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 A∪B或A+B A∩B或AxB A-B 集合(Se的抽象数据类型 template <class Type> class Set i 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 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); }