抽象数据类型.ppt

抽象数据类型
梁金华
Email: ******@.
办公室: 理四-338 教学办
抽象数据类型(Abstract Data Type 简称ADT)
抽象数据类型是与表示无关的数据类型,是一个数据模型及定义在该模型上的一组运算。对一个抽象数据类型进行定义时,必须给出它的名字及各运算的运算符名,即函数名,并且规定这些函数的参数性质。一旦定义了一个抽象数据类型及具体实现,程序设计中就可以像使用基本数据类型那样,十分方便地使用抽象数据类型。
抽象数据类型的描述包括给出抽象数据类型的名称、数据的集合、数据之间的关系和操作的集合等方面的描述。抽象数据类型的设计者根据这些描述给出操作的具体实现,抽象数据类型的使用者依据这些描述使用抽象数据类型。
是指一个数学模型以及定义在此数学模型上的一组操作
抽象数据类型和数据类型实质上是一个概念。
例如:各个计算机都拥有的“整数”类型是一个抽象数据类型,尽管它们在不同处理器上实现的方法可以不同,但由于其定义的数学特性相同,在用户看来都是同样的。因此,“抽象”的意义在于数据类型的数学抽象特性。
例如:线性表这样的抽象数据类型,其数学模型是:数据元素的集合,该集合内的元素有这样的关系:除第一个和最后一个外,每个元素有唯一的前趋和唯一的后继。可以有这样一些操作:插入一个元素、删除一个元素等。
作用:抽象数据类型可以使我们更容易描述现实世界。
例如:用线性表描述学生成绩表,用树或图描述遗传关系。
定义:一个数学模型以及定义在该模型上的一组操作。
关键:使用它的人可以只关心它的逻辑特征,不需要了解它的存储方式。定义它的人同样不必要关心它如何存储。
三元组:(D,S,P)
ADT抽象数据类型名{
数据对象:<数据对象的定义>
数据关系:<数据关系的定义>
基本操作:<基本操作的定义>
} ADT抽象数据类型名
抽象数据类型三元值的定义
ADT Triplet{
数据对象:D={e1,e2,e3|e1,e2,e3∈ElemSet(定义了关系运算的某个集合}
数据关系:R!={<e1,e2>,<e2,e3>}
基本操作:
InitTriplet(&T,v1,v2,v3)
操作结果:构造了三元值T,元素e1,e2和e3分别被赋以v1,v2和v3的值。
DestroyTriplet(&T)
操作结果:三元值T被销毁
Get(T,i,&e)
初始条件:三元值T已存在,1<=i<=3。
操作结果: 用e返回T的第i元的值。
Put(&T,i,e)
初始条件:三元值T已存在,1<=i<=3。
操作结果: 改变T的第i元的值为e。
IsAscending(T)
初始条件:三元值T已存在。
操作结果: 如果T的三个元素按升序排列,则返回1,否则返回0。
IsDescending(T)
初始条件:三元值T已存在。
操作结果: 如果T的三个元素按降序排列,则返回1,否则返回0。
Max(T, &e)
初始条件:三元值T已存在。
操作结果: 用e返回T的三个元素中的最大值。
Min(T, &e)
初始条件:三元值T已存在。
操作结果: 用e返回T的三个元素中的最小值。
} ADT Triplet
抽象数据类型的表示和实现
设 ElemType 是某种数据