带头循环双向链表专题

news/2024/5/18 15:57:55

1. 双向链表的结构

带头链表⾥的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这⾥“放哨 的” “哨兵位”存在的意义: 遍历循环链表避免死循环。

2. 双向链表的实现

2.1双向链表结构

typedef  int DataType;
typedef struct ListNode
{struct ListNode* perv;DataType val;struct ListNode* next;
}ListNode; 

双向链表有两个方向,所以要定义两个是指针,perv指向前一个节点,next指向后一个节点。

2.2开辟新节点

ListNode* NewNode(DataType x)
{ListNode* note = (ListNode*)malloc(sizeof(ListNode));if (note == NULL){perror("malloc");exit(0);}note->val = x;note->next = note->perv = note;return note;
}

当我们要插入新节点,或者初始化头结点时,需要开辟一个新节点。因为链表要循环,所以新节点的perv和next指针不能只想为NULL,要指向自己。

2.3初始化链表

void STInit(ListNode** pphead)
{*pphead = NewNode(-1);
}

双向带头循环链表的初始化就是建立头节点(哨兵位)。随便赋一个值就可以。

2.4双向链表头插

void HeadAdd(ListNode* phead, DataType x)
{assert(phead);ListNode* newnote = NewNode(x);newnote->next = phead->next;newnote->perv = phead;phead->next->perv = newnote;phead->next = newnote;
}

头插实际上是在头节点之后插入新节点。只需将新节点的perv指针指向phead,next指针指向phead->next节点。然后将phead->next的perv指针指向newnote。头节点的next指针指向新节点。

2..5双向链表打印

void ListPrint(ListNode* phead)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->val);pcur = pcur->next;}
}

双向链表的打印实际上是打印头节点之后的内容。先定义一个指针指向头结点的下一个节点。然后打印,最后让pcur指向下一个节点,重复这个过程,直到pcur指向phead。

2.6尾插

void TailAdd(ListNode* phead, DataType x)
{assert(phead);ListNode* newnode = NewNode(x);newnode->next = phead;newnode->perv = phead->perv;newnode->perv->next = newnode;phead->perv = newnode;
}

双向链表的尾插,首先要向内存申请一个新节点。新节点的perv指针指向phead->perv节点,next指针指向phead节点。phead->perv的next指针指向新节点。头结点的perv节点指向新节点。

2.7尾删

void TailDel(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->perv;del->perv->next = phead;phead->perv = del->perv;free(del);del = NULL;
}

先将要删除的节点的地址存起来,否则改完指针指向后就找不到了。改完指针指向后再释放del。

2.8头删

void HeadDel(ListNode* phead)
{assert(phead && phead->next != phead);ListNode* del = phead->next;del->next->perv = phead;phead->next = del->next;free(del);del = NULL;
}

头删即删除头节点之后的节点。同样要先把要删除的节点存起来。在改变指针指向之后把del释放。

2.9查找某一结点是否存在

ListNode* Find(ListNode* phead, DataType x)
{assert(phead);ListNode* pcur = phead->next;while (pcur != phead){if (pcur->val == x){return pcur;}}return -1;
}

遍历链表,查找某节点是否存在,如果存在则返回该节点的地址,若不存在返回一个小于0的值。

2.10在指定位置指点之后插入节点

void PosBAdd(ListNode* pop, DataType x)
{ListNode* newnode = NewNode(x);newnode->next = pop->next;newnode->perv = pop;pop->next->perv = newnode;pop->next = newnode;
}

同样也是简单的改变指针的指向。

2.11删除指定位置节点

void PosDel(ListNode* pop)
{pop->perv->next = pop->next;pop->next->perv = pop->perv;free(pop);pop = NULL;
}

改变指针指向后在释放掉要删除的节点。

2.12销毁链表

void ListDesTroy(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}
}

