第八章
抽 象 二,继 承
8.1 抽象数据类型回顾
第五章中,ADT是程序员定义的新数据类型，包括,
1、一个程序员定义的数据类型。
2、一组在该类型对象上的抽象操作。
3、该类型对象的封装。新类型的用户只能通过定义的操作
来操纵那些对象。
数据抽象是前面讨论的程序设计的基础部分，涉及抽象数据对
象及其操作的定义。
如果语言没有提供对数据抽象的支持，程序员仍然可以设计自
己的抽象数据类型，当然，这个概念在语言中颁布存在。程序
员需使用“编码约定”来组织他的程序。在这种情况下，封装
是不可能的。
类型定义使得变量的声明简单化，只需在声明中写入类型名。
但是，该类型的数据对象的内部结构不能对外封装。
任意一个可以声明某类型变量的子程序均可以访问该类型表示
的任意分量。任何这样的子程序均可以旁路数据对象上定义的
操作，而直接访问和操作该数据对象的部件。
封装的意图是要使得这样的访问不可能。仅仅那些知道数据对
象的内部表示的子程序是该类型上的操作，被定义为类型的一
部分。
Ada,C++,Smalltalk等语言提供了抽象类型定义机制。 Ada中
的 Package是抽象数据类型定义的形式。图 8.1是一个例子。
Private部分指出外界不能访问的内部结构。在包中定义的子程序
才可以访问私有数据。
Ada
中
抽
象
数
据
类
型
定
义
?实现
图 8.2给出了实现封装数据对象的两个模型。
间接封装（图 8.2（ a））：抽象数据类型的结构包规约 A定
义，对象 P的实际存储在 A的激活记录中维护。包 B中声明和
使用对象 P，运行时激活记录必须包含一个到实际数据存储
的指针。
直接封装（图 8.2（ b））：对象 P的实际存储在 B的激活记录
中维护。
在间接封装中,ADT的实现独立于其使用,A的内部修改不
影响 B。但运行时间花销大。
直接封装中：和上面情形相反，对 P的访问会省时间，但如
抽象对象的表示改变，所有它的使用的实例需重编译。时间
花销在编译过程中。
Ada使用直接封装模型。因此翻译抽象数据对象的使用将需
要对象表示的详细细节，即需知道包规约中的私有部分。
抽象数据的两种实现模型
直接封装和间接封装可以用在支持封装的任何程序中，而不
管其在语言中实现的封装模型是什么。
虽然 Ada中使用直接封装，程序员也可以实现间接封装。
图 8.3展示了 Ada中的两种实现策略。分别对应图 8.2的两种模
型的实现。
图 8.3b的直接封装的变体可以为,
Package A is
Type MyStack is record
Top,integer;
A,array (1..100) of integer;
End record;
…,
在此情形，激活记录组织和直接封装一样，但是，所有名字
均在 B中可见。
这也是在不提供封装机制的语言中常用的方式。
Ada数据的两种封装例子
指针类型
?类属抽象数据类型
语言固有的基本数据类型经常允许程序员声明一类新的数据
对象的基本类型，然后规约数据对象的几个属性。这是简单
的多态形式。
如,PASCAL提供了基本的数组类型，但也留下了用户可以
进一步定义的部分，如下标范围。
Type Vect = array [1..10] of real;
图 8.4是一个整数栈的规约。如要实数栈，则需另外规约。
类属抽象类型定义允许类型的一个属性被分离地规约，从而
给出一个基类型定义。使用该属性为参数，进而可从同一个
基类型导出几个特殊类型。
它们的结构和基类型类似，但参数可影响抽象类型定义中操
作的定义以及类型本身的定义。参数可以是类型名或值。图
8.5是类属栈类型的例子。
Ada
中
整
数
栈
抽
象
Ada
中
类
属
栈
抽
象
?类属抽象类型定义的实例化
一个类属包定义表示了一个模板，可用于创建特殊的抽
象数据类型。这个创建过程称为实例化，通过一组参数
的代入。
例：图 8.5类属栈类型定义的实例化,
package IntStackType is
new AnyStackType(elem=> integer);
package SetStackType is
new AnyStackType(elem=> Section);
不同大小的整数栈的声明,
Stk1,IntStackType.Stack(100);
NewStk,IntStackType.Stack(20);
类属类型 AnyStackType可以用不同的参数值多次实例化，
每次实例化均产生包中类型名 Stack的另一个定义。这样
当栈在声明中被引用时，有可能是含混的。
Ada中需要将包名放在类型名前作前缀，如,
IntStackType.stack或 SetStackType.stack
在 C++中，用模板来定义类属类,
template <class type_name> class classname class_definition
?实现：类属抽象数据类型通常有直接的实现。实例化时，必
须给出参数，编译器使用类属定义为模板，插入参数值，然
后编译该定义。
在程序执行过程中，只有数据对象和子程序出现。包定义仅
仅作为限制数据对象和子程序可见性的设备，包本身并不出
现在运行时。
如果类属类型定义被多次实例化，则该直接实现可能过于低
效，需要考虑避免产生过多的子程序拷贝及重复编译。
8.2 继承
在程序中某部分知道的信息经常在程序的另一部分需要和使用。
如：子程序调用的数据传递机制实现从实参到形参的传递。
信息也经常在程序部件间隐式地传递，这种传递称为继承。继
承是指一个程序部件从另一个程序部件按照它们之间的特殊关
系接收性质和特征。
继承的早期形式可在块结构数据的作用域规则中找到。使用于
内层的名字可以从外层继承。如,
{int I,j; {float j,k; k = i + j; }}
在 k = i + j中,j和 k均为局部浮点数,i从外层块继承而来。 j的内
层重定义覆写了外层定义，从而阻止了继承。
虽然作用域规则是一种继承形式，但继承这个术语更多地用于
指在独立程序模块间的数据和功能传递。如,C++中类间的继承。
继承分单继承和多继承。如图 8.6。
单继承和多继承
导出（派生）类
OO语言中的类是和封装概念紧密地联系在一起的。典型地，
类有一部分可被另一个类继承，有一部分被内部使用并对外
隐藏。 C++中整数栈的定义为,
class intstack
{public,
intstack() {size=0;}
void push(int i) {size=size+1; storage[size]=i;}
int pop…
private,
int size;
int storage(100);
}
C++中的继承通过派生类的使用而发生。
例如，一个类创建类型 elem的对象，另一个类创建该类型对
象的栈，如图 8.7。
ElemStack是派生类,elem是基类。
这个例子用类来封装数据,
1、所有在 elem中的公共名字被 ElemStack继承。这些名字
在派生类中也是公共的。可为外界所知道。
2、类型 elem的一个对象的内容是私有数据，不为类定义
的外界所知道。在本例中,ToElem和 FromElem是强制操
作子，完成整数和 elem类型间的转换。如果类的内部结构
是私有的，则这些操作总是需要的。
关键词 private和 public控制了被继承对象的可见性。 C++中还
使用 protected来表示：名字对基类型的任何派生类均可见，
但不为类定义层次的外界所知。
C++
中
派
生
类
?实现,
实现类并不会给翻译器增加太多的工作量。在某派生类
中,
只有从基类继承的名字被加入到派生类的局部名空间，
而且仅仅是公共的名字对外可见。被定义对象的实际存
储表示可以通过类定义中的数据声明静态地确定。
如果在类定义中有构造子存在，则翻译器必须在遇到新
的对象声明时调用该构造函数，例，在块的入口。
对方法调用，翻译器需要将信息传向的对象考虑为隐含
的第一参数，如,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，
我们不能在程序中作如下的声明,
ElemStack x；
然而，我们可将 ElemStack用作超类模板，而所有使用该类定
义的对象均来自其派生类。任意派生类为了创建实例，必须
重定义虚函数。
?Mixin继承：仅仅定义基类和新的派生类间的不同。考虑上
面的例子，我们不是直接定义新类 NewStack，而是定义一个
delta类来表示变化。采用 C++语法，有,
Deltaclass StackMod
{int peek() {return storage[size].FromElem()}}
从而,class NewStack = Class ElemStack + deltaclass
StackMod
一个重要的要点是,delta类可用于任意类。
对象和消息
Smalltalk是 OO语言的开先河者,Xerox Palo Alto研究中心的
Alan Kay在 70年代领导开发。 Smalltalk在其纯 OO特性、窗口
化的界面、以及鼠标的应用等方面的工作均是革命性的。
Smalltalk程序是一组类定义。信息隐蔽和封装是其固有特性。
一个 Smalltalk程序有三个主要的语言特性,
类定义：可执行语句，定义对象的内部结构和方法。
对象的实例化：通过调用类定义中的创建方法可以为类定
义创建特定的对象。方法可以为类实例定义。
消息传递：对象之间通过消息传递进行交互。有三类消息,
单元消息,x ← Set new
二元消息,x ← 3 + 6
关键字消息,x ← Array new,10,x at,3 put,42
?类继承
Smalltalk数据基于一个类网层，方法的查找沿网层上行。
网层的根是所有类的超类，称为 Object。
Smalltalk仅仅处理单继承。
self用于指向方法被传向的对象。
Smalltalk中类也作为对象处理，因此，具有高阶性。
Smalltalk的实现采用了基于 byte code的解释执行方式，有
一个虚拟机来执行 byte code。
抽象概念
封装提供了“分而治之”的机制，继承提供了对象间传递信
息的机制。有四种类及其对象间的关系,
特殊化：最常见的继承形式，允许派生类得到比其父类更
精确的信息。相反的概念是“一般化”。
分解：将一个抽象分成若干部件。相反的概念是“聚合”。
实例化：创建类的一个实例。本质上是一个拷贝操作。相
反的概念是“分类”。
个体化：类似的对象被组合在一起以达成共同的目的。相
反的概念是“成（编）组”。例如，翻译器中的栈可以是
激活记录和符号表,C和 PASCAL均将激活记录实现为栈，
但各有不同特征。
图 8.9给出了抽象概念。
抽象概念
8.3 多态
多态是指多个操作子或子程序名可指向一组函数定义，具体定
义的选择依赖于参数和结果的数据类型。
多态的几种形式,
重定义－－一名多用
重载－－固有重载和虚函数重载
包含多态－－由于继承机制的存在
语义多态－－类型作为参数，函数作为参数
抽 象 二,继 承
8.1 抽象数据类型回顾
第五章中,ADT是程序员定义的新数据类型，包括,
1、一个程序员定义的数据类型。
2、一组在该类型对象上的抽象操作。
3、该类型对象的封装。新类型的用户只能通过定义的操作
来操纵那些对象。
数据抽象是前面讨论的程序设计的基础部分，涉及抽象数据对
象及其操作的定义。
如果语言没有提供对数据抽象的支持，程序员仍然可以设计自
己的抽象数据类型，当然，这个概念在语言中颁布存在。程序
员需使用“编码约定”来组织他的程序。在这种情况下，封装
是不可能的。
类型定义使得变量的声明简单化，只需在声明中写入类型名。
但是，该类型的数据对象的内部结构不能对外封装。
任意一个可以声明某类型变量的子程序均可以访问该类型表示
的任意分量。任何这样的子程序均可以旁路数据对象上定义的
操作，而直接访问和操作该数据对象的部件。
封装的意图是要使得这样的访问不可能。仅仅那些知道数据对
象的内部表示的子程序是该类型上的操作，被定义为类型的一
部分。
Ada,C++,Smalltalk等语言提供了抽象类型定义机制。 Ada中
的 Package是抽象数据类型定义的形式。图 8.1是一个例子。
Private部分指出外界不能访问的内部结构。在包中定义的子程序
才可以访问私有数据。
Ada
中
抽
象
数
据
类
型
定
义
?实现
图 8.2给出了实现封装数据对象的两个模型。
间接封装（图 8.2（ a））：抽象数据类型的结构包规约 A定
义，对象 P的实际存储在 A的激活记录中维护。包 B中声明和
使用对象 P，运行时激活记录必须包含一个到实际数据存储
的指针。
直接封装（图 8.2（ b））：对象 P的实际存储在 B的激活记录
中维护。
在间接封装中,ADT的实现独立于其使用,A的内部修改不
影响 B。但运行时间花销大。
直接封装中：和上面情形相反，对 P的访问会省时间，但如
抽象对象的表示改变，所有它的使用的实例需重编译。时间
花销在编译过程中。
Ada使用直接封装模型。因此翻译抽象数据对象的使用将需
要对象表示的详细细节，即需知道包规约中的私有部分。
抽象数据的两种实现模型
直接封装和间接封装可以用在支持封装的任何程序中，而不
管其在语言中实现的封装模型是什么。
虽然 Ada中使用直接封装，程序员也可以实现间接封装。
图 8.3展示了 Ada中的两种实现策略。分别对应图 8.2的两种模
型的实现。
图 8.3b的直接封装的变体可以为,
Package A is
Type MyStack is record
Top,integer;
A,array (1..100) of integer;
End record;
…,
在此情形，激活记录组织和直接封装一样，但是，所有名字
均在 B中可见。
这也是在不提供封装机制的语言中常用的方式。
Ada数据的两种封装例子
指针类型
?类属抽象数据类型
语言固有的基本数据类型经常允许程序员声明一类新的数据
对象的基本类型，然后规约数据对象的几个属性。这是简单
的多态形式。
如,PASCAL提供了基本的数组类型，但也留下了用户可以
进一步定义的部分，如下标范围。
Type Vect = array [1..10] of real;
图 8.4是一个整数栈的规约。如要实数栈，则需另外规约。
类属抽象类型定义允许类型的一个属性被分离地规约，从而
给出一个基类型定义。使用该属性为参数，进而可从同一个
基类型导出几个特殊类型。
它们的结构和基类型类似，但参数可影响抽象类型定义中操
作的定义以及类型本身的定义。参数可以是类型名或值。图
8.5是类属栈类型的例子。
Ada
中
整
数
栈
抽
象
Ada
中
类
属
栈
抽
象
?类属抽象类型定义的实例化
一个类属包定义表示了一个模板，可用于创建特殊的抽
象数据类型。这个创建过程称为实例化，通过一组参数
的代入。
例：图 8.5类属栈类型定义的实例化,
package IntStackType is
new AnyStackType(elem=> integer);
package SetStackType is
new AnyStackType(elem=> Section);
不同大小的整数栈的声明,
Stk1,IntStackType.Stack(100);
NewStk,IntStackType.Stack(20);
类属类型 AnyStackType可以用不同的参数值多次实例化，
每次实例化均产生包中类型名 Stack的另一个定义。这样
当栈在声明中被引用时，有可能是含混的。
Ada中需要将包名放在类型名前作前缀，如,
IntStackType.stack或 SetStackType.stack
在 C++中，用模板来定义类属类,
template <class type_name> class classname class_definition
?实现：类属抽象数据类型通常有直接的实现。实例化时，必
须给出参数，编译器使用类属定义为模板，插入参数值，然
后编译该定义。
在程序执行过程中，只有数据对象和子程序出现。包定义仅
仅作为限制数据对象和子程序可见性的设备，包本身并不出
现在运行时。
如果类属类型定义被多次实例化，则该直接实现可能过于低
效，需要考虑避免产生过多的子程序拷贝及重复编译。
8.2 继承
在程序中某部分知道的信息经常在程序的另一部分需要和使用。
如：子程序调用的数据传递机制实现从实参到形参的传递。
信息也经常在程序部件间隐式地传递，这种传递称为继承。继
承是指一个程序部件从另一个程序部件按照它们之间的特殊关
系接收性质和特征。
继承的早期形式可在块结构数据的作用域规则中找到。使用于
内层的名字可以从外层继承。如,
{int I,j; {float j,k; k = i + j; }}
在 k = i + j中,j和 k均为局部浮点数,i从外层块继承而来。 j的内
层重定义覆写了外层定义，从而阻止了继承。
虽然作用域规则是一种继承形式，但继承这个术语更多地用于
指在独立程序模块间的数据和功能传递。如,C++中类间的继承。
继承分单继承和多继承。如图 8.6。
单继承和多继承
导出（派生）类
OO语言中的类是和封装概念紧密地联系在一起的。典型地，
类有一部分可被另一个类继承，有一部分被内部使用并对外
隐藏。 C++中整数栈的定义为,
class intstack
{public,
intstack() {size=0;}
void push(int i) {size=size+1; storage[size]=i;}
int pop…
private,
int size;
int storage(100);
}
C++中的继承通过派生类的使用而发生。
例如，一个类创建类型 elem的对象，另一个类创建该类型对
象的栈，如图 8.7。
ElemStack是派生类,elem是基类。
这个例子用类来封装数据,
1、所有在 elem中的公共名字被 ElemStack继承。这些名字
在派生类中也是公共的。可为外界所知道。
2、类型 elem的一个对象的内容是私有数据，不为类定义
的外界所知道。在本例中,ToElem和 FromElem是强制操
作子，完成整数和 elem类型间的转换。如果类的内部结构
是私有的，则这些操作总是需要的。
关键词 private和 public控制了被继承对象的可见性。 C++中还
使用 protected来表示：名字对基类型的任何派生类均可见，
但不为类定义层次的外界所知。
C++
中
派
生
类
?实现,
实现类并不会给翻译器增加太多的工作量。在某派生类
中,
只有从基类继承的名字被加入到派生类的局部名空间，
而且仅仅是公共的名字对外可见。被定义对象的实际存
储表示可以通过类定义中的数据声明静态地确定。
如果在类定义中有构造子存在，则翻译器必须在遇到新
的对象声明时调用该构造函数，例，在块的入口。
对方法调用，翻译器需要将信息传向的对象考虑为隐含
的第一参数，如,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，
我们不能在程序中作如下的声明,
ElemStack x；
然而，我们可将 ElemStack用作超类模板，而所有使用该类定
义的对象均来自其派生类。任意派生类为了创建实例，必须
重定义虚函数。
?Mixin继承：仅仅定义基类和新的派生类间的不同。考虑上
面的例子，我们不是直接定义新类 NewStack，而是定义一个
delta类来表示变化。采用 C++语法，有,
Deltaclass StackMod
{int peek() {return storage[size].FromElem()}}
从而,class NewStack = Class ElemStack + deltaclass
StackMod
一个重要的要点是,delta类可用于任意类。
对象和消息
Smalltalk是 OO语言的开先河者,Xerox Palo Alto研究中心的
Alan Kay在 70年代领导开发。 Smalltalk在其纯 OO特性、窗口
化的界面、以及鼠标的应用等方面的工作均是革命性的。
Smalltalk程序是一组类定义。信息隐蔽和封装是其固有特性。
一个 Smalltalk程序有三个主要的语言特性,
类定义：可执行语句，定义对象的内部结构和方法。
对象的实例化：通过调用类定义中的创建方法可以为类定
义创建特定的对象。方法可以为类实例定义。
消息传递：对象之间通过消息传递进行交互。有三类消息,
单元消息,x ← Set new
二元消息,x ← 3 + 6
关键字消息,x ← Array new,10,x at,3 put,42
?类继承
Smalltalk数据基于一个类网层，方法的查找沿网层上行。
网层的根是所有类的超类，称为 Object。
Smalltalk仅仅处理单继承。
self用于指向方法被传向的对象。
Smalltalk中类也作为对象处理，因此，具有高阶性。
Smalltalk的实现采用了基于 byte code的解释执行方式，有
一个虚拟机来执行 byte code。
抽象概念
封装提供了“分而治之”的机制，继承提供了对象间传递信
息的机制。有四种类及其对象间的关系,
特殊化：最常见的继承形式，允许派生类得到比其父类更
精确的信息。相反的概念是“一般化”。
分解：将一个抽象分成若干部件。相反的概念是“聚合”。
实例化：创建类的一个实例。本质上是一个拷贝操作。相
反的概念是“分类”。
个体化：类似的对象被组合在一起以达成共同的目的。相
反的概念是“成（编）组”。例如，翻译器中的栈可以是
激活记录和符号表,C和 PASCAL均将激活记录实现为栈，
但各有不同特征。
图 8.9给出了抽象概念。
抽象概念
8.3 多态
多态是指多个操作子或子程序名可指向一组函数定义，具体定
义的选择依赖于参数和结果的数据类型。
多态的几种形式,
重定义－－一名多用
重载－－固有重载和虚函数重载
包含多态－－由于继承机制的存在
语义多态－－类型作为参数，函数作为参数
