08-建立接口
17.3.2 建立接口
这个简单链表的接口有两个部分。第1部分是描述如何表示数据，第2部分是描述实现ADT操作的函数。例如，要设计在链表中添加项的函数和报告链表中项数的函数。接口设计应尽量与ADT的描述保持一致。因此，应该用某种通用的 Item 类型而不是一些特殊类型，如 int 或 struct film 。可以用C的 typedef 功能来定义所需的 Item 类型：
#define TSIZE 45 /* 存储电影名的数组大小 */
struct film
{
char title[TSIZE];
int rating;
};
typedef struct film Item;然后，就可以在定义的其余部分使用 Item 类型。如果以后需要其他数据形式的链表，可以重新定义 Item 类型，不必更改其余的接口定义。
定义了 Item 之后，现在必须确定如何存储这种类型的项。实际上这一步属于实现步骤，但是现在决定好可以让示例更简单些。在 films2.c 程序中用链式结构处理得很好，所以，我们在这里也采用相同的方法：
typedef struct node
{
Item item;
struct node * next;
} Node;
typedef Node * List;在链表的实现中，每一个链节叫作节点（node）。每个节点包含形成链表内容的信息和指向下一个节点的指针。为了强调这个术语，我们把 node 作为节点结构的标记名，并使用 typedef 把 Node 作为 struct node 结构的类型名。最后，为了管理链表，还需要一个指向链表开始处的指针，我们使用 typedef 把 List 作为该类型的指针名。因此，下面的声明：
List movies;创建了该链表所需类型的指针 movies 。
这是否是定义 List 类型的唯一方法？不是。例如，还可以添加一个变量记录项数：
typedef struct list
{
Node * head; /* 指向链表头的指针 */
int size; /* 链表中的项数 */
} List; /* List的另一种定义 */可以像稍后的程序示例中那样，添加第2个指针存储链表的末尾。现在，我们还是使用 List 类型的第1种定义。这里要着重理解下面的声明创建了一个链表，而不是一个指向节点的指针或一个结构：
List movies;movies 代表的确切数据应该是接口层次不可见的实现细节。
例如，程序启动后应把头指针初始化为 NULL 。但是，不要使用下面这样的代码：
movies = NULL;为什么？因为稍后你会发现 List 类型的结构实现更好，所以应这样初始化：
movies.head = NULL;
movies.size = 0;使用 List 的人都不用担心这些细节，只要能使用下面的代码就行：
InitializeList(movies);使用该类型的程序员只需知道用 InitializeList() 函数来初始化链表，不必了解 List 类型变量的实现细节。这是数据隐藏的一个示例，数据隐藏是一种从编程的更高层次隐藏数据表示细节的艺术。
为了指导用户使用，可以在函数原型前面提供以下注释：
/* 操作：初始化一个链表 */
/* 前提条件：plist指向一个链表 */
/* 后置条件：该链表初始化为空 */
void InitializeList(List * plist);这里要注意3点。第1，注释中的“前提条件”（precondition）是调用该函数前应具备的条件。例如，需要一个待初始化的链表。第2，注释中的“后置条件”（postcondition）是执行完该函数后的情况。第3，该函数的参数是一个指向链表的指针，而不是一个链表。所以应该这样调用该函数：
InitializeList(&movies);由于按值传递参数，所以该函数只能通过指向该变量的指针才能更改主调程序传入的变量。这里，由于语言的限制使得接口和抽象描述略有区别。
C语言把所有类型和函数的信息集合成一个软件包的方法是：把类型定义和函数原型（包括前提条件和后置条件注释）放在一个头文件中。该文件应该提供程序员使用该类型所需的所有信息。程序清单17.3给出了一个简单链表类型的头文件。该程序定义了一个特定的结构作为 Item 类型，然后根据 Item 定义了 Node ，再根据 Node 定义了 List 。然后，把表示链表操作的函数设计为接受 Item 类型和 List 类型的参数。如果函数要修改一个参数，那么该参数的类型应是指向相应类型的指针，而不是该类型。在头文件中，把组成函数名的每个单词的首字母大写，以这种方式表明这些函数是接口包的一部分。另外，该文件使用第16章介绍的 #ifndef 指令，防止多次包含一个头文件。如果编译器不支持C99的 bool 类型，可以用下面的代码：
enum bool {false, true}; /* 把bool定义为类型，false和true是该类型的值 */替换下面的头文件：
#include <stdbool.h> /* C99特性 */程序清单17.3 list.h 接口头文件
/* list.h -- 简单链表类型的头文件 */
#ifndef LIST_H_
#define LIST_H_
#include <stdbool.h> /* C99特性 */
/* 特定程序的声明 */
#define TSIZE 45 /* 存储电影名的数组大小 */
struct film
{
char title[TSIZE];
int rating;
};
/* 一般类型定义 */
typedef struct film Item;
typedef struct node
{
Item item;
struct node * next;
} Node;
typedef Node * List;
/* 函数原型 */
/* 操作： 初始化一个链表 */
/* 前提条件： plist指向一个链表 */
/* 后置条件： 链表初始化为空 */
void InitializeList(List * plist);
/* 操作： 确定链表是否为空，plist指向一个已初始化的链表 */
/* 后置条件： 如果链表为空，该函数返回true；否则返回false */
bool ListIsEmpty(const List *plist);
/* 操作： 确定链表是否已满，plist指向一个已初始化的链表 */
/* 后置条件： 如果链表已满，该函数返回真；否则返回假 */
bool ListIsFull(const List *plist);
/* 操作： 确定链表中的项数, plist指向一个已初始化的链表 */
/* 后置条件： 该函数返回链表中的项数 */
unsigned int ListItemCount(const List *plist);
/* 操作： 在链表的末尾添加项 */
/* 前提条件： item是一个待添加至链表的项, plist指向一个已初始化的链表 */
/* 后置条件： 如果可以，该函数在链表末尾添加一个项，且返回true；否则返回false */
bool AddItem(Item item, List * plist);
/* 操作： 把函数作用于链表中的每一项 */
/* plist指向一个已初始化的链表 */
/* pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值 */
/* 后置条件： pfun指向的函数作用于链表中的每一项一次 */
void Traverse(const List *plist, void(*pfun)(Item item));
/* 操作： 释放已分配的内存（如果有的话） */
/* plist指向一个已初始化的链表 */
/* 后置条件： 释放了为链表分配的所有内存，链表设置为空 */
void EmptyTheList(List * plist);
#endif只有 InitializeList() 、 AddItem() 和 EmptyTheList() 函数要修改链表，因此从技术角度看，这些函数需要一个指针参数。然而，如果某些函数接受 List 类型的变量作为参数，而其他函数却接受 List 类型的地址作为参数，用户会很困惑。因此，为了减轻用户的负担，所有的函数均使用指针参数。
头文件中的一个函数原型比其他原型复杂：
/* 操作： 把函数作用于链表中的每一项 */
/* plist指向一个已初始化的链表 */
/* pfun指向一个函数，该函数接受一个Item类型的参数，且无返回值 */
/* 后置条件： pfun指向的函数作用于链表中的每一项一次 */
void Traverse(const List *plist, void(*pfun)(Item item));参数 pfun 是一个指向函数的指针，它指向的函数接受 item 值且无返回值。第14章中介绍过，可以把函数指针作为参数传递给另一个函数，然后该函数就可以使用这个被指针指向的函数。例如，该例中可以让 pfun 指向显示链表项的函数。然后把 Traverse() 函数把该函数作用于链表中的每一项，显示链表中的内容。