数据结构
双向循环链表
双向循环链表的增删改查
/*****************************************************************************************************************
*
* 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;
}
结果验证：
