程序封装.ppt

《程序封装.ppt》由会员分享，可在线阅读，更多相关《程序封装.ppt（86页珍藏版）》请在三一文库上搜索。

1、第六章 封装,2,抽象,大型程序的构造中，程序员不可避免要涉及到新数据类型的设计和实现。 如：大学中，表示一堂课的数据对象section，包含的信息有：老师名、教室、最大注册数等，还可以包含一个注册学生列表作为部件。 操作包括：创建一个section、注册一个学生、消除一个section等。 其实现主要涉及其表示以及对应相关操作的子程序设计。 语言实现的目标是使得数据的各种形式的不同对程序员透明。因此，基本类型和用户定义类型对程序员的使用来说应不存在差别。,3,抽象机制,有四种机制可被程序员用来创建新类型和类型上的操作。 1、结构化数据 几乎所有语言都能够用基本数据对象创建复杂的数据对象。 2

2、、子程序 可用子程序来定义实现类型的操作，但如何正确地使用，却是程序员的责任。 3、类型声明 语言包含有定义新类型及其操作的能力。抽象数据类型即是这种机制，它提供了检测错误使用的能力。 4、继承 基于已有类型创建新类型的机制。,4,6.1 结构数据类型,数据结构包含其他数据对象作为元素或部件的数据对象。 基本概念 常见结构化数据 向量和数组 记录 列表 集合,5,结构数据对象和数据类型,结构数据对象一组其他数据对象构成的聚集，这些数据对象称为元素或部件，可以是基本类型，也可以是结构。 很多和数据结构相关的问题和概念与基本类型数据是相同的，但数据结构更为复杂。 数据结构类型也涉及类型规约和类型实

3、现，只是更为复杂。 两个方面是特别重要的： 结构信息的规约和实现变成了中心问题，用于指出部件对象及其间关系，以便于部件的直接选取（或访问）。 结构上的很多操作带来的存储管理问题。,6,数据结构类型的规约,规约的主要属性包括： 1、部件数量 结构的部件数量可能是固定的，在其生命期中不变，如：数组、记录等。 也可能是变长的，数量可以动态变化，如：栈、列表、集合、文件、表格等。 变长结构通常需定义插入和删去部件的操作。而且可变长数据对象经常使用指针类型。,7,数据结构类型的规约,2、每个部件的类型 同构的所有部件为相同类型，如：数组、字符串、集合、文件等。 异构的部件有不同类型，如：记录，列表等。

4、3、用于选取部件的名字 结构类型需要有标识结构中个体部件的选择机制。 对数组，个体部件的名字可以是整数下标或下标序列。 对列表，名字可以是用户定义的标识符。 有的结构，只允许访问特定部件，如栈顶元素。,8,数据结构类型的规约,4、部件的最大数量 对有的变长结构，结构的最大尺寸可以指定。 5、部件的组织 最常见的组织是简单的线性序列，如：向量、记录、字符串、栈、列表、文件等。 然而，数组、记录和列表类型也可以扩展为多维形式。 多维形式可以看成单独的类型，也可以简单地看成同类结构部件的顺序类型（其元素类型为结构）。 如A(i,j) 和Aij的差异。,9,数据结构上的操作,结构上操作的定义域和值域规

5、约的方法和基本类型操作是类似的，但是，有些新的操作类型特别重要。 1、部件选择操作 有两种类型： 随机选择可任意选择结构中某一部件 顺序选择以预定好的顺序选择部件。 数据对象中部件或数据值的选择和相关的引用操作是有区别的。如：V4选择V中第4个元素，分两步： 先引用（确定V的位置（l-值），返回一个指针）， 后选择（得到部件的位置）。,10,数据结构上的操作,2、整体数据结构操作 以完整的数据结构为参数，产生新的数据结构为结果。 大多数语言中，这样的整体性操作是有限的。如： 两个数组相加、记录间的赋值、集合的并等。 少数语言提供了大量整体操作，然而，程序员很少去选择个体部件。如：APL和SNO

