10.1.2　单向链表

单向链表由称为结点的数据项构成。数据项通常是由包含数据成员和链指针成员的结构型数据组成，链指针用来指向后继结点（即存放指向结点的地址）。单向链表的最后一个结点的链指针定义为空（用NULL或'\0'表示），表示链表结束。另外还需要一个头指针head，始终指向链表的起始结点，以便于对链表的操作。单向链表的结构如图10.1.1所示。

图10.1.1　单向链表结构

为建立一个单向链表，需要先定义一个存放数据和链指针的结构。例如：

该定义使链表的每个结点是struct slist结构类型的一个变量。next是指向struct slist结构类型的链指针。如前所述，这种在结构成员中包含有指向该结构本身的指针的结构类型称为引用自身的结构，

如果定义head是指向链表头的指针变量，定义p和q是指向链表中相邻结点的指针变量。按结构成员的引用方法，可以对两个结点的数据成员和指针成员赋值。如下面的程序段：

　　struct slist^*head，^*p，^*q；

　　head=p；

　　p−〉info=20；

　　p−〉next=q；

　　q−〉info=50；

　　q−〉next='\0'；

经赋值后，构成如图10.1.2所示的一个简单链表。

图10.1.2　包含两个结点的简单链表

链表是由链指针链接的一种动态数据结构，而用数组这种顺序存储结构实现的线性表称为静态数据结构。静态数据结构的顺序表最主要的缺点是，当数组的元素个数不确定时，必须以可能的最多元素个数确定数组的大小。在程序中，当数组元素个数发生变化时，常常会浪费存储空间，当数组元素个数超出时又可能产生溢出。对于动态数据结构而言，程序在执行前可以不确定处理数据项总共所需要的存储空间的大小。程序运行时可以动态地向链表中加入任意个数的结点（只要系统能提供足够的存储空间）。如果不向链表加入结点，则不需要占用存储空间。

为了把一个数据项放入链表，必须向系统申请存储该数据项的存储空间。在删除链表中的一个数据项后必须释放存储空间，以便系统再使用。C语言提供了标准库函数malloc（）和free（）实现这两项功能，有关这两个函数的详细内容请阅读7.7节。

在单向链表中插入一个结点要引起插入位置前面结点的链指针的变化，图10.1.3说明插入一个结点的情况。

下面的程序段实现了在图10.1.3的单向链表中，在p和q指针所指向的结点间插入一个数据为30的新结点。

图10.1.3　在单向链表中插入一个结点

　　struct slist^*np；

　　np=（struct slist^*）malloc（sizeof（struct slist））；

　　np−〉info=30；

　　np−〉next=p−〉next；

　　p−〉next=np；

在插入一个结点时首先定义一个指向struct slist类型的指针变量np；调用函数malloc（sizeof（struct slist））是向系统申请一个存放struct slist结构类型变量的存储空间，函数返回指向分配的存储区间起始地址的指针，并通过强制类型转换，将返回指针指向的数据类型转换成struct slist结构类型（使用（struct slist^*）实现）。通过指针赋值，使np指向新的结点。赋值语句“np−〉info=30；”为新结点的数据成员赋值。赋值语句“np−〉next=p−〉next；”或“np−〉next=q；”把插入位置后面一个结点的指针赋给该结点的链指针成员。赋值语句“p−〉next=np；”把指向新插入结点的指针赋给其前一个结点的链指针。通过上述步骤完成了新结点插入两个结点之间的操作。必须指出新结点也可以插在链表头和链表尾，这两种情况请读者考虑。

在单向链表中删除一个结点同样要引起被删除结点的前面结点的链指针的变化。图10.1.4说明了从单向链表中删除一个结点的情况。

下面的程序段将删除指针p指向的结点的后面一个结点：

　　struct slist^*temp；

　　temp=p−〉next；

　　p−〉next=p−〉next−〉next；

　　free（temp）；

在检索到被删除的结点后（p指针指向被删除结点的前一个结点），将指向该结点的链指针p−〉next保存在一个同类型的指针变量temp中，然后将该链指针改变为指向被删结点之后的一个结点，最后调用free（temp）函数，将temp指向的被删除结点占用的存储空间释放给系统。对于处于链表头和链表尾结点的删除操作，请读者思考。

图10.1.4　在单向链表中删除一个结点

由于链表是一个动态的数据结构，链表的各个结点由指针连接，访问链表数据项时，可通过每个结点的链指针逐个找到该结点的下一个结点，一直可以找到链表尾，链表的最后一个结点的链指针为NULL。下面是一个遍历链表的函数：