何謂資料結構
當數據儲存在記憶體中時,決定數據的順序和位置的,就是『資料結構 』(Data Structure)。而資料結構的邏輯與手機裡的電話簿相同。
列表
數據的結構是排成一直線,資料排序沒有按照『線性』的順序。
優點:便於數據追加或刪除。
缺點:數據的存取很費時。
每個數據和一個『指標』配對,指向下一個數據在記憶體中的位址。
常見的列表結構:
・單向連結串列 Singly Linked List
・雙向鏈結串列 Doubly Linked List /雙向串列 Bidirectional List
・環狀串列/循環串列 Circular List
使用列表的執行時間假設儲存在列表中的數據有n個,存取數據時必須從列表的前端開始(也就是線性搜尋),如果想存取的數據在很後面,需要花費 O(n)的執行時間。另一方面,追加數據時只需改變兩個指標的指向,所以是與n無關的常數時間 O(1);當然,前提為已經確定要追加數據的存取位置。同理,刪除數據只需耗費常數時間 O(1)。
陣列
數據的結構是排成一列,由相同類型的元素(Element)集合所組成。
優點:便於數據的存取。
缺點:數據的追加或刪除很費時。
數據分配在一塊連續的記憶體來儲存,所以可以利用元素的索引(Index)計算出該元素對應的儲存位址,直接存取每個數據,這種存取方式稱為『隨機存取』。
使用陣列的執行時間假設有n個數據儲存在陣列中,因為能隨機存取(可用索引算出記憶體位址),所以可以用常數 O(1)的執行時間來存取。另一方面,追加數據時,得將指定位置後的數據分別往後移。如果在陣列最前端追加數據,就需要 O(n)的時間,刪除也同理。
堆疊
數據的結構是排成一列,像一個U型容器。
優點:隨時能存取最新數據。
缺點:只能單邊操作,進出口只有一個。
原理為後進先出(Last In First Out)。
堆疊使用兩種基本操作:推入(Push)、彈出(Pop)
・推入:追加數據到堆疊中。
・彈出:從堆疊中取出數據。
使用堆疊的執行時間因為只有單邊操作,所以在追加或刪除數據時,所需要的時間就是常理時間 O(1)。而也因為只有單邊操作,假設有n個數據儲存在堆疊中,如果搜尋的數據在很後面,就需要 O(n)的時間。
佇列
數據的結構是排成一列,別名『隊列』,像一個II型容器。
優點:資料處理是在不同邊進行。
缺點:移動數據區域有限,無法存取夾在中間的數據。
原理為先進先出(First In First Out)。
佇列使用兩種基本操作:進入佇列(Enqueue)、輸出佇列(Dequeue)
・進入佇列:只允許在後端進行插入操作。
・輸出佇列:只允許在前端進行輸出資料。
使用佇列的執行時間兩邊操作方式不同,後端做輸入,前端做輸出,所以存取的時間是常理時間 O(1)。也因為只有一邊能輸出,假設已經有n個數據儲存在佇列中,而搜尋的數據才剛從後端輸入,則就需要 O(n)的時間。
雜湊表
以雜湊函數運算出來的雜湊值,根據鍵(Key)來儲存在數據結構中,儲存的資料為成對的鍵(Key)和值(Value)。
優點:利用雜湊函數,可以快速讀取陣列中的數據及方便儲存數據。
缺點:陣列規模太小,容易導致『碰撞』次數增加;陣列規模太大,容易產生未儲存的數據空箱,造成記憶體空間浪費。
其他:
・碰撞(Collision):當不同的數據經由雜湊函數及 mod 計算後,數據儲存位置重複。
・鏈結法(Chaining):發生碰撞時,利用列表將數據存在已存入的數據後面。
・開放定址法(Open Addresssing):發生碰撞時,求出第二候補位址並儲存,如果該位置已滿則會繼續找下一個候補位址,直至找到空的位址。
使用雜湊表的執行時間將一個 鍵/值 輸入或輸出到一個雜湊列表中時,這個鍵將通過雜湊函式對應到一個數字,用作 儲存/刪除 的鍵。未發生碰撞時,存取的時間是常理時間 O(1)。而如果發生碰撞時,存取的時間則是 O(n)。當你嘗試再次訪問相同的金鑰時,雜湊函式將處理該金鑰並返回相同的數字結果,用於查詢關聯的值。未發生碰撞時,搜尋的時間是常理時間 O(1)。而如果發生碰撞時,搜尋的時間則是 O(n)。
堆積
圖形的樹狀結構。用於實踐『優先佇列』(Priority Queue)。
優先佇列:可以自由追加數據,讀取數據時,依序從最小值開始選取。
堆積規則條件:
・樹狀結構中,各個頂點稱為『節點』(Node),數據儲存在各個節點。
・每個節點最多可以擁有兩個『子節點』(Child Node)。
・節點從上方開始加入,位處同一階層時,則從左方開始加入。
・儲存規則中,子節點的數必須比『父節點』(Father Node)大。因此最小的數被存入樹狀結構的最上方【『根』(Root)】。
・追加數據時,會從最下層的最左方節點開始,並往右方節點方向依序加入。若最下方一層被填滿時,則往下產生新的一層,並再從最左方開始追加數據。
・取出數據後,必須將最尾端的數據提到最上面,再進行整理。
使用堆積的執行時間因為最上方永遠是最小的數據,所以無論數據有多少,取出最小值的執行時間是 O(1)。取出數據後,重整堆積的結構時,必須將最尾端的數據放到最上面的節點,與子節點比較後再往下排序。因此執行時間與樹狀結構的高成等比。假設數據個數為n,根據樹狀結構的條件得知,高是 ㏒₂n,重整的時間是 O(㏒n)。追加數據同理,在最尾端追加數據後,數據須反覆與父節點比較後往上移動,直到滿足堆積的條件,所以需要與樹狀結構的高成等比的時間 O(㏒n)。
二元搜尋樹
圖形的樹狀結構。
具有兩項特性:
・所有父節點上的數都會大於連結在其左邊子節點上的數。
・所有父節點上的數都會小於連結在其右邊子節點上的數。
依據上述兩項特性得知,最小值的數落在最左邊的最尾端,反之,最大值的數落在最右邊的最尾端。
增加節點時依據特性加入二元搜尋樹中;刪除節點時,從該刪除的節點中,可以去選擇移動左邊樹狀結構中的最大節點或是移動右邊樹狀結構中的最小節點。
使用二元搜尋樹的執行時間比較的次數等同於樹狀結構的高度,也就是說,當有n個節點,樹狀結構的形狀達到平衡時,最多只要進行 ㏒₂n次的比較和移動,因此時間為 O(㏒n)。但是,當樹狀結構靠攏成縱向一直線的形狀,結構將變得很高,執行時間則為 O(n)。
補充
『平衡樹』(Self-balancing Binary Search Tree):在樹狀結構不平衡時,加以修正形狀,隨時維持結構均衡的資料結構,使其能夠保持搜尋的效率。
『B樹』(B-tree):將子節點擴張到m個(m為事先設定的定數),藉由控制子節點的數量來確保樹狀結構平衡。