当前位置: 首页 > news >正文

数据结构与算法学习笔记之线性表五---循环链表的表示和实现(C++)

目录

前言

1.双向链表的定义

2.双向链表的表示和实现

1.定义

2.初始化

3.销毁

4.清空

5.表长

6.获取数据元素

7.前驱节点

8.后继节点

9.插入

10.删除

11.遍历

12.完整代码


前言

        记录下双向链表的表示和实现。

1.循环链表的定义

        循环链表(circular linked list)是另一种形式的链式存储结构。它的特点是表中最后一个结点的指针域指向头结点,整个链表形成一个环。由此,从表中任一结点出发均可找到表中其他结点,如图 2.12所示为单链的循环链表。类似地,还可以有多重链的循环链表。。

2.循环链表的表示和实现

1.定义

typedef int Status;
typedef int ElemType;
// 定义循环链表
typedef struct CircularNode {ElemType data; // 数据域struct CircularNode * next; // 直接后继
}CircularNode,*CircularLinkedList;

2.初始化

        初始化双向链表,next指针指向自己。

// 初始化循环链表
Status initCircularLinkedList(CircularLinkedList &circularLinkedList){circularLinkedList = new CircularNode;if (!circularLinkedList) {//内存分配失败return 0;}circularLinkedList->next = circularLinkedList; // 将头节点的指针指向自身,形成循环return 1;
}

3.销毁

// 循环链表销毁
void destroyCircularLinkedList(CircularLinkedList &circularLinkedList) {if (!circularLinkedList) {return; // 链表为空,无需销毁}CircularLinkedList current = circularLinkedList->next; // 从第一个节点开始while (current != circularLinkedList) { // 遍历至头节点CircularLinkedList temp = current; // 暂存当前节点current = current->next; // 移动到下一个节点delete temp; // 释放当前节点内存}delete circularLinkedList; // 释放头节点内存circularLinkedList = nullptr; // 头指针置为空
}

4.清空

// 循环链表清空
void clearCircularLinkedList(CircularLinkedList &circularLinkedList) {if (!circularLinkedList) {return; // 链表为空,无需清空}CircularLinkedList current = circularLinkedList->next; // 从第一个节点开始while (current != circularLinkedList) { // 遍历至头节点CircularLinkedList temp = current; // 暂存当前节点current = current->next; // 移动到下一个节点delete temp; // 释放当前节点内存}circularLinkedList->next = circularLinkedList; // 头节点的 next 指针指向自身,链表置为空链表
}

5.表长

// 循环链表表长
int getCircularLinkedListLength(CircularLinkedList &circularLinkedList) {int length = 0;CircularNode *p = circularLinkedList->next; // 从第一个节点开始计数while (p != circularLinkedList) { // 当指针指向头节点时结束循环++length;p = p->next;}return length;
}

6.获取数据元素

// 获取循环链表中的元素
Status getCircularLinkedListElement(CircularLinkedList &circularLinkedList, int position, int *element) {if (position < 1 || position > getCircularLinkedListLength(circularLinkedList)) { // 非法位置return 0;}CircularNode *p = circularLinkedList->next; // 从第一个节点开始遍历int index = 1;while (index < position) { // 定位到指定位置p = p->next;index++;}*element = p->data; // 将节点的数据域值赋给 elementreturn 1;
}

7.前驱节点

// 获取循环链表中的第一个与element相同的元素的直接前驱
Status priorCircularLinkedListElement(CircularLinkedList &circularLinkedList, int element, int *priorElement) {if (isCircularLinkedListEmpty(circularLinkedList)) { // 空链表return 0;}CircularNode *p = circularLinkedList->next;CircularNode *pre = circularLinkedList; // 前驱节点do {if (p->data == element) { // 找到要查找的节点*priorElement = pre->data;return 1;}pre = p;p = p->next;} while (p != circularLinkedList->next); // 循环直到回到起始节点return 0; // 未找到相同元素
}

8.后继节点

        先判断循环链表是否是空链表,然后遍历删除节点。

// 获取循环链表中的第一个与element相同的元素的后继节点
Status nextCircularLinkedListElement(CircularLinkedList &circularLinkedList, int element, int *nextElement) {if (isCircularLinkedListEmpty(circularLinkedList)) { // 空链表return 0;}CircularNode *p = circularLinkedList->next;do {if (p->data == element) { // 找到要查找的节点*nextElement = p->next->data;return 1;}p = p->next;} while (p != circularLinkedList->next); // 循环直到回到起始节点return 0; // 未找到相同元素
}

9.插入

         首先判断插入位置是否合法,然后分别处理头结点和非头结点的情况。

// 循环链表插入
Status insertCircularLinkedList(CircularLinkedList &circularLinkedList, int i, int element) {if (i < 1) { // 插入位置非法return 0;}CircularNode *newNode = new CircularNode; // 新节点if (!newNode) { // 内存分配失败return 0;}newNode->data = element;if (i == 1) { // 插入到表头if (circularLinkedList == nullptr) { // 空链表newNode->next = newNode; // 自己指向自己circularLinkedList = newNode;} else {CircularNode *last = circularLinkedList;while (last->next != circularLinkedList) { // 找到最后一个节点last = last->next;}newNode->next = circularLinkedList; // 新节点指向表头last->next = newNode; // 最后一个节点指向新节点circularLinkedList = newNode; // 更新表头指针}} else { // 插入到非表头位置CircularNode *p = circularLinkedList;int j = 1;while (p->next != circularLinkedList && j < i - 1) { // 找到插入位置的前一个节点p = p->next;++j;}if (j < i - 1) { // 插入位置超出链表长度delete newNode;return 0;}newNode->next = p->next; // 新节点指向原来位置节点p->next = newNode; // 前一个节点指向新节点}return 1;
}

10.删除

        首先判断删除位置是否合法,然后分别处理头结点和非头结点的情况。

// 循环链表删除
Status deleteCircularLinkedList(CircularLinkedList &circularLinkedList, int position, ElemType *deletedElement) {if (position < 1 || circularLinkedList == nullptr) { // 删除位置非法或链表为空return 0;}if (position == 1) { // 删除表头节点CircularNode *temp = circularLinkedList;*deletedElement = temp->data; // 存储被删除节点的数据if (circularLinkedList->next == circularLinkedList) { // 链表只有一个节点delete temp;circularLinkedList = nullptr;} else {CircularNode *last = circularLinkedList;while (last->next != circularLinkedList) { // 找到最后一个节点last = last->next;}last->next = circularLinkedList->next; // 最后一个节点指向第二个节点circularLinkedList = circularLinkedList->next; // 更新表头指针delete temp; // 释放被删除节点的内存}} else { // 删除非表头节点CircularNode *p = circularLinkedList;int j = 1;while (p->next != circularLinkedList && j < position - 1) { // 找到要删除节点的前一个节点p = p->next;++j;}if (j < position - 1 || p->next == circularLinkedList) { // 删除位置超出范围return 0;}CircularNode *temp = p->next; // 要删除的节点*deletedElement = temp->data; // 存储被删除节点的数据p->next = temp->next; // 前一个节点指向后一个节点delete temp; // 释放被删除节点的内存}return 1;
}

11.遍历

        遍历循环链表

// 遍历循环链表
void traverseCircularLinkedList(CircularLinkedList &circularLinkedList) {if (circularLinkedList == nullptr) { // 空链表return;}CircularNode *p = circularLinkedList;do {cout << p->data << "\t"; // 输出当前节点的数据p = p->next; // 移动到下一个节点} while (p != circularLinkedList); // 循环直到回到起始节点cout << endl;
}

12.测试代码

void  testCircularLinkedList(void) {CircularLinkedList circularLinkedList;cout<<"\n**********\t循环链表初始化\t**********"<<endl;if (initCircularLinkedList(circularLinkedList)) {cout<<"顺序表初始化成功"<<endl;}cout<<"\n**********\t循环链表判空和长度计算\t**********"<<endl;if (isCircularLinkedListEmpty(circularLinkedList)) {cout<<"循环链表为空,长度为"<<getCircularLinkedListLength(circularLinkedList)<<endl;}cout<<"\n**********\t循环链表插入测试\t**********"<<endl;for (int i = 1; i <=11 ; i++) {if (insertCircularLinkedList(circularLinkedList,i, i)) {cout<<"数据元素"<<i<<"插入成功"<<endl;}else{cout<<"数据元素"<<i<<"插入失败"<<endl;}}traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表根据下标获取数据元素测试\t**********"<<endl;for (int i = 0; i <= 12 ; i++) {int element;if (getCircularLinkedListElement(circularLinkedList,i, &element)) {cout<<"第"<<i<<"个数据元素为"<<element<<endl;}else{cout<<"第"<<i<<"个数据元素不存在"<<endl;}}cout<<"插入之后的循环链表"<<endl;traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表删除测试\t**********"<<endl;ElemType element;if (deleteCircularLinkedList(circularLinkedList, 11, &element)){cout<<"数据元素"<<element<<"删除成功"<<endl;}cout<<"删除之后的循环链表"<<endl;traverseCircularLinkedList(circularLinkedList);cout<<"\n**********\t循环链表后继节点测试\t**********"<<endl;int nextArr[3] = {1,8,11};for (int i = 0; i < 3; i++) {ElemType nextElement;if (nextCircularLinkedListElement(circularLinkedList, nextArr[i], &nextElement)) {cout<<"数据元素"<<nextArr[i]<<"后继节点为:"<<nextElement<<endl;}else{cout<<"数据元素"<<nextArr[i]<<"后继节点不存在"<<endl;}}cout<<"\n**********\t循环链表前驱节点测试\t**********"<<endl;int priorArr[3] = {8,11,1};for (int i = 0; i < 3; i++) {ElemType priorElement;if (priorCircularLinkedListElement(circularLinkedList, priorArr[i], &priorElement)) {cout<<"数据元素"<<priorArr[i]<<"前驱节点为"<<priorElement<<endl;}else{cout<<"数据元素"<<priorArr[i]<<"前驱节点不存在"<<endl;}}cout<<"\n**********\t循环链表销毁\t**********"<<endl;destroyCircularLinkedList(circularLinkedList);cout<<"循环链表销毁"<<endl;}

相关文章:

数据结构与算法学习笔记之线性表五---循环链表的表示和实现(C++)

目录 前言 1.双向链表的定义 2.双向链表的表示和实现 1.定义 2.初始化 3.销毁 4.清空 5.表长 6.获取数据元素 7.前驱节点 8.后继节点 9.插入 10.删除 11.遍历 12.完整代码 前言 记录下双向链表的表示和实现。 1.循环链表的定义 循环链表(circular linked list)…...

微信小程序生命周期揭秘:从启动到消亡的全过程剖析【附代码】

微信小程序生命周期揭秘&#xff1a;从启动到消亡的全过程剖析 一、小程序生命周期概览核心生命周期函数 二、深入理解生命周期回调2.1 onLoad: 首次亮相的准备2.2 onShow: 重登舞台的瞬间2.3 onReady: 舞台就绪&#xff0c;静待表演2.4 onHide & onUnload: 谨慎离场&#…...

Linux 下载 miniconda

https://repo.anaconda.com/miniconda/ 下载对应版本&#xff1a; wget -c https://repo.anaconda.com/miniconda/Miniconda3-py310_24.3.0-0-Linux-x86_64.sh给下载的文件添加可执行权限 chmod x Miniconda3-py310_24.3.0-0-Linux-x86_64.sh安装 ./Miniconda3-py310_24.3.…...

第十五篇:全面防护:构建不容侵犯的数据库安全策略与实战指南

全面防护&#xff1a;构建不容侵犯的数据库安全策略与实战指南 1. 引言&#xff1a;数据库安全的现代战略 1.1 简介&#xff1a;数据库安全在当今的数字化时代中的重要性 在数字化的浪潮中&#xff0c;数据已成为企业乃至国家的核心资产&#xff0c;其价值不亚于实体世界的黄…...

电脑快速搜索文件及文件夹软件——Everything

一、前言 Everything是一款由voidtools开发的文件搜索工具&#xff0c;主要运行于Windows操作系统上。它的主要功能是快速、高效地搜索电脑上的文件和文件夹名称。Everything通过利用NTFS文件系统的MFT&#xff08;主文件表&#xff09;来索引文件&#xff0c;从而实现几乎实时…...

02-登录页面、动态路由、权限等模块开发

权限模块开发流程 前端login页面开发后端SpringSecurity配置后端login接口开发前端页面框架搭建前端路由守卫&#xff0c;状态管理开发前后端完成认证流程 开发Login页面 创建Login页面创建router&#xff0c;可以跳转到Login页面 Login页面 使用element-plus开发 认证功…...

万物生长大会 | 创邻科技再登杭州准独角兽榜单

近日&#xff0c;由民建中央、中国科协指导&#xff0c;民建浙江省委会、中国投资发展促进会联合办的第八届万物生长大会在杭州举办。 在这场创新创业领域一年一度的盛会上&#xff0c;杭州市创业投资协会联合微链共同发布《2024杭州独角兽&准独角兽企业榜单》。榜单显示&…...

(六)Linux的Shell编程(上)

一.Shell Shell 是一个用 C 语言编写的程序,它是用户使用 Linux 的桥梁。Shell 既是一种命令语言,又是一种程序设计语言。Shell 是指一种应用程序,这个应用程序提供了一个界面,用户通过这个界面访问操作系统内核的服务。Ken Thompson 的 sh 是第一种 Unix Shell,Windows …...

CANopen总线_CANOpen开源协议栈

CANopen是自动化中使用的嵌入式系统的通信协议栈和设备配置文件规范。就OSI 模型而言&#xff0c;CANopen 实现了以上各层&#xff0c;包括网络层。 CANopen 标准由一个寻址方案、几个小型通信协议和一个由设备配置文件定义的应用层组成。通信协议支持网络管理、设备监控和节点…...

Rust 语言不支持 goto 语句

一、Rust 不提供 goto 语句 Rust 语言并没有提供 goto 语句。goto 语句在很多现代编程语言中已经不再被推荐使用&#xff0c;因为它可能导致代码的流程变得难以跟踪和理解&#xff0c;特别是在复杂的程序中。Rust 语言设计者选择了更加结构化和可预测的控制流语句&#xff0c;…...

uniapp日期区间选择器

uniapp日期区间选择器 在 uniapp 中创建一个简单的自定义日期范围的日期区间选择器&#xff1a; - 限制有效日期范围开始日期为 2024-01-01&#xff0c;结束日期为当日&#xff1b; - 默认日期区间为当日向前计算的7日区间&#xff1b; - 选择开始时间后&#xff0c;判断不可大…...

k8s job

ReplicaSet 和 DaemonSet 会持续运行任务&#xff0c;永远达不到完成态。但在一个可完成的任务中&#xff0c;其进程终止后&#xff0c;不应该再重新启动。 Job 允许你运行一种 pod&#xff0c;该 pod 在内部进程成功结束时&#xff0c;不重启容器&#xff0c;一旦任务完成&…...

Python---NumPy万字总结【此篇文章内容难度较大,线性代数模块】(3)

NumPy的应用&#xff08;3&#xff09; 向量 向量&#xff08;vector&#xff09;也叫矢量&#xff0c;是一个同时具有大小和方向&#xff0c;且满足平行四边形法则的几何对象。与向量相对的概念叫标量或数量&#xff0c;标量只有大小&#xff0c;绝大多数情况下没有方向。我们…...

【面试经典题】环形链表

个人主页&#xff1a;一代… 个人专栏&#xff1a;数据结构 在面试中我们经常会遇到有关链表的相关题目&#xff0c;面试官通常会对题目给出拓展 下面我就两个leetcode上的一个双指针的题目为例&#xff0c;并对其进行拓展 题目链接&#xff1a;环形链表 题目描述&#xf…...

【联合索引】最左匹配原则是什么?

什么是联合索引 联合索引&#xff08;Composite Index&#xff09;是一种索引类型&#xff0c;它由多个列组成。 MySQL的联合索引&#xff08;也称为复合索引&#xff09;是建立在多个字段上的索引。这种索引类型允许数据库在查询时同时考虑多个列的值&#xff0c;从而提高查询…...

LeetCode 700.二叉搜索树中的搜索

LeetCode 700.二叉搜索树中的搜索 1、题目 题目链接&#xff1a;700. 二叉搜索树中的搜索 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和一个整数值 val。 你需要在 BST 中找到节点值等于 val 的节点。 返回以该节点为根的子树。 如果节点不存在&#xff0c;则…...

程序设计实践-课程设计任务布置(麦当劳) (price 200)(不包含文档)

WX: help-assignment code price 200&#xff08;不包含文档&#xff01;不包含文档&#xff01;不包含文档&#xff01;&#xff09; 课题任务-概述 2023年5月&#xff0c;麦当劳在北邮开业。大量的学生去那里订餐。正因为如此&#xff0c;麦当劳的在线点餐系统经常关闭以避…...

leetcode 918.环形子数组的最大和

思路&#xff1a;DP 其实和昨天做的哪个重复数组差不多&#xff0c;按顺序来说先做这个题目其实更好。 这里需要分两种情况&#xff1a;第一个&#xff0c;就是数组不越界的时候&#xff0c;这个时候最大子数组和就是leetcode 53题的题解。 如果说越界了&#xff0c;我们还需…...

Spring中用到的设计模式有哪些

工厂模式,BeanFactory就是简单工厂模式的体现,根据传入一个唯一的标识来获得Bean对象。 单例模式,Spring依赖注入Bean实例默认是单例的。Spring依赖注入(包括lazy-init方式)都是发生在AbstractBeanFactory的getBean里。getBean的doGetBean方法调用getSingleton进行bean的创…...

CSS 样式清单整理:文字超出部分显示省略号和设置placeholder的字体样式

单行文本的溢出显示省略号&#xff08;一定要有宽度&#xff09; p{width:200rpx;overflow: hidden;text-overflow:ellipsis;white-space: nowrap;}多行文本溢出显示省略号 p {display: -webkit-box;-webkit-box-orient: vertical;-webkit-line-clamp: 3;overflow: hidden;}设…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

零门槛NAS搭建:WinNAS如何让普通电脑秒变私有云?

一、核心优势&#xff1a;专为Windows用户设计的极简NAS WinNAS由深圳耘想存储科技开发&#xff0c;是一款收费低廉但功能全面的Windows NAS工具&#xff0c;主打“无学习成本部署” 。与其他NAS软件相比&#xff0c;其优势在于&#xff1a; 无需硬件改造&#xff1a;将任意W…...

中南大学无人机智能体的全面评估!BEDI:用于评估无人机上具身智能体的综合性基准测试

作者&#xff1a;Mingning Guo, Mengwei Wu, Jiarun He, Shaoxian Li, Haifeng Li, Chao Tao单位&#xff1a;中南大学地球科学与信息物理学院论文标题&#xff1a;BEDI: A Comprehensive Benchmark for Evaluating Embodied Agents on UAVs论文链接&#xff1a;https://arxiv.…...

IGP(Interior Gateway Protocol,内部网关协议)

IGP&#xff08;Interior Gateway Protocol&#xff0c;内部网关协议&#xff09; 是一种用于在一个自治系统&#xff08;AS&#xff09;内部传递路由信息的路由协议&#xff0c;主要用于在一个组织或机构的内部网络中决定数据包的最佳路径。与用于自治系统之间通信的 EGP&…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

[10-3]软件I2C读写MPU6050 江协科技学习笔记(16个知识点)

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16...

反射获取方法和属性

Java反射获取方法 在Java中&#xff0c;反射&#xff08;Reflection&#xff09;是一种强大的机制&#xff0c;允许程序在运行时访问和操作类的内部属性和方法。通过反射&#xff0c;可以动态地创建对象、调用方法、改变属性值&#xff0c;这在很多Java框架中如Spring和Hiberna…...

Maven 概述、安装、配置、仓库、私服详解

目录 1、Maven 概述 1.1 Maven 的定义 1.2 Maven 解决的问题 1.3 Maven 的核心特性与优势 2、Maven 安装 2.1 下载 Maven 2.2 安装配置 Maven 2.3 测试安装 2.4 修改 Maven 本地仓库的默认路径 3、Maven 配置 3.1 配置本地仓库 3.2 配置 JDK 3.3 IDEA 配置本地 Ma…...

TSN交换机正在重构工业网络,PROFINET和EtherCAT会被取代吗?

在工业自动化持续演进的今天&#xff0c;通信网络的角色正变得愈发关键。 2025年6月6日&#xff0c;为期三天的华南国际工业博览会在深圳国际会展中心&#xff08;宝安&#xff09;圆满落幕。作为国内工业通信领域的技术型企业&#xff0c;光路科技&#xff08;Fiberroad&…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...