单向循环链表（其一）
单向循环链表（其一）
单向循环链表的原理与应用：
单向循环的链表的使用规则和普通的单向链表没有较大的区别，需要注意：*单向循环链表的尾结点的指针域中必须指向链表的首结点的地址*，由于带头结点的单向循环链表更加容易进行管理，如下图所示：
上图所示的就是一个典型的单向循环链表的结构，可以发现单向循环链表的结构属于环形结构，链表中的最后一个结点的指针域中存储的是链表的第一个结点的地址。
单向循环链表实现分析：
（1）为了管理单向循环链表，需要构造头结点的数据类型以及构造有效结点的数据类型
// 指的是单向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
// 构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
DataType_t data; // 结点的数据域
struct CircularLinkedList *next; // 结点的指针域
} CircLList_t;
(2)创建一个空链表，由于是使用头结点，所以就需要申请头结点的堆内存并初始化即可！
/********************************************************************
*
* name : CircLList_Create
* function : 创建一个空单向循环链表，空链表应该有一个头结点，对链表进行初始化
* argument :
* none
*
* retval : 调用成功返回已经完成初始化的单向循环链表的头结点,否则退出程序
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
CircLList_t *CircLList_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
CircLList_t *Head = (CircLList_t *)calloc(1, sizeof(CircLList_t));
if (Head == NULL)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
Head->next = Head;
// 3.把头结点的地址返回即可
return Head;
}
(3)创建新结点，为新结点申请堆内存并对新结点的数据域和指针域进行初始化，操作如下：
/********************************************************************
*
* name : CircLList_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的单向循环链表的新节点,否则返回NULL
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
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;
}
(4)根据情况把新结点插入到链表中，此时可以分为尾部插入、头部插入、指定位置插入：
头插:
/********************************************************************
*
* name : CircLList_HeadInsert
* function : 将新节点头插进单向循环链表中
* argument :
* @Head 单向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_HeadInsert(CircLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
CircLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
CircLList_t *New = CircLList_NewNode(data);
if (New == NULL)
{
printf("HeadInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
New->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至尾结点，将尾结点的next更换为新节点
while (Phead->next != Head->next)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;将尾节点的next连接至新节点New
Phead->next = New;
// 2.将新节点的next指向为原首节点
New->next = Head->next;
// 3.将新节点更换为首节点
Head->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
尾插：
/********************************************************************
*
* name : CircLList_TailInsert
* function : 将新节点尾插进单向循环链表中
* argument :
* @Head 单向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_TailInsert(CircLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
CircLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
CircLList_t *New = CircLList_NewNode(data);
if (New == NULL)
{
printf("TailInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
New->next = New;
printf("TailInsert of %d is success!\n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至尾结点，将尾结点的next更换为新节点
while (Phead->next != Head->next)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;将尾节点的next连接至新节点New
Phead->next = New;
// 2.将新节点的next指向为首节点
New->next = Head->next;
printf("TailInsert of %d is success!\n", New->data);
return;
}
指定位置插:
/********************************************************************
*
* name : CircLList_DestInsert
* function : 将新节点插进单向循环链表指定位置中
* argument :
* @Head 单向循环链表头结点
* @destval 指定位置的数据域值
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
// 指定位置插入
void CircLList_DestInsert(CircLList_t *Head, DataType_t destval, DataType_t data)
{
// 定义一个循环指针变量Phead
CircLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
CircLList_t *New = CircLList_NewNode(data);
if (New == NULL)
{
printf("DestInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
New->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至目标节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
break;
}
Phead = Phead->next;
}
// 跳出while循环时，Phead为目标节点的前驱节点；且将新节点的next连接至目标节点
New->next = Phead->next;
// 2.将目标节点的前驱节点指向新节点
Phead->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
(5) 根据情况可以从链表中删除某结点，此时可以分为尾部删除、头部删除、指定元素删除：
头删:
/********************************************************************
*
* name : CircLList_HeadDel
* function : 删除链表的首节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的首节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_HeadDel(CircLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 1.遍历至尾结点，
while (Phead->next != Head->next)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;将尾节点的next连接至新首节点
Phead->next = Head->next->next;
// 2.定义一个指针变量用于备份删除节点
CircLList_t *Temp = Head->next;
// 3.将首节点更新
Head->next = Head->next->next;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
// 5.释放删除节点
free(Temp);
printf("HeadDel is success!\n");
return;
}
尾删:
/********************************************************************
*
* name : CircLList_TailDel
* function : 删除链表的尾节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_TailDel(CircLList_t *Head)
{
// 对单向循环链表的首结点的地址进行备份
CircLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 1.遍历至尾结点的前驱节点，跳出while循环时，Phead极为尾节点的前驱节点;
while (Phead->next->next != Head->next)
{
Phead = Phead->next;
}
// 2.定义一个指针变量用于备份删除节点
CircLList_t *Temp = Phead->next;
// 3.将删除节点的前驱节点的next改为首节点
Phead->next = Head->next;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
// 5.释放删除节点
free(Temp);
printf("TailDel is success!\n");
return;
}
指定位置删:
/********************************************************************
*
* name : CircLList_DestDel
* function : 删除链表的指定节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
@destval 指定位置的数据域值
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_DestDel(CircLList_t *Head,DataType_t destval)
{
// 对单向循环链表的首结点的地址进行备份
CircLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 1.遍历至目标节点的直接前驱节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->next->data == destval)
{
break;
}
Phead = Phead->next;
}
// 2.定义一个指针变量用于备份删除节点
CircLList_t *Temp = Phead->next;
// 3.将删除节点的前驱节点的next改为首节点
Phead->next = Phead->next->next;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
// 5.释放删除节点
free(Temp);
printf("DestDel is success!\n");
return;
}
(6)遍历输出链表中的所有节点的数据域值
/********************************************************************
*
* name : CircLList_Print
* function : 遍历输出单向循环链表中所有节点的数据域
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_Print(CircLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
return;
}
代码整体展示:
/*******************************************************************
*
* file name: CircularLinkedList.c
* author : 790557054@qq.com
* date : 2024/04/23
* function : 该案例是掌握单向循环链表的增删查改原理
* note : None
*
* CopyRight (c) 2023-2024 790557054@qq.com All Right Reseverd
*
* *****************************************************************/
#include <stdio.h>
#include <stdbool.h>
#include <stdlib.h>
// 指的是单向循环链表中的结点有效数据类型，用户可以根据需要进行修改
typedef int DataType_t;
// 构造单向循环链表的结点,链表中所有结点的数据类型应该是相同的
typedef struct CircularLinkedList
{
DataType_t data; // 结点的数据域
struct CircularLinkedList *next; // 结点的指针域
} CircLList_t;
/********************************************************************
*
* name : CircLList_Create
* function : 创建一个空单向循环链表，空链表应该有一个头结点，对链表进行初始化
* argument :
* none
*
* retval : 调用成功返回已经完成初始化的单向循环链表的头结点,否则退出程序
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
CircLList_t *CircLList_Create(void)
{
// 1.创建一个头结点并对头结点申请内存
CircLList_t *Head = (CircLList_t *)calloc(1, sizeof(CircLList_t));
if (Head == NULL)
{
perror("Calloc memory for Head is Failed");
exit(-1);
}
// 2.对头结点进行初始化，头结点是不存储数据域，指针域指向自身，体现“循环”思想
Head->next = Head;
// 3.把头结点的地址返回即可
return Head;
}
/********************************************************************
*
* name : CircLList_NewNode
* function : 创建新的结点，并对新结点进行初始化（数据域 + 指针域）
* argument :
* @data 新节点需要存储的数据
*
* retval : 调用成功返回已经完成初始化的单向循环链表的新节点,否则返回NULL
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
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;
}
/********************************************************************
*
* name : CircLList_HeadInsert
* function : 将新节点头插进单向循环链表中
* argument :
* @Head 单向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_HeadInsert(CircLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
CircLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
CircLList_t *New = CircLList_NewNode(data);
if (New == NULL)
{
printf("HeadInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
New->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至尾结点，将尾结点的next更换为新节点
while (Phead->next != Head->next)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;将尾节点的next连接至新节点New
Phead->next = New;
// 2.将新节点的next指向为原首节点
New->next = Head->next;
// 3.将新节点更换为首节点
Head->next = New;
printf("HeadInsert of %d is success!\n", New->data);
return;
}
/********************************************************************
*
* name : CircLList_TailInsert
* function : 将新节点尾插进单向循环链表中
* argument :
* @Head 单向循环链表头结点
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_TailInsert(CircLList_t *Head, DataType_t data)
{
// 定义一个循环指针变量Phead
CircLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
CircLList_t *New = CircLList_NewNode(data);
if (New == NULL)
{
printf("TailInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
New->next = New;
printf("TailInsert of %d is success!\n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至尾结点，将尾结点的next更换为新节点
while (Phead->next != Head->next)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;将尾节点的next连接至新节点New
Phead->next = New;
// 2.将新节点的next指向为首节点
New->next = Head->next;
printf("TailInsert of %d is success!\n", New->data);
return;
}
/********************************************************************
*
* name : CircLList_DestInsert
* function : 将新节点插进单向循环链表指定位置中中
* argument :
* @Head 单向循环链表头结点
* @destval 指定位置的数据域值
* @data 新节点的数据域需要存储的数据
*
* retval : 调用成功输出"插入成功"，否则输出"插入失败"
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
// 指定位置插入
void CircLList_DestInsert(CircLList_t *Head, DataType_t destval, DataType_t data)
{
// 定义一个循环指针变量Phead
CircLList_t *Phead = Head->next;
// 调用函数创立一个新节点,并完成对应的错误处理
CircLList_t *New = CircLList_NewNode(data);
if (New == NULL)
{
printf("DestInsert is fail!\n");
return;
}
// 进行判断，排除空链表的情况
if (Head->next == Head)
{
Head->next = New;
New->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
// 先遍历得到尾结点在插入
// 1.遍历至目标节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->data == destval)
{
break;
}
Phead = Phead->next;
}
// 跳出while循环时，Phead为目标节点的前驱节点；且将新节点的next连接至目标节点
New->next = Phead->next;
// 2.将目标节点的前驱节点指向新节点
Phead->next = New;
printf("DestInsert of %d is success!\n", New->data);
return;
}
/********************************************************************
*
* name : CircLList_Print
* function : 遍历输出单向循环链表中所有节点的数据域
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功输出链表中所有节点的数据域的值
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_Print(CircLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 从首结点开始遍历
while (Phead->next)
{
// 把头结点的直接后继作为新的头结点
Phead = Phead->next;
// 输出头结点的直接后继的数据域
printf("%d->", Phead->data);
// 判断是否到达尾结点，尾结点的next指针是指向首结点的地址
if (Phead->next == Head->next)
{
break;
}
}
return;
}
/********************************************************************
*
* name : CircLList_HeadDel
* function : 删除链表的首节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的首节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_HeadDel(CircLList_t *Head)
{
// 对单向循环链表的头结点的地址进行备份
CircLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 1.遍历至尾结点，
while (Phead->next != Head->next)
{
Phead = Phead->next;
}
// 跳出while循环时，Phead极为尾节点;将尾节点的next连接至新首节点
Phead->next = Head->next->next;
// 2.定义一个指针变量用于备份删除节点
CircLList_t *Temp = Head->next;
// 3.将首节点更新
Head->next = Head->next->next;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
// 5.释放删除节点
free(Temp);
printf("HeadDel is success!\n");
return;
}
/********************************************************************
*
* name : CircLList_TailDel
* function : 删除链表的尾节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_TailDel(CircLList_t *Head)
{
// 对单向循环链表的首结点的地址进行备份
CircLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 1.遍历至尾结点的前驱节点，跳出while循环时，Phead极为尾节点的前驱节点;
while (Phead->next->next != Head->next)
{
Phead = Phead->next;
}
// 2.定义一个指针变量用于备份删除节点
CircLList_t *Temp = Phead->next;
// 3.将删除节点的前驱节点的next改为首节点
Phead->next = Head->next;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
// 5.释放删除节点
free(Temp);
printf("TailDel is success!\n");
return;
}
/********************************************************************
*
* name : CircLList_DestDel
* function : 删除链表的指定节点，并保持链表的连续性
* argument :
* @Head 单向循环链表头结点
@destval 指定位置的数据域值
*
* retval : 调用成功后删除链表的尾节点
* author : 790557054@qq.com
* date : 2024/04/23
* note : none
*
* *****************************************************************/
void CircLList_DestDel(CircLList_t *Head,DataType_t destval)
{
// 对单向循环链表的首结点的地址进行备份
CircLList_t *Phead = Head->next;
// 判断当前链表是否为空，为空则直接退出
if (Head->next == Head)
{
printf("current linkeflist is empty!\n");
return;
}
// 1.遍历至目标节点的直接前驱节点
while (Phead->next != Head->next)
{
// 条件判断找出目标节点
if (Phead->next->data == destval)
{
break;
}
Phead = Phead->next;
}
// 2.定义一个指针变量用于备份删除节点
CircLList_t *Temp = Phead->next;
// 3.将删除节点的前驱节点的next改为首节点
Phead->next = Phead->next->next;
// 4.将删除节点的next指向NULL
Temp->next = NULL;
// 5.释放删除节点
free(Temp);
printf("DestDel is success!\n");
return;
}
int main(int argc, char const *argv[])
{
// 创建头结点
CircLList_t *Head = CircLList_Create();
//头插
CircLList_HeadInsert(Head, 10);
CircLList_HeadInsert(Head, 20);
CircLList_HeadInsert(Head, 30);
printf("\n");
// 遍历显示
CircLList_Print(Head);
printf("\n");
// 尾插
CircLList_TailInsert(Head, 30);
CircLList_TailInsert(Head, 20);
CircLList_TailInsert(Head, 10);
printf("\n");
// 指定位置插入
CircLList_DestInsert(Head, 20,666);
// 遍历显示
CircLList_Print(Head);
printf("\n");
// 头删
CircLList_HeadDel(Head);
//尾删
CircLList_TailDel(Head);
//指定删
CircLList_DestDel(Head, 20);
// 遍历显示
CircLList_Print(Head);
printf("\n");
return 0;
}
结果验证:
由上图所示，可以验证单向循环链表各个功能均能正常实现。