簡介 Intro

在開始講演算法的最入門，需要先講講資料結構。不同的資料結構，延伸出了不同的演算法。 這邊先列舉幾個常見的資料結構：

• Linear data structures 線性資料結構
  • List 列表
  • Array 陣列
  • Queue 佇列
  • Stack 堆疊
• Tree 二元樹
  • Heap 堆積
• Hash Table 雜湊表
• Graph 圖

Linear Structure 線性結構

List 列表

List 是將資料排成一直線，易於添加和刪除，但要存取資料卻很費時。此種資料結構具有順序性，不具有唯一性(資料可重複)。

前一筆資料，會使用指標(Pointer)指向下一筆資料的記憶體位址。當要添加或刪除資料時，只需要將前一筆的指標修改，並將當前資料的指標也做修改。

可是當要存取某一筆資料時，卻需要從開頭一筆一筆找下來，所以其複雜度會到 O(n)。

• Add / Delete：O(1)
• Get：O(n)

List 只是基本的資料結構，它還有其他延伸的結構：

• Circular list 循環列表
• Bidirectional list 雙向列表：前後筆資料會互相指向

Array 陣列

類似 List，但是更方便存取，添加和刪除較費力。資料是依序儲存在連續的記憶體位址，因此能用索引來計算記憶體位址，直接存取每個資料。

a[0]  a[1]  a[2]
Blue Yellow Red

要添加或刪除資料時，需要將後面的資料都做移動，才能將資料添加到該索引或是移除該資料

• Add / Delete：O(n)，修改時的複雜度，最差情況下是從陣列的開頭修改
• Get：O(1)，存取時的複雜度，因為可用索引直接讀取

Stack 堆疊

與 List 和 Array 類似，都是將資料排成一列，但是只有一個方面的開口

可以想像堆疊是一個紙箱，資料是由下往上增加，只能從最新增加的資料(紙箱最上層)開始存取。其原理是「後進先出」Last In First Out(LIFO)

增加資料稱為 push，取出最上一筆資料稱為 pop。

Queue 佇列

Queue 也是將資料排成一列，其概念類似於排隊。只能從後面添加、從前面移除。不能從中間修改。其原理是「先進先出」First In First Out(FIFO)

增加資料稱為 enqueue，取出最新一筆資料稱為 dequeue

Hash Table 雜湊表

雜湊函數：主要是將不定長度訊息的輸入，演算成固定長度雜湊值的輸出，且所計算出來的雜湊值必須符合兩個主要條件：

• 由雜湊值是無法反推出原來的訊息
• 雜湊值必須隨內容改變而改變

Hash Table 是儲存成對資料的結構之一。資料為成對的「鍵 Key」和「值 Value」。用雜湊函數運算出來的雜湊值，根據鍵 (key) 來儲存在資料結構中。而存放這些記錄的陣列就稱為雜湊表。

Tree Structure 樹狀結構

Binary Tree 二元樹

樹狀結構的資料結構之ㄧ，有兩個特性。

1. 所有節點上的值都會大於連結在其左側子節點的值
2. 所有節點上的值都會小於連結在其右側子節點的值

依照這兩個特性，可以知道最小值，會在最左側。最大值會在最右側。

刪除資料

1. 情境ㄧ：刪除沒有子節點的節點，直接刪除即可
2. 情境二：刪除只有一個子節點的節點，將子節點替換上來被刪除的節點即可
3. 情境三：刪除有兩個子節點的節點，將被刪除節點的左側子節點中的最大值替換即可

Heap 堆積

Heap 是樹狀結構之一，用於實踐「優先佇列」(priority queue)。堆積的每個節點最多可以擁有兩個子節點。資料從最上層開始添加、同一層左方開始。其子節點的資料必定要大於父節點。

資料依 1, 3, 6, 4, 8, 7 順序加入

      1
     /  \
   3    6 
  / \   /
4  8 7

現在要添加資料 5，依照順序會加到 6 的右側子節點。但是因為父節點不能比子節點。所以 5 和 6 需要對調

      1
     /  \
   3    5 
  / \   / \
4  8 7  6

Graph Structure 圖形結構