数据类型与数据结构

每个变量都需要一个数据类型(data type)——它容纳的值的种类和允许的操作:

• INTEGER — 一个整数(42、-7)。用于计数、索引、ID。
• REAL — 一个带小数部分的数(3.14)。用于金额、测量。
• STRING — 引号中的字符("Hello")。用于文本。
• CHAR — 一个单一字符('A')。
• BOOLEAN — TRUE 或 FALSE。用于标志。
• DATE — 一个日历日期。

选择适合的最小而精确的类型:INTEGER 用于整数计数,BOOLEAN 用于标志(而不是字符串 "yes"/"no")。

"给出合适的数据类型"表格由值的用法决定:全班的平均分是 REAL(有小数部分);电子邮箱地址是 STRING;学生人数是 INTEGER;学生是否已缴费是 BOOLEAN;出生日期是 DATE;数组下标永远是 INTEGER;单个等级字母是 CHAR;电话号码是 STRING,因为它以 0 开头且从不参与算术。BOOLEAN 用于只有两种状态的标志:查找是否找到目标、会员是否已缴费、座位是否已订。在标识符表中,变量名也必须有意义:NumberOfPeople,而不是 n。

一个记录(record,一个记录结构(record structure))在一个名称下容纳几个不同类型的字段——当几个值描述同一件事物时很有用。

TYPE TStockItem
    DECLARE ItemID : INTEGER
    DECLARE Category : STRING
    DECLARE ItemCost : REAL
    DECLARE InStock : BOOLEAN
ENDTYPE

这定义了类型 TStockItem;声明它的变量:

DECLARE Item1 : TStockItem
DECLARE Items : ARRAY[1:100] OF TStockItem

用点记法访问每个字段(field):

Item1.Category ← "Fruit"
OUTPUT Item1.Category, " costs ", Item1.ItemCost

当值总是属于一起时(一个客户、一个库存商品)用一个记录;对无关的值用分开的变量。

例题。 一个俱乐部为每个学生存储学生 ID(字符串)、姓名、出生日期和最多三个俱乐部编号(整数)。写出伪代码来声明记录类型、一个容纳 $3000$ 个学生的数组,以及把一个姓名存入第一个元素的语句。

TYPE Student
    DECLARE StudentID : STRING
    DECLARE Name : STRING
    DECLARE DateOfBirth : DATE
    DECLARE Club : ARRAY[1:3] OF INTEGER
ENDTYPE

DECLARE Membership : ARRAY[1:3000] OF Student
Membership[1].Name ← "Li Wei"

给分点:带标识符的 TYPE 和 ENDTYPE;每个字段以合适的类型声明;数组带边界和 OF Student 声明;用下标和点访问字段。"指出记录声明中的错误"通常指向缺少 ENDTYPE、没有类型的字段,或者一个必须参与算术却声明为 STRING 的字段。两个约定本身就得分:未使用的元素用一个不可能是真实数据的值标记(空字符串、-1、ID 为 0),而且处处用同一个标记是好习惯,这样每个模块都能识别未使用的槽;未使用的俱乐部字段是 0。记录数组的好处,用于"说出三个好处":一个实体的全部数据保存在一个标识符下;各字段可以有不同的数据类型;一个数组代替了几个必须保持同步的平行数组;整个集合可以用一个循环处理或作为一个参数传递;增加字段只需改类型定义。对一个客户,合适的结构是记录(一个名称下不同类型的字段);对所有客户,是记录数组。

一个数组(array)是同一类型的项的一个有序集合,在一个名称下,用一个索引(index)访问。

• 元素(element)——数组中的一项。
• 边界(bounds)——最低和最高的有效索引。
• 维度(dimension)——1-D(一个列表)、2-D(一个表格),等等。
• 下界(lower bound)和上界(upper bound)——第一个和最后一个有效下标;元素个数是上界减下界加一,二维数组则是两个个数之积。

