首页 > 代码库 > 不相交集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--链表实现
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。