循环链表的增删改查

循环链表与单向链表十分相似，两者唯一不同之处就是，循环链表的尾节点的next属性指向了链表的首节点（非头节点，头节点是没有数据的，头节点的下一个有数据的节点我们称为首节点）。他的表现形式有常见的两种，如下图：

一种是上面我们说的，而另外一种，则是将尾节点的next指向了头节点，这种做法不是方便，所以用的比较少，并不是不可用。 在循环链表中，我们增加了一个新的功能“游标”，在循环链表中可以定义一个“当前”指针，这个指针通常称为游标，可以通过这个游标来遍历链表中的所有元素，而我们不需要去动头节点的指针指向。以下为循环链表的增删改查操作，同样，我们使用了数据类型与算法分离的思路编写了代码（以下代码出自 传智播客 教师课件）

#ifndef _CIRCLE_LIST_H
#define _CIRCLE_LIST_H

//自定义循环链表数据类型
typedef void CircleList;
//自定义循环链表节点数据类型
typedef struct tag_CirclListNode
{
struct tag_CirclListNode *next;
}CircleListNode;

//创建循环链表
CircleList* CircleList_Create();

//销毁循环链表
void CircleList_Destroy(CircleList* list);

//清空循环链表
void CircleList_Clear(CircleList* list);

//获取循环链表长度
int CircleList_Length(CircleList* list);

//在循环链表中插入新节点
int CircleList_Insert(CircleList* list, CircleListNode* node, int pos);

//获取循环链表中的指定位置的节点
CircleListNode* CircleList_Get(CircleList* list, int pos);

//删除循环链表中的指定位置的节点
CircleListNode* CircleList_Delete(CircleList* list, int pos);

//—————— new add ——————

//直接指定删除链表中的某个数据元素
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node);

//将游标重置指向链表中的第一个数据元素
CircleListNode* CircleList_Reset(CircleList* list);

//获取当前游标指向的数据元素
CircleListNode* CircleList_Current(CircleList* list);

//将游标移动指向到链表中的下一个数据元素
CircleListNode* CircleList_Next(CircleList* list);

#endif //_CIRCLE_LIST_H

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “CircleList.h”

//创建结构体管理链表
typedef struct tag_CircleList
{
//循环链表头结点
CircleListNodeheader;
//循环链表游标
CircleListNode*slider;
//循环链表长度
intlength;
}TCircleList;

//创建循环链表
CircleList* CircleList_Create()
{
//定义TCircleList指针变量,并分配内存空间
TCircleList* tlist = (TCircleList*)malloc(sizeof(TCircleList));
if (tlist == NULL)
{
printf(“error: TCircleList* tlist = (TCircleList*)malloc(sizeof(TCircleList)) \n”);
return NULL;
}
//数据初始化
tlist->header.next = NULL;
tlist->slider = NULL;
tlist->length = 0;

return (CircleList*)tlist;
}

//销毁循环链表
void CircleList_Destroy(CircleList* list)
{
//定义TCircleList指针变量
TCircleList *tlist = NULL;
//判断list是否为有效指针
if (list == NULL)
{
printf(“Destory error: list 为无效指针\n”);
return;
}
free(list);
}

//清空循环链表
void CircleList_Clear(CircleList* list)
{
//定义TCircleList指针变量
TCircleList *tlist = NULL;
//判断list是否为有效指针
if (list == NULL)
{
printf(“Clear error: list 为无效指针\n”);
return;
}
//类型转换并赋值
tlist = (TCircleList*)list;
//将长度重置为0
tlist->length = 0;
//头结点指针域指向空
tlist->header.next = NULL;
//游标指向空
tlist->slider = NULL;
}

//获取循环链表长度
int CircleList_Length(CircleList* list)
{
//定义TCircleList指针变量
TCircleList *tlist = NULL;
//判断list是否为有效指针
if (list == NULL)
{
printf(“Length error: list 为无效指针\n”);
return -1;
}
//类型转换并赋值
tlist = (TCircleList*)list;

return tlist->length;
}

