A Level 數據表示法 (9618 第 13 章) 學習筆記
歡迎來到第 13 章：數據表示法！如果你覺得 AS 程度的數字系統有點棘手，不用擔心。A Level 的內容將建立在這些基礎上，並應用於電腦如何處理現實世界中複雜的數據，例如大數值和結構化資訊。理解這一點對於編寫高效程式，以及真正掌握數據的儲存與檢索方式至關重要。
準備好深入探索數據的底層運作了嗎？我們開始吧！
13.1 自訂數據類型 (User-defined Data Types, UDTs)
在程式設計中，我們經常使用標準數據類型，如 INTEGER（整數） 或 STRING（字串）。然而，有時我們需要一種能更好地反映數據現實背景，或將不同數據項目組合在一起的類型。這就是 自訂數據類型 (UDTs) 的用武之地。
為什麼需要 UDTs？
- 清晰度與可讀性： 它們使程式碼具有自我說明功能。如果你定義了一個名為 Colour 的類型，且只能是紅、綠或藍，這比單純使用整數 0、1 或 2 來得清晰得多。
- 限制數值： 它們有助於強制執行數據完整性，限制變數可保存的數值（特別是在枚舉類型中）。
- 分組相關數據： 它們允許你將屬於單一實體的不同類型數據捆綁在一起（例如 記錄 Record 或 類別 Class）。
非組合式 UDTs（構建基礎）
1. 枚舉類型 (Enumerated Type)
枚舉類型定義了一組命名的整數常數。程式設計師為一系列數字（通常從 0 開始）分配描述性的名稱。
範例： 如果你定義了一個名為 DaysOfTheWeek 的類型，它可能包含 Monday, Tuesday, Wednesday 等。電腦將它們儲存為 0, 1, 2，但程式碼使用的是這些名稱。
用途： 提高程式碼可讀性，並將變數限制在僅能使用這些已定義的數值。
2. 指標類型 (Pointer Type)
指標是一個儲存另一個數據項目之 記憶體位址 的變數。
核心概念： 指標不是儲存數據本身，而是指向數據所在的位置。這對於建構鏈結串列 (linked lists)、堆疊 (stacks) 和佇列 (queues) 等複雜數據結構至關重要。
類比： 指標就像是門牌號碼（位址），而不是房子裡面的東西。
組合式 UDTs（結構化數據）
組合類型是透過結合現有類型所建構的。
1. 記錄 (Record/Structure)
記錄（在某些語言中稱為結構）是一組欄位（屬性）的集合，這些欄位可以具有 不同 的數據類型，並歸類在同一個識別碼下。
範例： 一個名為 Student 的記錄可以包含 StudentID (INTEGER)、Name (STRING) 和 Enrolled (BOOLEAN)。
2. 集合 (Set)
集合是一組相異（唯一）項目的組合，元素的順序並不重要。
範例： 集合 A = {Apple, Banana, Pear}。如果你嘗試加入另一個 Apple，集合內容保持不變。
3. 類別/物件 (Class/Object)（物件導向程式設計入門）
類別 (Class) 是創建 物件 (Objects) 的藍圖。它是物件導向程式設計 (OOP) 中一種功能強大的組合類型。
- 屬性 (Attributes)： 描述物件的數據變數（就像記錄中的欄位）。
- 方法 (Methods)： 定義物件可以執行之動作的程序和函數（子程式）。
- 實例 (Instance/Object)： 根據類別藍圖創建的實際項目。
範例： Car 類別 定義了所有汽車都有 顏色（屬性）並且可以 加速()（方法）。你創建的一輛具體汽車 myCar，就是 Car 類別的 實例 或 物件，它的顏色可能是「紅色」。
第 13.1 章重點： UDTs 允許程式設計師創建反映現實世界實體的數據結構，從而提高程式碼的清晰度並高效管理複雜數據。指標和枚舉類型是非組合式的，而記錄和類別則用於將不同數據類型捆綁在一起。
13.2 檔案組織與存取
數據在磁碟上的儲存方式（檔案組織）決定了我們檢索數據的速度（檔案存取）。
檔案組織方法
組織方式的選擇取決於數據使用的頻率和性質。
1. 串列檔案組織 (Serial File Organisation)
- 描述： 記錄按建立順序一個接一個地儲存。沒有排序，也沒有關鍵欄位。
- 存取： 僅限順序存取。若要讀取第 50 筆記錄，必須先讀取前 49 筆記錄。
- 應用場景： 儲存紀錄檔 (logs) 或交易數據，其中輸入順序很重要，且通常一次處理所有記錄。
2. 順序檔案組織 (Sequential File Organisation)
- 描述： 記錄一個接一個地儲存，但會根據指定的 關鍵欄位 (key field)（例如學生 ID 或客戶名稱）進行排序。
- 存取： 主要為 順序存取。若從頭開始搜尋，比串列檔案更快，但仍需遍歷先前的記錄。
- 應用場景： 批次處理（例如薪資系統），其中所有或大部分記錄都是依序更新的。
3. 隨機檔案組織 (Random File Organisation)
- 描述： 記錄儲存在從 記錄鍵值 (record key)（例如雜湊鍵）計算出的物理位址中。
- 存取： 直接存取。你可以利用鍵值瞬間計算出記錄的位址，無需讀取其他記錄即可快速檢索。
- 應用場景： 資料庫、預訂系統或索引結構，在這些地方快速的單筆記錄查詢至關重要。
存取方法
存取指的是我們如何讀取數據。
- 順序存取 (Sequential Access)： 數據必須從頭開始按順序讀取。（用於串列和順序檔案）。
- 直接存取 (Direct Access)： 如果已知確切位址或鍵值，即可立即檢索數據。（用於隨機檔案和索引順序檔案）。
雜湊演算法 (Hashing Algorithms)
若要使用隨機檔案組織，我們需要一種將邏輯鍵（如產品代碼）轉化為物理儲存位址的方法。這是透過 雜湊 (hashing) 來完成的。
什麼是雜湊？
雜湊演算法（或雜湊函數）接收一個輸入鍵值，並透過數學運算計算出記錄應儲存的唯一（或幾乎唯一）記憶體位址。
逐步雜湊（簡易模數法）：
- 選擇儲存位置的最大數量 N（例如 100）。
- 取記錄的數字鍵 (K)（例如 K = 5472）。
- 應用模數運算：Address = K MOD N。
- 範例： Address = 5472 MOD 100 = 72。記錄儲存在 72 號位址。
碰撞與溢出 (Collision and Overflow)
由於位址空間 (N) 通常遠小於可能鍵值的範圍，兩個不同的鍵值可能會計算出相同的位址。這稱為 碰撞 (collision)。
- 碰撞處理： 如果 72 號位置已被佔用，系統必須使用某種技術（如 鏈結法 (chaining) 或 線性探測 (linear probing)）來尋找附近下一個可用的空位。
- 溢出： 如果檔案已滿，可能需要擴展儲存空間。
你知道嗎？ 雜湊也廣泛應用於安全領域，用於創建檔案的數位指紋（雜湊總和）以驗證其完整性。
第 13.2 章重點： 檔案組織決定了存取速度。隨機組織結合雜湊法提供了最快的直接存取，這對於即時系統至關重要，儘管需解決碰撞問題。
13.3 浮點數：表示與操作
AS 課程涵蓋了整數。現在我們要探討 實數（包含小數部分的數字，如 12.375 或 -0.5），它們是使用 浮點數 (floating-point) 格式來表示的。
浮點數分為兩個主要部分儲存，就像科學記號表示法 (\(a \times 10^b\)) 一樣：
數值 = 尾數 (Mantissa) × 底數\(^{\text{指數 (Exponent)}}\)
在二進位中，底數永遠是 2。因此，表示形式如下：
二進位數 = 尾數 × 2\(^{\text{指數}}\)
浮點數格式
分配的位元被分成三個部分：
- 符號位元 (Sign Bit)： 指示數字是正數 (0) 還是負數 (1)。
- 尾數 (Mantissa, M)： 儲存有效數字（精確度）。
- 指數 (Exponent, E)： 儲存 2 的冪次（數值的大小或範圍）。
關鍵點： 尾數和指數通常都使用 二補數 (Two's Complement) 來表示負值（這是課程綱要規定的）。
負數的表示
由於我們在尾數和指數中使用二補數，你必須記住以下步驟：
要找到負數的二補數：
- 反轉所有位元（0 變 1，1 變 0）。
- 將結果加 1。
正規化 (Normalisation)
儲存數字時，我們必須確保 尾數 始終以特定的、標準化的格式書寫。此過程稱為 正規化。
為什麼要正規化？ 為了確保保留最大可能的精確度（有效位數），並且每個數字都有唯一的表示方式。
在正規化二進位中，尾數必須始終以以下開頭：
- 0.1...（對於正數，0 後面跟著二進位點，然後是 1）
- 1.0...（對於負數，1 後面跟著二進位點，然後是 0）
範例：將 0.001101（正數）正規化：
- 原始值：0.001101。我們想要獲得 0.1... 的模式。
- 將二進位點向右移動 3 位：0.1101。
- 由於我們向右移動了 3 位，指數為 \(-3\)。
- 正規化尾數：0.1101。正規化指數：-3。
範例：將 101.01（正數）正規化：
- 原始值：101.01。
- 將二進位點向左移動 2 位：0.10101。
- 由於我們向左移動了 2 位，指數為 \(+2\)。
- 正規化尾數：0.10101。正規化指數：+2。
將浮點數轉換為十進位（逐步教學）
假設我們有 8 位元給尾數 (M)，4 位元給指數 (E)。
浮點表示法：01010000 | 0011
M = 01010000 (8 位元) | E = 0011 (4 位元)
- 計算指數 (E)：
E = 0011。由於這是二補數的正數，十進位值為 3。
這意味著我們將二進位點向右移動 3 位。
- 計算尾數值 (M)：
M = 01010000。這是一個正數（符號位元為 0）。二進位點在第一位之後：0.1010000
尾數值：\(0 \times 2^0 + 1 \times 2^{-1} + 0 \times 2^{-2} + 1 \times 2^{-3} + 0 \times 2^{-4} \dots\)
尾數值：\(0.5 + 0.125 = 0.625\)
- 應用指數位移：
取二進位尾數 (0.1010000) 並將二進位點向右移動 3 位（因為 E = +3）。
\(0.1010000 \rightarrow 0101.0000\)
- 將最終二進位數轉換為十進位：
二進位：\(101.0\)（由於小數部分為零，即 101）。
十進位：\(1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 4 + 1 = 5\)
此浮點數代表十進位值 5。
學習小貼士： 當處理負的尾數或指數時，記得先將二補數表示法轉換回其負的十進位值，然後再進行計算！
浮點表示法的後果
1. 位元分配的影響
尾數和指數之間的分配決定了可儲存數字的整體性質：
- 增加尾數大小： 增加 精確度（更多有效數字），但減少了可儲存的最大 範圍（指數空間變小）。
- 增加指數大小： 增加 範圍（可儲存更大和更小的數字），但減少了 精確度（用於儲存有效數字的位元變少）。
2. 近似值與捨入誤差
浮點表示法在尾數中僅保留有限的位元數。這意味著許多實數（特別是無限循環小數，如十進位中的 1/3 或二進位中的 0.1）只能作為 近似值 儲存。
這種近似值可能會導致算術運算中的 捨入誤差，意味著計算結果可能不完全精確。
範例： 如果你的尾數只有 4 位元，0.1011001 可能會被捨入為 0.1011，而丟失剩餘的小數部分。
3. 上溢與下溢 (Overflow and Underflow)
- 上溢 (Overflow)： 當計算結果大於最大 指數 大小所能表示的數值時發生。數值超過了最大範圍。
- 下溢 (Underflow)： 當計算結果太接近零（太小），以至於無法被最小 指數 大小準確表示時發生。數值低於最小範圍。
第 13.3 章重點： 浮點數表示法使用尾數（精確度）和指數（範圍），兩者通常皆使用二補數。正規化對於獲得最大精確度至關重要。請注意，此方法依賴近似值，這會導致潛在的捨入誤差，以及受位元分配限制的數值範圍（上溢/下溢）。
進階數據表示法總結
恭喜你攻克了這個複雜的主題！請記住：
- UDTs 有助於結構化和驗證複雜數據 (13.1)。
- 檔案組織控制存取速度；雜湊實現了快速的直接存取 (13.2)。
- 浮點數允許表示實數，但需要精確處理尾數、指數和正規化，以管理範圍和精確度的限制 (13.3)。
繼續練習這些浮點數轉換，你一定能掌握這一章！