一、单项循环链表的原理与应用
对于单链表而言，想要遍历链表，则必须从链表的首节点开始进行遍历，而单项循环链表则可以更简单的实现链表中数据的增删改查；单项循环链表的使用规则和普通的单项链表没有较大的区别，需要注意：单项循环链表的尾结点的指针域中必须指向链表的首结点的地址。带头节点的单向循环链表更加容易进行管理
上图所示的就是一个典型的单项循环链表的结构，可以发现单项循环链表的结构属于环形结构，链表中的最后一个节点的指针域中存储的是链表中第一个结点的地址。
为了管理单项循环链表，需要构造头结点的数据类型以及构造有效节点的数据类型，如下：
//定义数据类型暂时为int，后续由用户可方便修改
typedef int Datatype_t;
//创建一个循环单链表的节点，链表中的每一个节点都应该是相同的
typedef struct circularlinkedlist{
//节点中的数据域
Datatype_t data;
//节点中的指针域，存储下一个节点的地址
struct circularlinkedlist *next;
}circlinkedlist_t;
单项循环链表代码如下：
circlinkedlist.h：
/**
* @file : circlinkedlist.h
* @brief : 实现循环单链表，包含单链表的创建、添加、删除、遍历
* @author : TingFengLuo@126.com
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 单链表包含一个头节点，每个节点中都有一个数据域和一个指针域，尾指针的指针域指向首节点
CopyRight (c) 2025 TingFengLuo@126.com ALL RIGHT Reseverd
*/
#ifndef __CIRCLINKEDLIST_H
#define __CIRCLINKEDLIST_H
#include <stdlib.h>
#include <stdio.h>
#include <stdbool.h>
//定义数据类型暂时为int，后续由用户可方便修改
typedef int Datatype_t;
//创建一个循环单链表的节点，链表中的每一个节点都应该是相同的
typedef struct circularlinkedlist{
//节点中的数据域
Datatype_t data;
//节点中的指针域，存储下一个节点的地址
struct circularlinkedlist *next;
}circlinkedlist_t;
//创建循环单链表并对循环单链表初始化
circlinkedlist_t * CircLinkList_create(void);
//创建新节点，将新节点中的元素初始化
circlinkedlist_t * CircLinkList_NewNode(Datatype_t data);
//在链表的头部插入新节点
bool CircLinkList_HeadAdd(circlinkedlist_t *head,Datatype_t data);
//在链表的目标值后面插入新节点
bool CircLinkList_MidAdd(circlinkedlist_t *head,Datatype_t dest,Datatype_t data);
//在链表的尾部插入新节点
bool CircLinkList_TailAdd(circlinkedlist_t *head,Datatype_t data);
//遍历循环单链表
void CircLinkList_show(circlinkedlist_t *head);
//删除首节点
bool CircLinkList_HeadDel(circlinkedlist_t *head);
//删除尾节点
bool CircLinkList_TailDel(circlinkedlist_t *head);
//删除与目标值相同的节点
bool CircLinkList_DestDel(circlinkedlist_t *head,Datatype_t dest);
#endif
circlinkedlist.c
#include "circlinkedlist.h"
/**
* @name : CircLinkList_create
* @brief : 创建循环单链表并初始化数据
* @param : NULL
* @retval : 返回循环单链表类型的头节点地址
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 单链表创建中头节点中是没有数据域的，所以数据域没有初始化
*/
circlinkedlist_t * CircLinkList_create(void)
{
circlinkedlist_t * head=(circlinkedlist_t *)calloc(1,sizeof(circlinkedlist_t));
if(NULL == head){
perror("create memory failed for head");
return NULL;
}
head->next=head;
return head;
}
/**
* @name : CircLinkList_NewNode
* @brief : 创建新节点为后续的添加做准备
* @param
@data : 用户要传输的数据
* @retval : 返回新节点的地址
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 新节点的数据域和指针域需要初始化
*/
circlinkedlist_t * CircLinkList_NewNode(Datatype_t data)
{
circlinkedlist_t *new_node = (circlinkedlist_t *)calloc(1,sizeof(circlinkedlist_t));
if(NULL == new_node){
perror("create memory failed for new");
return NULL;
}
new_node->data = data;
new_node->next = NULL;
return new_node;
}
/**
* @name : CircLinkList_HeadAdd
* @brief : 在单链表的头部插入新节点
* @param
@head : 表示在哪个链表中
@data : 头部插入节点的数据
* @retval : 插入成功返回true,反之，返回flase
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 先判断链表是否为空，如果为空直接插入，如果不为空正常插入
*/
bool CircLinkList_HeadAdd(circlinkedlist_t *head,Datatype_t data)
{
//判断头节点是否为空
if(NULL == head){
printf("head node is Empty\n");
return false;
}
//创建新节点
circlinkedlist_t *new_node = CircLinkList_NewNode(data);
//如果新节点的地址为空，返回false
if(NULL == new_node){
printf("create new node failed\n");
return false;
}
//判断该链表是否为空,如果为空直接在头部添加头节点
if(head == head->next){
new_node->next = head;
head->next = new_node;
return true;
}
circlinkedlist_t *phead=head;
//循环遍历，找到尾节点
while(phead->next != head){
phead = phead->next;
}
//新节点的下一个指针存储之前的首节点的地址
new_node->next = head->next;
//头节点的下一个指针指向新节点的地址
head->next = new_node;
//将尾节点的下一个地址存储新首节点的地址
phead->next = head;
//成功返回true
return true;
}
/**
* @name : CircLinkList_TailAdd
* @brief : 在链表的尾部插入新节点
* @param
@head : 表示在哪个链表中
@data : 头部插入节点的数据
* @retval : 插入成功返回true,反之，返回flase
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 先判断链表是否为空，如果为空直接插入，如果不为空在尾部插入，插入的新节点的下一个指针必须指向头节点
*/
bool CircLinkList_TailAdd(circlinkedlist_t *head,Datatype_t data)
{
if(NULL == head){
printf("head node is Empty!!!\n");
return false;
}
//创建新节点
circlinkedlist_t * new = CircLinkList_NewNode(data);
if(NULL == new){
printf("create new node failed\n");
return false;
}
//判断链表是否为空
if(head == head->next){
new->next = head;
head->next = new;
return true;
}
//创建指针遍历链表
circlinkedlist_t *tail = head;
//如果链表不为空,先遍历链表，找到尾节点
while(tail->next != head){
tail = tail->next;
}
//将新节点的下一个指针指向首节点
new->next = head;
//将尾节点的下一个指针指向新节点
tail->next = new;
return true;
}
/**
* @name : CircLinkList_MidAdd
* @brief : 在链表的目标值后面插入新节点，不考虑头节点和尾节点后插入
* @param
@head : 表示在哪个链表中
@dest : 要添加节点的前一个节点的数据
@data : 要添加节点的数据
* @retval : 插入成功返回true,反之，返回flase
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : NULL
*/
bool CircLinkList_MidAdd(circlinkedlist_t *head,Datatype_t dest,Datatype_t data)
{
//判断链表是否存在
if(NULL == head){
printf("head node is Empty!!!\n");
return false;
}
if(head->next == head){
printf("链表无数据节点,无匹配目标\n");
return false;
}
//创建新节点，并判断新节点是否存在
circlinkedlist_t *new = CircLinkList_NewNode(data);
if(NULL == new){
printf("create new node failed\n");
return false;
}
circlinkedlist_t *mid = head->next;
//遍历链表，找到第一个与目标值相同的节点
while(mid){
if(mid->data == dest){
new->next = mid->next;
mid->next = new;
return true;
}
if(mid->next == head){
break;
}
mid = mid->next;
}
printf("do not have node value same to dest\n");
free(new);
return false;
}
/**
* @name : CircLinkList_HeadDel
* @brief : 在链表头部删除首节点
* @param
@head : 表示在哪个链表中
* @retval : 删除成功返回true,反之，返回flase
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : NULL
*/
bool CircLinkList_HeadDel(circlinkedlist_t *head)
{
//判断链表是否存在
if(NULL == head){
printf("circular linked list do not have head node\n");
return false;
}
//判断链表是否为空
if(head->next == head){
printf("circular linked list is empty\n");
return false;
}
//创建一个变量，存储首节点
circlinkedlist_t *phead = head->next;
//将头节点的下一个节点指向首节点的下一个节点
head->next = phead->next;
//将删除的首节点
phead->next = NULL;
free(phead);
return true;
}
/**
* @name : CircLinkList_TailDel
* @brief : 在链表尾部删除首节点
* @param
@head : 表示在哪个链表中
* @retval : 删除成功返回true,反之，返回flase
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : NULL
*/
bool CircLinkList_TailDel(circlinkedlist_t *head)
{
//判断链表是否存在
if(NULL == head){
printf("circular linked list do not have head node\n");
return false;
}
//判断链表是否为空
if(head->next == head){
printf("circular linked list is empty\n");
return false;
}
//创建变量，用来存储首节点地址
circlinkedlist_t *prev = head;
circlinkedlist_t *tail = prev->next;
//遍历链表，查找尾节点
while(tail->next != head){
//遍历链表,找到尾节点和尾节点的前一个节点
prev = prev->next;
tail = tail->next;
}
//尾节点的前一个节点的下一个节点指向Head头节点
prev->next = head;
//释放尾节点
tail->next = NULL;
return true;
}
/**
* @name : CircLinkList_DestDel
* @brief : 在链表中删除与目标值相同的值
* @param
@head : 表示在哪个链表中
@dest : 表示链表中的要删除的值
* @retval : 删除成功返回true,反之，返回flase
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : NULL
*/
bool CircLinkList_DestDel(circlinkedlist_t *head,Datatype_t dest)
{
//判断链表是否存在
if(NULL == head){
printf("circular linked list do not have head node\n");
return false;
}
//判断链表是否为空
if(head->next == head){
printf("circular linked list is empty\n");
return false;
}
//定义一个变量存储头节点地址
circlinkedlist_t *phead = head;
//定义一个变量存储首节点地址
circlinkedlist_t *dest_node = phead->next;
//遍历链表，找到第一个节点值与目标值相同
while(dest_node != head){
//如果找到目标值，将目标值的前一个节点的下一个节点指向目标值的下一个节点；
if(dest_node->data == dest){
phead->next = dest_node->next;
//将目标节点的下一个指针指向NULL
dest_node->next = NULL;
//释放目标值的内容
free(dest_node);
//将目标值节点指针置空，指向NULL
dest_node = NULL;
return true;
}
//遍历链表
phead = phead->next;
dest_node = dest_node->next;
}
//如果没有从while返回，说明没有找到目标值，退出
printf("circular linked list do not have dest value\n");
return false;
}
/**
* @name : CircLinkList_show
* @brief : 遍历循环单链表
* @param
@head : 表示在哪个链表中
* @retval : NULL
* @date : 2025-12-10
* @version 1.0 : V1.0
* @note : 先判断链表是否存在，再判断链表是否为空，遍历链表，打印链表的值
*/
void CircLinkList_show(circlinkedlist_t *head)
{
//判断链表是否存在
if(NULL == head){
printf("circular linked list do not have head node\n");
return;
}
//判断链表是否为空
if(head->next == head){
printf("circular linked list do not have valid value\n");
return;
}
//创建一个指针存储头节点的地址
circlinkedlist_t *phead = head;
//遍历链表并打印节点的值
while(phead->next != head){
printf("current node value = %d\n",phead->next->data);
phead=phead->next;
}
}
main.c
#include "circlinkedlist.h"
int main(int argc,char const * argv[])
{
//创建链表，用head指针表示该链表
circlinkedlist_t *head = CircLinkList_create();
//判断链表是否创建出来
if(NULL == head){
printf("create circular linkedlist failed in main for head\n");
return -1;
}
//头部插入
CircLinkList_HeadAdd(head,35);
//链表遍历
CircLinkList_show(head);
printf("--------------------------------------------------------------\n");
CircLinkList_HeadAdd(head,10);
CircLinkList_HeadAdd(head,43);
CircLinkList_HeadAdd(head,68);
CircLinkList_HeadAdd(head,53);
CircLinkList_HeadAdd(head,57);
CircLinkList_show(head);
printf("--------------------------------------------------------------\n");
//尾部插入
CircLinkList_TailAdd(head,99);
CircLinkList_show(head);
printf("--------------------------------------------------------------\n");
//目标后面插入
CircLinkList_MidAdd(head,53,40);
CircLinkList_show(head);
printf("--------------------------------------------------------------\n");
//头部删除
CircLinkList_HeadDel(head);
CircLinkList_show(head);
printf("--------------------------------------------------------------\n");
//目标删除
CircLinkList_DestDel(head,68);
CircLinkList_DestDel(head,70);
CircLinkList_show(head);
printf("--------------------------------------------------------------\n");
//尾部删除
CircLinkList_TailDel(head);
CircLinkList_show(head);
printf("--------------------------------------------------------------\n");
return 0;
}
发表回复