预计阅读本页时间：-
整数的属性
在C的int类型背后是一个更抽象的概念，即整数（integer）。数学家能够并且已经用正式的抽象方式定义了整数的属性。比如，如果N和M是整数，那么N+M=M+N；再比如，对任何两个整数N和M，有一个整数S，使得N+M=S。如果N+M=S且N+Q=S，那么M=Q。您可以认为数学提供了整数的抽象概念，而C提供了这一概念的实现。比如，C提供存储整数和执行诸如加法和乘法之类的整数运算的手段。请注意提供对算术运算的支持是表示整数的核心部分。如果您只能存储一个值而不能在算术表达式中使用它，那么int类型就不是那么有用了。还要注意C的这一实现并没有很好地表示整数。比如，整数是无穷的，但是一个2字节的int数只能表示65536个整数；不要将抽象概念和具体的实现相混淆。
假设您想定义一个新的数据类型。首先，您需要提供存储数据的方式，可能是通过设计一个结构。第二，需要提供操作数据的方式。比如，考虑films2.c程序（程序清单17.2）。它用一系列链接在一起的结构来保存信息，还提供了添加信息和显示信息的代码。但是这个程序并没有明确地表明我们在创建一个新的类型。应该怎么做呢？
计算机科学已经研究出一种定义新类型的成功方法。这种方法使用3个步骤来完成从抽象到具体的过程：
1．为类型的属性和可对类型执行的操作提供一个抽象的描述。这个描述不应受任何特定实现的约束，甚至不应受到任何特定编程语言的约束。这样一种正式的抽象描述被称为抽象数据类型（ADT）。
2．开发一个实现该ADT的编程接口。即说明如何存储数据并描述用于执行所需操作的函数集合。比如在C中，您可能同时提供一个结构的定义和用来操作该结构的函数的原型。这些函数对用户自定义类型的作用和C的内置运算符对C基本类型的作用一样。想要使用这种新类型的人可以使用这个接口来进行编程。
3．编写代码来实现这个接口。当然，这一步至关重要，但是使用这种新类型的程序员无须了解实现的细节。
我们通过一个例子来了解这个过程。因为我们已经在电影列表的例子中做过一些工作，所以就让我们使用这种新方法来重新完成这个任务。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
17.3.1 变得抽象
基本上，关于电影的工程所需的就是一个项目列表，每个项目包含一个影片名和一个等级。您需要能向列表末尾添加新的项目，并且能显示列表的内容。让我们把满足这些需求的抽象类型称为“列表（list）”。一个列表应有哪些属性呢？显然，列表应该能够保存项目序列。即，列表能够保存多个项目，并且这些项目以某种方式排列，从而能够谈及列表中的第一个项目或第二个项目或最后一个项目。而且，列表类型应该支持诸如向列表添加一个项目之类的操作。下面是一些有用的操作：
● 把列表初始化为空列表。
● 向列表末尾添加一个项目。
● 确定列表是否为空。
● 确定列表是否已满。
● 确定列表中有多少项目。
● 访问列表中每一个项目以执行某些任务，比如显示项目。
对此工程来说不需要对列表进行其他操作，但是通常的列表操作还包括如下内容：
● 在列表中的任何位置插入一个项目。
● 从列表中删除一个项目。
● 取出列表的一个项目（不改变列表）。
● 替换列表中的一个项目。
● 在列表中搜索一个项目。
非正式但抽象的列表定义是：它是一个能够保存项目序列并且可以对其应用任何前面的操作的数据对象。这个定义没有说明什么样的项目才能存储在列表中。它并未指定是否应该使用数组或链接的结构集或其他数据形式来保存这些项目。它并未指定使用何种方法来实现诸如获取列表中的元素个数之类的操作。这些都是留给实现的细节。
为了使例子更简单，我们采用一种简化的列表作为抽象数据类型，它只包含电影工程所需的属性。表17.1是此类型的一个总结：
表17.1 列表类型总结
| 类 型 名 称： | 简 单 列 表 |
|---|---|
| 类型属性： | 可保存一个项目序列 |
| 类型操作： | 把列表初始化为空列表 |
| 确定列表是否为空 | |
| 确定列表是否已满 | |
| 确定列表中项目的个 | |
| 向列表末尾添加项目 | |
| 遍历列表，处理列表中每个项目 | |
| 清空列表 |
下一步是为简单列表ADT开发一个C语言接口。
17.3.2 构造接口
简单列表的接口有两个部分。第一部分描述数据如何表示，第二部分描述实现ADT操作的函数。比如，应该有用于向列表添加项目的函数，和用于报告列表中项目数的函数。接口的设计应和ADT的描述尽可能密切地保持一致。因此，应该用某种通用的Item类型来进行表达，而不是用诸如int或struct film之类的专用类型。这样做的方法之一是使用C的typedef工具将Item定义为所需类型：
然后可以在其余的定义中使用Item类型。如果以后需要其他形式数据的列表，您可以重新定义Item类型，而使其余的接口定义保持不变。
定义了Item之后，您需要决定如何存储这种类型的项目。这一步确实应属于实现阶段，但是现在做出决定可以使例子更简单一些。在films2.c程序中，链接结构方法工作得很好，所以我们采用它，如下所示：
在链表的实现中，每一个链接被称为一个节点（node）。每一个节点包含形成列表内容的信息和指向下一节点的指针。为了强调这个术语，我们对节点结构使用标记node，并且通过typedef使Node成为struct node结构的类型名。最后，为了管理链表，需要一个指向其开始处的指针，我们通过typedef使List成为指向Node类型的指针的名称。因此：
的声明表明movies是一个适合指向链表的指针。
这是定义List类型的惟一方法吗？不是的。比如，可以加入一个变量来保存列表中项目的数量：
可以添加第二个指针来保存列表末尾。稍后，您可以看到一个这样做的例子。现在，还是让我们使用List类型的第一种定义。重要的一点是要考虑清楚如下声明：
是在建立一个列表，而不是在建立一个指向节点的指针或是建立一个结构。movies的确切数据表示是应该在接口层上不可见的实现细节。
比如，启动后程序应该把头指针初始化为NULL。但是，不应使用这样的代码：
为什么不能这样做？因为稍后您也许会发现您更喜欢List类型的结构实现，那将需要下面的初始化语句：
任何使用List类型的人都应无须担心这些细节，而应能够使用下面的代码：
程序员只需要知道他们应该使用InitializeList（）函数来初始化列表，不需要知道List变量的确切的数据实现。这是数据隐藏（data hiding）的一个例子。数据隐藏是一种对更高级编程隐藏数据表示细节的艺术。
为了引导用户，您可以用下面的行来提供函数原型。
有三点需要注意。第一，注释概要“操作前（precondition）”是调用函数之前应具有的情形。例如，这里需要一个待初始化的列表。第二，注释概要“操作后（postcondition）”是执行函数后应具有的情形。最后，函数使用一个指向列表的指针（而不是一个列表）作为其参数，所以函数调用应像下面这样：
原因是C按值来传递参数，所以C函数要想改变调用程序中的变量，惟一的途径是使用指向该变量的指针。这里，由于语言的限制使得接口和抽象描述有略微的差别。
C语言把所有的类型和函数信息集成到一个包中的方法是将类型定义和函数原型（包括“操作前”和“操作后”注释）放入一个头文件中。这个文件将提供程序员使用该类型所需的全部信息。程序清单117.3显示了简单列表类型的头文件。它定义了一个特定结构作为Item类型，然后根据Item类型定义了Node，又根据Node类型定义了List类型。然后，代表列表操作的函数用Item类型和List类型作为它们的参数。如果一个函数需要修改参数，它使用指向相关类型的指针，而不是直接使用类型。文件大写每个函数名，以表示其为接口包的一部分。另外，文件使用第16章“C预处理器和C库”中讨论的#ifndef技术对多次包含一个文件提供保护。如果你的编译器并不支持C99布尔类型，你可以在头文件中用：
替换：
程序清单17.3 list.h接口头文件
只有InitializeList（）、AddItem（）和EmptyTheList（）函数修改列表，因此，从技术上讲只有这些方法需要一个指针参数。然而，如果用户必须记住把一个List参数传递给某个函数并把一个List的地址作为参数传递给另外一个函数，那么这很容易混淆。因此，为了使用户的责任变得简单化，所有的函数都使用指针参数。
头文件中的一个原型比其他原型略复杂。
参数pfun是指向函数的指针。具体地，它是指向将一个项目作为参数且没有返回值的函数的指针。回忆一下第14章“结构和其他数据形式”中的内容，可以将指向函数的指针作为一个参数传递给另一个函数，然后这个函数就可以使用被指向的函数。例如，可以让pfun指向用于显示一个项目的函数。然后Traverse（）函数将此函数作用于列表中每一个项目，从而显示整个列表。
17.3.3 使用接口
我们的要求是应该能使用这个接口编写程序而不必知道太多的细节，比如，不用知道函数如何编写。在编写支持函数之前，我们编写电影程序的新版本。因为接口使用List和Item类型，所以程序也应使用这些类型。下面是一种可能的伪代码方案：
程序清单17.4显示的程序遵循了这个伪代码方案，其中加入了一些错误检查的代码。注意它如何利用list.h文件（程序清单17.3）中描述的接口。还要注意程序清单中含有与Traverse（）函数要求的原型一致的showmovies（）函数的代码。因此，程序能够把指针showmovies传递给Traverse（）,从而使Traverse（）能够对列表中的每一个项目应用showmovies（）函数（回忆一下，函数名是指向该函数的指针）。
程序清单17.4 films3.c程序
17.3.4 实现接口
当然，还需要实现List接口。C的方法是在list.c文件中集中进行函数定义。整个程序由三个文件组成：list.h,定义数据结构并为用户接口提供原型；list.c，提供函数代码以实现接口；films3.c，将列表接口应用于具体编程问题的源代码文件。程序清单17.5显示了list.c的一种可能实现。要运行这个程序，必须编译并链接films3.c和list.c（可以复习一下第9章“函数”中关于编译多文件程序的讨论）。文件list.h、list.c和films3.c共同组成了完整的程序（请参见图17.5）。
图17.5 程序包的三个部分
程序清单17.5 list.c实现文件
一、程序注释
list.c文件有许多有趣的方面。其一，它说明了何时该使用内部链接函数。如12章中所述，内部链接函数只在定义它的文件中可见。在实现接口时，您有时会发现编写不作为正式接口一部分的辅助函数很方便。比如，示例程序中使用了CopyToNode（）函数把一个Item类型值复制到一个Item类型变量。因为这个函数是实现的一部分但不是接口的一部分，所以我们通过使用static存储类限定词将其隐藏在list.c文件中。现在，我们来讨论其他函数。
InitializeList（）函数将列表初始化为空列表。在我们的实现中，这意味着把一个List类型变量设置为NULL。如前所述，这要求向函数传递一个指向list变量的指针。
ListIsEmpty（）函数很简单，其前提条件是当列表为空时，列表变量被设置为NULL。因此，在使用ListIsEmpty（）函数之前初始化列表很重要。而且，如果要扩展接口以包含删除项目的操作，就需要确保当列表的最后一项被删除后，删除函数将列表重置为空列表。因为这个函数不改变列表，不需要传递指针参数，所以参数的类型是List而不是指向List的指针。
对于链表而言，列表的大小受可用内存数量的限制。ListIsFull（）函数尝试为一个新项目分配足够的空间。如果这一操作失败，则列表已满；如果成功，就需要释放其刚分配的内存以使其为真正的项目所用。
ListItemCount（）函数使用常用的链表算法来遍历列表，同时统计项目个数：
AddItem（）函数是这些函数中所做工作最多的：
AddItem（）函数首先为新节点分配空间。如果成功，函数用CopyToNode（）把项目复制到新节点，然后设置节点的next成员为NULL。回忆一下，这表明该节点是链表中的最后一个节点。最后，在创建节点和对节点成员正确赋值之后，函数将该节点添加到列表结尾处。如果此项目是添加到列表中的第一项，程序把头指针设置为指向第一项（记住，头指针地址是传递给AddItem（）的第二个参数，所以*plist是头指针的值）。否则，代码继续在链表中前进，直到发现其next成员被设置为NULL的项目。这个节点就是当前的最后节点，所以函数重置其next成员以指向新的节点。
按照良好的编程惯例，您应在向列表中添加项目之前调用ListIsFull（）函数。但是，用户可能未能遵守这一惯例，所以AddItem（）自己检查malloc（）是否成功。而且，用户还可能会在调用ListIsFull（）和调用AddItem（）之间做其他事情时分配内存，所以最好检查malloc（）是否成功。
Traverse（）函数和ListItemCount（）函数类似，但它还将一个函数作用于列表中的每一项：
回忆一下，pnode->item表示节点中存储的数据，而pnode->next表示链表中的下一节点。比如，下面的函数调用将showmovies（）函数作用于列表中的每一项：
最后，EmptyTheList（）函数释放先前用malloc（）函数分配的内存：
实现通过把List变量设置为NULL来指示一个空列表。因此需要向这个函数传递List变量地址以使其能重置它。因为List已经是一个指针，所以plist是一个指向指针的指针。因此，在代码中，表达式*plist的类型是指向Node的指针。当列表到达结尾处时，*plist是NULL，这意味着原来的实际参数现在已设为NULL。
代码保存下一节点的地址，因为原则上调用free（）可能使当前节点（*plist指向的那个节点）的内容不再可用。
