目录 | 上一页 | 下一页
第17章高级数据表示

第17章高级数据表示

本章介绍以下内容：

函数：进一步学习malloc()

使用C表示不同类型的数据

新的算法，从概念上增强开发程序的能力

抽象数据类型（ADT）

学习计算机语言和学习音乐、木工或工程学一样。首先，要学会使用工具：学习如何演奏音阶、如何使用锤子等，然后解决各种问题，如降落、滑行以及平衡物体之类。到目前为止，读者一直在本书中学习和练习各种编程技能，如创建变量、结构、函数等。然而，如果想提高到更高层次时，工具是次要的，真正的挑战是设计和创建一个项目。本章将重点介绍这个更高的层次，教会读者如何把项目看作一个整体。本章涉及的内容可能比较难，但是这些内容非常有价值，将帮助读者从编程新手成长为老手。

我们先从程序设计的关键部分，即程序表示数据的方式开始。通常，程序开发最重要的部分是找到程序中表示数据的好方法。正确地表示数据可以更容易地编写程序其余部分。到目前为止，读者应该很熟悉C的内置类型：简单变量、数组、指针、结构和联合。

然而，找出正确的数据表示不仅仅是选择一种数据类型，还要考虑必须进行哪些操作。也就是说，必须确定如何储存数据，并且为数据类型定义有效的操作。例如，C实现通常把int类型和指针类型都储存为整数，但是这两种类型的有效操作不相同。例如，两个整数可以相乘，但是两个指针不能相乘；可以用*运算符解引用指针，但是对整数这样做毫无意义。C 语言为它的基本类型都定义了有效的操作。但是，当你要设记数据表示的方案时，你可能需要自己定义有效操作。在C语言中，可以把所需的操作设计成C函数来表示。简而言之，设计一种数据类型包括设计如何储存该数据类型和设计一系列管理该数据的函数。

本章还会介绍一些算法（algorithm），即操控数据的方法。作为一名程序员，应该掌握这些可以反复解决类似问题的处理方法。

本章将进一步研究设计数据类型的过程，这是一个把算法和数据表示相匹配的过程。期间会用到一些常见的数据形式，如队列、列表和二叉树。

本章还将介绍抽象数据类型（ADT）的概念。抽象数据类型以面向问题而不是面向语言的方式，把解决问题的方法和数据表示结合起来。设计一个ADT后，可以在不同的环境中复用。理解ADT可以为将来学习面向对象程序设计（OOP）以及C++语言做好准备。

17.1 研究数据表示

我们先从数据开始。假设要创建一个地址簿程序。应该使用什么数据形式储存信息？由于储存的每一项都包含多种信息，用结构来表示每一项很合适。如何表示多个项？是否用标准的结构数组？还是动态数组？还是一些其他形式？各项是否按字母顺序排列？是否要按照邮政编码（或地区编码）查找各项？需要执行的行为将影响如何储存信息？简而言之，在开始编写代码之前，要在程序设计方面做很多决定。

如何表示储存在内存中的位图图像？位图图像中的每个像素在屏幕上都单独设置。在以前黑白屏的年代，可以使用一个计算机位（1 或 0）来表示一个像素点（开或闭），因此称之为位图。对于彩色显示器而言，如果8位表示一个像素，可以得到256种颜色。现在行业标准已发展到65536色（每像素16位）、16777216色（每像素24位）、2147483色（每像素32位），甚至更多。如果有32位色，且显示器有2560×1440的分辨率，则需要将近1.18亿位（14M）来表示一个屏幕的位图图像。是用这种方法表示，还是开发一种压缩信息的方法？是有损压缩（丢失相对次要的数据）还是无损压缩（没有丢失数据）？再次提醒读者注意，在开始编写代码之前，需要做很多程序设计方面的决定。

我们来处理一个数据表示的示例。假设要编写一个程序，让用户输入一年内看过的所有电影（包括DVD和蓝光光碟）。要储存每部影片的各种信息，如片名、发行年份、导演、主演、片长、影片的种类（喜剧、科幻、爱情等）、评级等。建议使用一个结构储存每部电影，一个数组储存一年内看过的电影。为简单起见，我们规定结构中只有两个成员：片名和评级（0～10）。程序清单17.1演示了一个基本的实现。

程序清单17.1 films1.c程序

/* films1.c -- 使用一个结构数组 */

#include　<stdio.h>

#include　<string.h>

#define TSIZE　　 45　/* 储存片名的数组大小 */

#define FMAX　　　5　 /* 影片的最大数量 */

struct　film　{

char　title[TSIZE];

int　rating;

};

char * s_gets(char str[], int lim);

int　main(void)

{

struct　film　movies[FMAX];

int　i　=　0;

int　j;

puts("Enter　first　movie　title:");

while　(i　<　FMAX　&&　s_gets(movies[i].title,　TSIZE)　!=　NULL　&&

movies[i].title[0]　!=　'\0')

{

puts("Enter　your　rating　<0-10>:");

scanf("%d",　&movies[i++].rating);

while　(getchar()　!=　'\n')

continue;

puts("Enter　next　movie　title　(empty　line　to　stop):");

}

if　(i　==　0)

printf("No　data　entered.　");

else

printf("Here　is　the　movie　list:\n");

for　(j　=　0;　j　<　i;　j++)

printf("Movie:　%s　 Rating:　%d\n",　movies[j].title,movies[j].rating);

printf("Bye!\n");

return　0;

}

char * s_gets(char * st, int n)

{

char * ret_val;

char * find;

ret_val　=　fgets(st,　n,　stdin);

if　(ret_val)

{

find = strchr(st, '\n');　　// 查找换行符

if (find)　　　　　　　　　　　// 如果地址不是 NULL,

*find = '\0';　　　　　// 在此处放置一个空字符

else

while　(getchar()　!=　'\n')

continue;　　　　　　// 处理剩余输入行

}

return　ret_val;

}

该程序创建了一个结构数组，然后把用户输入的数据储存在数组中。直到数组已满（用 FMAX 进行判断）或者到达文件结尾（用NULL进行判断），或者用户在首行按下Enter键（用'\0'进行判断），输入才会终止。

这样设计程序有点问题。首先，该程序很可能会浪费许多空间，因为大部分的片名都不会超过40个字符。但是，有些片名的确很长，如The Discreet Charm of the Bourgeoisie和Won Ton Ton, The Dog Who Saved Hollywood。其次，许多人会觉得每年5部电影的限制太严格了。当然，也可以放宽这个限制，但是，要多大才合适？有些人每年可以看500部电影，因此可以把FMAX改为500。但是，对有些人而言，这可能仍然不够，而对有些人而言一年根本看不了这么多部电影，这样就浪费了大量的内存。另外，一些编译器对自动存储类别变量（如 movies）可用的内存数量设置了一个默认的限制，如此大型的数组可能会超过默认设置的值。可以把数组声明为静态或外部数组，或者设置编译器使用更大的栈来解决这个问题。但是，这样做并不能根本解决问题。

