数据结构-双向循环链表
函数功能实现
/**************************************************************************** * @name* @author* @date** *CopyRight (c) 2025-2026 All Right Reserved* *************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleCirLinkedList
{DataType_t data; //结点的数据域struct DoubleCirLinkedList *prev; //直接前驱的指针域struct DoubleCirLinkedList *next; //直接后继的指针域}DoubleCirLkList_t;/**************************************************************************** * @name DoubleCirLkList_Create* @brief 创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化* @param NULL* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
DoubleCirLkList_t * DoubleCirLkList_Create(void)
{//1.创建一个头结点并对头结点申请内存DoubleCirLkList_t *Head = (DoubleCirLkList_t *)calloc(1,sizeof(DoubleCirLkList_t));if (NULL == Head){perror("Calloc memory for Head is Failed");exit(-1);}//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”Head->prev = Head;Head->next = Head;//3.把头结点的地址返回即可return Head;
}/**************************************************************************** * @name DoubleCirLkList_NewNode* @brief 创建新的结点，并对新结点进行初始化（数据域 + 指针域）* @param NULL* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
DoubleCirLkList_t * DoubleCirLkList_NewNode(DataType_t data)
{//1.创建一个新结点并对新结点申请内存DoubleCirLkList_t *New = (DoubleCirLkList_t *)calloc(1,sizeof(DoubleCirLkList_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 DoubleCirLkList_HeadInsert* @brief 头节点后插入节点* @param bool* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleCirLkList_HeadInsert(DoubleCirLkList_t *Head , DataType_t Data)
{DoubleCirLkList_t *New = DoubleCirLkList_NewNode(Data);DoubleCirLkList_t *PHead = Head->next; //备份头节点//判断是否创建成功if (NULL == New){return false;}//1、如果为空链表，将头节点的Next指向新创建的节点 if (Head == Head->next){Head->next = New; //头节点的next指向Newreturn true;}//2、非空链表while (PHead->next != Head->next){PHead = PHead->next;}PHead->next = New; //尾节点的Next指向 New节点Head->next->prev = New; //首节点的prev指向 New节点New->prev = Head; //New节点的prev指向 Head节点New->next = Head->next; //New节点的next指向 首节点Head->next = New; //头节点的next指向 New节点return true;
}/**************************************************************************** * @name DoubleCirLkList_TailInsert* @brief 尾节点后插入节点* @param bool* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleCirLkList_TailInsert(DoubleCirLkList_t *Head , DataType_t Data)
{DoubleCirLkList_t *New = DoubleCirLkList_NewNode(Data);//判断是否创建成功if (NULL == New){return false;}//1、如果为空链表，将头节点的Next指向新创建的节点 if (Head == Head->next){Head->next = New; //头节点的next指向Newreturn true;}//2、非空链表DoubleCirLkList_t *PHead = Head->next; //将头节点地址赋值给p指针while (PHead->next != Head->next){PHead = PHead->next;}PHead->next = New; //尾节点的next指向 New节点New->prev = PHead; //New节点的prev指向 尾节点New->next = Head->next; //New节点的next指向 首节点return true;}/**************************************************************************** * @name DoubleCirLkList_DestInsert* @brief 指定位置后插入节点* @param DoubleLList_t *Head:头节点* DataType_t Data:数据域* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleLList_DestInsert(DoubleCirLkList_t *Head , DataType_t Dest , DataType_t Data)
{DoubleCirLkList_t *New = DoubleCirLkList_NewNode(Data);//判断是否创建成功if (NULL == New){return false;}//1、如果为空链表，将头节点的Next指向新创建的节点 if (Head == Head->next){Head->next = New; //头节点的next指向Newreturn true;}//2、非空链表DoubleCirLkList_t *PHead = Head; //将头节点地址赋值给p指针while (PHead->next){PHead = PHead->next;if (PHead->data == Dest){break;}}//2.1遍历没有目标节点,退出if (PHead->next == Head->next && PHead->data != Dest){printf("dest node is not found\n");return false;}//2.2如果有，分为尾，中间if (PHead->next == NULL) //尾插 {New->prev = PHead;PHead->next = New;New->next = Head->next;}else //中间{PHead->next->prev = New; //目标节点的直接后继的prev 指向新节点New->prev = PHead; //新节点的prev指向 目标节点New->next = PHead->next; //新节点的next指向 目标节点的直接后继PHead->next = New; //目标节点的next指向 新节点}return true;
}/**************************************************************************** * @name DoubleCirLkList_HeadDel* @brief 删除首节点* @param DoubleLList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleCirLkList_HeadDel(DoubleCirLkList_t *Head)
{//判断是否为空链表if (Head == Head->next){printf("dest node is not found\n");return false;}DoubleCirLkList_t *PHead = Head->next;DoubleCirLkList_t *Temp = Head->next;while (PHead->next != Head->next){PHead = PHead->next;}PHead->next = Temp->next;Head->next = Temp->next;Temp->next->prev = Head;Temp->next = NULL;Temp->prev = NULL;free(Temp);return true;
}/**************************************************************************** * @name DoubleCirLkList_TailDel* @brief 删除尾节点* @param DoubleLList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool DoubleCirLkList_TailDel(DoubleCirLkList_t *Head)
{//判断是否为空链表if (NULL == Head->next){printf("dest node is not found\n");return false;}DoubleCirLkList_t *PHead = Head->next; //将头节点地址赋值给p指针while (PHead->next != Head->next){PHead = PHead->next;}PHead->prev->next = Head->next;PHead->prev = NULL;PHead->next = NULL;free(PHead);return true;
}/**************************************************************************** * @name DoubleCirLkList_Print* @brief 遍历* @param DoubleLList_t *Head:头节点* * @retval ** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
void DoubleCirLkList_Print(DoubleCirLkList_t *Head)
{DoubleCirLkList_t *PHead = Head; //打印整个链表do{PHead = PHead->next;printf("Data=%d\n",PHead->data);} while (PHead->next != Head->next);
}
主函数
//主函数
int main(int argc, char const *argv[])
{DoubleCirLkList_t *DoubleCirLkList = DoubleCirLkList_Create();DoubleCirLkList_HeadInsert(DoubleCirLkList,10);DoubleCirLkList_TailInsert(DoubleCirLkList,20);DoubleCirLkList_TailInsert(DoubleCirLkList,30);DoubleCirLkList_TailInsert(DoubleCirLkList,40);DoubleCirLkList_TailInsert(DoubleCirLkList,50);DoubleLList_DestInsert(DoubleCirLkList,10,15);DoubleCirLkList_HeadDel(DoubleCirLkList);DoubleCirLkList_TailDel(DoubleCirLkList);DoubleCirLkList_Print(DoubleCirLkList); //15，20，30，40return 0;
}
