1-2 链式表示的线性表之一——单链表
【定义】
所谓线性表的链式存储，是采用一组任意的存储单元存放线性表的元素。这组存储单元可以是连续的，也可以是不连续的。为了表示每个元素ai与其直接后继ai+1的逻辑关系，除了存储元素本身的信息外，还需要存储一个指示其直接后继元素的信息（直接后继元素的地址）。这两部分构成的存储结构称为结点（node）。即结点包括两个域：数据域和指针域。结点结构如图1.9所示。
图1.9 结点结构
通过指针域将线性表中n个结点元素按照逻辑顺序链在一起就构成了链表。
一般情况下，我们只关心链表中结点的逻辑顺序，而不关心它的实际存储位置。通常用箭头表示指针，把链表表示成通过箭头链接起来的序列。线性表（Hou，Geng，Zhou，Hao，Chen，Liu，Yang）的链表形式如图1.10所示。
图1.10 单链表的逻辑状态
为了操作上的方便，在单链表的第一个结点之前增加一个结点，称之为头结点。头结点的数据域可以存放如线性表的长度等信息，头结点的指针域存放第一个元素结点的地址信息，使其指向第一个元素结点。带头结点的单链表如图1.11所示。
图1.11 带头结点的单链表
若带头结点的单链表为空链表，则头结点的指针域为“空”，如图1.12所示。
图1.12 带头结点的单链表
【存储结构】
单链表的存储结构用C语言描述如下：
其中，ListNode是链表的结点类型，LinkList是指向链表结点的指针类型。如果有以下定义：
LinkList L；
则L被定义为指向单链表的指针类型，相当于以下定义：
ListNode *L；
【基本运算】
（1）初始化单链表
（2）判断单链表是否为空。若单链表为空，返回1；否则，返回0。
（3）按序号查找操作。
（4）查找元素值为e的结点。
（5）定位操作，确定元素在单链表中的序号。从头指针出发，依次访问每个结点，并将结点的值与e比较，如果相等，则返回该序号表示成功；如果没有与e值相等的元素，则返回0表示失败。
（6）在第i个位置插入元素e。
先来看如何在单链表中插入一个结点。假设存储元素e的结点为p，要将p指向的结点插入到pre和pre->next之间，无须移动结点元素，只需要改变p和pre指针的指向即可。先把*pre的直接后继结点变成*p的直接后继结点，然后把*p变成*pre的直接后继结点，如图1.13所示，代码如下：
p->next=pre->next；
pre->next=p；
图1.13 在*pre结点之后插入新结点*p
注意：插入结点的两行代码不能颠倒顺序。如果先进行pre->next=p，后进行p->next=pre->next操作，则第一条代码就会覆盖掉pre->next的地址，pre->next的地址就变成了p的地址，执行p->next=pre->next就等于执行p->next=p，这样pre->next就与上级断开了链接，造成尴尬的局面。如图1.14所示。
图1.14 插入结点代码顺序颠倒后，*（pre->next）结点与上一个结点链接断开
在单链表的第i个位置插入一个新元素e的步骤如下：①在链表中找到其直接前驱结点，即第i-1个结点，并由指针pre指向该结点，如图1.15所示。②申请一个新结点空间，由p指向该结点，将值e赋值给p指向结点的数据域。③修改*p和*pre结点的指针域，如图1.16所示。
图1.15 找到第i个结点的直接前驱结点
图1.16 将新结点插入到第i个位置
在单链表中插入元素e的算法实现如下。
（7）删除第i个结点。
先来看如何删除链表的第i个结点。假设p指向第i个结点，要将*p结点删除，只需要将它的直接前驱结点的指针绕过，使其直接指向它的直接后继结点即可，如图1.17所示。
图1.17 删除*pre的直接后继结点
删除单链表中第i个结点的步骤如下：①找到第i个结点的直接前驱结点，即第i-1个结点，并用pre指向该结点，p指向其直接后继结点，即第i个结点，如图1.18所示；②将*p结点的数据域赋值给e；③删除第i个结点，即pre->next=p->next，并释放*p结点的内存空间。删除过程如图1.19所示。
图1.18 找到第i-1个结点和第i个结点
图1.19 删除第i个结点
删除第i个结点的算法实现如下。
注意：在查找第i-1个结点时，要注意不可以遗漏判断条件pre->next->next！=NULL，确保第i个结点非空。如果没有此判断条件，而pre指针指向了单链表的最后一个结点，在执行循环后的p=pre->next，*e=p->data操作时，p指针就指向的是NULL指针域，这样则会产生致命错误。
（8）求表长操作。
（9）销毁链表操作。
上述的基本操作存放在#include"LinkList.h"文件中，在需要这些基本操作时可以供其他函数调用。