所以在 ThisArray[n] ← 42 中,数组有一个维度,下标是变量 n(一个 INTEGER),该下标处的元素得到 42。声明数组之前,除了边界还需要它的数据类型。声明 $120$ 个可能带小数的值:DECLARE Data : ARRAY[1:120] OF REAL;一个 $150$ 行、两列的字符串表:DECLARE Data : ARRAY[1:150, 1:2] OF STRING,它有 $300$ 个元素。数组相对分开的变量的好处,用于两分的解释:一个标识符代替三十个;元素可以用以下标为计数器的循环处理;大小容易改变;整个集合可以作为一个参数传给模块。数组还可以代替一串选择语句:DaysInMonth[Month] 直接查出答案,代替十二个 IF 子句,更短、更快写、更易维护。

1-D arrays

DECLARE Names : ARRAY[1:5] OF STRING
Names[3] ← "Cara"
OUTPUT Names[3]

用一个 FOR 循环处理每个元素:

FOR i ← 1 TO 5
    OUTPUT Names[i]
NEXT i

2-D arrays (2D array)

DECLARE Grid : ARRAY[1:3, 1:4] OF INTEGER
Grid[2, 3] ← 99

第一个索引是行,第二个是列。用嵌套循环访问每个单元。对一个单一序列用 1-D,对两个自然维度(一个网格,行 × 列)用 2-D。

Common operations

一个线性查找(linear search)检查每个元素直到找到:

FOR i ← 1 TO n
    IF A[i] = Target THEN
        OUTPUT "Found at ", i
    ENDIF
NEXT i

要求一个和、计数、最大值或最小值,设一个运行中的变量,然后扫过:

Max ← A[1]
FOR i ← 2 TO n
    IF A[i] > Max THEN Max ← A[i]
NEXT i

一个冒泡排序(bubble sort)把一个数组排序:扫过它,比较每个相邻对,并交换任何顺序错误的;重复各趟直到某一趟不再有交换。

Paper 2 既要求把这些算法写成伪代码,也要求写成文字步骤,有时还要"高效"的形式:

• 最大值:把 Largest 设为第一个元素;对其余每个元素,如果它比 Largest 大,就存入 Largest;循环后输出 Largest。要求最大值的位置,就再用一个变量,在 Largest 每次改变时存下标。
• 返回位置的线性查找:循环前设 FoundAt ← -1(一个绝不可能是有效下标的值,所以表示"未找到");遍历数组;元素匹配时存下标并离开循环;循环后检验 FoundAt。
• 计数或输出非空元素:把每个元素与未使用元素的标记("" 或 -1)比较,只计数或输出不同的那些。
• 删除一项:用线性查找找到它的下标;把后面的每个元素向前移一位,填上空缺;把最后一个元素标为未使用(或把计数减一)。
• 插入到有序数组:找到第一个元素更大的下标;把该元素及其后的每个元素向后移一位;把新值存入空缺。
• 高效冒泡排序:一个 Swapped 标志,使某一趟没有交换时就停止;一个每趟减一的上限,因为最大值已经到达末尾。

REPEAT
    Swapped ← FALSE
    FOR Index ← 1 TO Limit - 1
        IF Data[Index] > Data[Index + 1] THEN
            Temp ← Data[Index]
            Data[Index] ← Data[Index + 1]
            Data[Index + 1] ← Temp
            Swapped ← TRUE
        ENDIF
    NEXT Index
    Limit ← Limit - 1
UNTIL Swapped = FALSE

给分点是:重复直到没有交换的外层循环、在 IF 内设置的标志、用临时变量的三行交换,以及逐渐缩小的上限。"分步"(逐步求精)的排序是:重复直到有序;每趟比较相邻对;交换顺序错误的一对;每趟之后最大的未排序值位于末尾。两个记录数组或平行数据的数组用一个循环和一个下标处理;二维数组需要嵌套循环,外层遍历行、内层遍历列,在某一行中查找就固定行下标、循环列。

一个文件(file)是存储在辅助存储器(secondary storage)上的数据,在程序运行之间保留。RAM 中的变量在程序结束时消失,所以要永久保存数据(高分、记录、设置),程序写入一个文件。文件也让程序共享数据并从一个保存的状态重启。

一个文本文件(text file)容纳一行或多行可读字符;程序逐行读写文本文件。使用前打开一个文件,用后关闭它:

OPENFILE "data.txt" FOR READ      // or FOR WRITE, FOR APPEND
WHILE NOT EOF("data.txt") DO
    READFILE "data.txt", LineString
    OUTPUT LineString
ENDWHILE
CLOSEFILE "data.txt"

EOF 在读取之前测试文件结束(end of file)。要写入:

OPENFILE "log.txt" FOR WRITE
FOR i ← 1 TO 100
    WRITEFILE "log.txt", "Event " & i
NEXT i
CLOSEFILE "log.txt"

总是关闭每个文件——否则缓冲的写入可能丢失,而且其他程序可能被锁在外面。

为什么用文件(两分):数据在程序结束后仍然保留,下次运行时可用;可以与其他程序共享;可以容纳超过内存容量的数据。让程序能逐行处理文本文件的特性是:它是一系列行,从头开始一行接一行地读。三种模式:READ 从头读取;WRITE 创建新文件,会删除已有的内容,所以不能用来向文件添加;APPEND 在已有文件末尾添加行。每次读取前检验 EOF,而且即使几个模块都用同一个文件也只打开一次。

例题。 写出过程 LastLines(FileName : STRING) 的伪代码,按顺序输出一个文本文件的最后三行。

PROCEDURE LastLines(BYVAL FileName : STRING)
    DECLARE LineX, LineY, LineZ : STRING
    LineX ← ""
    LineY ← ""
    LineZ ← ""
    OPENFILE FileName FOR READ
    WHILE NOT EOF(FileName) DO
        LineX ← LineY
        LineY ← LineZ
        READFILE FileName, LineZ
    ENDWHILE
    CLOSEFILE FileName
    OUTPUT LineX
    OUTPUT LineY
    OUTPUT LineZ
ENDPROCEDURE

每读一行新内容就把前三行往前推一格,所以文件结束时三个变量正好保存它的最后三行;行数不足的文件输出空字符串。要输出前五行,就数已读的行数,在读满五行或到 EOF 时停止,以先到者为准;空文件通过打开后 EOF 立即为 TRUE 来判断。

一行中的字段。 文本文件保存的是字符串,所以一个记录写成一行,各字段用一个分隔符(separator)字符连接,每个数或布尔值用 NUM_TO_STR 转换(读回时用 STR_TO_NUM,或与 "TRUE" 比较)。选一个绝不会出现在数据中的分隔符:姓名和数字用逗号或 |,姓名可能含空格时绝不用空格。如果某个字段可以含任何字符,分隔符就会与数据混淆;解决办法是把每个字段单独放一行,或在字段前写出它的长度。每项一行读回简单,但用的行更多,而且一条记录更难被看成一个整体。读取行按已知顺序(按 ID 升序)排列的文件时,一读到更大的 ID 就可以停止查找,而不必读到末尾。每次存档都新建的存档文件需要有意义的文件名,例如玩家姓名加日期和时间,这样任何较早的存档都能恢复。

一个抽象数据类型(Abstract Data Type,ADT)是一组数据加上对它的操作,由它做什么定义,而不是它如何存储。用户只通过操作工作;实现被隐藏,所以它可以改变而不影响使用该 ADT 的代码。要知道三个:栈、队列、链表。

一分的定义:ADT 是一组数据连同对该数据的一组操作。栈、队列、链表、二叉树和数组都是 ADT。要论证选择:当各项必须按到达顺序处理时用队列(打印任务、按键、商店里的顾客),因为它先进先出;当最近的项必须最先处理时用栈(撤销、网页后退、颠倒顺序、嵌套调用的返回地址),因为它后进先出;当经常在有序序列的中间插入和删除时用链表,因为只改指针,不必移动任何东西。要比较栈和队列:两者都是有顺序的线性结构,都用数组和指针实现,都需要在添加前检查是否满、在移除前检查是否空;栈有一个指针,在同一端添加和移除,队列有两个指针,在一端添加、在另一端移除。

Stack