该程序真正的问题是，数据表示太不灵活。程序在编译时确定所需内存量，其实在运行时确定会更好。要解决这个问题，应该使用动态内存分配来表示数据。可以这样做：

#define TSIZE 45　/*储存片名的数组大小*/

struct　film　{

char　title[TSIZE];

int　rating;

};

...

int　n,　i;

struct film * movies;　/* 指向结构的指针 */

...

printf("Enter　the　maximum　number　of　movies　you'll　enter:\n");

scanf("%d",　&n);

movies = (struct film *) malloc(n * sizeof(struct film));

第12章介绍过，可以像使用数组名那样使用指针movies。

while (i < FMAX && s_gets(movies[i].title, TSIZE) != NULL &&movies[i].title[0] != '\0')

使用malloc()，可以推迟到程序运行时才确定数组中的元素数量。所以，如果只需要20个元素，程序就不必分配存放500个元素的空间。但是，这样做的前提是，用户要为元素个数提供正确的值。

17.2 从数组到链表

理想的情况是，用户可以不确定地添加数据（或者不断添加数据直到用完内存量），而不是先指定要输入多少项，也不用让程序分配多余的空间。这可以通过在输入每一项后调用 malloc()分配正好能储存该项的空间。如果用户输入3部影片，程序就调用malloc()3次；如果用户输入300部影片，程序就调用malloc()300次。

不过，我们又制造了另一个麻烦。比较一下，一种方法是调用malloc()一次，为300个filem结构请求分配足够的空间；另一种方法是调用malloc()300次，分别为每个file结构请求分配足够的空间。前者分配的是连续的内存块，只需要一个单独的指向struct变量（film）的指针，该指针指向已分配块中的第1个结构。简单的数组表示法让指针访问块中的每个结构，如前面代码段所示。第2种方法的问题是，无法保证每次调用malloc()都能分配到连续的内存块。这意味着结构不一定被连续储存（见图17.1）。因此，与第1种方法储存一个指向300个结构块的指针相比，你需要储存300个指针，每个指针指向一个单独储存的结构。

图17.1 一块内存中分配结构和单独分配结构

一种解决方法是创建一个大型的指针数组，并在分配新结构时逐个给这些指针赋值，但是我们不打算使用这种方法：

#define TSIZE 45　/*储存片名的数组大小*/

#define FMAX 500　/*影片的最大数量*/

struct　film　{

char　title[TSIZE];

int　rating;

};

...

struct film * movies[FMAX]; /* 结构指针数组 */

int　i;

...

movies[i] = (struct film *) malloc (sizeof (struct film));

如果用不完500个指针，这种方法节约了大量的内存，因为内含500个指针的数组比内含500个结构的数组所占的内存少得多。尽管如此，如果用不到 500 个指针，还是浪费了不少空间。而且，这样还是有500个结构的限制。

还有一种更好的方法。每次使用 malloc()为新结构分配空间时，也为新指针分配空间。但是，还得需要另一个指针来跟踪新分配的指针，用于跟踪新指针的指针本身，也需要一个指针来跟踪，以此类推。要重新定义结构才能解决这个潜在的问题，即每个结构中包含指向 next 结构的指针。然后，当创建新结构时，可以把该结构的地址储存在上一个结构中。简而言之，可以这样定义film结构：

#define TSIZE 45　/* 储存片名的数组大小*/

struct　film　{

char　title[TSIZE];

int　rating;

struct film * next;

};

虽然结构不能含有与本身类型相同的结构，但是可以含有指向同类型结构的指针。这种定义是定义链表（linked list）的基础，链表中的每一项都包含着在何处能找到下一项的信息。

在学习链表的代码之前，我们先从概念上理解一个链表。假设用户输入的片名是Modern Times，等级为10。程序将为film类型的结构分配空间，把字符串Modern Times拷贝到结构中的title成员中，然后设置rating成员为10。为了表明该结构后面没有其他结构，程序要把next成员指针设置为NULL（NULL是一个定义在stdio.h头文件中的符号常量，表示空指针）。当然，还需要一个单独的指针储存第1个结构的地址，该指针被称为头指针（head pointer）。头指针指向链表中的第1项。图17.2演示了这种结构（为节约图片空间，压缩了title成员中的空白）。

图17.2 链表中的第1个项

现在，假设用户输入第2部电影及其评级，如Midnight in Paris和8。程序为第2个film类型结构分配空间，把新结构的地址储存在第1个结构的next成员中（擦写了之前储存在该成员中的NULL），这样链表中第1个结构中的next指针指向第2个结构。然后程序把Midnight in Paris和8拷贝到新结构中，并把第2个结构中的next成员设置为NULL，表明该结构是链表中的最后一个结构。图17.3演示了这两个项。

图17.3 链表中的两个项

每加入一部新电影，就以相同的方式来处理。新结构的地址将储存在上一个结构中，新信息储存在新结构中，而且新结构中的next成员设置为NULL。从而建立起如图17.4所示的链表。

图17.4 链表中的多个项

假设要显示这个链表，每显示一项，就可以根据该项中已储存的地址来定位下一个待显示的项。然而，这种方案能正常运行，还需要一个指针储存链表中第1项的地址，因为链表中没有其他项储存该项的地址。此时，头指针就派上了用场。

17.2.1 使用链表

从概念上了解了链表的工作原理，接着我们来实现它。程序清单17.2修改了程序清单17.1，用链表而不是数组来储存电影信息。

程序清单17.2 films2.c程序

/* films2.c -- 使用结构链表 */

#include　<stdio.h>

#include <stdlib.h>　　　　/* 提供malloc()原型 */

#include <string.h>　　　　/* 提供strcpy()原型 */

#define TSIZE　 45　　　　/* 储存片名的数组大小 */

struct　film　{

char　title[TSIZE];

int　rating;

struct film * next;　　/* 指向链表中的下一个结构 */

};

char * s_gets(char * st, int n);

int　main(void)

