- 数据结构与算法（C语言版）
- 胡明 王红梅编著
- 10694字
- 2020-08-27 10:10:20
3.3 线性表的存储结构及实现
3.3.1 顺序表
1.顺序表的存储结构定义
线性表的顺序存储结构称为顺序表（sequentiallist），其基本思想是用一段地址连续的存储单元依次存储线性表的数据元素，如图3-5所示。由于线性表中每个数据元素的类型相同，设顺序表的每个元素占用c个存储单元，则第i个元素的存储地址为：
图3-5 顺序表中元素ai的存储地址
LOC（ai）=LOC（a1）+（i-1）c
容易看出，顺序表中数据元素的存储地址是其序号的线性函数，只要确定了存储顺序表的起始地址（即基地址），计算任意一个元素的存储地址的时间就是相等的，具有这一特点的存储结构称为随机存取（randomaccess）结构。
通常用一维数组来实现顺序表，也就是把线性表中相邻的元素存储在数组中相邻的位置，从而导致了数据元素的序号和存放它的数组下标之间的一一对应关系，如图3-6所示。需要强调的是，C语言中数组的下标是从0开始的，而线性表中元素的序号是从1开始的，也就是说，线性表中第i个元素存储在数组中下标为i-1的位置①。
图3-6 数组的长度和线性表的长度具有不同含义
数组需要分配固定长度的数组空间，因此，必须确定存放线性表的数组空间的长度。因为在线性表中可以进行插入操作，所以，数组的长度应大于当前线性表的长度。用MaxSize表示数组的长度，用length表示线性表的长度，如图3-6所示。
下面给出顺序表的存储结构定义：
constintMaxSize=10； //假设顺序表最多存放10个元素
typedefintDataType； //DataType为线性表的数据类型
typedefstruct
{
DataTypedata[MaxSize]； //存放数据元素的数组
intlength； //线性表的长度
}SeqList；
2.顺序表的实现
在顺序表中，由于元素的序号与数组中存储该元素的下标之间具有一一对应关系，所以，容易实现顺序表的基本操作。下面讨论基本操作的算法。
（1）初始化顺序表
初始化顺序表只需简单地将顺序表的长度length初始化为0，算法如下：
初始化顺序表InitList
voidInitList（SeqList&L）
{
L.length=0；
}
（2）建立顺序表
建立一个长度为n的顺序表需要将给定的数据元素传入顺序表中，并将传入的元素个数作为顺序表的长度。设给定的数据元素存放在数组 a[n]中，建立顺序表的操作示意图如图3-7所示。算法如下：
图3-7 建立顺序表的操作示意图
建立顺序表Creat
voidCreat（SeqList&L，DataTypea[]，intn）
{
if（n＞MaxSize）{printf（＂参数非法＂）；exit（-1）；}
for（i=0；i＜n；i++）
L.data[i]=a[i]；
L.length=n；
}
（3）求顺序表的长度
在顺序表的存储结构定义中用结构体成员length保存了线性表的长度，因此，求线性表的长度只需返回length的值，算法如下：
顺序表的长度Length
intLength（SeqList&L）
{
returnL.length；
}
（4）按位查找
顺序表中第i个元素存储在数组中下标为i-1的位置，所以，容易实现按位查找。显然，按位查找算法的时间复杂度为O（1）。
顺序表按位查找算法Get
DataTypeGet（SeqList&L，inti）
{
if（i＜1&&i＞L.length）{printf（＂查找位置非法＂）；exit（-1）；}
elsereturnL.data[i-1]；
}
（5）按值查找
在顺序表中实现按值查找操作，需要对顺序表中的元素依次进行比较，如果查找成功，返回元素的序号（注意不是下标）；如果查找不成功，返回查找失败的标志“0”。
顺序表按值查找算法Locate
intLocate（SeqList&L，DataTypex）
{
for（i=0；i＜L.length；i++）
if（L.data[i]==x）returni+1； //下标为i的元素等于x，返回序号i+1
return0； //退出循环，说明查找失败
}
按值查找算法的问题规模是表长n，基本语句是for循环中元素比较的语句。顺序查找从第一个元素开始，依次比较每一个元素，直到找到x为止。如果顺序表的第一个元素恰好就是x，算法只要比较一次就行了，这是最好情况；如果顺序表的最后一个元素是x，算法就要比较n个元素，这是最坏情况；平均情况下，假设数据等概率分布，则平均比较表长的一半。所以，按值查找算法的平均时间性能是O（n）。
（6）插入操作
插入操作是在表的第i（1≤i≤n+1）个位置插入一个新元素 x，使长度为 n的线性表（a1，…，ai-1，ai，…，an）变成长度为n+1的线性表（a1，…，ai-1，x，ai，…，an），插入后，元素ai-1和ai之间的逻辑关系发生了变化并且存储位置要反映这个变化。图3-8给出了顺序表在进行插入操作的前后，数据元素在存储空间中位置的变化。
图3-8 将元素15插入位置3，顺序表前后状态的对比
注意元素移动的方向，必须从最后一个元素开始移动，直至将第i个元素后移为止，然后将新元素插入位置i处。如果表满了，则引发上溢错误；如果元素的插入位置不合理，则引发位置错误。算法如下：
顺序表插入算法Insert
voidInsert（SeqList&L，inti，DataTypex）
{
if（L.length＞=MaxSize）{printf（＂上溢＂）；exit（-1）；}
if（i＜1‖i＞length+1）{printf（＂位置＂）；exit（-1）；}
for（j=L.length；j＞=i；j--） //j表示元素序号
L.data[j]=L.data[j-1]；
L.data[i-1]=x；
L.length++；
}
该算法的问题规模是表的长度n，基本语句是for循环中元素后移的语句。当i=n+1时（即在表尾插入），元素后移语句将不执行，这是最好情况，时间复杂度为O（1）；当i=1时（即在表头插入），元素后移语句将执行n次，需移动表中所有元素，这是最坏情况，时间复杂度为O（n）；由于插入可能在表中任意位置上进行，因此需分析算法的平均时间复杂度。令Ein（n）表示元素移动次数的平均值，pi表示在表中第i个位置上插入元素的概率，不失一般性，假设p1=p2=…=pn+1=1/（n+1），由于在第i个（1≤i≤n+1）位置上插入一个元素后移语句的执行次数为n-i+1，故
也就是说，在顺序表上实现插入操作，等概率情况下，平均要移动表中一半的元素，算法的平均时间复杂度为O（n）。
（7）删除操作
删除操作是将表的第i（1≤i≤n）个元素删除，使长度为n的线性表（a1，…，ai-1，ai，ai+1，…，an）变成长度为n-1的线性表（a1，…，ai-1，ai+1，…，an），删除后元素ai-1和ai+1之间的逻辑关系发生了变化并且存储位置也要反映这个变化。图3-9给出了顺序表在删除操作的前后，数据元素在存储空间中位置的变化。
图3-9 将位置3处的元素删除，顺序表前后状态的对比
注意元素移动的方向，必须从第i+1个元素（下标为i）开始移动，直至将最后一个元素前移为止，并且在移动元素之前要取出被删元素。如果表为空，则引发下溢错误；如果元素的删除位置不合理，则引发位置错误。算法如下：
顺序表删除算法Delete
DataTypeDelete（SeqList&L，inti）
{
if（L.length==0）{printf（＂下溢＂）；exit（-1）；}
if（i＜1‖i＞L.length）{printf（＂位置＂）；exit（-1）；}
x=L.data[i-1]； //取出位置i的元素
for（j=i；j＜L.length；j++） //j表示元素所在数组下标
L.data[j-1]=L.data[j]；
L.length--；
returnx；
}
设顺序表的表长是n，显然，删除第i个（1≤i≤n）元素需要移动n-i个元素，令Ede（n）表示元素移动次数的平均值，pi表示删除第i个元素的概率，等概率情况下，pi=1/n，则
也就是说，在顺序表上实现删除操作，等概率情况下，平均要移动表中一半的元素，算法的平均时间复杂度为O（n）。
（8）判空操作
顺序表的判空操作只需判断长度length是否为0，算法如下：
顺序表判空算法Empty
intEmpty（SeqList&L）
{
if（L.length==0）return1； //顺序表为空返回1
elsereturn0；
}
（9）遍历操作
在顺序表中，遍历操作即是按下标依次输出各元素，算法如下：
顺序表遍历算法PrintList
voidPrintList（SeqList&L）
{
for（i=0；i＜L.length；i++）
printf（L.data[i]）； //依次输出线性表的元素值
}
3.3.2 单链表
1.单链表的存储结构定义
单链表①（singlylinkedlist）是用一组任意的存储单元存放线性表的元素，这组存储单元可以连续也可以不连续，甚至可以零散分布在内存中的任意位置。为了能正确表示元素之间的逻辑关系，每个存储单元在存储数据元素的同时，还必须存储其后继元素所在的地址信息，如图3-10所示，这个地址信息称为指针（pointer），这两部分组成了数据元素的存储映像，称为结点（node），结点结构如图3-11所示。单链表正是通过每个结点的指针域将线性表的数据元素按其逻辑次序链接在一起的，由于每个结点只有一个指针域，故称为单链表。
图3-10 线性表（a1，a2，a3）的单链表存储
图3-11 单链表的结点结构
用图3-10的方法表示一个单链表非常不方便，而且在使用单链表时，关心的只是数据元素以及数据元素之间的逻辑关系，而不是每个数据元素在存储器中的实际位置。通常将图3-10所示的单链表画成图3-12的形式。
图3-12 线性表（a1，a2，a3）的单链表存储
如图3-12所示，单链表中每个结点的存储地址存放在其前驱结点的next域中，而第一个元素无前驱，所以设头指针（headpointer）指向第一个元素所在结点（称为开始结点），整个单链表的存取必须从头指针开始进行，因而头指针具有标识一个单链表的作用；由于最后一个元素无后继，故最后一个元素所在结点（称为终端结点）的指针域为空，即NULL（图中用“∧”表示），也称尾标志（tailmark）。
从单链表的存储示意图可以看到，除了开始结点外，其余每个结点的存储地址都存放在其前驱结点的next域中，而开始结点是由头指针指示的。这个特例需要在单链表实现时特殊处理，增加了程序的复杂性和出现bug①的机会。因此，通常在单链表的开始结点之前附设一个类型相同的结点，称为头结点②（headnode），如图3-13所示。加上头结点之后，无论单链表是否为空，头指针始终指向头结点，因此空表和非空表的处理也统一了。
图3-13 带头结点的单链表
下面给出单链表的存储结构定义：
typedefintDataType； //DataType为线性表的数据类型
typedefstructNode
{
DataTypedata；
Node*next；
}Node，*first； //first为指向单链表的头指针
2.单链表的实现
单链表的基本思想就是用指针表示结点之间的逻辑关系，首先要正确区分指针变量、指针、指针所指结点和结点的值这四个密切相关的不同概念。
设p是一个指针变量，则p的值是一个指针。有时为了叙述方便，将“指针变量”简称为“指针”。例如，将“头指针变量”简称为“头指针”。
设指针p指向某个Node类型的结点，则该结点用*p来表示，*p为结点变量。有时为了叙述方便，将“指针p所指结点”简称为“结点p”。
在单链表中，结点p由两个域组成：存放数据元素的部分和存放后继结点地址的指针部分，分别用（*p）.data和（*p）.next来标识，为了使用方便，C语言为指向结构体的指针提供了运算符“-＞”，即用p-＞data和p-＞next分别表示结点p的数据域和指针域，如图3-14所示，设指针p指向结点ai，则p-＞next指向结点ai+1。
图3-14 指针和结点之间的关系
单链表由头指针唯一指定，整个单链表的操作必须从头指针开始。通常设置一个工作指针p，当指针p指向某结点时执行相应的处理，然后将指针p修改为指向其后继结点，直到p为NULL为止
。下面讨论单链表基本操作的算法。
（1）初始化单链表
初始化单链表也就是生成只有头结点的空链表，算法如下：
初始化单链表InitList
Node*InitList（Node*first）
{
first=（Node*）malloc（sizeof（Node））； //生成头结点
first-＞next=NULL； //头结点的指针域置空
returnfirst；
}
（2）遍历操作
所谓遍历单链表是指按序号依次访问单链表中的所有结点且仅访问一次。可以设置一个工作指针p依次指向各结点，当指针p指向某结点时输出该结点的数据域。遍历单链表的操作示意图如图3-15所示，算法用伪代码描述如下 ：
图3-15 遍历单链表的操作示意图
算法：PrintList（first）
输入：单链表的头指针first
输出：单链表所有结点的元素值
1.工作指针p初始化为指向开始结点；
2.重复执行下述操作，直到p为空：
2.1 输出结点p的数据域；
2.2 工作指针p后移；
遍历单链表需要将单链表扫描一遍，因此时间复杂度为O（n）。遍历单链表的算法用C语言描述如下：
单链表遍历算法PrintList
voidPrintList（Node*first）
{
p=first-＞next； //工作指针p初始化
while（p！=NULL）
{
printf（p-＞data）；
p=p-＞next； //工作指针p后移，注意不能写作p++
}
}
需要强调的是，工作指针p后移不能写作p++，因为单链表的存储单元可能不连续，因此p++不能保证工作指针p指向下一个结点，如图3-16所示。
图3-16 p++与p-＞next的执行结果
（3）求线性表的长度
由于单链表的存储结构定义中没有存储线性表的长度，因此，不能直接获得线性表的长度。考虑采用“数数”的方法来求其长度，即从第一个结点开始数，一直数到表尾。可以设置一个工作指针p依次指向各结点，当指针p指向某结点时求出其序号，然后将p修改为指向其后继结点并且将序号加1，则最后一个结点的序号即为表中结点个数（即线性表的长度）。求单链表长度的操作示意图如图3-17所示。
图3-17 求线性表长度的操作示意图
求线性表长度的算法用C语言描述如下：
求线性表长度算法Length
intLength（Node*first）
{
p=first-＞next；count=0； //工作指针p和累加器count初始化
while（p！=NULL）
{
p=p-＞next；
count++；
}
returncount； //注意count的初始化和返回值之间的关系
}
（4）按位查找
在单链表中，即使知道被访问结点的序号i，也不能像顺序表那样直接按序号访问，只能从头指针出发顺next域逐个结点往下搜索。当工作指针p指向某结点时判断是否为第i个结点，若是，则查找成功；否则，将工作指针p后移。对每个结点依次执行上述操作，直到p为NULL时查找失败。算法如下：
单链表按位查找算法Get
DataTypeGet（Node*first，inti）
{
p=first-＞next；count=1； //工作指针p和累加器count初始化
while（p！=NULL&&count＜i）
{
p=p-＞next； //工作指针p后移
count++；
}
if（p==NULL）{printf（＂位置＂）；exit（-1）；} //查找失败
elsereturnp-＞data；
}
查找算法的基本语句是工作指针p后移，该语句执行的次数与被查结点在表中的位置有关。在查找成功的情况下，若查找位置为i（1≤i≤n），则需要执行 i-1次，等概率情况下，平均时间性能为O（n）。因此，单链表是顺序存取（SequentialAccess）结构。
（5）按值查找
在单链表中实现按值查找操作，需要对单链表中的元素依次进行比较，如果查找成功，则返回元素的序号；如果查找不成功，返回0表示查找失败。算法如下：
单链表按值查找算法Locate
intLocate（Node*first，DataTypex）
{
p=first-＞next；count=1； //工作指针p和累加器count初始化
while（p！=NULL）
{
if（p-＞data==x）returncount； //查找成功，结束函数并返回序号
p=p-＞next；
count++；
}
return0； //退出循环表明查找失败
}
按值查找的基本语句是将结点p的数据域与待查值进行比较，具体的比较次数与待查值结点在单链表中的位置有关。在等概率情况下，平均时间性能为O（n）。
（6）插入操作
单链表的插入操作是将值为x的新结点插入到单链表的第i个位置，即插入到ai-1与ai之间。因此，必须先扫描单链表，找到ai-1的存储地址p，然后生成一个数据域为x的新结点s，将结点s的next域指向结点ai，将结点p的next域指向新结点s（注意指针的链接顺序），从而实现三个结点ai-1、x和ai之间逻辑关系的变化，插入过程如图3-18所示。注意分析在表头、表中间、表尾插入这三种情况，由于单链表带头结点，这三种情况的操作语句一致，不用特殊处理。算法用伪代码描述如下 ：
图3-18 在单链表中插入结点时指针的变化情况（① s-＞next=p-＞next；② p-＞next=s；）
算法：Insert（first，i，x）
输入：单链表的头指针first，插入位置i，待插值x
输出：无
1.工作指针p初始化为指向头结点；
2.查找第i-1个结点并使工作指针p指向该结点；
3.若查找不成功，说明插入位置不合理，结束算法并将异常代码返回；否则，生成一个元素值为x的新结点s，将结点s插入到结点p之后；
插入算法的时间主要耗费在查找正确的插入位置上，故时间复杂度为O（n）。单链表插入算法用C语言描述如下：
单链表插入算法Insert
voidInsert（Node*first，inti，DataTypex）
{
p=first；count=0； //工作指针p应指向头结点
while（p！=NULL&&count＜i-1） //查找第i-1个结点
{
p=p-＞next； //工作指针p后移
count++；
}
if（p==NULL）{printf（＂位置＂）；exit（-1）；} //没有找到第i-1个结点
else{
s=（Node*）malloc（sizeof（Node））；
s-＞data=x； //申请一个结点s，其数据域为x
s-＞next=p-＞next；p-＞next=s； //将结点s插入到结点p之后
}
}
在不带头结点的单链表中插入一个结点，在表头的操作和在表中间以及表尾的操作语句是不同的，则在表头的插入情况需要单独处理，如图3-19所示，算法如下：
图3-19 在不带头结点的单链表中插入结点时指针的变化情况
（❶ s-＞next=first；❷ first=s；① s-＞next=p-＞next；② p-＞next=s；）
不带头结点单链表的插入算法Insert
voidInsert（Node*first，inti，DataTypex）
{
if（i==1）
{
s=（Node*）malloc（sizeof（Node））；s-＞data=x；
s-＞next=first；first=s； //将结点s插入到头指针之后
return； //插入操作完毕，结束函数
}
p=first；count=0； //工作指针p初始化
while（p！=NULL&&count＜i-1）
{
p=p-＞next； //工作指针p后移
count++；
}
if（p==NULL）{printf（＂位置＂）；exit（-1）；}
else
{
s=（Node*）malloc（sizeof（Node））；s-＞data=x；
s-＞next=p-＞next； //将结点s插入到结点p之后
p-＞next=s；
}
}
可见，在不带头结点的单链表中实现插入操作，算法不仅冗长，而且需要考虑在表头操作的特殊情况，容易出现错误。所以，在单链表中，除非特别说明不能带头结点，否则，为了运算方便，都要加上头结点。
（7）建立单链表
设给定的数据元素存放在数组a[n]中，建立单链表就是生成存储这n个数据元素的单链表。有两种建立方法：头插法和尾插法。
头插法的基本思想是每次将新申请的结点插在头结点的后面，执行过程如图3-20所示，算法如下：
图3-20 头插法建立单链表的操作示意图（① s-＞next=first-＞next；② first-＞next=s；）
头插法建立单链表Creat
Node*Creat（Node*first，DataTypea[]，intn）
{
first=（Node*）malloc（sizeof（Node））；
first-＞next=NULL； //初始化头结点
for（i=0；i＜n；i++）
{
s=（Node*）malloc（sizeof（Node））；
s-＞data=a[i]； //为每个数组元素建立一个结点
s-＞next=first-＞next；first-＞next=s； //将结点s插入到头结点之后
}
returnfirst；
}
尾插法的基本思想是每次将新申请的结点插在终端结点的后面，执行过程如图3-21所示，算法如下：
尾插法建立单链表Creat
Node*Creat（Node*first，DataTypea[]，intn）
{
first=（Node*）malloc（sizeof（Node））； //生成头结点
r=first； //尾指针初始化
for（i=0；i＜n；i++）
{
s=（Node*）malloc（sizeof（Node））；
s-＞data=a[i]； //为每个数组元素建立一个结点
r-＞next=s；r=s； //将结点s插入到终端结点之后
}
r-＞next=NULL； //单链表建立完毕，将终端结点的指针域置空
returnfirst；
}
（8）删除操作
删除操作是将单链表的第i个结点删去。因为在单链表中结点ai的存储地址在其前驱结点ai-1的指针域中，所以必须首先找到ai-1的存储地址p，然后令p的next域指向ai的后继结点，即把结点ai从链上摘下，最后释放结点ai的存储空间。需要注意表尾的特殊情况，此时虽然被删结点不存在，但其前驱结点却存在。因此仅当被删结点的前驱结点p存在且p不是终端结点时，才能确定被删结点存在，如图3-22所示。算法用伪代码描述如下 ：
图3-22 在单链表中删除结点时指针的变化情况
算法：Delete（first，i）
输入：单链表的头指针first，删除位置i
输出：被删除的元素值
1.工作指针p初始化；累加器count初始化；
2.查找第i-1个结点并使工作指针p指向该结点；
3.若p不存在或p的后继结点不存在，则引发位置错误；
否则： 3.1 暂存被删结点和被删元素值；
3.2 摘链，将结点p的后继结点从链表上摘下；
3.3 释放被删结点；
3.4 返回被删元素值；
删除算法的时间主要耗费在查找正确的删除位置上，故时间复杂度亦为O（n）。单链表删除算法用C语言描述如下：
单链表删除算法Delete
DataTypeDelete（Node*first，inti）
{
p=first；count=0； //注意工作指针p要指向头结点
while（p！=NULL&&count＜i-1） //查找第i-1个结点
{
p=p-＞next；
count++；
}
if（p==NULL|p-＞next==NULL） //结点p不存在或p的后继结点不存在
{
printf（＂位置＂）；exit（-1）；
}
else
{
q=p-＞next；x=q-＞data； //暂存被删结点
p-＞next=q-＞next； //摘链
free（q）；
returnx；
}
}
3.3.3 双链表
1.双链表的存储结构定义
如果希望快速确定单链表中任一结点的前驱结点，可以在单链表的每个结点中再设置一个指向其前驱结点的指针域，这样就形成了双链表（doublylinkedlist）。和单链表类似，双链表一般也是由头指针唯一确定的，增加头结点也能使双链表的某些操作变得方便。双链表的存储示意图如图3-23所示。
图3-23 双链表存储示意图
在双链表中，每个存储单元在存储数据元素的同时，还存储了其前驱元素和后继元素所在的地址信息，这三部分组成了数据元素的存储映像。双链表的结点结构如图3-24所示，其中，data为数据域，存放数据元素；prior为前驱指针域，存放该结点的前驱结点的地址；next为后继指针域，存放该结点的后继结点的地址。下面给出双链表的存储结构定义：
图3-24 双链表的结点结构
typedefintDataType； //DataType为线性表的数据类型
typedefstructDulNode
{
DataTypedata；
structDulNode*prior，*next；
}DulNode，*first； //first为双链表的头指针
2.双链表的实现
在双链表中求表长、按位查找、按值查找、遍历等操作的实现与单链表基本相同。下面讨论插入和删除操作。
（1）插入操作
在结点p的后面插入一个新结点s，需要修改四个指针：
① s-＞prior=p；
② s-＞next=p-＞next；
③ p-＞next-＞prior=s；
④ p-＞next=s；
注意指针修改的相对顺序，如图3-25所示，在修改第②和③步的指针时，要用到p-＞next以找到结点p的后继结点，所以第④步指针的修改要在第②和③步的指针修改完成后才能进行。算法如下：
图3-25 双链表插入操作示意图
双链表插入算法Insert
voidInsert（DulNode*first，inti，DataTypex）
{
p=first；count=0； //工作指针p应指向头结点
while（p！=NULL&&count＜i-1） //查找第i-1个结点
{
p=p-＞next； //工作指针p后移
count++；
}
if（p==NULL） //没有找到第i-1个结点
{
printf（＂位置＂）；exit（-1）；
}
else
{
s=（DulNode*）malloc（sizeof（DulNode））；
s-＞data=x； //申请一个结点s，其数据域为x
s-＞prior=p； //将结点s插入到结点p之后
s-＞next=p-＞next；
p-＞next-＞prior=s；
p-＞next=s；
}
}
（2）删除操作
设指针p指向待删除结点，如图3-26所示，删除操作可通过下述两条语句完成：
图3-26 双链表删除操作示意图
①（p-＞prior）-＞next=p-＞next；
②（p-＞next）-＞prior=p-＞prior；
这两个语句的顺序可以颠倒。另外，虽然执行上述语句后结点p的两个指针域仍指向其前驱结点和后继结点，但在双链表中已经找不到结点p，而且，执行删除操作后，还要将结点p所占的存储空间释放。双链表删除算法如下：
双链表删除算法Delete
DataTypeDelete（Node*first，inti）
{
p=first；count=0； //工作指针初始化
while（p！=NULL&&count＜i） //查找第i个结点
{
p=p-＞next；
count++；
}
if（p==NULL） //结点p不存在
{
printf（＂位置＂）；exit（-1）；
}
else
{
q=p-＞next；x=q-＞data； //暂存被删结点
（p-＞prior）-＞next=p-＞next；//摘链
（p-＞next）-＞prior=p-＞prior；
free（q）；
returnx；
}
}
3.3.4 循环链表
在单链表中，如果将终端结点的指针域由空指针改为指向头结点，就使整个单链表形成一个环，这种头尾相接的单链表称为循环单链表（circularsinglylinkedlist），如图3-27所示。
图3-27 循环单链表存储示意图
在用头指针指示的循环单链表中，找到开始结点的时间是O（1），然而要找到终端结点，则需从头指针开始遍历整个链表，其时间是O（n）。在很多实际问题中，操作是在表的首或尾两端进行的，此时头指针指示的循环单链表就显得不够方便。如果改用指向终端结点的尾指针（rearpointer）来指示循环单链表，如图3-28所示，则查找开始结点和终端结点都很方便，它们的存储地址分别是（rear-＞next）-＞next和rear，显然，时间都是O（1）。因此，实际应用中多采用尾指针指示的循环单链表。
图3-28 带尾指针的循环单链表
在双链表中，如果将终端结点的后继指针域由空指针改为指向头结点，将头结点的前驱指针域由空指针改为指向终端结点，就使整个双链表形成一个头尾相接的循环双链表（circulardoublelinkedlist），如图3-29所示。在由头指针指示的循环双链表中，查找开始结点和终端结点都很方便，它们的存储地址分别是first-＞next和first-＞prior，显然，时间开销都是O（1）。
图3-29 循环双链表存储示意图
循环链表没有增加任何存储量，仅对链表的链接方式稍做改变，因此，基本操作的实现与链表类似，不同之处仅在于循环条件不同。从循环链表中任一结点出发，可扫描到其他结点，从而增加了链表操作的灵活性。但这种方法的危险在于循环链表中没有明显的尾端，可能会使循环链表的处理操作进入死循环，所以，需要格外注意循环条件。通常判断用作循环变量的工作指针是否等于某一指定指针（如头指针或尾指针），以判定工作指针是否扫描了整个循环链表。例如，在循环单链表的遍历算法中，用循环条件p！=first判断工作指针p是否扫描了整个链表，算法如下：
循环单链表遍历算法PrintList
voidPrintList（Node*first）
{
p=first-＞next； //工作指针p初始化
while（p！=first） //注意循环条件
{
printf（p-＞data）；
p=p-＞next； //工作指针p后移
}
}
3.3.5 静态链表
1.静态链表的存储结构定义
静态链表（staticlinkedlist）用数组来表示单链表，用数组元素的下标来模拟单链表的指针。静态链表的存储示意图如图3-30所示，其中，avail是空闲链表（所有空闲数组单元组成的单链表）头指针，first是静态链表头指针。为了运算方便，通常静态链表也带头结点。
图3-30 静态链表存储示意图
静态链表的每个数组元素由两个域构成：data域存放数据元素，next域存放该元素的后继元素所在的数组下标。由于它是利用数组定义的，属于静态存储分配，因此叫做静态链表。静态链表的存储结构定义如下：
constintMaxSize=10； //最多10个数组单元
typedefintDataType； //DataType是线性表的数据类型
typedefstruct
{
DataTypedata；
intnext； //指针域（也称游标），注意不是指针
}SNode，SList[MaxSize]；
2.静态链表的实现
在静态链表中求表长、按位查找、按值查找、遍历等操作的实现与单链表基本相同，下面讨论插入和删除操作。
（1）插入操作
在静态链表中进行插入操作时，首先从空闲链的最前端摘下一个结点，将该结点插入静态链表中，如图3-31所示。假设新结点插在结点p的后面，则修改指针的操作为：
图3-31 静态链表插入操作示意图
s=avail； //不用申请新结点，利用空闲链的第一个结点
avail=SList[avail].next； //空闲链的头指针后移
SList[s].data=x； //将x填入下标为s的结点
SList[s].next=SList[p].next； //将下标为s的结点插入到下标为p的结点后面
SList[p].next=s；
（2）删除操作
进行删除操作时，将被删除结点从静态链表中摘下，再插入空闲链的最前端，如图3-31所示。假设要删除结点p的后继结点，则修改指针的操作为：
q=SList[p].next； //暂存被删结点的下标
SList[p].next=SList[q].next； //摘链
SList[q].next=avail； //将结点q插在空闲链avail的最前端
avail=q； //空闲链头指针avail指向结点q
图3-32 静态链表删除操作示意图
静态链表虽然是用数组来存储线性表的，但在执行插入和删除操作时，只需修改游标，无须移动表中的元素，从而改进了在顺序表中插入和删除操作需要移动大量元素的缺点，但它没有解决连续存储分配带来的表长难以确定的问题。
3.3.6 顺序表和链表的比较
前面给出了线性表的两种截然不同的存储结构——顺序存储结构和链接存储结构，哪一种更好呢？如果实际问题需要采用线性表来解决，应该选择哪一种存储结构呢？通常情况下，需要比较不同存储结构的时间性能和空间性能。
1.时间性能比较
所谓时间性能是指基于某种存储结构的基本操作（即算法）的时间复杂度。
像取出线性表中第i个元素这样的按位置随机访问的操作，使用顺序表更快一些，时间性能为O（1）；相比之下，链表中按位置访问只能从表头开始依次向后扫描，直到找到那个特定的位置，所需要的平均时间为O（n）。
在链表中进行插入和删除操作不需要移动元素，在给出指向链表中某个合适位置的指针后，插入和删除操作所需的时间仅为O（1）；在顺序表中进行插入和删除操作需移动表长一半的元素，平均时间为O（n），当线性表中元素个数较多时，特别是当每个元素占用的存储空间较多时，移动元素的时间开销很大。对于许多应用，插入和删除是最主要的操作，因此它们的时间效率是举足轻重的，仅就这个原因而言，链表比顺序表更好。
作为一般规律，若线性表需频繁查找却很少进行插入和删除操作，或其操作和“数据元素在线性表中的位置”密切相关时，宜采用顺序表作为存储结构；若线性表需频繁进行插入和删除操作，则宜采用链表作为存储结构。
2.空间性能比较
所谓空间性能是指某种存储结构所占用的存储空间的大小。首先定义结点的存储密度（storagedensity）。
顺序表中每个结点（即数组元素）只存放数据元素，其存储密度为1；而链表的每个结点除了存放数据元素，还要存储指示元素之间逻辑关系的指针。如果数据域占据的空间较小，则指针的结构性开销将占用整个结点的大部分，因而从结点的存储密度上讲，顺序表的存储空间利用率较高。
由于顺序表需要预分配一定长度的存储空间，如果事先不知道线性表的大致长度，则有可能对存储空间预分配得过大，致使存储空间得不到充分利用，造成浪费；若估计得过小，又将发生上溢而造成存储空间的再分配；单链表不需要为其预分配空间，只要有内存空间可以分配，链表中的元素个数就没有限制。
作为一般规律，当线性表中元素个数变化较大或者未知时，最好使用链表实现；如果事先知道线性表的大致长度，使用顺序表的空间效率会更高。
总之，线性表的顺序存储和链接存储各有其优缺点，应该根据实际问题的需要，并对各方面的优缺点加以综合平衡，才能最终选定比较适宜的存储结构。