单链表的增删查改的讲解与实现(一篇包懂)

2024-05-06 01:04

本文主要是介绍单链表的增删查改的讲解与实现(一篇包懂),希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

一:顺序表的概念

概念:链表是一种 物理存储结构上非连续 、非顺序的存储结构,数据元素的 逻辑顺序 是通过链表
中的 指针链接 次序实现的 。

二:顺序表的实现
第一点:
本文采用三个文件进行实现
1:SList.h(对实现函数以及节点的声明)
2:SList.c(增删查改的函数的实现)
3:text.c(对程序的使用检测)

第二点:

本文需要用到的参数和变量

1:plist:实参,头指针
2:phead:形参,头指针
3:pphead:实参的地址,二级指针

第三点:

所有的函数实现内部第一步永远考虑是否需要对接收到的结构体指针进行断言,这样会更严谨!

1:参数为pphead的,一定需要断言,因为不管头指针plist是否为空,头指针plist的地址(pphead)都不会为空!

2:*pphead(plist)在某些函数下需要进行断言!头插尾插检查pphead,头删尾删不仅需要检查pphead还要检查*pphead,因为如果plist(*pphead)为空,代表是个空链表,空链表无法进行头删和尾删!

三:函数的实现讲解

前提:节点的声明

解释:

1:data用来保存节点的值,next用来指向下一个节点

2:将类型进行一个typedef,方便之后的类型改变带来的修改,只需要修改int即可。

3:将结构体重命名为SLTNode,方便之后使用。

第一个函数:创建新节点函数

解释:

1:参数为一个值,将会赋给创建的新节点的data。然后将创建的节点的next置空(会方便后续的操作)。

2:初始化(malloc)顺序表的空间为一个节点的大小,malloc函数的返回值为void*,所以需要强转为SLTNode* 的类型,然后该空间才能给新节点使用。

3:malloc开辟失败的检测,以及exit(-1)代表即刻退出。

第二个函数:头插

 解释:

1:头插一定会改变头指针的指向,本质是要改变plist指针的指向,所以参数应该是二级指针参数pphead(plist的地址),这样才能真正的改变plist指针。

2:对pphead断言,因为不管头指针plist是否为空,头指针plist的地址(pphead)都不会为空!不需要对*pphead(plist)断言,因为空链表也可以进行头插!

3:创建的newnode节点需要指向一开始头指针指向的节点(不管这个节点是NULL还是真的存在),然后再让头指针指向newnode节点。一定要注意这两步的先后顺序!

第三个函数:尾插

解释: 

1:尾插有可能会成为头插,在该链表为空链表的时候,而头插会改变头指针(plist)的指向,所以参数也是一个二级指针(pphead)。

2:不需要对*pphead(plist)进行断言,因为链表为空也可以进行尾插。

3:情况1(空链表),只需要把头指针plist(*pphead)的指向改为尾插创建的newnode节点,newnode的next不需要置空,因为在节点创建函数里面,newnode的next就已经置空为NULL了。

4:情况2(不是空链表),那就需要找到尾节点,然后将尾节点指向newnode,while(tail->next!=NULL),这一步会让tail在指向尾节点的时候停下来,因为尾节点的next为NULL。

第四个函数:头删

解释:

1:头删不仅要对pphead进行断言检查,还要对*pphead进行检查,因为空链表无法头删。

2:头删就是让头指针去指向原本头指针指向节点的下一个节点,然后再去释放掉第一个节点的内容,而为什么不直接用*pphead(plist)去进行操作,因为这样释放的时候会释放掉操作后头指针指向的第二个节点,所以需要将头指针保存到新变量newhead中,这样才能完美的完成操作!

第五个函数:尾删

解释:

1:尾删不仅要对pphead进行断言检查,还要对*pphead进行检查,因为空链表无法尾删。

2:情况1(只有一个节点),该情况类似头删中只有一个节点的时候,只需要将*ppead(plist)指向的内容free掉,然后将*pphead的next置空。

3:情况2(不止一个节点)

方法一:创建两个变量,tail和tailprev,目的是最后让tail指向尾节点,while(tail->next!=NULL),这一步会让tail在指向尾节点的时候停下来,因为尾节点的next为NULL。让tailprev指向倒数第二个节点(尾节点的前一个节点),然后释放掉tail指向的尾节点,然后把tail置空,最后把tailprev(指向倒数第二个节点)的next置空,因为此时倒数第二个节点就是尾节点了,尾节点的next应该为NULL。

方法二:只需要创建一个变量tail就行,while(tail->next->next)这一步会让tail最后指向倒数第二个节点,然后再tail->next找到尾节点,将其释放,然后再把tail 的next置空。

第六个函数:查找是否存在某节点的值为x

解释:

1:不需要断言,因为空链表我们找不到会返回NULL

2:找到会返回cur指向的节点

第七个函数:在pos节点之前插入一个值为x的节点

 解释:

1:不仅要对pphead进行断言检查,还要对*pphead进行检查,因为空链表无法找到pos节点。

2:情况1(头插),在第一个节点前插入,复用头插函数即可。

3:情况2(其他位置插入),创建一个prev,去找到pos节点的前一个节点,然后把prev指向插入的新节点newnode,然后再让newnode指向pos节点,这两步的先后顺序很重要!