销毁链表即逐个节点释放,但是在释放结点之前要先将下一个结点的地址存起来,因为如果不存起来就无法找到下一个节点。


http://www.mrgr.cn/p/70643755

相关文章

delphi清理txt文件多余的空格

PDF文件转存为文本,多了一堆不需要的空格,写个小程序处理一下,没逻辑,直接上代码。 delphi用的是XE11.3unit UnitSmallMain;interfaceusesSystem.SysUtils, System.Types, System.UITypes, System.Classes, System.Variants,FMX.Types, FMX.Controls, FMX.Forms, FMX.Graph…

[算法学习笔记] 并查集

并查集。非基础教学。提示:本文并非并查集模板讲解,是在模板基础上的进一步理解以及拓展。 Review 并查集可以用来维护集合问题。例如,已知 \(a,b\) 同属一个集合,\(b,c\) 同属一个集合。那么 \(a,b,c\) 都属一个集合。 并查集分为 合并,查询 操作。定义 \(fa_i\) 表示点 …

sherpa + ncnn 离线语音识别

目录结构 前言音视频格式转为wavsherpa-ncnn编译LinuxWindowswindows编译中遇到的问题问题“nmake -? failed with: no such file or directory”编译失败原因 成功编译截图 可执行程序说明模型下载语言识别测试LinuxWindows 参考文献 前言 小编需要实现离线音视频语言部分识…

【问题处理】银河麒麟操作系统实例分享,服务器操作系统VNC远程问题分析

1.服务器环境以及配置 【内核版本】 4.19.90-23.8.v2101.ky10.aarch64 【OS镜像版本】 0518-server 2.问题现象描述 服务器通过vncserver:1.service服务启动的vnc服务后,普通用户用vnc连接时,锁屏后,然后输入登陆密码会报密码错误&…

写博客复制黏贴的模板

Armv8/Armv9架构从入门到精通,Armv8/Armv9架构从入门到精通(一期),Armv8/Armv9架构从入门到精通(二期) Armv8/Armv9架构从入门到精通(三期),Arm一期、Arm二期、学习资料、…

计算机网络---第十一天

生成树协议 stp作用: 作用:stp用于解决二层环路问题。 BPDU: 含义:桥协议数据单元,用于传递stp协议相关报文 分类:配置bpdu---用于传递stp的配置信息 tcn bpdu---用于通告拓扑变更信息 包含信息&…

2024.04.24 完成的任务

今天在菜鸟教程学了这些内容。。。具体内容如下: <!DOCTYPE html> <html lang="en"> <head><meta charset="UTF-8"><title>我的联通</title><head></head></head><body><h1>中国联通&…

用AI给“高品质”加速,爱奇艺长期主义的又一程

「 AI时代,爱奇艺心态稳定,路线清晰。 」2023年卷大模型,2024年卷应用。作为新质生产力,生成式AI正在千行百业落地——看上去离AI更近的影视行业,也被市场持续注视。 环境的变化催着行业跑起来,谁起跑更早,谁跑得更稳?身处变局中的人多少都闻到一些焦虑的味道。在这样的…

【Web安全之机器学习】①分析邮箱数据

Enron数据集:https://www2.aueb.gr/users/ion/data/enron-spam/ Enron(安然公司)在2001年宣告破产之前,拥有约21000名雇员,曾是世界上最大的电力、天然气以及电讯公司之一,2000年披露的营业额达1010亿美元之巨。公司连续六年被财富杂志评选为“美国最具创新精神公司”,然…

Windows编程系列:设备I/O

Windows设备 在Windows平台下,设备被定义为能够与之进行通信的任何东西。最常见的 I/O 设备包括:文件、文件流、目录、物理磁盘、卷、控制台缓冲区、磁带驱动器、通信资源、mailslot 和管道等。 平常我们使用的文件,目录都可以称之为设备。本文是介绍设备的通用操作,以文件…

【C 数据结构】二叉树

