Data Types and Structures

資料類型與結構 (AS Level 9618：第 10 章)

各位未來的電腦科學家，大家好！這一章非常重要，因為它教會你如何組織和管理程式所使用的資料。你可以把資料類型和結構想像成程式中用來儲存資訊的各種容器或檔案櫃。選擇正確的容器能讓你的程式執行更有效率，也更易於管理。

如果某些術語聽起來有點抽象，不用擔心！我們會透過簡單的現實生活例子來為你拆解！

---

10.1 資料類型與記錄 (Data Types and Records)

基礎構件：內建資料類型 (Built-in Data Types)

電腦處理的每一項資訊都必須經過分類。資料類型 (Data Type) 定義了資料的種類（例如數字或文字），以及可以對該資料執行的操作。

對於 AS Level 的課程大綱，你必須熟悉以下基本類型（使用標準虛擬代碼名稱）：

- INTEGER (整數)

用於整數（正數、負數或零）。例子：計算學生人數 (1, 2, 3...)。

- REAL (實數/浮點數)

用於包含小數部分的數字。例子：測量溫度 (25.5°C) 或價格 ($19.99)。\n

\n\n- CHAR (字元)
\n

\n用於單一字元。例子：'A', '7', '$'。

- STRING (字串)

用於一連串的字元。例子："Hello World", "9618 syllabus"。

- BOOLEAN (布林值)

用於邏輯值：True (真) 或 False (假)。這對於決策（選擇和迭代）至關重要。例子：IsRaining = TRUE。

- DATE (日期)

專門用於儲存日期，通常也包含時間。例子：2024-08-15。

結構化資料：記錄 (The Record)

如果你需要儲存不同資料類型的相關項目怎麼辦？單一變數無法做到這一點，這時就需要用到記錄結構 (Record Structure)。

記錄的定義：

記錄是一組相關資料項目（欄位/屬性）的集合，這些項目可以屬於不同的資料類型，並全部儲存在同一個識別碼（名稱）之下。

類比：想像一張學生證。這張卡片本身就是一個「記錄」。裡面包含名字 (STRING)、年齡 (INTEGER)，以及費用是否已繳納 (BOOLEAN) 等資訊。

記錄的用途： 1. 組織性： 它能將相關資料整合在一起，使程式碼更簡潔。
2. 效率： 你可以將整個記錄變數傳遞給程序，而不必分別傳遞多個獨立的變數。

在虛擬代碼中定義記錄：
我們使用 TYPE... END TYPE 結構來定義結構，然後宣告該類型的變數。

TYPE T_Student
    StudentID : INTEGER
    StudentName : STRING
    FeePaid : BOOLEAN
END TYPE

DECLARE NewStudent : T_Student

之後你可以使用點運算子 (dot notation) 來存取這些欄位，例如：NewStudent.StudentName。

10.1 重點總結： 資料類型定義了單一資料項目的性質。記錄則將多個相關且可能類型不同的資料整合在同一個名稱下，以實現更好的組織。

---

10.2 陣列 (Arrays)

陣列可以說是程式設計中最常用的資料結構。

什麼是陣列？

陣列是一種資料結構，用於儲存一組相同資料類型的資料項目，並透過索引 (Index)（或稱下標）進行存取。

對比：請記住，記錄 (Record) 可以儲存不同類型的資料；而陣列則只能儲存同一種類型的資料。

與陣列相關的技術術語：

- 索引 (Index 或 Subscript)： 用於存取陣列中特定元素的數值位置。根據程式語言或虛擬代碼的不同，索引通常從 0 或 1 開始。
- 上界 (Upper Bound)： 陣列中有效的最高索引編號。
- 下界 (Lower Bound)： 陣列中有效的最低索引編號。

一維 (1D) 與二維 (2D) 陣列

1. 一維陣列 (1D Array)

一維陣列就是一個列表或向量。它只需要一個索引就能定位一個元素。
類比：一排編號 1 到 10 的信箱。

虛擬代碼宣告範例：
DECLARE Weekdays : ARRAY[1:7] OF STRING

這個陣列儲存了 7 個字串（一週七天）。要存取第三天：Weekdays[3]。

2. 二維陣列 (2D Array)

二維陣列的結構像表格或矩陣（行與列）。它需要兩個索引（列, 行）才能定位一個元素。
類比：電子表格或西洋棋盤。

虛擬代碼宣告範例：
DECLARE Scores : ARRAY[1:10, 1:5] OF INTEGER

這個陣列可以儲存 10 名學生（行）在 5 個科目（列）中的成績。要存取第 5 位學生在第 2 個科目的成績：Scores[5, 2]。

處理陣列資料（搜尋與排序）

課程大綱要求理解兩種用於處理陣列資料的特定演算法：

A. 搜尋：線性搜尋 (Linear Search)

目的： 在陣列中尋找特定項目（目標）。
過程： 從陣列的第一個元素開始，檢查每一個元素，直到找到目標或到達陣列末尾為止。

你知道嗎？ 這也被稱為循序搜尋。它適用於任何陣列（無論是否已排序），但對於大型陣列來說效率很低。

B. 排序：泡沫排序 (Bubble Sort)

