第五章数据类型

第五章数据类型1任何程序，不管以何种语言写成，均可以视为刻划了一个操作集合。并将以一定顺序作用到一定数据上。语言的基本不同在于：允许的数据类型允许的操作类型控制操作顺序的机制。2本章主要内容数据类型的基本概念及相关属性基本数据类型复合数据类型35.1类型和对象的性质数据对象、变量和常量数据类型及其规约简单数据类型的规约与实现数据对象的声明类型检查和类型转换数据对象的初始化4数据对象计算机的数据存储在结构上是简单的，通常是由位串构成的字节。而语言虚拟机的数据存储则有更复杂的组织，如：数组、栈、数、字符串、以及其它存在于程序执行中不同点的数据。我们称虚拟机上一个或多个数据片断运行时的组合为数据对象。5数据对象在程序运行中，存在许多不同类型的不同数据对象。这些对象及其相互关系在运行时动态变化。有些数据对象是程序员定义的，如变量、常量、数组、文件等。程序员通过声明和语句显式地创建和操作它们。有些数据对象是系统定义的，不可为程序员直接访问。如：运行时存储栈、子程序激活记录、文件缓冲、自由空间列表等。这些数据对象在运行需要时自动产生，不需要时删除。6数据对象标量数据对象:Numeric(Integers,Real)BooleansCharactersEnumerations复合对象:StringPointer结构化对象:ArraysRecordsListsSets抽象数据对象:Classes活动对象:TasksProcesses7数据对象数据对象表示了数据值的一个容器，是值被存放和检索的地方，而数据值是在存储器中以一种特定的位模式表示。数据对象和数据值在大多数语言中均是明确区分的，如图所示。8数据对象每个数据对象有生命期，在生命期内可用来存放数据值。数据对象可分为简单数据对象和数据结构数据结构—其他数据对象的聚集。数据对象在其生命期中涉及各种绑定，虽然其属性不变，但绑定可动态改变。9数据对象：属性和绑定重要的属性和绑定有：1、类型通常在程序翻译时，关联数据对象和它可能的取值集合。2、位置通常不由程序员规定，而是系统存储管理负责。3、值由赋值操作完成绑定。4、名通常在声明时完成绑定，但可被子程序调用和返回修改5、部件通常用指针值相连，可通过指针的修改而变动。返回10变量和常量程序员通过变量来显式地定义和命名数据对象。一个简单的变量是有名字的简单数据对象，其内容可以发生变化。常量是具有名字的数据对象，其值在其生命期内永久不变。一个文字（或文字常量）是一个常量，其名是其值的书写表示，如21表示值为21的整数常量。程序员定义的常量——其名字由程序员指定。常量的绑定由编译器完成。如C语言中，#defineMAX20语句MAX=4是非法的。返回11数据类型一个数据类型是一类数据对象加上创建及操作它们的一组操作。每个语言有一个基本数据类型集合，是语言固有的。有的语言还提供了设施允许程序员定义新数据类型。有的新语言还允许类型本身被语言操作（高阶能力）。每个数据类型都包括对其相关性质的规约以及在计算机中的具体实现12数据类型的规约数据类型的规约包括：1、区分该类型的数据对象的属性2、该类型数据对象可具有的值3、定义该类型数据对象可能处理的操作例如：数组数据类型的规约属性：维数、每维的下标范围、元素的数据类型等。值：形成数值元素有效值的数的集合。操作：选择个体数组元素、创建数组、改变数组形状，访问下标上下界、完成数组间的算术操作等。返回13数据类型的实现数据类型的实现包括：1、存储表示：用于在计算机存储器中表示数据对象。2、数据类型操作是以特殊的算法或过程表示的方式，这些算法和过程操纵数据对象的存储表示。返回14数据类型的规约与实现从语法表示来看，规约和实现大体上独立于特定的语法形式。属性：表示为声明或类型定义值：表示为文字或定义的常量操作：可由特殊的符号、固有过程或函数、或隐含地通过其他语言元素的特殊组合来调用。15基本（简单）数据类型的规约简单数据对象包含单个数据值，这类数据对象称为基本数据类型。虽然不同的语言有不同的基本类型集合，但整数、实数、字符、布尔、枚举、指针等基本都是有的。但各自精确的规约对不同语言会有差异。16简单数据类型的规约：属性数据对象的基本属性（如类型和名字）通常在生命期中是不变的。有的属性可存放在描述子中，作为数据对象的一部分在运行时出现。有的属性只用于确定其存储表示，在执行中不显式地出现。属性值和数据对象的值是不同的。17简单数据类型的规约：值数据对象的类型确定了它可包含的可能值集，但在执行中任一点，只包含一个来自该集合的单值。基本数据类型定义的值集通常是有序集，有最小值和最大值。18简单数据类型的规约：操作(1)操作确定数据对象被处理的方式。操作可能是原始操作，也可是用户定义操作。操作是一个数学函数，对一给定输入参数，有定义的、唯一确定的结果。每个操作有作用域、值域。操作的动作定义了对给定参数的结果。算法可用于刻划操作的动作，但其他规约也是可以的。如可用乘法表来刻划乘法的动作。19简单数据类型的规约：操作(2)操作的基调（signature）——定义了操作的作用域中参数的数量、顺序和类型，以及结果值域的顺序和类型。数学记号：OP：type1×type2×…typentype—也称为函数原形操作有单元、二元和多元。动作的精确规约需要比参数类型更多的信息。特别地，参数类型的存储表示通常确定那些参数如何被操作，如：二进制数的乘法和十进制数的乘法有很大不同。这样，在操作的规约中，常给出动作的非形式的描述。一旦参数的存储表示确定，动作的精确规约是操作实现的一部分。20简单数据类型的规约：操作(3)有时难于确定操作的精确规约为数学函数，有四个主要因素。1、操作对某些输入无定义。2、隐含的参数——操作会访问其他隐含参数（全局变量；非局部变量）。3、副作用（隐含结果）——可能修改其他数据对象。4、自我修改（历史敏感性）——操作修改自己的内部结构、或是执行中保持的局部数据、或是代码。操作的结果还依赖于历史调用。例：随机数产生器。LISP中可自我修改代码。21基本数据类型的实现存储表示基本类型的存储受低层计算机的影响很大。如：整数或实数几乎就是在低层硬件中使用的数的整数或浮点数表示。对字符值，硬件或操作系统字符码被使用。基本理由：如使用硬件存储表示，则该类型数据基本操作可以用硬件提供的基本操作实现。否则，将使用软件仿真，从而带来效率损失。22基本数据类型的实现基本数据类型的属性被类似地处理。1、为了效率，很多语言设计为属性由编译器确定。属性本身并不存放在运行时存储表示中——存储表示通常直接使用硬件，如：C、Fortran、Pascal等。2、数据对象的属性可存放在描述子中作为运行时数据对象的一部分，如：LISP、Prolog等，这里灵活性是主要目标。通常硬件不提供对描述子的直接表示。数据对象的表示通常独立于存储位置，这样给定类型的每个对象有相同的表示（除位置不同），通常用需要的内存块的尺寸（大小）来描述，同时也涉及属性和值在块中的布局。通常内存块的每一个字或字节的地址用于表示数据对象的位置。23基本数据类型的实现操作的实现1、直接作为硬件操作如：整数表示为硬件整数，+，－也直接用硬件实现。2、作为过程或函数子程序如：平方根操作。如数据对象不使用硬件表示，则所有操作必须是软件仿真，通常以子程序的形式。3、作为In-line（内嵌）代码序列。这也是操作的软件实现形式，但不是使用短小的子程序，而是将子程序中操作代码拷贝到程序中的调用点。返回24数据对象的声明编写程序时，程序员确定数据对象的名字和类型。还要确定：生命期、在程序中的活动范围、相关操作等。声明：一种程序语句，告知语言翻译器关于数据对象的信息。如声明语句放在特定的程序或类定义中，则指明了对象希望的生命期。声明可以是显式的，也可以是隐含的或缺省的。声明可以为数据对象赋上初始值，也可指定常量值。25数据对象的声明操作的声明翻译时需要的关于操作的信息，主要是其基调signature。对基本操作，不需显式的参数类型和结果类型声明，是语言中固有的。对程序员定义的操作，则必须指定之。如：sub:int×float→float

