一　抽象数据类型

  数据类型是指一个类型和定义在这个类型上的一组操作。
  抽象数据类型(ADT，Abstract Data Type)对数据类型的抽象描述。它并不关注数据类型的实现方式，转而关注数据类型的操作。

单击此处进一步体会二者差异

  以下给出了数据类型和抽象数据类型的表示示例：
数据类型示例 - 整数（Integer）

  • 名称：整数（Integer）
  • 描述：表示整数值的基本数据类型。
  • 内部表示：在内存中以二进制补码形式存储。
  • 支持的操作：
    • 加法、减法、乘法、除法等基本数学运算。
    • 比较操作（大于、小于、等于等）。
    • 转换为其他数据类型（例如，转换为浮点数）。

抽象数据类型示例 - 栈（Stack）

  • 名称：栈（Stack）
  • 描述：表示一个具有后进先出（LIFO）特性的抽象数据类型。
  • 支持的操作：
    • push(item): 将元素压入栈顶。
    • pop(): 弹出栈顶元素并返回。
    • peek(): 查看栈顶元素，不进行弹出操作。
    • isEmpty(): 检查栈是否为空。
    • size(): 返回栈中元素的数量。

  注意到栈定义了一组操作，但并未规定其具体实现方式。不同的数据结构（如数组、链表）可以用来支持栈的操作，但只需要关注栈的操作。这再次表明，抽象数据类型不必关心实现细节。

二　数据结构

  数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。它研究的是就是如何按一定的逻辑结构，把数据组织起来，并选择适当的存储表示方法把逻辑结构组织好的数据存储到计算机的存储器里。

请注意：
  数据结构-常指存储在计算机内存中的数据。
  文件结构-常指外存储器（如磁盘驱动器、CD）中数据的组织。

  诸如数组、栈、队列、链表等都是常用的数据结构。数据结构一般包含以下几种常用运算：

  • 检索。检索就是在数据结构里查找满足一定条件的节点。一般是给定一个某字段的值，找具有该字段值的节点。
  • 插入。往数据结构中增加新的节点。
  • 删除。把指定的结点从数据结构中去掉。
  • 更新。改变指定节点的一个或多个字段的值。
  • 排序。把节点按某种指定的顺序重新排列。例如递增或递减。

三　数据项、数据结构和抽象数据类型的关系

  数据项有逻辑形式和物理形式两个方面。ADT定义了数据项的逻辑形式，数据结构是实现数据项的物理形式。这是因为我们强调过ADT关注操作而不关注实现，因而ADT用以阐释数据项的逻辑形式。我们注意到在数据结构的研究内容中，提到了把逻辑结构组织好的数据，这就是ADT的作用。而数据结构关注的恰好就是如何存储，亦即如何实现，因而数据结构用以阐释数据项的物理形式。