Set

集合

集合：互不相同项的无序组合

• 要么指出集合的特殊属性，只有集合中元素才满足的特性
• 要么显式列出集合的所有成员

存储映像

位向量存储表示

位串表示法

• 每个集合S使用一个位串表示，位串中每位代表全集U的一个元素
• 当且仅当全集$U$中第i个元素被包含在子集$S$中时，位向量 第i个元素为1

typedef int BitSet[MAX_SET_SIZE/sizeof(int)];

• 可以实现快速的标准集合运算
• 以使用大量存储空间为代价的

线性表存储表示

线性表表示法

• 每个集合使用一个线性表表示，线性表中存储集合元素

typedef SqList SLSet;
	// 顺序表表示集合
typedef LinkList LLSet;
	// 链表表示集合

• 集合不能包含相同元素，列表可以

  • 可以引入multiset、bag绕过对唯一性的要求
  • 多重集和包是可重复项的无序组合

• 集合是元素的组合，而列表是集合的有序组合

  • 用线性表表示集合时，不必维护线性表的有序排列

集合运算

• 检查元素是否属于集合
• 集合的并集
• 集合的交集

Disjoint Set/Union Find

不相交集/并查集：由某个有限集的一系列不相交子集，及相应 操作构成

• 通常假设集合中元素为整数，或可以映射为整数
• 主要包括find、union操作

存储映像

• 实现应该对find、union有特殊优化

  • 按秩合并：将包含较少结点的集合合并到含有较多结点集合
  • 路径压缩：将每个结点都直接指向根节点

• 大多数实现会使用集合某个元素作为该集合代表

  • 有些对代表没有特殊约定
  • 有的要求代表为子集中最小元素等

树双亲表存储表示

双亲表示法

• 使用树的双亲表示法作存储结构

typedef PTree MFSet;

• 以集合中某个元素作为树根、集合名，其余所有结点都作为根 的孩子结点

• 每个结点只能有一个双亲结点，即只能属于一个集合，适合存储 不相交集

应用

• 生成不相交集
  • 求解无向图中连通分量数量
  • 求解等价问题：两两等价元素作为一类，求解每类元素
• 集合归并
  • 生成迷宫：连通入口、出口连通分量

Map/Dictionary

映射/字典：能查找给定元素、增加新元素、删除元素的集合

• 需要处理的是动态内容的查找，因此需要在查找效率和其他两种 操作中达到平衡

• 数组、散列法、平衡查找树都可以实现字典

  ||散列表|平衡查找树| |——-|——-|———| |渐进时间效率|平均$\in \Theta(1)；最坏$\in \Theta(n)$|$\in \Theta(logn)| |有序性保留|不假定键有序，不保证，不适合按序遍历、按范围查询|保证|

应用

• Extendible Hashing：可扩充散列，用于存储磁盘上大型字典
  • 查找时先计算可能包含查找键K的存储段磁盘地址
  • 然后从磁盘中读取段中所有键，从中查找K
  • 因为存取主存开销较磁盘小很多，宁可多次存取主存