数据类型与数据结构

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

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

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

一个记录(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

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

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

• 元素(element)——数组中的一项。
• 边界(bounds)——最低和最高的有效索引。
• 维度(dimension)——1-D(一个列表)、2-D(一个表格),等等。

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)把一个数组排序:扫过它,比较每个相邻对,并交换任何顺序错误的;重复各趟直到某一趟不再有交换。

一个文件(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"

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

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

Stack

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

Queue

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

Linked list

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

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。

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

例如,当 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)。要删除:解开该节点的链接并把它的槽还给空闲列表。这给出一个链式结构的灵活性和一个数组的静态分配。

例题。 一个循环队列存放在大小为 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(它的行为)和它的实现(数组加指针)。