{

struct film * head = NULL;

struct film * prev, *current;

char　input[TSIZE];

/* 收集并储存信息 */

puts("Enter　first　movie　title:");

while　(s_gets(input,　TSIZE)　!=　NULL　&&　input[0]　!=　'\0')

{

current = (struct film *) malloc(sizeof(struct film));

if (head == NULL)　　　/* 第1个结构 */

head　=　current;

else　　　　　　　　　 /* 后续的结构 */

prev->next　=　current;

current->next　=　NULL;

strcpy(current->title,　input);

puts("Enter　your　rating　<0-10>:");

scanf("%d",　&current->rating);

while　(getchar()　!=　'\n')

continue;

puts("Enter　next　movie　title　(empty　line　to　stop):");

prev　=　current;

}

/* 显示电影列表 */

if　(head　==　NULL)

printf("No　data　entered.　");

else

printf("Here　is　the　movie　list:\n");

current　=　head;

while　(current　!=　NULL)

{

printf("Movie:　%s　 Rating:　%d\n",

current->title,　current->rating);

current　=　current->next;

}

/* 完成任务，释放已分配的内存 */

current　=　head;

while　(current　!=　NULL)

{

current　=　head;

head　=　current->next;

free(current);

}

printf("Bye!\n");

return　0;

}

char * s_gets(char * st, int n)

{

char * ret_val;

char * find;

ret_val　=　fgets(st,　n,　stdin);

if　(ret_val)

{

find = strchr(st, '\n');　　// 查找换行符

if (find)　　　　　　　　// 如果地址不是 NULL，

*find = '\0';　　　　　// 在此处放置一个空字符

else

while　(getchar()　!=　'\n')

continue;　　　 // 处理剩余输入行

}

return　ret_val;

}

该程序用链表执行两个任务。第 1 个任务是，构造一个链表，把用户输入的数据储存在链表中。第 2个任务是，显示链表。显示链表的任务比较简单，所以我们先来讨论它。

1.显示链表

显示链表从设置一个指向第1个结构的指针（名为current）开始。由于头指针（名为head）已经指向链表中的第1个结构，所以可以用下面的代码来完成：

current = head;

然后，可以使用指针表示法访问结构的成员：

printf("Movie: %s Rating: %d\n", current->title, current->rating);

下一步是根据储存在该结构中next成员中的信息，重新设置current指针指向链表中的下一个结构。代码如下：

current = current->next;

完成这些之后，再重复整个过程。当显示到链表中最后一个项时，current 将被设置为 NULL，因为这是链表最后一个结构中next成员的值。

while　(current　!=　NULL)

{

printf("Movie:　%s　Rating:　%d\n",　current->title,　current->rating);

current　=　current->next;

}

遍历链表时，为何不直接使用head指针，而要重新创建一个新指针（current）？因为如果使用head会改变head中的值，程序就找不到链表的开始处。

2.创建链表

创建链表涉及下面3步：

（1）使用malloc()为结构分配足够的空间；

（2）储存结构的地址；

（3）把当前信息拷贝到结构中。

如无必要不用创建一个结构，所以程序使用临时存储区（input数组）获取用户输入的电影名。如果用户通过键盘模拟EOF或输入一行空行，将退出下面的循环：

while (s_gets(input, TSIZE) != NULL && input[0] != '\0')

如果用户进行输入，程序就分配一个结构的空间，并将其地址赋给指针变量current:

current = (struct film *) malloc(sizeof(struct film));

链表中第1 个结构的地址应储存在指针变量head中。随后每个结构的地址应储存在其前一个结构的next成员中。因此，程序要知道它处理的是否是第1个结构。最简单的方法是在程序开始时，把head指针初始化为NULL。然后，程序可以使用head的值进行判断：

if (head == NULL) /* 第1个结构*/

head = current;

else /* subsequent structures */

prev->next = current;

在上面的代码中，指针prev指向上一次分配的结构。

接下来，必须为结构成员设置合适的值。尤其是，把next成员设置为NULL，表明当前结构是链表的最后一个结构。还要把input数组中的电影名拷贝到title成员中，而且要给rating成员提供一个值。如下代码所示：

current->next　=　NULL;

strcpy(current->title,　input);

puts("Enter　your　rating　<0-10>:");

scanf("%d",　&current->rating);

由于s_gets()限制了只能输入TSIZE-1个字符，所以用strcpy()函数把input数组中的字符串拷贝到title成员很安全。

最后，要为下一次输入做好准备。尤其是，要设置 prev 指向当前结构。因为在用户输入下一部电影且程序为新结构分配空间后，当前结构将成为新结构的上一个结构，所以程序在循环末尾这样设置该指针：

prev = current;

程序是否能正常运行？下面是该程序的一个运行示例：

Enter　first　movie　title:

Spirited　Away

Enter　your　rating　<0-10>:

Enter　next　movie　title　(empty　line　to　stop):

The　Duelists

Enter　your　rating　<0-10>:

Enter　next　movie　title　(empty　line　to　stop):

Devil　Dog:　The　Mound　of　Hound

Enter　your　rating　<0-10>:

Enter　next　movie　title　(empty　line　to　stop):

Here　is　the　movie　list:

Movie:　Spirited　Away　Rating:　9

Movie:　The　Duelists　Rating:　8

Movie:　Devil　Dog:　The　Mound　of　Hound　Rating:　1

Bye!

3.释放链表

在许多环境中，程序结束时都会自动释放malloc()分配的内存。但是，最好还是成对调用malloc()和free()。因此，程序在清理内存时为每个已分配的结构都调用了free()函数：

current　=　head;

while　(current　!=　NULL)

{

current　=　head;

head　=　current->next;

free(current);

}

17.2.2 反思

films2.c 程序还有些不足。例如，程序没有检查 malloc()是否成功请求到内存，也无法删除链表中的项。这些不足可以弥补。例如，添加代码检查malloc()的返回值是否是NULL（返回NULL说明未获得所需内存）。如果程序要删除链表中的项，还要编写更多的代码。

这种用特定方法解决特定问题，并且在需要时才添加相关功能的编程方式通常不是最好的解决方案。另一方面，通常都无法预料程序要完成的所有任务。随着编程项目越来越大，一个程序员或编程团队事先计划好一切模式，越来越不现实。很多成功的大型程序都是由成功的小型程序逐步发展而来。

如果要修改程序，首先应该强调最初的设计，并简化其他细节。程序清单 17.2 中的程序示例没有遵循这个原则，它把概念模型和代码细节混在一起。例如，该程序的概念模型是在一个链表中添加项，但是程序却把一些细节（如，malloc()和 current->next 指针）放在最明显的位置，没有突出接口。如果程序能以某种方式强调给链表添加项，并隐藏具体的处理细节（如调用内存管理函数和设置指针）会更好。把用户接口和代码细节分开的程序，更容易理解和更新。学习下面的内容就可以实现这些目标。

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.编写代码实现接口。这一步至关重要，但是使用该新类型的程序员无需了解具体的实现细节。

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

17.3.1 建立抽象

