预计阅读本页时间：-
理想情况下，您会希望可以不确定地添加数据（或者不断添加数据，直到程序内存用完为止），而不用事先指定您会输入多少项目，也不用让程序分配不必要的大块内存。这一点可以通过在输入每个项目之后调用malloc（）分配大小合适的空间以保存新的数据项来做到。如果用户输入3部电影，程序就调用malloc（）函数3次。如果用户输入300部电影，程序就调用malloc（）函数300次。
这个不错的主意导致了一个新问题。为了发现这个问题是什么，试比较这两种情况：调用malloc（）函数1次、请求保存300个film结构的空间，和调用malloc（）函数300次、每次请求保存1个film结构的空间。第一种情况将分配一个连续的内存块，用以跟踪这些内容的只是一个指向struct film的指针变量，它指向块中第一个结构。通过使用简单的数组符号允许这个指针访问块中的每一个结构，如前面代码段所示。第二种方法的问题是不能保证连续的malloc（）调用产生相邻的内存块。这意味着这些结构不一定会被连续存储（请参见图17.1）。因此，需要存储300个指针，其中每个指针指向一个独立存储的结构；而不是存储一个指向有300个结构的块的指针。
广告：个人专属 VPN，独立 IP，无限流量，多机房切换，还可以屏蔽广告和恶意软件，每月最低仅 5 美元
图17.1 按块分配结构空间和个别地分配结构空间
一种解决方法是创建一个大的指针数组，并在分配新的结构时逐个地对这些指针赋值，但我们不打算使用这种方法：
如果用户输入的项目个数小于500个，这种方法将节省大量内存，因为500个指针的数组比500个结构的数组占用少得多的内存。但是，无用指针占用的空间仍然会被浪费掉，并且仍然有500个结构的限制。
有一种更好的方法。每次使用malloc（）为新结构分配空间时，也为新指针分配空间。您会说：“但是，然后我就需要另一个指针来跟踪新分配的指针，同时它本身也要一个指针来跟踪，依此类推。”避免这个潜在问题的方法是重新定义结构，使得每个结构包含一个指向下一个结构的指针。然后，每次创建新的结构时，就可以在前一个结构中存储它的地址。简而言之，需要这样来重新定义film结构：
是的，结构本身不能含有同类型的结构，但是它可以含有指向同类型结构的指针。这样的定义是定义一个链表（linked list）的基础。链表是一个列表，其中的每一项都包含描述何处能找到下一项的信息。
在给出使用链表的C代码之前，让我们先从概念上理解一个链表实例。假设用户输入片名为Modem Times、等级为10的一部电影。程序将为一个film结构分配空间，将Modern Times字符串复制到title成员中，并将rating成员设置为10。为了说明这个结构后面没有别的结构，程序将把next成员指针设为NULL（回忆一下，NULL是在stdio.h文件中定义的符号常量，代表空指针）。显然，需要跟踪第一个结构存储在哪里，可以将其地址赋给一个独立的称为头指针（head pointer）的指针。头指针指向数据项链表中的第一项。图17.2示意了这种结构（为了节省图中空间，对title成员中的空白部分进行了压缩）。
现在假设用户输入第二部电影及其等级，例如Titanic和8。程序为第二个film结构分配空间，并在第一个结构的next成员中存储这个新结构的地址（覆盖先前存储于此的NULL），使得结构的next指针指向链表中的下一个结构。然后程序将Titanic和8复制到新的结构中，并将它的next成员设为NULL，表示当前它是链表中的最后一个结构。图17.3显示了含有两个项目的链表。
图17.2 链表中的第一项
图17.3 含有两个项目的链表
每一部新电影都以同样的方式处理。其地址将被存储在前一个结构中，新信息存储在新的结构中，其next成员设为NULL，从而建立起如图17.4所示的链表。
图17.4 含有多个项目的链表
假设您想显示链表。每显示一个项目，您可以使用存储在相应结构中的地址定位要显示的下一项目。但是，要使这个方案能够工作，还需要一个指针来存储链表中第一个项目的地址，因为链表中没有一个项目存储第一个项目的地址。幸运的是，您已经用头指针完成了这个任务。
17.2.1 使用链表
现在您已从概念上理解了链表的工作原理，让我们来实现它。程序清单17.2修改了程序清单17.1，这样，使用一个链表而不是数组来存放电影信息。
程序清单 17.2 films2.c程序
程序用链表执行两个任务。第一，构造列表并用输入的数据填充。第二，显示列表。显示列表的任务相对简单，所以我们先讨论它。
一、显示列表
显示列表的方法是开始时把一个指针（名为current）设置为指向第一个结构。因为头指针（名为head）已经指向那里，所以下面这行代码可以完成这个任务：
然后可以使用指针符号访问结构的成员：
下一步是重设current指针以指向列表中的下一个结构。这个信息存储在结构的next成员中，所以下面这行代码可以完成这个任务：
完成这些之后，重复整个过程。显示列表中最后一项之后，current将被设为NULL，因为这是最后一个结构的next成员的值。可以用这个事实来终止显示过程。下面是films2.c中用来显示列表的完整代码：
为什么不是使用head来遍历整个列表，而是创建一个新指针current?因为使用head会改变head的值，这样程序将不再能找到列表的开始处。
二、创建列表
创建列表包括三步：
1．使用malloc（）函数为一个结构分配足够的空间。
2．存储这个结构的地址。
3．把正确的信息复制到这个结构中。
如果不需要，就不应该创建结构，所以程序使用临时存储（input数组）来获取用户输入的片名。如果用户从键盘模拟了EOF，或者输入了空行，输入循环就会退出：
如果有输入，程序就为一个结构请求存储空间，并将其地址赋给指针变量current：
第一个结构的地址必须保存在指针变量head中，后续每一个结构的地址都必须保存在前一个结构的next成员中。因此，程序需要知道是否在处理第一个结构。一种简单的方法是在程序开始时将head指针初始化为NULL。然后程序可以使用head的值来决定该如何做。
在这段代码中，prev是指向前一个分配的结构的指针。
接下来，需要为结构成员设置合适的值。具体地，应将next成员设为NULL来表示当前结构是列表中的最后一个，将片名从input数组复制到title成员，并且要为rating成员获取一个值。下面的代码完成这些任务：
最后，需要让程序准备接受下一轮输入。具体地，需要将prev设置为指向当前结构，因为在键入下一个片名和分配下一个结构之后，当前结构将成为前一个结构。程序在循环的结尾处设置这个指针：
程序能正常工作吗？下面是一个运行示例：
三、清理列表
程序在终止时会自动释放由malloc（）分配的内存，但最好是养成调用free（）来释放由malloc（）分配的内存的习惯。因此，程序通过对每一个已分配的结构应用free（）函数来清理其内存：
17.2.2 反思
films2.c程序有一些不足。比如，它没有检查malloc（）是否找到需要的内存，并且它不提供删除列表中的项目的功能。但是这些不足是可以解决的。比如，可以添加检查malloc（）的返回值是否为NULL（返回NULL表示它无法获得所需内存）的代码。如果需要程序删除项目，需要编写更多代码来实现。
这种用特定方法解决特定问题，并在需要时添加功能的编程方式通常不是最好的。另一方面，通常无法预料到程序要完成的所有任务。随着程序编制工程规模的扩大，一个程序员或一个编程团队事先做好一切计划的模式显得越来越不现实。可以看到很成功的大型程序往往是由一些成功的小型程序一步步发展而来的。
如果稍后需要修改计划，那么以简化修改过程的方式开发最初的设想是个好主意。程序清单17.2中的示例程序没有遵循这个原则。具体地，它把编码细节和概念模型混合在一起。比如，在示例程序中，概念模型是向一个列表中添加项目。但程序将诸如malloc（）和current->next之类的代码置于显著位置，因而模糊了这个接口。更好的方法是：明确地表明您在向一个列表中添加项目，并隐藏那些细节性的动作，比如调用内存管理函数和设置指针等。将细节和用户接口分开将使程序更易理解和升级。通过开始编程时就使用新的方法，您可以实现这些目标。让我们看看应该如何去做。
