数据结构

双向循环链表

双向循环链表的增删改查

/*****************************************************************************************************************
*	
*	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;
}

结果验证：