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

一些关于单链表的操作

思维导图:

一, 链表

1.1节点的结构

链表是啥样的啊?顾名思义链表就是一种用链子链接起来的表。那这种表是怎么样的啊?

这样的呗:

现在,我们知道了链表的形状了。那我们该如何用编程语言来形成这一种形状呢?

首先,一个链表节点是这样的:

毫无疑问,链表也需要存储一些数据(不然要链表来干嘛?)。而且链表还有一条尾巴(当然这是为了形象而画出来的)这条尾巴又要如何形成呢?现在让我们来想一想尾巴的作用是什么啊?当然是为了找到下一个节点啊,那我们要找到下一个节点的话我们应该用什么去找呢?当然是下一个节点的地址啊!那放地址我们是不是应该要用指针啊?那好,现在我们已经清楚的知道了这一个节点的结构组成了。画图如下:

现在,我们再往下推。首先,我们这一个结构里面含有两种不同类型的数据。不同类型的数据应该用什么数据结构来存储呢?明显是结构体。那我的指针指向的下一个节点是不是又是一个结构体或者空指针呢?那这个指针是不是又可以定义为结构体指针呢?答案是肯定的!

经过以上分析,现在我们就可以把代码写出来了:

代码:

typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;//这里的typedef是为了在后面对这个结构体更好的使用

 1.2节点的生成

现在我们已经把节点的结构搞明白了,我们就要进入第二阶段了。我们要把上面的结构的节点生成一下。生成节点用什么啊?malloc啊!

生成节点代码:

SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));//动态开辟空间if (newnode == NULL) {printf("malloc fail\n");return NULL;}newnode->data = x;//在数据区内放入数据newnode->next = NULL;//先置空指针区return newnode;//将新节点返回
}

1.3打印链表

打印链表该怎么做呢?

其实很简单,这样做就行了!

代码:

void SListPrint(SListNode* plist) {SListNode* cur = plist;while (cur) {printf("%d->", cur->data);cur = cur->next;}printf("->NULL\n");//当链表为空的时候就打印一个NULL来提示一下
}

1.4在链表中插入数据

         现在我们的链表的设计已经写好了,但是这个链表是一个空链表。现在我们就要来给这个链表插入数据。当然,插入数据的方法有很多种。像头插,尾插,中间插入等等……。现在我们就来一 一实现一下。

1.4.1:头插

头插的方法就是生成一个新的节点,然后让新的节点成为新的头节点连接*pplist。然后再移动*pplist的位置让它指向新的节点。

void SListPushFront(SListNode** pplist, SLTDateType x) {SListNode* newhead = BuySListNode(x);newhead->next = *pplist;*pplist = newhead;	
}

其实,这里的头插逻辑基本上没有什么难度。但是这里使用一级指针还是二级指针才是需要花时间去理解的!可以看到我们这里使用的是二级指针,为什么呢?一句话——“你要改变谁就要用谁的指针”。因为在test文件里面我用的是结构体的指针:

SListNode* plist = NULL;

所以我要改变外面的plist的话就要用plist的指针了,因为指针的指针就是二级指针!所以我这里就用了二级指针!!!(解答完毕)

1.4.2:中间插入

先来讲一下我的中间插入的逻辑:我的插入是在我要找到的数据的后一个位置插入,所以找到位置很重要所以我会写一个查找数据位置的函数

代码;

