ADTs (Abstract Data Types)是什么？

Question

我目前正在学习抽象数据类型（ADTs），但是我完全不理解这个概念。能否有人向我解释一下这到底是什么？另外，集合、袋子和列表 ADTs 又是什么？可以用简单的语言解释吗？

- Tommy2014

---

可能是重复问题：什么是面向对象编程中的抽象数据类型？ - Rishi Dua

答案：http://programmers.stackexchange.com/a/288504/114794 - Premraj

“ADT” 也可以指“代数数据类型”，它由乘积和和组成，是一个更加明确定义的概念（正如链接的重复问题目前有16个答案所证明的那样）。 - jberryman

Answer 1

抽象数据类型（ADT）是一种数据类型，仅定义了行为而没有实现方式。

与ADT相对的是具体数据类型（CDT），它包含了ADT的实现。

举例：
Array, List, Map, Queue, Set, Stack, Table, Tree, 和Vector都是ADT。每个ADT都有许多实现，即CDT。容器是所有ADT中最高级别的。

现实生活中的例子：
书是抽象的（电话簿是一种实现方式）。

- Premraj

---

加1代表书的例子。 - Akshansh Thakur

谢谢你的示例 :) - Aditya

太棒了。你用书的例子讲得非常好。 - Nouman Ghaffar

所以基本上是一个接口？ - funct7

一个接口是抽象的。 - Premraj

数组不是抽象数据类型。 - undefined

Answer 2

维基百科的抽象数据类型文章有很多内容。

在计算机科学中，抽象数据类型（ADT）是某类具有相似行为的数据结构的数学模型；或者是一种或多种编程语言的某些数据类型的数学模型。抽象数据类型仅通过可以对其执行的操作以及对这些操作的效果（可能的成本）的数学约束来间接定义。

稍微具体一点，您可以以Java的List接口为例。该接口并没有明确定义任何行为，因为没有具体的List类。该接口仅定义了一组方法，其他类（例如ArrayList和LinkedList）必须实现才能被视为List。

集合是另一种抽象数据类型。在Java的Collection接口的情况下，它比List更抽象，因为

以下是翻译：

List 接口在 Collection 接口规定的基础上，对 iterator、add、remove、equals 和 hashCode 方法的契约提出了额外的规定。

包也被称为multiset。

在数学中，多重集合（或称为“包”）的概念是集合概念的一种推广，其中允许成员出现多次。例如，包含元素 a 和 b 且不含其他元素的唯一集合是存在的，但有很多满足这个条件的多重集合，比如包含两个 a 和一个 b 的多重集合，或者包含三个 a 和三个 b 的多重集合。

在Java中，Bag将是一个实现非常简单接口的集合。您只需要能够向包中添加项目，检查其大小并迭代其包含的项目即可。请参见Bag.java以获取示例实现（来自Sedgewick和Wayne的算法第四版）。

- Bill the Lizard

Answer 3

抽象数据类型（ADT）的表示法

一个抽象数据类型可以被定义为数学模型，其中定义了一系列操作。一个简单的例子是整数集合，加上并、交等操作。

ADT是原始数据类型（如整数、字符等）的概括，它们封装了一个数据类型，即该类型的定义和所有操作都局限于程序的一个部分。在定义ADT及其操作的部分之外，它们被视为原始数据类型。

ADT的实现是将定义变量为该ADT的语句翻译成编程语言，并为该ADT的每个操作提供一个过程。ADT的实现选择一个数据结构来表示ADT。

指定数据类型逻辑属性的有用工具是抽象数据类型。从根本上讲，数据类型是一组值和对这些值进行操作的集合。该集合和这些操作形成了一个数学构造，可以使用特定的硬件和软件数据结构来实现。术语“抽象数据类型”指的是定义数据类型的基本数学概念。

