文档介绍：第五章集合
学习要点:
以集合为基础的抽象数据类型
理解集合的概念。
理解以集合为基础的抽象数据类型。
掌握用位向量实现集合的方法。
掌握用链表实现集合的方法。
11/11/2017
1
福州大学数学与计算机科学学院
引言
集合的概念的原形
银行中所有储户帐号的集合;图书馆中
所有藏书的集合;一个程序中所有标识
符的集合;2003级34班全体同学的集合等
11/11/2017
2
福州大学数学与计算机科学学院
引言
集合的概念与术语
集合:集合是由元素(成员)组成的一个类。
原子:不可再分的元素。
多重集合:允许同一元素在集合中多次出现的集合称为多重集合。
有序集:当由原子组成的集合具有线性序关系“<”时,称该集合为有序集。“<”是集合的一个线性序,它满足:(1)若a、b是集合中任意2个原子,则a<b,a=b和 b<a三者必居其一;(2)a,b和c是集合中的原子,且a<b,b<c则a<c(传递性)。
11/11/2017
3
福州大学数学与计算机科学学院
引言
集合的概念与术语
记录:集合中的元素通常是记录。
项(域):元素的属性。元素通常有多个项。
键(值):能唯一地标识元素的值。它也是元素的属性。有序集通常以键(值)的序为序。
约定以下常将一个元素当作一个键来处理,但要记住键只是元素记录中许多域中的一个域。
11/11/2017
4
福州大学数学与计算机科学学院
引言
集合的记号
枚举式:把集合的元素枚举在一对花括号中。
例如{1,4}表示由1和4两个元素组成的集合。
集合中元素的枚举顺序是任意的。例如{1,4}
和{4,1}表示同一集合。这种方式只对有穷
集可行。
解析式:把集合的元素应满足的条件解析地表
达在一对花括号中。例如{ x|存在整数y,使
x = y2 }表示由全体完全平方数组成的集合。这
种方式既可表示有穷集,又可表示无穷集。
11/11/2017
5
福州大学数学与计算机科学学院
引言
集合的基本运算
元素与集合之间的成员关系:xA
集合之间的包含关系:AB
集合之间的并:A∪B
集合之间的交:A∩B
集合之间的差:A-B
集合之间的异或:A㊉B=(A-B ) ∪(B-A)
11/11/2017
6
福州大学数学与计算机科学学院
5 以集合为基础的抽象数据类型
ADT集合支持的基本运算
约定:其中大写字母表示一个集合,小写字母表示集合中的一个元素。
(1) + (A):并集运算。
(2) * (A):交集运算。
(3) - (A):差集运算。
(4) = (A):赋值运算。
(5) = =(A):判等运算。
(6) Member(x):成员运算。
(7) Insert(x):插入运算。
(8) Delete(x):删除运算。
(9) Min( ):最小元运算(仅适用于有序集) 。
(10) Find(x):查找集合运算,作用在一个由不相交集合组成的类上,返回包含元素x的集合的名字。
11/11/2017
7
福州大学数学与计算机科学学院
5 以集合为基础的抽象数据类型
ADT集合的简单实现——用位向量实现
用位向量实现ADT集合
约定所讨论的集合都是全集合{1,2,…,N }的子集,而且N是一个不大的固定整数。对此,任何一个集合A{ 1,2,…,N },都可以用它的特征函数:
来表示。而特征函数δA(x)可以用位向量来表示:
V[size-1]
……
V[3]
V[2]
V[1]
V[0]
15 … 3 2 1 0 15 … 3 2 1 0 15 … 3 2 1 0 …… 15 … 3 2 1 0 15 … 3 2 1 0 15 … 3 2 1 0 15 … 3 2 1 0
11/11/2017
8
福州大学数学与计算机科学学院
5 以集合为基础的抽象数据类型
ADT集合的简单实现——用位向量实现(续)
位向量实现的集合类BitSet的定义
template <class T>
class BitSet
{
public:
BitSet(int setsize);
BitSet(const BitSet<T>& x);
~BitSet(void);
BitSet<T>& operator= (const BitSet<T>& x);
int Member(const T& x);
int operator== (const BitSet<T>& x) const; }
11/11/2017
9
福