第六章集合与字典.ppt
《第六章集合与字典.ppt》由会员分享,可在线阅读,更多相关《第六章集合与字典.ppt(138页珍藏版)》请在三一文库上搜索。
1、第六章 集合与字典,赵建华 南京大学计算机系,内容,集合及其表示 并查集与等价类 字典 跳表 散列,集合的基本概念,具有某种共同性质”的若干不同的对象合在一起构成集合。 在算法与数据结构中所遇到的集合中所有成员具有相同的数据类型。 例如: colour = red, orange, yellow, green, black, blue, purple, white ,一些说明,作为数据结构中的集合 在概念上讲,元素之间是无序的。 但是可能为了效率,在实现中将元素之间的某个序关系和元素的存储方式对应起来; 不同的表示方法: 保存实际数据值 保存下标或者reference 在父集中存放指示信息,表
2、示是否在子集合内。 允许相同元素多次出现的称为多重集合或者包。,集合的运算,还包括: 判断一个元素是否在集合中 集合是否为空 A是否为B的子集 以及添加/删除元素等操作 遍历所以元素 求满足某个条件的所有元素组成的子集,AB 或 A+B AB 或 AB A-B,A,A,A,B,B,B,集合(Set)的抽象数据类型,template class Set public: virtual Set() = 0; /构造函数 virtual makeEmpty() = 0; /置空集合 virtual bool addMember (const T x) = 0; virtual bool delMem
3、ber (const T x) = 0; virtual Set intersectWith (Set,集合的位向量实现,当集合是全集合 0,1,2,n 的一个子集,且n是不大的整数时,可用位(0,1)向量来实现集合。 对于每个i,有一个二进位;取值1或0分别表示在集合与不在集合中。 如果n小于32,可以直接用32位整数表示; 否则可以使用整数数组表示。 当全集合是由有限个可枚举的成员组成时,可建立全集合成员与整数0,1,2,的一一对应关系,然后用位向量来表示该集合的子集。 如果全集用数组表示,那么其子集也可以用位向量表示。但是,此时需要保证全集不改变。,位向量集合的类定义,#include
4、#include const int DefaultSize = 50; class bitSet /用位向量来存储集合元素, 集合元素的范围在0到 /setSize-1之间。数组采用16位无符号短整数实现 int setSize; /集合大小 int vecterSize; /位数组大小 unsigned short *bitVector; /bitVectori的第j位为0/1表示第i*16+j个元素是否在此集合内。,位向量集合的类定义(二),public: bitSet (int sz = DefaultSize); /构造函数 bitSet (const bitSet /删除老成员x,
5、位向量集合的类定义(三),bitSet /输出 ,构造函数的实现,bitSet:bitSet (int sz) : setSize (sz) /构造函数 assert (setSize 0); /检查参数的合理性 vectorSize = (setSize+15) /16; /vectorSize*16必须大于setSize bitVector = new int vectorSize; /分配空间 assert (bitVector != NULL); /检查存储分配是否成功 for (int i = 0; i vectorSize; i+) bitVectori = 0; /初始化为空集
6、;,复制构造函数,bitSet:bitSet (const bitSet,getMember,/判断x是否在这个集合中 int bitSet:getMember (const int x) int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 return int (elem (15-id) 注:第x个元素存放在bitVector的第x/16个元素的(从高位起)第x%16位上。,0,1,1,0,0,0,1,0,0,1,0,0,0,1,0,0,putMember,/如v为1,将x加入集合
7、;(如果x在集合中,操作无效果) /否则将x从集合中删除;(如果x不在集合中,操作无效果) void bitSet:putMember (const int x, int v) /将值v送入集合元素x int ad = x/16, id = x%16; /计算数组元素下标 unsigned short elem = bitVector ad; /取x所在数组元素 int temp = elem (15-id); /右移,该位移至末尾 elem = elem (id+1); /送回 ;,0,1,1,0,0,0,1,0,0,1,0,0,0,1,0,0,设:id=2;,右移后,temp为000000
8、0000000011 elem左移后为:0001001000100000,Add/delete member,bool bitSet:addMember (const int x) assert (x = 0 ,另一种实现位集合的方法,设立数组:bitArray16= 0x8000, 0x4000, 0x2000, 0x1000, 0x0800, 0x0400, 0x0200, 0x0100, 0x0080, 0x0040, 0x0020, 0x0010, 0x0008, 0x0004, 0x0002, 0x0001 判断bitVector的第i个元素的第j位是否为1 bitArrayj ,集
9、合的并运算,bitSet bitSet: /求集合this与R的并 operator + (const bitSet,集合的交运算,/求集合this与R的交 bitSet bitSet:operator * (const bitSet /按位求“与”, 由第三个集合返回 ,集合的差运算,/求集合this与R的差 bitSet bitSet:operator - (const bitSet,集合的并,集合的交,集合的差,集合的子集判断,/判this是否R的子集 bool bitSet:subSet (bitSet,判断集合相等,template bool bitSet:operator = (b
10、itSet,用有序链表实现集合,链表的每个结点存放集合的一个成员。 各结点所表示的成员 e0, e1, , en 在链表中按某种顺序排列,即 e0 e1 en。 有序链表可以表示无穷全集的子集,集合中的元素个数也没有限制; 本课程内使用带有表头结点的有序链表,也可以使用其它的链表形式。,集合的有序链表类的定义 (链表结点),template struct SetNode /集合的结点类定义 T data; /每个成员的数据 SetNode *link; /链接指针 SetNode() : link (NULL); /构造函数 SetNode (const T 注意:可参照带表头的链表的实现方式
11、,集合的有序链表类的定义(链表),template class LinkedSet /集合的类定义 private: SetNode *first, *last; /有序链表表头指针, 表尾指针 public: LinkedSet () first = last = new SetNode; LinkedSet (LinkedSet,加入一个元素的操作,template bool LinkedSet:addMember (const T,d1,d2,pre,data,s,插入时,必然有d1datad2,删除一个元素,template bool LinkedSet:delMember (cons
12、t T,集合的合并(1),template LinkedSet LinkedSet: operator + (LinkedSet /end of else if (pa-data data) ,待续,集合的合并(2),else /R集合元素值小 pc-link = new SetNode(pb-data); pb = pb-link; /end of else pc = pc-link; /扫尾处理 if (pa != NULL) p = pa; /this集合未扫完 else p = pb; /或R集合未扫完 while (p != NULL) /向结果链逐个复制 pc-link = new
13、 SetNode(p-data); pc = pc-link; p = p-link; /end of while pc-link = NULL; temp.last = pc; /链表收尾 return temp; ;,回忆一下以前的多项式合并算法: 1、一元多项式被表示成为不同次数的项的集合, 2、每个项包括系数、指数,且从小到大排列;,请考虑几个问题: 1、得到的集合仍然是从小到大排列吗? 2、既在A中,又在B中的元素会重复出现在并集中吗?,集合并运算的例子,判断集合相等,bool LinkedSet: operator = (LinkedSet,内容,集合及其表示 并查集与等价类 字典
14、 跳表 散列,等价关系/等价类,若用符号“”表示集合上的等价关系,则对于该集合中的任意对象x, y, z,下列性质成立: 自反性:x x (即等于自身)。 对称性:若 x y, 则 y x。 传递性:若 x y且 y z, 则 x z。 从数学上看,等价类是对象(或成员)的集合,在一个等价类中的各个元素满足等价关系。 一个集合上的等价关系将该集合划分成为互不相交的子集。,并查集(disjoint set),问题 高效地建立和表示某个集合上有一个等价关系 建立过程如下: 已知一个集合S,并且已知一个关系r。这个关系r通过一个二元组集合来表示; 等价关系R是r的自反/传递/对称闭包; 我们通过逐个
15、读入r中的二元组,高效建立起等价关系R。,用途,主要用于按照某些已知的等价关系事实,将一个集合中的元素分划成为互不相交的子集。 由已知事实推导出等价的两个元素一定在同一子集中。,等价关系建立的例子,给定集合 S = 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 , 已知: 0 4, 3 1, 6 10, 8 9, 7 4, 6 8, 3 5, 2 11, 11 0 归并过程: 初始0,1,2,3,4,5,6,7,8,9,10,11 0 4 0,4,1,2,3,5,6,7,8,9,10,11 3 1 0,4,1,3,2,5,6,7,8,9,10,11 6 10 0,4
16、,1,3,2,5,6,10,7,8,9,11 8 9 0,4,1,3,2,5,6,10,7,8,9,11 7 4 0,4,7,1,3,2,5,6,10,8,9,11 6 8 0,4,7,1,3,2,5,6,8,9,10,11 3 5 0,4,7,1,3,5,2,6,8,9,10,11 2 11 0,4,7,1,3,5,2,11,6,8,9,10 11 0 0,2,4,7,11,1,3,5,6,8,9,10,并查集 (Union-Find Sets),并查集支持一个有穷集合上的某些操作 并查集支持以下三种操作: Union (Root1, Root2) /合并操作 Find (x) /查找操作
17、UFSets (s) /构造函数 对于并查集来说,分划的每个子集用一棵树表示。也可以用树的根结点来代表子集。 子树采用双亲表示法。 全集本身可以使用其它数据结构表示。这里我们使用数组表示,用下标指示元素。,S=0,1,2,3,4,5,6,7,8,9 S1= 0, 6, 7, 8, S2= 1, 4, 9, S3= 2, 3, 5,为简化讨论,忽略实际的集合名,仅用表示集合的树的根来标识集合。,0,1,2,3,4,5,6,7,8,9,4,4,3,2,3,2,0,0,0,4,初始时, 用构造函数 UFSets(s) 构造一个森林, 每棵树只有一个结点, 表示集合中各元素自成一个子集合。 Find(
18、i):寻找集合元素 i所在子树的根。 Find(i) = Find(j)表明i和j在同一个子集中 Union(i, j):将 i 和 j 所在的子集合并,S1,下标 parent,集合 S1, S2 和 S3 的双亲表示,-4 4 -3 2 -3 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,S2,S3,S1 S2的可能的表示方法,下标 parent,集合 S1 S2 和 S3 的双亲表示,-7 4 -3 2 0 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,0,7,6,8,4,1,9,4,1,9,0,8,7,6,-7,-7,0,0,0,0,4,4,4,4,4,0,
19、0,0,用双亲表示实现并查集的类定义,const int DefaultSize = 10; class UFSets /集合中的各个子集合互不相交 public: UFSets (int sz = DefaultSize); /构造函数 UFSets() delete parent; /析构函数 UFSets,UFSets:UFSets (int sz) /构造函数:sz 是集合元素个数,双亲数组的 /范围为parent0parentsize-1。 size = sz; /集合元素个数 parent = new intsize; /创建双亲数组 for (int i = 0; i size;
20、 i+) parenti = -1; /每个自成单元素集合 ;,并查集操作的算法 查找,-5,0,1,2,3,0,1,2,3,4,Find (4),Find (3),Find (2),Find (1),Find (0),-5 0 返回 0,int UFSets:Find (int x) /函数搜索并返回包含元素x的树的根。 /递归版本 if (parentx 0) return x; /根的parent值小于0 else return (Find (parentx); ;,Find的非递归版本,int UFSets:Find (int x) /函数搜索并返回包含元素x的树的根。 while (
21、parentx 0) x=parentx; return x; ;,这两个版本都有待改进,Union的实现,void UFSets:Union (int Root1, int Root2) /求两个不相交集合Root1与Root2的并 parentRoot1 += parentRoot2; /注意,root1和root2都是根结点 /-parentRoot1表示集合的元素总数 parentRoot2 = Root1; /将Root2连接到Root1下面 ;,下标 parent,-7 4 -3 2 0 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,0,7,6,8,4,1,9,-7,
22、0,0,0,0,4,4,下标 parent,-4 4 -3 2 -3 2 0 0 0 4,0 1 2 3 4 5 6 7 8 9,退化情况及其改进,Union操作可能引起退化情况: 假设最初 n 个元素构成 n 棵树组成的森林,parenti = -1。做处理Union(n-2, n-1), , Union(1, 2), Union(0, 1)后,将产生退化的树。 此时进行Find的话,平均需要n/2次查询。 改进的方法:尽量使得树变矮 按树的结点个数合并 按树的高度合并 压缩元素的路径长度,朴素合并,-1,-1,-1,-1,-1,0,2,3,4,-3,-5,0,3,2,1,3,3,4,1,3
23、,3,2,2,0,2,3,1,4,Union(0,1),-2,3,-4,1,4,2,1,2,3,4,Union(1,2),Union(2,3),Union(3,4),按树结点个数合并 结点个数多的树的根结点作根,-1,-1,-1,-1,-1,0,1,2,3,4,-1,-1,0,-7,2,5,6,-5,-2,2,2,3,3,2,0,1,3,4,5,6,2,3,3,0,2,0,5,6,2,3,1,4,Union(2, 0),void UFSets : WeightedUnion (int Root1, int Root2) /按Union的加权规则改进的算法 int temp = parentRo
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 第六 集合 字典
链接地址:https://www.31doc.com/p-2566497.html