2.单向循环链表的接口设计

准挝 · 2025-8-1 01:39:29

/****************************************************************************
*
* file name: 2025-07-11_CircularLinkedList.c
* author : 15515376695@163.com
* date : 2025-07-11
* function : 该程序设计单向循环链表的接口
* note : None
* CopyRight (c) 2025 15515376695@163.com Right Reseverd
*
****************************************************************************/
//用户可以根据自己的需要进行修改所需的数据类型
typedef int DataType_t;
//构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
DataType_t data; //记录结点的数据域
struct CircularLinkedList *next; //记录结点的指针域
}CircLList_t;
//创建一个空单向循环链表，空链表应该有一个头结点，对链表进行初始化
CircLList_t * CircLList_Create(void)
{
//1.使用calloc为单向循环链表的头结点从堆空间申请一块内存，对链表进行初始化
CircLList_t * Head = (CircLList_t *)calloc(1,sizeof(CircLList_t));
if (NULL == Head)
{
perror("calloc memory for Head is failed");
exit(-1);//程序终止
}
//2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
Head->next = Head;
//3.把头结点的地址返回
return Head;
}
//创建新的结点，并对其初始化（数据域＋指针域）
CircLList_t * CircLList_NewNode(DataType_t data)
{
//1.创建一个新的结点并申请内存
CircLList_t *New = (CircLList_t *)calloc(1,sizeof(CircLList_t));
if (NULL == New)
{
perror("calloc memory for NewNode is Failed");
return NULL;
}
//2.对新结点进行初始化
New->data = data;
New->next = NULL;
return New;
}
//单向循环链表头部插入
bool CircLList_HeadInsert(CircLList_t *Head,DataType_t data)
{
//1.创建新的结点，并进行初始化
CircLList_t *New = CircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert newnode\n");
return false;
}
//2.判断链表是否为空，如果为空，直接插入
if (Head->next == Head)
{
Head->next = New;
New->next = New;
return true;
}
//3.若链表为非空，则把新结点插入链表头部
//先遍历找到尾结点地址
CircLList_t *Phead = Head->next;//备份首结点地址
//遍历寻找尾结点
while(Phead->next != Head->next)
{
Phead = Phead->next;// 得到尾结点地址
}
//进行头插
Phead->next = New;
New->next = Head->next;
Head->next = New;
return true;
}
////单向循环链表尾部插入
bool CircLList_TailInsert(CircLList_t *Head,DataType_t data)
{
CircLList_t *New = CircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert ner node\n");
return false;
}
if (Head->next == Head)
{
Head->next = New;
New->next = New;
return true;
}
//若链表非空
CircLList_t *Phead = Head->next;//备份首结点地址
while(Phead->next != Head->next)
{
Phead = Phead->next;// 得到尾结点地址
}
//进行尾部插入
Phead->next = New;
New->next = Head->next;
return true;
}
//向单向循环链表指定位置插入一个新的结点
bool CircLList_AppointInsert(CircLList_t *Head,DataType_t data,DataType_t DestVal)
{
CircLList_t * New = CircLList_NewNode(data);
if (NULL == New)
{
printf("can not insert ner node\n");
return false;
}
if (Head->next == Head)
{
Head->next = New;
New->next = New;
return true;
}
//若链表非空
CircLList_t * Phead = Head->next;
while(Phead->data != DestVal)
{
Phead = Phead->next;
if (Phead->next == Head->next && Phead->data != DestVal)
{
printf("The DestVal doesn't exist! \n");
return false;
}
}
//找到目标节点
New->next = Phead->next;
Phead->next = New;
return true;
}
//头删
bool CircLList_HeadDel(CircLList_t *Head)
{
CircLList_t * Phead = Head->next;//备份首结点地址
CircLList_t *Temp = Head->next;
//判断链表是否为空
if (Head->next == Head)
{
printf("CircLList is empty\n");
return false;
}
//判断是否只含有首结点
if (Head->next->next == Phead)
{
Head->next = Head;
Phead->next = NULL;//首结点的指针域指向NULL，目的是防止野指针出现和内存泄漏
free(Phead);//释放结点内存，防内存泄漏
return true;
}
//如果为非空，且含有多个结点，
//遍历找到尾结点
while(Phead->next != Head->next)
{
Phead = Phead->next;
}
Phead->next = Head->next->next;
Head->next = Head->next->next;
Temp->next = NULL;
free(Temp);
return true;
}
//中删
bool CircLList_DestDel(CircLList_t *Head, DataType_t dest)
{
// 检查头指针是否有效（防止空指针访问）
if (Head == NULL)
{
printf("Error, Head pointer is NULL! \n");
return false;
}
CircLList_t *Current = Head->next; // 指向首节点（若为空链表则指向头节点）
CircLList_t *Prev = Head; // 指向Current的前一个节点
// 1. 判断链表是否为空（头节点的next指向自身）
if (Head->next == Head)
{
printf("Error, CircularLinkList is empty! \n");
return false;
}
// 2. 查找目标节点
while (Current->data != dest)
{
Prev = Current;
Current = Current->next;
// 若遍历一圈回到首节点，说明未找到目标
if (Current == Head->next)
{
printf("The target doesn't exist! \n");
return false;
}
} // 退出循环时，Current指向目标节点，Prev指向其前驱
// 3. 分情况删除目标节点
// 3.1目标是首节点
if (Current == Head->next)
{
// 3.1.1 链表只有一个节点（首节点的next指向头节点）
if (Current->next == Head->next)
{
Head->next = Head; // 恢复为空链表
}
// 3.1.2 链表有多个节点
else
{
// 找到尾节点（尾节点的next指向首节点）
CircLList_t *Tail = Head->next;
while (Tail->next != Head->next)
{
Tail = Tail->next;
}
// 尾节点指向新首节点，头节点更新新首节点
Tail->next = Current->next;
Head->next = Current->next;
}
}
// 3.2 目标是尾节点（尾节点的next指向首节点）
else if (Current->next == Head->next)
{
Prev->next = Head->next; // 前驱直接指向首节点
}
// 3.3 目标是中间节点
else
{
Prev->next = Current->next; // 前驱指向目标的后继
}
// 释放目标节点内存
free(Current);
return true;
}
//尾删
bool CircLList_TailDel(CircLList_t *Head)
{
CircLList_t *Current = Head->next;
CircLList_t *Prev = Head;
// 1.判断单向循环链表是否为空
if (Head->next == Head)
{
printf("Error, CircularLinkList is empty! \n");
return false;
}
// 2.若单向循环链表非空
// 若链表只有首结点
if (Current->next == Head->next)
{
Head->next = Head; // 空链表状态
Current->next = NULL;
free(Current); // 防止内存泄漏
return true;
}
// 若还有别的结点
while (Current->next != Head->next) // 不断向下检查结点指针域
{
Prev = Current;
Current = Current->next;
}
// Current到达未尾结点 Prev为Current 的前一个位置
Prev->next = Head->next; // 新尾结点链接首结点, 行成循环
Current->next = NULL;
free(Current); // 防止内存泄漏
return true;
}

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！

账号		自动登录	找回密码
密码			立即注册

2.单向循环链表的接口设计

浏览过的版块

签约作者