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

数据结构之——单循环链表和双向循环链表

一、单循环链表的奥秘

        单循环链表是一种特殊的链表结构,它在数据结构领域中具有重要的地位。其独特的循环特性使得它在某些特定的应用场景中表现出强大的优势。

(一)结构与初始化

单循环链表的结构由节点组成,每个节点包含数据域和指向下一个节点的指针域。与普通单链表不同的是,单循环链表的最后一个节点的指针指向头节点,从而形成一个循环。在初始化单循环链表时,通常先创建一个头节点,头节点的数据域可以存储一些特定信息,比如链表长度等。头节点的指针域指向自身,代表此时链表为空。例如在 C 语言中,可以这样初始化单循环链表:

typedef int ElemType;typedef struct Node 
{ElemType data;struct Node *next;
} Node;typedef struct Node *LinkList;// 初始化单循环链表
void InitList(LinkList &L) 
{// 分配内存空间用于创建头节点L = (LinkList)malloc(sizeof(Node));if (!L) {// 如果内存分配失败,退出程序并返回错误码 OVERFLOWexit(OVERFLOW);}// 将头节点的 next 指针指向自身,形成单循环链表L->next = L;// 头节点的数据域可以用于存储链表的长度等信息,这里初始化为 0L->data = 0;
}

(二)插入与删除操作

1.头插法:头插法是将新节点插入到单循环链表的头部。首先创建新节点,将新节点的指针指向头节点的下一个节点,然后将头节点的指针指向新节点,完成插入操作。例如:

// 在单循环链表头部插入节点
void headInsert(LinkList &L, int data) 
{// 分配新节点内存空间Node *newNode = (Node *)malloc(sizeof(Node));// 设置新节点的数据域为传入的数据newNode->data = data;// 让新节点的 next 指针指向当前链表头部的下一个节点newNode->next = L->next;// 更新链表头部的 next 指针,使其指向新节点L->next = newNode;
}

2.尾插法:尾插法是将新节点插入到单循环链表的尾部。首先找到链表的尾节点,然后将新节点插入到尾节点之后,使其成为新的尾节点。例如:

// 在单循环链表尾部插入节点
void tailInsert(LinkList &L, int data) 
{// 分配新节点内存空间Node *newNode = (Node *)malloc(sizeof(Node));newNode->data = data;newNode->next = L;// 创建一个临时指针用于遍历链表找到尾节点Node *p = L;// 遍历链表直到找到尾节点(即当前节点的下一个节点是头节点)while (p->next!= L) {p = p->next;}// 将尾节点的 next 指针指向新节点p->next = newNode;
}

3.删除操作:删除操作可以分为删除头节点和删除其他节点两种情况。删除头节点时,只需将头节点的指针指向头节点的下一个节点即可。删除其他节点时,需要找到要删除节点的前一个节点,然后将其指针指向要删除节点的下一个节点,完成删除操作。例如:

// 删除指定值的节点
void deleteNode(LinkList &L, int data) 
{// 创建两个指针 p 和 q,用于遍历链表Node *p = L;Node *q = L->next;// 遍历链表,直到找到要删除的节点或遍历到链表尾部(q == L)while (q!= L && q->data!= data) {p = q;q = q->next;}// 如果遍历到链表尾部仍未找到要删除的节点if (q == L) {printf("节点不存在!\n");} else {// 调整指针,将待删除节点从链表中移除p->next = q->next;// 释放待删除节点的内存空间free(q);}
}

(三)总结与应用

单循环链表的优势在于可以方便地进行循环遍历,无需担心链表的末尾。在一些需要循环处理数据的场景中,如约瑟夫问题、魔术师发牌问题等,单循环链表表现出了强大的应用价值。然而,单循环链表也存在一些问题,比如在插入和删除操作时,需要特别注意链表的循环特性,否则容易出现错误。解决这些问题的方法是在编写代码时,仔细考虑各种情况,确保代码的正确性。总之,单循环链表是一种非常有用的数据结构,掌握它的特点和操作方法,对于提高编程能力和解决实际问题具有重要意义。

二、双向循环链表的魅力

        双向循环链表作为一种复杂而强大的数据结构,具有独特的魅力和价值。

