歡迎來到數據結構的世界！
在本章中，我們將探討電腦如何組織數據。你可以這樣想像：如果你的房間很凌亂，就很難找到你最喜歡的那雙襪子。但如果你有抽屜櫃、鞋架和洗衣籃，找東西就會變得輕而易舉！數據結構（Data structures）就像我們在電腦記憶體中用來儲存數據的「家具」，讓我們能更有效地運用這些資訊。
別擔心，如果有些術語乍聽之下讓你感到陌生，不必緊張。看完這份筆記後，你會發現它們大多數都是基於簡單的生活常識。
1. 靜態與動態數據結構
在探討具體的結構之前，我們需要先了解它們是如何增長的（或者是否會增長！）。
靜態數據結構（Static Data Structures）：這類結構的大小是固定的。你在程式執行前就決定好所需的空間，且在程式執行期間無法改變。比喻：一個木製雞蛋盒。無論你裡面裝了 1 顆還是 12 顆雞蛋，它永遠有 12 個格子。
動態數據結構（Dynamic Data Structures）：這類結構的大小可以隨時增加或減少。如果你不知道會有多少數據，用它們就對了！比喻：派對的賓客名單。隨著越來越多人回覆，你可以不斷新增名字。
快速複習：靜態結構大小固定，記憶體使用效率高，但若空間用盡會有風險；動態結構靈活，但管理記憶體需要消耗較多的處理能力。
2. 基礎：陣列、記錄與元組
陣列（Arrays）
陣列是儲存在一起的相同類型數據項的集合。每個項目都有一個索引（Index）（一個從 0 開始的數字），讓我們可以輕鬆找到它。
- 一維陣列：一個簡單的列表。例如：[ "Apple", "Banana", "Cherry" ]
- 二維陣列：就像網格或試算表。你需要兩個座標來定位一個項目：[列, 行]。
- 三維陣列：就像一棟大樓或一個魔術方塊。你需要三個座標：[層, 列, 行]。
常見錯誤：忘記了大多數程式語言的索引是從 0 而不是從 1 開始計數！
記錄（Records）與元組（Tuples）
元組：一組有序的數值，可以包含不同的數據類型（例如一個整數和一個字串）。元組一旦創建，通常就無法更改（它們是不可變的）。例如：(12, "High Street", "London")。
記錄：這與元組相似，但使用了具名欄位（named fields）。例如：「學生」記錄可能包含 ID、名（FirstName）和姓（Surname）等欄位。 它就像資料庫表格中的單行數據。
重點總結：陣列適合儲存相同類型的列表；記錄與元組則用於將關於某個事物的各種不同詳情組合在一起。
3. 堆疊與佇列（抽象數據類型 ADT）
這些被稱為抽象數據類型（Abstract Data Types, ADT）。這意味著我們更關心的是它們的運作方式，而非其底層如何實作。
堆疊（Stack，後進先出 LIFO）
堆疊是一種 LIFO 結構：後進先出（Last-In, First-Out）。
比喻：一疊晚餐碟子。最後放上去的那一個，一定會是第一個被拿走的。
操作：
- Push：將項目推入堆疊頂端。
- Pop：將頂端的項目移除。
- Peek：查看頂端項目而不將其移除。
- IsEmpty：檢查堆疊是否為空。
佇列（Queue，先進先出 FIFO）
佇列是一種 FIFO 結構：先進先出（First-In, First-Out）。
比喻：排隊搭巴士的人龍。先來排隊的人，就能先上車。
操作：
- Enqueue：在隊伍末端加入項目。
- Dequeue：從隊伍前端移除項目。
你知道嗎？電腦會使用堆疊來記住函數呼叫時的位置（即「呼叫堆疊 Call Stack」），並使用佇列來管理列印工作！
4. 連結串列（Linked Lists）
連結串列是一種動態結構，其中每個項目（稱為節點 Node）都「指向」下一個項目。想像一個尋寶遊戲，每個線索都會告訴你下一個線索在哪裡。
節點包含兩個部分：
- 數據（Data）：實際的值（例如："Hello"）。
- 指標（Pointer）：下一個節點的記憶體位址。
最後一個節點指向 Null，這告訴電腦：「到這裡就結束了！」
如何新增/移除：你不需要移動數據，只需要改變指標指向的位置即可。這就像切斷一條鍊子，然後以不同的順序將鍊環重新接起來。
5. 樹與二元搜尋樹（BST）
樹（Tree）是一種層次結構。它以頂端的根（Root）節點開始，向下「分枝」到子節點（Child）。沒有子節點的節點稱為葉（Leaves）。
二元搜尋樹（Binary Search Trees, BST）
BST 是一種特殊的樹，每個節點最多有兩個子節點。它遵循一個嚴格的規則：
- 小於父節點的值會放到左邊。
- 大於父節點的值會放到右邊。
樹的遍歷（Traversing）：存取每個節點有兩種主要方式：
- 廣度優先搜尋（Breadth-First）：在移動到下一層之前，你會先存取同一層的所有節點。（想像一下逐行掃描書籍的過程）。
- 深度優先搜尋（後序遍歷，Post-Order）：在「存取」節點之前，你會先盡可能深入一個分枝。在後序遍歷中，你會在父節點之前先存取子節點。
重點總結：BST 讓搜尋數據變得極快！每次你向左或向右移動，都會排除掉剩下一半的數據。
6. 圖（Graphs）
圖（Graph）是由線（稱為邊 Edges）連接的節點（稱為頂點 Vertices）集合。
比喻：倫敦地鐵圖。每個車站是一個頂點，而軌道就是邊。
圖的類型：
- 有向圖（Directed）：邊有箭頭（單行道）。
- 無向圖（Undirected）：邊沒有方向（雙向道）。
- 加權圖（Weighted）：邊有「成本」或「權重」（例如兩城市之間的里程距離）。
常見錯誤：學生經常混淆樹與圖。記住：樹只是一種特殊的圖，它沒有「環（cycles）」，且所有節點都連接到同一個根節點。
7. 雜湊表（Hash Tables）
雜湊表是為了實現「即時搜尋」而設計的。與其搜尋整個列表，我們使用雜湊演算法（Hashing Algorithm）來精確計算數據應該儲存在哪裡。
運作方式：
- 取出一筆數據（即鍵 Key）。
- 將其輸入雜湊函數（Hash Function）（一個數學公式）。
- 計算結果即為數據儲存的索引（Index，即「位址」）。
複雜度：理想情況下，在雜湊表中查找數據的時間複雜度為 \(O(1)\)，幾乎是瞬間完成！
碰撞（Collisions）：有時兩個不同的鍵會計算出相同的索引，這就是碰撞。電腦通常透過「溢位區」或「鏈結法（chaining，在該索引處建立一個小型連結串列）」來處理這種情況。
總結檢查清單
要在考試中取得好成績，請確保你能做到：
- 解釋靜態與動態結構之間的區別。
- 繪製堆疊（Push/Pop）和佇列（Enqueue/Dequeue）的圖示。
- 描述連結串列如何利用指標保持連接。
- 應用左 < 父 < 右的規則來構建一個二元搜尋樹。
- 識別圖中的有向與無向邊。
- 解釋為什麼雜湊表的搜尋速度如此之快。
如果這些內容看起來很多，不用擔心。試著在紙上畫出這些結構——當你能看見你正在構建的這些「家具」時，理解起來會容易得多！