第八个函数:在pos节点之后插入一个值为x的节点

解释:

1:对pos的断言,因为无法寻找空节点。

2:先让插入的新节点指向原先pos指向的节点,然后再让pos去指向这个新节点,这两步的先后顺序很重要!

第九个函数:删除pos节点

解释:

1:不仅要对pphead断言检查,也要对pos断言检查,因为无法删除一个空节点。

2:情况1(头删),删除第一个节点的时候,直接复用头删函数即可。

3:情况2(删除其他位置节点,包括尾删),创建一个prev,while循环让prev指向pos的前一个节点,然后将prev指向pos指向的节点,最后再释放掉pos节点。

第十个函数:删除pos节点的后一个节点 

解释:

1:不仅要对pos断言检查,因为无法删除空节点的下一个节点,也要对pos的下一个节点(pos->next)进行断言检查,因为如果下一个节点为空,也无法删除。

2:创建一个posNext,让其指向pos的下一个节点,然后让pos指向下一个节点(posNext)的下一个节点,最后再去释放(posNext),并将其置空。

第十一个函数:打印单链表

 解释:

1:不需要断言,空链表本身就是NULL。

2:遍历打印

最后是text.c函数进行一系列测试的运行结果:

效果如下:

头文件的展示:

 

 

 

这篇关于单链表的增删查改的讲解与实现(一篇包懂)的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/963129

相关文章

c++ 类成员变量默认初始值的实现

《c++类成员变量默认初始值的实现》本文主要介绍了c++类成员变量默认初始值,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧... 目录C++类成员变量初始化c++类的变量的初始化在C++中,如果使用类成员变量时未给定其初始值,那么它将被

Qt使用QSqlDatabase连接MySQL实现增删改查功能

《Qt使用QSqlDatabase连接MySQL实现增删改查功能》这篇文章主要为大家详细介绍了Qt如何使用QSqlDatabase连接MySQL实现增删改查功能,文中的示例代码讲解详细,感兴趣的小伙伴... 目录一、创建数据表二、连接mysql数据库三、封装成一个完整的轻量级 ORM 风格类3.1 表结构

基于Python实现一个图片拆分工具

《基于Python实现一个图片拆分工具》这篇文章主要为大家详细介绍了如何基于Python实现一个图片拆分工具,可以根据需要的行数和列数进行拆分,感兴趣的小伙伴可以跟随小编一起学习一下... 简单介绍先自己选择输入的图片,默认是输出到项目文件夹中,可以自己选择其他的文件夹,选择需要拆分的行数和列数,可以通过

Python中将嵌套列表扁平化的多种实现方法

《Python中将嵌套列表扁平化的多种实现方法》在Python编程中,我们常常会遇到需要将嵌套列表(即列表中包含列表)转换为一个一维的扁平列表的需求,本文将给大家介绍了多种实现这一目标的方法,需要的朋... 目录python中将嵌套列表扁平化的方法技术背景实现步骤1. 使用嵌套列表推导式2. 使用itert

Python使用pip工具实现包自动更新的多种方法

《Python使用pip工具实现包自动更新的多种方法》本文深入探讨了使用Python的pip工具实现包自动更新的各种方法和技术,我们将从基础概念开始,逐步介绍手动更新方法、自动化脚本编写、结合CI/C... 目录1. 背景介绍1.1 目的和范围1.2 预期读者1.3 文档结构概述1.4 术语表1.4.1 核

在Linux中改变echo输出颜色的实现方法

《在Linux中改变echo输出颜色的实现方法》在Linux系统的命令行环境下,为了使输出信息更加清晰、突出,便于用户快速识别和区分不同类型的信息,常常需要改变echo命令的输出颜色,所以本文给大家介... 目python录在linux中改变echo输出颜色的方法技术背景实现步骤使用ANSI转义码使用tpu

Python使用python-can实现合并BLF文件

《Python使用python-can实现合并BLF文件》python-can库是Python生态中专注于CAN总线通信与数据处理的强大工具,本文将使用python-can为BLF文件合并提供高效灵活... 目录一、python-can 库:CAN 数据处理的利器二、BLF 文件合并核心代码解析1. 基础合

Python使用OpenCV实现获取视频时长的小工具

《Python使用OpenCV实现获取视频时长的小工具》在处理视频数据时,获取视频的时长是一项常见且基础的需求,本文将详细介绍如何使用Python和OpenCV获取视频时长,并对每一行代码进行深入解析... 目录一、代码实现二、代码解析1. 导入 OpenCV 库2. 定义获取视频时长的函数3. 打开视频文

golang版本升级如何实现

《golang版本升级如何实现》:本文主要介绍golang版本升级如何实现问题,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录golanwww.chinasem.cng版本升级linux上golang版本升级删除golang旧版本安装golang最新版本总结gola

SpringBoot中SM2公钥加密、私钥解密的实现示例详解

《SpringBoot中SM2公钥加密、私钥解密的实现示例详解》本文介绍了如何在SpringBoot项目中实现SM2公钥加密和私钥解密的功能,通过使用Hutool库和BouncyCastle依赖,简化... 目录一、前言1、加密信息(示例)2、加密结果(示例)二、实现代码1、yml文件配置2、创建SM2工具