1.2 性表的实现

1.2.2 链式存储结构

　　采用链式存储结构存储的线性表就是链表，它具有如下两个特点：
　　① 数据元素的存储空间不一定连续。线性表的链式存储使用一组任意的存储单元来存储线性表的数据元素，不同数据元素的存储单元之间可以是连续的，也可以是不连续的。因此，线性表中的元素与其直接前驱和直接后继之间仅存在逻辑上的先后次序，在物理存储上并无前后关联。
　　② 采用结点存储数据元素。在顺序表中，元素的寻址可以通过数组来实现，但是链表中由于逻辑上相关联的元素的物理地址之间没有直接关联，因此，每个存储单元除了存储数据元素本身的信息外，还必须额外存储与其相关联的元素的物理地址，一般称前者为数据域，后者为指针域。指针域中存储的信息又称为指针或链，这个包含了数据域和指针域的存储单元就称为（链表的）结点，链表中每个结点都唯一对应了线性表中的一个元素。
　　指针域中既可以只记载一个关联结点的地址（例如，单链表中只记载了直接后继结点的地址），也可以记载多个关联结点的地址（例如，双向链表中同时记载了直接前驱结点和直接后继结点的地址）。例如，图1-5（a）描述单链表的结点，图1-5（b）描述单链表表示的线性表（Dat1，Dat2，Dat3，Dat4，Dat5）。

　　从图1-5（b）中可以看出，在链式存储结构的线性表中，第一个数据元素的存储地址称为该线性表的基地址（又称为头指针），线性表的其他元素都是通过头指针出发选择到的。例如，图1-5（b）中，头指针的值为第一个元素的存储位置，即头指针指向第一个结点；第一个结点的指针域的值为第二个元素的存储位置，即指向第二个结点；第二个结点的指针域又指向第三个结点，以此类推，直到线性表尾元素Data5，其后再无后继元素，故置该结点的指针域取值为NULL（空）。取值为NULL的指针称为空指针，在图中通常采用“Λ”符号表示。
　　如果结点的指针域只存储了其直接后继结点的地址，则称这个链表为线性链表或单链表。线性链表的逻辑示意如图1-6所示，其中图1-6（a）和图1-6（b）描述了线性表（A1，A2，A3，…，An），图1-6（c）描述了一个空线性表。

　　1．线性链表存储结构的定义
　　在高级语言中，通常使用结构体来描述结点，使用指向结构体的指针来描述指针域。下面是一个定义数据元素类型为Elemtype的链式存储线性表的例子：
　　
　　由于线性链表中各结点的存储地址不连续，并且相互之间无直接关联。因此，只有在拥有了数据元素的存储地址（即指向元素结点的指针后），才可以访问线性链表的元素。同理，在获取了线性链表的头指针后，就可以遍历整个线性链表。
　　2．线性链表的操作
　　假设线性链表的头指针为L，有：
　　
　　（1）初始化算法
　　初始化算法是链表分配内存空间，代码如下：
　　
　　（2）获取线性链表表长算法
　　除非在头结点的数据域同步存储线性表的表长，否则，只能通过遍历获取线性链表的长度，遍历代码如下所示（不带头结点的线性链表）：
　　
　　（3）空链表判断
　　当头结点的指针域取值为空时，链表为空：
　　
　　（4）获取元素取值算法
　　首先找到元素存储空间的地址，再读取其数据域即可。线性链表不能随机查找，它必须从头指针开始遍历i次，才能获取第i个元素的存储地址。以下代码读取不带头结点的单链表中第i个元素的取值：

　　（5）插入元素算法
　　在顺序表中，数据元素的前驱后继关系通过元素的存储位置确定，而在线性链表中数据元素的逻辑次序与其存储空间的地址无关，而是通过指针来决定的。因此，线性链表的插入操作不需要移动元素，但是必须修改结点的指针域。
　　1）不带头结点的线性链表的表头插入算法。
　　不带头结点的线性链表的表头插入步骤如下：
　　① 线性链表的初始状态如图1-7（a）所示。
　　② 申请一个结点的存储空间，设地址为s，数据域取值为A1，指针域取值为空，如图1-7（b）所示。
　　③ 将结点s的直接后继设置为原线性链表的第一个元素，设置结点s的指针域为该元素的存储地址，而此地址恰好就是头指针L的取值，即s->next = L，如图1-7（c）所示。
　　④ 将头指针L指向结点s，即L = s，如图1-7（d）所示。

　　综上所述，不带头结点的线性链表的表头插入算法为：
　　
　　2）带头结点的线性链表的表头插入算法。
　　带头结点的线性链表的表头插入步骤如下：
　　① 线性链表的初始状态如图1-8（a）所示。
　　② 申请一个结点的存储空间，设地址为s，并赋该结点数据域取值为A1、指针域取值为空，如图1-8（b）所示。
　　③ 将结点s的直接后继设置为原线性链表第一个元素，由于头结点的地址域(L->next)就记载了这个元素的存储地址，即s->next = L->next，如图1-8（c）所示。
　　④ 将头结点的地址域指向新插入的结点地址，即L->next = s，如图1-8（d）所示。
　　综上所述，带头结点的线性链表的表头插入算法为：
　　

　　3）带头结点的线性链表插入算法。