什么是C语言链表？C语言链表的概念

前面讲到的数组是 C语言中按顺序管理大量数据的一种方法，数组的元素都是按顺序存放在内存的一块连续空间中的（见图 1a) ）。数组在定义时需要说明数组的大小，这样一来，如果数组定义大了，就会有大量空闲存储单元，定义小了，又会在运行中发生数组下标越界的错误，这是静态存储分配的局限性。

利用定义为指向结构体类型的指针，可以构造简单而实用的动态存储分配结构——链表结构。链表也是 C语言中按顺序管理大量数据的一种方法，但它与数据在内存中的存放位置无关，即不需要按顺序存放在连续的内存空间中。链表的一个结点（数据元素，相当于数组中的数组元素）可以单独存放在内存的任意位置，并用指针来连接这些在内存中不连续的数据并管理这些数据的顺序（见图 1b) ）。

图 1：数组和链表在内存中的不同存储方式

1. 单链表

可以用如下代码所示构造一个单向链表结构（见图 2b) ）：

struct node{
    int data;
    struct node *next;    //该成员被定义为指向结构体自身类型的指针
}*head,*p,*q;

链表中的一个结点元素就是一个结构体对象，而且其中总有一个结构体对象成员被定义为指向该结构体类型的一个指针（如*next）。在单向链表中，这个指针指向下一个结点，被称为结点的后继指针。

如图 2a) 所示，单向链表的结点由两部分组成：其中一部分专门用来存储其后继指针，称为指针域；另一部分用于存储其他数据（该结构体对象的其他成员），称为数值域。

图 2：单向链表结构

链表的长度（结点的多少）是有弹性的，其最后一个结点的后续指针指向为 NULL 即表示到达链表的尾部，无须像数组一样事先指定大小。但是 C语言中，所有的数据必须存储在指定大小的内存空间中，所以，我们在建立链表时，每新增一个结点，就用 C语言提供的内存分配函数malloc(size)向系统申请一块内存空间用于存储该结点数据。同样地，在删除一个结点以后，也用函数free(指针名)释放它所占用的内存空间。因而，我们把链表结构称为是一种动态存储分配结构。

malloc(size)和free(指针名)都存放在malloc.h中，因此在调用时，要在程序开始加上#include <malloc.h>。

函数malloc(size)向系统申请 size 字节的连续内存空间，如果申请成功则返回连续空间起始地址的指针。通常用函数 sizeof(x) 来确定 size 的大小，其中的 x 是一个变量名或类型名，该函数返回的是 x 变量或类型在内存中占用空间的大小。例如sizeof(int)返回的就是一个 int 类型的数据所占字节的大小。

因此，可以如下面代码所示在定义一个链表结点后，用函数malloc(size)为它申请相应大小的内存空间：

struct node *head;
head = malloc(sizeof(struct node));

而free(head);则可以释放指针 head 指向的结点所占用的内存空间。

2. 其他链表结构

在单向链表中，表尾结点的后继指针指向为 NULL（空）。如果让表尾结点的后继指针指向表头结点，就形成了单向环形链表，简称单链环（见图 3a) ）。

在单向链表中，每个结点只有一个指向后继结点的指针域。如果给每个结点再增加一个指向其前面一个结点（前驱结点）的指针域，那么这种链表称为双向链表（见图 3b) ）。可以用如下所示代码构造双向链表：

struct node{
    int data;
    struct node *next,*prev;
};

与单链环类似，如图 3c) 所示的链表结构称为双向链环。

图 3：其他链表结构

3. 总结

1. 链表中的一个结点元素就是一个结构体对象；
2. 链表利用指针连接内存中非连续存放的数据并管理这些数据的顺序；
3. 单向链表的结点由数据和指向下一个结点的指针（后继结点）构成。