从根本上看，电影项目所需的是一个项链表。每一项包含电影名和评级。你所需的操作是把新项添加到链表的末尾和显示链表中的内容。我们把需要处理这些需求的抽象类型叫作链表。链表具有哪些属性？首先，链表应该能储存一系列的项。也就是说，链表能储存多个项，而且这些项以某种方式排列，这样才能描述链表的第1项、第2项或最后一项。其次，链表类型应该提供一些操作，如在链表中添加新项。下面是链表的一些有用的操作：

初始化一个空链表；

在链表末尾添加一个新项；

确定链表是否为空；

确定链表是否已满；

确定链表中的项数；

访问链表中的每一项执行某些操作，如显示该项。

对该电影项目而言，暂时不需要其他操作。但是一般的链表还应包含以下操作：

在链表的任意位置插入一个项；

移除链表中的一个项；

在链表中检索一个项（不改变链表）；

用另一个项替换链表中的一个项；

在链表中搜索一个项。

非正式但抽象的链表定义是：链表是一个能储存一系列项且可以对其进行所需操作的数据对象。该定义既未说明链表中可以储存什么项，也未指定是用数组、结构还是其他数据形式来储存项，而且并未规定用什么方法来实现操作（如，查找链表中元素的个数）。这些细节都留给实现完成。

为了让示例尽量简单，我们采用一种简化的链表作为抽象数据类型。它只包含电影项目中的所需属性。该类型总结如下：

类型名：　　　　简单链表

类型属性：　　　可以储存一系列项

类型操作：　　　初始化链表为空

确定链表为空

确定链表已满

确定链表中的项数

在链表末尾添加项

遍历链表，处理链表中的项

清空链表

下一步是为开发简单链表ADT开发一个C接口。

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.next　=　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()函数把该函数作用于链表中的每一项，显示链表中的内容。

17.3.3 使用接口

我们的目标是，使用这个接口编写程序，但是不必知道具体的实现细节（如，不知道函数的实现细节）。在编写具体函数之前，我们先编写电影程序的一个新版本。由于接口要使用List和Item类型，所以该程序也应使用这些类型。下面是编写该程序的一个伪代码方案。

创建一个List类型的变量。

创建一个Item类型的变量。

初始化链表为空。

当链表未满且有输入时：

把输入读取到Item类型的变量中。

在链表末尾添加项。

访问链表中的每个项并显示它们。

程序清单 17.4 中的程序按照以上伪代码来编写，其中还加入了一些错误检查。注意该程序利用了list.h（程序清单 17.3）中描述的接口。另外，还需注意，链表中含有 showmovies()函数的代码，它与Traverse()的原型一致。因此，程序可以把指针showmovies传递给Traverse()，这样Traverse()可以把showmovies()函数应用于链表中的每一项（回忆一下，函数名是指向该函数的指针）。

程序清单17.4 films3.c程序

/* films3.c -- 使用抽象数据类型（ADT）风格的链表 */

/* 与list.c一起编译　　　　　　　　　　　*/

#include　<stdio.h>

#include <stdlib.h>　 /* 提供exit()的原型 */

#include "list.h"　　 /* 定义List、Item　*/

void　showmovies(Item　item);

char * s_gets(char * st, int n);

int　main(void)

{

List　movies;

Item　temp;

/* 初始化　　　*/

InitializeList(&movies);

if　(ListIsFull(&movies))

{

fprintf(stderr,　"No　memory　available!　Bye!\n");

exit(1);

}

/* 获取用户输入并储存 */

puts("Enter　first　movie　title:");

while　(s_gets(temp.title,　TSIZE)　!=　NULL　&&　temp.title[0]　!=　'\0')

{

puts("Enter　your　rating　<0-10>:");

scanf("%d",　&temp.rating);

while　(getchar()　!=　'\n')

continue;

if　(AddItem(temp,　&movies)　==　false)

{

fprintf(stderr,　"Problem　allocating　memory\n");

break;

}

if　(ListIsFull(&movies))

{

puts("The　list　is　now　full.");

break;

}

puts("Enter　next　movie　title　(empty　line　to　stop):");

}

/* 显示　　　　*/

if　(ListIsEmpty(&movies))

printf("No　data　entered.　");

else

{

printf("Here　is　the　movie　list:\n");

Traverse(&movies,　showmovies);

}

printf("You　entered　%d　movies.\n",　ListItemCount(&movies));

/* 清理　　　 */

EmptyTheList(&movies);

printf("Bye!\n");

return　0;

}

void　showmovies(Item　item)

{

printf("Movie:　%s　 Rating:　%d\n",　item.title,

item.rating);

}

char * s_gets(char * st, int n)

{

char * ret_val;

char * find;

ret_val　=　fgets(st,　n,　stdin);

if　(ret_val)

{

find = strchr(st, '\n');　　// 查找换行符

if (find)　　　　　　　　　　　// 如果地址不是NULL，

*find = '\0';　　　　　// 在此处放置一个空字符

else

while　(getchar()　!=　'\n')

continue;　　　　　　// 处理输入行的剩余内容

}

return　ret_val;

}

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 list.c实现文件

/* list.c -- 支持链表操作的函数 */

#include　<stdio.h>

#include　<stdlib.h>

#include　"list.h"

/* 局部函数原型 */

static void CopyToNode(Item item, Node * pnode);

/* 接口函数　*/

/* 把链表设置为空 */

void InitializeList(List * plist)

{

*plist = NULL;

}

/* 如果链表为空，返回true */

bool ListIsEmpty(const List * plist)

{

if (*plist == NULL)

return　true;

else

return　false;

}

/* 如果链表已满，返回true */

bool ListIsFull(const List * plist)

{

Node * pt;

bool　full;

pt = (Node *)malloc(sizeof(Node));

if　(pt　==　NULL)

full　=　true;

else

full　=　false;

free(pt);

return　full;

}

/* 返回节点的数量 */

unsigned int ListItemCount(const List * plist)

{

unsigned　int　count　=　0;

Node * pnode = *plist;　 /* 设置链表的开始 */

while　(pnode　!=　NULL)

{

++count;

pnode = pnode->next;　/* 设置下一个节点 */

}

return　count;

}

/* 创建储存项的节点，并将其添加至由plist指向的链表末尾（较慢的实现） */

bool AddItem(Item item, List * plist)

{

Node * pnew;

Node * scan = *plist;

pnew = (Node *) malloc(sizeof(Node));

if　(pnew　==　NULL)

return false;　　/* 失败时退出函数 */

CopyToNode(item,　pnew);

pnew->next　=　NULL;

if (scan == NULL)　　　　/* 空链表，所以把 */

*plist = pnew;　　　 /* pnew放在链表的开头 */

else

{

while　(scan->next　!=　NULL)

scan = scan->next;　/* 找到链表的末尾 */

scan->next = pnew;　　 /* 把pnew添加到链表的末尾 */

}

return　true;

}

