一.循环链表
当使用单链表进行遍历的时候,我们只能从头结点开始,尾结点结束,如果需要查看指针所指向结点的前面结点,我们又必须从头结点开始遍历。为了解决这个问题,我们便引入了双链表,使其能够双向遍历,但是它又引入了prior指针域,增加了额外的开销。为此,我们便又引入了循环链表。所谓循环链表简单来说就是表尾的指针域指向表头从而使整个链表形成了一个闭环。
1.1循环单链表
循环单链表和单链表的的区别在于,表中最后一个节点的指针域不是NULL,而是指向了头结点,从而使整个链表形成一个环,如图所示:
在循环单链表中,表尾结点*r的next指针域指向头结点head,故表中没有指针域为NULL的结点。因此判断循环单链表是否为空的条件便是头结点的指针域是否指向自身。
循环单链表的插入,删除操作与单链表的基本操作一致,但是当在表尾结点处进行插入,删除操作时,必须注意不能使其断链。同时我们应注意到,一般情况下,我们对链表的操作大部分集中在表尾,如此,我们对循环单链表并不设置头指针,只设置一个尾指针,从而使得操作效率更高
1.2循环双链表
由循环单链表的定义我们很容易的便可以得到循环双链表,但与循环单链表不同的是循环双链表的尾结点的指针域next在指向头结点的同时, 头结点的prior指针域还必须指向尾结点。如图所示:
循环双链表中,链表为空的条件为头结点的prior指针域和next指针域均指向自身节点。
二.静态链表
静态链表是借助数组来描述线性表的链式存储结构的,节点同样有数据域data和“指针域”next,但与前面所讲的指针不同的是,这里的“指针”是结点的相对地址(即数组下标),或称为游标。因此它与顺序表一样,使用时必须预先分配一块连续的内存空间。
静态链表和单链表的对应关系如下图所示:
(a). 静态链表示例
(b). 静态链接对应的单链表
其数据结构描述如下:
#define MaxSize 50
typedef struct{
ElemType data;
int next;
}SLinkList[MaxSize];
静态链表以next==-1作为其结束的标识。静态链表的插入,删除操作与动态链表无异,只需修改“指针”便可。总的来说,静态链表没有单链表使用起来方便,但是在没有指针类型的高级程序设计语言(如Basic)中使用链表结构,却又不失为一种巧妙的设计方法。