下载掌阅APP，畅读海量书库
立即打开
循环单链表是首尾相连的单链表，是另一种形式的单链表。本节主要从循环单链表的存储结构并结合实例讲解循环单链表。
循环单链表 （circular linked list）是首尾相连的一种单链表。将单链表的最后一个结点的指针域由空指针改为指向头结点或第一个结点，整个链表就形成一个环，这样的单链表称为 循环单链表 。从表中任何一个结点出发均可找到表中其他结点。
与单链表类似，循环单链表也可分为带头结点结构和不带头结点结构两种。对于不带头结点的循环单链表，当表不为空时，最后一个结点的指针域指向头结点，如图3-23所示。对于带头结点的循环单链表，当表为空时，头结点的指针域指向头结点本身，如图3-24所示。
图3-23 循环单链表
图3-24 结点为空的循环单链表
循环单链表与单链表在结构、类型定义及实现方法上都是一样的，唯一的区别仅在于判断链表是否为空的条件上。判断单链表为空的条件是head->next==NULL，判断循环单链表为空的条件是head->next==head。
在单链表中，访问第一个结点的时间复杂度为O（1），而访问最后一个结点则需要将整个单链表扫描一遍，故时间复杂度为O（n）。对于循环单链表，只需设置一个 尾指针 （利用rear指向循环单链表的最后一个结点）而不设置头指针，就可以直接访问最后一个结点，时间复杂度为O（1）。访问第一个结点即rear->next->next，时间复杂度也为O（1）。如图3-25所示。
图3-25 仅设置尾指针的循环单链表
在循环单链表中设置尾指针，还可以使有些操作变得简单，例如要将如图3-26所示的两个循环单链表（尾指针分别为LA和LB）合并成一个链表，只需要将一个表的表尾和另一个表的表头连接即可，如图3-27所示。
图3-26 两个设置尾指针的循环单链表
图3-27 合并两个设置尾指针的循环单链表
将循环单链表合并为一个循环单链表只需要3步操作，第一步将LA的表尾与LB的第一个结点相连，即LA->next=LB->next->next；第二步释放LB的头结点，即free（LB->next）；第三步将LB的表尾与LA的表头相连，即LB->next=LA->next。
对于设置了头指针的两个循环单链表（头指针分别是head1和head2），要将其合并成一个循环单链表，需要先找到两个链表的最后一个结点，分别增加一个尾指针，分别使其指向最后一个结点。然后将第一个链表的尾指针与第二个链表的第一个结点连接起来，第二个链表的尾指针与第一个链表的第一个结点连接起来，就形成了一个循环链表。
合并两个循环单链表的算法实现如下。
LinkList Link(LinkList head1,LinkList head2)
/*
将两个链表head1
和head2
连接在一起形成一个循环链表*/
{
ListNode *p,*q;
p=head1;
while(p->next!=head1) /*
指针p
指向链表的最后一个结点*/
p=p->next;
q=head2;
while(q->next!=head2) /*
指针q
指向链表的最后一个结点*/
q=q->next;
p->next=head2->next; /*
将第一个链表的尾端连接到第二个链表的第一个结点*/
q->next=head1; /*
将第二个链表的尾端连接到第一个链表的第一个结点*/
return head1;
}
说明 部分图书把循环单链表中的头结点称为哨兵结点。
【例3-6】 已知一个带哨兵结点h的循环单链表中的数据元素含有正数和负数，试编写一个算法，构造两个循环单链表，使一个循环单链表中只含正数，另一个循环单链表只含负数。
【分析】 初始时，先创建两个空的单链表ha和hb，然后依次查看指针p指向的结点元素值，如果值为正数，则将其插入ha中，否则将其插入hb中。最后使最后一个结点的指针域指向头结点，构成循环单链表。
程序实现代码如下所示。
/*
头文件*/
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
/*
单链表类型定义*/
typedef int DataType;
typedef struct Node
{
DataType data;
struct Node *next;
}ListNode,*LinkList;
/*
函数声明*/
LinkList CreateCycList();/*
创建一个循环单链表*/
void Split(LinkList ha,LinkList hb);/*
按ha
中元素值的正数和负数分成两个循环单链表ha
和hb*/
void DispCycList(LinkList head);/*
输出循环单链表*/
void main()
{
LinkList ha,hb=NULL;
ListNode *s,*p;
ha=CreateCycList();
p=ha;
while(p->next!=ha)/*
找ha
的最后一个结点，p
指向该结点*/
p=p->next;
/*
为ha
添加哨兵结点*/
s=(ListNode*)malloc(sizeof(ListNode));
s->next=ha;
ha=s;
p->next=ha;
/*
创建一个空的循环单链表hb*/
s=(ListNode*)malloc(sizeof(ListNode));
s->next=hb;
hb=s;
Split(ha,hb);
printf("
输出循环单链表A(
正数):\n");
DispCycList(ha);
printf("
输出循环单链表B(
负数):\n");
DispCycList(hb);
}
void Split(LinkList ha,LinkList hb)
/*
将一个循环单链表ha
构造成两个循环单链表，其中ha
中的元素只含正数，hb
中的元素只含负数*/
{
ListNode *ra,*rb,*p=ha->next;
int v;
ra=ha;
ra->next=NULL;
rb=hb;
rb->next=NULL;
while(p!=ha)
{
v=p->data;
if(v>0)/*
若元素值大于0
，插入ha
中*/
{
ra->next=p;
ra=p;
}
else/*
若元素值小于0
，插入hb
中*/
{
rb->next=p;
rb=p;
}
p=p->next;
}
ra->next=ha;/*
变为循环单链表*/
rb->next=hb;/*
变为循环单链表*/
}
LinkList CreateCycList()
/*
创建循环单链表*/
{
ListNode *h=NULL,*s,*t=NULL;
DataType e;
int i=1;
printf("
创建一个循环单链表(
输入0
表示创建链表结束):\n");
while(1)
{
printf("
请输入第%d
个结点的data
域值:",i);
scanf("%d",&e);
if(e==0)
break;
if(i==1)
{
h=(ListNode*)malloc(sizeof(ListNode));
h->data=e;
h->next=NULL;
t=h;
}
else
{
s=(ListNode*)malloc(sizeof(ListNode));
s->data=e;
s->next=NULL;
t->next=s;
t=s;
}
i++;
}
if(t!=NULL)
t->next=h;
return h;
}
void DispCycList(LinkList h)
/*
输出循环单链表*/
{
ListNode *p=h->next;
if(p==NULL)
{
printf("
链表为空!\n");
return;
}
while(p->next!=h)
{
printf("%4d",p->data);
p=p->next;
}
printf("%4d",p->data);
printf("\n");
}
程序运行结果如图3-28所示。
图3-28 程序运行结果
从以上程序容易看出，循环单链表的创建与单链表的创建基本一样，只是最后增加了如下一条语句使最后一个结点指向第一个结点，构成一个循环单链表。
if(t!=NULL)
t->next=h;