(一)结构与初始化

双向循环链表的节点结构包含数据域、指向前驱节点的指针域和指向后继节点的指针域。这使得在链表中可以方便地双向遍历,提高了操作的灵活性。在 C 语言中,初始化双向循环链表通常先创建一个头节点,头节点的数据域一般不存储实际数据,其前驱和后继指针都指向自身,形成一个循环。例如:

#include <stdio.h>
#include <stdlib.h>typedef int ElemType;// 定义双向链表节点结构体
typedef struct DNode 
{ElemType data;struct DNode *prev; // 指向前驱节点的指针struct DNode *next; // 指向后继节点的指针
} DNode;// 定义指向双向链表节点的指针类型别名
typedef struct DNode *DLinkList;// 初始化双向循环链表
void initDList(DLinkList &DL) 
{// 分配内存空间用于创建头节点DL = (DLinkList)malloc(sizeof(DNode));if (!DL) {// 如果内存分配失败,退出程序并返回错误码 OVERFLOWexit(OVERFLOW);}// 将头节点的 prev 和 next 指针都指向自身,形成双向循环链表DL->prev = DL;DL->next = DL;// 头节点的数据域可以用于存储链表的长度等信息,这里初始化为 0DL->data = 0;
}

(二)插入操作

1.头部插入:头部插入操作先创建新节点,然后调整新节点的前驱和后继指针,使其指向头节点和原来的头节点的下一个节点,最后调整头节点和原来头节点的下一个节点的指针,使其指向新节点。例如:

// 在双向循环链表头部插入节点
void headInsertDList(DLinkList &DL, int data) 
{// 分配新节点内存空间DNode *newNode = (DNode *)malloc(sizeof(DNode));newNode->data = data;// 设置新节点的前驱指针指向头节点newNode->prev = DL;// 设置新节点的后继指针指向原来头节点的下一个节点newNode->next = DL->next;// 原来头节点下一个节点的前驱指针更新为新节点DL->next->prev = newNode;// 头节点的后继指针更新为新节点DL->next = newNode;
}

2.尾部插入:尾部插入操作先找到链表的尾节点,然后创建新节点,调整新节点的前驱和后继指针,使其指向尾节点和头节点,最后调整尾节点和头节点的指针,使其指向新节点。例如:

// 在双向循环链表尾部插入节点
void tailInsertDList(DLinkList &DL, int data) 
{// 分配新节点内存空间DNode *newNode = (DNode *)malloc(sizeof(DNode));newNode->data = data;// 设置新节点的前驱指针指向原尾节点(即头节点的前驱)newNode->prev = DL->prev;// 设置新节点的后继指针指向头节点newNode->next = DL;// 更新原尾节点的后继指针为新节点DL->prev->next = newNode;// 更新头节点的前驱指针为新节点DL->prev = newNode;
}

3.指定位置插入:指定位置插入操作先找到要插入位置的前一个节点,然后创建新节点,调整新节点的前驱和后继指针,使其指向该节点和该节点的下一个节点,最后调整该节点和该节点的下一个节点的指针,使其指向新节点。例如:

// 在双向循环链表指定位置插入节点
void insertAtPositionDList(DLinkList &DL, int pos, int data) 
{// 创建一个指针 p,初始指向头节点DNode *p = DL;// 用于计数当前位置的变量int i = 0;// 遍历链表找到要插入的位置while (p->next!= DL && i < pos - 1) {p = p->next;i++;}// 如果遍历完没有找到指定位置,输出插入位置无效的提示信息并返回if (i!= pos - 1) {printf("插入位置无效!\n");return;}// 分配新节点的内存空间DNode *newNode = (DNode *)malloc(sizeof(DNode));newNode->data = data;// 设置新节点的前驱指针指向当前位置的节点 pnewNode->prev = p;// 设置新节点的后继指针指向当前位置节点 p 的下一个节点newNode->next = p->next;// 将当前位置节点 p 的下一个节点的前驱指针更新为新节点p->next->prev = newNode;// 将当前位置节点 p 的后继指针更新为新节点p->next = newNode;
}

(三)删除操作

