4.2. 抽象数据类型¶
4.2.1. 抽象数据类型¶
本模块介绍与应对计算机程序巨大复杂性的各种技术相关的术语和定义。它还给出两个基本却颇为微妙的术语—— 数据项 和 数据结构 ——的实用定义。我们从数据结构赖以构建的基本要素讲起。
类型 是值的集合。例如，布尔类型由值 true 和 false 组成。整数也构成一个类型。整数是一种 简单类型 ，因为它的值不包含子部分。银行账户记录通常包含若干信息，比如姓名、地址、账号和账户余额。这样的记录就是 聚合类型 或 复合类型 的一个例子。 数据项 是一条信息或一个记录，其值取自某个类型。我们说数据项是某个类型的 成员 。
数据类型 是一种类型，连同操纵该类型的一组操作。例如，整型变量就是整数数据类型的一个成员。加法是对整数数据类型进行操作的一个例子。
应当区分数据类型的逻辑概念与其在计算机程序中的物理实现。 例如，线性表数据类型有两种传统实现： 链表和基于数组的线性表。 因此，线性表数据类型既可以用链表实现，也可以用数组实现。 但当我们想用线性表来辅助更复杂的设计时，并不需要知道线性表 是如何实现的。 例如，线性表可以用来辅助实现 图数据结构 。
再举一个例子，"数组（array）"一词既可以指一种数据类型，也可以 指一种实现。 在计算机编程中，"数组"通常指一块连续的内存单元，每个内存单元 存储一个定长的数据项。 按照这种含义，数组是一种物理数据结构。 然而，数组也可以指一种逻辑数据类型，它由（通常是同构的）数据项 集合组成，每个数据项由一个下标编号标识。 除了作为连续的内存块之外，数组还可以用许多不同的方式实现。 稀疏矩阵 指的是一种大型的 二维数组，只存储相对较少的非零值。 稀疏矩阵常用链式结构实现，也可能用 哈希表 实现。 但它也可以用一个使用传统行列下标的接口来实现，这样呈现给用户的 样子，与把它实现为一块连续内存单元时完全相同。
抽象数据类型 （ADT）是某种语言中对数据类型的规约，独立于任何实现。 ADT 的接口由一个类型以及作用在该类型上的一组操作来定义。每个操作的行为由其输入和输出决定。 ADT 并不规定数据类型 如何 实现。这些实现细节对 ADT 的用户是隐藏的，并受到保护而不被外部访问，这一概念称为 封装 。
数据结构 是 ADT 的实现。在面向对象语言中，ADT 及其实现合在一起构成一个 类 。与 ADT 相关联的每个操作都由 成员函数 或 方法 实现。定义数据项所需空间的那些变量称为 数据成员 。 对象 是类的实例，也就是说，它是在计算机程序执行期间被创建并占用存储空间的东西。
数据结构 一词通常指存储在计算机主存中的数据。与之相关的术语 文件结构 通常指数据在外围存储设备（如磁盘驱动器或光盘）上的组织方式。
对于使用同一 ADT 的两个应用程序，其中一个可能比另一个更频繁地使用某些操作，或者它们对各种操作有不同的时间约束。所幸 ADT 可以通过提供不同的实现来适应这些需求上的差异。
即使在与计算无关的应用中， ADT 的概念也能帮助我们把注意力集中在关键问题上。
ADT 的概念是这样一条重要原则的一个实例，任何成功的计算机科学家都必须理解它：通过抽象来管理复杂性。计算机科学的一个中心主题就是复杂性以及应对复杂性的技术。人类应对复杂性的方法是：给一组对象或概念贴上一个标签，然后操纵这个标签来代替这组对象或概念。认知心理学家把这样的标签称为 隐喻 。某个特定的标签可能与其他信息或其他标签相关联。这个集合反过来又可以被赋予一个标签，从而形成概念与标签的层次结构。这种标签的层次结构使我们能够专注于重要问题，同时忽略不必要的细节。
设想一下，在设计一个实现并操纵某个 ADT 的复杂计算机程序时，你会如何着手。该 ADT 在程序的一部分中由某个特定的数据结构实现。在设计程序中使用该 ADT 的那些部分时，你可以基于对数据类型的操作来思考，而不必关心数据结构的实现。如果没有这种简化复杂程序思维的能力，你就不可能理解或实现这个程序。
数据类型既有 逻辑形式 ，也有 物理形式 。用 ADT 给出的数据类型定义就是它的逻辑形式。把数据类型实现为某种数据结构就是它的物理形式。有时你可能会看到 concrete implementation （具体实现）这个术语，但"具体"一词是多余的。下图展示了数据类型逻辑形式与物理形式之间的这种关系。当你实现一个 ADT 时，你处理的是相应数据类型的物理形式。当你在程序的其他地方使用一个 ADT 时，你关心的是相应数据类型的逻辑形式。本书的某些小节关注给定数据结构的物理实现。另一些小节则在更高层次任务的语境中使用数据结构的逻辑 ADT。
ADT 定义数据类型的逻辑形式。数据结构实现数据类型的物理形式。 ADT 的使用者通常是程序员，他们与 ADT 的实现者使用同一种语言工作。通常，这些程序员希望把 ADT 用作另一个应用程序中的一个组件。 ADT 的接口也常被称为该 ADT 的应用程序编程接口（Application Programmer Interface，API）。接口成为实现者与使用者这两种程序员之间的一种交流方式。
