抽象数据类型

第七章继承抽象：数据处理（或方法）自动封装：抽象数据类型自动推导数据对象的操作—继承操作的多态Smalltalk简介7.1抽象数据类型回顾数据抽象类型基本概念，及与类型定义的区别实现类属抽象数据类型基本概念实例化实现抽象数据类型ADT是程序员定义的新数据类型，包括：1、一个程序员定义的数据类型。2、一组在该类型对象上的抽象操作。3、该类型对象的封装。新类型的用户只能通过定义的操作来操纵那些对象。数据抽象是程序设计的基础部分，涉及抽象数据对象及其操作的定义。类型定义与封装类型定义使得变量的声明简单化，只需在声明中写入类型名。但是，该类型的数据对象的内部结构不能对外封装。任意一个可以声明某类型变量的子程序均可以访问该类型表示的任意分量。任何这样的子程序均可以旁路数据对象上定义的操作，而直接访问和操作该数据对象的部件。封装的意图是要使得这样的访问不可能。仅仅那些知道数据对象的内部表示的子程序是该类型上的操作，且被定义为类型的一部分。抽象数据类型：例子Ada、C++、Smalltalk等语言提供了抽象类型定义机制。Ada中的Package是抽象数据类型定义的形式。Private部分指出外界不能访问的内部结构。在包中定义的子程序才可以访问私有数据。Ada中抽象数据类型定义返回抽象数据类型：实现实现封装数据对象的两个模型。间接封装（图（a））抽象数据类型的结构包A中不仅有对象P的定义，对象P的实际存储在A的激活记录中维护。包B中声明和使用对象P，运行时激活记录必须包含一个到实际数据存储的指针。直接封装（图（b））对象P的实际存储在B的激活记录中维护。在间接封装中，ADT的实现独立于其使用，A的内部修改不影响B。但运行时间花销大。直接封装中：和上面情形相反，对P的访问会省时间，但如抽象对象的表示改变，所有它的使用的实例需重编译。时间花销在编译过程中。抽象数据类型：实现Ada使用直接封装模型。因此翻译抽象数据对象的使用将需要对象表示的详细细节，即需知道包规约中的私有部分。直接封装和间接封装可以用在支持封装的任何程序中，而不管其在语言中实现的封装模型是什么。抽象数据类型：实现虽然Ada中使用直接封装，程序员也可以实现间接封装。Ada中的两种实现策略：图b的直接封装的变体可以为：PackageAisTypeMyStackisrecordTop:integer;A:array(1..100)ofinteger;Endrecord;….在此情形，激活记录组织和直接封装一样，但是，所有名字均在B中可见。这也是在不提供封装机制的语言中常用的方式。返回类属抽象数据类型语言固有的基本数据类型经常允许程序员声明一类新的数据对象的基本类型，然后规约数据对象的几个属性。这是简单的多态形式。如，PASCAL提供了基本的数组类型，但也留下了用户可以进一步定义的部分，如下标范围。TypeVect=array[1..10]ofreal;类属抽象数据类型Ada中整数栈抽象例子类属抽象数据类型类属抽象类型定义允许类型的一个属性被分离地规约，从而给出一个基类型定义。使用该属性为参数，进而可从同一个基类型导出几个特殊类型。它们的结构和基类型类似，但参数可影响抽象类型定义中操作的定义以及类型本身的定义。参数可以是类型名或值。类属抽象数据类型Ada中类属栈抽象例子返回类属抽象类型定义的实例化一个类属包定义表示了一个模板，可用于创建特殊的抽象数据类型。这个创建过程称为实例化，通过一组参数的代入。例：前图类属栈类型定义的实例化：packageIntStackTypeisnewAnyStackType(elem=integer);packageSetStackTypeisnewAnyStackType(elem=Section);不同大小的整数栈的声明：Stk1:IntStackType.Stack(100);NewStk:IntStackType.Stack(20);类属抽象类型定义的实例化类属类型AnyStackType可以用不同的参数值多次实例化，每次实例化均产生包中类型名Stack的另一个定义。这样当栈在声明中被引用时，有可能是含混的。Ada中需要将包名放在类型名前作前缀，如：IntStackType.stack或SetStackType.stack在C++中，用模板来定义类属类：templateclasstype_nameclassclassnameclass_definition返回类属抽象数据类型：实现类属抽象数据类型通常有直接的实现。实例化时，必须给出参数，编译器使用类属定义为模板，插入参数值，然后编译该定义。在程序执行过程中，只有数据对象和子程序出现。包定义仅仅作为限制数据对象和子程序可见性的设备，包本身并不出现在运行时。如果类属类型定义被多次实例化，则该直接实现可能过于低效，需要考虑避免产生过多的子程序拷贝及重复编译。返回7.2继承在程序中某个地方的信息经常需要在程序的另一地方使用。如：子程序调用的数据传递机制实现从实参到形参的传递。继承提供了从一个数据对象向另一个数据对象自动传递信息的手段。面向对象中的继承概念继承的分类继承的形式：派生类、方法继承、抽象类继承的原则继承继承的早期形式可在块结构数据的作用域规则中找到。使用于内层的名字可以从外层继承。如：{intI,j;{floatj,k;k=i+j;}}在k=i+j中，j和k均为局部浮点数，i从外层块继承而来。j的内层重定义覆写了外层定义，从而阻止了继承。虽然作用域规则是一种继承形式，但继承这个术语更多地用于指在独立程序模块间的数据和功能传递。如：C++中类间的继承。在面向对象的语言中，数据的继承是通过派生类显式地实现的。返回继承继承分单继承和多继承。返回导出（派生）类OO语言中的类是和封装概念紧密地联系在一起的。典型地，类有一部分可被另一个类继承，有一部分被内部使用并对外隐藏。C++中整数栈的定义为：classintstack{public:intstack(){size=0;}voidpush(inti){size=size+1;storage[size]=i;}intpop…private:intsize;intstorage(100);}派生类C++中的继承通过派生类的使用而发生。例如，一个类创建类型elem的对象，另一个类创建该类型对象的栈。ElemStack是派生类，elem是基类。这个例子用类来封装数据：1、所有在elem中的公共名字被ElemStack继承。这些名字在派生类中也是公共的。可为外界所知道。2、类型elem的一个对象的内容是私有数据，不为类定义的外界所知道。在本例中，ToElem和FromElem是强制操作子，完成整数和elem类型间的转换。如果类的内部结构是私有的，则这些操作总是需要的。关键词private和public控制了被继承对象的可见性。C++中还使用protected来表示：名字对基类型的任何派生类均可见，但不为类定义层次的外界所知。派生类：实现实现类并不会给翻译器增加太多的工作量。在某派生类中，只有从基类继承的名字被加入到派生类的局部名空间，而且仅仅是公共的名字对外可见。被定义对象的实际存储表示可以通过类定义中的数据声明静态地确定。如果在类定义中有构造子存在，则翻译器必须在遇到新的对象声明时调用该构造函数，例，在块的入口。对方法调用，翻译器需要将信息传向的对象考虑为隐含的第一参数，如：x.push(i)处理为push(x,i)。存储管理和标准C相同。类的每个实例有自己的数据存储，包括数据和到方法的指针。对派生类，采用拷贝方法来实现继承。对象的存储包含所有实现细节。另外一种方法称为代理方法，派生类对象将使用基类对象的数据存储。这种方法需要数据共享，并传播变化。返回方法继承通过方法继承而创建新的对象提供了超越封装的能力。例如，考虑ElemStack的扩展：加入公共过程MyType以打印出类型名字，将ElemStack的内部结构改为protected，使其可以被所有派生类继承。如希望一新类NewStack，它需要一返回栈顶值的操作，因此只需在继承ElemStack的基础上加上操作peek。原ElemStack中所有操作均可以对NewStack适用，而对ElemStack的修改也对NewStack透明。唯一的问题是：方法MyType仍然打印相同的内容。解决方法有二：1、简单地重定义MyType方法。当所需修改太多时，这是一项烦琐的工作。2、使用虚函数。将函数的绑定推迟到调用时。方法继承：实现虚方法可按类似于激活记录的中心环境表的方式实现。派生类中每个虚方法保留一个槽，由构造函数在创建对象时填充。返回抽象类有时人们希望类定义仅仅用作类的模板，而不允许用来声明对象。从而引出抽象超类和mixin继承的概念。抽象超类：考虑前面的具有虚方法MyType的类ElemStack，我们不能在程序中作如下的声明：ElemStackx；然而，我们可将ElemStack用作超类模板，而所有使用该类定义的对象均来自其派生类。任意派生类为了创建实例，必须重定义虚函数。Mixin继承：仅仅定义基类和新的派生类间的不同。考虑上面的例子，我们不是直接定义新类NewStack，而是定义一个delta类来表示变化。采用C++语法，有：DeltaclassStackMod{intpeek(){returnstorage[size].FromElem()}}从而，classNewStack=ClassElemStack+deltaclassStackMod一个重要的要点是：delta类可用于任意类。返回继承的原则继承提供了对象间传递信息的机制：特殊化：最常见的继承形式，允许派生类得到比其父类更精确的信息。相反的概念是“一般化”。分解：将一个抽象分成若干部件。相反的概念是“聚合”。实例化：创建类的一个实例。本质上是一个拷贝操作。相反的概念是“分类”。个性化：与“特殊化”相关，但它将对象按功能而不是按结构来分开。相反的概念是“成（编）组”。例如，堆栈和集合都有一个数组和一个索引指针，但它们的功能不能。返回7.3多态多态是指单个操作或子程序名可指向一组函数定义，具体定义的选择依赖于参数和结果的数据类型。多态的几种形式：重定义－－一名多用重载－－固有重载和虚函数重载包含多态－－由于继承机制的存在语义多态－－类型作为参数，函数作为参数返回多态的创建通常，可以通过构造参数化的对象来创建真正的多态，例如对象的堆栈：Y:stack(int,10)最多10整数Z:stack(float,20)最多20个实数对于那些不支持多态的语言，可以用“宏”来模拟多态。例如，在Pascal中：sum(int,A,B)可以用一个宏来实现，在宏中，根据参数的不同类型，可以从四种执行序列中选择一种：trunc(A)+BA+trunc(B)A+Btrunc(A)+trunc(B)多态的实现对于静态类型语言（如C++)，多态很容易实现：只要在编译器的符号表中，记住函数的参数类型即可。对于动态类型语言，可以将两种形式的参数传递给一个多态函数：1.一个直接描述符—当传给函数的参数值所占的空间小于固定字段的大小时。例如，在把一个布尔值、字符或小整数传给某个函数时，使用的空间比对象所允许的固定大小还要小，实际参数值放在参数所在的位置，字段多出来的位用来告诉函数参数值的类型到底是什么。2.否则，一个装箱（boxed）描述符。装箱（Boxed）描述符参数字段包含一个类型描述符，说明该参数被装在一个箱子里。字段的剩余部分为实际对象的地址（可能在其它地方，例如在堆存储区里）。在该地址内，给出完整的类型信息，例如一个复合数据对象的完整结构。动态多态的例子假设参数描述符字段为5个字节：第一个字节为数据类型描述符，第二到第五个字节为数据