《数据结构》课程教学资源（PPT课件讲稿）第六章 集合与字典

第六章集合与字典 集合及其表示 并查集与等价类 字典 散列

第六章 集合与字典 • 集合及其表示 • 并查集与等价类 • 字典 • 散列 1

集合及其表示 集合基本概念 集合是成员(元素)的一个群集。集合中的成 员可以是原子单元素),也可以是集合 集合的成员必须互不相同。 在算法与数据结构中所遇到的集合,其单元 素通常是整数、字符、字符串或指针,且同 集合中所有成员具有相同的数据类型。 19: colour= red, orange, yellow, green, black, blue, purple, white j

集合及其表示 • 集合是成员(元素)的一个群集。集合中的成 员可以是原子(单元素)，也可以是集合。 • 集合的成员必须互不相同。 • 在算法与数据结构中所遇到的集合，其单元 素通常是整数、字符、字符串或指针，且同 一集合中所有成员具有相同的数据类型。 • 例：colour = { red, orange, yellow, green, black, blue, purple, white } 2 集合基本概念

集合中的成员一般是无序的,但在表示 它时,常写在一个序列里。 常设定集合中的单元素具有线性有序关 系,此关系可记作“<”,表示“优先 于 整数、字符和字符串都有一个自然线性 顺序。指针也可依据其在序列中安排的 位置给予一个线性顺序

• 集合中的成员一般是无序的，但在表示 它时，常写在一个序列里。 • 常设定集合中的单元素具有线性有序关 系，此关系可记作“<”，表示“优先 于”。 • 整数、字符和字符串都有一个自然线性 顺序。指针也可依据其在序列中安排的 位置给予一个线性顺序。 3

A B A B A B AUB或A+BA∩B或A×B A-B 集合(Set)的抽象教据类型 template <class t> lass set public virtual Set(=0 构造函数 virtual makeEmpty=0;∥置空集合 virtual bool addMember (const tx)=0;

集合（Set）的抽象数据类型 template <class T> class Set { public: virtual Set() = 0; //构造函数 virtual makeEmpty() = 0; //置空集合 virtual bool addMember (const T x) = 0; 4 AB 或 A+B AB 或 AB A-B A B A B A B

virtual bool delmember(const Tx)=0; virtual Set<t> intersect With (set<t>&r)=0; /(集合的交运算 virtual Set<t> union With(Set<>&r)=0; 集合的并运算 virtual Set<t> difference from (Set<t>&r)=o ′集合的差运算 virtual bool Contains(Tx)=0; virtual bool subSet(Set<T>&r)=0; virtual bool operator==(Set<t>&r)=0; 判集合是否相等

virtual bool delMember (const T x) = 0; virtual Set<T> intersectWith (Set<T>& R) = 0; //集合的交运算 virtual Set<T> unionWith (Set<T>& R) = 0; //集合的并运算 virtual Set<T> differenceFrom (Set<T>& R) = 0; //集合的差运算 virtual bool Contains (T x) = 0; virtual bool subSet (Set<T>& R) = 0; virtual bool operator == (Set<T>& R) = 0; //判集合是否相等 }; 5