程序设计语言与编译原理-第二章数据类型课件

第二章数据类型数据类型实质上是对存储器中所存储的数据进行的抽象。它包含了一组值的集合和一组操作。1第二章数据类型数据类型实质上是对存储器中所存储的数据进行本章内容1、将类型作为数据结构的抽象表示可以分为三个层次的抽象，即

内部类型、用户定义类型和抽象数据类型2、数据类型与编译有关的几个问题3、类型的实现模型2本章内容1、将类型作为数据结构的抽象表示22.1引言1.数据类型的作用实现了数据抽象从机器的具体特征中解脱出来提高了编程效率32.1引言1.数据类型的作用3语言的某种特定的数据抽象受到两个因素的影响：语言所面向的机器（只提供定点运算或同时提供浮点运算）；语言所面向的应用领域。4语言的某种特定的数据抽象受到两个因素的影响：42.数据类型的分类内部类型自定义类型52.数据类型的分类5语言根据所面向的机器和应用定义了不同的数据类型，这些类型称为内部类型(语言定义类型

)。自Pascal语言开始，语言提供了由用户定义类型的方法。采用这类方法由用户自己定义的数据类型称为用户定义类型(自定义类型)。6语言根据所面向的机器和应用定义了不同的数据类型，这些类

第二节内部类型一.内部类型的特点内部类型反映基本硬件特性在语言级,内部类型是共用某些操作的数据对象的抽象表示7第二节内部类型一.内部类型的特点7

二.内部类型的优越性1.基本表示的不可见性基本位串对程序员是不可见的。优点：导致不同的程序设计风格可写性可读性可修改性例：25+9=34

基本表示00011001+00001001

结果001000108二.内部类型的优越性1.基本表示的不可见性例：25+9=

进行静态类型检查,如非法运算,形实参类型匹配（某些动态特性不一定能查出，如i/j中j=0）2.编译时能检查变量使用的正确性3.编译时可以确定无二义的操作超载(多态)的概念:运算符的意义依赖于操作数的类型。如“+”可以表示整数加或实数加编译时,可拒绝混合运算,或提供类型转换指令合理地使用超载,可以提高语言的可读性和可用性9进行静态类型检查,如非法运算,形实参类型匹配2.编译时能检

4.精度控制

可以通过数据类型显式定义数据的精度精度说明有利于空间优化精度说明可作为检查的一种手段精度说明有利于程序的修改104.精度控制精度说明有利于空间优化10

第三节用户定义类型许多语言除了定义内部类型外，还允许程序员定义新的数据类型，规定基本数据对象的聚合,乃至聚合的聚合。Howtodefine?11第三节用户定义类型许多语言除了定义内部类型外，还

1.笛卡尔积定义：N个集合A1,A2,…,An的笛卡尔积表示为A1

A2

…

An，它是一个集合,其元素为(a1,a2,…,an),其中ai

Ai在语言中对应什么构造？121.笛卡尔积定义：N个集合A1,A2,…,An的笛卡尔积

任意正多边形integer

real表示为边数每边边长在COBOL和PASCAL中称为记录；在ALGOL中称为结构。

注意：语言把笛卡尔积数据对象看成由若干个域组成，每个域有一个唯一的名字；通常用域名来选取域，对它进行修改；例：对于如前定义的多边形，有两个域no-of-edges和edge-size，Structpolygon{intno-of-edges;doubleedge-size}t1;若t1是一个边长为7.53的等边三角形(3,3.75)，则可以写为：t1.no-of-edges=3;t1.edge-size=3.75;13任意正多边形integerreal表示为边数每边边长

2.有限映像（射）定义：从定义域类型DT（domaintype）的值的有限集合，到值域类型RT（rangetype）的值的有限集合的函数称为有限映像（射）。在语言中对应什么构造？142.有限映像（射）定义：从定义域类型DT（domain

有限映像（射）的一些特点在高级语言中通常体现为数组构造；值域对象通过下标选取下标越界会出错，动态检查下标可用来选取值域的多个元素（如数组的分割、切片）SNOBOL4的ARRAY构造符并不要求值域集的所有元素是同一类型的