SListNode* SListFind(SListNode* plist, SLTDateType x) {assert(plist);SListNode* pos = plist;while (pos) {if (pos->data == x) {return pos;//找到了就返回,结束循环}pos = pos->next;}printf("你要找的值不存在\n");return NULL;//找不到就返回空
}

写完了寻找节点的函数以后,我们就可以来写一个中间插入的函数来。代码如下:

void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);//要对pos断言一下,因为这是中间插入,链表中有节点才能中间插入!SListNode* newnode = BuySListNode(x);SListNode* next = pos->next;//记录一下pos指向的下一个节点,因为pos->next要被改变!pos->next = newnode;newnode->next = next;}

1.4.3尾插

尾插?啥是尾插啊?顾名思义,尾插便是找到链表的尾巴然后再来插入,具体的逻辑可以参见代码。

void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newtail = BuySListNode(x);SListNode* tail = *pplist;if (tail == NULL) {//如果链表为空那就直接让*pplist指向newtail*pplist = newtail;}else {while (tail->next) {//这里找的是尾节点,所以当tail->next为空时就找到了尾节点了tail = tail->next;}tail->next = newtail;}
}

 1.5在链表中删除节点

和链表的插入一样,链表节点的删除也有三种。分别是头删,尾删,中间删除!

1.5.1:头删

头删,顾名思义便是删除头节点。思路很简单,就是调整一下plist的指向让plist指向下一个节点然后释放上一个节点就可以了。

代码:

void SListPopFront(SListNode** pplist) {assert(pplist);//pplist不可能为空,所以这里要预防一下assert(*pplist);//空链表不能删SListNode* del = *pplist;*pplist = (*pplist) ->next;free(del);del = NULL;
}

1.5.2:中间删除

这个操作的实现也是需要和 SListFind搭配使用的,前面我已经将 SListFind写好了。这里我就不再写了,我在这里直接写中间删除的函数就好了。当然这个中间删除函数与前面的中间插入一样,都只是删除中间的节点而不会删除头节点与尾节点。所以依照这个思路,我们便可以将代码写出来:

 代码:

void SListEraseAfter(SListNode* pos) {assert(pos);//中间删除不会删除头节点,更不会删除不存在的值。assert(pos->next);//也不能删除空指针SListNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}

1.5.3尾删

顾名思义,尾删就是把链表的尾节点删除掉。删除的逻辑就是找到链表的尾节点的前面一个节点然后将这一个节点中的指向改为空。并把尾节点给释放掉。

代码:

void SListPopBack(SListNode** pplist) {assert(pplist);//指针的地址不可能为NULLassert(*pplist);//空链表不能尾删if ((*pplist)->next == NULL) {free(*pplist);*pplist = NULL;}else {SListNode* tail = *pplist;while (tail->next->next) {tail = tail->next;}SListNode* del = tail->next;tail->next = NULL;free(del);del = NULL;}
}

1.6销毁链表

因为我们的链表是malloc出来的一块一块的空间,所以当我们的链表用完以后就要对这些一块一块的空间进行释放。说所以我们又要写一个函数来销毁链表。

代码:

void SListDestroy(SListNode** pplist) {assert(pplist);assert(*pplist);//链表未创建不能销毁SListNode* cur = NULL;while (*pplist) {cur = (*pplist)->next;free(*pplist);*pplist = cur;}*pplist = NULL;printf("链表销毁成功!\n");
}

总结:

到这里我们就已经把我能讲的一些关于链表的知识,我所知道的关于链表的知识给讲完了。但是我还是想要总结一下:

1.在我们要操作链表时,比如想要增删时就要用二级指针。

2.当一个变量不可能为空指针时要对它进行assert断言。

3.当一个变量为空时会导致错误时也要对这个变量进行assert断言。

好了,总结完毕!

相关文章:

一些关于单链表的操作

思维导图: 一, 链表 1.1节点的结构 链表是啥样的啊?顾名思义链表就是一种用链子链接起来的表。那这种表是怎么样的啊? 这样的呗: 现在,我们知道了链表的形状了。那我们该如何用编程语言来形成这一种形状…...

CTF-PHP反序列化漏洞2-利用魔法函数

作者:Eason_LYC 悲观者预言失败,十言九中。 乐观者创造奇迹,一次即可。 一个人的价值,在于他所拥有的。可以不学无术,但不能一无所有! 技术领域:WEB安全、网络攻防 关注WEB安全、网络攻防。我的…...

Doris(23):Doris的函数—字符串函数

1 append_trailing_char_if_absent(VARCHAR str, VARCHAR trailing_char) 如果s字符串非空并且末尾不包含c字符,则将c字符附加到末尾。 trailing_char只包含一个字符,如果包含多个字符,将返回NULL select append_trailing_char_if_absent(a,c);select append_trailing_cha…...

01-Shiro550漏洞流程

1. 漏洞原理 Apache Shiro框架提供了记住密码的功能(RememberMe),用户登录成功后会生成经过加密并编码的cookie。在服务端对rememberMe的cookie值,先base64解码然后AES解密再反序列化,就导致了反序列化RCE漏洞。 那么…...

《程序员面试金典(第6版)》面试题 16.08. 整数的英语表示

题目描述 给定一个整数,打印该整数的英文描述。 示例 1: 输入: 123输出: “One Hundred Twenty Three” 示例 2: 输入: 12345输出: “Twelve Thousand Three Hundred Forty Five” 示例 3: 输入: 1234567输出: “One Million Two Hundred Thirty Four Thousand…...

ChatGPT技术原理 第四章:Transformer模型

目录 4.1 什么是Transformer 4.2 Transformer结构详解 4.3 Self-Attention机制 4.4 Multi-Head Attention机制 4.1 什么是Transformer...

基于redis和threadlocal实现登录状态校验和拦截

1.流程图 单机节点下的登录状态校验 分布式节点下的登录状态校验 2.代码实现 实现步骤分为如下几步 实现WebMvcConfigurer接口,添加拦截器定义拦截器,需要配置两个interceptor,第一个用于刷新token,写threadlocal&#xff…...

14-6-进程间通信-信号量

前面学习了pipe,fifo,共享内存,信号。 本章将讲述信号量。 一、什么是信号量/信号量集? 1.什么是信号量 信号量是一个计数器。信号量用于实现进程间的同步和互斥。而可以取多个正整数的信号量被称为通用信号量。 对信号量的使用场景的解读 房间&#…...

《中国教育报》投稿邮箱编辑部征稿

《中国教育报》国家教育部主管,中国教育报刊社主办的以教育新闻为主的全国性日报。是迄今为止中国最具权威和最有影响力的教育新闻媒体。中国教育报刊社是中华人民共和国教育部直属的新闻出版机构。2018年获得第三届全国“百强报纸”。2019年入选“新媒体影响力指数…...

Photoshop如何使用绘画和图像修饰之实例演示?

文章目录 0.引言1.给图像添加渐变色效果2.快速创建一副素描画3.清除图像中多余的景物4.快速融合两张图像5.调整图像光影6.人像面部瑕疵修除7.美化眼睛 0.引言 因科研等多场景需要进行绘图处理,笔者对PS进行了学习,本文通过《Photoshop2021入门教程》及其…...

【C++】布隆过滤器

文章目录 布隆过滤器提出布隆过滤器概念布隆过滤器应用场景设计思路:布隆过滤器的插入布隆过滤器的查找布隆过滤器删除BloomFilter.h布隆过滤器优点布隆过滤器缺陷 布隆过滤器提出 我们在使用新闻客户端看新闻时,它会给我们不停地推荐新的内容,它每次推荐时要去重,去掉那些已经…...

功能齐全的 ESP32 智能手表,具有多个表盘、心率传感器硬件设计

相关设计资料下载ESP32 智能手表带心率、指南针设计资料(包含Arduino源码+原理图+Gerber+3D文件).zip 介绍 我们调查了智能手表项目的不同方面,并学会了集成和测试每个单独的部分。在本文中,我们将使用所学知识,结合使用硬件和软件组件,从头开始创建我们自己的智能手表。在…...

微服务不是本地部署的最佳选择,不妨试试模块化单体

微服务仅适用于成熟产品 关于从头开始使用微服务,马丁・福勒(Martin Fowler)总结道: 1. 几乎所有成功的微服务都是从一个过于庞大而不得不拆分的单体应用开始的。 2. 几乎所有从头开始以微服务构建的系统,最后都会因…...

解读Toolformer

【引子】读论文Toolformer: Language Models Can Teach Themselves to Use Tools,https://arxiv.org/pdf/2302.04761.pdf,再阅读了几篇关于Toolformer的网络热文,于是“无知者无畏”,开始自不量力地试图解读Toolformer。 大语言模…...

FCOS3D Fully Convolutional One-Stage Monocular 3D Object Detection 论文学习

论文地址:Fully Convolutional One-Stage Monocular 3D Object Detection Github地址:Fully Convolutional One-Stage Monocular 3D Object Detection 1. 解决了什么问题? 单目 3D 目标检测由于成本很低,对于自动驾驶任务非常重…...

Xpath学习笔记

Xpath原理:先将HTML文档转为XML文档,再用xpath查找HTML节点或元素 什么是xml? 1、xml指可扩展标记语言 2、xml是一种标记原因,类似于html 3、xml的设计宗旨是传输数据,而非显示数据 4、xml标签需要我们自己自定义 5、x…...

网络编程之 Socket 套接字(使用数据报套接字和流套接字分别实现一个小程序(附源码))

文章目录 1. 什么是网络编程2. 网络编程中的基本概念1)发送端和接收端2)请求和响应3)客户端和服务端4)常见的客户端服务端模型 3. Socket 套接字1)Socket 的分类2)Java 数据报套接字通信模型3)J…...

