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

95.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数

目录

1.双向链表的头插

方法一

方法二

2.双向链表的头删

3.双向链表的销毁

4.双向链表的某个节点的数据查找

5.双向链表的中间插入

5.双向链表的中间删除

6.对比顺序表和链表


承接94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删文章

1.双向链表的头插

方法一

头插注意操作顺序:新节点与头节点的后一个节点建立联系,与头节点建立联系,反过来会丢失指针

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);newnode->next = phead->next;phead->next->prev = newnode;phead->next = newnode;newnode->prev = phead;
}

方法二

当first保存了头节点的后一个节点的地址,可以反过来,即新节点与头节点建立联系,与头节点的后一个节点建立联系

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = BuyListNode(x);LTNode* first = phead->next;phead->next = newnode;newnode->prev = phead;newnode->next = first;first->prev = newnode;
}

2.双向链表的头删

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);first = NULL;
}

main.c的部分代码改为

void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTPopFront(plist);LTPrint(plist);
}

3.双向链表的销毁

void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;//保存cur1的下一个节点的地址free(cur);cur = next;}free(phead);phead = NULL;
}

注意:从phead的下一个节点开始逐步销毁每个节点,到cur值等于phead值时,停止循环

 备注:pos不置NULL也可以,形参的改变不影响实参(没有解引用操作) ,解决方法:在main.c中手动置NULL

4.双向链表的某个节点的数据查找

分为两种情况:找到和找不到

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x){return cur;//找到返回NULL}cur = cur->next;}return NULL;//找不到返回NULL
}

5.双向链表的中间插入

LTInsertBefore(LTNode* pos)表示在pos指向的节点之前(Before)插入(Insert)新节点

void LTInsertBefore(LTNode* pos,LTDataType x)
{assert(pos);LTNode* posprev = pos->prev;LTNode* newnode = BuyListNode(x);posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;
}

有了这个函数,而且有哨兵位的头节点,因此头插函数和尾插函数可以很容易改写

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTInsertBefore(phead->next,x);
}

由于是循环链表,因此head的前一个节点为尾节点

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTInsertBefore(phead,x);
}

中间插入函数应该和数据查找函数LTFind配合使用

main.c的部分代码改为

void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* pfind = LTFind(plist, 3);LTInsertBefore(pfind, 5);LTPrint(plist);
}

5.双向链表的中间删除

void LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;posprev->next = posnext;posnext->prev = posprev;free(pos);pos = NULL;
}

 备注:pos不置NULL也可以,形参的改变不影响实参(没有解引用操作) ,解决方法:在main.c中手动置NULL

中间删除函数应该和数据查找函数LTFind配合使用

main.c中部分代码改为

void TestList()
{LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);LTNode* pfind=LTFind(plist, 3);if (pfind){LTErase(pfind);pfind==NULL;}LTPrint(plist);
}

注意要判断pfind是否为NULL!!

有了中间删除函数,头删和尾删函数可以变简洁

void LTPopFront(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->next);
}
void LTPopBack(LTNode* phead)
{assert(phead);assert(!LTEmpty(phead));LTErase(phead->prev);
}

6.对比顺序表和链表

不同点顺序表链表
存储空间上物理上一定连续逻辑上连续,但物理上不一定连续
随机访问支持O(1)不支持:O(N)
任意位置插入或者删除元素可能需要搬移元素,效率低O(N)只需修改指针指向
插入动态顺序表,空间不够时需要扩容没有容量的概念
应用场景元素高效存储+频繁访问任意位置插入和删除频繁
缓存命中率

缓存命中率是什么参见第96篇

相关文章:

95.【C语言】数据结构之双向链表的头插,头删,查找,中间插入,中间删除和销毁函数

目录 1.双向链表的头插 方法一 方法二 2.双向链表的头删 3.双向链表的销毁 4.双向链表的某个节点的数据查找 5.双向链表的中间插入 5.双向链表的中间删除 6.对比顺序表和链表 承接94.【C语言】数据结构之双向链表的初始化,尾插,打印和尾删文章 1.双向链表的头插 方法…...

leetcode82:删除排序链表中的重复节点||