例如：Chararray[50]可看成是从0到49的整数到字符集的有限映像15有限映像（射）的一些特点在高级语言中通常体现为数组构造；

有限映像（射）的一些特点

DT到相应值的特定子集的绑定策略：

.编译时绑定(静态数组).对象建立时绑定(执行到分程序时,

动态数组).对象处理时绑定(对APL，子集范围可变)16有限映像（射）的一些特点DT到相应值的特定子集的绑定策略

3.序列定义：序列由任意多个数据项组成,这些数据项称为该序列的成分,且类型相同（记为CT）。串的一般操作有4种：连接首项选取尾项选取子串例：串是从所周知的序列，其成分类型为字符；顺序文件的思路也来自序列的概念173.序列定义：序列由任意多个数据项组成,这些数据项称为该序

4.递归定义：若数据类型T包含属于同一类型T的成份，那么类型T称为递归类型。递归类型的特点：允许在类型定义中使用被定义类型的名字指针是建立递归数据对象的重要手段例：二叉树可通过递归类型来定义。它的左子树和右子树分别是另一棵二叉树。184.递归定义：若数据类型T包含属于同一类型T的成份，那么类

5.判定或定义：判定或是一个选择对象结构的构造机制,规定在两个不同选择对象之间作出适当的选择;每一选择对象结构称为变体。例如：PASCAL和ADA中的变体记录;C和ALGOL68中的联合。195.判定或定义：判定或是一个选择对象结构的构造机制,规定在结构、共用体举例namenumtypeScore

situationchen0000012teacherHardworkingZhang2000112student90,88,99,89

20结构、共用体举例namenumtypeScorechen00结构、共用体举例Struct{ charname[10]; Intnum; Chartype[8]; Union { floatscore[10]; Charsituation[40]; }state;}person[2];21结构、共用体举例Struct21

定义：类型T的元素所有子集的集合，称为幂集,记为Powerset(T),T称为基类型。幂集类型的操作：

由于具有该类型的变量的值是一个子集，因此它们的基本操作是集合的操作，比如：联合、与、以及测试某个元素是否在一个集合中等。6.幂集22定义：类型T的元素所有子集的集合，称为幂集,记为Power

小结1.程序语言允许程序员以上六种机制来定义复杂的数据对象（新的类型）；2.新的类型可以通过非显式的方式说明；3.也可通过显式的方式说明；4.显示定义有如下优点：可读性（选择名字）可修改性（不修改变量说明）可分性（重复使用）一致性检查例如：struct{double:radius;doubleangle;}complexc1,c2,c3;例如：structcomplex{double:radius;doubleangle;}complexc1,c2,c3;23structstudent{charname[48];intage;…};小结1.程序语言允许程序员以上六种机制来定义复杂的数据对象可分性可分性概念用得比较普遍，C语言的函数就使用了可分性。把程序中相同的代码“分离”出来，用一个名字来标识，待使用这段代码时，通过该名字调用该段代码即可。可分性可分性概念用得比较普遍，C语言的函数就使用了可分性

内容回顾2.数据类型1.编译时-源程序2.运行时-代码段+活动记录3.活动记录4.别名、副作用1.程序单元1.值的集合+操作的集合2.六种数据类型聚合方式笛卡尔积有限映射序列递归幂集判定或记录、结构数组字符串、顺序文件二叉树联合、变体记录集合25内容回顾2.数据类型1.编译时-源程序2.运行时-代码段+

第四节PASCAL语言数据类型结构1.非结构类型内部类型integer,real,boolean,char有序类型每一元素都有唯一的前驱和后继如:整型,布尔型,字符型定义新的有序类型的方法枚举型其值不能直接读/写子界型动态检查范围例：typeday=(sunday,monday,tuseday,wednesday,thursday,friday,saturday);//枚举typework_day=monday..friday;//子界varclass_day:work_day;class_day:=succ(class_day); //后继……26第四节PASCAL语言数据类型结构1.非结构类型例：26

2.聚合构造数组构造构造符ARRAY允许程序员定义有限映像；数组构造的一般形式为：

array[t1]of[t2]元素（值域）的类型；下标（定义域）的类型；

