2.12 实现模型
这一节将讨论数据对象的实现模型。因为在计算机内对数据结构的表示依赖于硬件，所以我们提出的模型仅仅是原理性的，只给出简单易懂的表示，并未考虑实现方法的有效性。这里给出的模型并不是独立于语言的，重点给出Pascal语言的例子，仅供参考。
在实现模型中，一个数据用描述符和数据对象来表示，而不使用实际的数据结构。数据对象的所有属性的集合用描述符来描述。通常，在编译时将所有描述符保存在一张表中，以便编译时随时使用。有些描述符需要保存到运行阶段，而且存储在描述符中的属性可能随运行而变化。描述符的格式高度依赖于编译时表的总体结构，这里所列出的描述符仅仅是功能性的。
2.12.1 内部类型和用户定义的非结构类型实现模型
对大多数计算机来说，硬件以定点和浮点算术运算来支持整型和实型数据的处理。通常，整型和实型数据的表示如图2-8和图2-9所示。
图2-8 整型变量的表示
图2-9 实型变量的表示
子界中值的表示与它的基类型表示一样，所以它们之间值的传递不需要任何转换，只需在运行时检查是否越界。子界的描述符必须包含子界的界值，这个值在运行时用来做越界检查。
枚举类型t的值映像到整数0～(n-1)，其中n是t的基数。若所有运行时的访问都经过包含类型t的信息描述符，那么，这个映像就不会引起类型t的值与其他枚举类型值的混淆。
布尔型和字符型数据可以看成枚举类型，并按上述方法实现。为了节省存储空间，字符可能存储在比字小的存储单元中，若硬件直接按字节编址，显然字符可存储在字节中。也可能把同一程序单元的几个布尔说明压缩到同一存储单元(字或字节)中，用每一个特定位表示一个布尔值。在这种情况下，访问单个布尔值就相当于访问字(或字节)的某一位，因为机器没有位地址，所以执行效率很低。
2.12.2 结构类型实现模型
1.笛卡儿积
笛卡儿积(Pascal的记录)类型的数据对象的标准表示是成分的顺序排列，描述符包含类型名和一个三元式(选择符名，域类型，指针)，其中指针指向数据对象，每个域都对应一个三元式。例如，Pascal记录的类型说明
type t = record a ：real；
b ：integer
end
的表示如图2-10所示。
图2-10 Pascal记录的表示
笛卡儿积的每个成分占用整数个可编址的存储单元(字或字节)，在程序内通过给定的域名进行引用。域名不能用作变量的值，因此，在强类型语言中，笛卡儿积的描述符不需要保留到运行。对每个域的引用都是由编译器局部于程序单元并计算出它在活动记录中的位移。这里是针对Pascal记录而言的，若记录的成分包含动态数组，处理起来就要复杂得多。
在Pascal语言中，可用显式说明packed更有效地选择使用存储单元。此时，可以把几个成分压缩到一个可编址的存储单元中。例如
packed record a：char；
b：0..7
end
中的变量可由一个字的2个字节来表示。
2.有限映像
有限映像(Pascal的数组)的传统表示是为每一成分分配整数个可编址的存储单元(例如字)。描述符包含有限映像的类型名、定义域类型的基类型名、界的值、界类型名、存储每个元素所需的存储单元个数(如几个字)和存储数据对象的存储区的首地址。例如，Pascal的数组说明
type a = array[0..10]of real
的表示如图2-11所示。
图2-11 Pascal数组的表示
因为数组的引用通常用下标变量来索引，所以描述符中的界需要保留到运行，以便运行时执行越界检查。
对a[i]的引用计算从数组首地址到a[i]的位移，但这里仅计算在该程序单元的活动记录内局部于数组的地址，实际地址尚需进一步计算和实现。若定义域类型是子界m..n，每个元素所占存储单元个数是k，那么，按照k*(i-m)计算a[i]从首地址b到所分配的存储之间的位移。对a[i]的引用可以写成
b+k*(i-m)= b-k*m+k*i = b'+ k*i
其中，b'= b-k*m是编译时能计算出的数值。
有的语言支持动态数组，这时，描述符中某些属性要到运行时才能决定。此时，可将描述符分成静态部分和动态部分。静态部分只包含编译时所需信息(例如数组成分的类型和对动态部分的引用)；动态部分在运行时分配到单元活动记录中，它在活动记录内的位移在编译时就能确定。动态部分包含对数组数据对象的引用，即指向这个对象的指针(该对象通常只能在运行时计算)和界的值。任何对数组元素的访问都编译成通过动态描述符的间接地址。
3.序列
字符序列(串)和在后备存储器上的记录序列(文件)的表示方法是不同的，它们(特别是文件)依赖于语言的语义和机器体系结构。Pascal语言的串类似于压缩字符数组，因此，它的长度是静态确定的，且不能改变。在Ada语言中，串类似于动态字符数组，因此，它的长度通常在编译时不能确定。在运行时，进入串所在的程序单元之后，当串变量被说明时其长度才能确定。在这两种语言中，串都可由别的数组表示。
在其他语言(例如SNOBOL 4和ALGOL 68)中，串可以任意改变其长度，没有对程序员规定界限。显然，这样的串是动态的，必须分配在堆上。图2-12说明了一个长度为5的可变长串的表示。它的描述符分成静态和动态两部分，动态部分分配在活动记录栈上，包含当前的串长度(用于动态检查)及指向串在堆上的存储区的指针。分配在堆上的串是字的链表，每个字包含一个或多个字符。存储在一个字中的字符个数取决于字长。图2-12中假定每个字包含两个字符。
图2-12 可变长串的表示
4.判定或
判定或(Pascal的变体记录)类型的变量并不限制在任何特定的变体中，可随赋值结果而变化。因此，为这种变量分配的存储空间应足以容纳需要最大空间变体的值。Ada语言提供了将一个变量绑定于一个特定变体的选择。此时分配的存储空间量恰恰是每个变体所需要的。
Pascal记录说明
type v = record a ：integer；
case b ：boolean of
true：(c ：integer)；
false：(d ：integer；
e ：real)
end
中的判定或类型变量的表示如图2-13所示。
标识符域的描述符有一个表项指向case表，对每一可能的标识符值，case表都有一个表项指向有关变体的描述符。
5.幂集
对幂集可以通过提供可访问的存储空间(如机器字)来有效地实现。机器字至少要有足够的位数来表示可能的成员，即基类型的元素个数。若在某个集合S中出现基类型的第i个元素，那么与S相关联的字的第i个位置为“1”。若与某集合S相关联的字的所有位都为“0”，那么表示S是一个空集。两个集合的联合很容易通过它们相关联的字的“或”操作来实现，交集通过“与”操作来实现。
若机器不允许位访问，为了测试一个成员，就得对字进行移位，把所要求的位移到可访问的位置(如符号位)，或者使用屏蔽码。这种表示幂集的方法所能表示的集合个数，将受到该集合基数的限制，这种限制通常等于一个机器字的位数。
6.指针
指针变量的值绑定于它的类型对象的绝对地址上。其类型描述体现在指针描述符中。若指针值为nil，可由一个特定地址值来表示，这个值实际上是硬件产生的一个错误陷阱，以便捕捉经由值为nil的指针产生的错误引用。例如，这个值可以是一个超出物理地址空间且指向保护区的一个地址。
指针变量分配在活动记录栈上，而它指向的数据对象分配在堆上。
7.层次结构数据结构对象的表示
通常，用任意复杂的结构来聚合非结构类型可以形成结构类型。因此，结构类型变量的描述符可以组成一棵树，并用子树来描述它的每一成分类型。例如，类型t的数据对象说明
如下：
type t = record a ：real；
b ：tl；
c ：integer
end；
其中
tl = array[0..3]of integer；
可表示如图2-14所示。
图2-14 层次结构的数据对象的表示(1)
类似地，二维数组变量的类型说明
其中
type t2 = array[0..2]of t4；
t4 = array[0..5]of integer；
的表示如图2-15所示。
图2-15 层次结构的数据对象的表示(2 )
类型t2的一个数组的成分类型是t4，它的每个成分由6个连续存放的整数值表示。数组的每个基本成分的下标由(i，j)表示，其中i是属于子界0..2的值，它选取一个类型为t4的成分；j是属于子界0..5的值，它选取该成分内的一个整数。若b是数组在它的活动记录内的起始地址，那么，由表达式b+6*i+j给出对数组基本成分的引用。
关于类和抽象数据类型的表示，已超出本书的范围，此处不再深入讨论。