2.4 性表的链式存储结构★2◎3

　　2.4 线性表的链式存储结构★2◎3

　　采用链式存储结构的线性表，其数据元素不要求存储在一段连续的存储单元上，相邻的两个元素在存储位置上也不要求相邻。
　　1．线性表链式存储结构表示
　　链式线性表的存储单元可以是连续的，也可以是不连续的。为了能够准确地寻找到线性表的前驱和后继，每个存储单元中需要增加存储其直接后继（或直接前驱）的物理位置。因此，链式线性表的存储单元由两部分组成：存储数据元素信息的“数据域”和存储直接后继（前驱）位置的“指针域”，而链式线性表的存储单元被称为“结点”。
　　如果线性表的指针域中只包含了其直接后继的存储位置信息，则称这个链表为“线性链表”或“单链表”。
　　在高级语言中，通常使用结构来描述结点，使用指向结构的指针来描述指针域，如下定义了一个数据元素类型为Elemtype的链式存储线性表。
　　
　　指向线性链表第一个结点的指针称为头指针，如图2-5（a）所示，L是LinkList类型变量，也是该单链表的头指针，通过L可以遍历整个单链表。
　　当线性链表为空时，链表中没有任何结点，自然也不存在所谓的“第1个结点”，此时头指针L取值也必须为空，即“L＝NULL”。
　　由于使用头指针描述线性链表必须区分链表空和非空两种情况，这使得线性链表的插入和删除算法变得复杂，因此，人们常常在第1个结点之前再增加一个结点，它的指针域指向线性链表的第1个结点，我们把这个新增的结点称为“头结点”，并定义L为指向头结点的指针，如图2-5（b）所示为非空带头结点单链表示意图，如图2-5（c）为带头结点空单链表示意图。
　　在无头结点线性表中，头指针L可以为“NULL”，但是在带头结点的线性链表中，头指针L绝对不能为“NULL”，因此头结点通过浪费一个“数据域”的存储单元（如图2-5中的黑色部分），换来了头指针不为空的保证，其好处读者可以在线性链表的操作中慢慢体会。
　　2．线性表链式存储结构寻址算法
　　由于链式链表的存储位置并不固定在一起，因此只有在拥有了指向链表结点的指针后，才可以访问链式链表中的数据元素和遍历线性表。假设p是指向线性表中第i个结点的指针，那么：
　　第i个数据元素的数据域为：p->data；。
　　指向第i+1个数据元素的指针为：p->next；。
　　第i+1个数据元素的数据域为：p->next->data（假设链表存在第i+1个数据元素）；。
　　以下代码读取不带头结点的单链表中第i个元素（从1开始计数）的取值：

　　
　　若是带头结点的单链表，则L为指向单链表头结点的指针，确保不为NULL，此时只需将以上代码的遍历代码中赋初值语句更改为如下代码行即可：
　　
　　3．线性表链式存储结构插入算法
　　已知p为指向单链表中某一个结点的指针（假设p不为空），在该结点后插入新结点的过程分为三个步骤：
　　①分配新结点空间，定义s为指向该结点的指针，并将s所指向结点的数据域赋初始值，如图 2-6（a）所示。
　　②定义s所指结点的后继结点为p所指向结点的后继结点，即“s->next = p->next”，如图2-6（b）所示。
　　③定义p所指向结点的后继结点为s所指向的结点，即“p->next = s”，如图2-6（c）所示。

　　以下代码为在带头结点的单链表的第i个元素（从1开始计数）前插入数据元素E：
　　
　　从上述代码可以看出，链式线性表的插入过程只需要更改指针域的取值，不需要移动数据。
　　
　　4．线性表链式存储结构删除算法
　　已知s为指向单链表中某一个结点的指针（假设s不为空），删除该结点后的过程分为两步，其中p是指向待删除结点的前驱结点的指针：
　　（1）定义p所指向结点的后继结点为s所指向结点的后继结点，如图2-7所示。
　　（2）释放s所指向的存储空间。

　　以下为删除带头结点的单链表中的第i个元素（从1开始计数）的代码：
　　
　　从上述代码可以看出，链式线性表的删除只需要更改指针域的取值，不需要移动数据。
　　5．线性表链式存储结构的特点
　　链式结构线性表的特点有：
　　（1）不需要一次性分配所需的存储空间，而是在执行插入操作时申请存储空间，在执行删除操作时释放存储空间，从而只要存储空间足够，没有最大数据元素数的限制。
　　（2）插入和删除操作都不需要移动数据元素。
　　（3）不支持随机查找，每次查找都必须从头遍历整个链表。
　　（4）增加了指针域，在一定程度上加大了存储空间的开销，降低了存储密度。
　　因此，链式结构线性表适用于数据元素总数不固定，插入和删除操作频繁的应用。