注意：PASCAL把下标类型不同的数组看成不同的类型typea1=array[1..50]ofinteger;typea2=array[1..70]ofinteger;=?

272.聚合构造数组构造元素（值域）的类型；下标（定义域）的类

!这样定义的数组类型会产生严重问题，使得形式参数定义的数组和实际参数的数组类型不一致；解决办法：引入符合数组概念--维数相同，成分类型相同的数组；符合数组可以形、实参数匹配。例：proceduresort(vara:array[low..high:integer]ofctype);vari:integer;more:boolean;begin{sort}……end{sort}28!这样定义的数组类型会产生严重问题，使得形式参数定义的数

2)记录构造构造符RECORD用以定义笛卡尔积，一般形式为：Recordfield_1:type_1;field_2:type_2;… field_n:type_n;end记录可以整体访问，也可用圆点“.”作为选择符访问单个的域；假设t，p是前面定义的多边形，t.no_of_edges:=3;t.edge_size:=7.53;p:=t;292)记录构造记录可以整体访问，也可用圆点“.”作为选择符访

PASCAL的变体记录typedept=(house,sports,drugs,food,liquor);month=1..12;item=recordprice:real;caseavailable:booleanoftrue:(amount:integer;where:dept);false:(month_expected:month)end;变体记录item标识符域available，记录的判定成分

注意：PASCAL允许程序员访问记录结构的所有域，包括标识符域。例如，如果i1和i2被说明，则可对它们进行如下操作：vari1,i2:item:……i1.price:=5.24;i1.available:=true;i1.amount:=29;i1.where:=liquor;i2.price:=324.99;i2.available:=false;i2.month_expect:=8;30PASCAL的变体记录typedept=(house,s

程序的执行结果priceavailableamountwhere5.24true29liquori1priceavailablemonth_expected324.99false8i231程序的执行结果priceavailableamountwh

变体记录的特点改变一个变体记录的标识符，在概念上建立了一个新记录；变体记录在同一块存储区上重叠存放所有变体；变体记录允许程序员根据每个变体的类型，以不同的观点来解释存储在该区域中的位串；PASCAL变体记录的缺点使用变体记录不安全可以对变体赋值可以改变变体标识符标识符域的标识符可省缺recordprice:realcasebooleanoftrue:(amount:integer;where:dept);false:(mouth_expected:month)end32变体记录的特点改变一个变体记录的标识符，在概念上建立了一个

集合构造PASCAL语言的SET构造符是幂集构造受限制的形式，基类型只能是有序类型，而不能是实数、集合类型。例:typevegetable=(bean,cabbage,carrot,celery,lettuce,onion,mushroom,zucchizi);varmy_salad,leftover:setofvegetable;33集合构造例:33

文件构造PASCAL文件是任意类型的诸元素的序列；PASCAL文件仅能顺序处理；只能进行PUT和GET操作；例:typepattern=record…end;tape=fileof

pattern;vart1,t2:tape;Get操作把下一个元素读到缓冲区put操作把缓冲区中的元素附加到文件末尾34文件构造例:Get操作把下一个元素读到缓冲区put操作把缓

指针是PASCAL的第三类数据类型，是非结构的，可用来构造递归结构；指针可引用匿名数据对象，这类对象由建立语句NEW显示分配在堆上；空指针nil的使用；指针的操作:赋值,比较(相等或不等)PASCAL指针只能指向匿名数据对象，不能指向在栈上分配的的单元3.指针35指针是PASCAL的第三类数据类型，是非结构的，可用来构造typetree_ref=binary_tree_node;binary_tree_node=recordinfo:char;left,right:tree_refend;pointer=node;node=recorddata:integer;next:pointerend;指针例子36typetree_ref=binary_tree_nod

Pascal类型非结构类型指针类型(递归)结构类型内部类型整型实型字符型布尔型枚举类型子界类型记录类型(迪卡尔积)变体记录(判定或)数组集合文件4.小结37Pascal类型非结构类型指针类型结构类型内部类型枚举类型

第六节C语言数据类型结构1.非结构类型：分为内部类型和用户自定义类型非结构内部类型有整型、实型和字符型类型类型标志符数值范围占用字节数基本型int-32768327672短整型Short-32768327672长整型Long-231(231-1)4无符号整型Unsigned0655352无符号短整型Unsignedshort0655352无符号长整型Unsignedlong0(232-1)438第六节C语言数据类型结构1.非结构类型：类型类型标志符数

实型又称浮点型，其值是实数的一个子集，分为单精度和双精度两种类型字符型数据的值是一个有限字符集的元素；在C语言中，int类型与char类型在存储中没有本质区别；-308308-10308

1030815168Double双精度型-3838-1038

103874Float单精度型阶的范围数值范围能表示数值的有效位点用字节数类型标志符类型浮点型数据类型的特性

注意：C语言中没有布尔（bool)类型；0表示false，非0表示true。39实型又称浮点型，其值是实数的一个子集，分为单精度和双精度两

