链表详解(三)

目录

    • 链表功能实现
      • 链表的查找SLNode* SLFind(SLNode* phead, SLNDataType x)
        • 代码
      • 链表任意位置前插入void SLInsert(SLNode**pphead,SLNode* pos, SLNDataType x)
        • 代码
      • 链表任意位置前删除void SLErase(SLNode**pphead,SLNode* pos)
        • 代码
      • 链表任意位置后插入void SLInsertAfter( SLNode* pos,SLNDataType x)
        • 代码
        • 例题
      • 链表任意位置后删除void SLEraseAfter(SLNode* pos, SLNDataType x)
        • 代码
      • 销毁链表void SLDestroy(SLNode** pphead)
        • 代码

链表功能实现

链表的查找SLNode* SLFind(SLNode* phead, SLNDataType x)

我们用指针cur去遍历这个链表,如果cur的数据val值是和x想等的,那么就直接返回cur这个位置的节点,如果cur->val!=x,那么我们就让cur走到下一个节点cur=cur->next,当遍历完整个链表后我们还是没有找到和x相等的val,那么我们就直接返回一个NULL就行了

代码
SLNode* SLFind(SLNode* phead, SLNDataType x)
{assert(pphead);SLNode* cur = phead;while (cur){if (cur->val == x){return cur;}else{cur = cur->next;}}return NULL;
}

链表任意位置前插入void SLInsert(SLNode**pphead,SLNode* pos, SLNDataType x)

函数功能为在pos位置前插入链表数据x

在实现这个函数之前,有一个问题,就是pphead和*pphead的区别

pphead是一个二级指针,所有pphead表示对所一级指针的地址,也就是指向链表头节点指针的地址
*pphead是对pphead解引用,表示指向链表头节点的指针,注意不是指向链表头节点指针的地址

那么我们知道了这两个都区别,我们再来看看下面这个问题

pphead *pphead pos这三个是否需要断言

首先pphead断言 assert(pphead)表示我们要检查指向链表头节点指针的地址是否为空,换句话说就是如果传入为空,这个函数是否会出现问题,显然,如果我们传入为空,那么我们就无法找到指向链表头节点指针,

那*pphead断言assert(*pphead)就表示我们要检查链表头节点指针是否指向的空,如果指向空,就代表这个链表为空链表,我们就可以当这个函数为头插,或者尾插,所有这并不会对这个函数造成影响

pos断言assert(pos)表示传入参数插入位置指针的地址是否为空,如果为空,那么我们也就找不到插入的位置,所以pos是需要断言的
但是有一种情况pos只能为空,就是*pphead为空,空链表我们要插入的地址当然只能传空,为了防止这种情况我们就需要像这样断言 assert((!(*pphead) == !pos) || pos && *pphead)

!(*pphead) == !pos)表示pos为空时为假,pphead为空时也为假,通过!对两个取反,使假变成真
pos && pphead表示pos和pphead都不为空
这两个只需要满足其中的一个就可以继续用插入函数
当pos和
pphead二者中只有一个为空时就会断言报错

还有一种情况就是pos的位置根本不在链表中,我们整个链表都找完了,就是没有找到pos的位置,所有我们要判断当链表遍历完时,仍然没有找到pos的位置,我们就需要提醒一下找不到pos的位置

代码
void SLInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{assert(pphead);assert((!(*pphead) == !pos) || pos && *pphead);if ((*pphead == pos))//头插情况{SLPushFront(pphead, x);}else {SLNode* prev = *pphead;while (prev->next != pos){if (prev->next == NULL){printf("找不到pos的位置");exit(-1;}prev = prev->next;}	SLNode* newnode = CreateNode(x);prev->next = newnode;newnode->next = pos;}
}

链表任意位置前删除void SLErase(SLNode**pphead,SLNode* pos)

函数功能为删除pos位置的节点
这个函数和之前的函数实现方式都是差不多的,删除一个节点,就需要找到这个节点的前一个节点

void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);SLNode* prev = *pphead;while (prev->next != pos){if (prev->next == NULL){printf("找不到pos的位置");exit(-1);}prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;
}

这个代码过程如下图

prev->next=pos
在这里插入图片描述
让prev->next=pos->next
在这里插入图片描述
释放pos指向节点的空间
在这里插入图片描述

上面的代码还是少考虑了只有一个节点时的情况
prev->next为空,但是prev已经在pos所在的位置了
在这里插入图片描述
我们就应该加一个判断,if(*pphead=pos),然后就直接头删

