/********************************************************************************************************
*
*
* 设计双向循环链表的接�?
*
*
*
* Copyright (c) 2023-2024 cececlmx@126.com All right Reserved
* ******************************************************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>//指的是双向循环链表中的结点有效数据类型,用户可以根据需要进行修�?
typedef int DataType_t;//构造双向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct DoubleLinkedList
{DataType_t data; //结点的数据域struct DoubleLinkedList *prev; //直接前驱的指针域struct DoubleLinkedList *next; //直接后继的指针域}DoubleCirLList_t;//创建一个空双向循环链表,空链表应该有一个头结点,对链表进行初始�?
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;
}//创建新的结点,并对新结点进行初始化(数据�? + 指针域)
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;
}//头插
bool DoubleCirLList_HeadInsert(DoubleCirLList_t *Head,DataType_t data)
{DoubleCirLList_t *Phead=Head->next;DoubleCirLList_t *New = DoubleCirLList_NewNode(data);if (NULL == New){perror("Calloc memory for NewNode is Failed");return NULL;}if(Phead->next==Head){Head->next=New;return true;}New->prev=Phead->prev;New->next=Phead;Phead->prev->next=New;Phead->prev=New;Head->next=New;return true;
}//尾插
bool DoubleCirLList_tailInsert(DoubleCirLList_t *Head,DataType_t data)
{DoubleCirLList_t *Phead = Head->next;DoubleCirLList_t *New = DoubleCirLList_NewNode(data);if (NULL == New){perror("Calloc memory for NewNode is Failed");return false;}if(Phead==Head){Head->next=New;return true;}New->prev = Phead->prev;New->next = Phead;Phead->prev->next = New;Phead->prev=New;return true;
}//指定位置插入
bool DoubleCirLList_DestInsert(DoubleCirLList_t *Head,DataType_t destval,DataType_t data)
{DoubleCirLList_t *Phead = Head->next;DoubleCirLList_t *New = DoubleCirLList_NewNode(data);if (NULL == New){perror("Calloc memory for NewNode is Failed");return NULL;}if(Phead==Head){Head->next=New;return true;}while(Phead->data != destval){if(Phead->next==Head->next){printf("dest node is not found\n");return false;}Phead = Phead->next;}New->next=Phead->next;New->prev=Phead;Phead->next->prev=New;Phead->next=New;return true;
}//头删
bool DoubleCirLList_HeadDel(DoubleCirLList_t *Head)
{//对单向循环链表的头结点的地址进行备份DoubleCirLList_t *Phead=Head->next;if(Head==Phead){printf("头删双链表为空\n");return false;}if(Phead->next==Phead){Head->next=Head;}else{Head->next = Phead->next;Phead->prev->next=Phead->next;Phead->next->prev=Phead->prev;}Phead->next=NULL;Phead->prev = NULL;free(Phead);return true;}//尾删
bool DoubleCirLList_TailDel(DoubleCirLList_t *Head)
{//对单向循环链表的头结点的地址进行备份DoubleCirLList_t *Phead=Head->next;DoubleCirLList_t *Bhead=Phead->prev;if(Head==Phead){printf("尾删双链表为空\n");return false;}if(Phead==Head){Head->next=Head;}else{printf("进来了\n");Bhead->prev->next=Phead;Phead->prev=Bhead->prev;}Bhead->next=NULL;Bhead->prev = NULL;free(Bhead);return true;
}//指定删除
bool DoubleCirLList_Del(DoubleCirLList_t *Head, DataType_t dest)
{// 对双链表的头结点的地址进行备份DoubleCirLList_t *Phead = Head->next;if (Phead == NULL) {printf("指定双链表为空\n");return false;}while (Phead->data != dest) {if (Phead->next == Head->next) {printf("指删未找到目标节点\n");return false;}Phead = Phead->next;}// 找到目标节点if(Phead->next==Phead){Head->next=Head;}else{if (Phead == Head->next) //目标节点为头{Head->next=Phead->next;}Phead->prev->next=Phead->next;Phead->next->prev=Phead->prev;}Phead->next = NULL;Phead->prev = NULL;// 释放节点内存free(Phead);return true;
}bool DoubleCirLList_Print(DoubleCirLList_t *Head)
{//对单向循环链表的头结点的地址进行备份DoubleCirLList_t *Phead = Head;//判断当前链表是否为空,为空则直接退出if (Head->next == Head){printf("current linkeflist is empty!\n");return false;}//从首结点开始遍历while(Phead->next){//把头结点的直接后继作为新的头结点Phead = Phead->next;//输出头结点的直接后继的数据域printf("data = %d\n",Phead->data);//判断是否到达尾结点,尾结点的next指针是指向首结点的地址if (Phead->next == Head->next){break;} }return true;
}int main(int argc, char const *argv[])
{//1.创建顺序表DoubleCirLList_t * Manager = DoubleCirLList_Create();//2.向顺序表中的尾部插入新元素printf("*********************************尾插********************************\n");DoubleCirLList_tailInsert(Manager,5);DoubleCirLList_tailInsert(Manager,2);DoubleCirLList_tailInsert(Manager,1);DoubleCirLList_tailInsert(Manager,4);DoubleCirLList_tailInsert(Manager,6); // //3.遍历顺序表DoubleCirLList_Print(Manager); // -- 5 2 1 4 6printf("\n");//4.向顺序表中的头部插入新元素printf("*********************************头插********************************\n");DoubleCirLList_HeadInsert(Manager,9);DoubleCirLList_HeadInsert(Manager,7);DoubleCirLList_HeadInsert(Manager,8);DoubleCirLList_HeadInsert(Manager,0);DoubleCirLList_HeadInsert(Manager,10); // //5.遍历顺序表DoubleCirLList_Print(Manager); // --10 0 8 7 9 5 2 1 4 6printf("\n");//6.删除顺序表的元素printf("*********************************头删********************************\n");DoubleCirLList_HeadDel(Manager);DoubleCirLList_HeadDel(Manager);DoubleCirLList_HeadDel(Manager);DoubleCirLList_HeadDel(Manager);DoubleCirLList_HeadDel(Manager);DoubleCirLList_Print(Manager);// --5 2 1 4 6 //7.指定插入printf("*********************************指定插入********************************\n");DoubleCirLList_DestInsert(Manager,5,1);DoubleCirLList_DestInsert(Manager,2,3);DoubleCirLList_DestInsert(Manager,6,7);//8.遍历顺序表DoubleCirLList_Print(Manager); // --5 1 2 3 1 4 6 7printf("\n");//9.指定删除printf("*********************************指定删除********************************\n");DoubleCirLList_Del(Manager,5);DoubleCirLList_Del(Manager,7);DoubleCirLList_Del(Manager,3);//10.遍历顺序表DoubleCirLList_Print(Manager); // -- 1 2 1 4 6 printf("\n");//11.尾部删除printf("*********************************尾删********************************\n");DoubleCirLList_TailDel(Manager);DoubleCirLList_TailDel(Manager);DoubleCirLList_TailDel(Manager);DoubleCirLList_TailDel(Manager);//12.遍历顺序表DoubleCirLList_Print(Manager); // --1 printf("\n");return 0;
}