6、BOL4语言。,11,数据结构上的操作,3、部件的插入/删除 这种操作将改变部件数量，从而影响存储表示和存储管理。 4、数据结构的创建/消除 这类操作将对存储管理有很大影响。,返回,12,数据结构类型的实现,实现中需要考虑的两个问题： 结构中部件的高效选择， 高效的存储管理。 存储表示 结构的存储管理包括：结构中部件的存储；可选的描述子（用于存储结构的属性）。,13,数据结构类型的实现：存储表示,有两种基本表示： 1、顺序表示 结构存放在单个连续块中（包括描述符和部件）。 常用于固定长的结构，有时也用于同构变长结构。 2、链接表示 结构被存放在几个非连续的存储块中，这些块用指针链接在一起，该指

7、针称为链（link）。 通常用于变长结构。,14,两种基本存储表示,15,数据结构操作的实现,大多数结构的实现中，部件选择是最重要的，需要较高的随机和顺序访问效率。对顺序和链接存储表示，这两种类型的选择的实现有所不同。,16,数据结构操作的实现,顺序表示 部件的随机访问通常涉及“基地址（完整块的开始位置）+位移量（部件在块中的相对位置）”的计算。 对一个顺序存储的同构结构，部件序列的选择按如下步骤： 1、要选择序列的第一个部件，使用“基地址+位移量”。 2、要选择下一个部件，在当前部件位置上加上当前部件的大小，对同构结构，每个部件的大小是相同的。,17,数据结构操作的实现,链接表示 随机选择需

8、要沿指针链从头查找，需知道在部件块中链指针的位置。 部件序列的选取相对容易，沿指针向前即可。,返回,18,数据对象的访问,数据对象一旦创建，需同时创建它的访问路径，使得对象可被程序中的操作访问。 访问路径的创建方式： 将标识符（名字）和对象相关联 存放指向结构的指针于其他可访问的结构中，使成为其部件元素。 在生命期中，还可能产生其他的访问路径。 如：作为参数传递给子程序 创建一个新指针 访问路径也可以被删除 如：赋新值给一个新指针变量 从子程序返回。,19,数据对象的访问,与数据对象的生命周期及访问路径相关的两个中心问题： 1、垃圾： 当所有访问路径被消除，但数据对象仍然存在，它将不可再被访问

9、。因此，其和存储位置的绑定必须解除。 2、Dangling reference：悬空引用。 某个访问路径，它在关联的数据对象消除后仍然存在。 这对存储管理是一个严重的问题，因为它可能破坏运行时结构的完整性，如：修改不相关的数据和修改存储管理数据等。,返回,20,数据结构：向量和数组,向量由固定数量的同类型部件组成，按简单的线性序组织，向量部件由下标选择。 向量也称一维数组或线性数组。 二维数组或矩阵，其部件被组织为行、列的矩形格。,21,向量：属性,向量的属性包括： 1、部件的数量，通常由一组下标范围隐式地指定。 2、部件的类型，所有部件具有相同的类型。 3、用于选择每个部件的下标，通常是一个

10、整数域，第一个整数指定第一个部件，第二个数指定第二个部件，依此类推。下标可以是给出一个值的范围，也可以是只给出上界，而下界是隐含的。,22,向量：声明,典型的向量声明： V : array 110 of real; -PASCAL语言 float a10; -C语言 如果允许指定下标域，则可以使用枚举为下标，如： type class = (Fresh, Soph, Junior, Senior) var ClassAverage: array class of real;,23,向量：操作,向量上的操作： 选择元素的操作通常称为下标操作，如： V2， ClassAverageSoph 由于下

11、标大都是可计算值，固可用表达式作下标： VI + 2 其它操作包括：向量的创建和消除，向量元素的赋值，相同大小的两个向量间的算术操作等。通常插入和删除向量元素是不允许的。 APL是专门基于数组的语言，允许大量向量操作。,24,向量：实现,由于向量的同构性和固定大小，其存储和访问相同简单。同构性意味着每个元素的大小和结构相同，固定大小意味着元素数量及每个元素的位置保持不变。 顺序存储表示是很好的选择，描述子用于存放一些运行时必要的属性信息。,用于越界检查,25,向量：实现（访问）,元素的随机访问，即向量元素的左值访问公式： lvalue(AI) = + (I LB) E 这里为基地址，E为元素所