/* 访问每个节点并执行pfun指向的函数 */

void Traverse(const List * plist, void(*pfun)(Item item))

{

Node * pnode = *plist;　 /* 设置链表的开始 */

while　(pnode　!=　NULL)

{

(*pfun)(pnode->item); /* 把函数应用于链表中的项 */

pnode = pnode->next;　/* 前进到下一项　*/

}

/* 释放由malloc()分配的内存 */

/* 设置链表指针为NULL　　　*/

void EmptyTheList(List * plist)

{

Node * psave;

while (*plist != NULL)

{

psave = (*plist)->next;　　/* 保存下一个节点的地址　 */

free(*plist);　　　　　　　/* 释放当前节点　　　　 */

*plist = psave;　　　　　　/* 前进至下一个节点　　　*/

}

/* 局部函数定义 */

/* 把一个项拷贝到节点中 */

static void CopyToNode(Item item, Node * pnode)

{

pnode->item = item;　/* 拷贝结构 */

}

图17.5 电影程序的3个部分

1.程序的一些注释

list.c文件有几个需要注意的地方。首先，该文件演示了什么情况下使用内部链接函数。如第12章所述，具有内部链接的函数只能在其声明所在的文件夹可见。在实现接口时，有时编写一个辅助函数（不作为正式接口的一部分）很方便。例如，使用CopyToNode()函数把一个Item类型的值拷贝到Item类型的变量中。由于该函数是实现的一部分，但不是接口的一部分，所以我们使用 static 存储类别说明符把它隐藏在list.c文件中。接下来，讨论其他函数。

InitializeList()函数将链表初始化为空。在我们的实现中，这意味着把List类型的变量设置为NULL。前面提到过，这要求把指向List类型变量的指针传递给该函数。

ListIsEmpty()函数很简单，但是它的前提条件是，当链表为空时，链表变量被设置为NULL。因此，在首次调用 ListIsEmpty()函数之前初始化链表非常重要。另外，如果要扩展接口添加删除项的功能，那么当最后一个项被删除时，应该确保该删除函数重置链表为空。对链表而言，链表的大小取决于可用内存量。ListIsFull()函数尝试为新项分配空间。如果分配失败，说明链表已满；如果分配成功，则必须释放刚才分配的内存供真正的项所用。

ListItemCount()函数使用常用的链表算法遍历链表，同时统计链表中的项：

unsigned int ListItemCount(const List * plist)

{

unsigned　int　count　=　0;

Node * pnode = *plist;　 /* 设置链表的开始 */

while　(pnode　!=　NULL)

{

++count;

pnode = pnode->next;　/* 设置下一个节点 */

}

return　count;

}

AddItem()函数是这些函数中最复杂的：

bool AddItem(Item item, List * plist)

{

Node * pnew;

Node * scan = *plist;

pnew = (Node *) malloc(sizeof(Node));

if　(pnew　==　NULL)

return false;　　　　　　　/* 失败时退出函数 */

CopyToNode(item,　pnew);

pnew->next　=　NULL;

if (scan == NULL)　　　　　　　/* 空链表，所以把 */

*plist = pnew;　　　　　　 /* pnew放在链表的开头 */

else

{

while　(scan->next　!=　NULL)

scan = scan->next; /* 找到链表的末尾 */

scan->next = pnew;　　 /* 把pnew添加到链表的末尾 */

}

return　true;

}

AddItem()函数首先为新节点分配空间。如果分配成功，该函数使用 CopyToNode()把项拷贝到新节点中。然后把该节点的next成员设置为NULL。这表明该节点是链表中的最后一个节点。最后，完成创建节点并为其成员赋正确的值之后，该函数把该节点添加到链表的末尾。如果该项是添加到链表的第 1 个项，需要把头指针设置为指向第1项（记住，头指针的地址是传递给AddItem()函数的第2个参数，所以*plist就是头指针的值）。否则，代码继续在链表中前进，直到发现被设置为NULL的next成员。此时，该节点就是当前的最后一个节点，所以，函数重置它的next成员指向新节点。

要养成良好的编程习惯，给链表添加项之前应调用ListIsFull()函数。但是，用户可能并未这样做，所以在AddItem()函数内部检查malloc()是否分配成功。而且，用户还可能在调用ListIsFull()和调用AddItem()函数之间做其他事情分配了内存，所以最好还是检查malloc()是否分配成功。

Traverse()函数与ListItemCount()函数类似，不过它还把一个指针函数作用于链表中的每一项。

void Traverse (const List * plist, void (* pfun)(Item item) )

{

Node * pnode = *plist; /* 设置链表的开始 */

while　(pnode　!=　NULL)

{

(*pfun)(pnode->item); /* 把函数应用于该项*/

pnode = pnode->next;　 /* 前进至下一个项 */

}

pnode->item代表储存在节点中的数据，pnode->next标识链表中的下一个节点。如下函数调用：

Traverse(movies, showmovies);

把showmovies()函数应用于链表中的每一项。

最后，EmptyTheList()函数释放了之前malloc()分配的内存：

void EmptyTheList(List * plist)

{

Node * psave;

while (*plist != NULL)

{

psave = (*plist)->next;　　/* 保存下一个节点的地址　 */

free(*plist);　　　　　　　/* 释放当前节点　　　　 */

*plist = psave;　　　　　　/* 前进至下一个节点　　　*/

}

该函数的实现通过把List类型的变量设置为NULL来表明一个空链表。因此，要把List类型变量的地址传递给该函数，以便函数重置。由于List已经是一个指针，所以plist是一个指向指针的指针。因此，在上面的代码中，*plist是指向Node的指针。当到达链表末尾时，*plist为NULL，表明原始的实际参数现在被设置为NULL。

代码中要保存下一节点的地址，因为原则上调用了free()会使当前节点（即*plist指向的节点）的内容不可用。

提示 const的限制

多个处理链表的函数都把const List * plist作为形参，表明这些函数不会更改链表。这里， const确实提供了一些保护。它防止了*plist（即plist所指向的量）被修改。在该程序中，plist指向movies，所以const防止了这些函数修改movies。因此，在ListItemCount()中，不允许有类似下面的代码：

*plist = (*plist)->next; // 如果*plist是const，不允许这样做

因为改变*plist就改变了movies，将导致程序无法跟踪数据。然而，*plist和movies都被看作是const并不意味着*plist或movies指向的数据是const。例如，可以编写下面的代码：

(*plist)->item.rating = 3; // 即使*plist是const，也可以这样做

因为上面的代码并未改变*plist，它改变的是*plist指向的数据。由此可见，不要指望const能捕获到意外修改数据的程序错误。

2.考虑你要做的

现在花点时间来评估ADT方法做了什么。首先，比较程序清单17.2和程序清单17.4。这两个程序都使用相同的内存分配方法（动态分配链接的结构）解决电影链表的问题，但是程序清单17.2暴露了所有的编程细节，把malloc()和prev->next这样的代码都公之于众。而程序清单17.4隐藏了这些细节，并用与任务直接相关的方式表达程序。也就是说，该程序讨论的是创建链表和向链表中添加项，而不是调用内存函数或重置指针。简而言之，程序清单17.4是根据待解决的问题来表达程序，而不是根据解决问题所需的具体工具来表达程序。ADT版本可读性更高，而且针对的是最终的用户所关心的问题。

其次，list.h 和 list.c 文件一起组成了可复用的资源。如果需要另一个简单的链表，也可以使用这些文件。假设你需要储存亲戚的一些信息：姓名、关系、地址和电话号码，那么先要在 list.h 文件中重新定义Item类型：

typedef　struct　itemtag

{

char　fname[14];

char　lname　[24];

char　relationship[36];

char　address　[60];

char　phonenum[20];

}　Item;

然后„„只需要做这些就行了。因为所有处理简单链表的函数都与Item类型有关。根据不同的情况，有时还要重新定义CopyToNode()函数。例如，当项是一个数组时，就不能通过赋值来拷贝。

另一个要点是，用户接口是根据抽象链表操作定义的，不是根据某些特定的数据表示和算法来定义。这样，不用重写最后的程序就能随意修改实现。例如，当前使用的AddItem()函数效率不高，因为它总是从链表第 1 个项开始，然后搜索至链表末尾。可以通过保存链表结尾处的地址来解决这个问题。例如，可以这样重新定义List类型：

typedef　struct　list

{

Node * head;　/* 指向链表的开头 */

Node * end;　 /* 指向链表的末尾 */

}　List;

当然，还要根据新的定义重写处理链表的函数，但是不用修改程序清单17.4中的内容。对大型编程项目而言，这种把实现和最终接口隔离的做法相当有用。这称为数据隐藏，因为对终端用户隐藏了数据表示的细节。

注意，这种特殊的ADT甚至不要求以链表的方式实现简单链表。下面是另一种方法：

#define　MAXSIZE　100

typedef　struct　list

{

Item entries[MAXSIZE]; /* 项数组 */

int items;　　　　　　　　 /* 其中的项数 */

}　List;

这样做也需要重写list.c文件，但是使用list的程序不用修改。

最后，考虑这种方法给程序开发过程带来了哪些好处。如果程序运行出现问题，可以把问题定位到具体的函数上。如果想用更好的方法来完成某个任务（如，添加项），只需重写相应的函数即可。如果需要新功能，可以添加一个新的函数。如果觉得数组或双向链表更好，可以重写实现的代码，不用修改使用实现的程序。

17.4 队列ADT

在C语言中使用抽象数据类型方法编程包含以下3个步骤。

1.以抽象、通用的方式描述一个类型，包括该类型的操作。

2.设计一个函数接口表示这个新类型。

3.编写具体代码实现这个接口。

前面已经把这种方法应用到简单链表中。现在，把这种方法应用于更复杂的数据类型：队列。

17.4.1 定义队列抽象数据类型

队列（queue）是具有两个特殊属性的链表。第一，新项只能添加到链表的末尾。从这方面看，队列与简单链表类似。第二，只能从链表的开头移除项。可以把队列想象成排队买票的人。你从队尾加入队列，买完票后从队首离开。队列是一种“先进先出”（first in,first out，缩写为FIFO）的数据形式，就像排队买票的队伍一样（前提是没有人插队）。接下来，我们建立一个非正式的抽象定义：

类型名：　　　　队列

类型属性：　　　可以储存一系列项

类型操作：　　　初始化队列为空

确定队列为空

确定队列已满

确定队列中的项数

在队列末尾添加项

在队列开头删除或恢复项

清空队列

17.4.2 定义一个接口

接口定义放在queue.h文件中。我们使用C的typedef工具创建两个类型名：Item和Queue。相应结构的具体实现应该是queue.h文件的一部分，但是从概念上来看，应该在实现阶段才设计结构。现在，只是假定已经定义了这些类型，着重考虑函数的原型。

首先，考虑初始化。这涉及改变Queue类型，所以该函数应该以Queue的地址作为参数：

void InitializeQueue (Queue * pq);

接下来，确定队列是否为空或已满的函数应返回真或假值。这里，假设C99的stdbool.h头文件可用。如果该文件不可用，可以使用int类型或自己定义bool类型。由于该函数不更改队列，所以接受Queue类型的参数。但是，传递Queue的地址更快，更节省内存，这取决于Queue类型的对象大小。这次我们尝试这种方法。这样做的好处是，所有的函数都以地址作为参数，而不像 List 示例那样。为了表明这些函数不更改队列，可以且应该使用const限定符：

bool QueueIsFull(const Queue * pq);

bool QueueIsEmpty (const Queue * pq);

指针pq指向Queue数据对象，不能通过pq这个代理更改数据。可以定义一个类似该函数的原型，返回队列的项数：

int QueueItemCount(const Queue * pq);

在队列末尾添加项涉及标识项和队列。这次要更改队列，所以有必要（而不是可选）使用指针。该函数的返回类型可以是void，或者通过返回值来表示是否成功添加项。我们采用后者：

bool EnQueue(Item item, Queue * pq);

最后，删除项有多种方法。如果把项定义为结构或一种基本类型，可以通过函数返回待删除的项。函数的参数可以是Queue类型或指向Queue的指针。因此，可能是下面这样的原型：

Item DeQueue(Queue q);

然而，下面的原型会更合适一些：

bool DeQueue(Item * pitem, Queue * pq);

从队列中待删除的项储存在pitem指针指向的位置，函数的返回值表明是否删除成功。

清空队列的函数所需的唯一参数是队列的地址，可以使用下面的函数原型：

void EmptyTheQueue(Queue * pq);

17.4.3 实现接口数据表示

第一步是确定在队列中使用何种C数据形式。有可能是数组。数组的优点是方便使用，而且向数组的末尾添加项很简单。问题是如何从队列的开头删除项。类比于排队买票的队列，从队列的开头删除一个项包括拷贝数组首元素的值和把数组剩余各项依次向前移动一个位置。编程实现这个过程很简单，但是会浪费大量的计算机时间（见图17.6）。

图17.6 用数组实现队列

第二种解决数组队列删除问题的方法是改变队列首端的位置，其余元素不动（见图17.7）。

图17.7 重新定义首元素

解决这种问题的一个好方法是，使队列成为环形。这意味着把数组的首尾相连，即数组的首元素紧跟在最后一个元素后面。这样，当到达数组末尾时，如果首元素空出，就可以把新添加的项储存到这些空出的元素中（见图17.8）。可以想象在一张条形的纸上画出数组，然后把数组的首尾粘起来形成一个环。当然，要做一些标记，以免尾端超过首端。

图17.8 环形队列

另一种方法是使用链表。使用链表的好处是删除首项时不必移动其余元素，只需重置头指针指向新的首元素即可。由于我们已经讨论过链表，所以采用这个方案。我们用一个整数队列开始测试：

typedef int Item;

链表由节点组成，所以，下一步是定义节点：

typedef　struct　node

{

Item　item;

struct node * next;

}　Node;

对队列而言，要保存首尾项，这可以使用指针来完成。另外，可以用一个计数器来记录队列中的项数。因此，该结构应由两个指针成员和一个int类型的成员构成：

typedef　struct　queue

{

Node * front; /* 指向队列首项的指针 */

Node * rear;　/*指向队列尾项的指针*/

int items;　　　　/* 队列中的项数*/

}　Queue;

注意，Queue是一个内含3个成员的结构，所以用指向队列的指针作为参数比直接用队列作为参数节约了时间和空间。

接下来，考虑队列的大小。对链表而言，其大小受限于可用的内存量，因此链表不要太大。例如，可能使用一个队列模拟飞机等待在机场着陆。如果等待的飞机数量太多，新到的飞机就应该改到其他机场降落。我们把队列的最大长度设置为10。程序清单17.6包含了队列接口的原型和定义。Item类型留给用户定义。使用该接口时，可以根据特定的程序插入合适的定义。

程序清单17.6 queue.h接口头文件

/* queue.h -- Queue的接口 */

#ifndef　_QUEUE_H_

#define　_QUEUE_H_

#include　<stdbool.h>

// 在这里插入Item类型的定义，例如

typedef int Item;　　　// 用于use_q.c

// 或者 typedef struct item {int gumption; int charisma;} Item;

#define　MAXQUEUE　10

typedef　struct　node

{

Item　item;

struct node * next;

}　Node;

typedef　struct　queue

{

Node * front;　/* 指向队列首项的指针　　*/

Node * rear;　/* 指向队列尾项的指针　　*/

int items;　　/* 队列中的项数　　　　 */

}　Queue;

/* 操作：　　　初始化队列　　　　　　　　　　　　　　　　　 */

/* 前提条件：　 pq 指向一个队列　　　　　　　　　　　　　　　 */

/* 后置条件：　队列被初始化为空　　　　　　　　　　　　　　　*/

void InitializeQueue(Queue * pq);

/* 操作：　　　检查队列是否已满　　　　　　　　　　　　　　　*/

/* 前提条件：　 pq 指向之前被初始化的队列　　　　　　　　　　　*/

/* 后置条件：　如果队列已满则返回true，否则返回false　　　　　*/

bool QueueIsFull(const Queue * pq);

/* 操作：　　　检查队列是否为空　　　　　　　　　　　　　　　*/

/* 前提条件：　 pq 指向之前被初始化的队列　　　　　　　　　　　*/

/* 后置条件：　如果队列为空则返回true，否则返回false　　　　　*/

bool QueueIsEmpty(const Queue *pq);

/* 操作：　　　确定队列中的项数　　　　　　　　　　　　　　　*/

/* 前提条件：　 pq 指向之前被初始化的队列　　　　　　　　　　　*/

/* 后置条件：　返回队列中的项数　　　　　　　　　　　　　　　*/

int QueueItemCount(const Queue * pq);

/* 操作：　　　在队列末尾添加项　　　　　　　　　　　　　　　*/

/* 前提条件：　 pq 指向之前被初始化的队列　　　　　　　　　　　*/

/*　　　　　　item是要被添加在队列末尾的项　　　　　　　　　 */

/* 后置条件：　如果队列不为空，item将被添加在队列的末尾，　　　　*/

/*　　　　　　该函数返回true；否则，队列不改变，该函数返回false*/

bool EnQueue(Item item, Queue * pq);

/* 操作：　　　从队列的开头删除项　　　　　　　　　　　　　　*/

/* 前提条件：　 pq 指向之前被初始化的队列　　　　　　　　　　　*/

/* 后置条件：　如果队列不为空，队列首端的item将被拷贝到*pitem中 */

/*　　　　　　并被删除，且函数返回true；　　　　　　　　　　 */

/*　　　　　　如果该操作使得队列为空，则重置队列为空　　　　　　*/

/*　　　　　　如果队列在操作前为空，该函数返回false　　　　　　*/

bool DeQueue(Item *pitem, Queue * pq);

/* 操作：　　　清空队列　　　　　　　　　　　　　　　　　　 */

/* 前提条件：　 pq 指向之前被初始化的队列　　　　　　　　　　　*/

/* 后置条件：　队列被清空　　　　　　　　　　　　　　　　　 */

void EmptyTheQueue(Queue * pq);

#endif

1.实现接口函数

接下来，我们编写接口代码。首先，初始化队列为空，这里“空”的意思是把指向队列首项和尾项的指针设置为NULL，并把项数（items成员）设置为0：

void InitializeQueue(Queue * pq)

{

pq->front　=　pq->rear　=　NULL;

pq->items　=　0;

}

这样，通过检查items的值可以很方便地了解到队列是否已满、是否为空和确定队列的项数：

bool QueueIsFull(const Queue * pq)

{

return　pq->items　==　MAXQUEUE;

}

bool QueueIsEmpty(const Queue * pq)

{

return　pq->items　==　0;

}

int QueueItemCount(const Queue * pq)

{

return　pq->items;

}

把项添加到队列中，包括以下几个步骤：

（1）创建一个新节点；

（2）把项拷贝到节点中；

（3）设置节点的next指针为NULL，表明该节点是最后一个节点；

（4）设置当前尾节点的next指针指向新节点，把新节点链接到队列中；

（5）把rear指针指向新节点，以便找到最后的节点；

（6）项数加1。

函数还要处理两种特殊情况。第一种情况，如果队列为空，应该把front指针设置为指向新节点。因为如果队列中只有一个节点，那么这个节点既是首节点也是尾节点。第二种情况是，如果函数不能为节点分配所需内存，则必须执行一些动作。因为大多数情况下我们都使用小型队列，这种情况很少发生，所以，如果程序运行的内存不足，我们只是通过函数终止程序。EnQueue()的代码如下：

bool EnQueue(Item item, Queue * pq)

{

Node * pnew;

if　(QueueIsFull(pq))

return　false;

pnew = (Node *)malloc( sizeof(Node));

if　(pnew　==　NULL)

{

fprintf(stderr,"Unable　to　allocate　memory!\n");

exit(1);

}

CopyToNode(item,　pnew);

pnew->next　=　NULL;

if　(QueueIsEmpty(pq))

pq->front = pnew;　　　/* 项位于队列首端　　　　*/

else

pq->rear->next = pnew; /* 链接到队列尾端　　　 */

pq->rear = pnew;　　　　　 /* 记录队列尾端的位置　　*/

pq->items++;　　　　　　　 /* 队列项数加1　　　　 */

return　true;

}

CopyToNode()函数是静态函数，用于把项拷贝到节点中：

static void CopyToNode(Item item, Node * pn)

{

pn->item　=　item;

}

从队列的首端删除项，涉及以下几个步骤：

（1）把项拷贝到给定的变量中；

（2）释放空出的节点使用的内存空间；

（3）重置首指针指向队列中的下一个项；

（4）如果删除最后一项，把首指针和尾指针都重置为NULL；

（5）项数减1。

下面的代码完成了这些步骤：

bool DeQueue(Item * pitem, Queue * pq)

{

Node * pt;

if　(QueueIsEmpty(pq))

return　false;

CopyToItem(pq->front,　pitem);

pt　=　pq->front;

pq->front　=　pq->front->next;

free(pt);

pq->items--;

if　(pq->items　==　0)

pq->rear　=　NULL;

return　true;

}

关于指针要注意两点。第一，删除最后一项时，代码中并未显式设置front指针为NULL，因为已经设置front指针指向被删除节点的next指针。如果该节点不是最后一个节点，那么它的next指针就为NULL。第二，代码使用临时指针（pt）储存待删除节点的位置。因为指向首节点的正式指针（pt->front）被重置为指向下一个节点，所以如果没有临时指针，程序就不知道该释放哪块内存。

我们使用DeQueue()函数清空队列。循环调用DeQueue()函数直到队列为空：

void EmptyTheQueue(Queue * pq)

{

Item　dummy;

while　(!QueueIsEmpty(pq))

DeQueue(&dummy,　pq);

}

注意保持纯正的ADT

定义ADT接口后，应该只使用接口函数处理数据类型。例如，Dequeue()依赖EnQueue()函数来正确设置指针和把rear节点的next指针设置为NULL。如果在一个使用ADT的程序中，决定直接操控队列的某些部分，有可能破坏接口包中函数之间的协作关系。

程序清单17.7演示了该接口中的所有函数，包括EnQueue()函数中用到的CopyToItem()函数。

程序清单17.7 queue.c实现文件

/* queue.c -- Queue类型的实现 */

#include　<stdio.h>

#include　<stdlib.h>

#include　"queue.h"

/* 局部函数 */

static void CopyToNode(Item item, Node * pn);

static void CopyToItem(Node * pn, Item * pi);

void InitializeQueue(Queue * pq)

{

pq->front　=　pq->rear　=　NULL;

pq->items　=　0;

}

bool QueueIsFull(const Queue * pq)

{

return　pq->items　==　MAXQUEUE;

}

bool QueueIsEmpty(const Queue * pq)

{

return　pq->items　==　0;

}

int QueueItemCount(const Queue * pq)

{

return　pq->items;

}

bool EnQueue(Item item, Queue * pq)

{

Node * pnew;

if　(QueueIsFull(pq))

return　false;

pnew = (Node *) malloc(sizeof(Node));

if　(pnew　==　NULL)

{

fprintf(stderr,　"Unable　to　allocate　memory!\n");

exit(1);

}

CopyToNode(item,　pnew);

pnew->next　=　NULL;

if　(QueueIsEmpty(pq))

pq->front = pnew;　　　　　/* 项位于队列的首端　　　*/

else

pq->rear->next = pnew;　　 /* 链接到队列的尾端　　　*/

pq->rear = pnew;　　　　　　　 /* 记录队列尾端的位置　　*/

pq->items++;　　　　　　　　　 /* 队列项数加1　　　　 */

return　true;

}

bool DeQueue(Item * pitem, Queue * pq)

{

Node * pt;

if　(QueueIsEmpty(pq))

return　false;

CopyToItem(pq->front,　pitem);

pt　=　pq->front;

pq->front　=　pq->front->next;

free(pt);

pq->items--;

if　(pq->items　==　0)

pq->rear　=　NULL;

return　true;

}

/* 清空队列 */

void EmptyTheQueue(Queue * pq)

{

Item　dummy;

while　(!QueueIsEmpty(pq))

DeQueue(&dummy,　pq);

}

/* 局部函数 */

static void CopyToNode(Item item, Node * pn)

{

pn->item　=　item;

}

static void CopyToItem(Node * pn, Item * pi)

{

*pi = pn->item;

}

17.4.4 测试队列

在重要程序中使用一个新的设计（如，队列包）之前，应该先测试该设计。测试的一种方法是，编写一个小程序。这样的程序称为驱动程序（driver），其唯一的用途是进行测试。例如，程序清单17.8使用一个添加和删除整数的队列。在运行该程序之前，要确保queue.h中包含下面这行代码：

typedef int item;

记住，还必须链接queue.c和use_q.c。

程序清单17.8 use_q.c程序

/* use_q.c -- 驱动程序测试 Queue 接口　*/

/* 与 queue.c 一起编译　　　　　　　　　　*/

#include　<stdio.h>

#include "queue.h"　/* 定义Queue、Item　 */

int　main(void)

{

Queue　line;

Item　temp;

char　ch;

InitializeQueue(&line);

puts("Testing　the　Queue　interface.　Type　a　to　add　a　value,");

puts("type　d　to　delete　a　value,　and　type　q　to　quit.");

while　((ch　=　getchar())　!=　'q')

{

if (ch != 'a' && ch != 'd')　/* 忽略其他输出 */

continue;

if　(ch　==　'a')

{

printf("Integer　to　add:　");

scanf("%d",　&temp);

if　(!QueueIsFull(&line))

{

printf("Putting　%d　into　queue\n",　temp);

EnQueue(temp,　&line);

}

else

puts("Queue　is　full!");

}

else

{

if　(QueueIsEmpty(&line))

puts("Nothing　to　delete!");

else

{

DeQueue(&temp,　&line);

printf("Removing　%d　from　queue\n",　temp);

}

printf("%d　items　in　queue\n",　QueueItemCount(&line));

puts("Type　a　to　add,　d　to　delete,　q　to　quit:");

}

EmptyTheQueue(&line);

puts("Bye!");

return　0;

}

下面是一个运行示例。除了这样测试，还应该测试当队列已满后，实现是否能正常运行。

Testing　the　Queue　interface.　Type　a　to　add　a　value,

type　d　to　delete　a　value,　and　type　q　to　quit.

Integer　to　add:　40

Putting　40　into　queue

1　items　in　queue