資料結構/集合

資料結構
介紹 - 漸進符號 - 陣列 - 列表結構 & 迭代器
棧 & 佇列 - 樹 - 最小堆 & 最大堆 - 圖
雜湊表 - 集合 - 權衡

集合在軟體應用程式中是一個有用的工具，就像在數學中一樣，類似的抽象物件被聚合到集合中。一個數學集合有一個相當簡單的介面，可以用許多不同的方式實現。

Set<item-type> ADT

contains(test-item:item-type):Boolean

如果 test-item 包含在集合中，則返回 True。

insert(new-item:item-type)

將 new-item 新增到集合中。

remove(item:item-type)

從集合中刪除 item。如果 item 不在集合中，則此方法不做任何操作。

remove(item-iter:List Iterator<item-type>)

從集合中刪除 item-iter 所指向的專案。

get-begin():List Iterator<item-type>

允許迭代集合中的元素。

get-end():List Iterator<item-type>

也允許迭代集合中的元素。

union(other:Set<item-type>):Set<item-type>

返回一個包含此集合或 other 集合中所有元素的集合。具有預設實現。

intersect(other:Set<item-type>):Set<item-type>

返回一個包含此集合和 other 集合中所有元素的集合。具有預設實現。

subtract(other:Set<item-type>):Set<item-type>

返回一個包含此集合中所有元素但 other 集合中沒有的元素的集合。具有預設實現。

is-empty():Boolean

如果不再有專案可以彈出，並且沒有頂端專案，則返回 True。

get-size():Integer

返回集合中的元素數量。

所有操作都可以在 $O(N)$ 時間內完成。

列表實現

實現集合的方法有很多。最簡單但通常效率最低的方法是建立一個線性列表（陣列、連結串列或類似結構），其中包含集合中的每個元素。對於最基本的操作，測試成員資格，可能的實現可能如下所示

function contains(List<T> list, T member)
    for item in list
        if item == member
            return True
    return False

要向此集合新增新成員，只需將元素新增到列表的開頭或結尾。（如果進行檢查以確保沒有重複元素，則某些其他操作可能更簡單。）其他操作也可以類似地根據簡單的列表操作來實現。不幸的是，成員資格測試的 worst-case 執行時間為 $O(n)$，如果該專案不在列表中，甚至平均情況下也需要相同的時間，假設該專案在列表中的任何位置的可能性都相同。如果集合很小，或者如果頻繁訪問的專案可以放置在列表的前端，這可能是一個有效的解決方案，但其他選項可能具有更快的執行時間。

假設元素可以排序，並且插入和刪除很少，則保證按排序順序且沒有重複元素的列表可以更高效。使用排序列表，成員資格測試的效率可以達到 $O(logn)$ 的級別。此外，並集、交集和差集可以線上性時間內實現，而對於無序列表，則需要二次時間。

位陣列實現

對於某些資料，維護一個描述集合內容的位陣列可能更實用。在此表示中，每個問題域元素都對應一個 1 或 0，指定該物件是否為集合的元素。對於一個簡單的案例，假設只有從 0 到 n 的整數可以是集合的成員，其中 n 預先已知。這可以用長度為 n+1 的位陣列來表示。contains 操作很簡單

function contains(BitArray array, Int member)
    if member >= length(array)
       return False
    else if array[member] == 1
       return True
    else
       return False

要向這種型別的集合中新增或刪除元素，只需修改位陣列以反映該索引應該是 1 還是 0。成員資格在正好 $O(1)$（常數）時間內執行，但它的域受到嚴重限制。可以移動域，從 m 到 n 步長為 k，而不是如上所述從 0 到 n 步長為 1，但這裡沒有太多靈活性。然而，對於正確的域，這通常是最有效的解決方案。

位陣列是儲存布林變數集合的有效結構。一個例子是啟用應用程式各種執行時行為的命令列選項集。C 和類似語言提供位運算子，允許程式設計師在單個機器指令中訪問位欄位，而陣列訪問通常需要兩個或三個指令，包括記憶體讀取操作。一個功能齊全的位集實現包括用於計算集合並集、集合交集、集合差集和元素值的運算子。

關聯陣列實現

關聯陣列——即雜湊表和二叉搜尋樹，代表了一種重量級但通用的集合表示。二叉樹通常具有 $O(logn)$ 時間實現，用於查詢和修改特定鍵，雜湊表具有 $O(1)$ 實現（儘管有一個更高的常數因子）。此外，它們能夠儲存幾乎任何型別的鍵。成員資格測試很簡單：只需測試潛在的集合成員是否作為關聯陣列中的鍵存在。要新增元素，只需將集合成員作為關聯陣列中的鍵新增，並使用一個虛擬值。在最佳化的實現中，可以使用專門的雜湊表或二叉樹，而不是重用現有的關聯陣列實現，這些雜湊表或二叉樹不儲存與鍵相對應的值。在這裡，值沒有意義，它們佔用了一部分額外的記憶體空間。

資料結構
介紹 - 漸進符號 - 陣列 - 列表結構 & 迭代器
棧 & 佇列 - 樹 - 最小堆 & 最大堆 - 圖
雜湊表 - 集合 - 權衡