2.3.1　线性表的链式存储结构——链表

链表是用一组任意的存储单元来存放线性表的结点，这组存储单元可以是连续的，也可以是非连续的，甚至是零散分布在内存的任何位置上。因此，链表中结点的逻辑次序和物理次序不一定相同。为了正确地表示结点间的逻辑关系，必须在存储线性表的每个数据元素值的同时，存储指示其后继结点的地址（或位置）信息，这两部分信息组成的存储映像叫作结点（node）。它包括两个域，其中存储数据元素信息的域称为数据域；存储直接后继位置信息的域称为指针域，如图2－5所示。

图2－5 单链表结点结构

N个结点链接成一个链表，即为线性表的链式存储结构，又由于此链表的每个结点中只包含一个指针域，故又称线性链表或单链表。

整个链表的存取必须从头开始，我们把链接中第一个结点的存储位置叫作头指针。同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为“空”（NULL）。如图2－6所示，头指针指向地址31，即地址31里的数据“ZHAO”是第一个结点，“WANG”是最后一个结点，指针域是空。

用线性链表表示线性表时，数据元素之间的逻辑关系是由结点的指针指示的。换句话说，指针为数据元素之间逻辑关系的映像，因此逻辑上相邻的两个数据元素其存储的物理位置不要求相邻，由此，这种存储结构为非顺序映像或链式映像。

通常我们把链表画成用箭头相链接的结点的序列，结点之间的箭头表示链域中的指针。如图2－6的线性链表可画成如图2－7所示的形式，这是因为在使用链表时，关心的只是它所表示的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置。

图2－6 线性链表示例

图2－7 线性链表的逻辑状态

有时，为了更加方便地对链表进行操作，会在单链表第一个结点前加一个结点，称为头结点。头结点的数据域一般不存储任何信息，有时存储线性表长度等附加信息，如图2－8所示。

图2－8 头结点和头指针

头结点和头指针的比较如表2－2所示。

表2－2 头结点和头指针的比较

由上述可见，单链表可由头指针唯一确定，在C语言中可用“结构指针”来描述，线性表的结点可用结构来描述，如下所示：

假设L是LinkList型的变量，则L为单链表的头指针，它指向表中第一个结点。若L为“空”（L＝NULL），则所表示的线性表为“空”表，其长度n为“零”。如图2－9（a）所示，此时，单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为“空”，如图2－9（b）所示。

图2－9 带头结点的单链表