//在循环链表中插入新节点
int CircleList_Insert(CircleList* list, CircleListNode* node, int pos)
{
int i;
//定义TCircleList指针变量
TCircleList*tlist = NULL;
//定义辅助指针变量
CircleListNode*currentNode = NULL;
//判断list是否为有效指针
if (list == NULL node == NULL pos < 0)
{
printf(“Insert error: if (list == NULL node == NULL pos < 0)\n”);
return -1;
}
//类型转换并赋值
tlist = (TCircleList*)list;

//元素插入
//step 1: 使用辅助指针变量,指向头结点
currentNode = &tlist->header;
//step 2: 找到pos-1位置节点
for (i = 0; i < pos; ++i)
{
//判断是否有后继节点
if (currentNode->next != NULL)
{
//指针后移
currentNode = currentNode->next;
}
else
{
//没有后继节点跳出循环
break;
}
}
//step 3: 将node节点的指针指向当前节点(pos-1)的后继节点(pos)
node->next = currentNode->next;
//step 4: 当前节点的指针指向node节点的地址
currentNode->next = node;
//step 5: 如果是第一次插入节点
if (tlist->length == 0)
{
//将游标指向新插入节点
tlist->slider = node;
}
//step 6: 链表长度加1
tlist->length++;
//step 7:若头插法 currentNode仍然指向头部
//原因: 跳0步, 没有跳走
if (currentNode == &tlist->header)
{
CircleListNode* lastNode = CircleList_Get(list, tlist->length - 1);
//最后一个节点的指针,指向第一个数据节点
lastNode->next = currentNode->next;
}
return 0;
}

//获取循环链表中的指定位置的节点
CircleListNode* CircleList_Get(CircleList* list, int pos)
{
inti;
//定义TCircleList指针变量
TCircleList*tlist = NULL;
//定义辅助指针变量
CircleListNode*currentNode = NULL;
//判断list是否为有效指针
if (list == NULL pos < 0)
{
printf(“CircleList_Get error: if (list == NULL pos < 0)\n”);
return NULL;
}
//类型转换并赋值
tlist = (TCircleList*)list;

//step 1: 使用辅助指针变量,指向头结点
currentNode = &tlist->header;
//step 2: 找到pos位置节点
for (i = 0; i <= pos; ++i)
{
//判断是否有后继节点
if (currentNode->next != NULL)
{
//指针后移
currentNode = currentNode->next;
}
else
{
//没有后继节点跳出循环
printf(“error: 没找到指定位置的元素\n”);
return NULL;
}
}

return currentNode;
}

//删除循环链表中的指定位置的节点
//——————————-
CircleListNode* CircleList_Delete(CircleList* list, int pos)
{
inti;
//定义TCircleList指针变量
TCircleList*tlist = NULL;
//定义链表节点指针,保存要删除的节点地址
CircleListNode*deleteNode = NULL;
//定义链表节点指针,保存最后一个节点
CircleListNode *lastNode = NULL;
//定义辅助指针变量
CircleListNode *currentNode = NULL;

//判断list是否为有效指针
if (list == NULL pos < 0)
{
printf(“CircleList_Delete error: if (list == NULL pos < 0)\n”);
return NULL;
}
//类型转换并赋值
tlist = (TCircleList*)list;
//判断链表中是否有节点
if (tlist->length <= 0)
{
printf(“error: 链表为空,不能删除\n”);
return NULL;
}

//元素删除
//step 1: 辅助指针变量,指向头结点
currentNode = &tlist->header;
//step 2: 找到pos-1位置节点
for (i = 0; i < pos; ++i)
{
//指针后移
currentNode = currentNode->next;
}
//step 3: 保存要删除的节点的地址
deleteNode = currentNode->next;
//step 4-1: 判断删除的元素是否为第一个元素
if (currentNode == &tlist->header)
{
//step 4-2: 找到最后一个节点
lastNode = CircleList_Get(list, tlist->length - 1);
}
//step 4-3: 判断lastNode是否为空
if (lastNode != NULL)
{
//step 4-4: 将最后一个节点的地址指向要删除节点的后继节点
lastNode->next = deleteNode->next;
}
//step 4-5: 将头结点的指针指向要删除节点的后继节点
currentNode->next = deleteNode->next;
//step 5: 链表长度减1
tlist->length–;
//step 6-1: 判断删除的元素是否为游标指向的元素
if (tlist->slider == deleteNode)
{
//step 6-2: 游标后移
tlist->slider = deleteNode->next;
}
//step 7-1: 判断删除元素后,链表长度是否为零
if (tlist->length == 0)
{
//step 7-2: 链表头结点指针域指向空
tlist->header.next = NULL;
//step 7-3: 链表游标指向空
tlist->slider = NULL;
}

return deleteNode;
}

//—————— new add ——————

