数据结构详解：单循环链表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;
}
热门推荐
咳嗽用力后腰疼？可能是这些原因！
2025年以旧换新政策全解读：消费者如何享受最大优惠？
与ENTJ老板相处的艺术：三大策略助你职场突围
世界食品安全日：联合国呼吁全球关注食品安全问题
如何简单又干净地洗龙虾：14个步骤详解
自制美味小龙虾：4斤仅需60元，口感媲美餐馆
双十一珍珠项链选购全攻略：从分类到保养，教你挑选高性价比美珠
克利奥帕特拉的珍珠项链：一段跨越千年的传奇
从剑桥走出的科学巨匠：牛顿的学术之路
剑桥大学：一座孕育人文与科学的学术殿堂
亨利三世的飭令：剑桥大学崛起的起点
剑桥大学：814年的学术传奇
剑桥大学人文精神大揭秘：你不知道的秘密！
虎鲸：海洋中的智慧猎手
跟猴子有关的寓言故事精选
厨房秤选购指南：从精度到材质，一文详解选购要点
一直不温不火的她，决定“重新出道”？
靖康之变中的徐秉哲：从政绩良臣到卖国罪人
再次夭折！曾抱尸17天的虎鲸妈妈，痛失第四只小鲸
海中胖虎——虎鲸
秦国军功爵位制：从战场到贵族生活的途径
如何理解金融市场中的各类操作与风险？这些操作和风险如何进行有效管理？
如何计算封单金额并理解其市场意义？这种市场意义对交易决策有何影响？
从挂单盘口预判主力资金动向：四种挂单方式详解
坐飞机5岁的孩子需要购买机票吗？一大人带一小孩订机票怎么订
2024高铁小孩收费标准！
0糖0脂0添加……食品标签里的那些“0”你认识吗？
哪些属于商业行为
什么是GMP认证？认证流程是怎么样的？
海棠树和樱花树枝干病害防治指南