1.删除头部节点:删除头部节点操作先保存头节点的下一个节点,然后调整头节点和头节点的下一个节点的下一个节点的指针,使其指向对方,最后释放头节点的下一个节点。例如:

// 删除双向循环链表的头部节点
void deleteHeadDList(DLinkList &DL) 
{// 如果链表为空(头节点的下一个节点还是头节点),输出提示信息并返回if (DL->next == DL) {printf("链表为空,无法删除头部节点!\n");return;}// 保存要删除的头节点DNode *temp = DL->next;// 更新头节点的 next 指针指向原来头节点的下一个节点DL->next = temp->next;// 更新新的头节点的前驱指针为原来的头节点的前驱(现在还是尾节点)temp->next->prev = DL;// 释放被删除的头节点的内存空间free(temp);
}

2.删除尾部节点:删除尾部节点操作先找到链表的尾节点的前一个节点,然后调整该节点和头节点的指针,使其指向对方,最后释放尾节点。例如:

// 删除双向循环链表的尾部节点
void deleteTailDList(DLinkList &DL) 
{// 如果链表为空(头节点的下一个节点还是头节点),输出提示信息并返回if (DL->next == DL) {printf("链表为空,无法删除尾部节点!\n");return;}// 找到尾节点的前驱节点DNode *p = DL->prev->prev;// 保存要删除的尾节点DNode *temp = DL->prev;// 更新尾节点前驱节点的 next 指针指向头节点p->next = DL;// 更新头节点的 prev 指针指向新的尾节点(原来尾节点的前驱)DL->prev = p;// 释放被删除的尾节点的内存空间free(temp);
}

3.删除指定位置节点:删除指定位置节点操作先找到要删除位置的前一个节点,然后保存要删除的节点,调整该节点和该节点的下一个节点的指针,使其指向对方,最后释放要删除的节点。例如:

// 删除双向循环链表指定位置的节点
void deleteAtPositionDList(DLinkList &DL, int pos) 
{// 创建一个指针 p,初始指向头节点DNode *p = DL;// 用于计数当前位置的变量int i = 0;// 遍历链表找到要删除的位置的前一个节点while (p->next!= DL && i < pos - 1) {p = p->next;i++;}// 如果遍历完没有找到指定位置或者链表为空,输出删除位置无效的提示信息并返回if (i!= pos - 1 || p->next == DL) {printf("删除位置无效!\n");return;}// 保存要删除的节点DNode *temp = p->next;// 更新当前节点的 next 指针指向要删除节点的下一个节点p->next = temp->next;// 更新要删除节点的下一个节点的 prev 指针指向当前节点temp->next->prev = p;// 释放被删除的节点的内存空间free(temp);
}

(四)遍历与查找

1.遍历:遍历双向循环链表可以从任意一个节点开始,向前或向后遍历。例如从头节点开始向后遍历:

// 遍历双向循环链表
void traverseDList(DLinkList DL) 
{// 如果链表为空(头节点的下一个节点还是头节点),输出提示信息并返回if (DL->next == DL) {printf("链表为空!\n");return;}// 创建一个指针 p,初始指向头节点的下一个节点DNode *p = DL->next;// 遍历链表并输出每个节点的数据while (p!= DL) {printf("%d ", p->data);p = p->next;}printf("\n");
}

2.查找:查找指定元素可以从任意一个节点开始,向前或向后遍历,比较节点的数据域和要查找的元素是否相等。例如从头节点开始向后查找:

// 在双向循环链表中查找指定元素
DNode *findInDList(DLinkList DL, int data) 
{// 如果链表为空(头节点的下一个节点还是头节点),输出提示信息并返回 NULLif (DL->next == DL) {printf("链表为空!\n");return NULL;}// 创建一个指针 p,初始指向头节点的下一个节点DNode *p = DL->next;// 遍历链表查找指定元素while (p!= DL && p->data!= data) {p = p->next;}// 如果遍历完没有找到指定元素,输出未找到的提示信息并返回 NULLif (p == DL) {printf("未找到指定元素!\n");return NULL;}// 返回找到的节点指针return p;
}

(五)总结与展望