=>floatSub(intx，floaty)26声明的目的1、选择存储表示声明可以给语言翻译器提供关于数据类型和数据对象属性的信息，使得翻译器可以确定数据对象的最佳的存储表示，从而减少整体的存储需求和被翻译程序的执行时间。2、存储管理——声明使其更为高效声明可以提供关于数据对象生命期的信息，从而使得在程序执行过程中进行更高效的存储管理。如：在C语言中，在子程序头部声明的数据对象有相同的生命期，这样可以在进入子程序时分配一个整体的块来存放所有的数据对象，而在退出子程序时释放。其它动态创建的数据对象则需单独处理。27声明的目的3、多态操作——包括重载和真正多态大多数语言均使用特殊的符号来表示一组不同的操作，具体操作的选择将依赖于参数的数据类型。此即所谓重载。如：＋可以是整数加、实数加，甚至可用于字符和字符串操作。重载是一个在语法层次上处理的概念。由编译器处理。真正的多态通常是语义级别的概念，操作符的具体动作的确定是在运行时进行。如：函数语言中，类型可以作为参数带入，从而使函数的动作的选择依据类型实参而确定。恒等函数就是典型的多态。面向对象的继承机制也提供了所谓的包含多态性，即子类的对象可用于父类对象出现的地方。4、类型检查——最重要的目标，属语义检查，目标是排错，分静态或动态类型检查。类型检查提供了很好的防止错误的机制。返回28类型检查和类型转换计算机硬件固有的数据存储表示通常不含类型信息。数据上的基本原始操作也不需类型检查。如一个位串：111001……0011可能是整数、实数、字符串、或指令，没有办法来区分。硬件提供的基本操作（如加法），不能检查其参数是否为整数，他们仅仅是位串。汇编语言或机器语言编程中常见的错误源于错误的操作类型，这种错误难于发现，因为操作并不以明显的方式失败。操作可进行，但结果没有意义。有时这种错误可在连续的一串操作后出错，有时程序停止也不出错。29类型检查类型检查：指检查程序中每个操作均接收了正确数目的正确类型参数，可在运行时完成，即动态类型检查；或编译时检查，即静态类型检查。高级语言的主要优点之一：可提供对所有（或几乎所有）操作的类型检查。30动态类型检查需类型标志，不需对变量声明（即变量是无类型的）。优点：编程的灵活性。程序员不需考虑类型问题，具有较高灵活性。缺点：程序难于调试，不能完全消去所有参数类型错误。程序测试不可能检测所有的路径。需要在执行过程中保持类型信息，需存储空间。动态检查需以软件实现，有时间花销。31静态类型检查需要的信息通常由程序员在声明中及在其他语言结构中提供。需要：1、对每个操作，其参数的数量、顺序、类型及结果类型。2、对每个变量，被关联的命名数据对象的类型。3、每个常量数据对象的类型。编译器在翻译的早期阶段收集声明中的类型信息，以后将用于类型检查。静态检查涉及语言的多个方面：声明、数据控制结构、分开编译等。32静态与动态类型检查静态检查将针对程序中的所有操作进行，所有可能的执行路径均被检查。因此，关于类型错误的进一步测试是不需要的，因而不需类型标记和运行时类型检查。在多数语言中，对某些语言结构的静态检查在某种情况下是不可能的。解决方案：采用动态类型检查或不检查。33类型检查强类型如果我们可以静态地检测程序中的所有类型错误，则称语言是强赋类型的。通常类型为程序提供了一个安全层次。一个函数f:S→R称为类型安全的，如果f的执行不会产生R以外的值。类型安全的操作均不需动态检查。很少有语言是真正强类型的。类型推导如果解释不会出现二义性，则类型声明可以省去。可由语言实现推导出失去的类型信息。34类型转换和类型的强制转换如果在类型检查中，参数的实际类型和操作期望的类型间出现不匹配，则有两种处理方案：1、指出出错2、通过强制（隐式的类型转换）来改变实际参数的类型为正确类型。类型转换的基调为：conversion-op:type1→type2将一个对象变为另一类型的对象。大多数语言以两种方式提供类型转换：1、作为固有函数，程序员可显式地调用。如：将实数变成整数，Pascal中的round，C中的(int)x2、作为强制，自动在类型失配时调用。如：整数和实数间相加，总是先将整数转变为实数。35类型转换和类型的强制转换强制的基本原则是不失信息。这类强制称为widening或promotion。如强制会丢失信息，则称为变窄（narrowing）类型转换可能需要数据对象在运行时存储表示的改变，如：COBOL和PL/1中，数值以字符串方式存放，要相加需先转换，结果又要转换为字符串。有的语言中不提供类型强制，类型不匹配即被视为出错。而有的语言则尽可能在不匹配时采用强制（如C）。返回36赋值和初始化赋值是一基本操作，改变值到数据对象的绑定，这个改变是操作的副作用。有的语言中，赋值语句也返回值（作为表达式处理），该返回值包含被赋值拷贝的数据对象。Pascal中，赋值的规约为：Assignment(:=):integer1×integer2→eger2值赋给integer1无显式返回。C中，规约为：Assignment(=):integer1×integer2→integer3integer2值的拷贝赋给integer1，同时创建并返回包含integer2值的新数据对象integer3.37赋值考虑赋值X:=X右边的X称右端值，用于引用包含在命名数据对象中的值，r-值。左边的X用于引用将包含新值的数据对象的位置，称为左值，l-值。赋值操作定义为：1、计算第一个操作数表达式的左值（存储位置）。2、计算第二个操作数表达式的右值。3、将右值赋给左值对象。4、返回右值作为操作的结果。38赋值赋值的两个不同视角(A=B)39初始化未初始化变量（或未初始化数据对象）是一个数据对象，已被创建，但未赋值，即有l-值，但没有r-值。创建对象仅涉及存储块的分配，块中原有位模式不会改变。有的语言创建时不需初始化，初始化是在以后显式地通过赋值进行的。也可以在变量声明时进行显式的初始化工作，此时，需要编译器产生相应的赋值代码并插入到目标程序中。在变量声明后立即进行初始化工作是程序员应有的良好习惯之一。有的语言，创建时自动初始化（隐式初始化）。未初始化变量是程序错误的重要原因之一。返回405.2基本数据类型整数浮点实数定点实数枚举布尔41数值数据类型：整数规约：整数类型的对象除了其类型外，通常没有其它属性。该类型的整数值的集合形成了数学中研究的无限整数集的一个在有限界内的有序子集。最大整数值有时被表示为一个定义的常量，如：PASCAL中的maxint，其实际值由语言实现者根据具体的计算机硬件确定。C语言有四种不同的整数规约：int、short、long、char。42数值数据类型：整数（操作）整数数据对象上的操作：算术操作：二元算术操作的规约为：BinOp:integer×integer－>integer二元操作包括：＋、－、×、/、mod等。一元算术操作的规约为：UnaryOp:integer－>integer一元操作有：－、＋、以及其它，如：绝对值。43数值数据类型：整数（操作）关系操作：RelOp:integer×integer－>Boolean关系操作有：大于、小于、相等、不等、等等赋值：assignment:integer×integer－>voidassignment:integer×integer－>integer位操作：也分二元和一元。如：&、|、<<（移位）等。44数值数据类型：整数（实现）语言定义的整数数据类型经常使用硬件定义的整数存储表示和硬件提供的算术及关系操作来实现。通常使用一个完整的字来存储一个整数。三种可能的整数存储表示：需声明及静态类型检查，如C、FORTRAN等语言仍可使用硬件提供的算术操作省空间，但需附加的操作处理返回45数值数据类型：浮点实数(规约)通常规约为单个类型属性real或float，形成一个从硬件确定的最小负数到最大数的有序序列，但其值不是均匀地散布在这个范围内。此外，有的语言中，浮点数所需精度，即其所用的十进制位数，可由程序员来确定。实数具有和整数相同的算术、关系和赋值操作，但布尔操作有时会受限。由于进位的关系，实数间的相等是很难达到的，因此使用实数相等为判定条件必须慎重。此外，大多数语言提供一些固有函数作为实数上的其它操作：Sin:real－>realMax:real×real－>real46数值数据类型：浮点实数(实现)浮点实数的存储表示通常基于底层的硬件表示，其中存储位置被分为尾数和指数。在大多数语言实现，IEEE标准754被用为浮点数定义的标准。有单精度和双精度浮点数之分。二者通常由硬件算术操作支持其加、减、乘、除，而求幂操作通常由软件仿真。如果同时支持单精度和双精度，则必须给予程序员相应的声明机制。返回47数值数据类型：定点实数(规约)大多数硬件包含了整数和浮点数对象，然而，有很多应用需要特定的有理数，如：表示钱的元和分的数据对象。这些数不能写成整数或浮点数。因此，需要定点数。定点数表示为固定长度的数位，在给定位置为小数点。如，COBOL语言中，有如下声明：

