集合 (電腦科學)

在電腦科學中,集合是一組可變數量的數據項(也可能是0個)的組合,這些數據項可能共用某些特徵,需要以某種操作方式一起進行操作。一般來講,這些數據項的類型是相同的,或基礎類別相同(若使用的語言支援繼承)。列表(或陣列)通常不被認為是集合,因為其大小固定,但事實上它常常在實現中作為某些形式的集合使用。

集合的種類包括列表多重集列舉類型可以是列表或集。

列表

列表中,數據項的順序是確定的,也可以存在多個相同的數據項。列表支援的操作包括尋找專案並找到其位置(若存在),將專案從列表中刪除,在特定位置插入專案等。通常的佇列,或稱FIFO即是一個列表,該列表只能在一端添加專案,而在另一端刪除專案。而,或LIFO則只能在同一端添加或刪除專案。不管是佇列還是棧,集合中專案的順序都應當是一定的,因此這兩種情況只是列表的特例。其它列表支援的操作包括排序,再一次說明了其中順序的重要性。

列表的具體形式包括陣列鏈結串列等。

與列表不同,在中,數據項是無序的,也不允許存在相同數據項。集支援添加、刪除和尋找專案。一些語言內建對集的支援,而在其它語言中,可以利用雜湊表實現集。

多重集

多重集的行為類似於集,其中數據項是無序的。但在多重集中,可以存在相同的數據項。多重集支援的操作包括添加、刪除項,查詢相同項在多重集中出現的次數。多重集可以通過排序轉換成列表。

關聯陣列

關聯陣列(或稱尋找表字典等)的行為和字典相似,為(例如字典中的單詞)輸入提供一個(如字典中的定義)輸出。可以是對複雜數據結構的參照。通常使用雜湊表實現高效率的關聯陣列。

 
二叉樹是樹的一種類型

中,「根」節點與一定數量的數據項以親-子關係聯絡起來,而其子數據項也與另外的數據項以同樣的方式聯絡。除了根節點的每個項都有且只有一個父節點,並可能有一些子節點。樹支援的操作包括遍歷,插入等。用於排序操作的樹通常稱為。通常使用樹來儲存存在包含親-子關係的數據,例如選單,目錄及其中檔案等。

 
一張6節點圖

中,每個數據項都可以與一個或多個其它數據項聯絡起來,其中每個節點都是平等的,類似於無根節點、無親-子關係的樹。圖支援的操作包括遍歷,尋找等。圖常常用於對實際問題進行建模,並解決這些問題。在生成樹協定中,建立一張代表網絡結構的圖(或稱網格),從而了解應當斷開哪些鏈路以避免數據迴圈。

抽象概念及其實現

如上所述,集合,以及集合的各種分類都只是抽象概念。由於名字相同或相似,集合及其在各種語言中的實現常常會造成文字上的混淆。集合,列表,集,樹等名字究竟是數據結構,抽象資料類型抑或類只能通過具體分析來確定。其中,集合則是計算問題的解決方案中抽象程度最高的概念。從這個方面來看,若過於關注其實現,則可能會對理解集合的數學概念產生反作用。

參見

外部連結