用户自定义的非结构类型用户自定义的非结构类型在C语言中称为枚举类型（enum）enumbool{false,true};或typedefenum{false,true}bool;（1）定义了一个新类型bool（2）bool数据类型的取值为false和true（3）定义了一个顺序：false<true（4）可对这个类型的变量进行赋值和比较等操作enumbool{false,true};boolb;b=true;if(b==true){……}40用户自定义的非结构类型用户自定义的非结构类型在C语言中称为

2.聚合构造（1）数组实现有限映像说明的格式<类型说明符><数组名>[常量表达式]例如：intintarr[5];charchararr[255];boolboolarr[3];

注意：C语言中数组的下标总是从0开始。412.聚合构造（1）数组例如： 注意：C语言中数组的下标总

可以定义多维数组说明的格式<类型说明符><数组名>[常量表达式]…[常量表达式]例如：floatfarr[3][4];charc[2][2][2];C语言的数组按行存放对数组名的处理相当于指针数组a[3][4]的存放次序为：a[0][0]a[0][1]a[0][2]a[0][3]a[1][0]a[1][1]a[1][2]a[1][3]a[2][0]a[2][1]a[2][2]a[2][3]inta[10];int*pa;pa=a;42可以定义多维数组例如：C语言的数组按行存放数组a[3]

（2）结构C语言中构造符struct支持笛卡尔积说明的格式struct<结构体名>{成员表列}；成员表列由若干个成员类型说明组成：

