java - 所有数据结构都有抽象数据类型吗？

Question

我在某些地方读到了有关该主题的相互矛盾的内容，例如这里

Is heap an abstract data type? If so, what about priority queues?

答案是:

both priority queues & heaps are data types (more accurate; abstract data type or ADT)

但是这里

Is Heap considered an Abstract Data Type?

Heap is not an ADT. It is a Data Structure.

例如书中的例子:

Java 软件结构，国际版 [John Lewis、Joseph Chase]

它有一个作为 ADT 的堆和一个带有以下代码的 DS:

public interface HeapADT<T> extends BinaryTreeADT<T>
{
/**
* Adds the specified object to this heap.
*
* @param obj the element to be added to this heap
*/
public void addElement (T obj);
/**
* Removes element with the lowest value from this heap.
*
* @return the element with the lowest value from this heap
*/
public T removeMin();
/**
* Returns a reference to the element with the lowest value in
* this heap.
*
* @return a reference to the element with the lowest value in this heap
*/
public T findMin();
}

主要问题是，例如，我们是否说 DS 的所有行为定义都是 ADT

• List是静态和动态数组、链表的ADT
• 栈，是一个ADT，但是你可以用数组或者链表来实现栈，但最终这个栈是一个数据结构
• 队列，同栈
• 堆，与栈相同

因此，抽象数据类型是您将使用具有自己的 ADT 的另一个数据结构来实现的行为。

这是正确的吗？

谢谢

Answer 1

正如您所说，抽象数据类型描述了实体的行为(或“语义”)(通常从使用该实体的人的角度来看)。所以在你的例子中，堆栈、队列、列表等......

数据结构只是组织数据的一种特殊方式。所以它只是表示数据类型的一种方式。

The main question is if we say that all behaviour definition of a DS is an ADT

我不会这么说。如果我定义一个代表汽车经典示例的数据结构(再次将数据结构视为组织数据的方式)，则该数据结构的行为不一定代表 ADT。