假期连载之三
(线性表的链式存储—循环链表、双向链表、静态链表)
上节我们介绍了线性表的链式存储结构中最重要的一种—单链表结构，但在这样的结构中也存在一些问题，而这些在顺序存储中却能得到较好的体现。为此，我们需要对单链表的存储结构进行一些改进，以实现我们需要的功能。
例如，在单链表中有时会给出某个结点的地址，并要求寻找其它所有结点，我们知道单链表结点中包括了指向其直接后继的指针域，但并不能回溯执行，因此在大多数情况下并不能实现题设的要求。
我们提供一种“首尾相接”的链表，其原理是将尾结点的next指针由null改为指向表头结点，于是就形成了单链表形式的循环链表，简称循环链表。
在不带附加头结点链表中，尾结点的情况为rear->next=head，其中head为头指针。而在带头结点链表中这种情况就变成rear->next=head->next。相应地，关于单链表操作的循环条件p!=NULL或p->next!=NULL将变为p!=head或p!=head->next，具体由是否附加头结点决定。
下面来看一个关于循环链表的应用问题——约瑟夫环（Josephus）。
约瑟夫环问题原本为一个数学应用，是由古罗马的史学家约瑟夫（Josephus）提出的。它的具体数学抽象为：设有编号为1，2，……，n的n(n>0)个人围成一个圈，从第1个人开始报数，报到m时停止报数，报m的人出圈，再从他的下一个人起重新报数，报到m时停止报数，报m的出圈，……，如此下去，直到所有人全部出圈为止。当任意给定n和m后，设计算法求最后一个出圈的人的最初序号。
事实上数学家们早已给出了这个问题或以此为基础衍生出的各种问题的数学解答，我们仅需要根据简单的递推公式即可轻松解决此类问题。但事实上，它其实也是一个循环链表的典型问题。
这是因为，其一，环事实上就是循环链表的抽象表现，在本题中环链的大小不断发生改变，也恰符合链表设置的最初意义，另外，约瑟夫环所对应的操作几乎囊括了循环链表的所有基本运算问题。
下面给出C++描述的约瑟夫环求解代码：
template<class T>
void Josephus(CircList<T>&Js,int n,int m) //n为结点数，m为间隔数
{
CircLinkNode<T>*p=Js.getHead(),*pre=NULL;
int i,j;
for(i=0;i<n-1;i++)
{
for(j=1;j<m;j++)
{
pre=p;
p=p->link;
}
cout<<”出圈的是：”<<p->data<<endl;
pre->link=p->link;
delete p;
p=pre->link;
}
};
注：本例仅给出约瑟夫环的求解方法函数，CircLinkNode及CircList类需要自行写出。
循环链表实现了一定的回溯操作，丰富了单链表的功能。但其在寻找直接前驱时的时间复杂度仍为O(n)，我们要使用更为高效的替代算法以实现O(1)，则就产生了双向循环链表，简称双向链表。
顾名思义，双向链表的结点中包含了三个数据成员，除原有的数据域，直接后继指针*next外，又添加了指向直接前驱的指针*prior。
在实际应用中，双向循环链表在仅需求后继结点的情况下和单链表的基本用法相类似。但当需同时顾及到前驱和后继两方面结点时就会发生改变。
首先我们知道在双向链表中存在下式成立：
p->prior->next==p;
p==p->next->prior;
我们据此给出双向链表前插操作的伪码表示：
DlinkIns(L,i,e) //L为原链表，i为插入位置，e为插入数据
//检查位置i是否合法，否则返回-1
//设置*p指向第i个结点
S=(DNode*)malloc(sizeof(DNode));
If(s) then
s->data=e;
s->prior=p->prior;
p->prior->next=s;
s->next=p;
p->prior=s;
return OK
else then
return -1
执行循环链表删除运算时，需要注意应从两个方面同时补链，例如：
p->prior->next=p->next;
p->next->prior=p->prior;
通过连载一和连载二我们较详细地介绍了线性表的几种存储结构和运算方法，它们都是基于C/C++或Java语言而言的。在一些语言诸如BASIC、FORTRAN中并不包含“指针”这种数据类型（当然Java中也不存在C语言意义上的指针，但并这不影响其对链表结构的诠释）。
在我们同样需要在此类领域中实现链表应用时，数组就成为最为可靠的手段，但这并不同于顺序表的动态存储，而是采用结构体数组的形式，通过设置数据域和“游标Cursor”模拟链表结点，以达到和链表类似的目的，这就是静态链表。
游标Cursor通常为非负整数形式，它存放后继结点在结构数组中的数组下标值（并非绝对位置）。根据结点cursor值可以轻松凭借StaticList[cursor].data获得当前后继结点的值。而数组最后一个结点的cursor值通常为-1表示null。
由于数组的特性，首先静态链表的长度是固定的。因此在执行添加/删除操作时并不能实际创建/释放内存空间，而全部在原数组内部进行。
在后插法添加结点操作中，新结点先存放在数组空闲空间中，然后使新结点的cursor值等于要插入结点的cursor，再将原结点的cursor值等于新结点在结构体数组中的实际下标值。以上步骤可由以下语句实现：
StaticList[s].cursor=StaticList[p].cursor;
StaticList[p].cursor=s;
这说明尽管静态链表中的数据结点物理位置可能并不连续，但其逻辑次序并未发生变化，这就接近于链表的实际存储结构。
执行静态链表的删除操作时，只需使要删除结点前驱的cursor值等于要删除结点的cursor值即可。实际上要删除的结点空间并未发生任何修改。
由以上操作可知，当静态链表在经过数次插入/删除操作后，其总结点数其实只增未降，这就使得静态链表的运行效率大打折扣。
为此，我们一般额外设置一个备用静态链表，该表结点所存放的值是空闲空间以及因删除操作而回收的结点空间，实际运算时需要原链表和备用表的互相协作以达到相关目的。
（未完待续）