数据表示

内建类型(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

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

"说明枚举数据类型是什么意思。" 通过(按顺序)列出全部可能的值来定义的非复合用户定义类型。 因为这些值是有序的,它们可以比较和逐个遍历:有了 TYPE Month = (January, February, ..., December),测试 IF ThisMonth > June 是合法的,而且这些值在内部存储为整数。伪代码有三部分,考试各给分:关键字 TYPE、带 = 的标识符、以及括号内用逗号分隔的列表。

例题。 写出伪代码,定义一个枚举类型表示学校开放的日子(周一到周五),并声明一个该类型的变量,设为周三。

TYPE SchoolDay = (Monday, Tuesday, Wednesday, Thursday, Friday)
DECLARE Today : SchoolDay
Today ← Wednesday

枚举类型的变量不能被赋予列表之外的值,这正是要点:Today ← Saturday 是编译时错误,而 STRING 会接受 "Saturdy"。

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^)意味着访问它指向的变量。

"说明指针数据类型是什么意思。" 其值是某给定类型变量的内存地址(引用)的非复合类型。 伪代码用一个位于所指类型之前的脱字符声明该类型,考试要的正是这一行:

TYPE SelectParts = ^Parts        // 指向 Parts 类型值的指针
DECLARE Chosen : SelectParts
Chosen ← ^Keyboard               // Chosen 现在保存 Keyboard 的地址
OUTPUT Chosen^                   // 解引用:存储在该地址的值

指针是动态链表或二叉树(第 19 讲)的构件:每个节点保存指向下一个节点的指针。这里常丢两分:把指针类型写得好像它保存值本身,以及通过指针读取时忘记脱字符。

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

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

"描述用户定义数据类型集合"(三分)。 一种复合类型,容纳同一类型的值的集合,没有特定顺序、没有重复;可以添加和移除值,并可测试某值是否为成员。 用 SET OF 声明类型,然后用括号内的值定义一个集合常量:

TYPE EvenNumbers = SET OF INTEGER
DEFINE Evens (2, 4, 6, 8, 10, 12) : EvenNumbers
TYPE SymbolSet = SET OF CHAR
DEFINE Operators ('+', '-', '*', '/') : SymbolSet

"描述用户定义数据类型记录"(三分)。 由固定数目的字段(项)组成的复合类型,每个字段有自己的标识符和类型,整体用一个标识符引用;字段用点记法访问。

例题。 写出伪代码,声明记录类型 ClubMember,存储俱乐部成员的名、姓、会员编号(整数)、入会日期以及是否已缴费;然后声明一个变量并设置它的两个字段。

TYPE ClubMember
    DECLARE FirstName : STRING
    DECLARE LastName : STRING
    DECLARE Code : INTEGER
    DECLARE DateJoined : DATE
    DECLARE FeesPaid : BOOLEAN
ENDTYPE

DECLARE NewMember : ClubMember
NewMember.LastName ← "Chen"
NewMember.FeesPaid ← TRUE

每个字段需要自己的 DECLARE 行和合适的类型,块以 ENDTYPE 结束,字段(field)以 变量.字段 访问。被要求为每个字段选择类型时,按数据匹配:只用于比较的编号若可含字母则为 STRING,需要算术或排序则为 INTEGER;是/否为 BOOLEAN;日期为 DATE。能取少数几个命名值的字段(宠物的种类、颜色)正是该做成枚举类型的那个。

数组和文件中的记录。 许多成员的表是 DECLARE Members : ARRAY[1:100] OF ClubMember;于是 Members[3].LastName 是一个元素的一个字段,对下标的循环处理每条记录。记录也是写入和读出文件(见下)的自然单位,每次 PUTRECORD 或 WRITEFILE 一条记录。

例题。 复合类型 Pet 存储每只宠物的名字(字符串)、种类(狗、猫、兔、仓鼠之一)和以千克计的体重(实数)。定义这些类型并声明一个变量。

TYPE Species = (Dog, Cat, Rabbit, Hamster)
TYPE Pet
    DECLARE Name : STRING
    DECLARE Kind : Species
    DECLARE Weight : REAL