双向循环链表具有双向遍历、高效插入和删除等特点,在很多应用场景中都有重要的价值。例如在操作系统的内存管理中,可以使用双向循环链表来管理空闲内存块;在数据库系统中,可以用双向循环链表来实现事务的回滚和重做。未来,随着计算机技术的不断发展,双向循环链表可能会在更多的领域得到应用,并且可能会与其他数据结构结合,产生更强大的数据管理和处理能力。同时,对于双向循环链表的优化和改进也将是一个持续的研究方向,比如提高插入和删除操作的效率、减少内存占用等。总之,双向循环链表作为一种重要的数据结构,将在计算机科学的发展中继续发挥重要作用。

相关文章:

数据结构之——单循环链表和双向循环链表

一、单循环链表的奥秘 单循环链表是一种特殊的链表结构&#xff0c;它在数据结构领域中具有重要的地位。其独特的循环特性使得它在某些特定的应用场景中表现出强大的优势。 &#xff08;一&#xff09;结构与初始化 单循环链表的结构由节点组成&#xff0c;每个节点包含数据域…...

Git Stash: 管理临时更改的利器

Git 是一个非常强大的版本控制系统&#xff0c;它不仅帮助我们管理代码的版本&#xff0c;还提供了许多实用的功能来优化我们的工作流程。今天&#xff0c;我们要介绍的是 Git 中的一个非常实用的功能——git stash。 什么是 Git Stash&#xff1f; 在开发过程中&#xff0c;…...

ELK--收集日志demo

ELK--收集日志demo 安装ELK日志收集配置启动容器springboot配置测试 之前项目多实例部署的时候&#xff0c;由于请求被负载到任意节点&#xff0c;所以查看日志是开多个终端窗口。后来做了简单处理&#xff0c;将同一项目的多实例日志存入同一个文件&#xff0c;由于存在文件锁…...

Redis的主要特点及运用场景

Redis的主要特点及运用场景 Redis&#xff08;Remote Dictionary Server&#xff09;是一个开源的高性能键值对&#xff08;key-value&#xff09;数据库。它支持多种类型的数据结构&#xff0c;如字符串&#xff08;strings&#xff09;、散列&#xff08;hashes&…...

与我免费ai书童拆解《坚持》创作历程

插科打诨的海侃胡闹&#xff0c;调侃舒展《坚持》诗创的灵魂盛宴之旅。 (笔记模板由python脚本于2024年09月30日 19:11:42创建&#xff0c;本篇笔记适合喜欢python和诗歌的coder翻阅) 【学习的细节是欢悦的历程】 Python 官网&#xff1a;https://www.python.org/ Free&#x…...

昇思MindSpore进阶教程--下沉模式

大家好&#xff0c;我是刘明&#xff0c;明志科技创始人&#xff0c;华为昇思MindSpore布道师。 技术上主攻前端开发、鸿蒙开发和AI算法研究。 努力为大家带来持续的技术分享&#xff0c;如果你也喜欢我的文章&#xff0c;就点个关注吧 正文开始 昇腾芯片集成了AICORE和AICPU等…...

Hive SQL业务场景:连续5天涨幅超过5%股票

一、需求描述 现有一张股票价格表 dwd_stock_trade_dtl 有3个字段分别是&#xff1a; 股票代码(stock_code), 日期(trade_date)&#xff0c; 收盘价格(closing_price) 。 请找出满足连续5天以上&#xff08;含&#xff09;每天上涨超过5%的股票&#xff0c;并给出连续满足…...

Java 如何从图片上提取文字

生活中我们可能会遇到想从图片上直接复制上边的文字&#xff0c;该如何获取呢&#xff0c;接下来看看如何使用Java程序实现从图片中读取文字。 实现过程 1、引入Tess4J 依赖 <!--Tess4J 依赖--> <dependency><groupId>net.sourceforge.tess4j</groupId…...

C#进阶-读写Excel常用框架及其使用方式

目录 一、MiniExcel开源框架&#xff08;推荐&#xff09; 1、写/导出 方式一 方式二 多表创建 更改配置 特性使用 CSV尾行新增行 CSV、XLSX互转 2、读/导入 简单示例 二、NPOI开源框架 一、MiniExcel开源框架&#xff08;推荐&#xff09; 添加NuGet包MiniExcel…...

