06-抽象数据类型（ADT）

17.3　抽象数据类型（ADT）

在编程时，应该根据编程问题匹配合适的数据类型。例如，用 int 类型代表你有多少双鞋，用 float 或 double 类型代表每双鞋的价格。在前面的电影示例中，数据构成了链表，每个链表项由电影名（ C 字符串）和评级（一个 int 类型值）。C中没有与之匹配的基本类型，所以我们定义了一个结构代表单独的项，然后设计了一些方法把一系列结构构成一个链表。本质上，我们使用C语言的功能设计了一种符合程序要求的新数据类型。但是，我们的做法并不系统。现在，我们用更系统的方法来定义数据类型。

什么是类型？类型特指两类信息：属性和操作。例如， int 类型的属性是它代表一个整数值，因此它共享整数的属性。允许对 int 类型进行的算术操作有：改变 int 类型值的符号、两个 int 类型值相加、相减、相乘、相除、求模。当声明一个 int 类型的变量时，就表明了只能对该变量进行这些操作。

注意　整数属性 C的 int 类型背后是一个更抽象的整数概念。数学家已经用正式的抽象方式定义了整数的属性。例如，假设N和M是整数，那么N+M=M+N；假设S、Q也是整数，如果N+M=S，而且N+Q=S，那么M=Q。可以认为数学家提供了整数的抽象概念，而C则实现了这一抽象概念。注意，实现整数的算术运算是表示整数必不可少的部分。如果只是存储值，并未在算术表达式中使用， int 类型就没那么有用了。还要注意的是，C并未很好地实现整数。例如，整数是无穷大的数，但是2字节的 int 类型只能表示65536个整数。因此，不要混淆抽象概念和具体的实现。

假设要定义一个新的数据类型。首先，必须提供存储数据的方法，例如设计一个结构。其次，必须提供操控数据的方法。例如，考虑 films2.c 程序（程序清单17.2）。该程序用链接的结构来存储信息，而且通过代码实现了如何添加和显示信息。尽管如此，该程序并未清楚地表明正在创建一个新类型。我们应该怎么做？

计算机科学领域已开发了一种定义新类型的好方法，用3个步骤完成从抽象到具体的过程。

1．提供类型属性和相关操作的抽象描述。这些描述既不能依赖特定的实现，也不能依赖特定的编程语言。这种正式的抽象描述被称为抽象数据类型（ADT）。

2．开发一个实现ADT的编程接口。也就是说，指明如何存储数据和执行所需操作的函数。例如在C中，可以提供结构定义和操控该结构的函数原型。这些作用于用户定义类型的函数相当于作用于C基本类型的内置运算符。需要使用该新类型的程序员可以使用这个接口进行编程。

3．编写代码实现接口。这一步至关重要，但是使用该新类型的程序员无需了解具体的实现细节。

我们再次以前面的电影项目为例来熟悉这个过程，并用新方法重新完成这个示例。