数据结构——单循环链表clist

server/2025/3/14 9:59:38/

前言：大家好😍，本文主要介绍了数据结构——单循环链表clist

目录

一、单循环链表的定义

二、单循环链表的操作

2.1 定义

2.2 初始化 

 2.3 插入

2.3.1 头插

2.3.2 尾插 

2.3.3 按位置插 

​  2.4 删除

2.4.1 头删

2.4.2 尾删

2.4.3 按位置删

2.4.4 按值删

2.5 其余代码

2.6 主函数测试代码

一、单循环链表的定义

单循环链表是一种线性数据结构，其中每个节点包含两个部分：

  1. 数据域：存储数据元素。

  2. 指针域：存储指向下一个节点的指针。

与普通单链表不同的是，单循环链表的最后一个节点的指针指向头节点，而不是 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.assertassert(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.assertassert(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;
}

http://www.ppmy.cn/server/174850.html

相关文章

2025年Java面试题目收集整理归纳（持续更新）

2025年Java面试题目收集整理归纳（持续更新）

Java基础系列面试题 为了帮助大家更好地准备 Java 面试&#xff0c;我整理了这份 Java 基础面试题合集。这份合集涵盖了 Java 核心知识点&#xff0c;包括&#xff1a; Java 基础语法: 数据类型、运算符、流程控制、数组、字符串等面向对象编程: 类和对象、继承、多态、抽象类…
阅读更多...
代码社区开源协议

代码社区开源协议

开源协议是一种法律文件&#xff0c;用于规定开源软件的使用、修改和分发条件。它平衡了开发者和使用者的权益&#xff0c;同时推动开放协作与技术创新。以下是常见的开源协议及其特点和适用场景&#xff1a; 常见开源协议列表及介绍 1. MIT License 特点&#xff1a;非常宽…
阅读更多...
基于Spring Boot的宠物猫认养系统的设计与实现（LW+源码+讲解）

基于Spring Boot的宠物猫认养系统的设计与实现（LW+源码+讲解）

专注于大学生项目实战开发,讲解,毕业答疑辅导&#xff0c;欢迎高校老师/同行前辈交流合作✌。 技术范围&#xff1a;SpringBoot、Vue、SSM、HLMT、小程序、Jsp、PHP、Nodejs、Python、爬虫、数据可视化、安卓app、大数据、物联网、机器学习等设计与开发。 主要内容&#xff1a;…
阅读更多...
Ubuntu服务器安装JupyterNotebook，以便通过浏览器访问Jupyter

Ubuntu服务器安装JupyterNotebook，以便通过浏览器访问Jupyter

1.安装Anaconda/Miniconda 在Ubuntu中安装Miniconda 2.创建环境 conda create -n jupyter_env python3.12 3.安装 conda install jupyter notebookpip install -U jupyter 4.配置&#xff0c;生成访问密码 # 1.进入python环境 python# 2.生成sha1密码 from jupyter_serv…
阅读更多...
设计模式C++

设计模式C++

针对一些经典的常见的场景, 给定了一些对应的解决方案&#xff0c;这个就叫设计模式。 设计模式的作用&#xff1a;使代码的可重用性高&#xff0c;可读性强&#xff0c;灵活性好&#xff0c;可维护性强。 设计原则&#xff1a; 单一职责原则&#xff1a;一个类只做一方面的…
阅读更多...
构建rknn的docker镜像

构建rknn的docker镜像

文章目录 安装docker更改镜像源编写dockerfile构建docker镜像构建docker容器 安装docker 瑞芯微开发板自带docker环境&#xff0c;可跳过 # 删除老版本的docker sudo apt-get remove docker docker-engine# 开始安装 sudo apt-get update sudo apt-get install docker.io# 查…
阅读更多...
深入理解C++ stl::list 底层实现+模拟实现

深入理解C++ stl::list 底层实现+模拟实现

欢迎来到干货小仓库!!! "人生没有 Ctrl - Z &#xff0c;但永远可以 push 新版本" 1.list的介绍 ①stl::list的底层实现是带头双向循环链表结构。 ②list是可以在常数范围内在任意位置进行插入和删除的序列式容器&#xff0c;并且该容器可以前后双向迭代。 ③双向…
阅读更多...
5-24 色彩与风格——T2IA自适应

5-24 色彩与风格——T2IA自适应

前言&#xff1a; 上一节我们介绍了ControlNet中的inpaint局部重绘 主要介绍ControlNet中的T2IA自适应。 色彩风格的参考和借鉴能力&#xff0c;有点类似于5-17 reference参考图 或者 5-16 画面风格迁移-shuffle洗牌 。当然在硬件的要求&#xff0c;软件的算法实现和使用方式…
阅读更多...
最新文章

Copyright @ 2022~2023