聚合国内IT技术精华文章,分享IT技术精华,帮助IT从业人士成长

第七话:抽象数据类型ADT

2012-11-20 18:00 浏览: 1272994 次 我要评论(0 条) 字号:


我们对已有的数据类型进行抽象,就有了抽象数据类型。

抽象数据类型(Abstract Date Type, ADT):是指一个数学模型及定义在该模型上的一组操作。抽象数据类型的定义仅取决于它的一组逻辑特性,而与其在计算机内部如何表示和实现无关。

  • 为什么有了数据类型,还要有抽象数据类型呢?
  • 各个计算机,不管是大型机、小型机、PC、平板电脑、PDA, 甚至智能手机都拥有“整数”类型,也需要整数间的运算,那么整型其实就是一个抽象数据类型,尽管它在上面提到的这些在不同计算机中实现方法上可能不一样,但由于其定义的数学特性相同,在计算机编程者看来,它们都是相同的。因此,“抽象”的意义在于数据类型的数学抽象特性。
  • 而且,抽象数据类型不仅仅指那些已经定义并实现的数据类型,还可以是计算机编程者在设计软件程序时自己定义的数据类型,比如我们编写关于计算机绘图或者地图类的软件系统,经常都会用到坐标。也就是说,总是有成对出现的x和y,在3D 系统中还有z出现,既然这三个整型数字是始终在一起出现,我们就定义一个叫point 的抽象数据类型,它有x、y、z三个整型变量,这样我们很方便地操作一个point数据变量就能知道这一点的坐标了。

根据抽象数据类型的定义,它还包括定义在该模型上的一组操作。就像“超级玛丽”这个经典的任天堂游戏,里面的游戏主角是马里奥(Mario)。我们给他定义了几种基本操作,走(前进、后退、上、下)、跳、打子弹等。

一个抽象数据类型定义了:一个数据对象、数据对象中各数据元素之间的关系及对数据元素的操作。至于,一个抽象数据类型到底需要哪些操作,这就只能由设计者根据实际需要来定。像马里奥, 可能开始只有两种操作,走和跳,后来发现应该要增加一种打子弹的操作,再后来发现有些玩家希望它可以走得快一点,就有了按住打子弹键后前进就会“跑”的操作。这都是根据实际情况来设计的。

事实上,抽象数据类型体现了程序设计中问题分解、抽象和信息隐藏的特性。抽象数据类型把实际生活中的问题分解为多个规模小且容易处理的问题,然后建立一个计算机能处理的数据模型,并把每个功能模块的实现细节作为一个独立的单元,从而使具体实现过程隐藏起来。

抽象数据类型(Abstract Data Type, ADT) 是一个数据结构以及定义在该结构上的一组操作的总称。它是对数据类型的抽象,抽象的意义在于数据类型不是高级程序语言支持的基本数据类型,而是自定义的数据类型。

  • 抽象数据类型(ADT)的定义和实现通常是分开的。定义只包含数据逻辑结构的定义和所允许的一组操作;使用者通过这些定义了的操作对ADT进行操作;另一方面,实现者根据这些定义来完成ADT的各种具体实现方式。

为了便于在之后的讲解中对抽象数据类型进行规范的描述,我们给出了描述抽象数据类型的标准格式:


ADT 抽象数据类型名
Data
数据元素之间的逻辑关系的定义
Operation
操作1:
前置条件:执行此操作前数据所必须的状态
输入: 执行此操作所需要的输入
功能: 该操作将完成的功能
输出: 此操作执行完成后产生的输出
后置条件: 执行此操作后数据的状态
操作2:
.
.
.
操作n:
.
.
.
endADT

对抽象数据类型的定义,不涉及实现细节,形式上可繁可简。



网友评论已有0条评论, 我也要评论

发表评论

*

* (保密)

Ctrl+Enter 快捷回复