一个栈(stack)以 LIFO(后进先出,Last In, First Out)顺序工作。操作:入栈(push,加到顶部)、出栈(pop,从顶部移除)、peek(查看顶部),以及对空/满的测试。用途:撤销历史、函数调用返回地址、表达式解析、回溯。

例题。 一个字符栈从底部起存有 'P'、'N'、'Z'、'X'、'Y'、'W',栈顶指针指向 'W'(200–207 中的内存位置 202)。执行操作 POP、POP、PUSH 'A'、PUSH 'B'、POP。栈中有什么,指针指向哪里?

两次 pop 先后移除 'W' 和 'Y';两次 push 在它们的位置加入 'A' 和 'B';最后一次 pop 移除 'B'。栈现在存有 'P'、'N'、'Z'、'X'、'A',指针指向 'A',位置 203。在栈中停留最久的值是底部的项 'P';栈空之前最多还能 pop 五次,而对空栈 pop 是错误,所以 Pop() 先检验是否为空。成功时返回 TRUE 的 Push() 函数先检验指针是否在数组顶端(满),若是则返回 FALSE。数组元素使用前不需要初始化,因为仅凭指针就知道哪些元素在使用中。

Queue

一个队列(queue)以 FIFO(先进先出,First In, First Out)顺序工作。操作:入队(enqueue,加到后端)、出队(dequeue,从前端移除),以及对空/满的测试。用途:打印假脱机、调度、广度优先搜索、缓冲。

要描述添加一项:检查队列未满;把该项存入队尾指针给出的位置;队尾指针加一(计数也加一)。要描述移除:检查队列非空;读取队首指针处的项;队首指针加一(计数减一)。说明你用的约定:如果队尾指针标记的是下一个空位,队首和队尾指针相等就表示队列为空;如果它标记的是最后一项,指针相等表示有一项。在线性队列中队首指针只会向前移动,所以它后面的单元被浪费;下面的循环队列正是解决这一点的。要说出的队列的两个特征:项在后端添加、从前端移除,所以最先添加的最先移除。

Linked list

一个链表(linked list)把数据存储为一系列节点(nodes)。每个节点容纳一个值和一个指向下一个节点的指针(pointer);一个头指针标记起点,而最后一个节点的指针是一个哨兵(例如 NULL)。操作:插入、删除、搜索,以及遍历(traverse,按顺序访问每个节点)。它相对数组的优点是廉价的插入/删除(只需调整指针);它的缺点是慢的随机访问(你必须从头跟随指针)。

按顺序添加节点(四分):从头指针出发沿指针遍历链表,直到找到目标位置之前的节点(最后一个值更小的节点);取一个空闲节点并把新值存入其中;把新节点的指针设为前一个节点原来指向的地址;把前一个节点的指针设为新节点。如果新值应在最前面,则改头指针。删除节点:找到它前面的节点,把该节点的指针设为被删节点原来指向的地址,链表就绕过了它;释放的节点回到空闲列表。与一维数组相比,链表中插入或删除不需要移动其他项,而且链表可以增长到内存用完为止;代价是每一项都要额外存一个指针,以及到达第 $n$ 项要顺着 $n$ 个指针走,因为没有直接的下标。

Stack using an array

把项保存在 Stack[1:MaxSize] 中,带一个整数 Top(空时为 0)。

• Push(x):若 Top = MaxSize 则栈满(溢出(overflow));否则 Top ← Top + 1;Stack[Top] ← x。
• Pop():若 Top = 0 则栈空(下溢(underflow));否则返回 Stack[Top] 并 Top ← Top - 1。

Queue using a circular array

一个简单队列让 Front 和 Rear 走出末端,浪费起始部分。修正是一个循环数组(circular array)——当一个指针到达 MaxSize 时它绕回到 1:

• Enqueue(x):检查满;否则 Rear ← (Rear MOD MaxSize) + 1;Queue[Rear] ← x。
• Dequeue():检查空;否则返回 Queue[Front] 并 Front ← (Front MOD MaxSize) + 1。

跟踪一个单独的计数以区分空和满。