XPICTURE999V9948数值数据类型：定点实数(实现)定点实数可直接由硬件支持或用软件仿真。如PL/1中，DECLAREXFIXEDDECIMAL（10，3），

YFIXEDDECIMAL（10，2），

ZFIXEDDECIMAL（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)，SF为小数点位置49数值数据类型：实数的不同表示实数1.5的不同表示返回50基本数据类型：枚举类型我们通常希望一个变量只在一组符号值中选一值。如：变量StudentClass只有四种可能值：freshman,sophomore,junior,和senior。当然，可以用整数来代表这四者，但必须由程序员来维护这类变量的操作安全性及使用的类型正确性。规约：枚举是一个不同值的有序列表，由程序员确定其文字名及它们的顺序。如C中：

Emun

StudentClass{Fresh,Soph,Junior,Senior};

Emun

EmploySex{Male,Female};51基本数据类型：枚举类型(实现)枚举类型的基本操作为关系操作、赋值，以及后继和前驱。实现：枚举类型数据对象的存储表示是直接的，在枚举序列中的每个值在运行时被表示为整数，通常为0、1、2、…之一。有的语言也可由程序员指定值。枚举类型上的操作的实现也是直接的，直接使用硬件提供的基本操作。返回52基本数据类型：布尔类型大多数语言提供数据类型表示true和false，通常称为布尔或逻辑类型。规约：布尔类型的数据对象取二值之一。在某些语言中，可将其考虑为语言定义的枚举类型。

