A Level 数据表示 (9618 第 13 节) 学习笔记
欢迎来到第 13 节：数据表示！如果你觉得 AS 阶段的数制系统有点棘手，别担心。A Level 的这部分内容将在此基础上，探讨计算机如何处理现实世界中复杂的结构化数据及大数据。掌握这些知识是编写高效程序并深刻理解数据存储与检索原理的关键。
准备好深入探究数据运作的底层机制了吗？我们开始吧！
13.1 用户自定义数据类型 (UDT)
在编程中，我们经常使用 INTEGER（整数）或 STRING（字符串）等标准数据类型。然而，有时我们需要一种类型来更好地反映数据的现实意义，或者将不同的数据项组合在一起。这就是 用户自定义数据类型 (User-defined Data Types, UDT) 的用武之地。
为什么需要 UDT？
- 清晰度与可读性： 它们使代码能够“自解释”。例如，如果你定义了一个名为 Colour 的类型，其值只能是红、绿或蓝，这比单纯使用数字 0、1 或 2 要清晰得多。
- 值限制： 通过限制变量可以持有的值（特别是在枚举类型中），有助于强制执行数据完整性。
- 组合相关数据： 允许将属于同一实体的不同类型数据捆绑在一起（如 Record 或 Class）。
非复合 UDT（构建基础）
1. 枚举类型 (Enumerated Type)
枚举类型 定义了一组命名的整数常量。程序员为一系列数字（通常从 0 开始）分配描述性的名称。
示例： 如果你定义了一个名为 DaysOfTheWeek 的类型，它可能包含 Monday, Tuesday, Wednesday 等。计算机将其存储为 0, 1, 2，但代码中可以使用这些名称。
目的： 提高代码可读性，并将变量限制在预定义的范围内。
2. 指针类型 (Pointer Type)
指针 是一种存储另一个数据项 内存地址 的变量。
核心概念： 指针存储的不是数据本身，而是数据所处的“位置”。这对于构建链表、栈和队列等复杂数据结构至关重要。
类比： 指针就像是门牌号（地址），而不是房子内部的物品。
复合 UDT（结构化数据）
复合类型是通过组合现有类型构建而成的。
1. 记录/结构 (Record/Structure)
记录（在某些语言中称为结构）是将一组字段（属性）集合在一起的结构，这些字段可以是 不同 的数据类型，并归于同一个标识符下。
示例： 一个名为 Student 的记录可以包含 StudentID (INTEGER)、Name (STRING) 和 Enrolled (BOOLEAN)。
2. 集合 (Set)
集合 是一组不同（唯一）项目的集合。元素的顺序不重要。
示例： 集合 A = {Apple, Banana, Pear}。如果你尝试再次添加一个 Apple，集合保持不变。
3. 类/对象 (Class/Object - 面向对象编程简介)
类 是创建 对象 的蓝图。它是面向对象编程 (OOP) 中一种功能强大的复合类型。
- 属性 (Attributes/Properties)： 描述对象的数据变量（类似于记录中的字段）。
- 方法 (Methods)： 定义对象可以执行的动作的过程和函数（子程序）。
- 实例 (Instance/Object)： 通过类蓝图创建出的具体项目。
示例： Car 类 定义了所有汽车都有 颜色（属性）且可以 加速()（方法）。你创建的具体汽车 myCar 就是 Car 类的一个 实例 或 对象，它可能有“红色”这个属性值。
13.1 核心要点： UDT 允许程序员创建反映现实实体的结构，从而提高代码的清晰度并高效管理复杂数据。指针和枚举类型是非复合类型，而记录和类用于将不同类型的数据打包在一起。
13.2 文件组织与访问
数据在磁盘上的存储方式（文件组织）决定了我们检索数据的速度（文件访问）。
文件组织方法
组织方式的选择取决于数据使用的频率和性质。
1. 串行文件组织 (Serial File Organisation)
- 描述： 记录按创建顺序一个接一个地存储。没有排序，也没有关键字段。
- 访问： 仅限顺序访问。要读取第 50 条记录，必须先读取前 49 条。
- 用途： 存储日志或交易数据，此时进入顺序很重要，且通常一次性处理所有记录。
2. 顺序文件组织 (Sequential File Organisation)
- 描述： 记录按顺序存储，但它们是根据指定的 关键字 (Key Field)（如学生 ID 或客户姓名）进行排序的。
- 访问： 主要为 顺序访问。如果从头开始搜索，比串行文件快，但仍需遍历之前的记录。
- 用途： 批处理（如工资单系统），即按顺序更新全部或大部分记录。
3. 随机文件组织 (Random File Organisation)
- 描述： 记录存储在由 记录键值（如哈希键）计算出的物理地址上。
- 访问： 直接访问。你可以通过键值瞬间计算出记录地址，无需读取其他记录，检索速度极快。
- 用途： 数据库、预订系统或索引结构，其中快速的单条记录查找至关重要。
访问方法
访问是指我们读取数据的方式。
- 顺序访问 (Sequential Access)： 必须从头开始按顺序读取数据。（用于串行和顺序文件）。
- 直接访问 (Direct Access)： 如果已知确切地址或键值，可立即获取数据。（用于随机文件和索引顺序文件）。
哈希算法 (Hashing Algorithms)
为了使用随机文件组织，我们需要一种将逻辑键（如产品代码）转换为物理存储地址的方法，这就是 哈希 (Hashing)。
什么是哈希？
哈希算法（或哈希函数）接收输入键，并通过数学运算计算出记录应存储的唯一（或几乎唯一）内存地址。
哈希计算步骤（简单的取模法）：
- 选择最大存储空间 N（例如 100）。
- 获取记录的数字键值 K（例如 K = 5472）。
- 进行取模运算：Address = K MOD N。
- 示例： Address = 5472 MOD 100 = 72。记录存储在地址 72。
冲突与溢出
由于地址空间 (N) 通常远小于键值的可能范围，两个不同的键可能会计算出相同的地址，这称为 冲突 (Collision)。
- 冲突处理： 如果 72 号位置已被占用，系统必须使用某种技术（如 链地址法 或 线性探测法）来寻找附近下一个可用的空位。
- 溢出 (Overflow)： 如果文件已满，则可能需要扩展存储空间。
冷知识： 哈希也广泛应用于安全领域，通过创建文件的数字指纹（哈希校验和）来验证文件的完整性。
13.2 核心要点： 文件组织决定了访问速度。尽管存在冲突处理的挑战，但随机组织结合哈希技术能实现最快的直接访问，这对于实时系统至关重要。
13.3 浮点数：表示与运算
AS 课程涵盖了整数。现在我们来看 实数（包含小数部分的数字，如 12.375 或 -0.5），它们使用 浮点数 格式表示。
浮点数分为两部分存储，就像科学计数法 (\(a \times 10^b\))：
数值 = 尾数 × 基数\(^{\text{指数}}\)
在二进制中，基数始终为 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。
浮点数转十进制（步骤说明）
假设尾数 (M) 为 8 位，指数 (E) 为 4 位。
浮点表示：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\)，因为小数部分为 0)。
十进制：\(1 \times 2^2 + 0 \times 2^1 + 1 \times 2^0 = 4 + 1 = 5\)。
该浮点数代表的十进制值为 5。
学习建议： 当处理负尾数或负指数时，请务必先将补码转换回其负十进制值，然后再进行后续计算！
浮点表示法的后果
1. 位分配的影响
尾数和指数之间的位分配决定了所存储数字的整体特性：
- 增加尾数位数： 提高 精度（有效数字更多），但会减少数字可存储的最大 范围（指数的可用位减少）。
- 增加指数位数： 扩大 范围（可以存储更大或更小的数字），但会降低 精度（用于存储有效数字的位减少）。
2. 近似与舍入误差
浮点表示法中尾数的位数是有限的。这意味着许多实数（尤其是像十进制的 1/3 或二进制的 0.1 这样无限循环的分数）只能以 近似值 存储。
这种近似可能导致算术运算过程中出现 舍入误差，这意味着计算结果可能不够精确。
3. 上溢与下溢
- 上溢 (Overflow)： 当计算结果超出了最大 指数 所能表示的最大值时发生。数值超出了最大范围。
- 下溢 (Underflow)： 当计算结果极其接近 0（太小），以至于最小的 指数 无法准确表示时发生。数值低于最小范围。
13.3 核心要点： 浮点表示法使用尾数（精度）和指数（范围），两者通常都以补码形式存在。规格化对于最大化精度至关重要。请注意，此方法依赖近似，会导致舍入误差，并受限于位分配导致的数值范围（上溢/下溢）。
高级数据表示总结
恭喜你攻克了这个复杂的主题！请记住：
- UDT 有助于组织和验证复杂数据 (13.1)。
- 文件组织控制访问速度；哈希技术实现了快速的直接访问 (13.2)。
- 浮点数允许表示实数，但需要精准处理尾数、指数和规格化，以管理范围和精度的局限性 (13.3)。
保持练习浮点数转换，你一定能完全掌握这一节！