队尾指针的算法,用文字表述:如果计数等于大小,报告队列已满并停止;否则队尾指针加一;如果它超过了最后一个下标,就设为第一个下标;把项存在那里并把计数加一。五分的"描述声明和初始化"答案要列出的声明:带大小和元素类型的数组;队首指针和队尾指针,都初始化为第一个下标(或者队首为第一个下标、队尾为下一个空位);以及初始化为 $0$ 的项数计数。

例如,当 MaxSize = 6 时:若 Rear = 5,则 (5 MOD 6) + 1 = 6,所以下一项放入单元 6;若 Rear = 6,则 (6 MOD 6) + 1 = 1,所以指针绕回到单元 1。

Linked list using an array

用一个记录的数组,每个带一个 Next 索引:

TYPE TNode
    DECLARE Value : INTEGER
    DECLARE Next : INTEGER     // index of the next node, or -1 for end
ENDTYPE

DECLARE Nodes : ARRAY[1:MaxSize] OF TNode
DECLARE Head : INTEGER         // index of first node, -1 if empty
DECLARE FreeListHead : INTEGER // first available free node

一个空闲列表(free list)把未使用的槽链在一起,正如数据列表把它用过的槽链在一起。要插入:从 FreeListHead 取一个槽,设新节点的值和 Next,并更新前一个节点的 Next(或 Head)。要删除:解开该节点的链接并把它的槽还给空闲列表。这给出一个链式结构的灵活性和一个数组的静态分配。

例题。 一个链表存放在 Data 数组和 Pointer 数组中,Start 指向下标 1。链表是 1 → 3 → 4(下标 1 存 D40,下标 3 存 D32,下标 4 存 D11,其指针为 $\emptyset$);空闲列表从下标 2 开始,接着 2 → 5。在 D32 和 D11 之间插入 D6。

取第一个空闲节点下标 2,并把 FreeStart 设为它的指针 5;把 D6 存入 Data[2];把 Pointer[2] 设为 Pointer[3] 原来的值 4;把 Pointer[3] 设为 2。链表变为 1 → 3 → 2 → 4,空闲列表是 5 → $\emptyset$。"链表如何实现"的答案正是这些部分:存数据的数组(或记录数组)、存下标的平行指针数组、一个起始指针、一个空闲列表指针,以及像 $-1$ 这样表示末尾的空值。

例题。 一个循环队列存放在大小为 5 的数组中(下标 0 到 4),此时 Front = 3、Rear = 3,存有一个元素。先加入两个元素,再移除两个。指针各在哪里?为什么要用循环队列?每次移动都用 (指针 + 1) MOD 大小,所以指针会回绕。加入两次会移动 Rear:$3 \rightarrow 4$,然后 $4 \rightarrow 0$(因为 $(4+1) \bmod 5 = 0$),所以 Rear = 0,存有三个元素。移除两次同样地移动 Front:$3 \rightarrow 4$,然后 $4 \rightarrow 0$,剩下 Front = 0 和一个元素。回绕正是它的意义所在:在线性数组队列中,指针一路走到末端,前面腾出的空间即使队列已空也被浪费掉。记住队列在 Front 端移除、在 Rear 端加入 - 而栈的两端共用一个指针。

定义题按固定的表述给分。把这些记准确。

• 选择正确的数据结构并为它辩护(一个记录用于混合字段,一个 2-D 数组用于网格)。
• 知道如何用一个数组和指针实现一个栈、队列和链表(top;front/rear;next)。
• 区分一个 ADT(它的行为)和它的实现(数组加指针)。

常见错误

• 记录声明没有 ENDTYPE,或字段没有类型。每个字段都是一行带类型的 DECLARE。
• 读过文件末尾,或者在文件必须保留内容时用 WRITE 写。每次读前检验 EOF;要添加就用 APPEND。
• 把数直接写进文本文件而不转换。文件存的是字符串:出去用 NUM_TO_STR,回来用 STR_TO_NUM。
• 忘了检查。Push 和入队先检验是否满;Pop 和出队先检验是否空,而且答案里要写出来。
• 插入节点时丢掉链表的其余部分。先把新节点的指针设为原来的下一个节点,再改前一个节点的指针。
• 线性查找从不报告"未找到"。把位置初始化为 $-1$,循环后检验它。