第九节 抽象数据类型
1,用户定义类型与内部类型的异同
① 都建立某种基本表示的抽象
如,integer是位串的抽象 ;
reg_polygon是记录的抽象
② 每一类型都关联一组操作
③ 内部类型隐蔽了基本表示, 不能对
它的成分进行操作 ;用户定义类型具
有更高级别的抽象, 可以对其基本
表示的成分进行操作 。
2,抽象数据类型的定义
满足下述特性的用户定义类型称为 抽
象数据类型,
① 在实现该类型的程序单元中,建立与
表示有关的基本操作 ;
② 对使用该类型的程序单元来说,该类
型的表示是隐蔽的 。
一, SIMULA 67的类机制
1.类的说明
<类头 >;<类体 >
<类头 >包括类名和形式参数
<类体 >是传统的分程序,可包含变量, 过程
和类的局部说明, 以及一些执行语句
例：复数表示 (幅角,半径 )
class complex（ x,y）； real x,y；
begin real angle,radius；
radius,=sqrt（ x**2+y**2）；
if abs（ x） <epsilon
then begin if abs(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
2,类的有关性质
① 类说明定义了一类数据对象的原型
或样板
② 类的每个实例是一个可操作的数据
对象
③ 类的实例可多次动态建立,且仅能通
过指针引用
例, ref(complex) c;
c:- new complex(1.0,1.0);
c
0.78
1.42
1.0
1.0
angle
radius
x
y
④ 类实例的属性是指类体的 局部变量
和类头中的 参数
my_angle:=c.angle;
my_radius:=c.radius;
my_x:=c.x;
my_y:=c.y;
⑤ 类支持抽象数据类型的封装机制,它
可以封装实现对数据操作的各种过程
例, 可将复数加和乘的过程 add和 multiply封
装入类 complex的类体说明中,作为
complex的属性。
procedure add(operand);ref (complex) operand
procedure multiply(operand);ref (complex) operand
变量 c1,c2引用的两个复数相加可表示为：
c1.add(c2)
或
c3.angle:=c1.angle;
c3.radius:=c1.radius+c2.radius;
用户可以直接访问复数的内部表示,故 add
和 multiply不是复数对象的唯一操作
3,子类
用以定义类型的判定或和类属 。
要求：定义一个栈, 完成
?引用栈顶元素
?入栈
?出栈
?判栈是否空
(这些操作与栈中元素的类型无关 )
栈内成员的元素类
class stack_member;
begin ref (stack_member) next_member;
next_member:-none
end
指针型局部变量
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
stack_member class complex(……);
……
end complex
定义了一个复数栈
其中 complex称为 stack_member的子类
加在类说明之前
① 子类 complex具有自己的属性,同时
继承了 stack_member的属性
new complex
产生的对象具有 stack_member和 complex的
所有属性
ref(stack) s;
s:-new stack;
s.push(c1);
s.push(c2);
s.push(c3);
建立一个复数栈
② 具有 ref(stack_member)的变量可引用
多种类型的量,但不同类型的元素不得压
入同一栈实例中
下述语句说明向量也可是栈中元素,
stack_member class vector(…);
……
end vector
二,CLU的抽象数据类型
例, 定义复数完成, 建立、加、判等
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
1,簇（ Cluster）是 CLU用来定义抽象数据
类型的机制
①簇内,需要内部表示
②簇外,看到的是抽象表示
?rep说明数据对象的具体表示
?cvt用于抽象表示和具体表示之间的相互转
换,仅能在簇内使用
?return(rep $ …) 的含义为返回一个具体表示
类型的对象
2,CLU的性质
① CLU变量的作用域和生存期互不相干
P:complex 仅仅是一个说明
而 P:=complex $ create(h,k)才产生一个对象赋
于 P
② CLU变量被一致看成是对数据对象的引用
如 x:=e
其中 x类似于指针变量
③ CLU的参数传递由赋值定义
complex $ add(x,y)
把 x和 y分别赋予形式参数 a和 b
三, Ada的抽象数据类型
1,Ada用程序包描述抽象数据类型
程序包包括规格说明和程序包体
2.,移出, 的概念
这是程序包向外部世界提供的可以访问的实
体, 是程序包的可见部分
3.私有类型
① 私有类型的表示细节在程序包外是不
可见的
② 允许的操作,移出的子程序, 函数；
赋值, 相等, 不等
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-NUMBER is
procedure INITIALIZE(A,B:in REAL;X:out COMPLEX) is
begin X.R:=A;
X.I:=B;
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-NUMBER;
4,受限私有类型
只允许程序包移出的子程序和函数,不
允许赋值, 相等和不相等
5,类属的描述
使用 generic子句说明类型是一个参数,
实例化时代以具体的类型
例, package INTEGER is new SET-MANIPULATION（ INTEGER） ；
package FLAVORS is new SET-MANIPULATION（ FLAVOR） ；
generic
type COMPONENT is private;
package SET-MANIPULATION is
type SET is limited private;
procedure INSERT(S:out SET;ELEM:in COMPONENT);
procedure DELETE(S: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;
四, Modula-2的抽象数据类型
1,移入 (Inport)和移出 (Export)子句说明模块的
移入和移出实体
2,Modula-2 的模块可以封装一组相关子程序
3,抽象数据类型的描述由 定义模块 和 实现模块
两部分组成
4,Modula-2的模块可以移出类型，类型的细节
可通过“不透明移出”加以屏蔽
definition module ComplexNumber;
export qualified Complex,Initialize,Add;
type Complex; /* 不透明移出 */
Procedure Initialize(A,B:real;var x:Complex);
Procedure Add(A,B:Complex):Complex
end ComplexNumber,
implementation module ComplexNumber;
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 ComplexNumber,
第十节 实现模型
描述符,描述数据对象的所有属性
数据
数据对象 (存储区及其值 )
一, 内部类型和用户定义的非结构类型
1,描述符一般由“类型”和一个指针组成
2,子界的描述符必须包括子界的界值
3,布尔型和字符型可以压缩存储
如, 整型
integer
二, 结构类型
1,笛卡尔积
① 各成分顺序排列
② 描述符包含,类型名, 构造符, 若干
三元式 。 每个域对应一个三元式 (选
择符名,域类型,指针 )
③ 每个成分占整数个可编址的存储单
元 (字编址或字节编址 ）
④ 可以用 packed显式说明压缩存储
数据对象
浮点值
定点值
描述符
类型名
构造符
选择符
选择符
类型
类型
引用
引用
t
record
a
real
b
integer
域 1
域 2
type t=record a,real；
b,integer；
end；
2,有限映象
①为 每一成分分配整数个可编址的存储单
元
②描述符包括,类型名、构造符、定义域的
基类型、下界、上界、成分类型、单元个数、
首地址
③ 地址公式的计算
b+k(i-m)=b-km+ki
其中 b 为首地址, k为所占单元数, m为下界
④ 内情向量
描述符
类型名
构造符
基类型
成分类型
下界
单元个数
上界
引用
a
array
integer
0
real
1
下标类型
10
数据对象
浮点值
浮点值
浮点值
type a=array[1..10] of real;
3,序列
可变长串的表示,
静态描述符 +动态描述符 +堆
string 5
A L
P H
A nil
4,判定或
① 判定或类型的变量分配的空间应足以容
纳需要最大空间的变体的值
② Pascal的变量记录的表示包括,描述符, 数
据对象, case表, 若干变体描述符
type v=record a:integer;
case b:boolean of
true:(c:integer);
false:(d:integer;
e:real)
end;
v
variant record
a
integer
b
boolean
?
?
?
?
?
?
?
?
(false) (true)
d
integer
e
real
c
integer
定点值
布尔值
true
false
case表
描述符 数据对象
变体描述符
5,幂集
① 集合关联一个机器字,通过每一位的
取值可知该集合中有基类型的哪些
元素
② 位操作
6,指针
指针变量的表示类似于内部类型, 只是
其值为一地址, 并且它指向的数据对象
分配在堆上
7,层次结构数据结构对象的表示
描述符中的类型可以指向另外的描述符
type t1=array[0..3] of integer;
t=record a:real;
b:t1;
c:integer
end;
t4=array[0..5] of integer;
t2=array[0..2] of t4;
t
record
a
real
b
c
integer
浮点值
定点值
定点值
定点值
定点值
定点值
t1
array
integer
0
3
integer
1
t2
array
integer
0
2
6
t4
array
integer
0
5
integer
1
定点值
第二章习题
?必做题,
2-2,2-8,
2-16：请谈谈你对数据类型的认识
?思考题,
2-3,2-13,2-14
1,用户定义类型与内部类型的异同
① 都建立某种基本表示的抽象
如,integer是位串的抽象 ;
reg_polygon是记录的抽象
② 每一类型都关联一组操作
③ 内部类型隐蔽了基本表示, 不能对
它的成分进行操作 ;用户定义类型具
有更高级别的抽象, 可以对其基本
表示的成分进行操作 。
2,抽象数据类型的定义
满足下述特性的用户定义类型称为 抽
象数据类型,
① 在实现该类型的程序单元中,建立与
表示有关的基本操作 ;
② 对使用该类型的程序单元来说,该类
型的表示是隐蔽的 。
一, SIMULA 67的类机制
1.类的说明
<类头 >;<类体 >
<类头 >包括类名和形式参数
<类体 >是传统的分程序,可包含变量, 过程
和类的局部说明, 以及一些执行语句
例：复数表示 (幅角,半径 )
class complex（ x,y）； real x,y；
begin real angle,radius；
radius,=sqrt（ x**2+y**2）；
if abs（ x） <epsilon
then begin if abs(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
2,类的有关性质
① 类说明定义了一类数据对象的原型
或样板
② 类的每个实例是一个可操作的数据
对象
③ 类的实例可多次动态建立,且仅能通
过指针引用
例, ref(complex) c;
c:- new complex(1.0,1.0);
c
0.78
1.42
1.0
1.0
angle
radius
x
y
④ 类实例的属性是指类体的 局部变量
和类头中的 参数
my_angle:=c.angle;
my_radius:=c.radius;
my_x:=c.x;
my_y:=c.y;
⑤ 类支持抽象数据类型的封装机制,它
可以封装实现对数据操作的各种过程
例, 可将复数加和乘的过程 add和 multiply封
装入类 complex的类体说明中,作为
complex的属性。
procedure add(operand);ref (complex) operand
procedure multiply(operand);ref (complex) operand
变量 c1,c2引用的两个复数相加可表示为：
c1.add(c2)
或
c3.angle:=c1.angle;
c3.radius:=c1.radius+c2.radius;
用户可以直接访问复数的内部表示,故 add
和 multiply不是复数对象的唯一操作
3,子类
用以定义类型的判定或和类属 。
要求：定义一个栈, 完成
?引用栈顶元素
?入栈
?出栈
?判栈是否空
(这些操作与栈中元素的类型无关 )
栈内成员的元素类
class stack_member;
begin ref (stack_member) next_member;
next_member:-none
end
指针型局部变量
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
stack_member class complex(……);
……
end complex
定义了一个复数栈
其中 complex称为 stack_member的子类
加在类说明之前
① 子类 complex具有自己的属性,同时
继承了 stack_member的属性
new complex
产生的对象具有 stack_member和 complex的
所有属性
ref(stack) s;
s:-new stack;
s.push(c1);
s.push(c2);
s.push(c3);
建立一个复数栈
② 具有 ref(stack_member)的变量可引用
多种类型的量,但不同类型的元素不得压
入同一栈实例中
下述语句说明向量也可是栈中元素,
stack_member class vector(…);
……
end vector
二,CLU的抽象数据类型
例, 定义复数完成, 建立、加、判等
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
1,簇（ Cluster）是 CLU用来定义抽象数据
类型的机制
①簇内,需要内部表示
②簇外,看到的是抽象表示
?rep说明数据对象的具体表示
?cvt用于抽象表示和具体表示之间的相互转
换,仅能在簇内使用
?return(rep $ …) 的含义为返回一个具体表示
类型的对象
2,CLU的性质
① CLU变量的作用域和生存期互不相干
P:complex 仅仅是一个说明
而 P:=complex $ create(h,k)才产生一个对象赋
于 P
② CLU变量被一致看成是对数据对象的引用
如 x:=e
其中 x类似于指针变量
③ CLU的参数传递由赋值定义
complex $ add(x,y)
把 x和 y分别赋予形式参数 a和 b
三, Ada的抽象数据类型
1,Ada用程序包描述抽象数据类型
程序包包括规格说明和程序包体
2.,移出, 的概念
这是程序包向外部世界提供的可以访问的实
体, 是程序包的可见部分
3.私有类型
① 私有类型的表示细节在程序包外是不
可见的
② 允许的操作,移出的子程序, 函数；
赋值, 相等, 不等
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-NUMBER is
procedure INITIALIZE(A,B:in REAL;X:out COMPLEX) is
begin X.R:=A;
X.I:=B;
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-NUMBER;
4,受限私有类型
只允许程序包移出的子程序和函数,不
允许赋值, 相等和不相等
5,类属的描述
使用 generic子句说明类型是一个参数,
实例化时代以具体的类型
例, package INTEGER is new SET-MANIPULATION（ INTEGER） ；
package FLAVORS is new SET-MANIPULATION（ FLAVOR） ；
generic
type COMPONENT is private;
package SET-MANIPULATION is
type SET is limited private;
procedure INSERT(S:out SET;ELEM:in COMPONENT);
procedure DELETE(S: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;
四, Modula-2的抽象数据类型
1,移入 (Inport)和移出 (Export)子句说明模块的
移入和移出实体
2,Modula-2 的模块可以封装一组相关子程序
3,抽象数据类型的描述由 定义模块 和 实现模块
两部分组成
4,Modula-2的模块可以移出类型，类型的细节
可通过“不透明移出”加以屏蔽
definition module ComplexNumber;
export qualified Complex,Initialize,Add;
type Complex; /* 不透明移出 */
Procedure Initialize(A,B:real;var x:Complex);
Procedure Add(A,B:Complex):Complex
end ComplexNumber,
implementation module ComplexNumber;
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 ComplexNumber,
第十节 实现模型
描述符,描述数据对象的所有属性
数据
数据对象 (存储区及其值 )
一, 内部类型和用户定义的非结构类型
1,描述符一般由“类型”和一个指针组成
2,子界的描述符必须包括子界的界值
3,布尔型和字符型可以压缩存储
如, 整型
integer
二, 结构类型
1,笛卡尔积
① 各成分顺序排列
② 描述符包含,类型名, 构造符, 若干
三元式 。 每个域对应一个三元式 (选
择符名,域类型,指针 )
③ 每个成分占整数个可编址的存储单
元 (字编址或字节编址 ）
④ 可以用 packed显式说明压缩存储
数据对象
浮点值
定点值
描述符
类型名
构造符
选择符
选择符
类型
类型
引用
引用
t
record
a
real
b
integer
域 1
域 2
type t=record a,real；
b,integer；
end；
2,有限映象
①为 每一成分分配整数个可编址的存储单
元
②描述符包括,类型名、构造符、定义域的
基类型、下界、上界、成分类型、单元个数、
首地址
③ 地址公式的计算
b+k(i-m)=b-km+ki
其中 b 为首地址, k为所占单元数, m为下界
④ 内情向量
描述符
类型名
构造符
基类型
成分类型
下界
单元个数
上界
引用
a
array
integer
0
real
1
下标类型
10
数据对象
浮点值
浮点值
浮点值
type a=array[1..10] of real;
3,序列
可变长串的表示,
静态描述符 +动态描述符 +堆
string 5
A L
P H
A nil
4,判定或
① 判定或类型的变量分配的空间应足以容
纳需要最大空间的变体的值
② Pascal的变量记录的表示包括,描述符, 数
据对象, case表, 若干变体描述符
type v=record a:integer;
case b:boolean of
true:(c:integer);
false:(d:integer;
e:real)
end;
v
variant record
a
integer
b
boolean
?
?
?
?
?
?
?
?
(false) (true)
d
integer
e
real
c
integer
定点值
布尔值
true
false
case表
描述符 数据对象
变体描述符
5,幂集
① 集合关联一个机器字,通过每一位的
取值可知该集合中有基类型的哪些
元素
② 位操作
6,指针
指针变量的表示类似于内部类型, 只是
其值为一地址, 并且它指向的数据对象
分配在堆上
7,层次结构数据结构对象的表示
描述符中的类型可以指向另外的描述符
type t1=array[0..3] of integer;
t=record a:real;
b:t1;
c:integer
end;
t4=array[0..5] of integer;
t2=array[0..2] of t4;
t
record
a
real
b
c
integer
浮点值
定点值
定点值
定点值
定点值
定点值
t1
array
integer
0
3
integer
1
t2
array
integer
0
2
6
t4
array
integer
0
5
integer
1
定点值
第二章习题
?必做题,
2-2,2-8,
2-16：请谈谈你对数据类型的认识
?思考题,
2-3,2-13,2-14
