数据结构-单向循环链表
/**************************************************************************** * @name* @author:王玉珩* @date:2025/10/07** *CopyRight (c) 2025-2026 All Rightt Reseverd* *************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>typedef int DataType_t; //用户自定义类型typedef struct CircularLinkedList
{DataType_t Data; //数据域 struct CircularLinkedList *Next; //指针域 }CirLkList_t; //结构体别名 /**************************************************************************** * @name CirLkListTailInsert* @brief 创建空链表,申请一个头节点* @param NULL* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
CirLkList_t *CirLkListCreate(void)
{//创建头节点,申请堆内存CirLkList_t *Head = (CirLkList_t *)calloc(1,sizeof(CirLkList_t));//判断申请堆内存是否成功 if (NULL == Head){perror("Calloc memory for Head failed");exit(-1); //失败退出程序}Head->Next=Head; //指针域指向自己,体现循环 return Head;
}/**************************************************************************** * @name CirLkListTailInsert* @brief 创建独立节点* @param * @DataType_t Data:新节点中数据域的值* * @retval point** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
CirLkList_t *CirLkListNewNode(DataType_t Data)
{//为节点申请堆内存CirLkList_t *New = (CirLkList_t *)calloc(1,sizeof(CirLkList_t));//判断申请堆内存是否成功if (NULL == New){perror("Calloc memory for New is failed");return NULL;}New->Data = Data; //数据域New->Next = NULL; //指针域return New; //返回节点地址
}/**************************************************************************** * @name CirLkListTailInsert* @brief 头节点后插入节点* @param * @LkList_t *Head:头节点* @DataType_t Data:新节点中数据域的值* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool CirLkListHeadInsert(CirLkList_t *Head , DataType_t Data)
{CirLkList_t *New = CirLkListNewNode(Data); //调用函数创建新节点CirLkList_t *PHead = Head; //备份头节点//判断是否创建成功if (NULL == New){printf("can not insert new node\n");return false;}//如果为空链表,将头节点的指针域指向新创建的节点,新节点的指针域指向自己 if (Head->Next == Head){Head->Next = New; //头节点指针域新节点New->Next = New; //新节点指针域指向自己return true;}//如果为非空链表else{//找寻尾节点while (PHead->Next){PHead = PHead->Next;if (PHead->Next == Head->Next){break;}} PHead->Next = New; //将尾节点指针域指向新节点New->Next = Head->Next; //新节点指针域首节点Head->Next = New; //头节点指针域指向新节点return true; }}/**************************************************************************** * @name CirLkListTailInsert* @brief 尾节点后插入节点* @param * @LkList_t *Head:头节点* @DataType_t Data:新节点中数据域的值* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool CirLkListTailInsert(CirLkList_t *Head , DataType_t Data)
{CirLkList_t *New = CirLkListNewNode(Data); //调用函数创建新节点CirLkList_t *PHead = Head; //备份头节点 //判断是否创建成功if (NULL == New){printf("can not insert new node\n");return false;}//如果为空链表,将头节点的指针域指向新创建的节点,新节点的指针域指向自己 if (Head == Head->Next){Head->Next = New; //头节点指针域新节点New->Next = New; //新节点指针域指向自己return true;}//如果为非空链表else{while (PHead->Next){PHead = PHead->Next; //将PHead的直接后继赋值给PHeadif (PHead->Next == Head->Next){break;} } PHead->Next = New; //将尾节点指针域指向新节点New->Next = Head->Next; //新节点指针域首节点return true; } }/**************************************************************************** * @name CirLkListDestInsert* @brief 指定位置后插入节点* @param * @LkList_t *Head:头节点* @DataType_t Data:新节点中数据域的值* @DataType_t Dest:要找寻的节点数据域* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool CirLkListDestInsert(CirLkList_t *Head ,DataType_t Dest, DataType_t Data)
{CirLkList_t *New = CirLkListNewNode(Data); //调用函数创建新节点CirLkList_t *PHead = Head; //备份头节点//判断是否创建成功if (NULL == New){printf("can not insert new node\n");return false;}//如果为空链表,将头节点的指针域指向新创建的节点,新节点的指针域指向自己 if (Head == Head->Next){Head->Next = New; //头节点指针域新节点New->Next = New; //新节点指针域指向自己return true;}//如果为非空链表else{while (PHead->Next){PHead = PHead->Next; //将PHead的直接后继赋值给PHeadif (PHead->Data == Dest){break;} }New->Next = PHead->Next;PHead->Next = New;return true; }
}/**************************************************************************** * @name CirLkListHeadDel* @brief 删除首节点* @param * @CirLkList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool CirLkListHeadDel(CirLkList_t *Head)
{CirLkList_t *PHead = Head; //备份头节点 CirLkList_t *Temp = Head->Next; //备份头节点 //1、空链表if (Head == Head->Next){printf("Linkedlist is Empty\n");return false;}//2、只有首节点if (Head->Next == Head->Next->Next){Head->Next->Next = NULL; //首节点的Next指向空Head->Next = Head; //头节点的Next指向自己free(Temp); //释放return true;}//3、非空节点and非只有首节点while (PHead->Next){PHead = PHead->Next;if (PHead->Next == Head->Next){break;} } PHead->Next = Temp->Next; //尾节点的Next指向新的首节点 Head->Next = Temp->Next;Temp->Next = NULL; //首节点的Next赋值为NULLfree(Temp); //释放节点return true;
}/**************************************************************************** * @name CirLkListTailDel* @brief 删除尾节点* @param * @CirLkList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool CirLkListTailDel(CirLkList_t *Head)
{CirLkList_t *PHead = Head; //备份头节点 CirLkList_t *Temp = Head->Next; //备份首节点 //1、空链表if (Head == Head->Next){printf("Linkedlist is Empty\n");return false;}//2、只有首节点if (Temp == Head){Head->Next = Head; //头节点的Next指向自己Temp->Next = NULL; //首节点的Next指向空free(Temp); //释放return true;}//3、非空节点and非只有首节点CirLkList_t *PPrev = Head; //记录尾节点的直接前驱while (PHead->Next){PPrev = PHead;PHead = PHead->Next;if (PHead->Next == Head->Next){break;} }PPrev->Next = Head->Next; //尾节点的直接前驱指向首节点PHead->Next = NULL; //尾节点的Next指向NULLfree(PHead); //释放节点}/**************************************************************************** * @name CirLkListDestlDel* @brief 删除指定节点* @param * @CirLkList_t *Head:头节点* * @retval bool** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
bool CirLkListDestlDel(CirLkList_t *Head ,DataType_t Dest)
{CirLkList_t *PHead = Head; CirLkList_t *PPrev = Head; bool found = false; //空链表if (Head == Head->Next){printf("Linkedlist is Empty\n");return false;}//遍历查找要删除的节点do{if (PHead->Data == Dest){found = true;break;}PPrev = PHead;PHead = PHead->Next; } while (PHead != PHead->Next);//没找到if (!found){printf("Node ith data %d not found\n",Dest);return false;} //只有一个节点if (PHead == PHead->Next){Head->Next = Head; //头节点的Next指向自己PHead->Next = NULL; //节点的Next指向空free(PHead); //释放return true;}//多个节点的情况PPrev->Next = PHead->Next; //前驱节点指向后继节点//如果要删除的是首节点,需要更新头节点的指向if (PHead == Head->Next){Head->Next = PHead->Next; //头节点指向新的首节点}PHead->Next = NULL; //断开链接free(PHead); //释放节点return true;
}/**************************************************************************** * @name CirLkListPrint* @brief 遍历链表* @param * @CirLkList_t *Head:头节点* * @retval ** @author https://www.cnblogs.com/yuhengwang* *************************************************************************/
void CirLkListPrint(CirLkList_t *Head)
{CirLkList_t *PHead = Head; //记录首节点 //打印整个链表while (PHead->Next){PHead = PHead->Next;printf("data=%d\n",PHead->Data);if (PHead->Next == Head->Next){break;}}
}//主函数
int main(int argc , const char* argv[])
{CirLkList_t *CirLkList = CirLkListNewNode(10);CirLkListHeadInsert(CirLkList,10);CirLkListHeadInsert(CirLkList,0);CirLkListTailInsert(CirLkList,20);CirLkListTailInsert(CirLkList,30);CirLkListDestInsert(CirLkList,10,15);CirLkListPrint(CirLkList); //0,10,15,20,30printf("\n");CirLkListHeadDel(CirLkList);CirLkListTailDel(CirLkList);CirLkListDestlDel(CirLkList,15); CirLkListPrint(CirLkList); //10,20
}