循环链表是另一种形式的链式存贮结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。表中最后一个结点的指针域指向头结点,整个链表形成一个环。嗯下面就网上找的一张单链的循环链表
单项链表定义:
typedef struct LNode{
ElemType data;
struct LNode *next;
}LNode,*LinkList;
单向循环链表基本操作:
/*操作结果:构造一个空的线性表L*/
void InitList(LinkList &L)
/*初始条件:单循环链表L存在*/
/*操作结果:摧毁单循环链表L*/
void DestroyList(LinkList &L)
/*初始条件:单循环链表L存在*/
/*操作结果:将L重置为空表*/
Status ClearList(LinkList &L)
/*初始条件:单循环链表L存在*/
/*操作结果:若L为空表,则返回TRUE,否则返回FALSE*/
Status ListEmpty(LinkList L)
/*初始条件:单循环链表L存在*/
/*操作结果:返回L中数据元素个数*/
int ListLength(LinkList L)
/*初始条件:单循环链表L存在*/
/*操作结果:当第i个元素存在时,其值赋给e并返回OK,否则返回FALSE。*/
Status GetElem(LinkList L,int i,ElemType &e)
/*初始条件:单循环链表L存在,compare()是数据元素判定的函数*/
/*操作结果:返回L中第1个与e满足关系compare()的数据元素的位序。若这样的数据元素不存在,则返回值为ERROR*/
Status LocateElem(LinkList L,ElemType e,Status(*compare)(ElemType,ElemType))
/*初始条件:单循环链表L存在*/
/*操作结果:若cur_e是L的数据元素,且不是第一个,则用pre_e返回它的前驱;否则,操作失败,pre_e无定义*/
Status PriorElem(LinkList L,ElemType cur_e,ElemType &pre_e)
/*初始条件:单循环链表L存在*/
/*操作结果:若cur_e是L的数据元素,且不是最后一个,则用next_e返回它的后继;否则,操作失败,next_e无定义*/
Status NextElem(LinkList L,ElemType cur_e,ElemType &next_e)
/*初始条件:单循环链表L存在*/
/*操作结果:在L的第i个位置之前插入元素e*/
Status ListInsert(LinkList &L,int i,ElemType e)
/*初始条件:单循环链表L存在*/
/*操作结果:删除L的第i个元素,并由e返回其值*/
Status ListDelete(LinkList &L,int i,ElemType &e)
/*初始条件:单循环链表L存在*/
/*操作结果:依次对每个数据元素调用函数visit()*/
void ListTraverse(LinkList L,void(*visit)(ElemType))
单向链表操作基本实现:
构造一个空的线性表L
/*操作结果:构造一个空的线性表L*/
void InitList(LinkList &L)
{
L=(LinkList)malloc(sizeof(LNode)); //产生头结点,并使L指向此头结点
if(!L){//空的线性表构造失败
printf("空的线性表构造失败,退出程序!\n");
exit(0);
}
L->next=L; //指针域指向头结点
}
摧毁单循环链表L
/*初始条件:单循环链表L存在*/
/*操作结果:摧毁单循环链表L*/
void DestroyList(LinkList &L)
{
LinkList q;
LinkList p=L->next; //p指向头结点
while(p!=L) //没到表尾
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
}
将L重置为空表
/*初始条件:单循环链表L存在*/
/*操作结果:将L重置为空表*/
Status ClearList(LinkList &L)
{
LinkList p,q;
L=L->next; //L指向头结点
p=L->next; //p指向第一个结点
while(p!=L) //没到表尾
{
q=p->next;
free(p);
p=q;
}
L->next=L; //头结点指针域指向自身
}
对线性表进行判空
/*初始条件:单循环链表L存在*/
/*操作结果:若L为空表,则返回TRUE,否则返回FALSE*/
Status ListEmpty(LinkList L)
{
if(L->next==L) //线性表为空表
return TRUE;
else
return FALSE;
}
返回表长
/*初始条件:单循环链表L存在*/
/*操作结果:返回L中数据元素个数*/
int ListLength(LinkList L)
{
int i=0;
LinkList p=L->next; //p指向头结点
while(p!=L) //没到表尾
{
i++;
p=p->next;
}
return i;
}
求链表位序结点
/*初始条件:单循环链表L存在*/
/*操作结果:当第i个元素存在时,其值赋给e并返回OK,否则返回FALSE。*/
Status GetElem(LinkList L,int i,ElemType &e)
{
int count=1;
LinkList p=L->next->next; //p指向第一个结点
if(i<=0||i>ListLength(L)) //第i个元素不存在时
return ERROR;
while(count
next;
count++;
}
e=p->data; //取第i个元素
return OK;
}
求链表结点位序
/*初始条件:单循环链表L存在,compare()是数据元素判定的函数*/
/*操作结果