數據結構淺析(2)-集合
數據結構淺析(2)-集合
來自專欄 AnotherWorld
1 人贊了文章
本系列文章
(1) 數據結構淺析(1)-什麼是數據結構？
本文目標
試著理解什麼是數據結構中的集合。
什麼是集合
在計算機科學中，集合是一種抽象的數據類型，它可以儲存獨特的元素，並沒有任何特定的順序。它是一個有限集數學概念的計算機實現。與大多數其他集合類型不同，它不是從一個集合中檢索一個特定的元素，而是一個典型的測試一個集合中元素的值。
Unlike most other collection types, rather than retrieving a specific element from a set, one typically tests a value for membership in a set.一些集合的數據結構是為靜態或凍結集設計的，它們在構建後不會改變。靜態集只允許在其元素上進行查詢操作——比如檢查給定的元素是否在集合中，或者以任意順序來枚舉元素。其他的變體，被稱為動態或可變集，則允許從集合中插入和刪除元素。
引用自Set (abstract data type）
就如我在本系列文章中第一篇裏介紹的，集合作為數據結構中四種基本數據結構之一，意思就是集合中所有數據屬於該集合。
通俗點來說，集合就是一些具有某些關聯關係的離散數據的組成。
集合的特徵
有三個特徵：確定性，互異性，無序性。
- 確定性（集合中的元素必須是確定的）
- 互異性（集合中的元素互相之間不能相同；比如，有一個集合A={1,2,3,4}，但是{1,2,3,4,1}就不是集合）
- 無序性（集合中的元素沒有順序之說）；比如，集合{1,2,3}和{3,1,2}會被視作同一個集合。
集合的表示方法
描述法，可以用文字或則數學符號來表示。
A = 前100個非負整數
B = 所有有關集合的書
列舉法，在大括弧中列出其元素
A = {1,2,3,4,5,6,7}
B = {Django, 演算法，數據結構}
集合的基本操作
集合的操作有交集，並集，補集/差集 ，插入/添加和刪除。
交集
將兩個集合中相同的元素組合成新的集合
舉個例子，A={1,2,3,4,5}，B={4,5,6,7,8}
交集就是C = A∩B = {4,5}
並集
將兩個集合中所有元素組合併去掉一次相同元素的新的集合
舉個例子，A={1,2,3,4,5}，B={4,5,6,7,8}
交集就是C = A∪B = {1,2,3,4,5,6,7,8}
補集/差集
將兩個集合中除相同元素外剩下的元素組合成新的集合
這裡有兩個概念：相對補集和絕對補集。
- 相對補集，若A和B 是集合，則A在B 中的相對補集是由屬於B 但不屬於A 的元素組成的集合。舉個例子，{1,2,3}-{2,3,4}={1}.
- 絕對補集，若給定全集U，則集合A在U 中的相對補集稱為A 的絕對補集，記為A^c，即A^c=U-A.
插入/添加
將需要加入的元素插入/添加到集合中。
刪除
將集合中的元素刪除去掉。
在下一篇文章中，將著重講的是線性結構(1) - 數組。
如果你覺得我的文章有用，順手點個贊，關注下我的專欄或則留下你的評論吧！
推薦閱讀：
