57

我目前正在研究抽象数据类型（ADT），但我根本不明白这个概念。有人可以向我解释这实际上是什么吗？还有什么是collection、bag和List ADT？简单来说？

4

20 回答 20

118

抽象数据类型（ADT）是一种数据类型，其中只定义了行为而不是实现。

ADT 的对面是具体数据类型 (CDT)，其中包含 ADT 的实现。

示例：
Array, List, Map, Queue, Set, Stack, Table, Tree, and Vector是 ADT。这些 ADT 中的每一个都有许多实现，即 CDT。容器是所有 ADT 的高级 ADT。

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

在此处输入图像描述

于 2015-06-29T10:27:16.933 回答
20

Abstact数据类型Wikipedia 文章有很多话要说。

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

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

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

List除了接口中指定的规定之外，该接口还对、、、和方法Collection的合同进行了附加规定。iteratoraddremoveequalshashCode

包也称为multiset。

在数学中，多重集（或袋子）的概念是集合概念的概括，其中成员被允许多次出现。例如，有一个唯一集合包含元素 a 和 b 而没有其他元素，但是有许多具有此属性的多重集，例如包含 a 的两个副本和 b 的一个副本的多重集或包含三个副本的多重集a和b。

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

于 2012-08-06T02:33:36.240 回答
3

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

于 2016-10-25T21:10:45.413 回答
3

Brilliant wiki 上给出的最简单的解释之一：

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

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

ADT 示例：List - 可以使用 Array 和 LinkedList、Queue、Deque、Stack、Associative array、Set 来实现。

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

于 2021-01-18T09:02:03.067 回答
3

实际上抽象数据类型是：

  • 逻辑上定义数据类型的概念或理论模型
  • 指定数据集和可以对该数据执行的操作集
  • 没有提及任何有关如何实施操作的内容
  • “作为一个想法而存在，但没有一个物理的想法”

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

  1. 列表抽象数据类型：initialize()、get()、insert()、remove()等。
  2. 堆栈抽象数据类型：push()、pop()、peek()、isEmpty()、isNull()等。
  3. 队列抽象数据类型：enqueue()、dequeue()、size()、peek()等。
于 2020-09-27T10:49:16.637 回答
2