Python爬虫lxml模块安装导入和xpath基本语法

lxml模块是Python的一个解析库&#xff0c;主要用于解析HTML和XML文件。 一、安装导入 使用包管理器安装&#xff0c;在cmd下或编辑器下的控制台&#xff0c;运行&#xff1a; pip install lxml 导入&#xff1a; from lxml import etree 二、xpath基础知识 XPath&#…...

python魔法(python高级magic方法进阶)

python特殊方法(magic方法也叫魔术方法) 魔法方法是python的内置函数&#xff0c;一般以双下划线开头和结尾&#xff0c; 构造和初始化 每个人都知道一个最基本的魔术方法&#xff0c; init 。 通过此方法我们可以定义一个对象的初始操作。 然而&#xff0c;当我调用 x S…...

【论文笔记】Flamingo: a Visual Language Model for Few-Shot Learning

&#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&#xff0c;为生民立命&#xff0c;为往圣继绝学&#xff0c;为万世开太平。 基本信息 标题: Flamingo: a Visual Langu…...

问:JAVA阻塞队列实现类及最佳实践?

在多线程编程中&#xff0c;阻塞队列作为一种关键的数据结构&#xff0c;为线程间安全、高效的数据交换提供了重要支持。Java的java.util.concurrent包中提供了多种阻塞队列的实现&#xff0c;每种实现都有其独特的特点和适用场景。 一、阻塞队列实现类 以下是Java中Blocking…...

Springboot3 + MyBatis-Plus + MySql + Vue + ProTable + TS 实现后台管理商品分类(最新教程附源码)

Springboot3 MyBatis-Plus MySql Uniapp 商品加入购物车功能实现&#xff08;针对上一篇sku&#xff09; 1、效果展示2、数据库设计3、后端源码3.1 application.yml 方便 AliOssUtil.java 读取3.2 model 层3.2.1 BaseEntity3.2.1 GoodsType3.2.3 GoodsTypeSonVo3.3 Controll…...

消费电子制造企业如何使用SAP系统提升运营效率与竞争力

在当今这个日新月异的消费电子市场中&#xff0c;企业面临着快速变化的需求、激烈的竞争以及不断攀升的成本压力。为了在这场竞赛中脱颖而出&#xff0c;消费电子制造企业纷纷寻求数字化转型的突破点&#xff0c;其中&#xff0c;SAP系统作为业界领先的企业资源规划(ERP)解决方…...

算法记录——树

二叉树 3.1二叉树的最大深度 思路&#xff1a;二叉树的最大深度 根节点的最大高度。因此本题可以转换为求二叉树的最大高度。 而求高度的时候应该采用后序遍历。遍历顺序为&#xff1a;左右中。每次遍历的节点按后序遍历顺序&#xff0c;先收集左右孩子的最大高度&#xff0c;…...

单片机在控制和自动化任务中的应用场景广泛

单片机在控制和自动化任务中的应用场景广泛&#xff0c;以下是一些具体示例&#xff1a; 1. 家电控制 洗衣机&#xff1a;单片机用于控制洗衣周期、温度和水位。微波炉&#xff1a;控制加热时间、功率和用户界面。 2. 工业自动化 生产线监控&#xff1a;单片机用于控制传送…...

UEFI EDK2框架学习(三)——protocol

一、Protocol协议 搜索支持特定Protocol的设备&#xff0c;获取其Handle gBS->LocateHandleBuffer 将内存中的Driver绑定到给定的ControllerHandle gBS->OpenProtocol 二、代码实现 Protocol.c #include <Uefi.h> #include <Library/UefiLib.h> #includ…...

PostgreSQL的字段存储类型了解

PostgreSQL的字段存储类型了解 在 PostgreSQL 中&#xff0c;每个字段&#xff08;列&#xff09;都有其存储类型&#xff0c;这些存储类型决定了数据库如何存储和处理该字段的数据。了解和适当地利用这些存储类型&#xff0c;可以提高数据库的性能和存储效率。 主要的存储类…...

CTFshow 命令执行 web29~web36(正则匹配绕过)