代码
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pphead);assert(*pphead);assert(pos);if (*pphead == pos){SLPopFront(pphead);}else{SLNode* prev = *pphead;while (prev->next != pos){if (prev->next == NULL){printf("找不到pos的位置");exit(-1);}prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}

链表任意位置后插入void SLInsertAfter( SLNode* pos,SLNDataType x)

之前是在pos位置之前插入,我们需要遍历链表才能找到pos位置之前的节点,所以需要传pphead,而这个函数是在pos位置后插入,所有就不需要传pphead

void SLInsertAfter( SLNode* pos,SLNDataType x)
{assert(pos);SLNode* newnode = CreateNode(x);pos->next = newnode;newnode->next = pos->next;
}

这是一段错误的代码
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
我们发现按照上面的逻辑pos->next其实就是newnode->next,所以在用这个函数时就会出现问题

代码
void SLInsertAfter( SLNode* pos,SLNDataType x)
{assert(pos);SLNode* newnode = CreateNode(x);newnode->next = pos->next;pos->next = newnode;
}
例题

用void SLInsertAfter( SLNode* pos,SLNDataType x)实现在pos位置前插入一个节点
思路:虽然我们不知道pos位置前一个节点的地址,但是我们可以通过这个函数在pos位置后插入一个节点,然后让这个节点的数据val和pos位置的数据val交换,就可以实现这pos位置之前插入节点
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

链表任意位置后删除void SLEraseAfter(SLNode* pos, SLNDataType x)

我们来看看下面一段代码

void SLEraseAfter(SLNode*pos)
{assert(pos);pos->next=pos->next->next;free(pos->next);
}

这段代码有人认为程序运行的过程如下
在这里插入图片描述

在这里插入图片描述

其实是这样的
在这里插入图片描述

在这里插入图片描述
这段代码不仅没有删除pos的下一个节点,反而让pos下一个节点的next指针变成了野指针

正确的方法是需要用tail指针保存pos->next,然后让pos->next=pos->next->next,之后再释放掉tail指向的空间

void SLEraseAfter(SLNode* pos, SLNDataType x)
{assert(pos);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

但是我们还需要考虑到pos为尾节点的情况,因为pos->next=NULL,而pos->next->next就不知道是什么了,所以我们还需要加一下断言

代码
void SLEraseAfter(SLNode* pos, SLNDataType x)
{assert(pos);assert(pos->next);SLNode* tmp = pos->next;pos->next = pos->next->next;free(tmp);tmp = NULL;
}

销毁链表void SLDestroy(SLNode** pphead)

代码
void SLDestroy(SLNode** pphead)
{assert(pphead);SLNode* cur = *pphead;while (cur != NULL){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.xdnf.cn/news/1842.html

如若内容造成侵权/违法违规/事实不符,请联系一条长河网进行投诉反馈,一经查实,立即删除!

相关文章

有php转go项目经验者优先?

新的一周又来了,今天分享的是上海某公司的一面面经,内容主要就是go、mysql和项目,职位要求如下: 发现一个很有意思的点—有php转go项目经验者优先。想不到还有这种好事,本人就是php转go,跟我有相同经历的朋…

【AI换脸整合包及教程】AI 换脸新潮流:FaceFusion 3.0.0,开启无限创意之旅

在科技飞速发展的今天,人工智能已经深入到我们生活的各个角落。其中,AI 换脸技术以其惊人的创造力和趣味性,吸引了无数人的目光。而在众多 AI 换脸工具中,FaceFusion 3.0.0 脱颖而出,成为了引领潮流的佼佼者。 一、AI …

【智慧中控项目】

智慧中控 前言一、搭建开发环境1.需要做什么?1.1 刷机和启动OrangePi Zero2(全志H616芯片)1.2 在PC上安装虚拟机VM(安装VirtualBox或VMware:这是常用的虚拟机软件工具)1.3 在虚拟机VM(VirtualBo…

“短线看涨”,上升周期中,抓以小波段行情,落袋为安

使用技巧 短线看涨指标属于副图公式,短线怎么操作?看蓝色短期安全线 这个公式主要是在上升周期中,抓以小波段行情为主,落袋为安 弱水三千 只取一瓢 公式 DIFM:(EMA(C,240)-EMA(C,520)); DEAM:EMA(DIFM,180); MACD&#xff08…

21_双端 diff 算法

目录 双端比较的原理非理想状况的处理方式添加新元素移除不存在的元素 在上一节中,我们实现了简单的 diff 算法,简单的 diff 算法利用 key 属性,尽可能的复用 DOM 元素,并通过移动 DOM 元素来完成更新,从而减少不断创建…

微服务实战系列之玩转Docker(十六)

导览 前言Q:基于容器云如何实现高可用的配置中心一、etcd入门1. 简介2. 特点 二、etcd实践1. 安装etcd镜像2. 创建etcd集群2.1 etcd-node12.2 etcd-node22.3 etcd-node3 3. 启动etcd集群 结语系列回顾 前言 Docker,一个宠儿,一个云原生领域的…

注册信息的提交

动态网页是指能够根据用户的操作或输入动态变化的网页。与静态网页相比,动态网页具有交互性和可变性。 一 动态网页概念 动态网页通常使用脚本语言(如JavaScript)与服务器进行交互,从服务器获取数据并动态更新网页内容。常见的动…

aws 部署测试环境服务+ip域名绑定

aws 部署springboot vue ip域名绑定域名 1.新建实例之后,作为测试环境开放mysql入出站规则,route53域名,红框中放入阿里云域名 1.设置出入站规则 实例应用安全组 2.mysql aws部署,redis,java环境,参见之前文章腾讯…

《数字图像处理基础》学习05-数字图像的灰度直方图

目录 一,数字图像的数值描述 1,二值图像 2,灰度图像 3,彩色图像 二,数字图像的灰度直方图 一,数字图像的数值描述 在之前的学习中,我知道了图像都是二维信息&…

书生大模型第四期 | L0G3000 git 基础知识

1、破冰行动 fork项目 PR链接:跳转访问 https://github.com/InternLM/Tutorial/pull/21632、构建个人项目 创建一个仓库保存LLM学习的笔记,以md文件为主 博客页面项目

使用 OpenTelemetry 定制跨度名称并丰富跨度而无需更改代码 - 第 1 部分

作者:来自 Elastic David Hope OpenTelemetry Collector 提供强大的功能,可以在遥测数据到达可观察性工具之前丰富和细化遥测数据。在这篇博文中,我们将探讨如何利用 Collector 在 Elastic Observability 中创建更有意义的 transaction 名称&…

成都睿明智科技有限公司正规吗靠谱吗?

在这个短视频风起云涌的时代,抖音电商以其独特的魅力,成为了无数商家竞相追逐的新蓝海。而在这片浩瀚的商海中,成都睿明智科技有限公司犹如一艘装备精良的航船,引领着众多企业破浪前行,探索抖音电商的无限可能。今天&a…

GHuNeRF: Generalizable Human NeRF from a Monocular Video

研究背景 研究问题:这篇文章要解决的问题是学习一个从单目视频中泛化的人类NeRF模型。尽管现有的泛化人类NeRF已经取得了令人印象深刻的成果,但它们需要多视图图像或视频,这在某些情况下可能不可用。此外,一些基于单目视频的人类…

中聚企服:打造智能企业服务助手,“中聚AI”解答一切企业难题

近日,一款专为企业用户设计的智能问答助手——“中聚AI”正式亮相市场。这款AI由中产聚融有限公司旗下的中聚企服团队自主研发,旨在帮助企业用户快速、高效地解答经营过程中的各种难题,覆盖从公司注册、财税规划到知识产权和资质办理等多领域…

手把手教你轻松掌握~Air780E软件UDP应用示例!快来看!

还不会的小伙伴看过来!通过本文的介绍,相信大家已经掌握了Air780E模组UDP应用的基本操作和常见问题的解决方法。赶快动手实践吧,让你的项目更加高效稳定! 1、UDP概述 UDP(用户数据报协议,UserDatagramProt…

Win10搭建SFTP服务器

1、下载安装 Release v9.5.0.0p1-Beta PowerShell/Win32-OpenSSH GitHub 下载OpenSSH-Win64.zip 解压之后放入到:C:\Program Files (x86)\OpenSSH-Win64以管理员身份打开CMD进入到 C:\Program Files (x86)\OpenSSH-Win64 文件夹执行命令 powershell.exe -Exec…

1分钟解决Excel打开CSV文件出现乱码问题

一、编码问题 1、不同编码格式 CSV 文件有多种编码格式,如 UTF - 8、UTF - 16、ANSI 等。如果 CSV 文件是 UTF - 8 编码,而 Excel 默认使用的是 ANSI 编码打开,就可能出现乱码。例如,许多从网络应用程序或非 Windows 系统生成的 …

构建灵活、高效的HTTP/1.1应用:探索h11库

文章目录 构建灵活、高效的HTTP/1.1应用:探索h11库背景这个库是什么?如何安装这个库?库函数使用方法使用场景常见的Bug及解决方案总结 构建灵活、高效的HTTP/1.1应用:探索h11库 背景 在现代网络应用中,HTTP协议是基础…

【算法】C++深度优先搜索(DFS)全解析

📢博客主页:https://blog.csdn.net/2301_779549673 📢欢迎点赞 👍 收藏 ⭐留言 📝 如有错误敬请指正! 📢本文由 JohnKi 原创,首发于 CSDN🙉 📢未来很长&#…

汽车免拆诊断案例 | 2010款起亚赛拉图车发动机转速表指针不动

故障现象  一辆2010款起亚赛拉图车,搭载G4ED 发动机,累计行驶里程约为17.2万km。车主反映,车辆行驶正常,但组合仪表上的发动机转速表指针始终不动。 故障诊断  接车后进行路试,车速表、燃油存量表及发动机冷却温度…