12、占的存储大小。亦即： lvalue(AI) = ( LB E) + (I E) lvalue(AI) = K + (I E) -K表示常数 有的语言（如FORTRAN ）中K为常量，故可在编译时计算出来。 即使在有的语言（如PASCAL）中，K可能发生变化，也只需要在存储分配时计算一次。 由于E和I均是在编译时可知，因此，访问公式的计算完全可在编译时完成。 如C语言中，字符数组的E为1，LB总为0，访问公式为：lvalue(AI) = + I。,26,向量：实现（访问）,虚原点： lvalue(A0) = ( LB E) + (0 E) = K 即K为向量中元素0的地址，如果0元素存在。如果向

13、量的下界大于0，则这个地址称为虚原点VO。因此，构建向量并产生访问公式的算法为： 1、向量存储的创建：为N个大小为E的向量元素分配D(NE)，D为描述子的大小。 2、计算虚原点：VO LB E 3、访问具体元素：lvalue(AI) = VO + I E 上面公式假定I为A的有效下标，即，LB = I = UB。通常越界检查是必须的，因此LB和UB应该存放在描述子中。 如果虚原点也存放在描述子中，则数组和描述子可不必存放在一起。这是为什么通常描述子作为参数传递给子程序，而数据的数组却存放在别的地方。,27,向量：实现（访问）,这里描述子类型和元素类型均未在描述子中给出。通常，这些信息在编译时已

14、知。,28,向量：实现,打包及未打包存储表示： 通常每个数组元素占用完整的可编址存储单元。但是，有的类型只占用一个字中的一小部分，此时，需要将几个向量元素打包存放在在一个编址单元中。打包存储带来的问题是访问公式更加复杂。,29,向量：实现,全向量操作： 将向量作为整体的操作是基于顺序存储表示而实现的。 一个向量到另一个向量的赋值即是简单的内容拷贝，而描述子不需要拷贝。 向量上的算术操作实现为向量中元素循环顺序处理。 全向量操作实现的最大问题是结果的存储。需要临时分配存储来存放结果的右值，除非它被立即赋给一个左值位置。 当涉及的全向量操作过多时，临时存储的管理可能会增加复杂性和成本。,30,多维

15、数组,多维数组实际上是一维数组的推广。 规约和语法：和向量在属性上的差别只是需要指定每个维的下标范围。如： B : array110, -55 of real; 数组元素的选择需给定每一维，如： B2, 4。,31,多维数组：实现,矩阵可以方便地实现为向量的向量，三维数组的元素是向量的向量，依此类推。所有子向量必须有相同数量的元素，而且是相同类型。 矩阵是实现为“行之列”还是“列之行”是语境敏感的，特别是在不同语言的程序间作为参数传递时。最常见的实现是“行之列”，此即所谓的“行为主序”。 多维数组的存储表示类似于向量。如对矩阵，先存第一行的数据对象，再存第二行的数据，依此类推。,32,多维数组

16、：实现,二维数组的存储表示,33,多维数组：实现（访问）,下标操作及访问公式： 对MN的“行为主序”二维数组，有： lvalue(AI, J) = + (ILB1) S (J LB2) E 这里是基地址，S是一个行的长度，即 S(UB2LB2+1)E 考虑常量项：VO LB1SLB2E 则： lvalue(AI, J) VOISJE 更多维数组：AL1:U1, , Ln:Un 1、乘数的计算：mn=e，mi=(Ui+1Li+1+1)mi+1 2、虚原点的计算：VO (Limi) 3、数组元素的访问：lvalue(As1, , sn)=VO+ (simi),返回,34,记录,由固定数量的不同类型

17、部件组成。 规约和语法：记录和向量都是定长的线性结构，其不同在于： 1、记录的元素可能是异构的，是不同类型的混合。 2、记录的元素用符号命名，而不是用下标。,35,记录：声明,例如，C语言中的记录声明为： struct EmployeeType int ID; int Age; float Salary; char Dept; Employee; 从声明中可看出： 1、部件的数量 2、每个部件的数据类型 3、用于命名每个部件的选择子 部件也称域。,36,记录：实现,记录的存储表示包含一个顺序的存储块，其中元素顺序存放。每个元素可能需要描述子去指定它们的数据类型或其它属性，但通常对记录本身没有运

