数据表示

内建类型(INTEGER、REAL、STRING、CHAR、BOOLEAN)覆盖最简单的情况。对于更丰富的问题,你可以定义用户定义类型(user-defined types),使代码更清晰、编译器更严格。

Why they are needed

一个内建的 STRING 让你在一个应当只容纳几个合法值之一的字段里存储乱七八糟的东西;一个用户定义类型可以限制它。真实的实体通常是不同类型的值的一个集合。而 DECLARE Taxi : Vehicle 比 DECLARE Taxi : STRING 更清晰(自我说明)。

Non-composite types

Enumerated type

一个枚举类型(enumerated type)的值是一个命名常量的固定列表:

TYPE Vehicle = (M100, M230, T101, T102, T120, T150)
DECLARE MyTaxi : Vehicle
MyTaxi ← T102

这些名称是新类型的值(内部存储为小整数);你不能赋任何列表之外的东西。用途:星期几、颜色、状态码。

Pointer type

一个指针(pointer)容纳另一个变量的内存地址(或 NULL 表示"没有目标")。指针构建动态结构(链表、树)并传递引用而不复制。

TYPE PNode = ^TNode    // pointer to a TNode
DECLARE p : PNode
p ← NEW TNode
p^.Value ← 42          // dereference to reach the fields

解引用(dereference,p^)意味着访问它指向的变量。

Composite types

一个复合类型(composite type,复合数据类型之一)把几个值组合在一个名称下。

• record(记录,主题 10)——一个 TYPE ... ENDTYPE 块中不同类型的字段。
• set(集合)——一个唯一值的无序集合,带操作:添加、移除、成员测试、并集、交集:

DECLARE Available : SET OF Colour
Available ← {Red, Blue}
IF Green IN Available THEN ...

• class(类)/ object(对象)——OOP 复合类型,把数据字段(属性(attributes))与对它们的操作(方法(methods))结合。一个对象是一个类的一个实例:

CLASS Taxi
    PRIVATE Capacity : INTEGER
    PUBLIC FUNCTION GetCapacity() RETURNS INTEGER
        RETURN Capacity
    ENDFUNCTION
ENDCLASS

Choosing a type

对来自一个固定列表的值用枚举,为间接性用指针,为一组字段用记录,为一个无序的唯一集合用集合,而当你需要状态和行为在一起时用类。

文件组织(file organisation)是数据如何布置;文件存取(file access)是程序如何访问一条记录。

• serial file(串行文件)——记录按添加的顺序,没有排序。存取只能是顺序的;追加很快;搜索很慢。用于日志和审计追踪。
• sequential file(顺序文件)——记录按一个键排序。搜索更快(你可以尽早停止或二分查找);插入很慢(记录必须移位)。用于批量更新的主文件。
• random (direct-access) file(随机文件)——记录在从键算出的位置(常用一个散列)。按键的直接存取非常快;按键顺序读取更难。用于大的查找表和客户账户。

两种存取方法是顺序存取(sequential access,从头读到尾)和直接存取(direct access,直接跳到一个已知位置)。把结构匹配到主导操作:单键查找偏向随机;按序报表偏向顺序。

一个散列函数(hash function,一个散列算法)取一个记录键并产生一个存储记录的地址(address)。一个好的散列函数快、确定性(deterministic),并把键均匀地铺开。

$N$ 个槽的常见散列算法:取模散列 address ← key MOD N;折叠(把键拆开、把各部分相加、MOD N);一个字符串散列(把字符码相加、MOD N)。

一个冲突(collision)是当两个键散列到同一个地址时。解决它的三种方式:

要搜索:散列键,读那个槽;若键匹配你就完成了,否则跟随解决策略直到一个匹配或一个空槽。要插入:散列键,写入那个槽或下一个空闲的。保持装填因子(load factor,记录 ÷ 槽)低于约 70% 以获得接近 O(1) 的查找。

为了存储大小非常不同的实数,计算机用一个浮点(floating-point)格式——科学记数法的一个二进制形式,带两个字段:

• 一个尾数(mantissa)——有效数字。
• 一个指数(exponent)——要乘的 2 的幂。

两者都存储为补码(two's complement)整数。值是

把尾数读作一个二进制分数——小数点后第一位值 $1/2$,下一位 $1/4$,然后 $1/8$,如此等等。所以 0.1010000 是 $1/2 + 1/8 = 0.625$;带指数 00000010(= 2)值是 $0.625 \times 2^{2} = 2.5$。

Converting

• 二进制 → 十进制:把尾数(若为负用补码规则)读作一个分数,把指数读作一个有符号整数,然后把尾数乘以 $2^{\text{exponent}}$。
• 十进制 → 二进制:把数写成一个二进制分数 × 一个 2 的幂,然后把尾数和指数存储为约定的格式。

例题。 一个数有尾数 10110000 和指数 00000011。求它的十进制值。

指数 00000011 是 $+3$。尾数以一个 1 开始,所以它是负的。在补码中读作 1.0110000,符号位值 $-1$,分数位加上 $\tfrac{1}{4} + \tfrac{1}{8} = 0.375$,所以尾数是 $-1 + 0.375 = -0.625$。于是

例题。 在这个格式中存储 $+2.5$。

在二进制中 $2.5 = 10.1$。写成一个规格化的分数,$2.5 = 0.101 \times 2^{2}$。所以尾数是 01010000(符号位 0,然后 .101)而指数是 00000010($= 2$)。

Normalisation

一个数在它的第一个有效位紧跟在二进制小数点之后时是规格化的(normalised,没有浪费的前导零)。这最大化精度,因为每个尾数位都携带信息。要规格化,把尾数左移并减小指数(或右移并增大它),直到第一个有效位就位;值不变。对负(补码)尾数,符号位(1)之后紧跟一个 0。

Approximation and rounding errors

许多十进制实数不能在二进制中被精确存储——例如 $0.1_{10}$ 是循环二进制分数 $0.000110011\ldots_{2}$,它必须被截断。后果:

• 舍入误差(rounding errors)在许多操作上累积(0.1 + 0.2 不精确地是 0.3)。
• 比较失败——测试 ABS(x - 0.3) < 1e-9 而不是 x = 0.3。
• 两个几乎相等的值相减会损失精度。
• 当指数用尽范围时,溢出(overflow,一个对指数范围太大的结果)和下溢(underflow,一个太小的结果,舍入为零)发生。

对于精确的需要(货币),用定点(fixed-point)或 BCD(二进码十进数)而不是浮点。

• 对于浮点二进制 → 十进制,把尾数读作一个分数、把指数读作一个有符号整数,然后相乘;一个负尾数遵循补码规则。
• 通过移位直到小数点后第一位与符号位不同来规格化——这最大化精度。
• 解释舍入、溢出和下溢误差以及为什么 $0.1$ 不能被精确存储。
• 比较文件组织(串行、顺序、直接)以及散列如何快速找到一条记录。