ADT或混凝土

Question

有人能解释一下抽象数据类型(ADT)和具体数据结构之间的确切区别吗？当我读这本书(Anany Levitin，Design and Analysis of Algorithms)时，它指出ADT是一个数据结构加上对它们的一组操作。然而，让我困惑的是，数组和链表也定义了一些特定的操作(例如添加元素，删除元素)，它们被认为是具体的数据类型。由于这种混乱，我不能自己决定一个新的数据结构(例如堆、树、二进制搜索树)是抽象的还是具体的。

Answer 1

ADT是对数据结构外观的描述，它不包含任何代码-可以将它看作是一种规范，当程序员要求他们为您编写数据结构时，您可以将其视为一种规范。

堆栈的ADT可能如下所示：

void push(int)
int pop()

相应的具体数据结构将包含使这些函数工作所需的实际代码：

void push(int x){
    // implementation code here
}
int pop(){
    // implementation code here
}

Answer 2

数据结构、抽象数据类型和数据类型之间的关系与算法、伪代码和程序之间的关系相同。第一个是一个想法，第二个是描述，第三个是实现。