目录 web29 方法一&#xff1a;include伪协议包含文件读取 方法二&#xff1a;写入文件 方法三&#xff1a;通识符 web30 方法一&#xff1a;filter伪协议文件包含读取 方法二&#xff1a;命令执行函数绕过 方法三&#xff1a;写入文件 web31 方法一&#xff1a;filter伪…...

微信小程序之bind和catch

这两个呢&#xff0c;都是绑定事件用的&#xff0c;具体使用有些小区别。 官方文档&#xff1a; 事件冒泡处理不同 bind&#xff1a;绑定的事件会向上冒泡&#xff0c;即触发当前组件的事件后&#xff0c;还会继续触发父组件的相同事件。例如&#xff0c;有一个子视图绑定了b…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

【WiFi帧结构】

文章目录 帧结构MAC头部管理帧 帧结构 Wi-Fi的帧分为三部分组成&#xff1a;MAC头部frame bodyFCS&#xff0c;其中MAC是固定格式的&#xff0c;frame body是可变长度。 MAC头部有frame control&#xff0c;duration&#xff0c;address1&#xff0c;address2&#xff0c;addre…...

从零实现富文本编辑器#5-编辑器选区模型的状态结构表达

先前我们总结了浏览器选区模型的交互策略&#xff0c;并且实现了基本的选区操作&#xff0c;还调研了自绘选区的实现。那么相对的&#xff0c;我们还需要设计编辑器的选区表达&#xff0c;也可以称为模型选区。编辑器中应用变更时的操作范围&#xff0c;就是以模型选区为基准来…...

STM32标准库-DMA直接存储器存取

文章目录 一、DMA1.1简介1.2存储器映像1.3DMA框图1.4DMA基本结构1.5DMA请求1.6数据宽度与对齐1.7数据转运DMA1.8ADC扫描模式DMA 二、数据转运DMA2.1接线图2.2代码2.3相关API 一、DMA 1.1简介 DMA&#xff08;Direct Memory Access&#xff09;直接存储器存取 DMA可以提供外设…...

Rust 异步编程

Rust 异步编程 引言 Rust 是一种系统编程语言,以其高性能、安全性以及零成本抽象而著称。在多核处理器成为主流的今天,异步编程成为了一种提高应用性能、优化资源利用的有效手段。本文将深入探讨 Rust 异步编程的核心概念、常用库以及最佳实践。 异步编程基础 什么是异步…...

深入解析C++中的extern关键字:跨文件共享变量与函数的终极指南

&#x1f680; C extern 关键字深度解析&#xff1a;跨文件编程的终极指南 &#x1f4c5; 更新时间&#xff1a;2025年6月5日 &#x1f3f7;️ 标签&#xff1a;C | extern关键字 | 多文件编程 | 链接与声明 | 现代C 文章目录 前言&#x1f525;一、extern 是什么&#xff1f;&…...

【Nginx】使用 Nginx+Lua 实现基于 IP 的访问频率限制

使用 NginxLua 实现基于 IP 的访问频率限制 在高并发场景下&#xff0c;限制某个 IP 的访问频率是非常重要的&#xff0c;可以有效防止恶意攻击或错误配置导致的服务宕机。以下是一个详细的实现方案&#xff0c;使用 Nginx 和 Lua 脚本结合 Redis 来实现基于 IP 的访问频率限制…...

STM32---外部32.768K晶振(LSE)无法起振问题

晶振是否起振主要就检查两个1、晶振与MCU是否兼容&#xff1b;2、晶振的负载电容是否匹配 目录 一、判断晶振与MCU是否兼容 二、判断负载电容是否匹配 1. 晶振负载电容&#xff08;CL&#xff09;与匹配电容&#xff08;CL1、CL2&#xff09;的关系 2. 如何选择 CL1 和 CL…...

深入浅出Diffusion模型:从原理到实践的全方位教程

I. 引言&#xff1a;生成式AI的黎明 – Diffusion模型是什么&#xff1f; 近年来&#xff0c;生成式人工智能&#xff08;Generative AI&#xff09;领域取得了爆炸性的进展&#xff0c;模型能够根据简单的文本提示创作出逼真的图像、连贯的文本&#xff0c;乃至更多令人惊叹的…...