ENDTYPE
DECLARE MyPet : Pet
MyPet.Kind ← Rabbit

枚举类型要先定义,因为记录要用到它:伪代码里顺序和编译器里一样重要。

伪代码中的类。 类是同时带有行为的复合类型。考试要求写出声明:属性标为 PRIVATE,一个名为 NEW 的构造函数(constructor)设置它们,以及用于获取或修改它们的 PUBLIC 方法:

CLASS Appointment
    PRIVATE PatientName : STRING
    PRIVATE Treatment : STRING
    PRIVATE Medication : STRING
    PUBLIC PROCEDURE NEW(Name : STRING, Treat : STRING, Med : STRING)
        PatientName ← Name
        Treatment ← Treat
        Medication ← Med
    ENDPROCEDURE
    PUBLIC FUNCTION GetTreatment() RETURNS STRING
        RETURN Treatment
    ENDFUNCTION
ENDCLASS

DECLARE Visit : Appointment
Visit ← NEW Appointment("A. Chen", "filling", "none")
OUTPUT Visit.GetTreatment()

属性设为私有,使它们只能通过方法改变(封装,第 20 讲);构造函数是一个名为 NEW、每个属性一个参数的过程;获取器是返回属性的函数。每一项都是单独的一分。

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

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

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

描述每种组织方式(得分的措辞)。 *串行:*记录按加入的顺序一条接一条存储,不按键排序。*顺序:*记录按某个键字段的顺序(已排序)存储。*随机:*每条记录存储在由散列算法从其键计算出的地址处,所以记录没有任何顺序。**比较串行与顺序:**两者都把记录一条接一条存储,都顺序读取,但顺序文件按键有序,所以一旦读到大于目标的键搜索就可以停止,而新记录必须插入到正确位置(通常要重写文件);串行文件则只是追加。

描述每种存取方法。 *顺序存取:*从文件开头开始,一条接一条(按存储顺序)读记录,直到找到所需记录或到达文件末尾。用于串行文件意味着读到匹配为止的每条记录,并要读完整个文件才能确定记录不存在;用于顺序文件时搜索可以提前停止,一旦读到大于目标的键即可。*直接存取:*记录的地址由其键计算得出(用散列算法,或由索引),程序直接到那个位置,不读它前面的记录;这是随机文件以及磁盘上由唯一地址引用的记录所用的存取方法。

选择。 批处理、逐条处理每条记录的工资或公用事业账单主文件适合顺序文件;按发生顺序记录交易的日志适合串行文件;程序运行时按键查找并更新单条记录的库存或客户文件适合用直接存取的随机文件。

伪代码中的文件处理。 考试要求标准语句,试卷 3 出的算法会用到它们:

例题。 随机文件 Stock.dat 保存 StockItem 类型的记录,存储在 ItemID MOD 100 给出的地址处。写出伪代码:若散列地址处为空则存入新条目,否则报告该位置已被占用。

DECLARE Item, Existing : StockItem
DECLARE Address : INTEGER
INPUT Item.ItemID, Item.Description, Item.Quantity
Address ← Item.ItemID MOD 100
OPENFILE "Stock.dat" FOR RANDOM
SEEK "Stock.dat", Address
GETRECORD "Stock.dat", Existing
IF Existing.ItemID = 0 THEN        // 0 表示空位置
    SEEK "Stock.dat", Address
    PUTRECORD "Stock.dat", Item
    OUTPUT "Stored at ", Address
ELSE
    OUTPUT "Position ", Address, " is in use"
ENDIF
CLOSEFILE "Stock.dat"

评分方案检查两个细节:每次 GETRECORD 或 PUTRECORD 之前都要 SEEK(读取会使位置前移,所以写之前要再次定位),以及文件以 FOR RANDOM 打开并在最后关闭。要把随机文件的每条记录复制到另一个文件,就对地址循环,用 SEEK、从一个文件 GETRECORD、向另一个文件 PUTRECORD,跳过空位置。

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

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

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

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

