8.链表(八)

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

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

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

1. 单链表

可以用如下代码所示构造一个单向链表结构：

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

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

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

单向链表结构

链表的长度（结点的多少）是有弹性的，其最后一个结点的后续指针指向为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（空）。如果让表尾结点的后继指针指向表头结点，就形成了单向环形链表，简称单链环。

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

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

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

其他链表结构

3. 总结

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

了解了单链表的概念，接着我们就使用C语言来创建一个单链表。读入整数 n，建立一个单向链表，按顺序存储自然数 1 至 n。

该问题中，用于定义链表结点的结构体类型声明如下：

struct node{    
    int data;    //表示自然数1~n    
    struct node *next;    //定义链表后继指针
};

一个单向链表必然会有表头和表尾，因而定义两个结点指针 head 和 q，分别指向表头结点和表尾结点。初始链表只有一个结点（即是表头又是表尾）。在创建初始链表时，首先要给链表结点申请相应大小的内存空间，并给代表结点的结构体对象成员赋初值：

struct node *head, *q;
head = malloc(sizeof(struct node));    //为链表结点申请内存空间
head->data = 1;    //初始结点成员初始化赋值
head->next = NULL;

初始链表的表头和表尾是同一结点，所以 q=head。

为了向链表中添加新的结点，我们定义一个指向当前结点的指针 new：

struct node *new;

同样地，要为它申请相应的内存空间，并把当前要存储的自然数 i 赋值给 new->data，即new->data=i;。把这个新结点 new 连接到初始链表的表尾，即q->next=new;，这样结点 new 成为了链表表尾，所以要把 new 的后续结点指向 NULL，同时将表尾结点指针 q 指向结点 new。

new = malloc(sizeof(struct node));    //申请内存空间
q->next = new;    //加入新结点
new->data = i;    //给数值域内的成员赋值
new->next = NULL;    //后继指针指向为空
q = new;    //设置为表尾结点

以上代码通过 for 循环执行 n-1 次，就可以将自然数 2 至 n 存储到链表中。

打印输出链表时，我们可以用当前指针 q 从表头结点 head 开始顺序遍历整个链表，直至其后继指针为空：

for(q=head; q!=NULL; q=q->next){
    printf("%d",q->data);
}

C语言代码清单 1：创建一个单向链表，按顺序存储自然数 1 至 n

#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
struct node{
    int d;
    struct node *next;
};
struct node *head, *p, *q;
int main( )
{
    int i,n;
    printf("请输入一个正整数n：");
    scanf("%d",&n);
    head = malloc(sizeof(struct node));   //创建初始链表
    head->d = 1;
    head->next = NULL;
    q = head;     //初始链表表头就是表尾
    for(i=2; i<=n; i++){
        p = malloc(sizeof(struct node));  //申请内存空间
        q->next = p;    //加入新结点
        p->d = i;
        p->next = NULL;
        q = p;     //q指向表尾结点
    }
    for(p=head; p!=NULL; p=p->next){
        printf("%d ",p->d);
    }
    printf("\n");
    system("pause");
    return 0;
}

运行结果为：

请输入一个正整数n：8 1 2 3 4 5 6 7 8

邮箱：charon.chui@gmail.com
Good Luck!