集合及運算

  • 2019 年 10 月 3 日
  • 筆記

目錄

更新、更全的《數據結構與演算法》的更新網站，更有python、go、人工智慧教學等著你：https://www.cnblogs.com/nickchen121/p/11407287.html

一、集合的表示

集合運算：交、並、補、差，判定一個元素是否屬於某一集合

在上述集合運算中，我們只關心兩個集合運算，為並查集：集合並和查某元素屬於什麼集合。因此有一個問題——並查集問題中集合存儲如何實現？

對於上述問題，我們可以用樹結構表示集合，樹的每個結點代表一個集合元素

例如：有以下三個整數集合

  1. S1 = {1, 2, 4, 7}
  2. S2 = {3, 5, 8}
  3. S3 = {6, 9, 10}

對於上述三個集合，我們可以使用雙親表示法（孩子指向雙親）來構造下圖所示樹結構：

對於上述的樹結構，我們可以考慮使用數組存儲，存儲形式如下圖所示：

負數表示根結點；非負數表示雙親結點的下標。

對於數組中的每個元素，我們可以使用如下所示的程式碼描述：

/* c語言實現 */    typedef struct{    ElementType Data;    int Parent;  } SetType;
# python語言實現    class TreeNode:       def __init__(self, x):           self.data = None           self.parent = None

二、集合運算

2.1 集合的查運算

查找某個元素所在的集合（用根結點表示）

/* c語言實現 */    int Find(SetType S[], ElementType X)  {    // 在數組S中查找值為X的元素所屬的集合    // MaxSize是全局變數，為數組S的最大長度    int i;    for (i = 0; i < MaxSize && S[i].Data != X; i++);    if (i >= MaxSize) return -1; // 未找到X，返回-1    for (; S[i].Parent >= 0; i = S[i].Parent);    return i; // 找到X所屬集合，返回樹根結點在數組S中的下標  }

2.2 集合的並運算

分別找到X1和X2兩個元素所在集合樹的根結點

如果它們不同根，則將其中一個根結點的父結點指針設置成另個一個根結點的數組下標

/* c語言實現 */    void Union(SetType S[], ElementType X1, ElementType X2)  {    int Root1, Root2;    Root1 = Find(S, X1);    Root2 = Find(S, X2);    if (Root1 != Root2) S[Root2].Parent = Root1; // 當X1和X2不屬於同一個子集時，才需要合併  }

下圖所示為集合 {1, 2, 4, 7} 和 集合 {3, 5, 8}的並運算：

對於上述的兩個小集合，隨意選擇一個根結點並無太大影響，但是對於如下圖所示的兩個集合，隨意選擇根結點則會增加未來並集的查找效率：

對於上圖所示的兩個集合，如果要增加未來兩個集合併集的查找效率，應該盡量採用小的集合合併到相對大的集合中，但是我們如何判斷哪一個集合元素更多呢？

為了更高效的判斷那個集合元素更多，我們可以把根結點的-1改成-7或-3，用根結點的絕對值表示集合元素的個數，即數組更改為如下圖所示：

其中-7表示根結點數據為1的集合有7個元素；其中-3表示根結點數據為6的集合有3個元素。

Tags:

VirMach 便宜 VPS