目录

1.为什么要有循环链表

2.定义

3.循环链表和单链表的图示对比

4.循环链表和单链表的代码对比

5.循环链表的操作

1.clist.h

2.clist.cpp

1.初始化plist

2.往plist中头部插入数字val

3.往plist中的尾部插入数字val

4.在plist中查找val值,找到返回该节点地址,失败返回NULL

5.删除plist中的第一个val

6.判断plist是否为空链表(没有数据节点)

7.获取plist长度,数据节点的个数

8.获取plist链表的pos位置的值

9.获取val的前驱

10.获取val的后继

11.输出plist的所有数据

1.为什么要有循环链表

在单链表中我们是把结点遍历一遍后就结束了，为了使表处理更加方便灵活，我们希望通过任意一个结点出发都可以找到链表中的其它结点,因此我们引入了循环链表。

2.定义

将单链表中终端结点的指针端由空指针改为头结点，就使整个单链表形成了一个环，这种头尾相接的单链表称为循环链表。

简单理解就是形成一个闭合的环，在环内寻找自己需要的结点。

3.循环链表和单链表的图示对比

单链表：

 循环链表：

4.循环链表和单链表的代码对比

单链表：

typedef struct Node{ //定义单链表结点类型int data; //数据域，可以是别的各种数据类型struct Node *next; //指针域
}LNode, *LinkList;

循环链表：

typedef struct CNode//循环链表节点
{ElemType data;//数据struct CNode* next;//后继指针
}CNode ,*CList;

5.循环链表的操作

//带头结点的循环链表,其尾节点的后继为头结点(不是NULL)
//节点的结构和单链表一样

1.clist.h

#pragma oncetypedef int ElemType;typedef struct CNode//循环链表节点
{ElemType data;//数据struct CNode* next;//后继指针
}CNode ,*CList;//初始化plist
void InitList(CList plist);//往plist中头部插入数字val
bool Insert_head(CList plist, ElemType val);//往plist中的尾部插入数字val
bool Insert_tail(CList plist, ElemType val);//在plist中查找val值,找到返回该节点地址,失败返回NULL
CNode* Search(CList plist, ElemType val);//删除plist中的第一个val
bool DeleteVal(CList plist, ElemType val);//判断plist是否为空链表(没有数据节点)
bool IsEmpty(CList plist);//获取plist长度,数据节点的个数
int GetLength(CList plist);//获取plist链表的pos位置的值
bool GetElem(CList plist, int pos, int* rtval);//rtval:输出参数//获取val的前驱
CNode* Prior(CList plist, ElemType val);//获取val的后继
CNode* Next(CList plist, ElemType val);//输出plist的所有数据
void Show(CList plist);//清空数据
void Clear(CList plist);//销毁
void Destroy(CList plist);

2.clist.cpp

1.初始化plist

oid InitList(CList plist)
{assert(plist != NULL);if (plist == NULL)return;//数据域不使用plist->next = plist;
}

2.往plist中头部插入数字val

这里我们需要思考一下当链表为空时是否适用：这里明确告诉大家不管是否是空链表，这两行代码均可以使用，下面给大家用示意图表示一下；
不是空链：

 是空链：

bool Insert_head(CList plist, ElemType val)
{//1.动态申请一个新的节点CNode* p = (CNode*)malloc(sizeof(CNode));assert(p != NULL);if (p == NULL)return false;//2.把数据存放在新节点中p->data = val;//3.把新节点插入在头结点后面p->next = plist->next;plist->next = p;return true;
}

3.往plist中的尾部插入数字val

bool Insert_tail(CList plist, ElemType val)
{//1.创建新节点并赋值CNode* p = (CNode*)malloc(sizeof(CNode));assert(p != NULL);if (p == NULL)return false;p->data = val;//2.找到尾节点CNode* q;for (q = plist; q->next != plist; q = q->next);//3.插入新节点.把p插入在q的后面p->next = q->next;q->next = p;return true;
}

与单向链表的插入不同，循环单链表插入时只能往表头节点的后面插入，由初始结构可知，想完成插入操作，必须先找到要插入位置的前一个节点，然后修改相应指针即可完成操作。

4.在plist中查找val值,找到返回该节点地址,失败返回NULL

CNode* Search(CList plist, ElemType val)
{for (CNode* p = plist->next; p != plist; p = p->next){if (p->data == val)return p;}return NULL;
}

5.删除plist中的第一个val

bool DeleteVal(CList plist, ElemType val)
{CNode* p = Prior(plist, val);if (p == NULL)return false;CNode* q = p->next;//保存需要删除的节点p->next = q->next;//剔除qfree(q);//释放节点return true;
}

6.判断plist是否为空链表(没有数据节点)

bool IsEmpty(CList plist)
{return plist->next == plist;
}

7.获取plist长度,数据节点的个数

int GetLength(CList plist)
{int count = 0;//计数器for (CNode* p = plist->next; p != plist; p = p->next)count++;return count;
}

8.获取plist链表的pos位置的值

bool GetElem(CList plist, int pos, int* rtval)//rtval:输出参数
{if (pos < 0 || pos >= GetLength(plist))return false;CNode* p = plist->next;for (int i = 0; i < pos; i++){p = p->next;}*rtval = p->data;return true;
}

9.获取val的前驱

CNode* Prior(CList plist, ElemType val)
{for (CNode* p = plist; p->next != plist; p = p->next){if (p->next->data == val)return p;}return NULL;
}

10.获取val的后继

CNode* Next(CList plist, ElemType val)
{CNode* p = Search(plist,val);if (p == NULL)return NULL;return p->next;
}

11.输出plist的所有数据

void Show(CList plist)
{//从头到尾遍历数据节点for (CNode* p = plist->next; p != plist; p = p->next){printf("%d ",p->data);}printf("\n");
}

#include 
#include "clist.h"
//#include //需要安装vldint main()
{CNode head;//循环链表的表头节点InitList(&head);for (int i = 0; i < 10; i++){Insert_head(&head,i);//9 8 7 6 5 4 3 2 1 0Insert_tail(&head,i);//0,1,2,3,4,5,6,7,8,9}Show(&head);CNode* p;for (int i = -1; i < 12; i++){if ((p = Search(&head, i)) != NULL){printf("%d找到了\n",i);}else{printf("%d没有找到\n",i);}}//for (int i = -1; i < 11; i++)//{//	DeleteVal(&head,i);//}int val;GetElem(&head,3,&val);printf("%d\n",val);Show(&head);Destroy(&head);//Destroy(&head);return 0;
}