双向循环链表的接口

双向循环链表的接口

头文件

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

创建链表、节点

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

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

} DoubleCircLList_t;

/********************************************************************
 *
 *	name	 :	DoubleCircLList_HeadInsert
 *	function :  创建一个空双向循环链表,空链表应该有一个头结点,对链表进行初始化
 *	argument :
 *				@data:节点需存储的数据
 *	retval	 :  返回新创建链表头节点的地址
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :	None
 *
 * *****************************************************************/

DoubleCircLList_t *DoubleCircCirLList_Create(void)
{
	// 1.创建一个头结点并对头结点申请内存
	DoubleCircLList_t *Head = (DoubleCircLList_t *)calloc(1, sizeof(DoubleCircLList_t));
	if (NULL == Head)
	{
		perror("Calloc memory for Head is Failed");
		exit(-1);
	}

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

	// 3.把头结点的地址返回即可
	return Head;
}
/********************************************************************
 *
 *	name	 :	DoubleCircLList_HeadInsert
 *	function :  创建新的结点,并对新结点进行初始化(数据域 + 指针域)
 *	argument :
 *				@data:节点需存储的数据
 *	retval	 :  返回新创建节点的地址
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :	None
 *
 * *****************************************************************/

DoubleCircLList_t *DoubleCircCirLList_NewNode(DataType_t data)
{
	// 1.创建一个新结点并对新结点申请内存
	DoubleCircLList_t *New = (DoubleCircLList_t *)calloc(1, sizeof(DoubleCircLList_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;
}
​```

三种插入方式

在链表的头部插入

/********************************************************************
 *
 *	name	 :	DoubleCircLList_HeadInsert
 *	function :  向链表的头部进行数据插入
 *	argument :	@head:目标链表
 *				@data:需插入的数据
 *	retval	 :  返回新创建链表节点的地址
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :	None
 *
 * *****************************************************************/
bool DoubleCircLList_HeadInsert(DoubleCircLList_t *Head, DataType_t data)
{
	// 备份头节点
	DoubleCircLList_t *Phead = Head;
	// 1.创建新的结点,并对新结点进行初始化
	DoubleCircLList_t *New = DoubleCircCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}
	// 2.判断链表是否为空,如果为空,则直接插入即可
	if (Head == Head->next)
	{
		Head->next = New;
		return true;
	}
	// 3.如果链表为非空,则把新结点插入到链表的头部
	Phead->next->prev->next = New; // 尾结点指向新的首节点
	New->prev = Phead->next->prev; // 新节点指向尾结点
	New->next = Phead->next;	   // 新节点指向原来的首节点
	Phead->next->prev = New;	   // 原首节点指向新节点
	Head->next = New;			   // 头结点指向新节点
	return true;
}
​```

在链表的尾部插入

/********************************************************************
 *
 *	name	 :	DoubleCircLList_TailInsert
 *	function :  向链表的尾部进行数据插入
 *	argument :	@head:目标链表
 *				@data:需插入的数据
 *	retval	 :  返回1成功0失败
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :	None
 *
 * *****************************************************************/

bool DoubleCircLList_TailInsert(DoubleCircLList_t *Head, DataType_t data)
{
	// 备份首节点
	DoubleCircLList_t *Phead = Head->next;
	// 1.创建新的结点,并对新结点进行初始化
	DoubleCircLList_t *New = DoubleCircCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}
	// 2.判断链表是否为空,如果为空,则直接插入即可
	if (Head == Head->next)
	{
		Head->next = New;
		return true;
	}
	// 3.如果链表为非空,则把新结点插入到链表的尾部

	Phead->prev->next = New; // 尾结点指向新节点
	New->prev = Phead->prev; // 新节点指向尾结点
	New->next = Head->next;	 // 新节点指向首节点
	Phead->prev = New;		 // 首节点指向新节点
	return true;
}
​```

在链表指定数据节点后插入

/********************************************************************
 *
 *	name	 :	DoubleCircLList_DestInsert
 *	function :  向链表的指定节点数据的节点后进行插入
 *	argument :	@head:目标链表
 *				@data:需插入的数据
 *				@dest:插入位置
 *	retval	 :  返回1成功0失败
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :	None
 *
 * *****************************************************************/

bool DoubleCircLList_DestInsert(DoubleCircLList_t *Head, DataType_t destval, DataType_t data)
{
	// 备份头节点
	DoubleCircLList_t *Phead = Head;
	// 备份首节点
	DoubleCircLList_t *Temp = Head->next;
	// 1.创建新的结点,并对新结点进行初始化
	DoubleCircLList_t *New = DoubleCircCirLList_NewNode(data);
	if (NULL == New)
	{
		printf("can not insert new node\n");
		return false;
	}
	// 目标数据在头部
	if (destval == Phead->next->data)
	{
		DoubleCircLList_HeadInsert(Head, data);
		return true;
	}
	// 找目标数据
	DoubleCircLList_t *P = NULL; // 定义变量保存找的目标数据的节点地址
	while (Head->next != Temp->next)
	{
		Temp = Temp->next;
		if (destval == Temp->data)
		{
			P = Temp;
			break;
		}
	}
	// 找不到目标数据
	if (NULL == P)
	{
		perror("The target data cannot be found\n");
		return false;
	}
	// 目标数据在尾部
	if (Head->next == P->next)
	{
		DoubleCircLList_TailInsert(Head, data);
	}
	// 节点在中间开始插入
	else
	{
		P->next->prev = New; // 目标节点的后继指向新节点
		New->next = P->next; // 新节点指向目标节点的后继
		P->next = New;		 // 目标节点指向新节点
		New->prev = P;		 // 新节点指向目标节点
	}
	return true;
}
​```

三种删除方式

删除链表头部的节点

/********************************************************************
 *
 *	name	 :	DoubleCircLList_HeadDel
 *	function :  头删
 *	argument :	@head:目标链表
 *
 *	retval	 :  返回1成功0失败
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :	None
 *
 * *****************************************************************/

bool DoubleCircLList_HeadDel(DoubleCircLList_t *Head)
{
	// 备份首节点地址
	DoubleCircLList_t *Phead = Head;
	// 备份头节点地址
	DoubleCircLList_t *Temp = Head->next;
	// 1.判断链表是否为空,如果为空
	if (Head == Head->next)
	{
		perror("Linked lists have no data\n");
		return false;
	}
	// 链表只有一首个节点
	if (Head->next == Head->next->next)
	{
		Temp->next = NULL; // 释放尾指针
		Temp->prev = NULL; // 释放首指针
		Head->next = Head; // 头指针重新指向
		free(Temp);		   // 释放堆内存
	}
	// 删除原首节点
	else
	{
		Temp->prev->next = Temp->next; // 尾结点指向二节点
		Temp->next->prev = Temp->prev; // 二节点指向尾节点
		Head->next = Head->next->next; // 头节点指向二节点
		Temp->next = NULL;			   // 原首节点尾指针释放
		Temp->prev = NULL;			   // 原首节点首指针释放
		free(Temp);
	}
	return true;
}
​```

删除链表尾部的节点

/********************************************************************
 *
 *	name	 :	DoubleCircLList_TailDel
 *	function :  尾删
 *	argument :	@head:目标链表
 *				@data:需删除的数据
 *
 *	retval	 :  返回1成功0失败
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :	None
 *
 * *****************************************************************/
bool DoubleCircLList_TailDel(DoubleCircLList_t *Head)
{
	// 备份首节点地址
	DoubleCircLList_t *Phead = Head->next;
	// 备份尾节点地址
	DoubleCircLList_t *Tail = Head->next->prev;
	// 1.判断链表是否为空,如果为空
	if (Head == Head->next)
	{
		perror("Linked lists have no data\n");
		return false;
	}
	// 链表只有一首个节点
	if (Head->next == Head->next->next)
	{
		Phead->next = NULL; // 释放尾指针
		Phead->prev = NULL; // 释放首指针
		Phead = Head;		// 头指针重新指向
		free(Phead);		// 释放堆内存
	}
	// 删除链表尾部节点
	Tail->prev->next = Head->next; // 尾结点前驱指向首节点
	Head->next->prev = Tail->prev; // 首节点指向尾结点前驱
	Tail->prev = NULL;			   // 尾结点首指针释放
	Tail->next = NULL;			   // 尾结点尾指针释放
	free(Tail);					   // 释放尾结点堆内存
	return true;
}
​```

删除链表指定数据节点后的节点

/********************************************************************
 *
 *	name	 :	DoubleCircLList_Del
 *	function :  中删
 *	argument :	@head:目标链表
 *				@data:需删除的数据
 *
 *	retval	 :  返回1成功0失败
 *	author	 :  [email protected]
 *	date	 :  2024-4-24
 * 	note	 :
 *
 * *****************************************************************/
bool DoubleCircLList_Del(DoubleCircLList_t *Head, DataType_t data)
{
	// 备份首节点地址
	DoubleCircLList_t *Phead = Head;
	// 备份头节点地址
	DoubleCircLList_t *Temp = Head->next;
	// 1.判断链表是否为空,如果为空
	if (Head == Head->next)
	{
		perror("Linked lists have no data\n");
		return false;
	}
	// 删除的节点在头
	if (data == Head->next->data)
	{
		DoubleCircLList_HeadDel(Head);
		return true;
	}
	// 遍历找的目标数据节点
	DoubleCircLList_t *P = NULL; // 定义变量保存找的目标数据的节点地址
	while (Head->next != Temp->next)
	{
		Temp = Temp->next;
		if (data == Temp->data)
		{
			P = Temp;
			break;
		}
	}
	// 找不到目标数据
	if (NULL == P)
	{
		perror("The target data cannot be found\n");
		return false;
	}
	// 目标数据在尾部
	if (Head->next == P->next)
	{
		DoubleCircLList_TailDel(Head);
	}
	else
	{
		P->next->prev = P->prev; // 删除节点的后继指向删除节点的前驱
		P->prev->next = P->next; // 删除节点的前驱指向删除节点的后继
		P->next = NULL;			 // 删除节点的首指针释放
		P->prev = NULL;			 // 删除节点的尾指针释放
		free(P);				 // 释放删除节点的堆内存
	}
	return true;
}

热门相关:校花之贴身高手   聊斋大圣人   视死如归魏君子   视死如归魏君子   我在镇夜司打开地狱之门