What Are Docker Image Layers?

Docker images consist of multiple layers that collectively provide the content you see in your containers. But what actually is a layer, and how does it differ from a complete image? In this article you’ll learn how to distinguish these two concepts and…...

范数详解-torch.linalg.norm计算实例

文章目录 二范数F范数核范数无穷范数L1范数L2范数 前些天发现了一个巨牛的人工智能学习网站,通俗易懂,风趣幽默,忍不住分享一下给大家。点击跳转到网站。 范数是一种数学概念,可以将向量或矩阵映射到非负实数上,通常被…...

postgresdb备份脚本

以下是一个简单的postgresdb备份脚本示例: 复制 #!/bin/bash # 设置备份目录和文件名 BACKUP_DIR/path/to/backup BACKUP_FILEdb_backup_$(date %F_%H-%M-%S).sql # 设置数据库连接参数 DB_HOSTlocalhost DB_PORT5432 DB_NAMEmydatabase DB_USERmyusername DB_PA…...

(二)原型模式

原型的功能是将一个已经存在的对象作为源目标,其余对象都是通过这个源目标创建。发挥复制的作用就是原型模式的核心思想。 一、源型模式的定义 原型模式是指第二次创建对象可以通过复制已经存在的原型对象来实现,忽略对象创建过程中的其它细节。 📌 核心特点: 避免重复初…...