"解释文件存取语境下散列算法是什么意思"(三分)。 对记录的键字段进行的一种计算(函数),产生一个值,该值用作记录在文件中存储的地址(位置),并据此取回记录。 对同一个键做同样的计算总是给出同样的地址,这就是不用搜索也能再次找到记录的原因。

"概述克服冲突的两种方法。" (1) 线性探测(开放寻址):把记录存到计算地址之后的下一个空闲位置,必要时绕回开头;取回时从散列地址开始向前读,直到键匹配。(2) 溢出区(overflow area)或链接法:把冲突的记录存到单独的溢出区(或挂在该地址上的链表),主地址不匹配后再顺序搜索它。两者都得分;存储和取回都要描述。

例题。 一个随机文件有 11 个记录位置,编号 0 到 10,散列算法为 Address ← Key MOD 11。键为 1250、1381、1452、1613 和 1470 的记录按此顺序用线性探测存入。指出每条记录的位置,并描述如何取回键 1470。

$1250 \bmod 11 = 7$;$1381 \bmod 11 = 6$;$1452 \bmod 11 = 0$;$1613 \bmod 11 = 7$,与 1250 冲突,所以 1613 取下一个空闲位置 8;$1470 \bmod 11 = 7$ 再次,位置 7 和 8 已满,所以 1470 到 9。取回 1470:算出 $7$,读位置 7(键 1250,不匹配),读 8(1613,不是),读 9(1470,找到)。若在匹配之前遇到空位置,则记录不在文件中。冲突是小文件的代价:好的散列算法把键均匀分散,而且文件保持远未填满,使探测保持短。

为了存储大小非常不同的实数,计算机用一个浮点(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$)。

考试的格式:补码、尾数和指数

考试给出诸如 10 位尾数和 6 位指数、两者都用补码的格式。尾数的二进制小数点位于其第一位(符号位)之后,所以正尾数是 0.xxxxxxxxx,负尾数是 1.xxxxxxxxx;指数是普通的有符号整数。每次转换都用同样的三步:把尾数读作分数(若以 1 开头则用补码规则),把指数读作整数,乘以 $2^{\text{指数}}$。

例题(二进制到十进制)。 尾数 0101100000,指数 000011。

尾数:$0.101100000_2 = \tfrac{1}{2} + \tfrac{1}{8} + \tfrac{1}{16} = 0.6875$。指数:$000011_2 = 3$。值:$0.6875 \times 2^{3} = 5.5$。

例题(负尾数)。 尾数 1011000000,指数 000010。

尾数以 1 开头,所以为负。它的值是 $-1 + 0.011000000_2 = -1 + (\tfrac{1}{4} + \tfrac{1}{8}) = -0.625$;指数 $= 2$;值 $-0.625 \times 4 = -2.5$。(或者,取尾数的补码 0101000000 $= 0.625$,再加上负号。)负指数如 111110 $= -2$ 则是除:尾数 $0.5$ 配该指数是 $0.5 \times 2^{-2} = 0.125$。

例题(十进制到二进制)。 在 10 位和 6 位的格式中以规格化形式存储 $+6.5$ 和 $-6.5$。

$6.5 = 110.1_2 = 0.1101_2 \times 2^{3}$,所以尾数是 0110100000,指数是 000011。对 $-6.5$,取尾数的补码:1001100000(检验:$-1 + 0.0011_2 = -1 + 0.1875 = -0.8125$,且 $-0.8125 \times 8 = -6.5$),指数 000011 不变。符号决不进入指数;负数有负的尾数。

Normalisation

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

识别和产生规格化形式。 正的规格化尾数以 01 开头;负的以 10 开头。所以 0011000000 不是规格化的(左移一位并把指数减一:0110000000,指数少一)而 1100000000 也不是(左移直到模式为 10...)。尾数每左移一位都必须对应把指数减一,否则值就变了。

