06数据结构---集合与字典

本章主要讲述集合与字典,其中包括并查集:互不相交的集合:需要经常合并集合,需要经常查找元素属于哪个集合;并查集支持以下操作:初始化,合并,查找;用树表示集合;合并方式:将结点数更少的集合作为结点数更多的集合的根的子树,等
展开查看详情

1.第六章 集合与字典 东南大学计算机学院 方效林 方效林 本课件借鉴了清华大学殷人昆老师 和哈尔滨工业大学张岩老师的课件

2. 本章主要内容  并查集 2

3. 并查集  互不相交的集合 ( 等价类的划分 )  需要经常合并集合 ( 等价类的合并 )  需要经常查找元素属于哪个集合 3

4. 并查集  并查集支持以下操作  初始化 UFSets(s): 将 s 中每个元素自成一个集合  合并 Union(Root1,Root2): 集合 Root2 并入 Root1  查找 Find(x): 查找元素 x 属于哪个集合 4

5. 并查集  用树表示集合  初始化时,每个元素自成为一棵树 0 1 2 3 4 5 6 7 8 9 全集合 S 初始化时形成的森林 负数表示没有父结点 -1 表示树中有 1 个结点 -2 表示有 2 个结点, 以此类推 下标 0 1 2 3 4 5 6 7 8 9 父指针 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 初始化时形成的父指针表示 5

6. 并查集  用树表示集合  假设经过若干合并后有 3 个集合 {0,6,7,8} , {1,4,9} {2,3,5} 0 1 2 6 7 8 4 9 3 5 集合的树形表示 下标 0 1 2 3 4 5 6 7 8 9 父指针 -4 -3 -3 2 1 2 0 0 0 1 6 集合的父指针表示

7. 并查集 0  用树表示集合  合并 s1={0,6,7,8}  s2={1,4,9} 6 7 8 1  s2 作为 s1 根的子树,或相反 4 9 0 1  第一种合并方式 6 7 8 4 9 1 合并集合 下标 0 1 2 3 4 5 6 7 8 9 0 4 9 父指针 -7 0 -3 2 0 2 0 0 0 0 6 7 8 第二种合并方式 7 第一种合并的父指针表示

8. 并查集 0  用树表示集合  合并 s1={0,6,7,8}  s2={1,4,9} 6 7 8 1  s2 作为 s1 根的子树,或相反 4 9  哪一种合并方式好? 第一种合并方式  先介绍查找 Find 操作  Find(4) 表示 4 所属集合,返回值 0 号结点 ( 即根结点 )  Find 操作时间相当于结点到根路径长度 1 0 4 9 第一种方式好:查找时间更优 合并方式: 6 7 8 将结点数更少的集合作为结点数更多的集合的根的子树 第二种合并方式 8