前言

抽象数据类型(Abstract Data Type,ADT)是计算机领域中被广泛接受的一种思想和方法,也是一种用于设计和实现程序模块的有效技术。ADT的基本思想是抽象,或者说是数据抽象(与函数定义实现的计算抽象或过程抽象对应)。

1.数据类型和数据构造

数据类型是程序设计领域最重要的基本概念之一。在程序里描述的、通过
计算机去处理的数据,通常都分属不同的类型,例如整数或浮点数等。每个类型包含一集合法的数据对象,并规定了这些对象的合法操作。各种编程语言都提供了一组数据类型,为每个内置类型提供了一批操作。

以Python为例,它提供了基本类型包括逻辑类型bool、数值类型int和float等、字符串类型等等。开发程序时候,应该更具需要选择合适的数据类型。

但是无论编程语言提供了多少内置类型,在处理较为复杂的问题时,程序员或早或晚都会遇到一些情况,此时各种内置类型都不能满足或者不适合于自己的需要。在这种情况下,编程语言提供的组合类型有可能帮助解决一些问题。例如,Python为数据的组合提供了list、tuple、set、dict等结构,编程时可以利用他们把一组相关数据组织在一起,构成一个数据对象,作为整体存储、传递和处理。

2.抽象数据类型的概念

抽象数据类型的基本思想是把数据定义为抽象的对象集合,只为它们定义可用的合法操作,并不暴露其内部实现的具体细节,不论是数据的表示细节还是操作的实现细节。当然,要使用一种对象,首先需要能构造这种对象,而后能操作它们。抽象数据类型提供的操作应该满足这些要求。一个数据类型的操作通常可以分为三类:

  1. 构造操作:这些操作基于一些已知信息,产生出这种类型的一个新对象。例如,基于一对整数产生出一个有理数对象。
  2. 解析操作:这种操作从一个对象取得有用的信息,其结果反应了被操作对象的某方面特性,单结果并不是本类型的对象。例如:坑你需要有两个操作,分别从一个有理数获取其分子或者分母,操作的结果应该是整数(整数类型的对象)。
  3. 变动操作:这类操作修改被操作对象的内部状态。例如对一个银行账户对象,其类型就应该提供查看余额和修改余额的操作等。经过一次变动操作,对象还是原来的账户,仍然表示原来的银行客户的有关信息,但是对象内部记录的存款余额改变了,反映了实际客户账户的余额变动。

当然,一个抽象数据类型还应该有一个名字,用于代表这个类型。

作为数据类型,特别是比较复杂的数据类型,有一个很重要的性值称为变动性,表示该类型的对象在创建之后是否允许变化。如果某个类型只提供上面的第1和第2类操作,那么该类型的对象在创建之后就不会变化,永远处于一个固定的状态。这样的类型称为不变数据类型,这种类型的对象成为不变对象。对于这种类型,在程序里只能(基于其他信息或者已有对象)构造新对象或者取得已有对象的特性,不能修改已建立的对象。如果提供了第3类操作,对该类型的对象执行这种操作后,虽然对象依旧,但其内部状态已经改变。这样的数据类型称为可变数据类型,其对象称为可变对象

例如,Python中对str、tuple、forzenset类型只提供了前两类操作,因此其是一个不可变数据类型。对list,set,dict等就是可变数据类型。在编程中设计或定义抽象数据类型时,也要根据情况,决定是将其定义为不变数据类型或者是可变数据类型。

3.抽象数据类型的描述

定义一个抽象数据类型,目的是要定义一类计算对象,它们具有某些特定的功能,可以在计算中使用。这类对象的功能体现为一组可以对它们使用的操作。当然,还需要为这一抽象数据类型确定一个类型名。

下面为抽象数据类型引进一种描述方式,其形式体现了抽象数据类型的主要特点。写出这种描述的过程本身也很有意义,因为他能帮助开发者理清楚对希望定义的数据类型的想法,清晰的表述出各方面的形式要求(如操作的名字、参数的个数和类型等)和功能要求(希望这个操作完成什么样计算,或产生什么效果等)。

现在考虑一个简单的有理数抽象数据类型,有如下描述:
在这里插入图片描述
这里用特殊名字ADT表示这是一个抽象数据类型的描述,随它之后给出被定义类型的名字。ADT定义的主要部分描述一组操作,每个操作的描述由两部分组成:首先是用标识符给出操作名和操作的参数,随后用类似Python注释的形式给出操作的功能描述。另外注意,在描述操作的参数时,可以考虑在参数名前写一个类型名,表示这个参数应该具有的类型;也可以省略,通过文字描述说明。

具体到上面的抽象数据类型,其名字时Rational,其中提供了7个操作。第一个操作以Rational作为名字,这种形式表示它是一个最基本的构造操作,从其他类型的参数出发构造本类型的操作。随后的几个算数运算也是构造操作,它们基于Rational类型的对象生成Rational类型的新对象。最后两个是解析操作,取得有理数对象的性质(成分)。

使用抽线数据类型的思想和技术,不但可以描述有理数一类数学类型,也可以描述实际应用中的各种类型。例如,下面描述了一个表示日期的抽象数据类型:
在这里插入图片描述
通过上面的两个抽象数据类型的例子,现在总结其中的一些情况:

  • 一个ADT描述由一个头部和按一定格式给出的一组操作描述成。
  • ADT的头部给出类型名,最前面是表示抽象数据类型的关键词ADT。
  • 操作的形式描述给出操作的名字、参数的类型和参数名。在ADT描述中,参数名主要用在解释这个操作的功能的地方(如上面的Python注释形式)。
  • 各种操作的实际功能用自然语言描述,这是一种非形式的说明,主要是为了帮助理解这些操作需要(能够)做什么,以便正确地实现和使用它们。

在抽象数据类型的描述中,其他方面都比较清晰和严格,用自然语言形式给出的功能描述则不然。自然语言有着天然的非精确性和歧义性,用它写的描述很难精确无误。这种描述的意义需要人去理解,误解是造成错误的最重要根源之一

ADT是一种思想,也是一种组织程序的技术,主要包括:

  1. 围绕这一类数据定义程序模块,如上面的Rational和Date都是这样的
  2. 模块的接口和实现分离。上面只给出了模块的接口规范,包括模块名、模块提供的各种操作的名字和参数。每个操作还有非形式化的语义说明。
  3. 在需要实现时,从所用的编程语言里选择一套合适的机制,采用合理的技术,实现这种ADT的功能,包括具体的数据表示和操作。
Logo

为开发者提供学习成长、分享交流、生态实践、资源工具等服务,帮助开发者快速成长。

更多推荐