抽象数据类型的概念与表示,什么叫做抽象数据类型
什么是抽象数据类型?简介:数据类型和数据结构:2。抽象数据类型的概念:3。抽象数据类型的描述。
前言
抽象数据类型
(抽象数据类型,ADT)是计算机领域普遍接受的思想和方法,也是设计和实现程序模块的有效技术。ADT的基本思想是抽象,或者说数据抽象(对应于通过函数定义实现的计算抽象或者进程抽象)。 1.数据类型与数据结构
数据类型
是编程领域最重要的基本概念之一。程序中描述的,通过了 计算机处理的数据通常属于不同的类型,如整数或浮点数。每种类型都包含一组合法的数据对象,并指定这些对象的合法操作。各种编程语言都提供了一组数据类型和每个内置类型的一批操作。
以Python为例,它提供的基本类型包括逻辑类型bool、数值类型int和float、string类型等等。在开发程序时,选择合适的数据类型应该更有必要。
但是,无论编程语言提供了多少内置类型,在
处理较为复杂的问题时
,程序员迟早会遇到一些情况。此时,所有内置类型都无法满足或不适合自己的需求。在这种情况下,编程语言提供的组合类型可能有助于解决一些问题。比如Python提供了list、tuple、set、dict等结构。对于数据的组合。在编程时,可以用它们将一组相关的数据组织在一起,形成一个数据对象,作为一个整体进行存储、传输和处理。 2.抽象数据类型
抽象数据类型的基本思想
的概念是将数据定义为对象的抽象集合,只为其定义可用的合法操作,而不揭示其内部实现的具体细节,无论是数据的表示细节还是操作的实现细节。当然,要使用一个对象,首先需要能够构造它,然后才能操作它。抽象数据类型提供的操作应该满足这些要求。数据类型的操作通常可以分为三类: 构造:这些操作基于一些已知的信息生成一个这种类型的新对象。例如,基于一对整数生成一个有理数对象。解析操作:该操作从对象中获取有用的信息,其结果反映了被操作对象的某些特征。单一结果不是这种类型的对象。比如:pit你需要有两个运算来从一个有理数中得到它的分子或者分母,运算的结果应该是一个整数(一个整数类型的对象)。Change:这种操作修改被操作对象的内部状态。例如,对于银行账户对象,其类型应该提供诸如检查余额和修改余额的操作。经过一次变更操作,对象仍然是原来的账户,仍然代表原来银行客户的相关信息,但是对象内部记录的存款余额发生了变化,反映的是实际客户账户余额的变化。当然,抽象数据类型也应该有一个名称来表示这种类型。
作为一种数据类型,尤其是复杂数据类型,有一个非常重要的属性值叫做
变动性
,表示该类型的对象在创建后是否允许更改。如果一个类型只提供了上面的第一个和第二个操作,那么该类型的对象在创建之后就不会改变,会一直处于固定的状态。这种类型叫做不变数据类型
,这种类型的对象就变成了不变对象
。对于这种类型,在程序中,只能构造新的对象(基于其他信息或已有对象)或获取已有对象的特征,不能修改已建立的对象。如果提供了类型3操作,在对该类型的对象执行该操作后,虽然对象保持不变,但其内部状态发生了变化。这种数据类型称为可变数据类型,其对象称为
可变对象。
比如Python只为str、tuple和forzenset提供了前两类操作,所以是不可变的数据类型。列表、集合、字典等。是可变数据类型。在编程中设计或定义抽象数据类型时,还需要根据情况决定是将其定义为不可变数据类型还是可变数据类型。
3.抽象数据类型的描述定义了一个抽象数据类型,目的是定义一类计算对象,这些对象具有某些特定的功能,可以在计算中使用。这些对象的功能体现在一组可以对它们使用的操作中。当然,也有必要为这个抽象数据类型确定一个类型名。
下面介绍一种抽象数据类型的描述方法,其形式反映了抽象数据类型的主要特征。写这个描述的过程本身也是很有意义的,因为它可以帮助开发人员理解他们想要定义的数据类型的想法,并清晰地表达形式上的需求(如操作的名称、参数的数量和类型等。)和功能需求(他们希望这个操作达到什么样的计算或者效果等。).
现在考虑一个简单的有理数抽象数据类型,描述如下:
在这里,特殊名称ADT表示这是对抽象数据类型的描述,后跟已定义类型的名称。ADT定义的主要部分描述了一组操作,每个操作的描述由两部分组成:首先由标识符给出操作名称和参数,然后以类似Python的注释形式给出操作的功能描述。另外,在描述一个操作的参数时,可以考虑在参数名前写一个类型名来表示这个参数应该具有的类型;也可以省略,通过文字描述。
具体到上面的抽象数据类型,它的名字叫Rational,提供了七种操作。第一个操作的名字是Rational,意思是它是最基本的构造操作。这种类型的操作是由其他类型的参数构造的。下面的算术运算也是构造运算,它基于Rational类型的对象生成新的Rational类型的对象。后两种是获取有理数对象的属性(成分)的解析运算。
利用绘制数据类型的思想和技术,不仅可以描述有理数等数学类型,还可以描述实际应用中的各种类型。例如,下面描述了表示日期的抽象数据类型:
通过以上两个抽象数据类型的例子,现在总结其中的一些:
ADT描述由一个标题和一组以某种格式给出的操作描述组成。ADT的头给出了类型名,第一个是表示抽象数据类型的关键字ADT。操作的正式描述给出了操作的名称、参数的类型和参数名称。在ADT描述中,参数名主要用于解释该操作的功能(如上面的Python注释形式)。用自然语言描述各种操作的实际功能,这是一种非正式的解释,主要是帮助理解这些操作需要(能)做什么,从而正确地实现和使用。在抽象数据类型的描述中,其他方面都是清晰严格的,而自然语言给出的函数描述却不是。语言天生就不精确,不明确,所以很难用它写出准确的描述。这种描述的意义需要人去理解,误解是造成错误的最重要根源之一
。
ADT是一种组织程序的思想和技术,主要包括:
围绕这类数据定义的程序模块,如上面的Rational和Date,就是这类模块的接口和实现分离。上面只给出了模块的接口规范,包括模块名称,模块提供的各种操作的名称和参数。每个操作也有一个非正式的语义描述。当需要实现时,从使用的编程语言中选择一套合适的机制,采用合理的技术来实现该ADT的功能,包括具体的数据表示和操作。