循环链表的增删改查

发表评论

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

2015-05-28_190050

一种是上面我们说的，而另外一种，则是将尾节点的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
{
	//循环链表头结点
	CircleListNode	header;
	//循环链表游标
	CircleListNode	*slider;
	//循环链表长度
	int				length;
}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)
{
	int				i;
	//定义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)
{
	int				i;
	//定义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)
{
	int			i;
	int			nPos = 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、普通插入元素（和单链表是一样的）

2015-05-28_213356

2、尾插法（和单链表是一样的，单链表的写法支持尾插法；
分析：辅助指针向后跳length次，指向最后面那个元素（length-1位置），因为是循环
链表，所以length位置元素即为第一个数据节点。）

2015-05-28_213402

3、头插法
要进行头插法，需要求出尾节点，连接新的0号位置节点
第一次插入元素时，让游标指向0号结点（即第一个数据节点）

2015-05-28_213408

4、第一次插入元素（相当于头插法）
求出尾节点，尾节点指针指向第一个数据节点（即自己指向自己）

2015-05-28_213426

【删除节点】

1、删除普通结点

2015-05-28_213433

2、删除头结点（删除0号位置处元素），需要求出尾结点，连接新的零号位置节点

2015-05-28_213437

以上便是针对循环链表的操作详细介绍，其对比单向链表来看，不但增强了功能，有了游标使遍历更加方便了。但是缺点是点吗的复杂度少有提高，不太好理解。不过完全可以替换掉单向链表了。

发表评论