Data Types and Structures

数据类型与数据结构 (AS Level 9618: 第10章)

你好，未来的计算机科学家们！本章内容至关重要，因为它将教你如何组织和管理程序所使用的数据。你可以把数据类型和数据结构想象成存储信息时所使用的不同类型的容器和文件柜。选择合适的容器能让你的程序更高效、更易于管理。

如果某些术语看起来很抽象，不必担心。我们将通过简单、现实生活中的例子来一一拆解！

---

10.1 数据类型与记录

基本构建块：内置数据类型

计算机处理的每一条信息都必须经过分类。数据类型 (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。

结构化数据：记录 (Record)

如果需要存储 不同 数据类型的相关项该怎么办？简单的变量无法实现。这时就轮到 记录结构 (Record Structure) 上场了。

记录的定义：

记录是一组相关数据项（字段/属性）的集合，它们可能具有 不同的数据类型，并统一存储在一个标识符（名称）下。

类比：想象一张学生证。这张卡本身就是一个“记录”。在卡里，你有姓名（STRING）、年龄（INTEGER）以及是否缴费的状态（BOOLEAN）。

记录的用途： 1. 组织性： 它将相关数据保存在一起，使代码更加整洁。
2. 高效性： 你可以将一个记录变量传递给过程（Procedure），而无需传递多个独立的变量。

在伪代码中定义记录：
我们使用 TYPE... END TYPE 结构来定义结构，然后声明该类型的变量。

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

DECLARE NewStudent : T_Student

然后，你可以使用点符号访问这些字段，例如：NewStudent.StudentName。

10.1 小结： 数据类型定义了单个数据项的性质。记录将多个相关且可能类型不同的数据项组合在一个名称下，从而实现更好的组织。

---

10.2 数组 (Arrays)

数组可以说是你在编程中最常使用的数据结构。

什么是数组？

数组是一种数据结构，用于保存 相同数据类型 的一系列数据项，通过 索引 (index)（或下标）进行访问。

对比：请记住，记录存放不同类型的数据；而数组存放相同类型的数据。

与数组相关的技术术语：

- 索引 (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 是 数据 以及 一组可在该数据上执行的允许操作 的集合。

关键词是 抽象 (Abstract)：我们不必担心底层的实现细节（例如它是否使用数组或链表）；我们只关注可用的操作及其效果。

AS Level 中的 ADT 示例

1. 栈 (Stack, LIFO)

栈是一种有序列表，所有插入和删除操作都在同一端进行，称为 栈顶 (Top)。

- 关键特性： LIFO (后进先出)。最后添加的项目总是第一个被移除的项目。

类比：餐厅餐盘托架。你只能在顶部添加 (PUSH) 和移除 (POP) 餐盘。

- 操作： 1. PUSH： 将项目添加到栈顶。
2. POP： 移除并返回栈顶的项目。
3. PEEK/TOP： 查看栈顶项目但不移除它。
- 原理/用途： 管理函数调用（最后调用的函数是第一个完成的）、软件中的撤销机制以及计算算术表达式。

2. 队列 (Queue, FIFO)

队列是一种有序列表，插入操作在一端（队尾 Rear）进行，删除操作在另一端（队首 Front）进行。

- 关键特性： FIFO (先进先出)。第一个添加的项目是第一个被移除的项目。

类比：公交站的排队人流。第一个排队的人是第一个上车的人。

- 操作： 1. ENQUEUE (或 INSERT)： 将项目添加到队列的队尾。
2. DEQUEUE (或 REMOVE)： 移除并返回队首的项目。
- 原理/用途： 管理打印任务、操作系统中处理 CPU 任务以及网络缓冲。

3. 链表 (Linked List)

链表是一种动态结构，数据元素（节点）存储在非连续的内存位置（彼此不相邻），并使用 指针 (pointers) 链接在一起。

- 关键特性： 动态大小。与数组不同，链表可以随着数据的添加或删除而轻松增长或缩减。
- 结构： 每个元素（节点）通常包含两部分：数据 和指向列表中下一个节点的 指针。
- 原理/用途： 管理数据量灵活且需要频繁插入和删除的操作（例如内存管理或多项式表示）。

10.4 小结： ADT 侧重于功能（操作），提升了抽象程度。栈是 LIFO（如盘子堆），队列是 FIFO（如排队），链表则是通过指针连接的灵活列表。它们都可以使用固定的数组结构来实现。