首页 > 代码库 > 不相交集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--数组实现