双向循环链表
原理与应用
双向循环链表与双向链表的区别：指的是双向循环链表的首结点中的prev指针成员指向链表的尾结点，并且双向循环链表的尾结点里的next指针成员指向链表的首结点，所以双向循环链表也属于环形结构。
双向循环链表各功能实现
（1）为了管理双向循环链表，需要构造头结点的数据类型以及构造有效结点的数据类型
//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleCirLinkedList
{
DataType_t data; //结点的数据域
struct DoubleCirLinkedList *prev; //直接前驱的指针域
struct DoubleCirLinkedList *next; //直接后继的指针域
}DoubleCirLList_t;
(2)创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！
/********************************************************************
*
* name : DoubleCirLList_Create
* function : 创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
* argument :
* none
*
* retval : 调用成功返回已经完成初始化的双向循环链表的头结点,否则退出程序
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
//创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
DoubleCirLList_t * DoubleCirLList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
DoubleCirLList_t *Head = (DoubleCirLList_t *)calloc(1,sizeof(DoubleCirLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1); //程序异常退出
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”
Head->prev = Head;
Head->next = Head;
//3.把头结点的地址返回即可
return Head;
}
(3)创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：
/********************************************************************
*
* name : DoubleCirLList_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域(prev+next)）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
DoubleCirLList_t * DoubleCirLList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
DoubleCirLList_t *New = (DoubleCirLList_t *)calloc(1,sizeof(DoubleCirLList_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;
}
(4)根据情况把新结点插入到链表中，此时可以分为尾部插入、头部插入、指定位置插入：
头插:
原理图示：
代码实现：
/********************************************************************
*
* name : DoubleCirLList_HeadInsert
* function : 将新节点头插进双向循环链表中
* argument :
* @Head 双向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleCirLList_HeadInsert(DoubleCirLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleCirLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleCirLList_t *New = DoubleCirLList_NewNode(data);
if (New == NULL)
{
printf("HeadInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
// 1.将尾结点的next指向新节点
Phead->prev->next = New;
// 2.将新节点的prev指向尾结点
New->prev = Phead->prev;
// 3.将新节点的next指向首节点
New->next = Phead;
//4.将首节点的prev指向新节点
Phead->prev = New;
//5.将头结点的next指向新节点
Head->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
尾插：
原理图示：
代码实现：
/********************************************************************
*
* name : DoubleCirLList_TailInsert
* function : 将新节点尾插进双向链表中
* argument :
* @Head 双向链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleCirLList_TailInsert(DoubleCirLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleCirLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleCirLList_t *New = DoubleCirLList_NewNode(data);
if (New == NULL)
{
printf("TailInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
printf("TailInsert of %d is success!\n", New->data);
return;
}
//1.将新节点的prev指向尾结点
New->prev = Phead->prev;
//2.将尾结点的next指向新节点
Phead->prev->next = New;
//3.将新节点的next指向首节点
New->next = Phead;
//4.将首节点的prev指向新节点
Phead->prev = New;
printf("TailInsert of %d is success!\n", New->data);
return;
}
指定位置插：
原理图示：
代码实现：
/********************************************************************
*
* name : DoubleCirLList_DestInsert
* function : 将新节点插进双向循环链表指定位置中
* argument :
* @Head 双向链表头结点
* @destval 指定位置的数据域值
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
// 指定位置插入
void DoubleCirLList_DestInsert(DoubleCirLList_t *Head, DataType_t destval, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleCirLList_t *Phead = Head->next;
// 定义一个旗帜变量，用于判断是否找到目标节点
int flag = 0;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleCirLList_t *New = DoubleCirLList_NewNode(data);
if (New == NULL)
{
printf("DestInsert of %d is fail!\n",destval);
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
// 1.遍历至目标节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
flag = 1;
break;
}
Phead = Phead->next;
}
//判断当链表中只有一个首节点是不是目标节点
if(Head->next->data == destval)
{
flag = 1;
Phead = Head->next;
}
//判断尾结点是不是目标节点
if(Phead->data == destval)
{
flag = 1;
}
//判断是否找到目标节点,未找到则不执行插入操作
if(flag == 0)
{
printf("destval is no find!\n");
free(New);
return;
}
//找到目标节点执行插入操作
//2.将新节点next连接至目标节点的直接后继
New->next = Phead->next;
//3.将目标节点的直接后继的prev连接至新节点
Phead->next->prev = New;
//4.将新节点的prev连接至目标节点
New->prev = Phead;
//5.将目标节点的next连接至新节点
Phead->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
(5) 根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定元素删除：
头删:
原理图示：
代码实现：
/********************************************************************
*
* name : DoubleCirLList_HeadDel
* function : 删除链表的首节点，并保持链表的连续性
* argument :
* @Head 双向循环链表头结点
*
* retval : 调用成功后删除链表的首节点
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_HeadDel(DoubleCirLList_t *Head)
{
// 对双向循环链表的头结点的地址进行备份
DoubleCirLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
//判断链表是否只有一个首节点
if(Phead->next == Head)
{
Head->next = Head;
free(Phead);
return;
}
// 1.将尾结点的next连接首节点的直接后继
Phead->prev->next= Phead->next;
// 2.将首节点的直接后继的prev连接尾结点
Phead->next->prev = Phead->prev;
// 3.将首节点的next连接自己
Phead->next = Phead;
//4.将头结点连接至新首节点
Head->next = Phead->prev->next;
// 5.将原首节点的prev指向自己
Phead->prev = Phead;
//6.释放掉原首节点
free(Phead);
printf("HeadDel is success!\n");
return;
}
尾删：
原理图示：
代码实现：
/********************************************************************
*
* name : DoubleCirLList_tailDel
* function : 删除链表的尾节点，并保持链表的连续性
* argument :
* @Head 双向循环链表头结点
*
* retval : 调用成功后删除链表的尾节点
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_TailDel(DoubleCirLList_t *Head)
{
// 对双向循环链表的首结点的地址进行备份
DoubleCirLList_t *Phead = Head->next;
// 对双向循环链表的尾结点的地址进行备份
DoubleCirLList_t *Temp = NULL;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
//判断链表是否只有一个首节点
if(Phead->next == Head)
{
Head->next = Head;
free(Phead);
return;
}
//1.将尾结点的直接前驱的next连接至首节点
Phead->prev->prev->next = Phead;
//2.对尾结点进行备份
Temp = Phead->prev;
//3. 将首节点的prev连接至尾结点的直接前驱
Phead->prev = Temp->prev;
//4. 将Temp的prev和next均连接至自己
Temp->prev = Temp;
Temp->next = Temp;
//5.释放掉Temp
free(Temp);
printf("TailDel is success!\n");
return;
}
指定位置删：
原理图示：
代码实现：
/********************************************************************
*
* name : DoubleCirLList_DestDel
* function : 删除链表的指定节点，并保持链表的连续性
* argument :
* @Head 双向循环链表头结点
@destval 指定位置的数据域值
*
* retval : 调用成功后删除链表的尾节点
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_DestDel(DoubleCirLList_t *Head, DataType_t destval)
{
// 对双向循环链表的首结点的地址进行备份
DoubleCirLList_t *Phead = Head->next;
// 定义一个旗帜变量用于判断是否找到目标值
int flag = 0;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 遍历至目标节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
flag = 1;
break;
}
Phead = Phead->next;
}
//判断链表中只有一个首节点是不是目标节点
if(Head->next->data == destval)
{
flag = 2;
Phead = Head->next;
}
//判断链表中的尾结点是不是目标节点
else if( Phead->data == destval)
{
flag = 1;
}
//判断是否找到目标节点,未找到则不执行删除操作
if(flag == 0)
{
printf("destval of %d is no find!\n",destval);
return;
}
else if(flag == 2) //首节点为目标节点
{
//1.将首节点的直接前驱的next连接至首节点的直接后继
Phead->prev->next = Phead->next;
//2.将首节点的直接后继的prev连接至首节点的直接前驱
Phead->next->prev = Phead->prev;
//3.将头结点的next与首节点的直接后继相连接
Head->next = Phead->next;
//4.将首节点的prev和next均连接至自己
Phead->next = Phead;
Phead->prev = Phead;
//5.释放掉首节点
free(Phead);
return;
}
else
{
//1.将目标节点的直接前驱的next连接至目标节点的直接后继
Phead->prev->next = Phead->next;
//2.将目标节点的直接后继的prev连接至目标节点的直接前驱
Phead->next->prev = Phead->prev;
//3.将目标节点的prev和next均连接至自己
Phead->next = Phead;
Phead->prev = Phead;
//4.释放目标节点
free(Phead);
}
printf("DestDel of %d is success!\n",destval);
return;
}
(6)遍历输出链表中的所有节点的数据域值
/********************************************************************
*
* name : DoubleCirLList_Print
* function : 遍历输出双向循环链表中所有节点的数据域
* argument :
* @Head 双向循环链表头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_Print(DoubleCirLList_t *Head)
{
// 对双向循环链表的头结点的地址进行备份
DoubleCirLList_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!\n");
return;
}
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
return;
}
代码完整展示
/*******************************************************************
*
* file name: DoubleLinkedList.c
* author : [email protected]
* date : 2024/04/24
* function : 该案例是掌握双向循环链表的增删查改原理
* note : None
*
* CopyRight (c) 2023-2024 [email protected] All Right Reseverd
*
* *****************************************************************/
#include <stdio.h>
#include <stdlib.h>
//指的是双向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleCirLinkedList
{
DataType_t data; //结点的数据域
struct DoubleCirLinkedList *prev; //直接前驱的指针域
struct DoubleCirLinkedList *next; //直接后继的指针域
}DoubleCirLList_t;
/********************************************************************
*
* name : DoubleCirLList_Create
* function : 创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
* argument :
* none
*
* retval : 调用成功返回已经完成初始化的双向循环链表的头结点,否则退出程序
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
//创建一个空双向循环链表，空链表应该有一个头结点，对链表进行初始化
DoubleCirLList_t * DoubleCirLList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
DoubleCirLList_t *Head = (DoubleCirLList_t *)calloc(1,sizeof(DoubleCirLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1); //程序异常退出
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身即可，体现“循环”
Head->prev = Head;
Head->next = Head;
//3.把头结点的地址返回即可
return Head;
}
/********************************************************************
*
* name : DoubleCirLList_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域(prev+next)）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的双向链表的新节点,否则返回NULL
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
DoubleCirLList_t * DoubleCirLList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
DoubleCirLList_t *New = (DoubleCirLList_t *)calloc(1,sizeof(DoubleCirLList_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 : DoubleCirLList_HeadInsert
* function : 将新节点头插进双向循环链表中
* argument :
* @Head 双向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleCirLList_HeadInsert(DoubleCirLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleCirLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleCirLList_t *New = DoubleCirLList_NewNode(data);
if (New == NULL)
{
printf("HeadInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
// 1.将尾结点的next指向新节点
Phead->prev->next = New;
// 2.将新节点的prev指向尾结点
New->prev = Phead->prev;
// 3.将新节点的next指向首节点
New->next = Phead;
//4.将首节点的prev指向新节点
Phead->prev = New;
//5.将头结点的next指向新节点
Head->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
/********************************************************************
*
* name : DoubleCirLList_TailInsert
* function : 将新节点尾插进双向链表中
* argument :
* @Head 双向链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void DoubleCirLList_TailInsert(DoubleCirLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleCirLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleCirLList_t *New = DoubleCirLList_NewNode(data);
if (New == NULL)
{
printf("TailInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
printf("TailInsert of %d is success!\n", New->data);
return;
}
//1.将新节点的prev指向尾结点
New->prev = Phead->prev;
//2.将尾结点的next指向新节点
Phead->prev->next = New;
//3.将新节点的next指向首节点
New->next = Phead;
//4.将首节点的prev指向新节点
Phead->prev = New;
printf("TailInsert of %d is success!\n", New->data);
return;
}
/********************************************************************
*
* name : DoubleCirLList_DestInsert
* function : 将新节点插进双向循环链表指定位置中
* argument :
* @Head 双向链表头结点
* @destval 指定位置的数据域值
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
// 指定位置插入
void DoubleCirLList_DestInsert(DoubleCirLList_t *Head, DataType_t destval, DataType_t data)
{
// 定义一个循环指针变量Phead
DoubleCirLList_t *Phead = Head->next;
// 定义一个旗帜变量，用于判断是否找到目标节点
int flag = 0;
// 调用函数创立一个新节点,并完成对应的错误处理
DoubleCirLList_t *New = DoubleCirLList_NewNode(data);
if (New == NULL)
{
printf("DestInsert of %d is fail!\n",destval);
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
// 1.遍历至目标节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
flag = 1;
break;
}
Phead = Phead->next;
}
//判断当链表中只有一个首节点是不是目标节点
if(Head->next->data == destval)
{
flag = 1;
Phead = Head->next;
}
//判断尾结点是不是目标节点
if(Phead->data == destval)
{
flag = 1;
}
//判断是否找到目标节点,未找到则不执行插入操作
if(flag == 0)
{
printf("destval is no find!\n");
free(New);
return;
}
//找到目标节点执行插入操作
//2.将新节点next连接至目标节点的直接后继
New->next = Phead->next;
//3.将目标节点的直接后继的prev连接至新节点
Phead->next->prev = New;
//4.将新节点的prev连接至目标节点
New->prev = Phead;
//5.将目标节点的next连接至新节点
Phead->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
/********************************************************************
*
* name : DoubleCirLList_Print
* function : 遍历输出双向循环链表中所有节点的数据域
* argument :
* @Head 双向循环链表头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_Print(DoubleCirLList_t *Head)
{
// 对双向循环链表的头结点的地址进行备份
DoubleCirLList_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == NULL)
{
printf("current linkeflist is empty!\n");
return;
}
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
return;
}
/********************************************************************
*
* name : DoubleCirLList_HeadDel
* function : 删除链表的首节点，并保持链表的连续性
* argument :
* @Head 双向循环链表头结点
*
* retval : 调用成功后删除链表的首节点
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_HeadDel(DoubleCirLList_t *Head)
{
// 对双向循环链表的头结点的地址进行备份
DoubleCirLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
//判断链表是否只有一个首节点
if(Phead->next == Head)
{
Head->next = Head;
free(Phead);
return;
}
// 1.将尾结点的next连接首节点的直接后继
Phead->prev->next= Phead->next;
// 2.将首节点的直接后继的prev连接尾结点
Phead->next->prev = Phead->prev;
// 3.将首节点的next连接自己
Phead->next = Phead;
//4.将头结点连接至新首节点
Head->next = Phead->prev->next;
// 5.将原首节点的prev指向自己
Phead->prev = Phead;
//6.释放掉原首节点
free(Phead);
printf("HeadDel is success!\n");
return;
}
/********************************************************************
*
* name : DoubleCirLList_tailDel
* function : 删除链表的尾节点，并保持链表的连续性
* argument :
* @Head 双向循环链表头结点
*
* retval : 调用成功后删除链表的尾节点
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_TailDel(DoubleCirLList_t *Head)
{
// 对双向循环链表的首结点的地址进行备份
DoubleCirLList_t *Phead = Head->next;
// 对双向循环链表的尾结点的地址进行备份
DoubleCirLList_t *Temp = NULL;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
//判断链表是否只有一个首节点
if(Phead->next == Head)
{
Head->next = Head;
free(Phead);
return;
}
//1.将尾结点的直接前驱的next连接至首节点
Phead->prev->prev->next = Phead;
//2.对尾结点进行备份
Temp = Phead->prev;
//3. 将首节点的prev连接至尾结点的直接前驱
Phead->prev = Temp->prev;
//4. 将Temp的prev和next均连接至自己
Temp->prev = Temp;
Temp->next = Temp;
//5.释放掉Temp
free(Temp);
printf("TailDel is success!\n");
return;
}
/********************************************************************
*
* name : DoubleCirLList_DestDel
* function : 删除链表的指定节点，并保持链表的连续性
* argument :
* @Head 双向循环链表头结点
@destval 指定位置的数据域值
*
* retval : 调用成功后删除链表的尾节点
* author : [email protected]
* date : 2024/04/24
* note : none
*
* *****************************************************************/
void DoubleCirLList_DestDel(DoubleCirLList_t *Head, DataType_t destval)
{
// 对双向循环链表的首结点的地址进行备份
DoubleCirLList_t *Phead = Head->next;
// 定义一个旗帜变量用于判断是否找到目标值
int flag = 0;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 遍历至目标节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
flag = 1;
break;
}
Phead = Phead->next;
}
//判断链表中只有一个首节点是不是目标节点
if(Head->next->data == destval)
{
flag = 2;
Phead = Head->next;
}
//判断链表中的尾结点是不是目标节点
else if( Phead->data == destval)
{
flag = 1;
}
//判断是否找到目标节点,未找到则不执行删除操作
if(flag == 0)
{
printf("destval of %d is no find!\n",destval);
return;
}
else if(flag == 2) //首节点为目标节点
{
//1.将首节点的直接前驱的next连接至首节点的直接后继
Phead->prev->next = Phead->next;
//2.将首节点的直接后继的prev连接至首节点的直接前驱
Phead->next->prev = Phead->prev;
//3.将头结点的next与首节点的直接后继相连接
Head->next = Phead->next;
//4.将首节点的prev和next均连接至自己
Phead->next = Phead;
Phead->prev = Phead;
//5.释放掉首节点
free(Phead);
return;
}
else
{
//1.将目标节点的直接前驱的next连接至目标节点的直接后继
Phead->prev->next = Phead->next;
//2.将目标节点的直接后继的prev连接至目标节点的直接前驱
Phead->next->prev = Phead->prev;
//3.将目标节点的prev和next均连接至自己
Phead->next = Phead;
Phead->prev = Phead;
//4.释放目标节点
free(Phead);
}
printf("DestDel of %d is success!\n",destval);
return;
}
int main(int argc, char const *argv[])
{
//创建头结点
DoubleCirLList_t *Head = DoubleCirLList_Create();
// 头插
DoubleCirLList_HeadInsert(Head, 10);
DoubleCirLList_HeadInsert(Head, 20);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
// 尾插
DoubleCirLList_TailInsert(Head, 50);
DoubleCirLList_TailInsert(Head, 60);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
// 指定位置插
//1.目标值为首节点时
DoubleCirLList_DestInsert(Head, 20, 666);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
//2.目标值为中间值时
DoubleCirLList_DestInsert(Head, 50, 888);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
//3.目标值为尾节点时
DoubleCirLList_DestInsert(Head, 60, 999);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
//4.当目标值找不到时
DoubleCirLList_DestInsert(Head, 66, 666);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
// 头删
DoubleCirLList_HeadDel(Head);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
// 尾删
DoubleCirLList_TailDel(Head);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
// 指定位置删
//删除此时链表首节点
DoubleCirLList_DestDel(Head, 666);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
//删除此时链表的尾结点
DoubleCirLList_DestDel(Head, 60);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
//删除此时链表的中间节点
DoubleCirLList_DestDel(Head, 50);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
//删除链表中不存在值
DoubleCirLList_DestDel(Head, 666);
printf("\n");
// 遍历显示
DoubleCirLList_Print(Head);
printf("\n");
return 0;
}
结果验证：
