从数组到链表（C Primer Plus 第六版）

一、从数组到链表

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

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

书里面这段话写的太好了，我全加粗了！

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

#define TSIZE 45    //储存片名的数组大小
struct film {
char title [ TSIZE];
int rating;
struct film * next;
};

1.1 重要的一个点

虽然结构不能含有与本身类型相同的结构，但是可以含有指向同类型结构的指针。这种定义是定义链表( linked list）的基础，链表中的每一项都包含着在何处能找到下一项的信息。 在学习链表的代码之前，我们先从概念上理解一个链表。假设用户输入的片名是Modern Times，等级为10。程序将为film类型的结构分配空间，把字符串 Modern Times拷贝到结构中的title成员中，然后设置rating成员为10。为了表明该结构后面没有其他结构,程序要把next成员指针设置为NULL(NULL是一个定义在stdio.h头文件中的符号常量，表示空指针)。当然，还需要一个**单独的指针储存第1个结构的地址，该指针被称为头指针( head pointer)。头指针指向链表中的第1项。**图17.2演示了这种结构（为节约图片空间，压缩了title成员中的空白)。

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

书上的介绍写的太好了！

每加入一部新电影，就以相同的方式来处理。新结构的地址将储存在上-一个结构中，新信息储存在新结构中，而且新结构中的next成员设置为NULL

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

二、使用链表

我们用代码来实现一个链表！

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TSIZE 45
struct film
{
    char title[TSIZE];
    int rating;
    struct film *next; //指向链表中的下一个结构
};
char *s_gets(char *st, int n); //函数返回值为char类型的指针
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)
            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)
            *find = '\0';
        else
            while (getchar() != '\n')
                continue;
    }
    return ret_val;c
}
输出结果为：
PS D:\Code\C\结构> cd "d:\Code\C\结构\" ; if ($?) { gcc 链表Demo01.c -o 链表Demo01 } ; if ($?) { .\链表Demo01 }
Enter first movie title:
Roman Holiday
Enter your rating <0-10>:
8 
Enter next movie title (empty line to stop)
Rose
Enter your rating <0-10>:
2
Enter next movie title (empty line to stop)
Here is the movie list:
Movie: Roman Holiday Rating: 8
Movie: Rose Rating: 2

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

2.1 程序解析

2.1.1显示链表

由于书上的写的太好了，我直接照抄下来给大家参考！

显示列表从设置一个指向结构的指针开始（名为current）。由于头指针（head）已经指向链表中的第一个结构，所以可以这样表示

current = head；

然后用前面章节讲的指针表示法访问结构体中的成员

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

打印之后，在把current指针指向下一个结构

current = current->next ;

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

while (current != NULL)
    {
        //指针访问结构中的成员可以用指针.成员即可
        printf ("Movie: %s Rating: %d\n",current->title,current -> rating);
        current = current->next ;
    }

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

2.1.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 ( "%di",&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  :

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!

2.1.3释放链表

在许多环境中，程序结束时都会自动释放malloc ()分配的内存。但是,最好还是成对调用malloc() 和free()。因此，程序在清理内存时为每个已分配的结构都调用了free()函数: current = head; while (current != NULL) { current = head; head = current->next; free (current) ;

}