"解释为什么数以规格化形式存储"(两分)。 (1) 它对可用的位数给出最大精度(准确度),因为没有位浪费在前导零(或负数的前导一)上;(2) 每个数于是有唯一的表示,所以数可以比较;(3) 它最好地利用了可用的范围。任意两点得分。

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(二进码十进数)而不是浮点。

"描述改变位分配的影响"(三分)。 总位数固定时,增加尾数、减少指数给出更高的精度(precision)(更多有效数字、更小的舍入误差)但更小的范围(range)(能存储的最大和最小量值缩小);增加指数则相反:以精度为代价换更大的范围。两种影响、两个方向都要说。

最大和最小。 在 10 位尾数、6 位指数的格式中,最大正数的尾数为 0111111111($= 1 - 2^{-9}$),指数为 011111($= 31$):约 $2^{31}$。最小的正规格化数尾数为 0100000000($= 0.5$),指数为 100000($= -32$):$0.5 \times 2^{-32} = 2^{-33}$。最负的数尾数为 1000000000($= -1$),指数为 $31$:$-2^{31}$。

"解释溢出和下溢是什么意思。" 当计算结果大于能表示的最大数、指数需要的位数超过它拥有的位数时,发生溢出;当结果小于能表示的最小(非零)数、太接近零以至于指数无法表达时,发生下溢,它被存为零。两者都源于指数的范围,而不是尾数的。

为什么二进制表示只是近似。 二进制分数只能精确表示 $\tfrac{1}{2}, \tfrac{1}{4}, \tfrac{1}{8}, \ldots$ 之和;像 $0.1$ 或 $\tfrac{1}{3}$ 这样的值有无限的二进制展开,而尾数位数固定,所以存储的是能放下的最接近的值。差值就是舍入误差;对一个数它很小,但在重复计算中会累积(把 $0.1$ 加十次可能不恰好得到 $1$),这就是决不应对实数做精确相等测试的原因。

定义题按固定措辞评分。准确学会这些,只给一个答案。

• 伪代码声明逐行评分:枚举用 TYPE ... = (...),指针用 TYPE ... = ^...,集合用 TYPE ... = SET OF ... 再 DEFINE ... (...) : ...,记录用 TYPE ... DECLARE ... ENDTYPE,类用 CLASS ... PRIVATE ... PUBLIC PROCEDURE NEW ... ENDCLASS。
• 按数据匹配类型:固定的命名值用枚举;一组不同字段用记录;唯一值的集合用集合;数据加行为用类;地址用指针。
• 文件组织是记录如何存储;文件存取是如何找到它们。串行和顺序文件顺序读取;随机文件通过键的散列直接存取。对顺序文件的顺序搜索可以提前停止;对串行文件不能。
• 随机文件伪代码:OPENFILE ... FOR RANDOM,每次 GETRECORD 或 PUTRECORD 之前 SEEK,最后 CLOSEFILE。描述散列时要说明冲突如何解决。
• 浮点:尾数作为补码分数(小数点在符号位之后),指数作为整数,乘以 $2^{\text{指数}}$;规格化时左移并把指数减一;尾数买精度,指数买范围。
• 三个"解释"标准答案:为什么规格化(精度、唯一形式、范围)、重新分配位的影响(精度对范围)、为什么 $0.1$ 不能精确存储(有限尾数中的无限二进制分数)。

常见错误

• 新类型写 DECLARE 而不是 TYPE,或漏掉 ENDTYPE;声明集合时没有 SET OF,或枚举值加引号。
• 把浮点数的符号放进指数;符号是尾数的第一位。
• 把负尾数当作原码读;它是补码,所以 1011000000 是 $-0.625$,不是 $-0.375$。
• 规格化时移动尾数而不改指数,或改错方向(左移,指数减)。
• 把随机文件描述成"随机顺序";记录在由键算出的地址处。
• 说顺序存取对顺序文件读"整个文件";遇到更大的键就停止。
• 解释散列时不说算出的值用来做什么(存储和取回记录的地址),或没有处理冲突的方法。
• 把溢出定义为"位数太多"而不是超出最大可表示值的结果,或把它归咎于尾数。