TypeBoolean=(false,true);其顺序为false<true。布尔类型对象上的操作为一般的逻辑操作。53基本数据类型：布尔类型(实现)实现：布尔数据对象的存储表示是一个二进制位。通常，为了可以直接访问，而表示为单个可编址单元。用一个特殊位来表示，0为假，1为真。或者，0为假，其余非零值为真。也有其它数据类型可用于布尔型的表示，而C中没有布尔型。返回545.3复合数据类型字符串指针文件55字符串字符串是一个字符构成的序列。几乎所有的语言均有字符串类型。规约和语法：至少有三种不同的字符串类型处理方式：1、固定声明长度。在程序中声明字符串对象的固定长度。赋给该对象的值总是该长度的字符串。新串值赋给该数据对象将导致长度调整：减短或补足。PASCAL和COBOL中常采用此技术。56字符串2、有界变长。字符串数据对象具有固定的最大长度，但实际的字符串值长度可以小于此，甚至是空串。执行过程中，字符串长度会发生变化，但超长时需减短。3、无界长度。字符串数据对象可以具有任意长度，而且长度可以在执行过程中动态地无界变化。前两种方法允许翻译时确定每个字符串数据对象的存储分配。第三种方法需要存储的运行时动态分配。57字符串：操作(1)1、串联将两个字符串连接在一起以形成一个长串。如：“BLOCK”||“HEAD”产生“BLOCKHEAD”。2、串上的关系操作包括一般的相等、大于、小于等均可用于字符串。由于字符本身是有序的，因此可以扩展形成字符串的字典序。3、使用定位下标的子串选择很多语言提供了选择子串的操作。如：FORTRAN中，NEXT＝STR(6:10)将STR中从位置6到10的5个字符赋给NEXT。如果允许子串选择出现在赋值的两边，则其语义必须仔细定义。58字符串：操作(2)4、I/O格式程序设计语言中提供的某些字符串操作常常是为了帮助输出数据的格式化或将格式化的输入流分界成小的数据单元。如：C和FORTRAN中的格式化I/O特性。5、使用模式匹配的子串选择由于不知道子串在大串中的位置，模式匹配则成为一种重要的方法。如：SNOBOL4就提供了强大的模式匹配操作。59字符串：实现三种不同的方法使用不同的存储表示。对固定长度的字符串操作可以有硬件支持。其它方式则需要软件仿真。返回60指针通常，不是引入一系列可变长的链接数据对象类型，而是提供设施来允许使用指针将数据对象链接在一起而形成某种结构，这样需要如下几个语言特性：1、基本数据类型－指针（pointer），也称引用或访问类型。指针对象包含另一个数据对象的位置（左值），空指针为nil或null。2、定长数据对象的创建操作创建操作分配一个存储块，并返回其左值，可用于存放对象的右值。这种创建操作和声明创建方式有两个差别：a.数据对象不需要名字b.可在程序执行中任何位置创建3、取引用操作允许跟随指针到其指向的对象。61指针数据类型：规约指针数据类型定义一类数据对象，它们的值是其它数据对象的位置。指针类型的对象有两种处理方式：1、指针只能引用单个类型的数据对象。如C、PASCAL和Ada等语言，需要进行指针类型声明和相应的静态类型检查。2、指针可以引用任意类型的数据对象。如：SMALLTALK语言，数据对象本身带有描述子，需要进行动态类型检查。也可以不进行类型检查。62指针数据类型：操作创建操作为一定长数据对象分配存储空间，并创建指向该新数据对象的指针，该指针可以存放到指针数据对象中。如：PASCAL和Ada中的new，C中的系统函数malloc。选择操作允许跟踪指针值以达到指定的数据对象。因为指针是普通的数据对象，指针数据对象本身也可以用一般的选择机制。如：*用于取指针的右值，并将其变成左值，用左值访问数据。63指针数据类型：实现指针数据对象被表示为存储位置（包含另一个存储位置的地址，该地址是表示该指针指向的数据对象的存储块的基地址）。指针值的两种存储表示：1、绝对地址：指针值可以表示为数据对象所在存储块的实际存储地址。2、相对地址：指针值可以表示为从某基地址开始的位移量。数据对象是被分配在一个大的存储堆中。64指针数据类型：实现当使用绝对地址时，由创建操作创建的数据对象可以分配在存储区中的任意地方，通常，该分配发生在一个存储堆区域中。使用绝对地址的选择操作将更为高效，因为指针值提供了直接的访问。缺点是存储管理更为困难，因为数据对象不能随意在存储中移动，存储的回收必须逐个进行。使用相对地址需要一个存储块的初始分配，可以是每种类型各有一个区域，也可以是所有数据对象共有一个区域。每个区域管理为一个堆。缺点是选择操作需要更大的代价，优点是存储块可以整体任意移动，整个区域可以处理为一个数据对象。返回65文件和I/O文件是一种数据结构，具有两个特殊性质：1、通常表示在外存上，比其它数据类型也要大得多。2、生命期长，通常会跨越创建它的程序的生命期而存在。顺序文件是最常见的文件类型。很多语言也提供直接访问文件和索引顺序文件。文件的两种常见用途：针对外部操作环境的数据输入和输出。作为数据的临时存储，以解决高速内存不足的问题。文件的部件称为记录。但有别于记录类型。66顺序文件顺序文件是相同类型部件的线性序列，其长度可变且没有固定的最大上界。（当然，受外存大小限制）一个典型的PASCAL声明：

Master:fileofEmployeeRec;文件部件的类型可以是基本类型，