给定一个已排序的链表的头 head , 删除原始链表中所有重复数字的节点,只留下不同的数字 。返回 已排序的链表 。 示例 1: 输入:head [1,2,3,3,4,4,5] 输出:[1,2,5]示例 2: 输入:head [1,1,1,2…...

【C#】使用.net9在C#中向现有对象动态添加属性

在 C# 中向现有对象动态添加属性并不像在 Python 或 JavaScript 中那样容易,因为 C# 是一种强类型语言。 但是,我们可以通过使用一些技术和库来实现这一点,例如扩展方法、字典等。本文将详细介绍如何在 C# 中实现这一点。ExpandoObject 方法 …...

Linux进程信号(信号的产生)

目录 什么是信号? 信号的产生 信号产生方式1:键盘 前台进程 后台进程 查看信号 signal系统调用 案例 理解进程记录信号 软件层面 硬件层面 信号产生方式2:指令 信号产生方式3:系统调用 kill系统调用 案例 其他产生信号的函数调用 1.rais…...

97_api_intro_imagerecognition_pdf2word

通用 PDF OCR 到 Word API 数据接口 文件处理,OCR,PDF 高可用图像识别引擎,基于机器学习,超精准识别率。 1. 产品功能 通用识别接口;支持中英文等多语言字符混合识别;formdata 格式 PDF 文件流传参&#xf…...

【算法】【优选算法】二分查找算法(上)

目录 一、二分查找简介1.1 朴素二分模板1.2 查找区间左端点模版1.3 查找区间右端点模版 二、leetcode 704.⼆分查找2.1 二分查找2.2 暴力枚举 三、Leetcode 34.在排序数组中查找元素的第⼀个和最后⼀个位置3.1 二分查找3.2 暴力枚举 四、35.搜索插⼊位置4.1 二分查找4.2 暴力枚…...

springboot初体验

目录 环境 controller 修改端口号 更改banner图标 运行结果 最核心的:自动装配 环境 jdk17springboot3.3.5maven3.8.2 controller controller层和启动类同级 package com.example.demo.controller; ​ import org.springframework.web.bind.annotation.RequestMapping;…...

使用kalibr_calibration标定相机(realsense)和imu(h7min)

vslam-evaluation/VINS/Installation documentation/4.IMU和相机联合标定kalibr_calibration.md at master DroidAITech/vslam-evaluation GitHub 目录 1.kalibr安装 1.1安装依赖项 1.2创建工作空间 1.3下载kalibr并编译 1.4设置环境变量 2.准备标定板 3.配置驱动和打…...

绿色工厂认定流程

以下是认定绿色工厂的一般流程: 编制年度创建计划 各省辖市、省直管县(市)会结合本地区重点产业发展现状,挑选一批基础条件良好、有创建意愿和条件的企业进行储备培育,并依据当地工业企业发展实际情况按年度制定绿色工…...

《Python游戏编程入门》注-第5章5

《Python游戏编程入门》的“Analog Clock示例程序”部分讲解了模拟时钟的实现方法。该模拟时钟可以通过时针、分针和秒针的旋转,显示当前时间,如图1所示。 图1 模拟时钟 1 绘制圆 从图1中可以看出,时钟的边缘是一个白色的圆,可以通过如图2所示的代码进行绘制。 图2 绘制圆…...

LangChain Ollama实战文献检索助手(二)少样本提示FewShotPromptTemplate示例选择器

本期是用样例来提示大模型生成我们想要的答案。即在输入中给定提示的样例,以及提示模板,然后匹配较相关的样例进行文献综述。 创建示例样本FewShotPromptTemplate 这里我用GTP-o1生成了几个回答,作为样本 samples [{"theme": &…...

K倍区间 C++

1230. K倍区间 - AcWing题库 一开始想到的用前缀和来做&#xff0c;时间复杂度为O(n^2),Time Limit Exceeded #include <iostream> #include <cstring> #include <algorithm> #include <cstdio>using namespace std;const int N 100010;int n,k; in…...

Linux - 弯路系列3:安装和编译libvirt-4.5.0

系统&#xff1a;Anolis8&#xff08;离线&#xff09; 目录 1、步骤2、make过程中的错误错误1&#xff1a;error: xdr_u_int64_t undeclared (first use in this function) 3、make install的错误错误1&#xff1a;/usr/bin/mkdir -p ""/usr/local/etc/libvirt/nwf…...

Jenkins插件使用问题总结

Git Push插件 插件介绍 主要是用于git推送代码到远程仓库中使用&#xff0c;插件地址 pipeline中使用 官方说明中只有一句代码gitPush(gitScm: scm, targetBranch: env.BRANCH_NAME, targetRepo: origin) 流水线语法中也做的不齐全所以一开始我老是设置错&#xff0c;导致代…...

u盘怎么重装电脑系统_u盘重装电脑系统步骤和详细教程【新手宝典】

u盘怎么重装电脑系统&#xff1f;一个u盘怎么重装电脑系统呢&#xff0c;需要将u盘制作成u盘启动盘pe&#xff0c;然后通过U盘启动盘进入pe进行安装系统&#xff0c;下面小编就教大家u盘重装电脑系统步骤和详细教程。 u盘启动是什么意思&#xff1f; U盘启动盘是一种具有特殊功…...

Sql server查询数据库表的数量

SELECT count(*) FROM sys.objects WHERE typeU --统计表数量 SELECT NAME FROM sys.objects WHERE typeU --列出表名称 或者 SELECT COUNT(*) FROM SysObjects Where XTypeU --统计表数量 SELECT Name FROM SysObjects Where XTypeU --列出表名称 --判断字…...

Linux学习笔记之软件包管理RPM与YUM

RPM包的管理 介绍 RPM&#xff08;RedHat Package Manager&#xff09;用于互联网下载包的打包及安装工具&#xff0c;它包含在某些Linux分发版中。他生成具有.RPM扩展名的文件。RPM类似Windows的setup.exe&#xff0c;这一文件格式虽然打上了RedHat的标志&#xff0c;但理念…...

15分钟学 Go 第 41 天:中间件的使用

第41天&#xff1a;中间件的使用 目标&#xff1a;学习如何在Go语言的Web服务中使用中间件 中间件&#xff08;Middleware&#xff09;是Web开发中的一种常见设计模式&#xff0c;通常用于处理请求和响应过程中的一些共通功能。比如&#xff1a;日志记录、认证授权、请求处理…...

《Python 与 SQLite:强大的数据库组合》

《Python 与 SQLite&#xff1a;强大的数据库组合》 一、Python 与 SQLite 的结合二、安装与连接&#xff08;一&#xff09;安装 SQLite 模块&#xff08;二&#xff09;连接到数据库 三、数据库操作&#xff08;一&#xff09;创建表格&#xff08;二&#xff09;插入数据&am…...

Golang | Leetcode Golang题解之第552题学生出勤记录II

题目&#xff1a; 题解&#xff1a; const mod int 1e9 7type matrix [6][6]intfunc (a matrix) mul(b matrix) matrix {c : matrix{}for i, row : range a {for j : range b[0] {for k, v : range row {c[i][j] (c[i][j] v*b[k][j]) % mod}}}return c }func (a matrix) p…...

设计模式和设计原则回顾

设计模式和设计原则回顾 23种设计模式是设计原则的完美体现,设计原则设计原则是设计模式的理论基石, 设计模式 在经典的设计模式分类中(如《设计模式:可复用面向对象软件的基础》一书中),总共有23种设计模式,分为三大类: 一、创建型模式(5种) 1. 单例模式(Sing…...

Debian系统简介

目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版&#xff…...

屋顶变身“发电站” ,中天合创屋面分布式光伏发电项目顺利并网!

5月28日&#xff0c;中天合创屋面分布式光伏发电项目顺利并网发电&#xff0c;该项目位于内蒙古自治区鄂尔多斯市乌审旗&#xff0c;项目利用中天合创聚乙烯、聚丙烯仓库屋面作为场地建设光伏电站&#xff0c;总装机容量为9.96MWp。 项目投运后&#xff0c;每年可节约标煤3670…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...

MeshGPT 笔记

[2311.15475] MeshGPT: Generating Triangle Meshes with Decoder-Only Transformers https://library.scholarcy.com/try 真正意义上的AI生成三维模型MESHGPT来袭&#xff01;_哔哩哔哩_bilibili GitHub - lucidrains/meshgpt-pytorch: Implementation of MeshGPT, SOTA Me…...

LUA+Reids实现库存秒杀预扣减 记录流水 以及自己的思考

目录 lua脚本 记录流水 记录流水的作用 流水什么时候删除 我们在做库存扣减的时候&#xff0c;显示基于Lua脚本和Redis实现的预扣减 这样可以在秒杀扣减的时候保证操作的原子性和高效性 lua脚本 // ... 已有代码 ...Overridepublic InventoryResponse decrease(Inventor…...

后端下载限速(redis记录实时并发,bucket4j动态限速)

✅ 使用 Redis 记录 所有用户的实时并发下载数✅ 使用 Bucket4j 实现 全局下载速率限制&#xff08;动态&#xff09;✅ 支持 动态调整限速策略✅ 下载接口安全、稳定、可监控 &#x1f9e9; 整体架构概览 模块功能Redis存储全局并发数和带宽令牌桶状态Bucket4j Redis分布式限…...

Unity VR/MR开发-开发环境准备

视频讲解链接&#xff1a; 【XR马斯维】UnityVR/MR开发环境准备【UnityVR/MR开发教程--入门】_哔哩哔哩_bilibili...