在将抽象数据类型定义为数学概念时，我们不关心空间或时间效率。这些是实现问题。事实上，ADT的定义根本不涉及实现细节。甚至可能无法在特定的硬件或使用特定的软件系统上实现特定的ADT。例如，我们已经看到，整数ADT并非普遍可实现。

为了说明ADT和我的规范方法的概念，请考虑与有理数的数学概念相对应的ADT RATIONAL。有理数是可以表示为两个整数的商的数字。我们定义的有理数操作是从两个整数创建一个有理数、加法、乘法和测试相等。以下是此ADT的初始规范。

                  /* Value defination */

abstract typedef <integer, integer> RATIONAL;
condition RATIONAL [1]!=0;

                 /*Operator defination*/

abstract RATIONAL makerational (a,b)
int a,b;
preconditon b!=0;
postcondition makerational [0] =a;
              makerational [1] =b;
abstract RATIONAL add [a,b]
RATIONAL a,b;
postcondition add[1] = = a[1] * b[1]
              add[0] = a[0]*b[1]+b[0]*a[1]
abstract RATIONAL mult [a, b]
RATIONAL a,b;
postcondition mult[0] = = a[0]*b[a]
              mult[1] = = a[1]*b[1]
abstract equal (a,b)
RATIONAL a,b;
postcondition equal = = |a[0] * b[1] = = b[0] * a[1];

一个ADT由两部分组成：

1) 值定义

2) 操作定义

1) 值定义：

值定义定义了ADT的值集合，包括两个部分：

1) 定义子句

2) 条件子句

例如，ADT RATIONAL的值定义说明RATIONAL值由两个整数组成，其中第二个整数不等于0。

关键字abstract typedef引入了值定义，关键字condition用于指定新定义的数据类型上的任何条件。在这个定义中，条件规定分母不能为0。定义子句是必需的，但条件对于每个ADT可能并不一定需要。

2) 操作定义：

每个操作符都被定义为一个抽象交接点，由三个部分组成。

1）标头

2）可选的前置条件

3）可选的后置条件

例如，ADT RATIONAL 的操作符定义包括创建操作（makerational）、加法操作（add）、乘法操作（mult）以及相等性测试（equal）。让我们首先考虑乘法的规范，因为它是最简单的。它包含一个标头和后置条件，但没有前置条件。

abstract RATIONAL mult [a,b]
RATIONAL a,b;
postcondition mult[0] = a[0]*b[0]
              mult[1] = a[1]*b[1]

这个定义的头部是前两行，就像C函数头一样。关键字abstract表示它不是C函数，而是ADT运算符定义。 后置条件指定了操作的作用。在后置条件中，函数的名称（在本例中为mult）用于表示操作结果。因此，mult [0]表示结果的分子，mult 1表示结果的分母。它指定了操作执行后哪些条件变为真。在这个例子中，后置条件指定了有理数乘法结果的分子等于两个输入的分子的整数积，分母等于两个分母的整数积。

列表

在计算机科学中，列表或序列是一种抽象数据类型，表示可数数量的有序值，其中相同的值可能出现多次。列表的一个实例是有限序列的数学概念的计算机表示；列表的（可能）无限模拟是流。列表是容器的基本示例，因为它们包含其他值。如果同一值多次出现，则每个出现被视为一个不同的项。列表的名称也用于几种具体的数据结构，可以用来实现抽象列表，特别是链表。

列表图片

袋子

袋子是一组物体，您可以将物体添加到袋子中，但添加后无法将其删除。因此，使用袋数据结构，您可以收集所有对象，然后遍历它们。在Java编程中通常会使用袋。

一个包的图片

集合

Java中的集合指实现了Collection接口的任何类。通用意义上的集合只是一组对象。

收藏图片

- coding_ninza

Answer 4

Brilliant的维基百科上给出的最简单的解释之一：

