数据结构详解：单循环链表CList的实现与应用
创作时间:
作者:
@小白创作中心
数据结构详解：单循环链表CList的实现与应用
引用
CSDN
1.
https://blog.csdn.net/weixin_75197906/article/details/146158198
单循环链表是一种常见的线性数据结构，它在许多计算机科学和软件工程领域都有广泛的应用。本文将详细介绍单循环链表的定义、基本操作及其C语言实现，帮助读者全面理解这一重要数据结构。
一、单循环链表的定义
单循环链表是一种线性数据结构，其中每个节点包含两个部分：
- 数据域：存储数据元素。
- 指针域：存储指向下一个节点的指针。
与普通单链表不同的是，单循环链表的最后一个节点的指针指向头节点，而不是NULL。这种环状结构使得单循环链表在某些场景下具有独特的优势。
二、单循环链表的操作
2.1 定义
typedef int ELEM_TYPE;
//单循环链表的有效节点的结构体设计
typedef struct CNode
{
ELEM_TYPE data;//数据域
struct CNode* next;//指针域(保存下一个有效节点的地址)
}CNode, * PCNode;
2.2 初始化
void Init_CList(CNode* plist)
{
plist->next = plist;//指针域指向自身
}
plist->next = plist;：将头节点的next指针指向它自己。- 目的：形成一个空的环状结构。
- 意义：在单循环链表中，最后一个节点的
next指针会指向头节点，而当链表为空时，头节点的next指针也指向它自己，表示链表中没有其他节点。
2.3 插入
2.3.1 头插
bool Insert_head(CNode* plist, ELEM_TYPE val)
{
//0.assert
assert(plist != NULL);
if (plist == NULL)
{
return false;
}
//1.购买新节点
CNode* pnewnode = (CNode*)malloc(sizeof(CNode));
if (pnewnode == NULL)
exit(1);
pnewnode->data = val;
//2.找到合适的待插入位置
//因为是头插 比较特殊，就是插入在辅助节点的后边
//3.插入
pnewnode->next = plist->next;
plist->next = pnewnode;
return true;
}
2.3.2 尾插
bool Insert_tail(CNode* plist, ELEM_TYPE val)
{
//0.assert
assert(plist != NULL);
//1.购买新节点
CNode* pnewnode = (CNode*)malloc(sizeof(CNode));
if (pnewnode == NULL)
exit(1);
pnewnode->data = val;
//2.找到合适的待插入位置
//尾插，需要让临时指针p，停在当前的尾结点处
CNode* p = plist;
while (p->next != plist)
{
p = p->next;
}
//3.插入(两行代码)
pnewnode->next = p->next;
p->next = pnewnode;
return true;
}
- 从头节点开始，通过循环找到链表的尾节点。
- 条件：
p->next != plist，说明当前节点的下一个节点不是头节点，即当前节点不是尾节点。 - 当循环结束时，
p指向尾节点。 pnewnode->next = p->next;：将新节点的next指针指向头节点（因为尾节点的next指向头节点）。p->next = pnewnode;：将尾节点的next指针指向新节点，完成插入操作。
2.3.3 按位置插
2.4 删除
2.4.1 头删
bool Del_head(CNode* plist)
{
//0.安全性处理
assert(plist != NULL);
if (plist == NULL)
return false;
//1.对单循环链表判空
if (Is_Empty(plist))
return false;
//2.需要一个临时指针q指向待删除节点
//因为是头删，所以待删除节点就是第一个有效值节点
CNode* q = plist->next;
//3.再需要一个临时指针p指向待删除节点的前驱(上一个节点)
//因为是头删,所以这里的p用辅助节点plist代替即可
//4.跨越指向+释放
plist->next = q->next;
free(q);
q = NULL;
return true;
}
- 定义一个临时指针
q，指向第一个有效节点（即头节点的下一个节点） plist->next = q->next;：将头节点的next指针指向q的下一个节点，即跨越q节点。free(q);：释放q节点的内存。q = NULL;：将q指针置为NULL，避免野指针。
2.4.2 尾删
bool Del_tail(CNode* plist)
{
//0.安全性处理
assert(plist != NULL);
if (plist == NULL)
return false;
//1.对单循环链表判空
if (Is_Empty(plist))
return false;
//2.需要一个临时指针q指向待删除节点
CNode* q = plist;
for (; q->next != plist; q = q->next);
//3.再需要一个临时指针p指向待删除节点的前驱(上一个节点)
CNode* p = plist;
for (; p->next != q; p = p->next);
//4.跨越指向+释放
p->next = q->next;
free(q);
q = NULL;
return true;
}
2.4.3 按位置删
bool Del_pos(CNode* plist, int pos)
{
//0.安全性处理
assert(plist != NULL);
if (plist == NULL)
return false;
assert(pos >= 0 && pos < Get_length(plist));
//1.对单循环链表判空
if (Is_Empty(plist))
return false;
//2.需要一个临时指针q指向待删除节点
//3.再需要一个临时指针p指向待删除节点的前驱(上一个节点)
CNode* p = plist;
for (int i = 0; i < pos; i++)
p = p->next;
CNode* q = p->next;
//4.跨越指向+释放
p->next = q->next;
free(q);
q = NULL;
return true;
}
2.4.4 按值删
//8.按值删(删除值val出现的第一次的地方)
bool Del_val(CNode* plist, ELEM_TYPE val)
{
//0.安全性处理
assert(plist != NULL);
if (plist == NULL)
return false;
//1.对单循环链表判空
if (Is_Empty(plist))
return false;
//2.需要一个临时指针q指向待删除节点
//通过Search去找一下，val值出现的第一次的位置
CNode* q = Search(plist, val);
if (q == NULL)
return false;
//3.再找到待删除节点的前驱，用p指向
CNode* p = plist;
for (; p->next != q; p = p->next);
//4.跨越指向+释放
p->next = q->next;
free(q);
q = NULL;
return true;
}
//8.5 按值删(删除值val出现的所有的地方)
bool Del_val_all(CNode* plist, ELEM_TYPE val)
{
CNode* p = plist;
CNode* q = plist;
while (p->next != plist)
{
q = p->next;
if (q->data == val)
{
p->next = q->next;
free(q);
q = NULL;
}
else
{
p = q;
}
}
return true;
}
2.5 其余代码
//9.查找(查找值val出现的第一次的地方)
CNode* Search(CNode* plist, ELEM_TYPE val)
{
for (CNode* p = plist->next; p != plist; p = p->next)
{
if (p->data == val)
{
return p;
}
}
return NULL;
}
//10.清空
void Clear(CNode* plist)
{
Destroy1(plist);
}
//11.销毁1(需要辅助节点参与进来)
void Destroy1(CNode* plist)
{
while (plist->next != plist)
{
CNode* p = plist->next;
plist->next = p->next;
free(p);
p = NULL;
}
}
//12.销毁2(不需要辅助节点参与进来)
void Destroy2(CNode* plist)
{
//0.assert head
//1.申请指针p，让其保存辅助节点的指针域
CNode* p = plist->next;
//2.申请指针q，先不给q赋值
CNode* q = NULL;
//3.反复通过p和q打配合，去销毁后续节点
while (p != plist)
{
q = p->next;
free(p);
p = q;
}
//4.节点全部销毁完毕，别忘了把辅助节点的指针域处理一下
plist->next = plist;
}
//13.判空
bool Is_Empty(CNode* plist)
{
return plist->next == plist;
}
//14.获取有效值长度
int Get_length(CNode* plist)
{
int count = 0;
for (CNode* p = plist->next; p != plist; p = p->next)
{
count++;
}
return count;
}
//15.打印
void Show(CNode* plist)
{
for (CNode* p = plist->next; p != plist; p = p->next)
{
printf("%d ", p->data);
}
printf("\n");
}
2.6 主函数测试代码
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include "clist.h"
单循环链表的测试用例
int main()
{
CNode head;
Init_CList(&head);
Insert_head(&head, 100);
Insert_tail(&head, 200);
Insert_head(&head, 300);
Insert_tail(&head, 400);
Show(&head);
Del_head(&head);
Show(&head);
Del_tail(&head);
Show(&head);
Del_pos(&head, 1);
Show(&head);
Del_val(&head, 100);
Show(&head);
Insert_tail(&head, 1);
Insert_tail(&head, 2);
Insert_tail(&head, 1);
Insert_tail(&head, 4);
Insert_tail(&head, 1);
Show(&head);
Del_val_all(&head, 1);
Show(&head);
return 0;
}
热门推荐
怎么提高自己的即兴表演和演讲的能力
守望先锋如何才能提升准度？
“保水虾仁”，浮出水面！1斤虾仁7两冰……
考古学家王巍：三星堆与中原文明在青铜原料方面有共同来源
2024年前三季度泸州市地区生产总值（GDP）2044.8亿元，同比增长3.7%
大爷吃几十年猪油都没事，为何有人说猪油不健康？
吃猪油的好处，只有一个
古代凶厄之兽：讹兽的神秘传说
如何确定外观专利侵权？判定方法与标准详解
中药炮制，让匠心融入创新
“京帆”撑起绿色城市会客厅 副中心站枢纽年节电超48万度
城市副中心：以“含绿量”推动“含金量”！生态环境持续向好——
高考高校专项计划是什么意思 有什么优势
四肢瘦肚子大是脾虚吗？多种原因及解决方案详解
健康科普：常见异常步态分析
如何打造一个具有影响力的品牌口号：提升品牌形象的关键技巧
三体宇宙入局虚拟现实 “IP+VR”打开更大想象空间
换电池要掏22万元？第一批新能源车到了换电池周期，车主怎么办
一生气就触发咳嗽？警惕5种疾病来“拜访”！
摩托车可以上高速吗？一文详解各地规定与安全要求
如何提升云盘下载速度
瓜蒌薤白半夏汤的有效成分及作用机制
流感大量喝水有用吗？这些利弊要知道
大学生考研怎么选学校和专业？看看这里就知道了！
PS5 Pro 與 Xbox Series X：哪個更好？它們有何不同？
强化学习成帮凶，对抗攻击LLM有了新方法
如何让自己更有魅力？你可能缺乏的是一点“攻击性”
男人更年期的表现及应对方法
智慧居家养老服务平台的设计与实现方案
如何提升大学生自我管理能力