数据结构详解：单循环链表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;
}
热门推荐
信息安全三剑客：漏洞扫描、渗透测试与攻防演练
宝可梦朱紫七星炎武王打法详解
嵌入式人工智能：概念、技术与应用
我们在长江做水情“精算师”
出租房屋应缴纳房产税：法律规定的义务与注意事项
致敬科学女神，改变世界的11位女性。｜诺贝尔奖得主邀约赋能
工商业储能电站的储能技术
投资比特币前须知，比特币波动率有多大？还会一天腰斩吗？
内蒙古扎赉特旗：新业态新场景促旅游热起来
如何打造有趣的团队活动
探讨汉字“兮”的读音、文化内涵及其在现代生活中的独特魅力
公务员考试行测推理题型解析及备考指南
阿司匹林能不能和降压药一起服用？医生说，因人而异
阿司匹林能不能和降压药一起服用？医生说，因人而异
怎么把Excel里面的表格间距调一致
满天星肥料指南（打造鲜艳而健康的满天星）
个人征信对贷款有什么影响
守护锂电安全生命线：隔膜技术的重要性与进展
摩托车性能评价看这几条就够了！
涉及农用地转用或征地的，必须经过什么批准
在线考试防作弊，三阶段严密措施保公正
中央红军长征中女红军人数的谜团
乡镇交通运输发展计划与2025年总结
如何通过4个步骤优化工程项目资源分配
Excel选号完全指南：从基础到高级应用
狗狗摇尾巴一定是开心吗？那就错了，这种情况下也会摇尾巴
中部大运河，真的要来了？
出海情报局：湘菜出海马来西亚合规指南
屋顶租赁合同标准及注意事项
屋顶租赁合同标准及注意事项