首页 > 代码库 > 不相交集ADT--链表实现

不相交集ADT--链表实现

     

       每一个集合用用一个链表来表示。链表的第一个对象作为它所在集合的代表。链表中每个对象都包含一个集合成员,一个指向下一个对象的指针,以及指向代表的指针。每个链表含head和tail指针,head指向链表的代表,tail指向链表中最后的对象。

  

      如下图所示:

 

技术分享

  Union的简单实现:将x所在的链表拼接到y所在链表的表尾。对于原先x所在链表中的每一个对象都要更新其指向代表的指针。

  如下图所示:

技术分享

  根据以上思想,代码如下:

 

#include<iostream>

using namespace std;

#define NumSets 8

typedef struct Node *Position;
typedef struct Node *Head;
typedef Head DisjSet[NumSets + 1];

//对于头节点,head_node指向第一个元素,tail指向最后一个元素,Key为该集合的大小
//对于普通节点,head_node指向第一个元素,tail指向后面的一个元素,相当于Next,Key为关键字
struct Node
{
   Position head_node;
   Position tail;
   int Key;
};

Head Make_One_Node (int x)
{
   Head Head_one = (Head)malloc(sizeof(Node));   //先申请一个头结点
   Head_one->Key = 1;  //个数为1

   Position p = (Position)malloc(sizeof(Node));   //这个节点才是存储数据的节点

   p->Key = x;
   p->head_node = p;    //普通节点的hand_node域指向第一个元素,此时就是它本身
   p->tail = NULL;

   Head_one->head_node = p;   //头节点的hand_node域指向第一个元素
   Head_one->tail = p;    //头节点的tail域指向最后一个元素

  
   return Head_one;
}
void Set_Union (Head head1, Head head2)
{
	Head tempHead;
    if (head1->Key < head2->Key )
    {
        tempHead = head1;
        head1 = head2;
        head2 = tempHead;
    }

	//把短的接在长的后面
	
	//下面两句话的位置不能交换,否则会陷入死循环
    head1->tail->tail = head2->head_node;  //head1最后一个元素的tail域指向head2的第一个元素
	head1->tail = head2->tail ;  //head1的tail域指向head2的最后一个元素,也就是head2->tail

	Position p = head2->head_node ;
	while(p)
	{
	   p->head_node = head1->head_node ;//head2的所有元素都指向head1的第一个元素
	   p = p->tail;
	}
	head1->Key  += head2->Key ;

	//释放head2的所有元素
	head2->Key = 0;
	head2->head_node = NULL;
	head2->tail = NULL;

}

Head Set_Find (DisjSet S,int x)   //返回该节点的头结点
{
	for (int i = 1; i <= NumSets; ++i)
	{
	   Position p = S[i]->head_node ;
	   while(p)
	   {
	       if(x == p->Key )
			   return p->head_node;
		   else
			   p = p->tail;
	   }
	   
	}
}

void printf_list(DisjSet S)
{
	for (int i = 1; i <= NumSets; ++i)
	{
		if(S[i]->Key == 0)
		{
		   cout << "第 "<< i << " 个集合没有元素。" <<endl;
		}
		else
		{
		   cout << "第 "<< i << " 个集合一个共有 " << S[i]->Key  << " 个元素,分别是:";
			Position p = S[i]->head_node ;
			while(p)
			{
			   cout << p->Key << "\t";
			   p = p->tail;
			}
			cout << endl;
		}
	     
	}
   
}

int main ()
{
	DisjSet S;
	for (int i = 1; i <= NumSets; ++i)
	{
	    S[i] = Make_One_Node (i);
	}
	Set_Union (S[1], S[2]);
	Set_Union (S[3], S[4]);
	Set_Union (S[3], S[1]);
	printf_list(S);

	cout << Set_Find (S,5)->Key << endl;

  return 0;
}

  看着比数组实现要复杂一点啊。

 

    夜深了,,,

   

   今天5月20号啊,520啊,还是周末啊,还在写代码,代码才是真爱。

 

不相交集ADT--链表实现