Set: 簡單的資料結構

簡單的資料結構

set是指數學名詞「集合」。在這裡我們只考慮元素為整數的集合。「集合」有幾點特性:

一、空集合。

二、集合中的元素不會重複。

要表達一個集合,可以直觀的用一條一維的int陣列:將集合裡的所有元素,依序放進陣列中。再用一個變數,紀錄元素總數。

這樣就能存入1000個元素。

然而,以這種資料結構,做聯集、交集、差集之類的運算,則會相當麻煩,也會比較慢。

【待補程式碼】【待補link list的紀錄法】

UVa 496

Set: 另一種資料結構

另一種資料結構

另外一種表達集合的方法,是用一條一維的bool陣列:集合裡若有x這個元素,就讓array[x]這個位置為true,反之則為false。其概念類似於數學領域提到的Index Set。

它的壞處就是數值有界限、受陣列大小影響。但是,以這種資料結構,做聯集、交集、差集之類的運算,則會比較快,時間複雜度為O(元素總個數)。

這裡是練習題。

UVa 608 665 10227

Set: Bit Array

Bit Array(Bitmap)

還有一種方法,是用bit來代替bool變數。在電腦當中,一個bit只有0和1兩種值,類似於bool變數,兩者都可以用來表示一個集合元素存不存在。利用bit們來表達集合,可以節省儲存空間,也可以節省運算時間。

一個int變數所使用的記憶體大小為32bit,可以當作是32個數字的集合。需要更多bit的話,就開一條陣列吧!