首页 > 代码库 > 不相交集ADT--数组实现
不相交集ADT--数组实现
不相交集是解决等价问题的一种有效的数据结构,之所以称之为有效是因为,这个数据结构简单(几行代码,一个简单数组就可以搞定),快速(每个操作基本上可以在常数平均时间内搞定)。
首先我们要明白什么叫做等价关系,而在这个之前要先有一个关系(relation)的定义
Relation:定义在数据集S上的关系R是指,对于属于数据集S中的每一对元素(a,b),a R b要么是真要么是假。如果a R b为真,就说a related b,即a与b相关。
等价关系也是一种关系(Relation),只不过是要满足一些约束条件
a) a R a,对于所有属于S的a
b) a R b 当且仅当 b R a
c) a R b 并且 b R a 意味着 a R c
动态等价性问题:
定义在非空集合S上的关系R,对于任意属于数据集S中的每一对元素(a,b),确定a R b是否为真,也就是说a与b是否有关系。
而对于a与b是否有关系,我们只需要证明a与b是否在同一个等价类集合中。
数组实现的代码如下:
#include<iostream> using namespace std; #define NumSets 8 typedef int DisjSet [NumSets + 1]; typedef int SetType; typedef int ElementType; void Initiaize (DisjSet S) { for (int i = NumSets; i > 0; --i) S[i] = 0; } SetType Find(ElementType x, DisjSet S) { if(S[x] <= 0) return x; else return Find(S[x],S); } void SetUnion (DisjSet S, SetType Root1, SetType Root2) //按高度求并 { if(S[Root2] < S[Root1]) //Root2高度高一点 S[Root1] = Root2; else { if(S[Root1] == S[Root2]) //一样高 S[Root1]--; S[Root2] = Root1; } } int main () { DisjSet S1; Initiaize (S1); SetUnion (S1, 5,6); SetUnion (S1, 7,8); SetUnion (S1, 5,7); SetUnion (S1, 5,4); for (int i = 1; i <= NumSets; ++i) cout << S1[i] << ‘\t‘; cout << endl; cout << Find(3, S1) << endl; return 0; }
传送门: http://blog.csdn.net/changyuanchn/article/details/16810535 这篇博客写的比较清楚,可以参考,我的这篇博客主要是代码完整。
夜深了,,,
不相交集ADT--数组实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。