抽象数据类型 (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表示结果的分母。也就是说，它指定了在执行操作后哪些条件变为真。在此示例中，后置条件指定有理乘法结果的分子等于两个输入的分子的整数乘积，分母等于两个分母的整数乘积。

列表

在计算机科学中，列表或序列是一种抽象数据类型，表示可计数的有序值，其中相同的值可能出现多次。列表的实例是有限序列的数学概念的计算机表示；列表的（可能）无限模拟是流。列表是容器的基本示例，因为它们包含其他值。如果相同的值多次出现，则每次出现都被视为一个不同的项目

名称列表也用于几个具体的数据结构，这些数据结构可以用来实现抽象列表，尤其是链表。

在此处输入图像描述

列表的图像

包

袋子是对象的集合，您可以在其中继续向袋子中添加对象，但一旦添加到袋子中，您就无法删除它们。因此，使用 bag 数据结构，您可以收集所有对象，然后遍历它们。当你用 Java 编程时，你会正常打包。

包

包的图像

收藏

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

在此处输入图像描述

收藏图片

于 2017-12-23T11:28:20.243 回答
1

ADT 是一组完全独立于任何特定实现的数据值和相关操作。ADT 的优势在于实现对用户隐藏。仅声明接口。这意味着 ADT 有多种方式

于 2013-12-11T05:16:55.057 回答
1

摘要 数据类型是一个数学模块，包括具有各种操作的数据。实现细节是隐藏的，这就是它被称为抽象的原因。抽象允许您通过关注数据和操作的逻辑属性来组织任务的复杂性。

于 2016-11-21T14:51:47.263 回答
1

在编程语言中，类型是一些数据和相关的操作。ADT 是用户定义的数据聚合和对这些数据的操作，其特点是封装，数据和操作在单个句法单元中表示或声明在列表中，并且信息隐藏，只有相关操作对ADT 的用户，ADT接口，与编程语言中的普通数据类型相同。这是一种抽象，因为数据的内部表示和操作的实现与 ADT 用户无关。

于 2017-05-16T19:14:32.457 回答
1

在定义抽象数据类型之前，让我们考虑系统定义数据类型的不同视图。我们都知道，默认情况下，所有原始数据类型（int、float 等）都支持加减法等基本操作。系统提供原始数据类型的实现。对于用户定义的数据类型，我们还需要定义操作。当我们想要实际使用它们时，可以完成这些操作的实现。这意味着通常，用户定义的数据类型与其操作一起定义。

为了简化解决问题的过程，我们将数据结构与其操作结合起来，我们称之为“抽象数据类型”。（ADT）。

常用的ADT包括：链表、堆栈、队列、二叉树、字典、不相交集（联合和查找）、哈希表等。

ADT由两种类型组成：

1. 数据声明。

2. 经营声明。

于 2017-12-23T11:58:01.500 回答
0

简单的抽象数据类型不过是一组操作，一组数据用于在机器中有效地存储一些其他数据。不需要任何特定的类型声明。它只需要 ADT 的实现。

于 2015-03-08T14:14:21.160 回答
0

抽象只为您提供信息（服务信息），但不提供实现。例如：当您从 ATM 机取款时，您只知道一件事，即将您的 ATM 卡放到机器上，单击取款选项，输入金额，如果有钱，您的钱就出来了。这只是您对 ATM 机的了解。但是你知道你是怎么收钱的吗？背后是什么业务逻辑？哪个数据库被调用？正在调用哪个位置的哪个服务器？不，您只知道服务信息，即您可以提款。这是一个抽象。

同样，ADT 为您提供数据类型的概述：它们是/可以存储什么以及您可以对这些数据类型执行哪些操作。但它没有提供如何实现它。这是 ADT。它只定义数据类型的逻辑形式。

另一个类比是：在汽车或自行车上，你只知道当你踩刹车时，你的车就会停下来。但是你知道踩刹车时自行车是怎么停下来的吗？？？不，意味着实现细节被隐藏了。您只知道踩下刹车时的作用，但不知道它是如何作用的。

于 2021-05-12T02:08:16.940 回答
0

抽象数据类型就像用户定义的数据类型，我们可以在不知道数据类型内部有什么以及如何对它们执行操作的情况下执行功能。由于信息未公开，因此其抽象化。例如。列表、数组、堆栈、队列。在 Stack 上，我们可以执行 Push、Pop 等功能，但我们不确定它是如何在幕后实现的。

于 2017-05-31T04:07:24.627 回答
0

为了解决问题，我们将数据结构与其操作相结合。ADT 由两部分组成：

  1. 数据声明。
  2. 操作声明。

常用的 ADT 是链表、堆栈、队列、优先级队列、树等。在定义 ADT 时，我们不需要担心实现细节。只有当我们想使用它们时，它们才会出现。

于 2017-03-14T13:31:21.410 回答
0

抽象数据类型，有时缩写为 ADT，是对我们如何查看数据和允许的操作的逻辑描述，而不考虑它们将如何实现。这意味着我们只关心数据代表什么，而不关心它最终将如何构建。

https://runestone.academy/runestone/books/published/pythonds/Introduction/WhyStudyDataStructuresandAbstractDataTypes.html

于 2020-09-02T18:23:50.573 回答
0

抽象数据类型是值的集合以及对这些值的任何类型的操作。例如，由于 String 不是原始数据类型，我们可以将其包含在抽象数据类型中。

于 2018-01-11T08:32:20.427 回答
0

简而言之：抽象数据类型是数据和对该数据进行操作的集合。这些操作既向程序的其余部分描述数据，又允许程序的其余部分更改数据。“抽象数据类型”中的“数据”一词使用松散。ADT 可能是一个图形窗口，其中包含影响它的所有操作、文件和文件操作、保险费率表及其上的操作，或其他东西。

从代码完成 2 本书

于 2018-06-01T17:37:51.777 回答
0

ADT 是一种数据类型，其中数据的收集和操作对该数据起作用。它更多地关注概念而不是实现。这取决于您使用哪种语言使其在地球上可见示例：堆栈是 ADT 而数组不是堆栈是 ADT，因为我们可以通过多种语言实现它，Python c c ++ java等等，而Array是内置的数据类型

于 2019-05-14T23:17:26.903 回答
0

ADT 是一组对象和操作，在 ADT 的定义中没有任何地方提到如何实现这组操作。使用集合的程序员只需要知道如何以某种预先确定的方式实例化和访问数据，而不用关心集合实现的细节。换句话说，从用户的角度来看，集合是一种抽象，因此，在计算机科学中，一些集合被称为抽象数据类型 (ADT)。用户只关心学习它的界面，或者它执行的操作集......更多

于 2017-11-26T13:08:52.150 回答
-1

术语数据类型是特定变量可以保存的数据类型——它可以是整数、字符、浮点数或任何范围的简单数据存储表示。但是，当我们构建面向对象的系统时，我们会使用其他数据类型，称为抽象数据类型，它表示更现实的实体。

例如：我们可能对表示“银行账户”数据类型感兴趣，它描述了程序中如何处理所有银行账户。抽象是关于降低复杂性，忽略不必要的细节。

于 2019-08-13T19:34:33.957 回答