双向循环链表的增删改查功能
数据结构
双向循环链表
双向循环链表的增删改查
/*****************************************************************************************************************
*
* file name : DoubleCirLinkedList.c
* author : [email protected]
* data : 2024/04/24
* function : 双向循环链表的接口程序
* note : None
*
* CopyRight (c) 2024 [email protected] 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 : [email protected]
* 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 : [email protected]
* 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 : [email protected]
* 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 : [email protected]
* 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 : [email protected]
* 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 : [email protected]
* 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 : [email protected]
* 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;
}
结果验证：
