1.概述：
对于一个循环链表来说,其首节点和末节点被连接在一起。这种方式在单向和双向链表中皆可实现。要转换一个循环链表，可以选择开始于任意一个节点然后沿着列表的任一方向直到返回开始的节点。再来看另一种方法，循环链表可以被视为“无头无尾”。这种列表很利于节约数据存储缓存， 假定你在一个列表中有一个对象并且希望所有其他对象迭代在一个非特殊的排列下。
指向整个列表的指针可以被称作访问指针。
用单向链表构建的循环链表
循环链表中第一个节点之前就是最后一个节点，反之亦然。循环链表的无边界使得在这样的链表上设计算法会比普通链表更加容易。对于新加入的节点应该是在第一个节点之前还是最后一个节点之后可以根据实际要求灵活处理，区别不大(详见下面实例代码)。当然，如果只会在最后插入数据（或者只会在之前），处理也是很容易的。
另外有一种模拟的循环链表，就是在访问到最后一个节点之后的时候，手工的跳转到第一个节点。访问到第一个节点之前的时候也一样。这样也可以实现循环链表的功能，在直接用循环链表比较麻烦或者可能会出现问题的时候可以用。
2.程序实现：
struct LNode
{
ElemType data;
struct LNode *next;
};
typedef struct LNode *linkList;
Status InitList_CL(linkList *L)
{
*L=(linkList)malloc(sizeof(struct LNode));
if(!*L)
exit(OVERFLOW);
(*L)->next=*L;
return OK;
}
Status DestroyList_CL(linkList *L)
{
linkList q,p=(*L)->next;
while(p!=*L)
{
q=p->next;
free(p);
p=q;
}
free(*L);
*L=NULL;
return OK;
}
Status ClearList_CL(linkList *L)
{
linkList p,q;
*L=(*L)->next;
p=(*L)->next;
while(p!=*L)
{
q=p->next;
free(p);
p=q;
}
(*L)->next=*L;
return OK;
}
Status ListEmpty_CL(linkList L)
{
if(L->next==L)
return TRUE;
else
return FALSE;
}
int ListLength_CL(linkList L)
{
int i=0;
linkList p=L->next;
while(p!=L)
{
i++;
p=p->next;
}
return i;
}
Status GetElem_CL(linkList L,int i,ElemType *e)
{
int j=1;
linkList p=L->next->next;
if(i<=0||i>ListLength_CL(L))
return ERROR;
while(jnext;
j++;
}
*e=p->data;
return OK;
}
int LocateElem_CL(linkList L,ElemType e,Status(*compare)(ElemType,ElemType))
{
int i=0;
linkList p=L->next->next;
while(p!=L->next)
{
i++;
if(compare(p->data,e))
return i;
p=p->next;
}
return 0;
}
Status PriorElem_CL(linkList L,ElemType cur_e,ElemType *pre_e)
{
linkList q,p=L->next->next;
q=p->next;
while(q!=L->next)
{
if(q->data==cur_e)
{
*pre_e=p->data;
return TRUE;
}
p=q;
q=q->next;
}
return FALSE;
}
Status NextElem_CL(linkList L,ElemType cur_e,ElemType *next_e)
{
linkList p=L->next->next;
while(p!=L)
{
if(p->data==cur_e)
{
*next_e=p->next->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
Status ListInsert_CL(linkList *L,int i,ElemType e)
{
linkList p=(*L)->next,s;
int j=0;
if(i<=0||i>ListLength_CL(*L)+1)
return ERROR;
while(jnext;
j++;
}
s=(linkList)malloc(sizeof(struct LNode));
s->data=e;
s->next=p->next;
p->next=s;
if(p==*L)
*L=s;
return OK;
}
Status ListDelete_CL(linkList *L,int i,ElemType *e)
{
linkList p=(*L)->next,q;
int j=0;
if(i<=0||i>ListLength_CL(*L))
return ERROR;
while(jnext;
j++;
}
q=p->next;
p->next=q->next;
*e=q->data;
if(*L==q)
*L=p;
free(q);
return OK;
}
Status ListTraverse_CL(linkList L,void(*vi)(ElemType))
{
linkList p=L->next->next;
while(p!=L->next)
{
vi(p->data);
p=p->next;
}
printf("n");
return OK;
}
#include"c1.h"
typedef int ElemType;
#include"c2-2.h"
#include"bo2-4.c"
Status compare(ElemType c1,ElemType c2)
{
if(c1==c2)
return TRUE;
else
return FALSE;
}
void visit(ElemType c)
{
printf("%d ",c);
}
void main()
{
linkList L;
ElemType e;
int j;
Status i;
i=InitList_CL(&L);
printf("初始化单循环链表L i=%d (1:初始化成功)n",i);
i=ListEmpty_CL(L);
printf("L是否空 i=%d(1:空 0:否)n",i);
ListInsert_CL(&L,1,3);
ListInsert_CL(&L,2,5);
i=GetElem_CL(L,1,&e);
j=ListLength_CL(L);
printf("L中数据元素个数=%d,第1个元素的值为%d。n",j,e);
printf("L中的数据元素依次为：");
ListTraverse_CL(L,visit);
PriorElem_CL(L,5,&e);
printf("5前面的元素的值为%d。n",e);
NextElem_CL(L,3,&e);
printf("3后面的元素的值为%d。n",e);
printf("L是否空 %d(1:空 0:否)n",ListEmpty_CL(L));
j=LocateElem_CL(L,5,compare);
if(j)
printf("L的第%d个元素为5。n",j);
else
printf("不存在值为5的元素n");
i=ListDelete_CL(&L,2,&e);
printf("删除L的第2个元素：n");
if(i)
{
printf("删除的元素值为%d,现在L中的数据元素依次为：",e);
ListTraverse_CL(L,visit);
}
else
printf("删除不成功！n");
printf("清空L：%d(1: 成功)n",ClearList_CL(&L));
printf("清空L后，L是否空：%d(1:空 0:否)n",ListEmpty_CL(L));
printf("销毁L：%d(1: 成功)n",DestroyList_CL(&L));
}