文章目录 【 1. 基本原理 】1.1 二叉树的性质1.2 满二叉树1.3 完全二叉树 【 2. 二叉树的顺序存储结构 】2.1 完全二叉树的顺序存储2.2 普通二叉树的顺序存储2.3 完全二叉树的还原 【 3. 二叉树的链式存储结构 】【 4. 二叉树的先序遍历 】4.1 递归实现4.2 非递归实现 【 5. 二…

Modbus转Profinet网关接电表与工控机通讯

Modbus转Profinet网关(XD-MDPN100/300)的主要功能是实现Modbus协议和Profinet协议之间的转换和通信。Modbus转Profinet网关集成了Modbus和Profinet两种协议,支持Modbus RTU主站/从站,并可以与RS485接口的设备,如变频器、智能高低压电器、电量测量装置等进行连接。同时,它…

安全中级-初开始

一、网络基础 重要点&#xff1a;TTL值&#xff08;防环&#xff0c;linux64.Windows128 &#xff09;&#xff0c;IP数据包包头格式字节&#xff08;20&#xff09; 标识标志偏移量起到什么作用&#xff08;数据超过1500会分片&#xff09; wireshack抓包会有一个MSS&#x…

面试被刷,原因居然是不会Git

大家好,我是知微! 假设你是一个刚入行的菜狗程序员,正在开发一个软件。现在老板需要你加一些功能,此时的你有一些担忧,如果对代码进行大刀阔斧的改动,最终却失败了。之前能正常运行的代码也被改得乱七八糟的,跑不起来了,那可咋办? 聪明的你想到了一个绝妙的主意,那就…

风格迁移adaIN 和iT的adaLN

文章目录 BN、LN、IN、GN的区别![](https://img-blog.csdnimg.cn/direct/d38c005616f145cba2aa1c4c2e046be0.png)图像风格迁移adaINDiT adaLN BN、LN、IN、GN的区别 BatchNorm&#xff1a;batch方向做归一化&#xff0c;算NxHxW的均值&#xff0c;对小batchsize效果不好&#x…

【pytorch学习】之线性神经网络-线性回归

线性神经网络 【摘要】在介绍深度神经网络之前,我们需要了解神经网络训练的基础知识。我们将介绍神经网络的整个训练过程,包括:定义简单的神经网络架构、数据处理、指定损失函数和如何训练模型。为了更容易学习,我们将从经典算法————线性神经网络开始,介绍神经网络的基…

分布式事务的实现方式

分布式事务的5种实现方式XA方案 TCc方案 本地方法表 可靠性消息最终一致性方案 最大努力通知方案1.两阶段提交/XA方案 所谓的 XA 方案,即:两阶段提交,有一个事务管理器的概念,负责协调多个数据库(资源管理器)的事务,事务管理器先问问各个数据库你准备好了吗?如果每个数…

使用shared lib将各个构建工具集成到一起

共享库代码 package devopsdef Build(buildType, buildShell){def buildTools ["mvn": "MVN", "ant": "ANT", "gradle": "GRADLE"]println("当前buildType是${buildType}")buildHome tool buildTool…

恶补《操作系统》2_1——王道学习笔记

2操作系统-进程 2.1_1 进程的定义、组成、组织方式、特征 组成&#xff1a;PCB&#xff08;进程存在唯一的标志&#xff09;&#xff0c;程序段&#xff0c;数据段 组织方式&#xff1a;链接方式&#xff0c;指针指向不同的队列&#xff1b;索引方式&#xff0c;索引表 特征…

检索增强生成(RAG)技术

随着大语言模型&#xff08;LLMs&#xff09;在自然语言处理&#xff08;NLP&#xff09;领域的显著进步&#xff0c;它们在多个评估基准测试中显示出超越人类水平的语言和知识掌握能力。然而&#xff0c;这些模型在实际应用中也面临着一系列挑战&#xff0c;如制造事实、知识更…