algorithm - ADT 或混凝土

Question

有人可以阐明抽象数据类型 (ADT) 和具体数据结构之间的确切区别吗？当我阅读这本书(Anany Levitin，算法的设计和分析)时，它指出 ADT 是一种数据结构加上对它们的一组操作。然而，让我感到困惑的是，数组和链表也定义了一些特定的操作(例如添加元素、删除元素)，它们被认为是具体的数据类型。由于这种困惑，我不能自己决定一个新的数据结构(例如堆、树、二叉搜索树)是抽象的还是具体的。

Answer 1

ADT 是对数据结构外观的描述，它不包含任何代码 - 将其视为您在要求程序员为您编写数据结构时可能提供给他们的规范。

堆栈的 ADT 可能如下所示:

void push(int)
int pop()

相应的具体数据结构将包含使这些功能正常工作所需的实际代码:

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