数据结构-双向循环链表
双向循环链表和双向链表相比，可以直接从首结点找到尾结点，不需要再通过遍历来查找尾结点了，方便数据的增删，降低了程序的时间复杂度，其在插入删除的时候不需要定义太多的变量，减少了程序的空间复杂度。/*********************************************************************************
*
*
* 设计双向循环链表的接口
* author：jindouliu2024@163.com
* date：2025.4.1
*
*
* Copyright (c)2024-2025 jindouliu2024@163.com All right Reserved
* *********************************************************************************/创建一个头结点
//构造双向链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleCriLinkedList
{
DataType_t data; //结点的数据域
struct DoubleCriLinkedList *prev; //直接前驱的指针域
struct DoubleCriLinkedList *next; //直接后继的指针域
}DoubleCriLList_t;创建双向循环空链表
//创建一个空双向链表，空链表应该有一个头结点，对链表进行初始化
DoubleCriLList_t * DoubleCriLList_Create(void)
{
//1.创建一个头结点并对头结点申请内存
DoubleCriLList_t *Head = (DoubleCriLList_t *)calloc(1,sizeof(DoubleCriLList_t));
if (NULL == Head)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向NULL
Head->prev = Head;
Head->next = Head;
//3.把头结点的地址返回即可
return Head;
}创建新结点
//创建新的结点，并对新结点进行初始化（数据域 + 指针域）
DoubleCriLList_t * DoubleCriLList_NewNode(DataType_t data)
{
//1.创建一个新结点并对新结点申请内存
DoubleCriLList_t *New = (DoubleCriLList_t *)calloc(1,sizeof(DoubleCriLList_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;
}在链表头部插入元素
bool DoubleCriLList_HeadInsert(DoubleCriLList_t * Head,DataType_t data)
{
DoubleCriLList_t *Phead=Head->next;
//创建新结点
DoubleCriLList_t * New= DoubleCriLList_NewNode(data);
//判断新结点创建是否成功
if(NULL == New){
printf("HeadInsert create new node failed\n ");
return false;
}
//判断链表是否为空
if(Head->next == Head){
Head->next = New;
New->next = New;
New->prev = New;
return true;
}
New->prev = Head->next->prev;
Head->next->prev->next = New;
New->next = Phead;
Phead->prev = New;
Head->next = New;
return true;
}在链表尾部插入
bool DoubleCriLList_TailInsert(DoubleCriLList_t * Head,DataType_t data)
{
DoubleCriLList_t *Phead=Head->next;
//创建新结点
DoubleCriLList_t * New= DoubleCriLList_NewNode(data);
//判断新结点创建是否成功
if(NULL == New){
printf("TailInsert create new node failed\n ");
return false;
}
//判断链表为空
if(Head->next == Head){
Head->next = New;
New->next = New;
New->prev = New;
return true;
}
New->prev = Head->next->prev;
Head->next->prev->next = New;
New->next = Head->next;
Head->next->prev = New;
return true;
}在链表指定元素后边插入
bool DoubleCriLList_DestInsert(DoubleCriLList_t * Head,DataType_t destval,DataType_t data)
{
DoubleCriLList_t * Phead = Head->next;
//创建新结点
DoubleCriLList_t * New= DoubleCriLList_NewNode(data);
//判断新结点创建是否成功
if(NULL == New){
printf("DestInsert create new node failed\n ");
return false;
}
//链表为空
if(Head->next == Head){
Head->next = New;
New->next = New;
New->prev = New;
return true;
}
//循环遍历查找目标结点 在中间的情况
while(Phead->next != Head->next){
if(Phead->data == destval){
New->next = Phead->next;
New->prev = Phead;
Phead->next->prev = New;
Phead->next = New;
return true;
}
Phead = Phead->next;
}
//尾结点是目标结点时
if(Phead->data == destval){
New->prev = Head->next->prev;
Head->next->prev->next = New;
New->next = Head->next;
Head->next->prev = New;
}
return true;
}在链表头部删除元素
bool DoubleCriLList_HeadDel(DoubleCriLList_t * Head)
{
DoubleCriLList_t * Phead = Head->next;
//判断链表是否为空
if(Head->next == Head){
printf("this is empty list,do not delete head\n");
return false;
}
//只有头首结点时
if(Head->next->next == Head->next){
Head->next->next = NULL;
Head->next->prev = NULL;
free(Head->next);
Head->next = Head;
}
else{
Head->next->prev->next = Head->next->next;
Head->next->next->prev = Head->next->prev;
Head->next = Head->next->next;
Phead->next = NULL;
Phead->prev = NULL;
free(Phead);
}
return true;
}在链表尾部删除元素
bool DoubleCriLList_TailDel(DoubleCriLList_t * Head)
{
DoubleCriLList_t * Phead = Head->next->prev;//记录尾结点
//判断链表是否为空
if(Head->next == Head){
printf("this is empty list,do not delete tail\n");
return false;
}
//只有头首结点时
if(Head->next->next == Head->next){
Head->next->next = NULL;
Head->next->prev = NULL;
free(Head->next);
Head->next = Head;
}
else{
Phead->prev->next = Head->next;//Head->next->prev->prev->next = Head->next;
Head->next->prev = Phead->prev;//Head->next->prev = Head->next->prev->prev;
Phead->prev = NULL;
Phead->next = NULL;
free(Phead);
}
return true;
}删除指定元素
bool DoubleCriLList_DestDel(DoubleCriLList_t * Head,DataType_t destval)
{
DoubleCriLList_t * Phead = Head->next;
//判断链表是否为空
if(Head->next == Head){
printf("this is empty list,do not delete tail\n");
return false;
}
//只有头首结点,首结点为目标结点时
if(Head->next->next == Head->next && Phead->data == destval){
Head->next->next = NULL;
Head->next->prev = NULL;
free(Head->next);
Head->next = Head;
}
//目标元素在首结点
else if(Phead->data == destval){
Head->next->prev->next = Head->next->next;
Head->next->next->prev = Head->next->prev;
Head->next = Head->next->next;
Phead->next = NULL;
Phead->prev = NULL;
free(Phead);
}
else{
//目标元素在中间时
while(Phead->next != Head->next){
if(Phead->data == destval){
Phead->next->prev = Phead->prev;
Phead->prev->next = Phead->next;
Phead->next = NULL;
Phead->prev = NULL;
free(Phead);
return true;
}
Phead = Phead->next;
}
}
//目标元素在尾结点
if(Phead->data == destval){
Phead->prev->next = Head->next;//Head->next->prev->prev->next = Head->next;
Head->next->prev = Phead->prev;//Head->next->prev = Head->next->prev->prev;
Phead->prev = NULL;
Phead->next = NULL;
free(Phead);
}
else if(Phead->data != destval){
printf("do not find this value\n");
}
return true;
}循环遍历打印链表
bool DoubleCriLList_Print(DoubleCriLList_t * Head)
{
DoubleCriLList_t * Phead = Head;
//判断链表是否为空
if(Head->next == Head){
printf("this is empty DoubleCriList\n");
return false;
}
//循环遍历链表
while(Phead->next)
{
//把头结点的直接后继作为新的头结点
Phead = Phead->next;
//输出头结点的直接后继的数据域
printf("data = %d\n",Phead->data);
//判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
return true;
}
来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！
页:
[1]