深入探索不相交集合：链表表示与加权合并策略的实现

1. MAKE-SET 操作
- 伪代码
- C语言实现
2. FIND-SET 操作
- 伪代码
- C语言实现
3. UNION 操作
- 伪代码
- C语言实现
4. 集合对象和表对象的属性
5. 总结

在本文中，我们将探讨如何使用链表表示和加权合并启发式策略来实现不相交集合（Disjoint Set）的操作，包括MAKE-SET、FIND-SET和UNION。不相交集合是一种数据结构，用于处理一些元素的集合，而这些集合之间没有公共元素。这种数据结构在很多算法中都非常有用，比如在图算法中确定连通分量或者在并查集算法中。
我们将首先介绍每种操作的基本概念和伪代码表示，然后提供相应的C语言实现代码，并讨论在集合对象和表对象中所使用的属性。
在这里插入图片描述

1. MAKE-SET 操作

MAKE-SET操作是用来创建一个只包含单个元素x的集合。在链表表示中，这可以通过简单地创建一个新的节点，并将该节点的指针指向自己来完成。

伪代码

MAKE-SET(x)
1. 创建一个新节点 node
2. node 的成员设置为 x
3. node 的 next 指针指向 NULL
4. 集合对象指向 node

C语言实现

#include <stdio.h>
#include <stdlib.h>
typedef struct Node {int element;struct Node *next;
} Node;
typedef struct DisjointSet {Node *head;
} DisjointSet;
void makeSet(int x, DisjointSet *djSet) {Node *node = (Node *)malloc(sizeof(Node));node->element = x;node->next = NULL;djSet->head = node;
}

2. FIND-SET 操作

FIND-SET操作是用来找出给定元素x所在的集合的代表元素。在链表表示中，由于每个集合只有一个元素，所以FIND-SET操作直接返回该元素即可。

伪代码

FIND-SET(x)
1. 返回 x

C语言实现

int findSet(DisjointSet *djSet) {return djSet->head->element;
}

3. UNION 操作

UNION操作是用来合并两个集合的。在链表表示中，我们可以使用加权合并启发式策略，即较小集合的所有元素都链接到较大集合的末尾。

伪代码

UNION(x, y)
1. 计算 x 所在集合的成员数 size_x
2. 计算 y 所在集合的成员数 size_y
3. 如果 size_x < size_ya. 将 x 所在的链表追加到 y 所在的链表b. 更新 y 所在集合的代表为合并后的集合
4. 否则a. 将 y 所在的链表追加到 x 所在的链表b. 更新 x 所在集合的代表为合并后的集合

C语言实现

void unionSets(DisjointSet *djSet1, DisjointSet *djSet2) {Node *node1 = djSet1->head;Node *node2 = djSet2->head;if (node1->next == NULL && node2->next == NULL) {// 特殊情况：两个集合都只包含一个元素node1->next = node2;djSet2->head = node1;} else {// 通用情况：找到两个链表的尾部Node *tail1 = node1;while (tail1->next != NULL) tail1 = tail1->next;Node *tail2 = node2;while (tail2->next != NULL) tail2 = tail2->next;// 根据加权合并启发式策略，将较小集合链接到较大集合if (tail1->next == NULL) {tail1->next = node2;djSet2->head = node1;} else if (tail2->next == NULL) {tail2->next = node1;djSet1->head = node2;} else {// 比较链表长度并合并if (tail1->element < tail2->element) {tail1->next = tail2->next;tail2->next = node1;djSet1->head = djSet2->head;} else {tail2->next = tail1->next;tail1->next = node2;djSet2->head = djSet1->head;}}}
}