抽象数据类型（Abstract data types，通常缩写为ADTs）是根据数据结构的使用方式和行为特征进行分类的一种方式。它们不规定数据结构必须如何实现或布局在内存中，而只提供一个最小的期望接口和一组行为特征。例如，堆栈是一种抽象数据类型，它指定了具有LIFO（后进先出）行为的线性数据结构。堆栈通常使用数组或链表来实现，但使用二叉搜索树等不必要复杂的实现仍然是有效的实现方法。需要明确的是，说堆栈就是数组或反之则是错误的。可以使用数组作为堆栈，同样，也可以使用数组来实现堆栈。

由于抽象数据类型没有指定实现方法，这意味着谈论给定抽象数据类型的时间复杂度也是不正确的。关联数组可能具有O（1）平均搜索时间，也可能没有。通过哈希表实现的关联数组确实具有O（1）平均搜索时间。

ADT示例：List - 可以使用Array和LinkedList、Queue、Deque、Stack、关联数组、Set来实现。

来源：https://brilliant.org/wiki/abstract-data-types/?subtopic=types-and-data-structures&chapter=abstract-data-types

- Sarvar Nishonboyev

Answer 5

一个真正抽象的数据类型描述它的实例属性，而不承诺它们的表示或特定操作。例如，抽象（数学）类型 Integer 是一组离散的、无限的、线性有序的实例。具体类型为实例提供了具体的表示，并实现了一组特定的操作。

- Dee

---

Integer类的加入有助于程序员处理通用类和Java集合框架中需要指定要创建的集合类型的情况，包装器/ ADT类非常有帮助。 - cammando

Answer 6

抽象数据类型实际上是:

• 定义逻辑数据类型的概念或理论模型
• 指定一组数据和一组可对该数据执行的操作
• 不提及如何实现操作
• "作为一种思想存在而没有物理形式"

例如，让我们看一些抽象数据类型的规范：

1. 列表抽象数据类型：initialize(), get(), insert(), remove()等
2. 栈抽象数据类型：push(), pop(), peek(), isEmpty(), isNull()等
3. 队列抽象数据类型：enqueue(), dequeue(), size(), peek()等

- Yeasin Arafath

Answer 7

ADT是一组数据值和相关操作，与任何特定实现完全独立。 ADT的优点在于其实现对用户隐藏，只有接口被声明。这意味着ADT可以以各种方式实现。

- purushottam ROY

Answer 8

抽象数据类型是一个包含各种操作的数学模块。实现细节被隐藏，因此它被称为抽象。抽象使您可以通过关注数据和操作的逻辑属性来组织任务的复杂性。

- user7189947

---

你把正确的知识放在了不好的格式里。在创建时，ADT绝对不需要具有实现细节。我们可以根据我们的用例定义它们的操作。简而言之，让我们从实现细节或定义操作中获得优势。 - cammando

Answer 9

抽象数据类型（ADT）是数据结构的抽象，仅提供数据结构必须遵循的接口。该接口不提供有关如何实现某些内容或使用哪种编程语言的具体细节。

- Mosharof Hossen

---

你的回答可以通过提供更多支持信息来改进。请编辑以添加进一步的细节，例如引用或文档，以便他人可以确认你的答案是正确的。您可以在帮助中心找到有关如何编写良好答案的更多信息。 - Sumit Sharma

Answer 10

在定义抽象数据类型之前，让我们考虑一下系统定义的数据类型的不同视图。 我们都知道，默认情况下所有基本数据类型（int、float等）都支持加法和减法等基本操作。 系统为原始数据类型提供实现。 对于用户定义的数据类型，我们还需要定义操作。 当我们想要实际使用它们时，可以对这些操作进行实现。 通常情况下，用户定义的数据类型与其操作一起定义。
为了简化解决问题的过程，我们将数据结构与其操作组合起来，称之为“抽象数据类型”（ADT）。 常用的ADT'S包括：链表、堆栈、队列、二叉树、字典、不相交集（联合和查找）、哈希表等等。
ADT's由两种类型组成：
1. 数据声明。
2. 操作声明。

- user9131165