程序封装.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,可变记录:实现,可变记录的实现比正确地使用它要容易。在翻译时,每个变体的部件的存储需要量是确定的,存储的分配根据最大的可能变体来安排。在存储块内,每个变体根据
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 程序 封装
链接地址:https://www.31doc.com/p-4156287.html