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

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

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

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

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

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

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

AUB或A+BA⌒B或AXB A-B 集合(Set)的抽象数据类型 template <class T> class Set public: virtual Set(=0; /构造函数 virtual makeEmpty()=0; 川置空集合 virtual bool addMember (const Tx)=0; 4

集合（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>intersectWith(Set<T>&R)=0; 川集合的交运算 yirtual Set<T>unionWith(Set<T>&R)=0; 川集合的并运算 virtual Set<T>differenceFrom (Set<T>&R)=0; 川集合的差运算 yirtual bool Contains(Tx)=0; virtual bool subSet (Set<T>&R)=0; virtual bool operator ==(Set<T>&R)=0; /判集合是否相等 }; 5

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