数据结构详解：单循环链表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;
}
热门推荐
产后服用中药是否会影响母乳
2024年中国陶瓷行业深度分析：产业链全景、市场供需、竞争格局及发展趋势
税号与统一社会信用代码：定义、区别及应用指南
银行债券市场的投资策略与风险控制
西门子S7-1200 PLC编程及应用教程（第2版）
全球视角下的袁隆平：中国杂交水稻的国际影响力与赞誉
城市桥梁结构组成与类型
微生物学的发展史
槽波透视勘探技术在淮北某矿8102里工作面隐伏地质构造探查工程中的应用
国债期货交易特点与策略全解析
对方起诉离婚怎么应对措施呢
海南医科大学第一附属医院：建设热带特色鲜明的国际化高水平医院
大学学习计划设计方法
白头发是怎么长出来的，还能变黑吗？
记者亲历低收入者生活：住进“罐子”的劳动力
常见抗心绞痛药物及使用注意事项
普通人面对失业该怎样做呢？
仙人掌叶子的特点及适应环境能力（探索仙人掌植物叶子的奇特结构和功能）
舟山必游景点TOP排行榜：探索海洋文化的绝佳去处
2025，燃料电池汽车驶向蓬勃发展拐点
解日头条新闻法律热点与社会影响
有限元分析从定义到场景到硬件配置详细讲解
喝乐虎有什么好处和坏处
青岛即墨：开通疾控公益科普直播间 打造健康教育新模式
揭秘中国历史上五大未解之谜：奇闻异事背后的真相
张艺谋组建AI团队，“AI+影视”浪潮汹涌
香港城市大学硕士专业汇总及申请条件2025
什么商品期货适合短线操作？这些商品有什么独特的交易特性？
襄阳中医医院药学专家创新太阳能干燥技术获国际关注
学习酒店与旅游管理：终极学生指南