第四章
数 据 类 型
?任何程序, 不管以何种语言写成, 均可以视为刻划了一个操
作集合 。 并将以一定顺序作用到一定数据上 。
?语言的基本不同在于：允许的数据类型, 允许的操作类型,
以及控制操作顺序的机制 。
?下面章节将围绕这些方面展开 。
4.1 类型和对象的性质
数据对象、变量和常量
?计算机的数据存储在结构上是简单的, 通常是由位串构成的
字节 。
?而语言虚拟机的数据存储则有更复杂的组织, 如：数组, 栈,
数, 字符串, 以及其它存在于程序执行中不同点的数据 。
?我们称虚拟机上一个或多个数据片断运行时的组合为数据对
象 。
?在程序运行中, 存在许多不同类型的不同数据对象 。 这些对
象及其相互关系在运行时动态变化 。
?有些数据对象是程序员定义的, 如变量, 常量, 数组, 文件
等 。 程序员通过声明和语句显式地创建和操作它们 。
?有些数据对象是系统定义的，不可为程序员直接访问。如：
运行时存储栈、子程序激活记录、文件缓冲、自由空间列
表等。这些数据对象在运行需要时自动产生，不需要时删
除。
?数据对象表示了数据值的一个容器，是值被存放和检索的
地方，而数据值是在存储器中以一种特定的位模式表示。
?数据对象和数据值在大多数语言中均是明确区分的，如图
4.1所示。
?每个数据对象有生命期，在生命期内可用来存放数据值。
?数据对象可分为简单数据对象和数据结构 ——其他数据对
象的聚集。
?数据对象在其生命期中涉及各种绑定，虽然其属性不变，
但绑定可动态改变。
?重要的属性和绑定有,
1,类型
通常在程序翻译时, 关联数据对象和它可能的取值集合 。
2,位置
通常不由程序员规定, 而是系统存储管理负责 。
3,值
由赋值操作完成绑定 。
4,名
通常在声明时完成绑定, 但可被子程序调用和返回修改
5,部件
通常用指针值相连, 可通过指针的修改而变动 。
?变量和常量
程序员通过变量显式地定义和命名数据对象 。
一个简单的变量是有名字的简单数据对象, 通过赋值修
改变量值 。
常量是具有名字的数据对象, 其值在其生命期内永久不
变 。 一个文字 （ 或文字常量 ） 是一个常量, 其名是其值
的书写表示, 如 21表示值为 21的整数常量 。
程序员定义的常量 ——其名字由程序员指定 。
常量的绑定由编译器完成 。
如 C语言中, #define MAX 20
语句 MAX=4是非法的 。
?永久性 Persistence
现今大多数程序仍是采用批处理模式, 即
1,将程序装入内存
2,适当的外部数据被准备给程序所用 。
3,将相关输入数据读入程序中变量, 变量被操作,
然后结果数据被写回外部数据格式 。
4,程序终止 。
程序中变量的生命期由程序的执行时间所确定 。 然而,
数据的生命期经常超出程序的单次执行, 这种数据称
为永久的, 在程序的多次执行间存在 。
具有永久特性的语言对书写基于事务的系统更为高效 。
文件系统可以解决永久性问题 。
数据类型
?一个数据类型是一类数据对象加上创建及操作它们的一组
操作。
?每个语言有一个基本数据类型集合，是语言固有的。
有的语言还提供了设施允许程序员定义新数据类型。
有的新语言还允许类型本身被语言操作（高阶能力）。
?数据类型的规约包括,
1、区分该类型的数据对象的属性
2、该类型数据对象可具有的值
3、定义该类型数据对象可能处理的操作
?例如：数组数据类型的规约
属性：维数、每维的下标范围、元素的数据类型等。
值：形成数值元素有效值的数的集合。
操作：选择个体数组元素、创建数组、改变数组形状，
访问下标上下界、完成数组间的算术操作等。
?数据类型的实现包括,
1、存储表示：用于在计算机存储器中表示数据对象。
2、数据类型操作被以特殊的算法或过程表示的方式，
这些算法和过程操纵数据对象的存储表示。
?数据类型的规约大致可对应虚拟机中该类型定义部分的规
约。而数据类型的实现定义了那些虚拟机部分基于更基本
的低层结构的仿真，低层结构可以直接是硬件，也可以是
有操作系统或微代码定义的软、硬件组合。
?从语法表示来看, 规约和实现大部分独立于特定的语法形
式 。
属性：表示为声明或类型定义
值：表示为文字或定义的常量
操作：可由特殊的符号, 固有过程或函数, 或隐含地通
过其他语言元素的特殊组合来调用 。
?特定的语法表示并没什么不同, 但程序语法中提供的信息
被用于确定各种属性的绑定时间, 从而允许翻译器建立高
效的存储表示或完成类型检查 。
基本 （ 简单 ） 数据类型的规约
简单数据对象包含单个数据值, 这类数据对象称为基本数
据类型 。
虽然不同的语言有不同的基本类型集合, 但整数, 实数,
字符, 布尔, 枚举, 指针等基本都是有的 。 但各自精确的
规约对不同语言会有差异 。
?属性
对象的基本属性 （ 如类型和名字 ） 通常在生命期中是不
变的 。
有的属性可存放在描述子中, 作为数据对象的一部分在
运行时出现 。
有的属性只用于确定其存储表示, 在执行中不显式地出
现 。
属性值和数据对象的值是不同的 。
?值
数据对象的类型确定了它可包含的可能值集，但在执行
中任一点，只包含一个来自该集合的单值。
基本数据类型定义的值集通常是有序集，有最小值和最
大值。
?操作
确定数据对象被处理的方式。操作可能是原操作，也可
是用户定义操作，本章强调语言固有的原操作。
操作是一个数学函数，对一给定输入参数，有定义的、
唯一确定的结果。每个操作有作用域，值域。操作的动
作定义了对给定参数的结果。
算法可用于刻划操作的动作，但其他规约也是可以的。
如可用乘法表来刻划乘法的动作。
操作的基调（ signature） ——定义了操作的作用域中参
数的数量、顺序和类型，以及结果值域的顺序和类型。
数学记号,
OP,type1× type2× …typen ?type—也称为函数原形
操作有单元、二元和多元。
动作的精确规约需要比参数类型更多的信息。
特别地，参数类型的存储表示通常确定那些参数如何
被操作，如：二进制数的乘法和 10进制数的乘法有很
大不同。
这样，在操作的规约中，常给出动作的非形式的描述。
一旦参数的存储表示确定，动作的精确规约是操作实现
的一部分。
有时难于确定操作的精确规约为数学函数，有四个主要
因素。
1、操作对某些输入无定义。
2、隐含的参数 ——操作会访问其他隐含参数（全局
变量；非局部变量）。
3、副作用（隐含结果） ——可能修改其他数据对象。
4、自我修改（历史敏感性） ——操作修改自己的内
部结构、或是执行中保持的局部数据、或是代码。
操作的结果还依赖于历史调用。
例：随机数产生器。
LISP中可自我修改代码。
?子类型
指一个类型是某大类的一部分（子类型 ——超类型）
如,PSCAL中的子域机制,OO中的继承机制。
但从理论角度看，子类型有严格定义,
凡是超类型对象可存在的地方（可承受的操作），
子类型对象同样适用，子类型对象继承超类型对象
的行为。
基本数据类型的实现
?存储表示
基本类型的存储受低层计算机的影响很大。
如：整数或实数几乎就是在低层硬件中使用的数的
整数或浮点数表示。
对字符值，硬件或 OS字符码被使用。
基本理由,
如使用硬件存储表示，则该类型数据基本操作可以
用硬件提供的基本操作实现。
否则，将使用软件仿真，从而带来效率损失。
基本数据类型的属性被类似地处理。
1、为了效率，很多语言设计为属性由编译器确定。
属性本身并不存放在运行时存储表示中 ——存储表示
通常直接使用硬件，如,C,Fortran,Pascal等。
2、数据对象的属性可存放在描述子中作为运行时数
据对象的一部分，如,LISP,Prolog等，这里灵活性
是主要目标。通常硬件不提供对描述子的直接表示。
数据对象的表示通常独立于存储位置，这样给定类型的
每个对象有相同的表示（除位置不同），通常用需要的
内存块的尺寸（大小）来描述，同时也涉及属性和值在
块中的布局。
通常内存块的每一个字或字节的地址用于表示数据对象
的位置。
?操作的实现
1、直接作为硬件操作
如：整数表示为硬件整数,+，－也直接用硬件实现。
2、作为过程或函数子程序
如：平方根操作。
如数据对象不使用硬件表示，则所有操作必须是软
件仿真，通常以子程序的形式。
3、作为 In-line（内嵌）代码序列。
这也是操作的软件实现形式，但不是使用短小的子程序，
而是将子程序中操作代码拷贝到程序中的调用点。
如 P118下部的例子，绝对值函数的实现。
声明
编写程序时，程序员确定数据对象的名字和类型。还要确
定：生命期、在程序中的活动范围、相关操作等。
声明：一种程序语句，告知语言翻译器关于数据对象的信
息。
如声明语句放在特定的程序或类定义中，则指明了对象
希望的生命期。
声明可以是显式的，也可以是隐含的或缺省的。声明可以
为数据对象赋上初始值，也可指定常量值。
?操作的声明
翻译时需要的关于操作的信息，主要是其基调 signature。
对基本操作，不需显式的参数类型和结果类型声明，是
语言中固有的。
对程序员定义的操作，则必须指定之。
如,sub,int× float→float ＝ >float Sub (int x,float y)
?声明的目的
1、选择存储表示
声明可以给语言翻译器提供关于数据类型和数据对象属
性的信息，使得翻译器可以确定数据对象的最佳的存储
表示，从而减少整体的存储需求和被翻译程序的执行时
间。
2、存储管理 ——声明使其更为高效
声明可以提供关于数据对象生命期的信息，从而使得在
程序执行过程中进行更高效的存储管理。
如：在 C语言中，在子程序头部声明的数据对象有相同
的生命期，这样可以在进入子程序时分配一个整体的块
来存放所有的数据对象，而在退出子程序时释放。
其它动态创建的数据对象则需单独处理。
3、多态操作 ——包括重载和真正多态
大多数语言均使用特殊的符号来表示一组不同的操作，
具体操作的选择将依赖于参数的数据类型。此即所谓重
载。如：＋可以是整数加、实数加，甚至可用于字符和
字符串操作。
重载是一个在语法层次上处理的概念。有编译器处理。
真正的多态通常是语义级别的概念，操作符的具体动作
的确定是在运行时进行。如：函数语言中，类型可以作
为参数带入，从而使函数的动作的选择依据类型实参而
确定。恒等函数就是典型的多态。
面向对象的继承机制也提供了所谓的包含多态性，即子
类的对象可用于父类对象出现的地方。
4、类型检查 ——最重要的目标，属语义检查，目标是
排错，分静态或动态类型检查。类型检查提供了很好的
防止错误的机制。
类型检查和类型转换
计算机硬件固有的数据存储表示通常不含类型信息。数据
上的基本原操作也不需类型检查。如一个位串,
111001……0011
可能是整数、实数、字符串、或指令，没有办法来区分。
硬件提供的基本操作（如加法），不能检查其参数是否为
整数，他们仅仅是位串。
汇编语言或机器语言编程中常见的错误源于错误的操作类
型，这种错误难于发现，因为操作并不以明显的方式失败。
操作可进行，但结果没有意义。
有时这种错误可在连续的一串操作后出错，有时程序停
止也不出错。
类型检查：指检查程序中每个操作均接收了正确数目的正
确类型参数，可在运行时完成，即动态类型检查；或编译
时检查，即静态类型检查。
高级语言的主要优点之一：可提供对所有（或几乎所有）
操作的类型检查。
动态类型检查：需类型标志，不需对变量声明（即变量是
无类型的）。
优点：编程的灵活性。程序员不需考虑类型问题，具有
较高灵活性。
缺点,
程序难于调试，不能完全消去所有参数类型错误。
程序测试不可能检测所有的路径。
需要在执行过程中保持类型信息，需存储空间。
动态检查需以软件实现，有时间花销。
静态类型检查：需要的信息通常由程序员在声明中及在其他
语言结构中提供。需要,
1、对每个操作，其参数的数量、顺序、类型及结果类型。
2、对每个变量，被关联的命名数据对象的类型。
3、每个常量数据对象的类型。
编译器在翻译的早期阶段收集声明中的类型信息，以后将用
于类型检查。
静态检查将针对程序中的所有操作进行，所有可能的执行路
径均被检查。因此，关于类型错误的进一步测试是不需要的，
因而不需类型标记和运行时类型检查。
静态检查涉及语言的多个方面：声明、数据控制结构、分别
编译等。
在多数语言中，对某些语言结构的静态检查在某种情况下是
不可能的。解决方案,
采用动态类型检查或不检查。
?强类型
如果我们可以静态地检测程序中的所有类型错误，则称
语言是强赋类型的。
通常类型为程序提供了一个安全层次。
一个函数 f,S→R 称为类型安全的，如果 f的执行不会
产生 R以外的值。
类型安全的操作均不需动态检查。
很少有语言是真正强类型的。
?类型推导
如果解释不会出现二义性，则类型声明可以省去。可由
语言实现推导出失去的类型信息。
?类型转换和强制
如果在类型检查中，参数的实际类型和操作期望的类型
间出现不匹配，则有两种处理方案,
1、指出出错
2、通过强制（隐式的类型转换）来改变实际参数的
类型为正确类型。
类型转换的基调为,
conversion-op, type1→type2
将一个对象变为另一类型的对象。
大多数语言以两种方式提供类型转换,
1、作为固有函数，程序员可显式地调用。
如：将实数变成整数,Pascal中的 round,C中的
(int) x
2、作为强制，自动在类型失配时调用。
如：整数和实数间相加，总是先将整数转变为实数。
强制的基本原则是不失信息。
这类强制称为 widenings或 promotion。
如强制会丢失信息，则称为变窄（ narrowing）
类型转换可能需要数据对象在运行时存储表示的改变，
如,COBOL和 PL/1中，数值以字符串方式存放，要相加
需先转换，结果又要转换为字符串。
有的语言中不提供类型强制，类型不匹配即被视为出错。
而有的语言则尽可能在不匹配时采用强制（如 C）。
赋值和初始化
?赋值是一基本操作，改变值到数据对象的绑定，这个改变
是操作的副作用。
?有的语言中，赋值语句也返回值（作为表达式处理），该
返回值包含被赋值拷贝的数据对象。
?Pascal中，赋值的规约为,
Assignment (:=), integer1× integer2→void,
integer2值赋给 integer1无显式返回 。
?C中, 规约为,
Assignment (=), integer1× integer2→integer 3
integer2值的拷贝赋给 integer1,
同时创建并返回包含 integer2值的新数据对象 integer3,
?考虑赋值 X,=X
右边的 X称右端值，用于引用包含在命名数据对象中的
值,r-值。
左边的 X用于引用将包含新值的数据对象的位置，称为
左值,l-值。
?赋值操作定义为,
1、计算第一个操作数表达式的左值。
2、计算第二个操作数表达式的右值。
3、将右值赋给左值对象。
4、返回右值作为操作的结果。
?赋值的两个不同视角,
?相等和等价
考虑 Zark语言中赋值,
A←2+3
有两种解释,
计值表达式 2+3，将其等价值 5赋给 A；
将操作 2+3赋给 A。
如有静态类型检查,A的类型决定赋值的语义。但对动态
类型语言，两种语义均是可能的。
这种情形在 Prolog中,is表示赋等价的值,=表示赋模式，
相等性由被赋值变量的当前值决定。
X is 2+3，则 X=5为真
X=2+3，则 X=5为假
?初始化
未初始化变量（或未初始化数据对象）是一个数据对象，
已被创建，但未赋值，即有 l-值，但没有 r-值。
创建对象仅涉及存储块的分配，块中原有位模式不会改
变。
有的语言创建时不需初始化，初始化是在以后显式地通
过赋值进行的。也可以在变量声明时进行显式的初始化
工作，此时，需要编译器产生相应的赋值代码并插入到
目标程序中。
在变量声明后立即进行初始化工作是程序员应有的良好
习惯之一。
有的语言，创建时自动初始化（隐式初始化）。
未初始化变量是程序错误的重要原因之一。
4.2 基本数据类型
数值数据类型
几乎任何语言均提供数值数据类型。其中，整数和实数是最
常见的，它们通常直接由计算机硬件支持。
1、整数
规约,整数类型的对象除了其类型外，通常没有其它属性。
该类型的整数值的集合形成了数学中研究的无限整数集的一
个在有限界内的有序子集。
最大整数值有时被表示为一个定义的常量，如,PASCAL中
的 maxint，其实际值由语言实现者根据具体的计算机硬件确
定。
C语言有四种不同的整数规约,int,short,long,char。
整数数据对象上的操作,
算术操作：二元算术操作的规约为,
BinOp, integer × integer － > integer
二元操作包括：＋、－,×, /,mod等。
一元算术操作的规约为,UnaryOp, integer－ > integer
一元操作有：－、＋、以及其它，如：绝对值。
关系操作,
RelOp, integer × integer － > Boolean
关系操作有：大于、小于、相等、不等、等等
赋值,
assignment, integer × integer － > void
assignment, integer × integer － > integer
位操作：也分二元和一元。如,&,|,<<（移位）等。
实现,语言定义的整数数据类型经常使用硬件定义的整数存
储表示和硬件提供的算术及关系操作来实现。通常使用一个
完整的字来存储一个整数。
三种可能的整数存储表示,
需声明及静态类型检查,
如 C,FORTRAN等语言
仍可使用硬件提供的
算术操作
省空间,
但需附加的操作处理
2、子域
规约：整数数据类型的子域是整数类型的子类型，包含一个
在限制范围内的整数序列。子域类型允许和一般整数类型相
同的操作集。
实现：子域类型对实现有两个重要影响,
更小的存储需求：可以用较少的位来存储子域。如：
1..10子域只需要四为存储表示，而完整的整数可能需 8、
16,32位或更多。但是，由于算术操作的限制，子域通
常表示为最小的有硬件实现算术操作的位数，通常为 8或
16。
更好的类型检查：声明某变量为子域对象可以允许更精
确的类型检查。如,month声明为 1..12，则,
month,= 0 将为非法操作。（可编译时检查）
有的子域检查不能在编译时进行，如,
month,= month + 1
3、浮点实数
规约：通常规约为单个类型属性 real或 float，形成一个从硬
件确定的最小负数到最大数的有序序列，但其值不是均匀地
散布在这个范围内。
此外，有的语言中，浮点数所需精度，即其所用的十进制位
数，可由程序员来确定。
实数具有和整数相同的算术、关系和赋值操作，但布尔操作
有时会受限。由于进位的关系，实数间的相等是很难达到的，
因此使用实数相等为判定条件必须慎重。
此外，大多数语言提供一些固有函数作为实数上的其它操作,
Sin, real － > real
Max,real × real － > real
实现：浮点实数的存储表示通常基于底层的硬件表示，其中
存储位置被分为尾数和指数。在大多数语言实现,IEEE 标
准 754被用为浮点数定义的标准。
有单精度和双精度浮点数之分。二者通常由硬件算术操作支
持其加、减、乘、除，而求幂操作通常由软件仿真。
如果同时支持单精度和双精度，则必须给予程序员相应的声
明机制。
4、定点实数
规约：大多数硬件包含了整数和浮点数对象，然而，有很多
应用需要特定的有理数，如：表示钱的元和分的数据对象。
这些数不能写成整数或浮点数。因此，需要定点数。
定点数表示为固定长度的数位，在给定位置为小数点。如，
COBOL语言中，有如下声明,
X PICTURE 999V99
实现：定点实数可直接由硬件支持或用软件仿真。如 PL/1中,
DECLARE X FIXED DECIMAL （ 10,3）,
Y FIXED DECIMAL（ 10,2）,
Z FIXED DECIMAL（ 10,2）；
X为带 3个小数位的十位十进制数,Y和 Z有两个小数位。 X的
比例因子 SF为 3,Y和 Z为 2。
value(X) = rvalue(X) × 10-SF
即,X值为 103.421，其右值为 103421。
考虑语句,Z ＝ X ＋ Y
实际加法的代码为,Z ＝ （ X ＋ 10× Y） / 10
考虑 X × Y，则,
积 ＝ rvalue(X) × rvalue(Y)
SF = SF(X) + SF(Y)
5、其它数据类型
复数,
复数包含一对数，分别表示数的实部和虚部。可以通过将数
据对象表示为两个存储位置构成的块（存放一对实数）来表
示复数。操作则通过软件仿真，这是不可能用硬件操作来实
现的。
有理数,
有理数是两个整数的商。引入有理数类型的原因是为了避免
实数的浮点和定点表示中的舍入问题。可以将有理数表示为
不限长的整数对。此时，长整数是用链接来表示的。
实数 1.5的不同表示,
枚举类型
我们通常希望一个变量只在一组符号值中选一值。如：变量
StudentClass只有四种可能值,freshman,sophomore,junior,和
senior。当然，可以用整数来代表这四者，但必须由程序员
来维护这类变量的操作安全性及使用的类型正确性。
规约：枚举是一个不同值的有序列表，由程序员确定其文字
名及它们的顺序。如 C中,
Emun StudentClass {Fresh,Soph,Junior,Senior};
Emun EmploySex {Male,Female};
枚举类型的基本操作为关系操作、赋值，以及后继和前驱。
实现：枚举类型数据对象的存储表示是直接的，在枚举序列
中的每个值在运行时被表示为整数，通常为 0,1,2,… 之
一。有的语言也可由程序员指定值。枚举类型上的操作的实
现也是直接的，直接使用硬件提供的基本操作。
布尔类型
大多数语言提供数据类型表示 true和 false，通常称为布尔或
逻辑类型。
规约：布尔类型的数据对象取二值之一。在某些语言中，可
将其考虑为语言定义的枚举类型。
Type Boolean = (false,true);
其顺序为 false < true。
布尔类型对象上的操作为一般的逻辑操作。
实现：布尔数据对象的存储表示是一个二进制位。通常，为
了可以直接访问，而表示为单个可编址单元。
用一个特殊位来表示,0为假,1为真。
或者,0为假，其余非零值为真。
也有其它数据类型可用于布尔型的表示，而 C中没有布尔型。
字符类型
大多数数据以字符形式输入和输出，有的被转换为其它数据
类型，但有的需要被直接以字符形式处理。字符类型也可以
作为字符串类型的基础。
规约：字符类型对象取单个字符为其值。可能的字符的集合
通常是对应于底层硬件支持的标准字符集的语言定义的枚举，
如 ASCII字符集。在该集合中的字符的顺序称为字符集的
collating顺序（比较顺序）。字符上的操作有关系操作、赋
值、以及字符测试等。
实现：字符数据值几乎都是硬件和操作系统直接支持的。通
常语言使用相同的存储表示。但在某些情形，语言也定义了
一些底层所不支持的特殊字符。在此情形下，需要提供相应
的转换规则和特殊的关系操作实现。
国际化
字符类型虽然看上去简单, 但在今天的语言设计中变得日益
重要 。 世界经济的全球化和对全世界通讯的计算机需要, 需
要计算机, 记, 多种语言 。 只用 8位的 ASCII字符是不够的,
从而出现国际化需求 （ I18N） 。
?Collating序列
排序 （ 分类 ）,非罗马字符的位置无统一定义, 在不同
国家有不同解释 。
大小写：有的语言不分大小写 。
扫描方向：不一定全是从左到右 。
?国家特定的日期格式：美 11/26/95,英 26/11/95等 。
?国家特定的时间格式,5:40pm(美 ),17:40(日 ),17.40(德 )，
17h40(法 )等。
?时区
?Ideographic systems，大字符集对日、中等是需要的。
?现金符号,$,￡,￥等。
4.3 结构数据类型
数据结构 ——包含其他数据对象作为元素或部件的数据对象。
结构数据对象和数据类型
结构数据对象 ——一组其他数据对象构成的聚集, 这些数据
对象称为元素或部件, 可以是基本类型, 也可以是结构 。
很多和数据结构相关的问题和概念与基本类型数据是相同的,
但数据结构更为复杂 。
数据结构类型也涉及类型规约和类型实现, 只是更为复杂 。
两个方面是特别重要的,
结构信息的规约和实现变成了中心问题, 用于指出部件
对象及其间关系, 以便于部件的直接选取 。
结构上的很多操作带来的存储管理问题 。
数据结构类型的规约
?规约的主要属性包括,
1、部件数量
结构的部件数量可能是固定的，在其生命期中不变，如：
数组、记录等。
也可能是变长的，数量可以动态变化，如：栈、列表、
集合、文件、表格等。
变长结构通常需定义插入和删去部件的操作。而且可变
长数据对象经常使用指针类型。
2、每个部件的类型
同构的 ——所有部件为相同类型，如：数组、字符串、
集合、文件等。
异构的 ——部件有不同类型，如：记录，列表等。
3、用于选取部件的名字
结构类型需要有标识结构中个体部件的选择机制。
对数组，个体部件的名字可以是整数下标或下标序列。
对列表，名字可以是用户定义的标识符。
有的结构，只允许访问特定部件，如栈顶元素。
4、部件的最大数量
对有的变长结构，结构的最大尺寸可以指定。
5、部件的组织
最常见的组织是简单的线性序列，如：向量、记录、字
符串、栈、列表、文件等。
然而，数组、记录和列表类型也可以扩展为多维形式。
多维形式可以看成分别的类型，也可以简单地看成顺
序类型（其元素类型为结构）。
如 A(i,j) 和 A[i][j]的差异。
?数据结构上的操作
结构上操作的定义域和值域规约的方法和基本类型操作
是类似的，但是，有些新的操作类型特别重要。
1、部件选择操作
有两种类型：随机选择 ——可任意选择结构中某一部件
顺序选择 ——以预定好的顺序选择部件。
2、整体数据结构操作
以完整的数据结构为参数，产生新的数据结构为结果。
大多数语言中，这样的整体性操作是有限的。如,
两个数组相加、记录间的赋值、集合的并等。
少数语言提供了大量整体操作，然而，程序员很少去选
择个体部件。如,APL和 SNOBOL4语言。
3、部件的插入 /删除
这种操作将改变部件数量，从而影响存储表示和存储管
理。
2、数据结构的创建 /消除
这类操作将对存储管理有很大影响。
?数据对象中部件或数据值的选择和相关的引用操作是有区
别的。如,V[4]选择 V中第 4个元素，分两步,
先引用（确定 V的位置（ l-值），返回一个指针）,
后选择（得到部件的位置）。
数据结构类型的实现
实现中需要考虑的两个问题：结构中部件的高效选择，以及
高效的存储管理。
?存储表示
结构的存储管理包括：①结构中部件的存储；②可选的描
述子（用于存储结构的属性）。有两种基本表示,
1、顺序表示
结构存放在单个连续块中（包括描述符和部件）。
常用于固定长的结构，有时也用于同构变长结构。
2、链接表示
结构被存放在几个非连续的存储块中，这些块用指针链接
在一起，该指针称为链（ link）。
通常用于变长结构。
两种存储表示方式,
?数据结构操作的实现
大多数结构的实现中，部件选择是最重要的，需要较高
的随机和顺序访问效率。对顺序和链接存储表示，这两
种类型的选择的实现有所不同。
顺序表示
部件的随机访问通常涉及“基地址（完整块的开始位置）
+位移量（部件在块中的相对位置）”的计算。
对一个顺序存储的同构结构, 部件序列的选择按如下步
骤,
1,要选择序列的第一个部件, 使用, 基地址 +位移量, 。
2,要选择下一个部件, 在当前部件位置上加上当前部件
的大小, 对同构结构, 每个部件的大小是相同的 。
链接表示
随机选择需要沿指针链从头查找, 需知道在部件块中链
指针的位置 。
部件序列的选取相对容易, 沿指针向前即可 。
?存储管理和数据结构
当一个对象被绑定到一个特定的存储位置，即：一个存
储块被分配并被初始化，则该对象的生命期开始。而当
绑定解除，则标志生命期结束。
对变长结构而言，其中个体对象有自己的生命期。
数据对象一旦创建，需同时创建它的访问路径，使得对
象可被程序中操作访问。
访问路径的创建方式,
——将标识符（名字）和对象相关联
——存放指向结构的指针于其他可访问的结构中，使
成为其部件元素。
在生命期中，还可能产生其他的访问路径。
如：作为参数传递给子程序
创建一个新指针
访问路径也可以被删除
如：赋新值给一个新指针变量
从子程序返回。
两个存储管理的中心问题,
1、垃圾,
当所有访问路径被消除，但数据对象仍然存在，它将
不可再被访问。因此，其和存储位置的绑定必须解除。
2,Dangling reference：悬空引用。
是一个访问路径，它在关联的数据对象消除后仍然存
在。
这对存储管理是一个严重的问题，因为它可能破坏运
行时结构的完整性，如：修改不相关的数据和修改存
储管理数据等。
数据结构的声明和类型检查
例,Pascal声明,A,array[1…10,-5..5] of real
有如下含义,
1、类型是数组
2、维数为二
3、行下标为整数 1到 10
4、列下标为整数 -5到 5
5、部件数是 110（ 10× 11）
6、部件类型为实数。
这些属性的声明允许 A的顺序存储表示，并可在编译时确定
A中元素的选择访问公式，虽然 A只是在进入子程序时才创
建。
如无声明，则 A的属性只能在运行时动态确定，从而产生在
存储表示和元素访问上的低效。
数据结构的类型检查更为复杂，因为必须考虑元素选择操作。
有两个主要问题,
1、被选择部件的存在性
选择操作的参数可能是类型正确性，但指定的部件可能
在结构中不存在，如：下标越界。
这本身并不是类型检查的问题，通常会产生“例外处
理”。
然而，在没有运行时类型检查和例外处理的情况下，会
产生类似类型检查错的效果。
通常，通过运行时检查确定被选部件是否存在（在用公
式确定其精确左值前）
2、选择部件的类型
静态检查只保证：如果部件存在，则它具有正确类型。
向量和数组
向量由固定数量的同类型部件组成，按简单的线性序组织，
向量部件由下标选择。
向量也称一维数组或线性数组。
二维数组或矩阵，其部件被组织为行、列的矩形格。
?向量
向量的属性包括,
1、部件的数量，通常由一组下标范围隐式地指定。
2、部件的类型，所有部件具有相同的类型。
3、用于选择每个部件的下标，通常是一个整数域，第一
个整数指定第一个部件，第二个数指定第二个部件，依
此类推。下标可以是给出一个值的范围，也可以是只给
出上界，而下界是隐含的。
典型的向量声明,
V, array [1..10] of real; --PASCAL语言
float a[10]; --C语言
如果允许指定下标域，则可以使用枚举为下标，如,
type class = (Fresh,Soph,Junior,Senior)
var ClassAverage,array [class] of real;
向量上的操作,
选择元素的操作通常称为下标操作，如,
V[2],ClassAverage[Soph]
由于下标大都是可计算值，固可用表达式作下标,
V[I + 2]
其它操作包括：向量的创建和消除，向量元素的赋
值，相同大小的两个向量间的算术操作等。通常插
入和删除向量元素是不允许的。
APL是专门基于数组的语言，允许大量向量操作。
实现,由于向量的同构性和固定大小，其存储和访问相
同简单。同构性意味着每个元素的大小和结构相同，固
定大小意味着元素数量及每个元素的位置保持不变。
顺序存储表示是很好的选择，描述子用于存放一些运行
时必要的属性信息。
用于越界检查
元素的随机访问，即向量元素的左值访问公式,
lvalue(A[I]) = ? + (I － LB) × E
这里 ?为基地址,E为元素所占的存储大小。亦即,
lvalue(A[I]) = (? － LB × E) + (I × E)
lvalue(A[I]) = K + (I × E) ----K表示常数
有的语言（如 FORTRAN ）中 K为常量，故可在编译
时计算出来。
即使在有的语言（如 PASCAL）中,K可能发生变化，
也只需要在存储分配时计算一次。
由于 E和 I均是在编译时可知，因此，访问公式的计算
完全可在编译时完成。
如 C语言中，字符数组的 E为 1,LB总为 0，访问公式
为,lvalue(A[I]) = ? + I。
虚原点,
lvalue(A[0]) = (? － LB × E) + (0 × E) = K
即 K为向量中元素 0的地址，如果 0元素存在。如果向
量的下界大于 0，则这个地址称为虚原点 VO。因此，
构建向量并产生访问公式的算法为,
1、向量存储的创建：为 N个大小为 E的向量元素分配
D＋ (N× E),D为描述子的大小。
2、计算虚原点,VO ＝ ? － LB × E
3、访问具体元素,lvalue(A[I]) = VO + I × E
上面公式假定 I为 A的有效下标，即,LB <= I <= UB。
通常越界检查是必须的，因此 LB和 UB应该存放在描
述子中。
如果虚原点也存放在描述子中，则数组和描述子可不
必存放在一起。这是为什么通常描述子作为参数传递
给子程序，而数据的数组却存放在别的地方。
这里描述子类型和
元素类型均未在描
述子中给出。通常,
这些信息在编译时
已知。
打包及未打包存储表示,
通常每个数组元素占用完整的可编址存储单元。但是，
有的类型只占用一个字中的一小部分，此时，需要将
几个向量元素打包存放在在一个编址单元中。打包存
储带来的问题是访问公式更加复杂。
全向量操作,
将向量作为整体的操作是基于顺序存储表示而实现的。
一个向量到另一个向量的赋值即是简单的内容拷贝，
而描述子不需要拷贝。
向量上的算术操作实现为向量中元素循环顺序处理。
全向量操作实现的最大问题是结果的存储。需要临时
分配存储来存放结果的右值，除非它被立即赋给一个
左值位置。
当涉及的全向量操作过多时，临时存储的管理可能会
增加复杂性和成本。
?多维数组
多维数组实际上是一维数组的推广。
规约和语法：和向量在属性上的差别只是需要指定每个
维的下标范围。如,
B, array[1..10,-5..5] of real;
数组元素的选择需给定每一维，如,B[2,4]。
实现：矩阵可以方便地实现为向量的向量，三维数组的
元素是向量的向量，依此类推。所有子向量必须有相同
数量的元素，而且是相同类型。
矩阵是实现为“行之列”还是“列之行”是语境敏感的，
特别是在不同语言的程序间作为参数传递时。最常见的
实现是“行之列”，此即所谓的“行为主序”。
多维数组的存储表示类似于向量。如对矩阵，先存第一
行的数据对象，再存第二行的数据，依此类推。
二
维
数
组
的
存
储
表
示
下标操作及访问公式,
对 M× N的“行为主序”二维数组，有,
lvalue(A[I,J]) = ? + (I－ LB1) × S ＋ (J － LB2) × E
这里 ?是基地址,S是一个行的长度，即
S＝ (UB2－ LB2+1)× E
考虑常量项,VO＝ ?－ LB1× S－ LB2× E
则,lvalue(A[I,J]) ＝ VO＋ I× S＋ J× E
更多维数组,A[L1:U1,…,L n:Un]
1、乘数的计算,mn=e,mi=(Ui+1－ Li+1+1)× mi+1
2、虚原点的计算,VO＝ ?－ ?(Li× mi)
3、数组元素的访问,lvalue(A[s1,…,s n])=VO+ ?(si× mi)
?切片
规约：切片是数组的子结构，也是一个数组。如图,
PL/1中，分别表示为,A(*,2),B(3,*),C(3,*,*)。
FORTRAN77中允许传递数组的部分为参数。由于采用
“列为主序”，传递 A(1,3)到向量 B意味着 A(1,3)到 B(1)、
A(2,3)到 B(2),A(3,3)到 B(3)。
FORTRAN90引入了切片概念，分别表示为,A(1:4,2)、
B(3,1:3),C(3,1:3,1:4)。
实现：描述子的使用使得切片的高效实现成为可能。如：
3× 4数组 A的描述子为,
VO ?
LB1 1
UB1 4
Multiplier1 3
LB2 1
UB2 3
Multiplier2 1
这里 Multiplier2表示数据对象的大小，也是数组中相邻元
素的距离。切片的性质是：一维元素可能不相邻，但距
离一定是相等的。因此，切片 A(*,2)的描述子为,
VO ?－ 2
LB1 1
UB1 4
Multiplier1 3
切片的长度为 4，每个元素相隔三个位置，起始点为 A后
一个位置。
记录
由固定数量的不同类型部件组成。
规约和语法：记录和向量都是定长的线性结构，其不同在于,
1、记录的元素可能是异构的，是不同类型的混合。
2、记录的元素用符号命名，而不是用下标。
C语言中的记录声明为,
struct EmployeeType
{int ID;
int Age;
float Salary;
char Dept;
} Employee;
记录元素的选择,
Employee.ID
Employee.Salary
上述声明中可看出,
1、部件的数量
2、每个部件的数据类型
3、用于命名每个部件的选择子
部件也称域。部件选择是记录的基本操作，但不是使用计
算值，而是使用文字部件名。很少有针对整个记录的操作。
实现：记录的存储表示包含一个顺序的存储块，其中元素
顺序存放。每个元素可能需要描述子去指定它们的数据类
型或其它属性，但通常对记录本身没有运行时描述子。
元素的选择相对容易实现，因为在翻译时域名就已经知道，
记录的声明也使得每个元素的大小和位置在翻译时可确定。
因此，在翻译时可以计算出任意元素的位移量。
基本的访问公式,
Lvalue(R.I) = ? + ?(size of R.j) j=1..I-1
= ? + KI ---KI为元素 I的位移量
有些数据类型的存储必须从特定的地址边界开始。例如，整
数可能必须从字的边界开始存放，对可字节编址的机器而言，
该地址必须能够被 4除。在 C语言中,
struct EmployeeDivision
{ char Division;
int IdNumber; } Employee
如果 IdNumber必须从字边界开始，则在 Division和 IdNumber
间有三个字节未用，称为填料（ padding）。存储表示就好象
如下声明一样,
struct EmployeeDivision
{ char Division;
char UnusedPadding[3];
int IdNumber; } Employee
完整记录的赋值被实现为简单的拷贝。
?含结构元素的记录和数组
如果语言同时提供数组和记录类型，则这两种类型的元
素可能和其它基本类型的元素混杂在一起。如：一个向
量的每个元素都是一个记录，在 C中有如下声明,
struct EmployeeType
{int ID;
int Age;
float Salary;
char Dept;
} Employee[500];
这样一个复合数据结构的元素的选择需要一系列选择操
作，如,Employee[3].Salary。
记录的部件也可以是数组或其它记录，导致记录具有层
次结构。 COBOL和 PL/1中，使用层次编号来语法地指定
这种层次结构。如下是一个 PL/1声明,
1 Employee,
2 Name,
3 Last CHARACTER(10),
3 First CHARACTER(15),
3 Middle CHARACTER(1),
2 Age FIXED(2),
2 Address,
3 Street,
4 Number FIXED(5),
4 St-Name CHARACTER(20),
3 City CHARACTER(15),
3 State CHARACTER(10),
3 Zip FIXED(5);
实现：存储表示类似于简单的数组和记录类型。记录构
成的向量的存储表示相对简单，每个行被记录的存储表
示替代。类似地，记录的记录保持相同的实现结构，但
每个元素是一个子块，子块本身是一个完整记录的表示。
?可变记录（ variant records）
可使用一个记录来表示相似的、但不同的数据对象。这
样的记录类型有几个变体，它们有共同的部分，但各个
变体又有自己独有的部件。如，雇员可以分为按月和按
小时领工资两种情况，从而呈现两个变体。
一个 PASCAL声明如下,
type PayType = (Salaried,Hourly)
var Employee,record
ID,integer;
Dept,array [1..3] of char;
Age,integer;
case PayClass,PayType of
Salaried,(MonthlyRate,real;
StartDate,integer);
Hourly,(HourRate,real;
Reg,integer;
Overtime,integer)
end
PayClass称为标记或
判别子，用于指定被
采用的变体。
变体记录的选择操作和一般记录相同，但由于变体问题，
有的部件的存在性会在运行中发生变化，因此，有的选
择操作可能在运行中某时刻找不到希望的部件，如：
Employee.Reg。这类似于下标越界问题，解决方案为,
1、动态检查：在访问部件前检查标记以保证该部件
存在。如果标记值不对，则出现运行时错。
2、不检查：语言设计可能允许变体记录的定义没有
显式的可在运行时检查的标记，因此，变体记录的部
件选择总被假定为合法的。由于变体记录的实现方式，
这样的选择总是可能的，但是，如果部件不存在，当
前变体的值可能会被不经意地取出或覆写。 C语言中
的 union类型就不允许标记，从而不能提供检查。
具有变体的记录也称为 union类型，可视为一组数据对象
集合的“和”。如果不允许标记，则称为“自由和”类
型（ free-union），如果允许标记，则称为“判别和”类
型（ discriminated-union）。
实现：可变记录的实现比正确地使用它要容易。在翻译
时，每个变体的部件的存储需要量是确定的，存储的分
配根据最大的可能变体来安排。在存储块内，每个变体
根据部件的类型和数量具有不同的布局。布局在编译时
确定，并用于计算被选择部件的位移。运行时，不需要
特殊的描述子。
如果不进行检查的话，变体中部件的选择相同于普通记
录的部件选择。在翻译时，被选择部件在存储块中的位
移被计算出来，在运行时，位移被加到块的基地址上以
形成部件的地址。此时，部件存在与否十分重要，如不
存在，则将取出不是所期望的值，而对该部件位置的修
改也有可能带来灾难性后果。
如果提供动态检查，则先检查标记部件的内容，以保证
标记指示出所需的变体确实存在。
变体记录的存储表示,
List列表
由数据结构的有序序列组成的数据结构 。
规约和语法：列表类似于向量, 都由数据对象的有序序列构
成, 即可以访问列表的第一个元素, 第二个元素, 依此类推 。
它们的不同主要体现在,
1,列表基本上不会固定长度, 通常用于表示任意的
数据结构, 并在运行中增长和缩小 。
2,列表基本上都是异构的, 列表的每个成员的数据
类型均可以不同 。
3,使用列表的语言典型地通过隐式的方式声明这样
的数据, 其成员没有显式的属性 。
LISP语法是典型的列表结构,
(FunctionName Data1 Data2 … Datan)
在 LISP中，大多数操作以列表为参数并返回列表值。如,
(cons ?(a b c) ?(d e f)) = ((a b c) d e f)
LISP的一个重要特征是：所有参数需先计值。如上式写为,
(cons (a b c) (d e f)) = ((a b c) d e f)
则首先计值函数 a，然后计值函数 d，这可能产生错误。
而函数 (quote x)，或‘ x，只返回变量的文字值，从而避
免不适当的计值。
ML属于赋类型的函数语言，因此，其表是同构的。如,[1,
2,3],[a,b,c],[“abc”,“def”,“ghi”]等。
实现：由于列表元素的异构性和大多数列表实现的动态性，
向量、数组所用的存储表示将不适用于列表。通常适用链接
列表存储组织结构。表项是基本元素，通常由固定长度的数
据对象构成。
在 LISP中，通常含有三个信息域：一个类型域，两个表指针。
如果类型域指明为原子，则剩下的域为描述该原子的描述子。
如果类型域指明为表，则第一个指针为表头，第二个指针为
表的尾。
这种表示的中间和底层结构的类似性显示了这种实现方式的
功效,
1,cons,cons或 join操作通过创建一个新表节点而实现，
该节点的头域指向第一个参数，尾域指向第二个参数。
2,head：表的头是表项的头域的内容（右值）。
3,tail：表的尾是表项的尾域的内容。
列
表
的
存
储
表
示
LISP最早是在 60年代早期实现于 IBM704计算机上。该机器
字长为 36位，一个 36位的寄存器可存放两个 18位的地址，
前 18位称为,address register”，后 18位称为,decrement
register”。
因此,head操作是,contents of the address register”，或 CAR；
tail操作是,contents of the decrement register”，或 CDR。
LISP中就使用这两个词来作为头及尾操作。
列表是 ML,LISP和 Prolog等语言中的基本数据对象，但并
不出现在 C,PASCAL或 Ada等编译型语言中。
维护列表所需要的动态存储管理和编译型语言中的高效存
储管理是不一致的。
然而，使用编译型语言的程序员仍然可以访问列表，但是，
必须将其作为程序员定义的数据类型。
?列表的变种
栈和队列：栈是一种列表，其中部件的选择、插入和删
除被限制在一端进行。队列的部件选择和删除被限制在
一端，而插入被限制在另一端。
树：其中的部件可以是列表以及基本数据对象，而每个
列表只能最多是另一个列表的部件。大多数 LISP例子实
际上是树。
有向图：其中的部件可以被任意的链接模式链接在一起，
而不仅仅是线性序。
性质表：具有可变数量部件的记录通常称为性质表，如
果部件的数量可以无限变化。在性质表中，部件名及其
值均需被存储，分别称为性质名和性质值。性质表通常
表示为链接表。
性
质
表
的
存
储
表
示
字符串
字符串是一个字符构成的序列。几乎所有的语言均有字符串
类型。
规约和语法：至少有三种不同的字符串类型处理方式,
1、固定声明长度。在程序中声明字符串对象的固定长度。
赋给该对象的值总是该长度的字符串。新串值赋给该数
据对象将导致长度调整：减短或补足。 PASCAL和
COBOL中常采用此技术。
2、有界变长。字符串数据对象具有固定的最大长度，但
实际的字符串值长度可以小于此，甚至是空串。执行过
程中，字符串长度会发生变化，但超长时需减短。
3、无界长度。字符串数据对象可以具有任意长度，而且
长度可以在执行过程中动态地无界变化。
前两种方法允许翻译时确定每个字符串数据对象的存储分配。
第三种方法需要存储的运行时动态分配。
一些重要的字符串操作,
1、串联。将两个字符串连接在一起以形成一个长串。如：
,BLOCK”||“HEAD”产生,BLOCKHEAD”。
2、串上的关系操作。包括一般的相等、大于、小于等均
可用于字符串。由于字符本身是有序的，因此可以扩展形
成字符串的字典序。
3、使用定位下标的子串选择。很多语言提供了选择子串
的操作。如,FORTRAN中,NEXT ＝ STR (6:10)将 STR中
从位置 6到 10的 5个字符赋给 NEXT。如果允许子串选择出
现在赋值的两边，则其语义必须仔细定义。
4,I/O格式。字符串上的操作经常被提供以帮助输出数据
的格式化或将格式化的输入流分界成小的数据单元。如：
C和 FORTRAN中的格式化 I/O特性。
5、使用模式匹配的子串选择。由于不知道子串在大串中
的位置，模式匹配则成为一种重要的方法。如：
SNOBOL4就提供了强大的模式匹配操作。
实现：三种不同的方法使用不同的存储表示。对固定长度的
字符串操作可以有硬件支持。其它方式则需要软件仿真。
指针及程序员构造的数据对象
通常，不是引入一系列可变长的链接数据对象类型，而是提
供设施来允许使用指针链接对象而相连结构，这样需要如下
几个语言特性,
1、基本数据类型－指针（ pointer），也称引用或访问类型。
指针对象包含另一个数据对象的位置（左值），空指针
为 nil或 null。
2、定长数据对象的创建操作
创建操作分配一个存储块，并返回其左值，可用于存放
对象的右值。这种创建操作和声明创建方式有两个差别,
a.数据对象不需要名字
b.可在程序执行中任何位置创建
3、取引用操作
允许跟随指针到其指向的对象。
规约：指针数据类型定义一类数据对象，它们的值是其它数
据对象的位置。指针类型的对象有两种处理方式,
1、指针只能引用单个类型的数据对象。
如 C,PASCAL和 Ada等语言，需要进行指针类型声明
和相应的静态类型检查。
2、指针可以引用任意类型的数据对象。
如,SMALLTALK语言，数据对象本身带有描述子，
需要进行动态类型检查。也可以不进行类型检查。
创建操作为一定长数据对象分配存储空间，并创建指向该新
数据对象的指针，该指针可以存放到指针数据对象中。如：
PASCAL和 Ada中的 new,C中的系统函数 malloc。
选择操作允许跟踪指针值以达到指定的数据对象。因为指针
是普通的数据对象，指针数据对象本身也可以用一般的选择
机制。如,*用于取指针的右值，并将其变成左值，用左值访
问数据。
实现：指针数据对象被表示为存储位置（包含另一个存储位
置的地址，该地址是表示该指针指向的数据对象的存储块的
基地址）。指针值的两种存储表示,
1、绝对地址：指针值可以表示为数据对象所在存储块的
实际存储地址。
2、相对地址：指针值可以表示为从某基地址开始的位移
量。数据对象是被分配在一个大的存储堆中。
当使用绝对地址时，有创建操作创建的数据对象可以分配在
存储中任意地方，通常，该分配发生在一个存储堆区域中。
使用绝对地址的选择操作将更为高效，因为指针值提供了直
接的访问。缺点是存储管理更为困难，因为数据对象不能随
意在存储中移动，存储的回收必须逐个进行。
使用相对地址需要一个存储块的初始分配，可以是每种类型
各有一个区域，也可以是所有数据对象共有一个区域。每个
区域管理为一个堆。缺点是选择操作需要更大的代价，优点
是存储块可以整体任意移动，整个区域可以处理为一个数据
对象。
集合
集合是一个数据对象，它包含不同值的无序集合。而列表中
元素是可以重复的。集合上的基本操作有,
1、成员关系,X是否为 S中的成员？ X?S？
2、单个值的插入和删除。如果 X不是 S中的成员，则可
以插入 X；如果 X是 S中的成员，则可从 S中删除 X。
3、并、交和差。
集合中成员的访问不能使用下标或相对位置。
实现：在程序设计语言中，术语集合有时是指表示有序集合
的数据结构。一个有序集合实际上是一个列表，只是不允许
元素的重复。对此不需要特殊的考虑。而无序集合则需要两
种不同的存储表示。
集合的位串表示,
位串存储表示适合于已经知道集合元素域的大小较小的情
形。假定在域中有 N个元素，这些元素任意排序为 e1、
e2,…, eN，从该域选择出的一组元素可以用长度为 N的
位串来表示，其中，如果 ei存在于集合中，则串的第 i位为
1，否则为 0。
位串表示了集合的特征函数。元素的插入表现为相应位的
设置，元素的删除表现为相应位的清除，成员关系判断表
现为检查相应位，并、交及差的操作可实现为位串上的布
尔操作，通常有硬件支持。
如果提供了对位串操作的硬件支持，则集合的位串表示的
操作将是非常高效的。然而，硬件操作通常仅仅应用到某
固定长度的位串（如：字的长度）。如果串的长度大于最
大值，则软件仿真将是需要的，用于将位串分为较小的、
可被硬件直接操作的单元。有的语言为此而限定集合的大
小。
集合的 HASH编码表示,
另一种常见的集合表示方法为 HASH编码或散列存储。该
方法可以用于集合的域较大时。
该方法可允许集合的成员测试、插入、删除高效地完成。
然而，并、交及差等操作效率不高，必须实现为一系列
个体元素的成员测试、插入、删除等操作。
为了有效,HASH编码方法需要实质性的存储分配。
最常见的是，语言并不向用户提供集合数据类型的这种
表示方式，但语言的实现在翻译或执行中使用这种表示
来实现一些系统定义的数据。
如，大多数 LISP实现使用这种存储表示来实现名为 object
list的集合，它包含 LISP程序执行中所有原子数据对象的
名字。
几乎所有的编译器使用 HASH编码来查找符号表的名字。
在一个向量中，每个下标指定一个唯一的部件，可以使用
简单的访问函数来达到该目标。
HASH编码的目标就是要尽可能地达到这样的效果。问题
是：潜在的合法名字的集合相对于可用的存储而言是大的。
如果我们分配 HASH表至少为我们所期望使用的两倍大，
则 HASH编码将是非常高效的。
不是将集合中元素顺序地存放在存储块中，而是将元素随
机地散列在块中。其技巧在于以这种方式存放每一个元素，
而其存在与否在以后将可以立即地确定，而不需要搜索整
个存储块。
考虑加入元素 X到集合 S，位串 Bx表示 X，存储块 Ms表示 S。
应用 HASH函数到 Bx得到 Bx在 Ms中的位置 Ix，称为 HASH
地址，用为指向块中位置的索引。如果 X不在 S中，则 Bx
将被存入到 Ms中由 Ix指定的位置。 X的查找是方便的，提
供使用同样的 HASH函数可找到其在 Ms中的位置。
对 HASH函数的要求一是计算速度，二是分布的随机性。假
定 Ms为 1024个字，需要存放的数据项是表示为双字位串的字
符串，则我们可以表示一个可含 511个不同元素的集合。假
定块的起始地址为 ?，一个合适的 HASH地址将是 9位的串 Ix，
因为公式 ?＋ 2× Ix将总是产生在块内的地址。 Ix由 Bx产生，
假定 Bx存放在字 a和 b中。
1,a乘以 b，得到 c（两个字长）
2、将 c的两个字相加，得到 d（一个字长）
3、将 d平方，得到 e
4、取 e的中间 9位，得到 Ix
即使最好的 HASH函数也不能保证对不同的数据项产生不同
的地址。几乎不可避免地会产生冲突。
处理冲突的解决办法,
1、重新 HASH。可以考虑修改初始的位串 Bx，如：乘以
某常量。然后重新 HASH。直至无冲突为止。
2、顺序扫描。从块中的冲突点开始进行顺序搜索，直至
找到某 Bx，或遇到一个空位置。
3、使用桶（ bucketing）。在块中的位置上用一个指针来
指向具有相同 HASH地址的一个链接桶表。
不同的 HASH函数合适于不同的将被存放的位串表示。如果
有一个好的 HASH函数，且表是半满的，则冲突较少发生。
前面例子中 512个项只用了 511个的原因就是为了解决冲突。
可执行数据对象
大多数语言中，可执行源程序和其操作数据是分开的。而有
的语言，可执行语句可以是数据，也可被程序访问。如：
LISP将所有数据存放在表中。
（ define myfunction (cons (abc) (def))）
这里 myfunction是可执行的数据对象。
Prolog中也有类似情况。
文件和 I/O
文件是一种数据结构，具有两个特殊性质,
1、通常表示在外存上，比其它数据类型也要大得多。
2、生命期长，通常会跨越创建它的程序的生命期而存在。
顺序文件是最常见的文件类型。很多语言也提供直接访问文
件和索引顺序文件。
文件的两种常见用途,
针对外部操作环境的数据输入和输出。
作为数据的临时存储，以解决高速内存不足的问题。
文件的部件称为记录。但有别于我们前面所提到的记录类型。
顺序文件,
顺序文件是相同类型部件的线性序列，其长度可变且没
有固定的最大上界。（当然，受外存大小限制）
一个典型的 PASCAL声明,
Master,file of EmployeeRec;
文件部件的类型可以是基本类型，也可以是结构类型。
通常是定长的。此外，文件记录不应该为链接表示，不
允许含指针值。
为了输入、输出，数据通常被表示为字符形式，这样一
个文件的部件为单个字符，此即所谓文本文件，是一种
特殊的顺序文件。
文件的访问可以是读写两种模式。文件位置指针用于指
定文件中位置，或者是第一个文件部件之前，或者是两
个文件之间，或者是最末一个文件之后。
规约：顺序文件上的主要操作有,
1、打开（ OPEN）。给定文件名及访问模式，从操作
系统获取文件的位置和性质信息，分配所需的内存作
为缓冲及存放其它信息，设置文件位置指针到合适位
置。打开操作可以是显式的或隐含的。
2、读。将当前文件部件的内容存放到指定变量。可
以是程序员定义的变量，也可以是缓冲变量。
3、写。在文件的当前位置创建一新部件，并将指定
变量的内容写入该部件。
4、文件尾测试。 eof测试是必需的，以避免读操作的
不恰当使用。
5、关闭（ close）。通知操作系统文件可以从程序分
离，文件所占的内存可以释放。通常，程序的执行终
止将隐式地关闭文件。
实现：在大多数计算机系统中，主要是底层操作系统负责
文件的实现。特定的语言仅仅负责必要的局部数据结构以
和操作系统接口。文件操作通过调用操作系统提供的原语
而实现。
从语言的角度，主要的实现问题是：系统数据和缓冲的存
储。当打开文件时，必须提供文件信息表和缓冲的存储。
操作系统的 open原语存储文件的位置和特征信息到文件信
息表中，缓冲用于队列的顺序表示。
文件的读写操作由操作系统原语针对缓冲区进行。当所有
操作完成后才成块转存到外存中。
使用缓冲的文件表示
文本文件,
文本文件是字符的文件，是大多数语言 I/O的主要文件形式。
文本文件可以被打印，以及通过计算机键盘输入来创建。
文本文件可以按顺序文件的方式被操作，但也提供了一些
特殊的操作，如：一些数值数据在输入过程中被自动地转
换成内部存储表示，而不需要存为字符形式。也允许在输
出时将内部表示直接转换为字符形式。
此外，还提供了输入、输出格式的操作。
交互式输入－输出,
考虑一文本文件表示一交互终端，“写”命令在终端上显
示字符，“读”命令从键盘请求数据（通过提示符表示）。
那么,
1、文件必须同时处于“读”和“写”模式，通常读和
写交替进行。
2、数据输入 /输出的缓冲是有限的。
3、文件位置指针和文件尾测试相对意义不大。
直接访问文件,
可以随机访问文件中的单个部件，用于选择部件的下标称
为“键”，可以是整数或其它标识符。
部件的组织是无序的，每个部件关联一个键值。键值通常
和位置关联，形成一个“对”。“对”的向量序列称为索
引。
索引顺序文件,
类似于直接访问文件，同时具有顺序访问部件的机制，从
随机选择的一个部件开始顺序访问。
文件的组织是纯的顺序方式和纯的直接访问方式的折中。
索引顺序文件需要键值的索引，但是，在索引中的项必须
根据键值排序。
文件位置指针指向当前部件位置。
数 据 类 型
?任何程序, 不管以何种语言写成, 均可以视为刻划了一个操
作集合 。 并将以一定顺序作用到一定数据上 。
?语言的基本不同在于：允许的数据类型, 允许的操作类型,
以及控制操作顺序的机制 。
?下面章节将围绕这些方面展开 。
4.1 类型和对象的性质
数据对象、变量和常量
?计算机的数据存储在结构上是简单的, 通常是由位串构成的
字节 。
?而语言虚拟机的数据存储则有更复杂的组织, 如：数组, 栈,
数, 字符串, 以及其它存在于程序执行中不同点的数据 。
?我们称虚拟机上一个或多个数据片断运行时的组合为数据对
象 。
?在程序运行中, 存在许多不同类型的不同数据对象 。 这些对
象及其相互关系在运行时动态变化 。
?有些数据对象是程序员定义的, 如变量, 常量, 数组, 文件
等 。 程序员通过声明和语句显式地创建和操作它们 。
?有些数据对象是系统定义的，不可为程序员直接访问。如：
运行时存储栈、子程序激活记录、文件缓冲、自由空间列
表等。这些数据对象在运行需要时自动产生，不需要时删
除。
?数据对象表示了数据值的一个容器，是值被存放和检索的
地方，而数据值是在存储器中以一种特定的位模式表示。
?数据对象和数据值在大多数语言中均是明确区分的，如图
4.1所示。
?每个数据对象有生命期，在生命期内可用来存放数据值。
?数据对象可分为简单数据对象和数据结构 ——其他数据对
象的聚集。
?数据对象在其生命期中涉及各种绑定，虽然其属性不变，
但绑定可动态改变。
?重要的属性和绑定有,
1,类型
通常在程序翻译时, 关联数据对象和它可能的取值集合 。
2,位置
通常不由程序员规定, 而是系统存储管理负责 。
3,值
由赋值操作完成绑定 。
4,名
通常在声明时完成绑定, 但可被子程序调用和返回修改
5,部件
通常用指针值相连, 可通过指针的修改而变动 。
?变量和常量
程序员通过变量显式地定义和命名数据对象 。
一个简单的变量是有名字的简单数据对象, 通过赋值修
改变量值 。
常量是具有名字的数据对象, 其值在其生命期内永久不
变 。 一个文字 （ 或文字常量 ） 是一个常量, 其名是其值
的书写表示, 如 21表示值为 21的整数常量 。
程序员定义的常量 ——其名字由程序员指定 。
常量的绑定由编译器完成 。
如 C语言中, #define MAX 20
语句 MAX=4是非法的 。
?永久性 Persistence
现今大多数程序仍是采用批处理模式, 即
1,将程序装入内存
2,适当的外部数据被准备给程序所用 。
3,将相关输入数据读入程序中变量, 变量被操作,
然后结果数据被写回外部数据格式 。
4,程序终止 。
程序中变量的生命期由程序的执行时间所确定 。 然而,
数据的生命期经常超出程序的单次执行, 这种数据称
为永久的, 在程序的多次执行间存在 。
具有永久特性的语言对书写基于事务的系统更为高效 。
文件系统可以解决永久性问题 。
数据类型
?一个数据类型是一类数据对象加上创建及操作它们的一组
操作。
?每个语言有一个基本数据类型集合，是语言固有的。
有的语言还提供了设施允许程序员定义新数据类型。
有的新语言还允许类型本身被语言操作（高阶能力）。
?数据类型的规约包括,
1、区分该类型的数据对象的属性
2、该类型数据对象可具有的值
3、定义该类型数据对象可能处理的操作
?例如：数组数据类型的规约
属性：维数、每维的下标范围、元素的数据类型等。
值：形成数值元素有效值的数的集合。
操作：选择个体数组元素、创建数组、改变数组形状，
访问下标上下界、完成数组间的算术操作等。
?数据类型的实现包括,
1、存储表示：用于在计算机存储器中表示数据对象。
2、数据类型操作被以特殊的算法或过程表示的方式，
这些算法和过程操纵数据对象的存储表示。
?数据类型的规约大致可对应虚拟机中该类型定义部分的规
约。而数据类型的实现定义了那些虚拟机部分基于更基本
的低层结构的仿真，低层结构可以直接是硬件，也可以是
有操作系统或微代码定义的软、硬件组合。
?从语法表示来看, 规约和实现大部分独立于特定的语法形
式 。
属性：表示为声明或类型定义
值：表示为文字或定义的常量
操作：可由特殊的符号, 固有过程或函数, 或隐含地通
过其他语言元素的特殊组合来调用 。
?特定的语法表示并没什么不同, 但程序语法中提供的信息
被用于确定各种属性的绑定时间, 从而允许翻译器建立高
效的存储表示或完成类型检查 。
基本 （ 简单 ） 数据类型的规约
简单数据对象包含单个数据值, 这类数据对象称为基本数
据类型 。
虽然不同的语言有不同的基本类型集合, 但整数, 实数,
字符, 布尔, 枚举, 指针等基本都是有的 。 但各自精确的
规约对不同语言会有差异 。
?属性
对象的基本属性 （ 如类型和名字 ） 通常在生命期中是不
变的 。
有的属性可存放在描述子中, 作为数据对象的一部分在
运行时出现 。
有的属性只用于确定其存储表示, 在执行中不显式地出
现 。
属性值和数据对象的值是不同的 。
?值
数据对象的类型确定了它可包含的可能值集，但在执行
中任一点，只包含一个来自该集合的单值。
基本数据类型定义的值集通常是有序集，有最小值和最
大值。
?操作
确定数据对象被处理的方式。操作可能是原操作，也可
是用户定义操作，本章强调语言固有的原操作。
操作是一个数学函数，对一给定输入参数，有定义的、
唯一确定的结果。每个操作有作用域，值域。操作的动
作定义了对给定参数的结果。
算法可用于刻划操作的动作，但其他规约也是可以的。
如可用乘法表来刻划乘法的动作。
操作的基调（ signature） ——定义了操作的作用域中参
数的数量、顺序和类型，以及结果值域的顺序和类型。
数学记号,
OP,type1× type2× …typen ?type—也称为函数原形
操作有单元、二元和多元。
动作的精确规约需要比参数类型更多的信息。
特别地，参数类型的存储表示通常确定那些参数如何
被操作，如：二进制数的乘法和 10进制数的乘法有很
大不同。
这样，在操作的规约中，常给出动作的非形式的描述。
一旦参数的存储表示确定，动作的精确规约是操作实现
的一部分。
有时难于确定操作的精确规约为数学函数，有四个主要
因素。
1、操作对某些输入无定义。
2、隐含的参数 ——操作会访问其他隐含参数（全局
变量；非局部变量）。
3、副作用（隐含结果） ——可能修改其他数据对象。
4、自我修改（历史敏感性） ——操作修改自己的内
部结构、或是执行中保持的局部数据、或是代码。
操作的结果还依赖于历史调用。
例：随机数产生器。
LISP中可自我修改代码。
?子类型
指一个类型是某大类的一部分（子类型 ——超类型）
如,PSCAL中的子域机制,OO中的继承机制。
但从理论角度看，子类型有严格定义,
凡是超类型对象可存在的地方（可承受的操作），
子类型对象同样适用，子类型对象继承超类型对象
的行为。
基本数据类型的实现
?存储表示
基本类型的存储受低层计算机的影响很大。
如：整数或实数几乎就是在低层硬件中使用的数的
整数或浮点数表示。
对字符值，硬件或 OS字符码被使用。
基本理由,
如使用硬件存储表示，则该类型数据基本操作可以
用硬件提供的基本操作实现。
否则，将使用软件仿真，从而带来效率损失。
基本数据类型的属性被类似地处理。
1、为了效率，很多语言设计为属性由编译器确定。
属性本身并不存放在运行时存储表示中 ——存储表示
通常直接使用硬件，如,C,Fortran,Pascal等。
2、数据对象的属性可存放在描述子中作为运行时数
据对象的一部分，如,LISP,Prolog等，这里灵活性
是主要目标。通常硬件不提供对描述子的直接表示。
数据对象的表示通常独立于存储位置，这样给定类型的
每个对象有相同的表示（除位置不同），通常用需要的
内存块的尺寸（大小）来描述，同时也涉及属性和值在
块中的布局。
通常内存块的每一个字或字节的地址用于表示数据对象
的位置。
?操作的实现
1、直接作为硬件操作
如：整数表示为硬件整数,+，－也直接用硬件实现。
2、作为过程或函数子程序
如：平方根操作。
如数据对象不使用硬件表示，则所有操作必须是软
件仿真，通常以子程序的形式。
3、作为 In-line（内嵌）代码序列。
这也是操作的软件实现形式，但不是使用短小的子程序，
而是将子程序中操作代码拷贝到程序中的调用点。
如 P118下部的例子，绝对值函数的实现。
声明
编写程序时，程序员确定数据对象的名字和类型。还要确
定：生命期、在程序中的活动范围、相关操作等。
声明：一种程序语句，告知语言翻译器关于数据对象的信
息。
如声明语句放在特定的程序或类定义中，则指明了对象
希望的生命期。
声明可以是显式的，也可以是隐含的或缺省的。声明可以
为数据对象赋上初始值，也可指定常量值。
?操作的声明
翻译时需要的关于操作的信息，主要是其基调 signature。
对基本操作，不需显式的参数类型和结果类型声明，是
语言中固有的。
对程序员定义的操作，则必须指定之。
如,sub,int× float→float ＝ >float Sub (int x,float y)
?声明的目的
1、选择存储表示
声明可以给语言翻译器提供关于数据类型和数据对象属
性的信息，使得翻译器可以确定数据对象的最佳的存储
表示，从而减少整体的存储需求和被翻译程序的执行时
间。
2、存储管理 ——声明使其更为高效
声明可以提供关于数据对象生命期的信息，从而使得在
程序执行过程中进行更高效的存储管理。
如：在 C语言中，在子程序头部声明的数据对象有相同
的生命期，这样可以在进入子程序时分配一个整体的块
来存放所有的数据对象，而在退出子程序时释放。
其它动态创建的数据对象则需单独处理。
3、多态操作 ——包括重载和真正多态
大多数语言均使用特殊的符号来表示一组不同的操作，
具体操作的选择将依赖于参数的数据类型。此即所谓重
载。如：＋可以是整数加、实数加，甚至可用于字符和
字符串操作。
重载是一个在语法层次上处理的概念。有编译器处理。
真正的多态通常是语义级别的概念，操作符的具体动作
的确定是在运行时进行。如：函数语言中，类型可以作
为参数带入，从而使函数的动作的选择依据类型实参而
确定。恒等函数就是典型的多态。
面向对象的继承机制也提供了所谓的包含多态性，即子
类的对象可用于父类对象出现的地方。
4、类型检查 ——最重要的目标，属语义检查，目标是
排错，分静态或动态类型检查。类型检查提供了很好的
防止错误的机制。
类型检查和类型转换
计算机硬件固有的数据存储表示通常不含类型信息。数据
上的基本原操作也不需类型检查。如一个位串,
111001……0011
可能是整数、实数、字符串、或指令，没有办法来区分。
硬件提供的基本操作（如加法），不能检查其参数是否为
整数，他们仅仅是位串。
汇编语言或机器语言编程中常见的错误源于错误的操作类
型，这种错误难于发现，因为操作并不以明显的方式失败。
操作可进行，但结果没有意义。
有时这种错误可在连续的一串操作后出错，有时程序停
止也不出错。
类型检查：指检查程序中每个操作均接收了正确数目的正
确类型参数，可在运行时完成，即动态类型检查；或编译
时检查，即静态类型检查。
高级语言的主要优点之一：可提供对所有（或几乎所有）
操作的类型检查。
动态类型检查：需类型标志，不需对变量声明（即变量是
无类型的）。
优点：编程的灵活性。程序员不需考虑类型问题，具有
较高灵活性。
缺点,
程序难于调试，不能完全消去所有参数类型错误。
程序测试不可能检测所有的路径。
需要在执行过程中保持类型信息，需存储空间。
动态检查需以软件实现，有时间花销。
静态类型检查：需要的信息通常由程序员在声明中及在其他
语言结构中提供。需要,
1、对每个操作，其参数的数量、顺序、类型及结果类型。
2、对每个变量，被关联的命名数据对象的类型。
3、每个常量数据对象的类型。
编译器在翻译的早期阶段收集声明中的类型信息，以后将用
于类型检查。
静态检查将针对程序中的所有操作进行，所有可能的执行路
径均被检查。因此，关于类型错误的进一步测试是不需要的，
因而不需类型标记和运行时类型检查。
静态检查涉及语言的多个方面：声明、数据控制结构、分别
编译等。
在多数语言中，对某些语言结构的静态检查在某种情况下是
不可能的。解决方案,
采用动态类型检查或不检查。
?强类型
如果我们可以静态地检测程序中的所有类型错误，则称
语言是强赋类型的。
通常类型为程序提供了一个安全层次。
一个函数 f,S→R 称为类型安全的，如果 f的执行不会
产生 R以外的值。
类型安全的操作均不需动态检查。
很少有语言是真正强类型的。
?类型推导
如果解释不会出现二义性，则类型声明可以省去。可由
语言实现推导出失去的类型信息。
?类型转换和强制
如果在类型检查中，参数的实际类型和操作期望的类型
间出现不匹配，则有两种处理方案,
1、指出出错
2、通过强制（隐式的类型转换）来改变实际参数的
类型为正确类型。
类型转换的基调为,
conversion-op, type1→type2
将一个对象变为另一类型的对象。
大多数语言以两种方式提供类型转换,
1、作为固有函数，程序员可显式地调用。
如：将实数变成整数,Pascal中的 round,C中的
(int) x
2、作为强制，自动在类型失配时调用。
如：整数和实数间相加，总是先将整数转变为实数。
强制的基本原则是不失信息。
这类强制称为 widenings或 promotion。
如强制会丢失信息，则称为变窄（ narrowing）
类型转换可能需要数据对象在运行时存储表示的改变，
如,COBOL和 PL/1中，数值以字符串方式存放，要相加
需先转换，结果又要转换为字符串。
有的语言中不提供类型强制，类型不匹配即被视为出错。
而有的语言则尽可能在不匹配时采用强制（如 C）。
赋值和初始化
?赋值是一基本操作，改变值到数据对象的绑定，这个改变
是操作的副作用。
?有的语言中，赋值语句也返回值（作为表达式处理），该
返回值包含被赋值拷贝的数据对象。
?Pascal中，赋值的规约为,
Assignment (:=), integer1× integer2→void,
integer2值赋给 integer1无显式返回 。
?C中, 规约为,
Assignment (=), integer1× integer2→integer 3
integer2值的拷贝赋给 integer1,
同时创建并返回包含 integer2值的新数据对象 integer3,
?考虑赋值 X,=X
右边的 X称右端值，用于引用包含在命名数据对象中的
值,r-值。
左边的 X用于引用将包含新值的数据对象的位置，称为
左值,l-值。
?赋值操作定义为,
1、计算第一个操作数表达式的左值。
2、计算第二个操作数表达式的右值。
3、将右值赋给左值对象。
4、返回右值作为操作的结果。
?赋值的两个不同视角,
?相等和等价
考虑 Zark语言中赋值,
A←2+3
有两种解释,
计值表达式 2+3，将其等价值 5赋给 A；
将操作 2+3赋给 A。
如有静态类型检查,A的类型决定赋值的语义。但对动态
类型语言，两种语义均是可能的。
这种情形在 Prolog中,is表示赋等价的值,=表示赋模式，
相等性由被赋值变量的当前值决定。
X is 2+3，则 X=5为真
X=2+3，则 X=5为假
?初始化
未初始化变量（或未初始化数据对象）是一个数据对象，
已被创建，但未赋值，即有 l-值，但没有 r-值。
创建对象仅涉及存储块的分配，块中原有位模式不会改
变。
有的语言创建时不需初始化，初始化是在以后显式地通
过赋值进行的。也可以在变量声明时进行显式的初始化
工作，此时，需要编译器产生相应的赋值代码并插入到
目标程序中。
在变量声明后立即进行初始化工作是程序员应有的良好
习惯之一。
有的语言，创建时自动初始化（隐式初始化）。
未初始化变量是程序错误的重要原因之一。
4.2 基本数据类型
数值数据类型
几乎任何语言均提供数值数据类型。其中，整数和实数是最
常见的，它们通常直接由计算机硬件支持。
1、整数
规约,整数类型的对象除了其类型外，通常没有其它属性。
该类型的整数值的集合形成了数学中研究的无限整数集的一
个在有限界内的有序子集。
最大整数值有时被表示为一个定义的常量，如,PASCAL中
的 maxint，其实际值由语言实现者根据具体的计算机硬件确
定。
C语言有四种不同的整数规约,int,short,long,char。
整数数据对象上的操作,
算术操作：二元算术操作的规约为,
BinOp, integer × integer － > integer
二元操作包括：＋、－,×, /,mod等。
一元算术操作的规约为,UnaryOp, integer－ > integer
一元操作有：－、＋、以及其它，如：绝对值。
关系操作,
RelOp, integer × integer － > Boolean
关系操作有：大于、小于、相等、不等、等等
赋值,
assignment, integer × integer － > void
assignment, integer × integer － > integer
位操作：也分二元和一元。如,&,|,<<（移位）等。
实现,语言定义的整数数据类型经常使用硬件定义的整数存
储表示和硬件提供的算术及关系操作来实现。通常使用一个
完整的字来存储一个整数。
三种可能的整数存储表示,
需声明及静态类型检查,
如 C,FORTRAN等语言
仍可使用硬件提供的
算术操作
省空间,
但需附加的操作处理
2、子域
规约：整数数据类型的子域是整数类型的子类型，包含一个
在限制范围内的整数序列。子域类型允许和一般整数类型相
同的操作集。
实现：子域类型对实现有两个重要影响,
更小的存储需求：可以用较少的位来存储子域。如：
1..10子域只需要四为存储表示，而完整的整数可能需 8、
16,32位或更多。但是，由于算术操作的限制，子域通
常表示为最小的有硬件实现算术操作的位数，通常为 8或
16。
更好的类型检查：声明某变量为子域对象可以允许更精
确的类型检查。如,month声明为 1..12，则,
month,= 0 将为非法操作。（可编译时检查）
有的子域检查不能在编译时进行，如,
month,= month + 1
3、浮点实数
规约：通常规约为单个类型属性 real或 float，形成一个从硬
件确定的最小负数到最大数的有序序列，但其值不是均匀地
散布在这个范围内。
此外，有的语言中，浮点数所需精度，即其所用的十进制位
数，可由程序员来确定。
实数具有和整数相同的算术、关系和赋值操作，但布尔操作
有时会受限。由于进位的关系，实数间的相等是很难达到的，
因此使用实数相等为判定条件必须慎重。
此外，大多数语言提供一些固有函数作为实数上的其它操作,
Sin, real － > real
Max,real × real － > real
实现：浮点实数的存储表示通常基于底层的硬件表示，其中
存储位置被分为尾数和指数。在大多数语言实现,IEEE 标
准 754被用为浮点数定义的标准。
有单精度和双精度浮点数之分。二者通常由硬件算术操作支
持其加、减、乘、除，而求幂操作通常由软件仿真。
如果同时支持单精度和双精度，则必须给予程序员相应的声
明机制。
4、定点实数
规约：大多数硬件包含了整数和浮点数对象，然而，有很多
应用需要特定的有理数，如：表示钱的元和分的数据对象。
这些数不能写成整数或浮点数。因此，需要定点数。
定点数表示为固定长度的数位，在给定位置为小数点。如，
COBOL语言中，有如下声明,
X PICTURE 999V99
实现：定点实数可直接由硬件支持或用软件仿真。如 PL/1中,
DECLARE X FIXED DECIMAL （ 10,3）,
Y FIXED DECIMAL（ 10,2）,
Z FIXED DECIMAL（ 10,2）；
X为带 3个小数位的十位十进制数,Y和 Z有两个小数位。 X的
比例因子 SF为 3,Y和 Z为 2。
value(X) = rvalue(X) × 10-SF
即,X值为 103.421，其右值为 103421。
考虑语句,Z ＝ X ＋ Y
实际加法的代码为,Z ＝ （ X ＋ 10× Y） / 10
考虑 X × Y，则,
积 ＝ rvalue(X) × rvalue(Y)
SF = SF(X) + SF(Y)
5、其它数据类型
复数,
复数包含一对数，分别表示数的实部和虚部。可以通过将数
据对象表示为两个存储位置构成的块（存放一对实数）来表
示复数。操作则通过软件仿真，这是不可能用硬件操作来实
现的。
有理数,
有理数是两个整数的商。引入有理数类型的原因是为了避免
实数的浮点和定点表示中的舍入问题。可以将有理数表示为
不限长的整数对。此时，长整数是用链接来表示的。
实数 1.5的不同表示,
枚举类型
我们通常希望一个变量只在一组符号值中选一值。如：变量
StudentClass只有四种可能值,freshman,sophomore,junior,和
senior。当然，可以用整数来代表这四者，但必须由程序员
来维护这类变量的操作安全性及使用的类型正确性。
规约：枚举是一个不同值的有序列表，由程序员确定其文字
名及它们的顺序。如 C中,
Emun StudentClass {Fresh,Soph,Junior,Senior};
Emun EmploySex {Male,Female};
枚举类型的基本操作为关系操作、赋值，以及后继和前驱。
实现：枚举类型数据对象的存储表示是直接的，在枚举序列
中的每个值在运行时被表示为整数，通常为 0,1,2,… 之
一。有的语言也可由程序员指定值。枚举类型上的操作的实
现也是直接的，直接使用硬件提供的基本操作。
布尔类型
大多数语言提供数据类型表示 true和 false，通常称为布尔或
逻辑类型。
规约：布尔类型的数据对象取二值之一。在某些语言中，可
将其考虑为语言定义的枚举类型。
Type Boolean = (false,true);
其顺序为 false < true。
布尔类型对象上的操作为一般的逻辑操作。
实现：布尔数据对象的存储表示是一个二进制位。通常，为
了可以直接访问，而表示为单个可编址单元。
用一个特殊位来表示,0为假,1为真。
或者,0为假，其余非零值为真。
也有其它数据类型可用于布尔型的表示，而 C中没有布尔型。
字符类型
大多数数据以字符形式输入和输出，有的被转换为其它数据
类型，但有的需要被直接以字符形式处理。字符类型也可以
作为字符串类型的基础。
规约：字符类型对象取单个字符为其值。可能的字符的集合
通常是对应于底层硬件支持的标准字符集的语言定义的枚举，
如 ASCII字符集。在该集合中的字符的顺序称为字符集的
collating顺序（比较顺序）。字符上的操作有关系操作、赋
值、以及字符测试等。
实现：字符数据值几乎都是硬件和操作系统直接支持的。通
常语言使用相同的存储表示。但在某些情形，语言也定义了
一些底层所不支持的特殊字符。在此情形下，需要提供相应
的转换规则和特殊的关系操作实现。
国际化
字符类型虽然看上去简单, 但在今天的语言设计中变得日益
重要 。 世界经济的全球化和对全世界通讯的计算机需要, 需
要计算机, 记, 多种语言 。 只用 8位的 ASCII字符是不够的,
从而出现国际化需求 （ I18N） 。
?Collating序列
排序 （ 分类 ）,非罗马字符的位置无统一定义, 在不同
国家有不同解释 。
大小写：有的语言不分大小写 。
扫描方向：不一定全是从左到右 。
?国家特定的日期格式：美 11/26/95,英 26/11/95等 。
?国家特定的时间格式,5:40pm(美 ),17:40(日 ),17.40(德 )，
17h40(法 )等。
?时区
?Ideographic systems，大字符集对日、中等是需要的。
?现金符号,$,￡,￥等。
4.3 结构数据类型
数据结构 ——包含其他数据对象作为元素或部件的数据对象。
结构数据对象和数据类型
结构数据对象 ——一组其他数据对象构成的聚集, 这些数据
对象称为元素或部件, 可以是基本类型, 也可以是结构 。
很多和数据结构相关的问题和概念与基本类型数据是相同的,
但数据结构更为复杂 。
数据结构类型也涉及类型规约和类型实现, 只是更为复杂 。
两个方面是特别重要的,
结构信息的规约和实现变成了中心问题, 用于指出部件
对象及其间关系, 以便于部件的直接选取 。
结构上的很多操作带来的存储管理问题 。
数据结构类型的规约
?规约的主要属性包括,
1、部件数量
结构的部件数量可能是固定的，在其生命期中不变，如：
数组、记录等。
也可能是变长的，数量可以动态变化，如：栈、列表、
集合、文件、表格等。
变长结构通常需定义插入和删去部件的操作。而且可变
长数据对象经常使用指针类型。
2、每个部件的类型
同构的 ——所有部件为相同类型，如：数组、字符串、
集合、文件等。
异构的 ——部件有不同类型，如：记录，列表等。
3、用于选取部件的名字
结构类型需要有标识结构中个体部件的选择机制。
对数组，个体部件的名字可以是整数下标或下标序列。
对列表，名字可以是用户定义的标识符。
有的结构，只允许访问特定部件，如栈顶元素。
4、部件的最大数量
对有的变长结构，结构的最大尺寸可以指定。
5、部件的组织
最常见的组织是简单的线性序列，如：向量、记录、字
符串、栈、列表、文件等。
然而，数组、记录和列表类型也可以扩展为多维形式。
多维形式可以看成分别的类型，也可以简单地看成顺
序类型（其元素类型为结构）。
如 A(i,j) 和 A[i][j]的差异。
?数据结构上的操作
结构上操作的定义域和值域规约的方法和基本类型操作
是类似的，但是，有些新的操作类型特别重要。
1、部件选择操作
有两种类型：随机选择 ——可任意选择结构中某一部件
顺序选择 ——以预定好的顺序选择部件。
2、整体数据结构操作
以完整的数据结构为参数，产生新的数据结构为结果。
大多数语言中，这样的整体性操作是有限的。如,
两个数组相加、记录间的赋值、集合的并等。
少数语言提供了大量整体操作，然而，程序员很少去选
择个体部件。如,APL和 SNOBOL4语言。
3、部件的插入 /删除
这种操作将改变部件数量，从而影响存储表示和存储管
理。
2、数据结构的创建 /消除
这类操作将对存储管理有很大影响。
?数据对象中部件或数据值的选择和相关的引用操作是有区
别的。如,V[4]选择 V中第 4个元素，分两步,
先引用（确定 V的位置（ l-值），返回一个指针）,
后选择（得到部件的位置）。
数据结构类型的实现
实现中需要考虑的两个问题：结构中部件的高效选择，以及
高效的存储管理。
?存储表示
结构的存储管理包括：①结构中部件的存储；②可选的描
述子（用于存储结构的属性）。有两种基本表示,
1、顺序表示
结构存放在单个连续块中（包括描述符和部件）。
常用于固定长的结构，有时也用于同构变长结构。
2、链接表示
结构被存放在几个非连续的存储块中，这些块用指针链接
在一起，该指针称为链（ link）。
通常用于变长结构。
两种存储表示方式,
?数据结构操作的实现
大多数结构的实现中，部件选择是最重要的，需要较高
的随机和顺序访问效率。对顺序和链接存储表示，这两
种类型的选择的实现有所不同。
顺序表示
部件的随机访问通常涉及“基地址（完整块的开始位置）
+位移量（部件在块中的相对位置）”的计算。
对一个顺序存储的同构结构, 部件序列的选择按如下步
骤,
1,要选择序列的第一个部件, 使用, 基地址 +位移量, 。
2,要选择下一个部件, 在当前部件位置上加上当前部件
的大小, 对同构结构, 每个部件的大小是相同的 。
链接表示
随机选择需要沿指针链从头查找, 需知道在部件块中链
指针的位置 。
部件序列的选取相对容易, 沿指针向前即可 。
?存储管理和数据结构
当一个对象被绑定到一个特定的存储位置，即：一个存
储块被分配并被初始化，则该对象的生命期开始。而当
绑定解除，则标志生命期结束。
对变长结构而言，其中个体对象有自己的生命期。
数据对象一旦创建，需同时创建它的访问路径，使得对
象可被程序中操作访问。
访问路径的创建方式,
——将标识符（名字）和对象相关联
——存放指向结构的指针于其他可访问的结构中，使
成为其部件元素。
在生命期中，还可能产生其他的访问路径。
如：作为参数传递给子程序
创建一个新指针
访问路径也可以被删除
如：赋新值给一个新指针变量
从子程序返回。
两个存储管理的中心问题,
1、垃圾,
当所有访问路径被消除，但数据对象仍然存在，它将
不可再被访问。因此，其和存储位置的绑定必须解除。
2,Dangling reference：悬空引用。
是一个访问路径，它在关联的数据对象消除后仍然存
在。
这对存储管理是一个严重的问题，因为它可能破坏运
行时结构的完整性，如：修改不相关的数据和修改存
储管理数据等。
数据结构的声明和类型检查
例,Pascal声明,A,array[1…10,-5..5] of real
有如下含义,
1、类型是数组
2、维数为二
3、行下标为整数 1到 10
4、列下标为整数 -5到 5
5、部件数是 110（ 10× 11）
6、部件类型为实数。
这些属性的声明允许 A的顺序存储表示，并可在编译时确定
A中元素的选择访问公式，虽然 A只是在进入子程序时才创
建。
如无声明，则 A的属性只能在运行时动态确定，从而产生在
存储表示和元素访问上的低效。
数据结构的类型检查更为复杂，因为必须考虑元素选择操作。
有两个主要问题,
1、被选择部件的存在性
选择操作的参数可能是类型正确性，但指定的部件可能
在结构中不存在，如：下标越界。
这本身并不是类型检查的问题，通常会产生“例外处
理”。
然而，在没有运行时类型检查和例外处理的情况下，会
产生类似类型检查错的效果。
通常，通过运行时检查确定被选部件是否存在（在用公
式确定其精确左值前）
2、选择部件的类型
静态检查只保证：如果部件存在，则它具有正确类型。
向量和数组
向量由固定数量的同类型部件组成，按简单的线性序组织，
向量部件由下标选择。
向量也称一维数组或线性数组。
二维数组或矩阵，其部件被组织为行、列的矩形格。
?向量
向量的属性包括,
1、部件的数量，通常由一组下标范围隐式地指定。
2、部件的类型，所有部件具有相同的类型。
3、用于选择每个部件的下标，通常是一个整数域，第一
个整数指定第一个部件，第二个数指定第二个部件，依
此类推。下标可以是给出一个值的范围，也可以是只给
出上界，而下界是隐含的。
典型的向量声明,
V, array [1..10] of real; --PASCAL语言
float a[10]; --C语言
如果允许指定下标域，则可以使用枚举为下标，如,
type class = (Fresh,Soph,Junior,Senior)
var ClassAverage,array [class] of real;
向量上的操作,
选择元素的操作通常称为下标操作，如,
V[2],ClassAverage[Soph]
由于下标大都是可计算值，固可用表达式作下标,
V[I + 2]
其它操作包括：向量的创建和消除，向量元素的赋
值，相同大小的两个向量间的算术操作等。通常插
入和删除向量元素是不允许的。
APL是专门基于数组的语言，允许大量向量操作。
实现,由于向量的同构性和固定大小，其存储和访问相
同简单。同构性意味着每个元素的大小和结构相同，固
定大小意味着元素数量及每个元素的位置保持不变。
顺序存储表示是很好的选择，描述子用于存放一些运行
时必要的属性信息。
用于越界检查
元素的随机访问，即向量元素的左值访问公式,
lvalue(A[I]) = ? + (I － LB) × E
这里 ?为基地址,E为元素所占的存储大小。亦即,
lvalue(A[I]) = (? － LB × E) + (I × E)
lvalue(A[I]) = K + (I × E) ----K表示常数
有的语言（如 FORTRAN ）中 K为常量，故可在编译
时计算出来。
即使在有的语言（如 PASCAL）中,K可能发生变化，
也只需要在存储分配时计算一次。
由于 E和 I均是在编译时可知，因此，访问公式的计算
完全可在编译时完成。
如 C语言中，字符数组的 E为 1,LB总为 0，访问公式
为,lvalue(A[I]) = ? + I。
虚原点,
lvalue(A[0]) = (? － LB × E) + (0 × E) = K
即 K为向量中元素 0的地址，如果 0元素存在。如果向
量的下界大于 0，则这个地址称为虚原点 VO。因此，
构建向量并产生访问公式的算法为,
1、向量存储的创建：为 N个大小为 E的向量元素分配
D＋ (N× E),D为描述子的大小。
2、计算虚原点,VO ＝ ? － LB × E
3、访问具体元素,lvalue(A[I]) = VO + I × E
上面公式假定 I为 A的有效下标，即,LB <= I <= UB。
通常越界检查是必须的，因此 LB和 UB应该存放在描
述子中。
如果虚原点也存放在描述子中，则数组和描述子可不
必存放在一起。这是为什么通常描述子作为参数传递
给子程序，而数据的数组却存放在别的地方。
这里描述子类型和
元素类型均未在描
述子中给出。通常,
这些信息在编译时
已知。
打包及未打包存储表示,
通常每个数组元素占用完整的可编址存储单元。但是，
有的类型只占用一个字中的一小部分，此时，需要将
几个向量元素打包存放在在一个编址单元中。打包存
储带来的问题是访问公式更加复杂。
全向量操作,
将向量作为整体的操作是基于顺序存储表示而实现的。
一个向量到另一个向量的赋值即是简单的内容拷贝，
而描述子不需要拷贝。
向量上的算术操作实现为向量中元素循环顺序处理。
全向量操作实现的最大问题是结果的存储。需要临时
分配存储来存放结果的右值，除非它被立即赋给一个
左值位置。
当涉及的全向量操作过多时，临时存储的管理可能会
增加复杂性和成本。
?多维数组
多维数组实际上是一维数组的推广。
规约和语法：和向量在属性上的差别只是需要指定每个
维的下标范围。如,
B, array[1..10,-5..5] of real;
数组元素的选择需给定每一维，如,B[2,4]。
实现：矩阵可以方便地实现为向量的向量，三维数组的
元素是向量的向量，依此类推。所有子向量必须有相同
数量的元素，而且是相同类型。
矩阵是实现为“行之列”还是“列之行”是语境敏感的，
特别是在不同语言的程序间作为参数传递时。最常见的
实现是“行之列”，此即所谓的“行为主序”。
多维数组的存储表示类似于向量。如对矩阵，先存第一
行的数据对象，再存第二行的数据，依此类推。
二
维
数
组
的
存
储
表
示
下标操作及访问公式,
对 M× N的“行为主序”二维数组，有,
lvalue(A[I,J]) = ? + (I－ LB1) × S ＋ (J － LB2) × E
这里 ?是基地址,S是一个行的长度，即
S＝ (UB2－ LB2+1)× E
考虑常量项,VO＝ ?－ LB1× S－ LB2× E
则,lvalue(A[I,J]) ＝ VO＋ I× S＋ J× E
更多维数组,A[L1:U1,…,L n:Un]
1、乘数的计算,mn=e,mi=(Ui+1－ Li+1+1)× mi+1
2、虚原点的计算,VO＝ ?－ ?(Li× mi)
3、数组元素的访问,lvalue(A[s1,…,s n])=VO+ ?(si× mi)
?切片
规约：切片是数组的子结构，也是一个数组。如图,
PL/1中，分别表示为,A(*,2),B(3,*),C(3,*,*)。
FORTRAN77中允许传递数组的部分为参数。由于采用
“列为主序”，传递 A(1,3)到向量 B意味着 A(1,3)到 B(1)、
A(2,3)到 B(2),A(3,3)到 B(3)。
FORTRAN90引入了切片概念，分别表示为,A(1:4,2)、
B(3,1:3),C(3,1:3,1:4)。
实现：描述子的使用使得切片的高效实现成为可能。如：
3× 4数组 A的描述子为,
VO ?
LB1 1
UB1 4
Multiplier1 3
LB2 1
UB2 3
Multiplier2 1
这里 Multiplier2表示数据对象的大小，也是数组中相邻元
素的距离。切片的性质是：一维元素可能不相邻，但距
离一定是相等的。因此，切片 A(*,2)的描述子为,
VO ?－ 2
LB1 1
UB1 4
Multiplier1 3
切片的长度为 4，每个元素相隔三个位置，起始点为 A后
一个位置。
记录
由固定数量的不同类型部件组成。
规约和语法：记录和向量都是定长的线性结构，其不同在于,
1、记录的元素可能是异构的，是不同类型的混合。
2、记录的元素用符号命名，而不是用下标。
C语言中的记录声明为,
struct EmployeeType
{int ID;
int Age;
float Salary;
char Dept;
} Employee;
记录元素的选择,
Employee.ID
Employee.Salary
上述声明中可看出,
1、部件的数量
2、每个部件的数据类型
3、用于命名每个部件的选择子
部件也称域。部件选择是记录的基本操作，但不是使用计
算值，而是使用文字部件名。很少有针对整个记录的操作。
实现：记录的存储表示包含一个顺序的存储块，其中元素
顺序存放。每个元素可能需要描述子去指定它们的数据类
型或其它属性，但通常对记录本身没有运行时描述子。
元素的选择相对容易实现，因为在翻译时域名就已经知道，
记录的声明也使得每个元素的大小和位置在翻译时可确定。
因此，在翻译时可以计算出任意元素的位移量。
基本的访问公式,
Lvalue(R.I) = ? + ?(size of R.j) j=1..I-1
= ? + KI ---KI为元素 I的位移量
有些数据类型的存储必须从特定的地址边界开始。例如，整
数可能必须从字的边界开始存放，对可字节编址的机器而言，
该地址必须能够被 4除。在 C语言中,
struct EmployeeDivision
{ char Division;
int IdNumber; } Employee
如果 IdNumber必须从字边界开始，则在 Division和 IdNumber
间有三个字节未用，称为填料（ padding）。存储表示就好象
如下声明一样,
struct EmployeeDivision
{ char Division;
char UnusedPadding[3];
int IdNumber; } Employee
完整记录的赋值被实现为简单的拷贝。
?含结构元素的记录和数组
如果语言同时提供数组和记录类型，则这两种类型的元
素可能和其它基本类型的元素混杂在一起。如：一个向
量的每个元素都是一个记录，在 C中有如下声明,
struct EmployeeType
{int ID;
int Age;
float Salary;
char Dept;
} Employee[500];
这样一个复合数据结构的元素的选择需要一系列选择操
作，如,Employee[3].Salary。
记录的部件也可以是数组或其它记录，导致记录具有层
次结构。 COBOL和 PL/1中，使用层次编号来语法地指定
这种层次结构。如下是一个 PL/1声明,
1 Employee,
2 Name,
3 Last CHARACTER(10),
3 First CHARACTER(15),
3 Middle CHARACTER(1),
2 Age FIXED(2),
2 Address,
3 Street,
4 Number FIXED(5),
4 St-Name CHARACTER(20),
3 City CHARACTER(15),
3 State CHARACTER(10),
3 Zip FIXED(5);
实现：存储表示类似于简单的数组和记录类型。记录构
成的向量的存储表示相对简单，每个行被记录的存储表
示替代。类似地，记录的记录保持相同的实现结构，但
每个元素是一个子块，子块本身是一个完整记录的表示。
?可变记录（ variant records）
可使用一个记录来表示相似的、但不同的数据对象。这
样的记录类型有几个变体，它们有共同的部分，但各个
变体又有自己独有的部件。如，雇员可以分为按月和按
小时领工资两种情况，从而呈现两个变体。
一个 PASCAL声明如下,
type PayType = (Salaried,Hourly)
var Employee,record
ID,integer;
Dept,array [1..3] of char;
Age,integer;
case PayClass,PayType of
Salaried,(MonthlyRate,real;
StartDate,integer);
Hourly,(HourRate,real;
Reg,integer;
Overtime,integer)
end
PayClass称为标记或
判别子，用于指定被
采用的变体。
变体记录的选择操作和一般记录相同，但由于变体问题，
有的部件的存在性会在运行中发生变化，因此，有的选
择操作可能在运行中某时刻找不到希望的部件，如：
Employee.Reg。这类似于下标越界问题，解决方案为,
1、动态检查：在访问部件前检查标记以保证该部件
存在。如果标记值不对，则出现运行时错。
2、不检查：语言设计可能允许变体记录的定义没有
显式的可在运行时检查的标记，因此，变体记录的部
件选择总被假定为合法的。由于变体记录的实现方式，
这样的选择总是可能的，但是，如果部件不存在，当
前变体的值可能会被不经意地取出或覆写。 C语言中
的 union类型就不允许标记，从而不能提供检查。
具有变体的记录也称为 union类型，可视为一组数据对象
集合的“和”。如果不允许标记，则称为“自由和”类
型（ free-union），如果允许标记，则称为“判别和”类
型（ discriminated-union）。
实现：可变记录的实现比正确地使用它要容易。在翻译
时，每个变体的部件的存储需要量是确定的，存储的分
配根据最大的可能变体来安排。在存储块内，每个变体
根据部件的类型和数量具有不同的布局。布局在编译时
确定，并用于计算被选择部件的位移。运行时，不需要
特殊的描述子。
如果不进行检查的话，变体中部件的选择相同于普通记
录的部件选择。在翻译时，被选择部件在存储块中的位
移被计算出来，在运行时，位移被加到块的基地址上以
形成部件的地址。此时，部件存在与否十分重要，如不
存在，则将取出不是所期望的值，而对该部件位置的修
改也有可能带来灾难性后果。
如果提供动态检查，则先检查标记部件的内容，以保证
标记指示出所需的变体确实存在。
变体记录的存储表示,
List列表
由数据结构的有序序列组成的数据结构 。
规约和语法：列表类似于向量, 都由数据对象的有序序列构
成, 即可以访问列表的第一个元素, 第二个元素, 依此类推 。
它们的不同主要体现在,
1,列表基本上不会固定长度, 通常用于表示任意的
数据结构, 并在运行中增长和缩小 。
2,列表基本上都是异构的, 列表的每个成员的数据
类型均可以不同 。
3,使用列表的语言典型地通过隐式的方式声明这样
的数据, 其成员没有显式的属性 。
LISP语法是典型的列表结构,
(FunctionName Data1 Data2 … Datan)
在 LISP中，大多数操作以列表为参数并返回列表值。如,
(cons ?(a b c) ?(d e f)) = ((a b c) d e f)
LISP的一个重要特征是：所有参数需先计值。如上式写为,
(cons (a b c) (d e f)) = ((a b c) d e f)
则首先计值函数 a，然后计值函数 d，这可能产生错误。
而函数 (quote x)，或‘ x，只返回变量的文字值，从而避
免不适当的计值。
ML属于赋类型的函数语言，因此，其表是同构的。如,[1,
2,3],[a,b,c],[“abc”,“def”,“ghi”]等。
实现：由于列表元素的异构性和大多数列表实现的动态性，
向量、数组所用的存储表示将不适用于列表。通常适用链接
列表存储组织结构。表项是基本元素，通常由固定长度的数
据对象构成。
在 LISP中，通常含有三个信息域：一个类型域，两个表指针。
如果类型域指明为原子，则剩下的域为描述该原子的描述子。
如果类型域指明为表，则第一个指针为表头，第二个指针为
表的尾。
这种表示的中间和底层结构的类似性显示了这种实现方式的
功效,
1,cons,cons或 join操作通过创建一个新表节点而实现，
该节点的头域指向第一个参数，尾域指向第二个参数。
2,head：表的头是表项的头域的内容（右值）。
3,tail：表的尾是表项的尾域的内容。
列
表
的
存
储
表
示
LISP最早是在 60年代早期实现于 IBM704计算机上。该机器
字长为 36位，一个 36位的寄存器可存放两个 18位的地址，
前 18位称为,address register”，后 18位称为,decrement
register”。
因此,head操作是,contents of the address register”，或 CAR；
tail操作是,contents of the decrement register”，或 CDR。
LISP中就使用这两个词来作为头及尾操作。
列表是 ML,LISP和 Prolog等语言中的基本数据对象，但并
不出现在 C,PASCAL或 Ada等编译型语言中。
维护列表所需要的动态存储管理和编译型语言中的高效存
储管理是不一致的。
然而，使用编译型语言的程序员仍然可以访问列表，但是，
必须将其作为程序员定义的数据类型。
?列表的变种
栈和队列：栈是一种列表，其中部件的选择、插入和删
除被限制在一端进行。队列的部件选择和删除被限制在
一端，而插入被限制在另一端。
树：其中的部件可以是列表以及基本数据对象，而每个
列表只能最多是另一个列表的部件。大多数 LISP例子实
际上是树。
有向图：其中的部件可以被任意的链接模式链接在一起，
而不仅仅是线性序。
性质表：具有可变数量部件的记录通常称为性质表，如
果部件的数量可以无限变化。在性质表中，部件名及其
值均需被存储，分别称为性质名和性质值。性质表通常
表示为链接表。
性
质
表
的
存
储
表
示
字符串
字符串是一个字符构成的序列。几乎所有的语言均有字符串
类型。
规约和语法：至少有三种不同的字符串类型处理方式,
1、固定声明长度。在程序中声明字符串对象的固定长度。
赋给该对象的值总是该长度的字符串。新串值赋给该数
据对象将导致长度调整：减短或补足。 PASCAL和
COBOL中常采用此技术。
2、有界变长。字符串数据对象具有固定的最大长度，但
实际的字符串值长度可以小于此，甚至是空串。执行过
程中，字符串长度会发生变化，但超长时需减短。
3、无界长度。字符串数据对象可以具有任意长度，而且
长度可以在执行过程中动态地无界变化。
前两种方法允许翻译时确定每个字符串数据对象的存储分配。
第三种方法需要存储的运行时动态分配。
一些重要的字符串操作,
1、串联。将两个字符串连接在一起以形成一个长串。如：
,BLOCK”||“HEAD”产生,BLOCKHEAD”。
2、串上的关系操作。包括一般的相等、大于、小于等均
可用于字符串。由于字符本身是有序的，因此可以扩展形
成字符串的字典序。
3、使用定位下标的子串选择。很多语言提供了选择子串
的操作。如,FORTRAN中,NEXT ＝ STR (6:10)将 STR中
从位置 6到 10的 5个字符赋给 NEXT。如果允许子串选择出
现在赋值的两边，则其语义必须仔细定义。
4,I/O格式。字符串上的操作经常被提供以帮助输出数据
的格式化或将格式化的输入流分界成小的数据单元。如：
C和 FORTRAN中的格式化 I/O特性。
5、使用模式匹配的子串选择。由于不知道子串在大串中
的位置，模式匹配则成为一种重要的方法。如：
SNOBOL4就提供了强大的模式匹配操作。
实现：三种不同的方法使用不同的存储表示。对固定长度的
字符串操作可以有硬件支持。其它方式则需要软件仿真。
指针及程序员构造的数据对象
通常，不是引入一系列可变长的链接数据对象类型，而是提
供设施来允许使用指针链接对象而相连结构，这样需要如下
几个语言特性,
1、基本数据类型－指针（ pointer），也称引用或访问类型。
指针对象包含另一个数据对象的位置（左值），空指针
为 nil或 null。
2、定长数据对象的创建操作
创建操作分配一个存储块，并返回其左值，可用于存放
对象的右值。这种创建操作和声明创建方式有两个差别,
a.数据对象不需要名字
b.可在程序执行中任何位置创建
3、取引用操作
允许跟随指针到其指向的对象。
规约：指针数据类型定义一类数据对象，它们的值是其它数
据对象的位置。指针类型的对象有两种处理方式,
1、指针只能引用单个类型的数据对象。
如 C,PASCAL和 Ada等语言，需要进行指针类型声明
和相应的静态类型检查。
2、指针可以引用任意类型的数据对象。
如,SMALLTALK语言，数据对象本身带有描述子，
需要进行动态类型检查。也可以不进行类型检查。
创建操作为一定长数据对象分配存储空间，并创建指向该新
数据对象的指针，该指针可以存放到指针数据对象中。如：
PASCAL和 Ada中的 new,C中的系统函数 malloc。
选择操作允许跟踪指针值以达到指定的数据对象。因为指针
是普通的数据对象，指针数据对象本身也可以用一般的选择
机制。如,*用于取指针的右值，并将其变成左值，用左值访
问数据。
实现：指针数据对象被表示为存储位置（包含另一个存储位
置的地址，该地址是表示该指针指向的数据对象的存储块的
基地址）。指针值的两种存储表示,
1、绝对地址：指针值可以表示为数据对象所在存储块的
实际存储地址。
2、相对地址：指针值可以表示为从某基地址开始的位移
量。数据对象是被分配在一个大的存储堆中。
当使用绝对地址时，有创建操作创建的数据对象可以分配在
存储中任意地方，通常，该分配发生在一个存储堆区域中。
使用绝对地址的选择操作将更为高效，因为指针值提供了直
接的访问。缺点是存储管理更为困难，因为数据对象不能随
意在存储中移动，存储的回收必须逐个进行。
使用相对地址需要一个存储块的初始分配，可以是每种类型
各有一个区域，也可以是所有数据对象共有一个区域。每个
区域管理为一个堆。缺点是选择操作需要更大的代价，优点
是存储块可以整体任意移动，整个区域可以处理为一个数据
对象。
集合
集合是一个数据对象，它包含不同值的无序集合。而列表中
元素是可以重复的。集合上的基本操作有,
1、成员关系,X是否为 S中的成员？ X?S？
2、单个值的插入和删除。如果 X不是 S中的成员，则可
以插入 X；如果 X是 S中的成员，则可从 S中删除 X。
3、并、交和差。
集合中成员的访问不能使用下标或相对位置。
实现：在程序设计语言中，术语集合有时是指表示有序集合
的数据结构。一个有序集合实际上是一个列表，只是不允许
元素的重复。对此不需要特殊的考虑。而无序集合则需要两
种不同的存储表示。
集合的位串表示,
位串存储表示适合于已经知道集合元素域的大小较小的情
形。假定在域中有 N个元素，这些元素任意排序为 e1、
e2,…, eN，从该域选择出的一组元素可以用长度为 N的
位串来表示，其中，如果 ei存在于集合中，则串的第 i位为
1，否则为 0。
位串表示了集合的特征函数。元素的插入表现为相应位的
设置，元素的删除表现为相应位的清除，成员关系判断表
现为检查相应位，并、交及差的操作可实现为位串上的布
尔操作，通常有硬件支持。
如果提供了对位串操作的硬件支持，则集合的位串表示的
操作将是非常高效的。然而，硬件操作通常仅仅应用到某
固定长度的位串（如：字的长度）。如果串的长度大于最
大值，则软件仿真将是需要的，用于将位串分为较小的、
可被硬件直接操作的单元。有的语言为此而限定集合的大
小。
集合的 HASH编码表示,
另一种常见的集合表示方法为 HASH编码或散列存储。该
方法可以用于集合的域较大时。
该方法可允许集合的成员测试、插入、删除高效地完成。
然而，并、交及差等操作效率不高，必须实现为一系列
个体元素的成员测试、插入、删除等操作。
为了有效,HASH编码方法需要实质性的存储分配。
最常见的是，语言并不向用户提供集合数据类型的这种
表示方式，但语言的实现在翻译或执行中使用这种表示
来实现一些系统定义的数据。
如，大多数 LISP实现使用这种存储表示来实现名为 object
list的集合，它包含 LISP程序执行中所有原子数据对象的
名字。
几乎所有的编译器使用 HASH编码来查找符号表的名字。
在一个向量中，每个下标指定一个唯一的部件，可以使用
简单的访问函数来达到该目标。
HASH编码的目标就是要尽可能地达到这样的效果。问题
是：潜在的合法名字的集合相对于可用的存储而言是大的。
如果我们分配 HASH表至少为我们所期望使用的两倍大，
则 HASH编码将是非常高效的。
不是将集合中元素顺序地存放在存储块中，而是将元素随
机地散列在块中。其技巧在于以这种方式存放每一个元素，
而其存在与否在以后将可以立即地确定，而不需要搜索整
个存储块。
考虑加入元素 X到集合 S，位串 Bx表示 X，存储块 Ms表示 S。
应用 HASH函数到 Bx得到 Bx在 Ms中的位置 Ix，称为 HASH
地址，用为指向块中位置的索引。如果 X不在 S中，则 Bx
将被存入到 Ms中由 Ix指定的位置。 X的查找是方便的，提
供使用同样的 HASH函数可找到其在 Ms中的位置。
对 HASH函数的要求一是计算速度，二是分布的随机性。假
定 Ms为 1024个字，需要存放的数据项是表示为双字位串的字
符串，则我们可以表示一个可含 511个不同元素的集合。假
定块的起始地址为 ?，一个合适的 HASH地址将是 9位的串 Ix，
因为公式 ?＋ 2× Ix将总是产生在块内的地址。 Ix由 Bx产生，
假定 Bx存放在字 a和 b中。
1,a乘以 b，得到 c（两个字长）
2、将 c的两个字相加，得到 d（一个字长）
3、将 d平方，得到 e
4、取 e的中间 9位，得到 Ix
即使最好的 HASH函数也不能保证对不同的数据项产生不同
的地址。几乎不可避免地会产生冲突。
处理冲突的解决办法,
1、重新 HASH。可以考虑修改初始的位串 Bx，如：乘以
某常量。然后重新 HASH。直至无冲突为止。
2、顺序扫描。从块中的冲突点开始进行顺序搜索，直至
找到某 Bx，或遇到一个空位置。
3、使用桶（ bucketing）。在块中的位置上用一个指针来
指向具有相同 HASH地址的一个链接桶表。
不同的 HASH函数合适于不同的将被存放的位串表示。如果
有一个好的 HASH函数，且表是半满的，则冲突较少发生。
前面例子中 512个项只用了 511个的原因就是为了解决冲突。
可执行数据对象
大多数语言中，可执行源程序和其操作数据是分开的。而有
的语言，可执行语句可以是数据，也可被程序访问。如：
LISP将所有数据存放在表中。
（ define myfunction (cons (abc) (def))）
这里 myfunction是可执行的数据对象。
Prolog中也有类似情况。
文件和 I/O
文件是一种数据结构，具有两个特殊性质,
1、通常表示在外存上，比其它数据类型也要大得多。
2、生命期长，通常会跨越创建它的程序的生命期而存在。
顺序文件是最常见的文件类型。很多语言也提供直接访问文
件和索引顺序文件。
文件的两种常见用途,
针对外部操作环境的数据输入和输出。
作为数据的临时存储，以解决高速内存不足的问题。
文件的部件称为记录。但有别于我们前面所提到的记录类型。
顺序文件,
顺序文件是相同类型部件的线性序列，其长度可变且没
有固定的最大上界。（当然，受外存大小限制）
一个典型的 PASCAL声明,
Master,file of EmployeeRec;
文件部件的类型可以是基本类型，也可以是结构类型。
通常是定长的。此外，文件记录不应该为链接表示，不
允许含指针值。
为了输入、输出，数据通常被表示为字符形式，这样一
个文件的部件为单个字符，此即所谓文本文件，是一种
特殊的顺序文件。
文件的访问可以是读写两种模式。文件位置指针用于指
定文件中位置，或者是第一个文件部件之前，或者是两
个文件之间，或者是最末一个文件之后。
规约：顺序文件上的主要操作有,
1、打开（ OPEN）。给定文件名及访问模式，从操作
系统获取文件的位置和性质信息，分配所需的内存作
为缓冲及存放其它信息，设置文件位置指针到合适位
置。打开操作可以是显式的或隐含的。
2、读。将当前文件部件的内容存放到指定变量。可
以是程序员定义的变量，也可以是缓冲变量。
3、写。在文件的当前位置创建一新部件，并将指定
变量的内容写入该部件。
4、文件尾测试。 eof测试是必需的，以避免读操作的
不恰当使用。
5、关闭（ close）。通知操作系统文件可以从程序分
离，文件所占的内存可以释放。通常，程序的执行终
止将隐式地关闭文件。
实现：在大多数计算机系统中，主要是底层操作系统负责
文件的实现。特定的语言仅仅负责必要的局部数据结构以
和操作系统接口。文件操作通过调用操作系统提供的原语
而实现。
从语言的角度，主要的实现问题是：系统数据和缓冲的存
储。当打开文件时，必须提供文件信息表和缓冲的存储。
操作系统的 open原语存储文件的位置和特征信息到文件信
息表中，缓冲用于队列的顺序表示。
文件的读写操作由操作系统原语针对缓冲区进行。当所有
操作完成后才成块转存到外存中。
使用缓冲的文件表示
文本文件,
文本文件是字符的文件，是大多数语言 I/O的主要文件形式。
文本文件可以被打印，以及通过计算机键盘输入来创建。
文本文件可以按顺序文件的方式被操作，但也提供了一些
特殊的操作，如：一些数值数据在输入过程中被自动地转
换成内部存储表示，而不需要存为字符形式。也允许在输
出时将内部表示直接转换为字符形式。
此外，还提供了输入、输出格式的操作。
交互式输入－输出,
考虑一文本文件表示一交互终端，“写”命令在终端上显
示字符，“读”命令从键盘请求数据（通过提示符表示）。
那么,
1、文件必须同时处于“读”和“写”模式，通常读和
写交替进行。
2、数据输入 /输出的缓冲是有限的。
3、文件位置指针和文件尾测试相对意义不大。
直接访问文件,
可以随机访问文件中的单个部件，用于选择部件的下标称
为“键”，可以是整数或其它标识符。
部件的组织是无序的，每个部件关联一个键值。键值通常
和位置关联，形成一个“对”。“对”的向量序列称为索
引。
索引顺序文件,
类似于直接访问文件，同时具有顺序访问部件的机制，从
随机选择的一个部件开始顺序访问。
文件的组织是纯的顺序方式和纯的直接访问方式的折中。
索引顺序文件需要键值的索引，但是，在索引中的项必须
根据键值排序。
文件位置指针指向当前部件位置。