目的： 將陣列中的元素按升序或降序排列。
過程（步驟）： 1. 演算法重複走訪列表。
2. 它比較相鄰的元素。
3. 如果它們的順序錯誤，就進行交換 (Swap)。
4. 重複此過程，直到某一次走訪過程中沒有發生任何交換，這表示陣列已經排好序了。

類比：最輕的「氣泡」在多次走訪後會浮到列表的頂端（或其中一端）。

10.2 重點總結： 陣列儲存許多相同類型的項目。你必須能夠定義一維和二維陣列，並在概念上及虛擬代碼中理解線性搜尋和泡沫排序的工作原理。

---

10.3 檔案 (Files)

為什麼需要檔案？

當程式執行時，其資料（變數、陣列、記錄）通常儲存在 RAM（主記憶體）中。RAM 是揮發性 (Volatile) 的，這意味著當電源關閉或程式結束時，所有資料都會丟失。

我們需要使用檔案將資料永久儲存在次要儲存裝置 (Secondary Storage)（如 SSD 或 HDD）上。檔案讓資料能夠持久存在，並在未來被共享或再次存取。

在虛擬代碼中處理文字檔

你必須能夠編寫虛擬代碼來處理文字檔（由一行或多行文字組成的檔案）。常見的操作包括：

1. 開啟檔案： 在執行任何動作前，必須先 OPEN 檔案並指定模式：
- READ (讀取)： 查看現有的資料。
- WRITE (寫入)： 建立新檔案或覆寫現有檔案。
- APPEND (附加)： 將新資料新增至現有檔案的末尾。

例子：OPENFILE "results.txt" FOR APPEND

2. 讀取/寫入資料：
- 讀取： READFILE myFile, RecordVariable (讀取單一記錄或一行)。
- 寫入： WRITEFILE myFile, DataToWrite (寫入資料，通常後接換行)。

3. 關閉檔案： 操作完成後務必 CLOSEFILE，以正確儲存資料並釋放系統資源。
例子：CLOSEFILE "results.txt"

處理範例（新增名稱）：

1. OPENFILE "names.txt" FOR APPEND
2. INPUT NameInput
3. WRITEFILE "names.txt", NameInput
4. CLOSEFILE "names.txt"

10.3 重點總結： 檔案提供了永久儲存空間。你必須了解三種檔案模式（讀取、寫入、附加），以及開啟、讀取、寫入和關閉文字檔的虛擬代碼指令。

---

10.4 抽象資料類型 (ADT) 簡介

本節介紹的概念結構著重於資料結構的功能（做什麼），而非其實作方式（怎麼做）。

什麼是抽象資料類型 (ADT)？

ADT 是一組資料以及可以在該資料上執行的操作集合。

關鍵字在於「抽象」：我們不擔心底層的實作細節（例如它是使用陣列還是鏈結串列）；我們只關注可用的操作及其效果。

AS Level 中的 ADT 範例

1. 堆疊 (Stack - LIFO)

堆疊是一種有序列表，所有的插入和刪除都在同一端進行，稱為頂端 (Top)。

- 關鍵特性： LIFO (後進先出 - Last In, First Out)。 最後加入的項目永遠是第一個被移除的。

類比：自助餐廳的盤子堆。你只能從頂端放入 (PUSH) 和移除 (POP) 盤子。

- 操作： 1. PUSH： 將項目加入堆疊頂端。
2. POP： 移除並回傳堆疊頂端的項目。
3. PEEK/TOP： 查看頂端項目而不將其移除。
- 用途： 管理函式呼叫（最後呼叫的函式會最先完成）、軟體中的復原 (Undo) 機制，以及算術表達式的計算。

2. 佇列 (Queue - FIFO)

佇列是一種有序列表，插入在一端（後端 Rear）進行，而刪除在另一端（前端 Front）進行。

- 關鍵特性： FIFO (先進先出 - First In, First Out)。 第一個加入的項目永遠是第一個被移除的。

類比：巴士站的排隊隊伍。第一個排隊的人第一個上車。

- 操作： 1. ENQUEUE (或 INSERT)： 將項目加入佇列後端。
2. DEQUEUE (或 REMOVE)： 移除並回傳佇列前端的項目。
- 用途： 管理列印任務、作業系統中的 CPU 任務處理，以及網路緩衝 (Buffering)。

3. 鏈結串列 (Linked List)

鏈結串列是一種動態結構，資料元素（節點）在記憶體中非連續儲存，並透過指標 (Pointer) 連接在一起。

- 關鍵特性： 大小動態可變。與陣列不同，鏈結串列可以隨著資料的增減輕鬆擴充或縮小。
- 結構： 每個元素（節點）通常包含兩部分：資料和指向列表中下一個節點的指標。
- 用途： 管理資料量不固定的情況，且需要頻繁插入和刪除時（例如記憶體管理或多項式表示）。

10.4 重點總結： ADT 著重於功能（操作），這促進了抽象化。堆疊是 LIFO（盤子），佇列是 FIFO（排隊），而鏈結串列則是由指標連接的靈活列表。它們都可以使用固定結構的陣列來實作。