18、行时描述子。,37,记录：元素的访问（选择）,部件选择是记录的基本操作，但不是使用计算值，而是使用文字部件名。很少有针对整个记录的操作。例如，记录元素的选择： Employee.ID Employee.Salary 元素的选择相对容易实现，因为在翻译时域名就已经知道，记录的声明也使得每个元素的大小和位置在翻译时可确定。因此，在翻译时可以计算出任意元素的位移量。,38,记录：元素的访问（选择）,基本的访问公式： Lvalue(R.I) = + (size of R.j) j=1I-1 = + KI -KI为元素I的位移量,39,记录：存储,有些数据类型的存储必须从特定的地址边界开始。例如，整数可

19、能必须从字的边界开始存放，对可字节编址的机器而言，该地址必须能够被4除。在C语言中， struct EmployeeDivision char Division; int IdNumber; Employee 如果IdNumber必须从字边界开始，则在Division和IdNumber间有三个字节未用，称为填料（padding）。存储表示就好象如下声明一样： struct EmployeeDivision char Division; char UnusedPadding3; int IdNumber; Employee,40,含结构元素的记录和数组,如果语言同时提供数组和记录类型，则这两种类

20、型的元素可能和其它基本类型的元素混杂在一起。如：一个向量的每个元素都是一个记录，在C中有如下声明： struct EmployeeType int ID; int Age; float Salary; char Dept; Employee500; 这样一个复合数据结构的元素的选择需要一系列选择操作，如：Employee3.Salary。,41,含结构元素的记录和数组,记录的部件也可以是数组或其它记录，导致记录具有层次结构。COBOL和PL/1中，使用层次编号来语法地指定这种层次结构。如，一个PL/1声明：,1 Employee, 2 Name, 3 Last CHARACTER(10), 3

21、 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);,42,含结构元素的记录和数组：实现,存储表示类似于简单的数组和记录类型。记录构成的向量的存储表示相对简单，每个行被记录的存储表示替代。类似地，记录的记录保持相同的实现结构，但每个元素是一个子块，子块本身是一个完整记录的表示。,

22、43,可变记录（variant records）,可使用一个记录来表示相似的、但不同的数据对象。这样的记录类型有几个变体，它们有共同的部分，但各个变体又有自己独有的部件。如，雇员可以分为按月和按小时领工资两种情况，从而呈现两个变体。,例如，一个PASCAL声明如下： type PayType = (Salaried, Hourly) var Employee: record ID: integer; Dept: array 13 of char; Age: integer; case PayClass: PayType of Salaried: (MonthlyRate: real; Star

23、tDate: integer); Hourly: (HourRate: real; Reg: integer; Overtime: integer) end,PayClass称为标记或判别子，用于指定被采用的变体。,44,可变记录：元素的访问（选择）,变体记录的选择操作和一般记录相同，但由于变体问题，有的部件的存在性会在运行中发生变化，因此，有的选择操作可能在运行中某时刻找不到希望的部件，如：Employee.Reg。这类似于下标越界问题，解决方案为： 1、动态检查：在访问部件前检查标记以保证该部件存在。如果标记值不对，则出现运行时错。 2、不检查：语言设计可能允许变体记录的定义没有显式的可在

24、运行时检查的标记，因此，变体记录的部件选择总被假定为合法的。由于变体记录的实现方式，这样的选择总是可能的，但是，如果部件不存在，当前变体的值可能会被不经意地取出或覆写。C语言中的union类型就不允许标记，从而不能提供检查。 具有变体的记录也称为union类型，可视为一组数据对象集合的“和”。如果不允许标记，则称为“自由和”类型（free-union），如果允许标记，则称为“判别和”类型（discriminated-union）。,45,可变记录：实现,可变记录的实现比正确地使用它要容易。在翻译时，每个变体的部件的存储需要量是确定的，存储的分配根据最大的可能变体来安排。在存储块内，每个变体根据

25、部件的类型和数量具有不同的布局。布局在编译时确定，并用于计算被选择部件的位移。运行时，不需要特殊的描述子。 如果不进行检查的话，变体中部件的选择相同于普通记录的部件选择。在翻译时，被选择部件在存储块中的位移被计算出来，在运行时，位移被加到块的基地址上以形成部件的地址。此时，部件存在与否十分重要，如不存在，则将取出不是所期望的值，而对该部件位置的修改也有可能带来灾难性后果。 如果提供动态检查，则先检查标记部件的内容，以保证标记指示出所需的变体确实存在。,46,可变记录：存储表示,返回,47,列表（ List ）,由数据结构的有序序列组成的数据结构。 规约和语法：列表类似于向量，都由数据对象的有序

