双向循环链表的增删改查功能-Toy模板网

这篇具有很好参考价值的文章主要介绍了双向循环链表的增删改查功能。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。
数据结构

双向循环链表

双向循环链表的增删改查
/*****************************************************************************************************************
*	
*	file name	:	DoubleCirLinkedList.c
*	author	 	:	cnzycwp@126.com
*	data  	 	:	2024/04/24
*	function	:	双向循环链表的接口程序
*	note	 	:	None
* 	
*  	CopyRight (c)	2024	cnzycwp@126.com 	All Right Reseverd
*
* ****************************************************************************************************************/

#include<stdio.h>
#include<stdbool.h>
#include<stdlib.h>
#include<string.h>

//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int  DataType_t;

//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{
	DataType_t  		     data; //结点的数据域
	struct DoubleLinkedList	*prev; //直接前驱的指针域
	struct DoubleLinkedList	*next; //直接后继的指针域

}DoubleLList_t;


//创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
DoubleLList_t * DoubleCirLList_Create(void)
{
	//1.创建一个头结点并对头结点申请内存
	DoubleLList_t *Head = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

	//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”
	Head->prev = Head;
	Head->next = Head;

	//3.把头结点的地址返回即可
	return Head;
}

//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
DoubleLList_t * DoubleCirLList_NewNode(DataType_t data)
{
	//1.创建一个新结点并对新结点申请内存
	DoubleLList_t *New = (DoubleLList_t *)calloc(1,sizeof(DoubleLList_t));
	if (NULL == New)
	{
		perror("Calloc memory for NewNode is Failed");
		return NULL;
	}

	//2.对新结点的数据域和指针域（2个）进行初始化,指针域指向结点自身，体现“循环”
	New->data = data;
	New->prev = New;
	New->next = New;

	return New;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_HeadInsert
*	function	:	把新结点插入双向循环链表中的头部
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//头插
bool DoubleCirLLinst_HeadInsert(DoubleLList_t *Head,DataType_t data)
{
	//1.创建新结点，并对新结点进行初始化
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("Can not insert new node\n");
		return false;
	}
	
	//2.判断循环双向链表是否为空，如果为空，则直接插入即可
	if (Head->next == Head)
	{
		Head->next = New;
		return true;
	}
	
	//3.如果循环双向链表为非空，则把新结点插入链表头部
	Head->next->prev->next = New;	//把尾结点的next指针指向新结点

	New->prev = Head->next->prev;	//把新结点的prev指针指向尾结点

	New->next = Head->next;			//把新结点的next指针指向原本首结点

	Head->next->prev = New;			//把原本首结点的prev指针指向新结点

	Head->next = New;				//把头结点的next指针指向新结点
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_TailInsert
*	function	:	把新结点插入双向循环表链中的尾部
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//尾插
bool DoubleCirLLinst_TailInsert(DoubleLList_t *Head,DataType_t data)
{
	//1.创建新结点，并对新结点进行初始化
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("Can not insert new node\n");
		return false;
	}
	
	//2.判断循环双向链表是否为空，如果为空，则直接插入即可
	if (Head->next == Head)
	{
		Head->next = New;
		return true;
	}

	//3.如果循环双向链表为非空，则把新结点插入链表头部
	New->prev= Head->next->prev;	//把新结点的prev指针指向原本的尾结点

	Head->next->prev->next = New;	//把原本的尾结点的next指针指向新结点

	New->next = Head->next;			//把新结点的next指针指向首结点

	Head->next->prev = New;			//把首结点的prev指针指向新结点
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_DestInsert
*	function	:	把新结点插入双向循环链表中的指定元素的尾部
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//指定插
bool DoubleCirLLinst_DestInsert(DoubleLList_t *Head,DataType_t destval,DataType_t data)
{
	//1.创建新结点，并对新结点进行初始化
	DoubleLList_t *New = DoubleCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("Can not insert new node\n");
		return false;
	}
	
	//2.判断循环双向链表是否为空，如果为空，则直接插入即可
	if (Head->next == Head)
	{
		Head->next = New;
		return true;
	}

	//3.如果循环双向链表为非空，则把新结点插入链表中指定元素的尾部
	DoubleLList_t *Phead = Head->next;	//备份首结点地址，防止首结点丢失
	while (Phead->next != Head->next)
	{	
		if (Phead->data == destval)
		{
			break;
		}
		Phead = Phead->next;
	}

	//如果遍历链表之后发现没有目标结点，则退出即可
	if (Phead->next == Head->next && Phead->data != destval)
	{
		printf("dest node is not found\n");
		return false;
	}
	
	//如果遍历链表找到目标结点，则分为(头部 or 尾部 or 中间)

	// if (Phead == Head->next)
	// {
	// 	New->prev = Head->next;		//把新结点的prev指针指向首结点

	// 	New->next = Head->next;		//把新结点的next指针指向首结点

	// 	Head->next->next = New;		//把首结点的next指针指向新结点

	// 	Head->next->prev = New;		//把首结点的prev指针指向新结点

	//	}
	if (Phead->next == Head->next)
	{
		New->next = Head->next;		//把新结点的next指针指向首结点

		New->prev = Phead;			//把新结点的prev指针指向原本的尾结点

		Phead->next = New;			//把原本的尾结点的next指针指向新结点

		Head->next->prev = New;		//把首结点的prev指针指向新结点
	}else
	{
		New->next = Phead->next;	//把新结点的next指针指向指定结点的直接后继

		Phead->next->prev = New;	//把指定结点的直接后继的prev指针指向新结点

		New->prev = Phead;			//把新结点的prev指针指向指定节点
	
		Phead->next = New;			//把指定节点的next指针指向新结点
	}
	
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_HeadDel
*	function	:	删除双向循环链表的头部结点
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//头删
bool DoubleCirLLinst_HeadDel(DoubleLList_t *Head)
{
	//1.判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkedlist is empty!\n");
		return false;
	}

	//2.判断链表中是否只有首结点
	if (Head->next == Head->next->next)
	{
		Head->next = Head;	//头结点的next指针指向头结点，体现“循环”

		free(Head->next);	//释放首结点内存

		return true;
	}
	

	//3.如果当前链表为非空，则删除当前链表的头部结点
	DoubleLList_t *Phead = Head->next;			//备份首结点地址
	
	Head->next->prev->next = Head->next->next;	//把尾结点的next指针指向首结点的直接后继

	Head->next->next->prev = Head->next->prev;	//把首结点的直接后继的prev指针指向尾结点

	Head->next =Phead->next;					//把头结点的next指针指向首结点的直接后继
	
	Phead->next = Phead;						//把首结点的next指针指向首结点

	Phead->prev = Phead;						//把首结点的prev指针指向首结点
	
	free(Phead);								//释放首结点内存

	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_TailDel
*	function	:	删除双向循环链表的尾部结点
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//尾删
bool DoubleCirLLinst_TailDel(DoubleLList_t *Head)
{
	//1.判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}

	//2.判断链表中是否只有首结点
	if (Head->next == Head->next->next)
	{
		Head->next = Head;	//头结点的next指针指向头结点，体现“循环”

		free(Head->next);	//释放首结点内存

		return true;
	}

	//3.如果当前链表为非空，则删除当前链表的尾部结点
	DoubleLList_t *Phead = Head->next->prev;	//备份尾结点地址

	Head->next->prev->prev->next = Head->next;	//把尾结点的直接前驱的next指针指向首结点

	Head->next->prev = Head->next->prev->prev;	//把首结点的prev指针指向尾结点的直接前驱

	Phead->next = Phead;						//把尾结点的next指针指向尾结点

	Phead->prev = Phead;						//把尾结点的prev指针指向尾结点

	free(Phead);								//释放尾结点内存

	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_DestDel
*	function	:	删除双向循环链表的指定结点
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//指定删
bool DoubleCirLLinst_DestDel(DoubleLList_t *Head,DataType_t destval)
{
	//1.判断当前链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		return false;
	}

	//2.判断链表中是否只有首结点
	if (Head->next == Head->next->next)
	{
		Head->next = Head;	//头结点的next指针指向头结点，体现“循环”

		free(Head->next);	//释放首结点内存

		return true;
	}

	//3.如果当前链表为非空，则删除当前链表的指定结点
	DoubleLList_t *Phead = Head->next;	//备份首结点地址
	while (Phead->next != Head->next)
	{
		if (Phead->data == destval)
		{
			break;
		}
		Phead = Phead->next;
	}

	//如果遍历链表之后发现没有目标结点，则退出即可
	if (Phead->next == Head->next && Phead->data != destval)
	{
		printf("dest node is not found\n");
		return false;
	}

	//如果遍历链表找到目标结点，则分为(头部 or 尾部 or 中间)
	if (Phead == Head->next)
	{
		
		Head->next->prev->next = Head->next->next;	//把尾结点的next指针指向首结点的直接后继

		Head->next->next->prev = Head->next->prev;	//把首结点的直接后继的prev指针指向尾结点

		Head->next = Head->next->next; 				//把头结点的next指针指向首结点的直接后继

		Phead->next = Phead;						//把首结点的next指针指向首结点

		Phead->prev = Phead;						//把首结点的prev指针指向首结点

		
		free(Phead);								//释放首结点内存

	}else if (Phead->next == Head->next)
	{
		Phead->prev->next = Head->next;		//把尾结点的直接前驱的next指针指向首结点

		Head->next->prev = Phead->prev;		//把首结点的prev指针指向尾结点的直接前驱

		Phead->next = Phead;				//把尾结点的next指针指向尾结点

		Phead->prev = Phead;				//把尾结点的prev指针指向尾结点

		free(Phead);						//释放尾结点内存

	}else
	{
		Phead->prev->next = Phead->next;	//把指定结点的直接前驱的next指针指向指定结点的直接后继

		Phead->next->prev = Phead->prev;	//把指定结点的直接后继的prev指针指向指定结点的直接前驱

		Phead->next = Phead;				//把指定结点的next指针指向指定结点

		Phead->prev = Phead;				//把指定结点的prev指针指向指定结点

		free(Phead);						//释放指定结点的内存
	}
	
	return true;
}

/******************************************************************************************************************
*	
*	func name	:	DoubleCirLLinst_Print
*	function	:	遍历双向循环链表并输出链表中的数据域
*	retval		:	bool
*	note		:	None
*	author	 	:	cnzycwp@126.com
*	date  	 	:	2024/04/24
*
* ****************************************************************************************************************/

//遍历双向循环链表
bool DoubleCirLLinst_Print(DoubleLList_t *Head)
{
	//1.判断当前双向循环链表是否为空，为空则直接退出
	if (Head->next == Head)
	{
		printf("current linkeflist is empty!\n");
		
		return false;
	}
	//2.从首结点开始遍历链表
	DoubleLList_t *Phead = Head;	 //备份头结点地址，防止头结点丢失
	while (Phead->next)
	{
		Phead = Phead->next;		 //把头结点的直接后继作为新的头结点

		printf("%d->",Phead->data);	 //输出头结点的直接后继的数据域

		if (Phead->next == Head->next)//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
		{
			break;
		}
		
	}
	return true;
	
}

int main(int argc, char const *argv[])
{
	//创建双向循环链表
	DoubleLList_t *Head = DoubleCirLList_Create();

	//头插
	DoubleCirLLinst_HeadInsert(Head,5);
	DoubleCirLLinst_HeadInsert(Head,56);
	DoubleCirLLinst_HeadInsert(Head,35);
	DoubleCirLLinst_HeadInsert(Head,20);
	DoubleCirLLinst_HeadInsert(Head,8);
	DoubleCirLLinst_Print(Head);
	printf("\n");

	// //尾插
	DoubleCirLLinst_TailInsert(Head,61);
	DoubleCirLLinst_TailInsert(Head,9);
	DoubleCirLLinst_TailInsert(Head,4);
	DoubleCirLLinst_TailInsert(Head,18);
	DoubleCirLLinst_TailInsert(Head,40);
	DoubleCirLLinst_Print(Head);
	printf("\n");

	//指定插
	DoubleCirLLinst_DestInsert(Head,5,21);
	DoubleCirLLinst_DestInsert(Head,40,89);
	DoubleCirLLinst_Print(Head);
	printf("\n");

	// 头删
	DoubleCirLLinst_HeadDel(Head);
	DoubleCirLLinst_HeadDel(Head);
	DoubleCirLLinst_Print(Head);
	printf("\n");
	
	// 尾删
	DoubleCirLLinst_TailDel(Head);
	DoubleCirLLinst_TailDel(Head);
	DoubleCirLLinst_Print(Head);
	printf("\n");
	
	// //指定删
	DoubleCirLLinst_DestDel(Head,5);
	DoubleCirLLinst_DestDel(Head,61);
	DoubleCirLLinst_Print(Head);
	printf("\n");


	return 0;
}
结果验证：
双向循环链表的增删改查功能文章来源地址https://www.toymoban.com/news/detail-858070.html