Data structures and abstract data types

歡迎來到資料結構的世界！

在本章中，我們將探討電腦是如何組織資訊的。試想一下，如果你要在凌亂的衣櫃裡找一雙特定的襪子，這簡直是永無止境的折磨！但如果你把襪子放進抽屜，把襯衫掛好，把鞋子擺在鞋架上，找東西就變得輕而易舉了。資料結構 (Data structures) 正是電腦世界裡的「抽屜」與「架子」。它們能幫助我們有效地儲存與管理資料，讓程式運行得既快速又有條理。如果初次接觸覺得有點抽象也別擔心，我們會運用大量生活中的例子，讓一切變得一目瞭然！

1. 什麼是資料結構？

資料結構是一種用於組織、處理、檢索與儲存資料的特殊格式。你可以把它想像成將相關的資料項目歸類在一起，以便更有效地使用它們。

現實類比： 圖書館就是一個巨大的資料結構。書本絕不會被隨意扔在地上，而是按照類別、作者或杜威十進位圖書分類法進行整理。這種「結構」讓我們能在幾分鐘內，從成千上萬本書中找到想要的那一本。

重點回顧：為什麼我們需要它？

• 處理大量數據。
• 加快搜尋資訊的速度。
• 運用經過驗證的方法，解決複雜的問題。

2. 陣列：結構的基石

陣列 (Array) 是最基本且最常見的資料結構之一。它是一組相同資料類型的元素，按順序儲存而成。

一維陣列 (Single-Dimensional Arrays)

你可以把它想像成一個簡單的清單。在一維陣列中，你可以用來表示數學上的向量 (vector)。清單中的每一項都有一個索引（通常從 0 或 1 開始），讓你能輕鬆找到它。

多維陣列 (Multi-Dimensional Arrays)

二維陣列就像一個網格或表格（包含行與列），在數學上常用來表示矩陣 (matrix)。廣義來說，n 維陣列就是一組由 \(n\) 個整數組成的「元組 (tuple)」來進行索引的元素集合。

現實類比：
- 一維陣列： 學校走廊上的一排儲物櫃。
- 二維陣列： 電影院的座位表（F 行，12 號座）。

3. 欄位、記錄與檔案

有時候，我們需要將不同類型的資料組合在一起。例如，如果你正在建立一個學生資料庫，你可能需要姓名（字串）、年齡（整數）和成績（浮點數）。

• 欄位 (Field)： 單一資訊（例如：「學生姓名」）。
• 記錄 (Record)： 相關欄位的集合（例如：某位特定學生的所有資料）。
• 檔案 (File)： 儲存在電腦中的記錄集合。

重要提示： 你需要學會如何讀取與寫入文字檔 (text files)（人類可讀）以及二進位檔 (binary files)（電腦可讀代碼）。

4. 抽象資料類型 (ADTs)

這聽起來很深奧，但其實是個非常有用的概念！抽象資料類型 (Abstract Data Type, ADT) 是一種從使用者角度定義其行為的資料結構。它告訴我們資料「做什麼」，而不是在底層「如何編碼」。

「汽車」類比： 當你開車時，你只需要操作方向盤和踏板（介面）。你不需要確切了解引擎如何燃燒燃料或齒輪如何轉動（實作），就能讓車子移動。ADT 的運作原理正是如此！

你需要掌握的關鍵 ADT：

• 佇列 (Queue)： 就像店裡的排隊。最先進入的人最先獲得服務（FIFO - 先進先出）。
• 堆疊 (Stack)： 就像堆疊餐盤。最後放上去的盤子，是第一個拿走的（LIFO - 後進先出）。
• 圖 (Graph)： 由「節點」與連接它們的「邊」組成的集合（就像倫敦地鐵圖）。
• 樹 (Tree)： 資料的階層結構（就像家譜或你電腦裡的資料夾）。
• 雜湊表 (Hash Table)： 一種儲存資料的方式，讓你透過「鍵 (key)」幾乎能瞬間找到資料。
• 字典 (Dictionary)： 鍵值對的集合（就像真正的字典：單字 -> 定義）。
• 向量 (Vector)： 一種表示同時具有大小與方向的數學量的方式。

核心觀念： ADT 讓程式設計師能專注於程式的邏輯，而不必陷入記憶體管理的「繁瑣細節」中。

5. 靜態與動態資料結構

這是考試中的熱門題目！資料結構可分為靜態或動態。

靜態資料結構 (Static Data Structures)

這類結構在程式啟動時就有固定大小。
- 優點： 記憶體一次性分配，速度快且效率高。
- 缺點： 如果沒用滿會浪費記憶體；如果數據太多則會空間不足。

動態資料結構 (Dynamic Data Structures)

這些結構在程式運行時可以擴展或縮減。
- 優點： 僅使用實際需要的記憶體空間。
- 缺點： 編寫程式較複雜，且因為電腦需要不斷搜尋新的記憶體空間，速度可能稍慢。

快速回顧框：
靜態 (Static) = 固定大小（像木盒）。
動態 (Dynamic) = 靈活大小（像氣球）。

6. 建立與維護資料

課程大綱要求你理解如何建立並維護特定的結構。我們會在後續章節深入探討，但這裡先提供一個「速查表」：

佇列 (Queue)（線性、循環、優先級）

• 新增 (Add)： 將項目放到末端 (Enqueue)。
• 移除 (Remove)： 從前端取出項目 (Dequeue)。
• 滿/空檢查： 新增前務必檢查空間是否足夠，移除前檢查是否有資料！

堆疊 (Stack)

• 推入 (Push)： 將項目加到頂端。
• 彈出 (Pop)： 從頂端移除項目。
• 檢視 (Peek)： 查看頂端項目而不移除它。

雜湊表 (Hash Table)

• 使用雜湊演算法 (hashing algorithm) 將「鍵」轉為記憶體位址。
• 碰撞 (Collision)： 如果兩個不同的鍵想要同一個位址怎麼辦？你需要處理方法（例如「再雜湊」）。

堆疊與佇列的記憶法：
- Stack = Stop（最後進去的是在頂部/停止的地方）。LIFO。
- Queue = Quick（最先進去的人很快就出去了）。FIFO。

最終重點整理

1. 資料結構只是儲存資料的組織方式。
2. 陣列是最基本的結構，且可以是多維的。
3. 抽象資料類型 (ADT) 專注於邏輯行為，而非物理代碼。
4. 靜態結構大小固定；動態結構則靈活可變。
5. 不同的結構（如堆疊與佇列）用於不同的特定任務。

如果覺得要背的東西很多，不用擔心！當你開始在自己的程式中使用它們時，這些概念就會變得像直覺一樣自然。繼續練習吧！