Python爬虫(一):爬虫伪装

一、网站防爬机制概述 在当今互联网环境中,具有一定规模或盈利性质的网站几乎都实施了各种防爬措施。这些措施主要分为两大类: 身份验证机制:直接将未经授权的爬虫阻挡在外反爬技术体系:通过各种技术手段增加爬虫获取数据的难度…...

CRMEB 框架中 PHP 上传扩展开发:涵盖本地上传及阿里云 OSS、腾讯云 COS、七牛云

目前已有本地上传、阿里云OSS上传、腾讯云COS上传、七牛云上传扩展 扩展入口文件 文件目录 crmeb\services\upload\Upload.php namespace crmeb\services\upload;use crmeb\basic\BaseManager; use think\facade\Config;/*** Class Upload* package crmeb\services\upload* …...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

Linux系统部署KES

1、安装准备 1.版本说明V008R006C009B0014 V008:是version产品的大版本。 R006:是release产品特性版本。 C009:是通用版 B0014:是build开发过程中的构建版本2.硬件要求 #安全版和企业版 内存:1GB 以上 硬盘&#xf…...

Elastic 获得 AWS 教育 ISV 合作伙伴资质,进一步增强教育解决方案产品组合

作者:来自 Elastic Udayasimha Theepireddy (Uday), Brian Bergholm, Marianna Jonsdottir 通过搜索 AI 和云创新推动教育领域的数字化转型。 我们非常高兴地宣布,Elastic 已获得 AWS 教育 ISV 合作伙伴资质。这一重要认证表明,Elastic 作为 …...

API网关Kong的鉴权与限流:高并发场景下的核心实践

🔥「炎码工坊」技术弹药已装填! 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中,API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关,Kong凭借其插件化架构…...

Java详解LeetCode 热题 100(26):LeetCode 142. 环形链表 II(Linked List Cycle II)详解

文章目录 1. 题目描述1.1 链表节点定义 2. 理解题目2.1 问题可视化2.2 核心挑战 3. 解法一:HashSet 标记访问法3.1 算法思路3.2 Java代码实现3.3 详细执行过程演示3.4 执行结果示例3.5 复杂度分析3.6 优缺点分析 4. 解法二:Floyd 快慢指针法(…...

OCR MLLM Evaluation

为什么需要评测体系?——背景与矛盾 ​​ 能干的事:​​ 看清楚发票、身份证上的字(准确率>90%),速度飞快(眨眼间完成)。​​干不了的事:​​ 碰到复杂表格(合并单元…...

JDK 17 序列化是怎么回事

如何序列化?其实很简单,就是根据每个类型,用工厂类调用。逐个完成。 没什么漂亮的代码,只有有效、稳定的代码。 代码中调用toJson toJson 代码 mapper.writeValueAsString ObjectMapper DefaultSerializerProvider 一堆实…...