04-使用链表

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)
     {
          head = current->next;
          free(current);        
          current = head;
     }
     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>:
9
Enter next movie title (empty line to stop):
The Duelists
Enter your rating <0-10>:
8
Enter next movie title (empty line to stop):
Devil Dog: The Mound of Hound
Enter your rating <0-10>:
1
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)
{
     head = current->next;
     free(current);
     current = head;
}