2.8 抽象数据类型
Pascal，ALGOL 68和SIMULA 67等语言的用户定义类型，例如，2.4.2定义的用户定义类型reg_polygon，与这些语言的内部类型有着某些相似之处。无论内部类型还是用户定义类型都要建立某种基本表示的抽象。位串是integer的表示，记录是reg_polygon的表示。并且，每种类型都关联一组操作，算术和比较操作是与integer关联的，插入和打印是与reg_pol-ygon关联的。
然而，内部类型与用户定义类型也有重要的区别。对程序员来说，内部类型隐蔽了基本表示，不能对它的基本表示直接进行操作。程序员不能访问表示一个整数的位串的某个特定位。而对用户定义类型来说，例如，对类型reg_polygon，除了规定的插入和打印操作外，程序员还可以对其基本表示(记录)的成分直接进行操作。例如
t.no_of_edges：=3
是合法的，它确定t是一个等边三角形。
这里存在两个级别的抽象：内部类型是对(硬件)二进制位串的抽象；用户定义类型是对内部类型和已定义的用户定义类型作为基本表示的抽象。内部类型的基本表示是不可见的，而用户定义类型的基本表示是可见的。在这一节我们将讨论具有信息隐蔽(Information Hid-ing)、封装(Packaging，Encapsulation)和继承(Inheritance)等特性的新类型，称它们为抽象数据类型(Abstract Data Type)，它们是以内部类型和用户定义类型为基本表示的更高层次的抽象，它的基本表示也是不可见的。
20世纪60年代末期，当IBM 360出现在市场时，使计算机的计算能力大大提高，给人们带来了许多方便。但是，IBM 360的操作系统是由许多技术人员协作研制(编程)实现的，在使用中不断发现错误，究其原因在于编程人员众多，难免存在重复使用存储单元的问题，造成信息破坏。这时，有人惊呼“信息爆炸”和“软件危机”。为了避免自己的信息被别人破坏，人们提出了“信息隐蔽”的程序设计技术。程序设计语言也提供了相应的结构来支持这种技术。
所谓信息隐蔽，实际上是一个术语，即程序员在定义的抽象中，应该对用到这个抽象的用户隐蔽尽可能多的信息。如通常用到的函数，就具备一些这样的能力。封装实质上是语言为了支持信息隐蔽而提供的手段。将数据和对该数据进行的操作组成一个实体，用户不知道该实体对数据的行为(操作)的实现细节，只需根据该实体提供的外部特性接口来访问实体。
在大型软件设计中，有许多软件是可以重复使用的，我们把这种特性称为重用(Reuse)。重用可以减少许多重复开发，避免浪费人力与时间等资源，达到提高软件开发效率的目的。程序设计语言为了支持软件重用，提出了继承的概念。若一个程序中两个组成成分之间存在特殊联系，由一个组成成分去继承另一个组成成分的性质或特性，这样就实现了继承。在程序设计中，我们经常使用继承。
许多语言，例如CLU，Ada，Modula_2，C++和Java等，都设计了支持上述特性的机制，接下来我们将讨论这个机制。
前已叙述，内部类型和用户定义类型是不同的两个级别的抽象。一方面，可用reg_poly-gon作为新类型；另外，它又是根据更低级别的抽象来实现的。无论语言的内部类型还是用户定义类型，都是建立基本表示的抽象，都关联一组相应的操作。内部类型隐蔽了基本表示，不能对它的成分进行操作；用户定义类型具有更高级别的抽象，它由更低级别的抽象来实现，可以对其基本表示的成分进行操作。为了在语言的程序中定义新类型，语言应具有下列两个特性。
① 在允许实现这个新类型的程序单元中，建立与表示有关的具体操作。
② 对使用这个新类型的程序单元来说，新类型的表示是隐蔽的。
满足特性①和②的用户定义类型称为抽象数据类型(Abstract Data Type)。特性①使程序反映在程序设计时发现的抽象，使程序结构易于理解。特性②强制区分抽象层次，以提高程序的可修改性。传统的语言不能同时满足特性①和②，例如SIMULA 67的类只满足①而不满足②。新近的语言，例如CLU，Ada、C++和Java语言提供了定义抽象数据类型的机制，能同时满足①和②。
抽象数据类型是从更一般的信息隐蔽原则派生出来的。抽象数据类型隐蔽了表示的细节，通过过程来访问抽象数据对象。对象的表示是被保护的，防止了任何外界试图对它的直接操作。要对抽象数据类型的实现进行修改，只能在描述这个实现的程序单元中，对它的程序进行修改，而不影响整个程序的其他部分。抽象数据类型不只根据表示结构来为对象分类，而且还根据对象行为来为对象分类。这里对象行为指对数据的操作，如建立、修改和访问对象等操作。从SIMULA 67开始，许多程序设计语言，例如并发Pascal，CLU，Mesa，Euclid，Modula 2，Smalltalk，EIFFEL，C++和Ada等，都提供了某种语言构造，用于封装实现数据抽象的表示和具体操作，使程序员能在某种程度上定义抽象数据类型。在本书中将简要讨论SIMULA 67，CLU，Ada，Modula 2，C++和Java语言的有关机制。
2.8.1 SIMULA 67 语言的类机制
从图1-3可以看出，SIMULA 67是ALGOL 60的扩展，它又是一些面向对象语言和支持抽象数据类型语言的前身，这主要表现在类(Class)的概念上。
SIMULA 67主要用于系统描述和模拟，在描述离散事件的模拟这类特殊需要时，产生了类，后来人们发现它可作为一般工具，用于根据抽象层次来组织程序。
类的概念导致了抽象数据类型的思想，但类本身尚不是抽象数据类型，它仅满足抽象数据定义的特性①而不满足特性②。事实上，类为实现信息隐蔽模块和后来的面向对象程序设计奠定了基础。
类说明的一般形式为
<类头>；
<类体>
其中，类头包括类名和形式参数；类体是传统的分程序，可包含变量、过程和类的局部说明，以及一些执行语句。例如，用极坐标表示复数概念可由下列类说明描述：
class complex(x，y)；real x，y；
begin real angle，radius；
radius：=sqrt(x**2+y**2)；
if abs(x)<epsilon
then begin
ifabs(y)<epsilon
then error
else begin if y>epsilon
then angle：=pi/2
else angle：=3*pi/2
end
end
else angle：=arctan(y/x)
end complex
其中，参数x和y代表一个复数的两个笛卡儿坐标值，局部变量angle和radius代表复数在极坐标下的辐角和半径。sqrt和arctan是内部函数，error(未做说明)是在该类中可使用的一个报错过程。全局变量epsilon代表一个逼近零的正实数，全局变量pi代表π的值。
类说明定义了一类数据对象的原型(Prototype)或模板(Template)。类的每个实例(In-stance)是一个可操作的数据对象。类的实例在SIMULA中称为对象，可多次动态建立，且仅能通过指针引用。例如语句
ref(complex)c；
c ：-new complex (1.0，1.0)；
其中，第一条语句说明c是一个指向复数的指针；第二条语句使c指向一个新建立的复数对象。“：-”是SIMULA专用的引用赋值号，可读为“指向”。上述语句的效果如图2-7所示。
图2-7 复数类的一个实例
类实例的属性是指类体的局部变量和类头中的参数，可用圆点选择符“.”在此类的外部访问类实例的属性。因此，SIMULA的类不满足抽象数据类型定义中的条件(2)，例如，执行完上述两条语句之后，写出语句
my_angle：=c.angle；
my_radius：=c.radius；
my_x：=c.x；
my_y：=c.y；
使得my_angle = 0.78，my_radius = 1.42，my_x = 1.0，my_y = 1.0。
类实例的访问只能通过引用变量(例如上例中的指针c)完成。类实例没有名字，类的每个实例必须由new语句显式建立。类的实例是一个初始化了的对象，因为new语句要导致类体自动执行。
更一般地讲，类可视为支持抽象数据类型的封装机制，它可以封装实现对数据操作的各种过程。例如，用于实现复数加和乘的过程add和multiply，可以封装到类complex的类体说明中。这些操作作为complex的属性，可以用圆点访问，并可以带有参数。add和multiply封入类complex的过程头为
procedure add(operand)；ref(complex)operand；
和
procedure multiply(operand)；ref(complex)operand；
这里过程体从略。变量c1和c2引用的两个复数相加可表示为
cl.add(c2)
即c2作为参数传递给cl所关联的add过程。
虽然已经将add和multiply两个操作封装在类说明中，但SIMULA 67的圆点表示法允许访问对象的所有属性，因而语句
cl.angle：=c2.angle；
cl.radius：=c2.radius+c3.radius；
是正确的。在已知c2和c3的辐角时，c1代表了c2和c3相加。换言之，add和multiply不是对复数对象的仅有操作，因为用户可以直接访问复数的内部表示。
SIMULA 67还有一个特殊的构造用来定义类型的判定或和类属(Generic)抽象数据类型，这一构造称为子类(Subclass)，用来实现继承。它的用途很广，并可作为一种通用工具用于根据抽象层次来组织程序。它的说明方式是在类说明之前再加上另一个类的名字作为前缀。
假定我们要定义一个抽象的栈，并允许程序员对栈执行如下操作：
① 引用第一元素，即栈顶元素(top)；
② 在第一元素前下推一个新元素(push)；
③ 上托第一元素(pop)；
④ 测试栈是否为空(empty)。
这些操作与栈中元素的类型无关。我们先描述可作为栈内成员的元素类如下：
class stack_member；
begin ref(stack_member)next_member；
next_member ：- none
end；
上述说明指出了所有栈对象有唯一的一个共同性质，即它们都具有一个引用栈中下一项的属性。换句话说，stack_member的每个实例都具有属性next_member，其初值为none，它是一个指向空值的指针。类stack说明为
class stack；
begin ref(stack-member)first；
ref(stack-member)procedure top；
top：=first；
procedure pop；
if⇁empty then first：-first.next-member；
procedure push(e)；ref(stack-member)e；
begin if first=/=none
then e.next-member：=first；
first：=e
end push；
boolean procedure empty；
empty：=first==none；
first：=none
end stack
其中，符号“⇁”代表逻辑“非”；“=/=”代表“不等于”；“= =”代表“等于”；过程empty返回布尔值；stack的每个实例初始化为空栈，即属性first的初值为none。
有了上述stack_member和stack的定义，我们可构造出具有特定栈元素类型的栈，例如
stack_member class complex (…)；
……
end complex；
定义一个复数栈，其中省略号参见复数类的定义。语句
new complex；
产生的对象具有stack_member和complex的所有属性。换句话说，它们可作为栈元素的复数。complex称为stack_member的子类，它比stack_member更特殊，具有自己的属性，同时继承了stack_member的属性。
设已知s具有类型ref(stack)，下面的语句用于建立一个复数栈：
s ：- new stack；
此时，栈s不包含任何元素，s.empty将返回true。设c1，c2和c3为复数对象，其类型为com-plex，可用语句
s.push(c1)；
s.push(c2)；
s.push(c3)；
把它们插入栈，用s.top观察栈顶元素，用s.pop移出栈顶元素。
stack_member可看成其所有子类型对应的类型的联合。例如，程序中出现向量说明
stack_member class vector (…)；
……
end vector；
则具有类型ref(stack_member)的变量既可引用复数的stack_member，也可引用向量的stack_member。
在上述情况下，向量对象和复数对象可以插入同一个栈里，因为所有的栈只关心其操作对象的next_member属性，而stack_member的所有子集都包含这一属性。这样将对象自由插入栈里会导致不安全性。例如，把两个向量对象(v1和v2)插入上述复数栈，即用
s.push(vl)；
s.push(v2)；
插入栈里，待将来的某一次pop操作既可能产生向量对象，也可能产生复数对象。如果产生向量对象，而又使用v.angle操作，这显然是一个不存在的操作，将引起错误。因此，在把stack定义成类属类型时必须小心，不得把不同类型的元素压入同一个栈实例中。
概括起来，SIMULA 67融会了许多有趣的性质，它们是：
① 允许使相互关联、高度依赖的程序设计对象组织到一个封装构造(类)中；
② 提供了一种有用的语言构造(子类)，使得具有层次性的系统能通过继承性来分解；
③ 把抽象对象看作仅能通过引用访问的实体，并提供了显式操作引用的机制；
④ 允许说明类实例的伪并行机制(参见3.3.3节)。
2.8.2 CLU语言的抽象数据类型
簇(Cluster)是CLU用来定义抽象数据类型的机制。下面的例子说明了簇的应用和CLU的若干性质。我们定义一个复数的抽象数据类型，它具有下述操作。
(1)建立creat
接收一对实数作为参数，分别把参数看作实部和虚部，建立一个复数(CLU的数据对象必须显式建立)。
(2)加add
接收一对复数作为参数，返回它们的“和”作为结果。
(3)相等equal
接收一对复数作为参数，若它们相等，返回true，否则返回false。
实现该数据对象的抽象数据类型描述如下：
complex = cluster is create，add，equal
rep = record[x，y：real]
create = proc(a，b：real)returns(cvt)
return(rep$ {x：a，y ：b })
end create
add = proc(a，b：cvt)returns(cvt)
return(rep ${x：a.x+b.x，y ：a.y+b.y })
end add
equal = proc(a，b：cvt)returns(bool)
return(a.x=b.x and a.y=b.y)
end equal
end complex
簇头(cluster is ...)列出了抽象数据类型complex可用的操作，这里是create，add和e-qual。rep子句说明抽象数据类型的数据对象所具有的具体表示的数据结构，以便在类型封装机制内使用。这里的具体表示为一记录结构，它包含两个实数域，一个代表实部，一个代表虚部。rep子句之后，是实施若干操作的过程，以及一些类内部的局部过程，本例无局部过程，只有create，add和equal三个过程。
关键字cvt用于对象的抽象表示和具体表示之间的相互转换，仅能在簇内使用。例如，对于过程add，从簇外看，它的两个参数a和b是类型complex的抽象表示，但在簇内add过程内部，需要它的内部表示(这里是record ...)，因此需要将抽象表示转换成具体表示。这样，在add内部，a.x是合法的。类似地，过程结束时所要返回的值的具体表示也要转换成抽象表示。
return(rep $...)
的含义为返回一个具体表示类型(此例为记录record)的对象，而returns cvt使该对象在返回调用者时转换成抽象表示。
CLU语言变量的作用域和生存期互不相干，这是它与其他语言不同的地方。例如
P ：complex
说明P的类型是complex，但这里的P未建立，它必须在其后的某个地方显式建立。例如
P：=complex $ create(h，k)
这里的P才实际存在。其中，符号$类似圆点表示法中的圆点，h和k为实参。该语句调用簇complex的create操作，create过程的return语句产生一个对象并赋予P。
CLU变量被一致看成对数据对象的引用，赋值语句
x：=e
使得x指向e计算所产生的结果数据对象，在此赋值之前x可能引用了一个对象，赋值仅使x引用另一个对象，并未修改原来的对象，原来的对象还可以为其他变量所引用(若已无其他变量引用该对象，它就变成不可访问的对象)。这种形式的赋值称为共享赋值(Assignment by Sharing)或引用赋值(Assignment by Reference)。
CLU的参数传递由赋值定义。例如调用
complex $add (x，y)
把x和y分别赋予形式参数a和b，结果使同一数据对象分别由x和a，y和b共享。
CLU的过程和簇可以是类属的，此外我们不再进行详细讨论。
2.8.3 Ada语言的抽象数据类型
Ada语言程序由一组程序单元组成，程序单元包括子程序和程序包(Package)。程序包是封装机制。Ada语言具有典型的类ALGOL嵌套结构，子程序或程序包的说明内可包含变量、子程序和程序包的局部说明。程序包用途很广，适用范围可从一般实体(如变量、常量、类型)说明到相关子程序集簇(如求解微分方程的程序包)或描述抽象数据类型。一般的实体说明如下述例子：
package COMPLEX-NUMBERS is
type COMPLEX is record
RE：INTEGER；
IM：INTEGER；
end record；
TABLE：array(1..500)of COMPLEX；
end COMPLEX-NUMBERS；
它说明了一个类型COMPLEX和一个变量TABLE，它们在定义的程序包COMPLEX_NUM-BERS(即COMPLEX_NUMBERS的作用域)内有效。程序包内说明的名字可以在程序包的作用域内用圆点表示法引用，例如
COMPLEX_NUMBERS.TABLE(K)
在用程序包集簇相关子程序或描述抽象数据类型时，通常需要隐蔽一些局部实体。对于相关子程序集，需隐蔽的局部实体可能是局部变量或局部过程。对于抽象数据类型，则可能是具体表示和某些内部的辅助变量和过程。Ada程序包通常包括两个部分：程序包规格说明和程序包体。程序包规格说明定义了程序包向外部世界提供的可以访问的实体，称为移出(Ex-port)，它是程序包的可见部分(Visible Part)。程序包体包含全部隐蔽了的实现细节和一个初始化部分，是程序包的不可见部分(Invisible Part)。
下面给出一个程序包，它有两个移出函数：
① BELONGS_TO(X)判定X是否属于某个(有序)整数集，返回一个布尔值。
② POSITION(X)给出X在集中的顺序位置。
有序整数集的表示结构和内容被隐蔽在程序体之内，BELONGS_TO和POSITION是该集合上仅有的两个操作。定义如下：
package INT_SET_PACK is
function BELONGS_TO(X：INTEGER)return BOOLEAN；
function POSITION (X：INTEGER)return INTEGER；
end INT_SET_PACK；
package body INT_SET_PACK is
STORED_INT ：array(1 ..10)of INTEGER；
function BELONGS_TO(X ：INTEGER)return BOOLEAN；
……
end BELONGS_TO；
function POSITION(X ：INTEGER)return INTEGER；
……
end POSITION；
… 数组STORED_INT初始化，即集合的初始化
end INT_SET_PACK；
在前面曾用CLU定义过复数的抽象数据类型，现在用程序包定义这个抽象数据类型：
package COMPLEX-NUMBERS is
type COMPLEX is private；
procedure INITIALIZE(A，B：in REAL；X：out COMPLEX)；
function ADD(A，B：in COMPLEX)return COMPLEX；
private
type COMPLEX is
record R，I：REAL；
end record；
end COMPLEX-NUMBERS；
package body COMPLEX-NUMBERS is
procedure INITIALIZE(A，B：in REAL；X：out COMPLEX)is
begin X.R：=1；
X.I：=2；
end INITIALIZE；
function ADD(A，B：in COMPLEX)return COMPLEX is
TEMP：COMPLEX；
begin TEMP.R：=A.R+B.R；
TEMP.I：=A.I+B.I；
return TEMP；
end ADD；
end COMPLEX-NUMBERS；
在定义中，模块移出的COMPLEX类型是私有类型(Private Type)，即规格说明中的pri-vate...end COMPLEX_NUMBERS部分。私有类型的结构和值的集合定义得很清楚，但却不能被该类型的使用者直接使用，它所表示的细节在程序包之外是不可见的，只有通过为它定义的一组操作才能知道私有类型。COMPLEX类型的变量只能由该程序包移出的INITIAL-IZE子程序和ADD函数操纵。另外，预定义的赋值、相等和不等操作也可以使用。
移出类型还可定义成受限私有类型(Limited Private Type)limited private，此时，赋值、相等和不等操作，在此类型上并未自动定义，程序若需要，必须显式定义(作为附加过程)。
上例中，过程的参数说明成in和out。in说明代表一个不可修改的输入参数，out说明代表一个输出参数，其值由过程设置。程序包(和过程)还可以是类属的，它们在使用之前必须实例化。下面给出一个描述类属的例子。
generic
type COMPONENT is private；
package SET-MANIPULATION is
type SET is limited private；
procedure INSERT(S：in out SET；ELEM：in COMPONENT)；
procedure DELETE(S：in out SET；ELEM：in COMPONENT)；
procedure IS-IN(S：in SET；ELEM：in COMPONENT)return BOOLEAN；
private
type SET is
record STORE：array(1..MAX-CARDINALITY)of COMPONENT；
CARDINALITY：INTEGER range 0..MAX-CARDINALITY：=0；
end record；
end SET-MANIPULATION；
其中，过程INSERT和DELETE分别用于向集合加入和删除一个元素；函数IS_IN用于测试集合成员；表示集合数据结构的是一个数组，其成员类型是一个参数，由程序包前缀的generic子句说明。全局变量MAX_CARDINALITY限制了集合的最大基数。COMPONENT是私有类型，即程序包内对该类型变量的唯一合法操作是赋值、相等和不等。若需要其他操作，可以作为其他类属参数提供。类型SET的CARDINALITY域用于记录集合存放的元素个数，其初始化为零。
类属模块的实例化需经一个实在类属参数说明，例如
package INTEGERS is new SET_MANIPULATION(INTEGER )；
package FLAVORS is new SET_MANIPULATION(FLAVOR)；
此处的FLAVORS是在2.5.2节中Ada子类型中定义的一个类型。从语义上讲，这两个实例可看成两个独立的程序包说明，只是碰巧它们具有相同的内部结构，同属于一个类属。在这两个实例的作用域内，可以写出下列说明：
A，B：INTEGERS.SET A和B具有实例化成INTEGER的SET类型
C：FLAVORS.SET C具有实例化成FIAVOR的SET类型
2.8.4 Modu I a 2 语言的抽象数据类型
Modula 2语言是由Pascal语言发展而来的，增加了模块(Module)概念。模块构造提供Ada程序包所能提供的几乎所有功能。
Modula 2程序由一组模块组成，每个模块具有类似于Pascal的嵌套结构，即子程序或模块说明可以包含子程序和模块的局部说明。
Modula 2用移入(Import)和移出(Export)子句说明模块的移入和移出实体。例如
……
var a，b：integer；
module x；
import a；
export g，h；
var g：integer；
h：boolean；
procedure f(…)；
……
end f；
end x；
模块x从外界移入一个变量a，移出变量g和h。移入实体必须是在模块定义处基于作用域规则的可见实体；移出实体必须是模块内的局部定义实体，移出实体在模块外(模块的作用域内)是可见的。
模块构造可用于封装一组相关子程序或访问一个加防护的隐蔽数据结构。前述用Ada写出的模块INT_SET_PACK可用Modula 2改写成：
module Intsetpack；
export BelongsTo，Position；
var Stored_Int ：array[l..10]of integer；
procedure BelongsTo(x：integer)：boolean；
……
end BelongsTo；
procedure Position(x：integer)：integer；
……
end Position；
……
Modula 2的过程可以返回值；模块可以有一个模块体，当进入模块作用域时，模块开始执行；此处省略的模块体可用于初值化Stored_Int。
Modula 2模块可以移出任何种类的实体，包括类型。当一个类型被移出时，类型的结构细节也同时移出。Modula_2提供了一个解决封装数据类型信息隐蔽的办法，不过该办法只对出现在语言嵌套结构最外层的模块(由它实现抽象数据类型)有效。对Modula_2语言而言，需移出实体的最外层模块分成两部分：定义模块(DM)和实现模块(IM)。定义模块主要用于列出模块的所有移出实体，这些实体可为移入这些实体的模块所用。为了隐蔽移出类型的细节，Modula_2提供一种所谓不透明(Opaque)移出。不透明移出意味着只是类型的名字被列入定义模块，而所有的细节均在对应的实现模块中给出。为了得到高效的实现，规定不透明移出限定为指针，因而抽象数据类型对象须要定义成可访问对象。
下面定义一个复数抽象数据类型：
definition modul ComplexNumbers；
export qualified Complex，Initialize，Add；
{属性qualified指用户可用圆点表示法(模块名，移出实体)访问移出名字}
type Complex；
{这是一个不透明移出，这里不给出类型的细节，在对应的实现模块中给出细节}
procedure Initialize (A，B：real；var x：Complex)；
procedure Add(A，B：Complex)：Complex
end ComplexNumbers.
implementation module ComplexNumbers；
type C=record
R，I：real
end；
type Complex=pointer to C；
procedure Initialize(A，B：real；var x：Complex)；
begin
new(x)；
x↑.R：=A；
x↑.I：=B
end Initialize；
procedure Add(A，B：Complex)：Complex；
var T：Complex；
begin
new(T)；
T↑.R：=A↑.R+B↑.R；
T↑.I：=A↑.I+B↑.I；
return(T)
end Add
end ComplexNumbers.
2.8.5 C++语言的抽象数据类型
C++语言是当前应用广泛的面向对象程序设计语言，它定义的类(class)抽象数据类型与SIMULA 67类似，将类的实例称为对象(Obj ect)。但它与SIMULA 67有很大的不同，它满足抽象数据类型的条件(1)和(2)，支持封装(信息隐蔽)、继承和多态性。
C++语言类定义的一般形式为
class<类名>
{
private：
私有段数据声明；
私有段函数定义；
protected：
保护段数据声明；
保护段函数定义；
public：
公有段数据声明；
公有段函数定义；
}；
其中，类名为一般标识符，代表该类的类型名；花括号内的部分称为类内(类体)；花括号以外部分称为类外。一个类的类体封装了一些数据和对这些数据所进行的操作，分别称为数据成员(Data Member)和函数成员(Function Member)。成员又可分为私有(Private)段成员、保护(Protected)段成员和公有(Public)段成员。
一个类的定义实现了数据封装和信息隐蔽，被封装和隐蔽的部分包括私有段和保护段所有成员(函数与数据)、公有段函数的实现，这些在类外是不可见的(保护段成员在派生类中可见)。数据封装是一个相对概念，只是对类外而言，类外是不可见的，而对于类内，所有成员都是可见的。类的实例是对象，对象继承了类中的数据和方法(操作)，只是各实例(对象)的数据初始化状态和各个数据成员的值不同。
在C++语言中，类外部的函数或者其他的类只能通过使用类的公有段成员来访问这个类。因此，类的公有段成员(公有段数据和公有段成员)提供了类的外部接口，而私有段成员以及所有段成员函数的实现细节(函数体部分)则由类封装起来，而让类的使用者看不到。类的私有数据只能严格通过成员函数访问，任何类外(除了友元)对私有数据的访问都是非法的。使用私有数据这一语言特性来隐藏由类对象操纵的数据，然后提供一些成员函数来访问这些数据，但隐藏了改变这些数据的能力和实现细节。这样，使得类对数据的描述和类提供给外部世界来处理数据的接口这两件事互相独立，这就给出了面向对象的重要性。
C++语言的继承是通过派生类来实现的。下面的例子定义了一个数组类，队列和堆栈是派生类。
#include<iostream.h>
class Array
{
protected：
int* p；
int size；
public：
Array (int num)
{
size=(num>6)？ num：6；
p=new int[size]；
}
～Array()
{
delete[]p；
}
int& operator[](int idx) //超载[]
{
if(idx<size)
return p[idx]；
else
{
expend(x-size+1)；
return p[idx]；
}
}
void expend (int offset)
{
int* pi；
pi=new int[size+offset]；
for(int num=0；num<size；num++)
pi [num]=p[num]；
delete[]p；
p=pi；
size=size+offset；
}
void contract (int offset)
{
size=size-offset；
}
}；
class Queue：public Array
{
int first，last；
public：
Queue (int a)：Array(a)
{first=last=0；}
void j oin_queue (int x)
{
if last==size
expend(1)；
p[last++]=x；
}
int get()
{
if first<last
return p(first++)；
else
{
cout≪"空队"；
return-1；
}
}
}；
class stack：public Array
{
int top；
public：
stack (int a)：Array(a)
{top=0；}
void push (int x)
{
if top==size
expend(1)；
p[top++]=x；
}
int pop()
{
if top>0
return p(--top)；
else
{
cout≪"空堆栈"；
return-1；
}
}
}；
2.8.6 Java抽象数据类型
Java的抽象数据类型称为类(Class)，这是Java的基础。
类的实例称为对象。
类说明格式为
class<类名>
{<类体>}
类的说明还可以有更多的属性，如类的超类(Super class)，或称父类，其格式为
class(类名)extends<父类名>
{<类体>}
这样说明的类是父类的子类，它可以继承父类的变量和函数。
列出类实现的接口(Interface)的类说明格式为
class<类名>extends <父类名>implements call
{<类体>}
接口是一种比类更加抽象的概念，它只定义了一些公用的行为和操作，而无任何实现过程。这些类的行为或操作被称为抽象方法(Abstract Method)。
对于任何类，都可以实现其需要的接口。同时，一个类虽然只能有一个父类(单一继承)，但它却可以实现多个接口，从而以这种方法来实现多重继承。
带有public(公共)的类说明表明，它可以被当前包(Package)之外的其他对象调用。默认的情况下，类能被其定义在同一包中的其他类调用。以下说明
public class<类名>extends<父类名>implements call
{<类体>}
定义的类能被其他类或对象调用。
Java可以定义抽象类(Abstract Class)，抽象类是未完全定义的函数类，它本身不具备实际的功能，只能用于衍生子类，可包含抽象函数(没有实现的函数)的定义，不能实例化。其格式如下：
abstract class<类名>extends <父类名>
{<类体>}
Java还可以定义最终(Final)类。这种类不能通过扩充来建立新的类，即不能构造其子类。其格式如下：
final class <类名>extends<父类名>
{<类体>}
一个抽象类不能说明成最终类，因为抽象类有未实现的函数，必须通过定义它的子类来实现这些函数。
综上所述，类说明可概括为
[<修饰符>]〕class<类名>[extends<父类名>][implements<接口名表>]
{<类体>}
其中，修饰符包括public，abstract和final。接口名表中为以逗号分隔的多个接口名(用于实现类)。
下面是一个Java程序实例。
一个数组元素求和的程序。
(1)import Java.io.*；
(2)class DataConvert {
(3)public int convert(byte ch){return ch-'0'；}}；
(4)class Datastore extends DataConvert {
(5)public void initial(inta)
(6) {ci = 0；
(7) size = a；}；
(8)void save(int a)
(9) {store[ci++]= a；}；
(10)int setprint (){ci = 0；return size；}；
(11)int printval (){return store[ci++]；}；
(12)int sum ()
(13) {int arrsum=0；
(14) for(ci=0；ci < size；ci++)arrsum = arrsum + store[ci]；
(15) return arrsum；}；
(16)private static int maxsize = 9；
(17)int size；//size of array
(18)int ci；//current index into array
(19)int[]store = new int[maxsize]；}；
(20)class sample {
(21)public static void main(string argy[])
(22) {int sz，j；
(23) byte[]Line = new byte[10]；
(24) Datastore x = new Datastore ()；
(25) try
(26) {while((sz=System.in.read(Line))= 0)
(27) {int k = x.convert (Line[O])；
(28) x.initial(k)；}
(29) for(j = 1；j <= k；j+ +)x.save(x.convert(Line[j]))；
(30) for(j = x.Setprint()；j > 0；j- -)
(31) System.out.print(x.printval())；
(32) System.out.print (“；SUM =”)；
(33) System.out.println(x.sum())；}
(34) catch(Exception e){System.out.println("File error .")；}
(35) }//End main
(36) }//End class sample
在这一节，我们介绍了某些语言的抽象数据类型，我们对每一种抽象数据类型均给出了它的实例。因为编程不是本书的目的，所以通过这些程序读者只需了解每种抽象数据类型的结构和形式，以及它们的属性就可以了。
下面3节我们将以较短的篇幅来讨论与编译有关的数据类型问题。