数据抽象.doc

首先明确什么是数据类型。
定义数据类型是数据对象和施加在数据对象上操作的聚合体。
无论程序中用到的是预定义数据类型,或自定义数据类型,都应该考虑数据对象和数据操作两方面的内容。
抽象数据类型(ADT Abstract Data Type)中的数据对象和数据操作的规范声明与数据对象的表示和数据操作的实现相互分离。
一些程序设计语言提供明显的机制支持区分规范声明和实现,例如c++语言中的类。尽管c语言并未明显的提供实现ADT的机制,我们还是可以利用c语言的现有机制构造类似的数据类型。
在ADT的定义清楚无误之后,我们接着讨论数据对象的表示和操作的具体实现,这两方面内容是数据结构的核心。以下用一个例子引出ADT的记法:
抽象数据类型NaturalNumber,下面的ADT定义了自然数的抽象数据类型:
ADT NnturalNumber
//数据对象:由于整数数列,范围0到机器能够表示的最大整数//(INT_MAX)
//成员函数:以下x,y∈NaturalNumber; TRUE,FALSE∈Boolean
NatuarlNumber Zero() ::= 0
Boolean IsZero(x) ::= if(x) return FALSE
else return TRUE
Boolean Equal(x,y) ::= if(x==y) return TRUE
else return FALUE
NaturalNumber essor(x) ::= if(x==INT_MAX) return x
else return x+1
NaturalNumber Add(x,y) ::= if((x+y)<INT_MAX) return x+y
else return INT_MAX
NaturalNumber Subtract(x,y) ::= if(x<y) return 0
else return x-y
end