26、序列构成，即可以访问列表的第一个元素、第二个元素、依此类推。它们的不同主要体现在： 1、列表基本上不会固定长度，通常用于表示任意的数据结构，并在运行中增长和缩小。 2、列表基本上都是异构的，列表的每个成员的数据类型均可以不同。 3、使用列表的语言典型地通过隐式的方式声明这样的数据，其成员没有显式的属性。,48,列表：实例,LISP语法是典型的列表结构： (FunctionName Data1 Data2 Datan) 在LISP中，大多数操作以列表为参数并返回列表值。如： (cons (a b c) (d e f) = (a b c) d e f) LISP的一个重要特征是：所有参数需先计值。

27、如上式写为： (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”等。,49,列表：实现,由于列表元素的异构性和大多数列表实现的动态性，向量、数组所用的存储表示将不适用于列表。通常适用链接列表存储组织结构。表项是基本元素，通常由固定长度的数据对象构成。,50,列表：存储表示（1）,在LISP中，通常含有三个信息域：一个类型域，

28、两个表指针。如果类型域指明为原子，则剩下的域为描述该原子的描述子。如果类型域指明为表，则第一个指针为表头，第二个指针为表的尾。,51,列表：存储表示（2）,这种表示的中间和底层结构的类似性显示了这种实现方式的功效： 1、cons：cons或join操作通过创建一个新表节点而实现，该节点的头域指向第一个参数，尾域指向第二个参数。 2、head：表的头是表项的头域的内容（右值）。 3、tail：表的尾是表项的尾域的内容。,52,列表的变种(1),栈和队列：栈是一种列表，其中部件的选择、插入和删除被限制在一端进行。队列的部件选择和删除被限制在一端，而插入被限制在另一端。 树：其中的部件可以是列表以及

29、基本数据对象，而每个列表只能最多是另一个列表的部件。大多数LISP例子实际上是树。,53,列表的变种(2),有向图：其中的部件可以被任意的链接模式链接在一起，而不仅仅是线性序。 性质表：具有可变数量部件的记录通常称为性质表，如果部件的数量可以无限变化。在性质表中，部件名及其值均需被存储，分别称为性质名和性质值。性质表通常表示为链接表。,54,性质表的存储表示,返回,55,集合,集合是一个数据对象，它包含不同值的无序集合。而列表中元素是可以重复的。集合上的基本操作有： 1、成员关系：X是否为S中的成员？XS？ 2、单个值的插入和删除。如果X不是S中的成员，则可以插入X；如果X是S中的成员，则可从

30、S中删除X。 3、并、交和差。 集合中成员的访问不能使用下标或相对位置。 实现：在程序设计语言中，集合有时是指表示有序集合的数据结构。一个有序集合实际上是一个列表，只是不允许元素的重复。而无序集合则需要两种不同的存储表示。,56,集合的表示：位串,位串存储表示适合于已经知道集合元素域的大小较小的情形。假定在域中有N个元素，这些元素任意排序为e1、e2、eN，从该域选择出的一组元素可以用长度为N的位串来表示，其中，如果ei存在于集合中，则串的第i位为1，否则为0。 位串表示了集合的特征函数。元素的插入表现为相应位的设置，元素的删除表现为相应位的清除，成员关系判断表现为检查相应位，并、交及差的操作

31、可实现为位串上的布尔操作，通常有硬件支持。 如果提供了对位串操作的硬件支持，则集合的位串表示的操作将是非常高效的。然而，硬件操作通常仅仅应用到某固定长度的位串（如：字的长度）。如果串的长度大于最大值，则软件仿真将是需要的，用于将位串分为较小的、可被硬件直接操作的单元。有的语言为此而限定集合的大小。,57,集合的表示：HASH编码,另一种常见的集合表示方法为HASH编码或散列存储。该方法可以用于集合的域较大时。 该方法可允许集合的成员测试、插入、删除高效地完成。 然而，并、交及差等操作效率不高，必须实现为一系列个体元素的成员测试、插入、删除等操作。 为了有效，HASH编码方法需要实质性的存储分配

32、。,58,集合的表示：HASH编码,语言并不向用户提供集合数据类型的这种表示方式，但语言的实现在翻译或执行中使用这种表示来实现一些系统定义的数据。 如，大多数LISP实现使用这种存储表示来实现名为object list的集合，它包含LISP程序执行中所有原子数据对象的名字。 几乎所有的编译器使用HASH编码来查找符号表的名字。,59,集合的表示：HASH编码,在一个向量中，每个下标指定一个唯一的部件，可以使用简单的访问函数来达到该目标。 HASH编码的目标就是要尽可能地达到这样的效果。问题是：潜在的合法名字的集合相对于可用的存储而言是大的。如果我们分配HASH表至少为我们所期望使用的两倍大，则

33、HASH编码将是非常高效的。 不是将集合中元素顺序地存放在存储块中，而是将元素随机地散列在块中。其技巧在于以这种方式存放每一个元素，而其存在与否在以后将可以立即地确定，而不需要搜索整个存储块。 考虑加入元素X到集合S，位串Bx表示X，存储块Ms表示S。应用HASH函数到Bx得到Bx在Ms中的位置Ix，称为HASH地址，用为指向块中位置的索引。如果X不在S中，则Bx将被存入到Ms中由Ix指定的位置。X的查找是方便的，提供使用同样的HASH函数可找到其在Ms中的位置。,60,集合的表示：HASH编码,对HASH函数的要求一是计算速度，二是分布的随机性。假定Ms为1024个字，需要存放的数据项是表示

34、为双字位串的字符串，则我们可以表示一个可含511个不同元素的集合。假定块的起始地址为，一个合适的HASH地址将是9位的串Ix，因为公式2Ix将总是产生在块内的地址。Ix由Bx产生，假定Bx存放在字a和b中。 1、a乘以b，得到c（两个字长） 2、将c的两个字相加，得到d（一个字长） 3、将d平方，得到e 4、取e的中间9位，得到Ix,61,集合的表示：HASH编码,即使最好的HASH函数也不能保证对不同的数据项产生不同的地址。几乎不可避免地会产生冲突。 处理冲突的解决办法： 1、重新HASH。可以考虑修改初始的位串Bx，如：乘以某常量。然后重新HASH。直至无冲突为止。 2、顺序扫描。从块中的

35、冲突点开始进行顺序搜索，直至找到某Bx，或遇到一个空位置。 3、使用桶（bucketing）。在块中的位置上用一个指针来指向具有相同HASH地址的一个链接桶表。 不同的HASH函数合适于不同的将被存放的位串表示。如果有一个好的HASH函数，且表是半满的，则冲突较少发生。 前面例子中512个项只用了511个的原因就是为了解决冲突。,返回,62,6.2 抽象数据类型,数据类型概念的演化 早期类型定义为值的集合，该类型的变量可在该集合中取值。 70年代初，Pascal扩展类型定义为：变量的集合。 70年代早期，概念进一步演化，类型不仅仅是类型对象的集合，还包含了其相关操作。正是操作展示了对象的行为。

36、 例：对基本类型实数和整数，语言提供了声明机制和相关操作。从而其存储表示被封装，程序员使用它们而不需知道表示细节。,63,数据类型概念的演化 数据抽象以数据为中心的封装方式 ADT定义为： 1、一组数据对象，通常使用一个或多个类型定义。 2、一组对这些对象的抽象操作。 3、二者的封装，使得该类型的用户只能通过这些操作来操纵该类型的数据对象。,64,信息隐蔽,“分而治之”是我们编写大型程序的一般策略，程序被分成模块。 模块设计有两种途径：功能分解，数据分解。 然而，功能设计有一定缺陷，不能对数据结构的细节提供很好隐蔽。 而使用数据抽象可以避免这些问题。 数据类型的规约给出了所有使用该类型对象所需

37、要的信息，而实现细节则对外屏蔽。,“抽象”在语言中是一个重要概念，语言以两种方式提供对抽象的支持。首先，提供一个抽象虚拟机，它比实际计算机更易于使用，也更强大，语言直接提供了一些有用的抽象，称为语言的特性；第二，语言提供了辅助程序员定义抽象的设施，这些抽象形成了特定程序定义的抽象机。,65,信息隐蔽,信息隐蔽是程序定义抽象设施的设计的中心原则 每个程序部件应尽可能对用户隐藏信息。 当信息被封装在抽象中时，意味着抽象的用户： 1、为了使用该抽象，不需要知道隐蔽的信息。 2、不允许直接使用或操纵被隐蔽的信息，即使用户希望这么做。 例如：Fortran、Pascal中的整数类型不仅隐蔽了整数的表示细

38、节，甚至有效地封装了表示，使得程序员不能操作整数中的个体位。 但它们难于封装新数据类型的表示，虽然也可以构造子程序集合来创建和操作抽象，但不能真正封装其表示，程序员可以编写其他子程序来非法地或不合适地操作抽象。,66,信息隐蔽,封装对使程序易于修改特别有用，只要保持子程序（操作）接口不变即可。 注意：信息隐蔽是一个程序设计问题，和语言无关。封装则是语言设计问题。抽象被有效封装的前提是有机制防止外界对抽象中隐蔽信息的访问。,返回,67,6.3 通过子程序封装,子程序是程序员定义的抽象操作是大多数程序的基本建筑块。对子程序可从两个方面来看： 在程序设计级子程序表示程序员定义的抽象操作。 在语言设计

39、级涉及子程序设施的设计和实现。,68,子程序作为抽象操作,子程序的规约和实现均由程序员提供。 子程序的规约和基本原操作类似，包括： 1、子程序的名字 2、子程序的基调 3、子程序的动作,69,子程序的规约,子程序可以表示成将一组特定的参数映射到特定的结果集的数学函数。 函数式子程序（即函数） 返回单个结果对象 过程式子程序（即过程或子程序） 返回多个结果，或通过修改参数的值来返回结果,70,子程序的规约,函数子程序显示地返回单个结果数据对象。 基调为：FN：realintegerreal 过程式子例程返回多个结果，或修改参数而不是显式地返回结果。 如C语言中： void Sub(float X

40、, int Y, float * Z, int *W); 无显式返回，*表示指针，可以被修改的参数。 Ada中： procedure Sub (X: in REAL; Y: in integer; Z: inout REAL; W: out Boolean) 其基调为： Sub: real1integerreal2real3Boolean in和out指出参数的性质。,71,子程序的规约,当子程序表示数学函数，如何精确地描述其功能有如下问题： 1、子程序可能有隐式参数（以非局部变量形式） 2、子程序可能有隐式结果（副作用）（对非局部变量和in-out参数） 3、可能对某些可能的参数没有定义。

41、4、子程序是历史敏感的。,72,子程序的实现,一个子程序表示了由程序员构造的虚拟机层次上的一个操作。这样，子程序用程序语言本身提供的数据结构和操作来实现。 子程序的实现用子程序体定义。包括： 局部数据声明定义局部结构或数据； 语句定义动作。 封装保证：局部数据和语句不可被用户单独访问，只能通过传入参数而调用子程序。 有些语言中，子程序体中也允许其他子程序的定义。 子程序调用需要合适类型的参数，因此，类型检查也是需要的。类型检查和基本操作类似处理。,返回,73,子程序定义和调用,子程序定义和子程序激活 子程序定义描述程序的静态性质，在执行中，如子程序被调用，则子程序的一个激活被创建，当子程序执行

42、结束，则激活被消除，因此，定义作为创建执行过程中激活的模板。 定义和激活的不同是重要的。 定义是程序的语法成分，其信息只是在翻译时所用信息（如变量类型，但其左、右值并不知道）。 激活在执行时存在（可访问左值、执行右值，但类型不再可用，除非描述子）。,74,子程序定义和调用,二者的差别类似于类型（作为模板）定义和数据对象（运行的创建）的差别。 malloc在程序运行时创建新对象。 call则是创建一个新的程序激活。 事实上，激活也可视为一种数据对象，表示为存储块，含有分量数据项。 激活也有生命期。 激活中独有的概念有：执行某激活，在执行中引用和修改其他数据对象。,返回,75,子程序定义和激活的实

43、现,考虑C中的子程序定义： float FN (float X, int Y) const initval=2; /常量定义:initval有左值和右值。 #define finalval 10 /宏定义：finalval无左值，只有右值。 Float M(10); int N; N=initval; If (Nfinalval) Return (20*X+M(N); ,76,子程序的激活,这个定义描述了子程序的运行时激活所需的部件 1、FN的基调行定义了参数和结果所需存储信息。 2、声明提供了局部变量的存储（M和N）。 3、文字及被定义常量的存储。 4、从子程序体中语句生成的可执行代码的存储

44、。,77,子程序的激活,激活的模板分为两个部分： 静态部分：称为代码段，包含常量和可执行代码。它在子程序执行中是不变的，可被所有激活共享。 动态部分：称为激活记录，包含参数、结果、局部数据以及其它实现项（临时存储区、返回点、非局部变量引用连接等），每个激活有相同结构，但数值不同。,78,子程序的激活,激活记录的结构和大小在翻译时确定，其在存储中的表示和记录类型的数据对象类似。 为了创建激活记录，只需要知道存储块的尺寸，不需知道其结构细节，因为块中位移已在编译时确定，只是基地址在运行时确定。因此，不需在运行时存放完全的激活模板，只需存放尺寸大小即可。 当子程序调用时，有一些隐敝动作发生，这些动作

45、在实际代码执行前完成。 子程序终止时，也有一些动作，这些动作代码是编译插入的。,返回,79,6.4 类型定义,要定义一个新的抽象数据类型，需要某种机制来定义一组数据对象，这种机制称为类型定义。 在类型定义中，给出一个类型名，以及关于数据对象结构的声明。 如：PASCAL中： type Rational = record numerator:integer demominator:integer End 声明：var A, B, C: Rational 不需要重复描述结构。,C语言中： struct RationalType int numerator; int denominator; 声明：

46、struct RationalType A, B, C;,80,类型定义,上述（C语言）定义方式违背了我们的数据抽象原则。我们希望新类型是语言的自然扩展，在语法和语义上类似基本类型，但struct的使用破坏了此规则。采用另一个方可解决这个问题。 Typedef struct RationalType 这里typedef类似宏 int numerator; int denominator;Rational 声明：Rational A, B, C;,81,类型定义,类型定义的优点：修改局部化，只需对类型修改即可。作为参数时，不需全写类型定义。 类型定义在执行中用为构造数据对象的模板。 类型定义是封

47、装和信息隐蔽的一种新形式，隐蔽了内部结构。 实现：类型定义只在翻译过程中使用，对语言实现本身没有什么影响。,82,类型等价,类型检查涉及类型的比较，类型等价带来两个相关概念： 1、两个类型相同，含义是什么？ 类型问题 2、同类型的两个数据对象相等，含义是什么？语义问题 类型相等 例(Pascal)： Program main (input, output); type Vect1 = Array 110 of real; Vect2 = Array 110 of real; Var X, Z: Vect1; Y: Vect2; Procedure Sub (A: Vect 1); End Be

48、gin X=Y; Sub(Y) end 问题：是否X、Y、Z和A有相同类型？,83,类型相等的判定(1/2),名等价两个类型是等价的，仅当他们有相同名字 这样Vect1, Vect2不是相同类型，虽然有相同结构。 X:=Y是非法的。 名等价的缺点： 1、每个数据对象必须有类型名：不能有匿名类型。 如：Var W: array 110 of real W有类型，但不能作为子程序参数，因其无类型名。 2、单个类型定义必须为所有或大部分程序服务，需有单独的全局类型定义。,84,类型相等的判定(2/2),结构等价两个类型是等价的，仅当他们有相同的内部部件（意味着相同存储表示）。这样Vect1,Vect

49、2是等价类型。 缺点： 1、结构等价带来一些微妙问题，如：对记录，是否部件名必须相同？是否数组下标域是相同的？枚举中文字和顺序是否必须相同。 2、即使程序员将两个变量声明为不同类型，但可能是结构等价的。 例:type Meters=integer; Liters=integer; Var Len: Meters; Vol: Liters; Len和Vol是结构等价的，这样Len+Vol这样的类型错便不可检测。 3、经常确定两个复杂类型是否结构等价、翻译代价较大。 类型等价的方式在语言设计中是一个重要问题。,85,数据对象相等,编译器确定两个对象有相同类型，但它们是否相等？大多数语言对此没有提供帮助。 例： struct stack struct set in