<类型标识符><成员名>；例如：structstudent{ intnum; charname[2]; charsex; intage; floatscore; charaddr[30]; }43（2）结构例如：structstudent{43

注意：C语言中结构不能整体赋值和输出，只能对其中的各个成员分别进行操作。在内存中，结构的各成员依次存放；结构体可以嵌套；例如：structstudentme,you;strcpy(,“john”);me.sex=‘M’;me.age=21;me.score=80;strcpy(me.addr,“UESTC”);44 注意：C语言中结构不能整体赋值和输出，只能对其中的各个成

（3）联合

C语言中构造符union（联合）支持判定或联合结构举例：

uniondata{ inti; charc; floatf; } uniondataa,b,c;a.i=2;a.c=‘s’;a.f=3.14;（1）C语言中联合中没有标识符域；（2）单元中的值的类型，取决于程序员的使用；45（3）联合联合结构举例：a.i=2;（1）C语言中联合

（4）文件C语言中文件是一个字符序列；分为ASCII码文件和二进制文件；C语言中文件的预定义格式如下：

typedefstruct{ int_fd; int_cleft; int_mode; char*_next; char*_buf; }FILE;文件名缓冲区中剩下的字符数文件操作模式下一个字符指针缓冲区指针46（4）文件C语言中文件的预定义格式如下：文件名缓冲区中剩下

3.指针

C语言中的指针是第三种数据类型，是非结构类型；可用来构造结构类型；支持递归；利用指针定义递归结构的例子：

structtree{ charday; structtree*lchild; structtree*rchild; }; structtree*my_tree;473.指针C语言中的指针是第三种数据类型，是非结构类型

4.空类型

C语言中有一种特殊的数据类型void，称为空类型；是一种非结构类型；有两个主要用途：用来表示一个无返回值的函数用来表示不确定类型的指针例：voidmain(){ inti; i=1;}例如：void*p;表示这是一个指针，它的值是一个地址，但不指明p指向的值是什么类型。484.空类型C语言中有一种特殊的数据类型void，称为

5.C数据类型小结C数据类型非结构型结构型指针类型(递归)内部类型枚举类型数组类型（有限映象）联合类型（判定或）结构类型（笛卡尔积）（文件）（序列）整型空类型实型字符型单精度型双精度型495.C数据类型小结C数据类型非结构型结构型指针类型内部类

第八节抽象数据类型1.用户定义类型与内部类型的异同都建立某种基本表示的抽象内部类型:对二进制位串的抽象；用户定义类型:对内部类型和已定义的用户定义类型的数据作为基本表示的抽象每一类型都关联一组操作内部类型隐蔽了基本表示，不能对它的成分进行操作;用户定义类型具有更高级别的抽象，可以对其基本表示的成分进行操作。能不能仿照内部类型，隐藏用户自定义类型的内部信息？50第八节抽象数据类型1.用户定义类型与内部类型的异同能不能

2.抽象数据类型的定义满足下述特性的用户定义类型称为抽象数据类型:在实现该类型的程序单元中,建立与表示有关的基本操作;对使用该类型的程序单元来说,该类型的表示是隐蔽的。3.在描述实现的程序单元中进行修改1.对象的表示是被保护的，外界不能对它进行直接操作2.隐蔽了表示的细节，通过过程来访问抽象数据对象512.抽象数据类型的定义3.在描述实现的程序单元中进行修改

1.SIMULA67的类机制2.CLU的抽象数据类型-簇3.Ada的抽象数据类型4.Modula-2的抽象数据类型521.SIMULA67的类机制2.CLU的抽象数据类型

C++语言中的抽象数据类型称为类（class），类的实例称为对象（object）；class<类名>{private:

私有段数据定义；私有段函数定义；

protected:

保护段数据定义；保护段函数定义；

public:

公有段数据定义；公有段函数定义；

}C++语言类定义的一般形式5.C++语言的抽象数据类型C++的类满足抽象数据类型的条件（1）和（2）?53C++语言中的抽象数据类型称为类（class），类的

类的实例是对象，对象继承类中的数据和方法封装、继承、多态C++支持重载和多态C++的继承性通过派生类来实现虚函数、抽象类54类的实例是对象，对象继承类中的数据和方法封装、继承、多态C

第九节类型检查对数据对象的类型和使用的操作是否匹配的一致性检查称为类型检查；语言的类型检查分为静态检查（staticchecking）和动态检查（dynamicchecking）;静态检查使程序更正确更有效动态检查使编程方便,但影响了可读性,且降低了执行效率语言按类型可分为无类型语言、弱类型语言和

强类型语言；在编译时进行的检查在运行时进行的检查语言没有类型定义语言的类型检查不能全部在编译时完成，有些要在运行时才能完成语言的类型检查全部在编译时完成55第九节类型检查对数据对象的类型和使用的操作是否匹配的一致

理由：编译时,不能确定一个过程中的过程参数和子程序参数类型Pascal的子界类型不能静态检查变体记录的标识符可以在运行时改变Pascal没有严格规定类型的一致性规则procedurewho_knows(i,j:integer;proceduref);vark:boolean;begink:=j<i;ifkthenf(k)elsef(j)end;如:a:=b+c;且a、b、c均属于子界类型1..10PASCAL是非强类型语言56procedurewho_knows(i,j:integ

第九节类型转换将一个类型的值转换成另一个类型的值，称为类型转换；类型转换分为拓展（widening）和收缩（narrowing）；在某些语言中，类型转换的要求和规则是隐式的，它由编译器自动生成类型转换的代码；一般来说，语言对基本类型提供适当的类型转换，而对复合类型或用户自定义类型不提供转换；转换之后的类型值的集合包含转换之前的类型值的集合；例如：整型

实型转换之前的类型值的集合包含转换之后的类型值的集合；例如：实型整型1.截断2.舍入法57第九节类型转换将一个类型的值转换成另一个类型的值，称为类

一些语言规定的转换规则：FORTRAN语言：转换规则隐式给出；转换规则根据类型和类型之间的优先级来确定；由低级类型向高级类型转换；FORTRAN的类型优先级为：COMPLEX>DOUBLEPRECISION>REAL>INTEGERPASCAL语言：只允许整数到实数，以及子界类型到整数的转换；其他的转换必须显示处理varr:real;i:integer;i:=r;？应写为varr:real;i:integer;i:=round(r);58一些语言规定的转换规则：FORTRAN语言：PASCAL语

ALGOL68语言：完全的、形式化的隐式转换规则；它一共给出6种隐式转换规则；Ada语言：必须显示转换；59ALGOL68语言：Ada语言：59

隐式转换发生在下述的情况下：混合运算：级别低的类型向级别高的类型值转换。将表达式的值赋给变量：表达式的值向变量类型的值转换。实参向函数形参传值：实参的值向形参的值进行转换。函数返回值：返回值向函数返回类型的值进行转换。注意语言规定的转换规则隐式转换发生在下述的情况下：注意语言规定的转换规则

第十节类型等价若T1和T2是两个类型，T1的任何值都可以赋予T2类型的变量，反之亦然，T1类型的实参可以对应类型T2的形参，反之亦然，则称T1和T2是相容的，或等价的；61第十节类型等价若T1和T2是两个类型，61

第十节类型等价有两种类型的相容性概念：①名字等价:两个变量的类型名相同62structRecA{charx;inty;};typedefstructRecARecA;structRecAa;RecAb;structRecAc;struct{charx;inty;}d;a和c是名字等价，b和d与其他任何变量都不是名字等价。struct{charx;inty;}d，e;struct{charx;inty;}d;struct{charx;inty;}e;第十节类型等价有两种类型的相容性概念：62struct不等价第十节类型等价有两种类型的相容性概念：②结构等价两个变量的类型具有相同的结构。63structRec1{charx;inty;charz[10];};structRec2{charx;inty;charz[10];};structRec3{inty;charx;charz[10];};Rec1和Rec2是结构等价，Rec1和Rec3不是结构等价。structRec1{charx;inty;}；structRec2{chara;intb;}；不等价第十节类型等价有两种类型的相容性概念：63stru

第十节类型等价两种相容性实现时的比较①名字等价的实现比较简单②结构等价的实现需要的模式匹配过程可能十分复杂64第十节类型等价两种相容性实现时的比较64

第十一节实现模型在实现模型中，数据用描述符和数据对象来表示；描述符用来描述数据对象的所有属性只考虑原理性的实现，不考虑效率以PASCAL语言为例

描述符:描述数据对象的所有属性数据数据对象(存储区及其值)65第十一节实现模型在实现模型中，数据用描述符和数据对象来表

1.内部类型和用户定义的非结构类型的实现模型描述符一般由“类型”和一个指针组成integer描述符数据对象整数变量的表示real描述符实型变量的表示数据对象子界的描述符必须包括子界的界值布尔型和字符型可以压缩存储661.内部类型和用户定义的非结构类型的实现模型integer

2.结构类型的实现模型笛卡尔积各成分顺序排列（数据）描述符包含:类型名、构造符、若干三元式。每个域对应一个三元式(选择符名,域类型,指针)每个成分占整数个可编址的存储单元(字编址或字节编址）672.结构类型的实现模型67

typet=recorda:real；

b:integer；

end；数据对象浮点值定点值描述符类型名构造符选择符选择符类型类型引用引用trecordarealbinteger域1域268typet=recorda:real；数据对象浮点值定

有限映像为每一成分分配整数个可编址的存储单元描述符包括:类型名、构造符、定义域的基类型、下界、上界、成分类型、单元个数、首地址内情向量；69有限映像69地址公式的计算若定义域类型是子界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是编译时能计算出的地址公式的计算

例：typea=array[1..10]ofreal;描述符类型名构造符基类型成分类型下界单元个数上界引用aarrayinteger1real1下标类型10数据对象浮点值浮点值浮点值71例：typea=array[1..10]ofreal

序列PASCAL中的串长度静态可定；静态分配；其他语言中（如SNOBOL4和ALGOL68中），可变长串的表示:静态描述符+动态描述符+堆string5ALPHA