//直接指定删除链表中的某个数据元素
CircleListNode* CircleList_DeleteNode(CircleList* list, CircleListNode* node)
{
inti;
intnPos = 0;
//定义TCircleList指针变量
TCircleList *tlist = NULL;
//判断list是否为有效指针
if (list == NULL node == NULL)
{
printf(“CircleList_DeleteNode error: if (list == NULL node == NULL)\n”);
return NULL;
}
//类型转换并赋值
tlist = (TCircleList*)list;

//定义辅助指针变量,指向头结点
CircleListNode* currentNode = &tlist->header;
//定义辅助指针变量,用来保存要删除的节点地址
CircleListNode* delNode = NULL;
//查找node节点在循环链表中的位置
for (i = 0; i < tlist->length; ++i)
{
//从第一个数据节点开始判断,查找等于node的节点
if (currentNode->next == node)
{
//保存与node节点相等的节点的位置
nPos = i;
//保存要删除的节点地址
delNode = currentNode->next;
//跳出循环
break;
}
//当前节点指针后移
currentNode = currentNode->next;
}
//如果找到delNode,根据nPos删除该节点
if (delNode != NULL)
{
//删除指定位置的元素
CircleList_Delete(list, nPos);
}

return delNode;
}

//将游标重置指向链表中的第一个数据元素
CircleListNode* CircleList_Reset(CircleList* list)
{
//定义TCircleList指针变量
TCircleList *tlist = NULL;
//判断list是否为有效指针
if (list == NULL)
{
printf(“CircleList_Reset error: if (list == NULL)\n”);
return NULL;
}
//类型转换并赋值
tlist = (TCircleList*)list;
//重置游标位置
tlist->slider = tlist->header.next;

return tlist->slider;
}

//获取当前游标指向的数据元素
CircleListNode* CircleList_Current(CircleList* list)
{
//定义TCircleList指针变量
TCircleList *tlist = NULL;
//判断list是否为有效指针
if (list == NULL)
{
printf(“CircleList_Current error: if (list == NULL)\n”);
return NULL;
}
//类型转换并赋值
tlist = (TCircleList*)list;

return tlist->slider;
}

//将游标移动指向到链表中的下一个数据元素
CircleListNode* CircleList_Next(CircleList* list)
{
//定义链表节点指针变量
CircleListNode*currNode = NULL;
//定义TCircleList指针变量
TCircleList*tlist = NULL;
//判断list是否为有效指针
if (list == NULL)
{
printf(“CircleList_Next error: if (list == NULL)\n”);
return NULL;
}
//类型转换并赋值
tlist = (TCircleList*)list;
//存储当前游标位置
currNode = tlist->slider;

//判断当前游标是否指向空
if (tlist->slider != NULL)
{
//游标后移
tlist->slider = currNode->next;
}

return currNode;
}

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include “CircleList.h”

typedef struct tag_value
{
CircleListNode circleNode;
int v;
}Value;

int main()
{
int i;
//定义Value结构体数组
Value val[10];//创建循环链表
CircleList* list = CircleList_Create();

//循环初始化数组
for (i = 0; i < sizeof(val) / sizeof(Value); ++i)
{
val[i].v = i + 20;
//往循环链表中插入数据
CircleList_Insert(list, (CircleListNode*)&val[i], i);
}
//遍历循环链表
//************* 怎么证明是循环链表? *************
for (i = 0; i < CircleList_Length(list) * 2; ++i)//打印两遍
{
Value *pVal = (Value*)CircleList_Get(list, i);
printf(“Value %d = %d\n”, i, pVal->v);
}
//删除节点
while (CircleList_Length(list) > 0)
{
Value *pVal = (Value*)CircleList_Delete(list, 0);
printf(“Delete Value: val = %d\n”, pVal->v);
}
//销毁循环链表
CircleList_Destroy(list);

return 0;
}

最后我们详细分析一下循环链表中，插入数据和删除数据时具体步骤的图解，这样有助于我们有深刻的理解。（大部分内容源自 传智播客 教师课件） 【插入元素】 插入元素分很多中情况，如在中间插入元素、在尾部插入元素、在头部插入元素、首次插入元素，下面我们分别来看一下。 1、普通插入元素（和单链表是一样的） 2、尾插法（和单链表是一样的，单链表的写法支持尾插法； 分析：辅助指针向后跳length次，指向最后面那个元素（length-1位置），因为是循环 链表，所以length位置元素即为第一个数据节点。） 3、头插法 要进行头插法，需要求出尾节点，连接新的0号位置节点 第一次插入元素时，让游标指向0号结点（即第一个数据节点） 4、第一次插入元素（相当于头插法） 求出尾节点，尾节点指针指向第一个数据节点（即自己指向自己） 【删除节点】 1、删除普通结点 2、删除头结点（删除0号位置处元素），需要求出尾结点，连接新的零号位置节点 以上便是针对循环链表的操作详细介绍，其对比单向链表来看，不但增强了功能，有了游标使遍历更加方便了。但是缺点是点吗的复杂度少有提高，不太好理解。不过完全可以替换掉单向链表了。