【数据结构与算法】单链表的增删查改(附源码)
这么可爱的猫猫不值得点个赞吗😽😻
目录
一.链表的概念和结构
二.单链表的逻辑结构和物理结构
1.逻辑结构
2.物理结构
三.结构体的定义
四.增加
1.尾插 SListpushback
2.头插 SListpushfront
五.删除
1.尾删 SListpopback
2.头删 SListpopfront
六.查找 插入 释放 打印
1.查找 SListfind
2.插入 SListinsert
3.释放 SListerase
4.打印 SListprint
七.源码
1.SList.h
2.SList.c
3.test.c
一.链表的概念和结构
链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表
中的指针链接次序实现的
链表其实有很多种类:
1.单向 双向
2.带头 不带头
3.循环 不循环
其中共能组合出8种形式的链表;
这篇文章讲的是结构最简单的链表,也就是单向不带头不循环链表,即单链表。
单链表中的元素称为节点,节点有一个数据data,还有一个结构体指针next 存储下一个节点的地址,最后一个节点的next是NULL。
二.单链表的逻辑结构和物理结构
1.逻辑结构
2.物理结构
三.结构体的定义
typedef int SLdatatype; //对数据类型重定义,方便后续更改typedef struct SListNode
{SLdatatype data;struct SListNode* next;
}SLNode;
四.增加
1.尾插 SListpushback
想要实现尾插,就要先找到尾节点,但要注意,当链表是空时,就没有尾节点,这个时候直接插入就行了;
我们可以申请一个新的节点newnode,然后插入链表中,由于尾插和头插都需要申请新的节点,所以我们可以将这封装成一个函数;
注意,不管是尾插还是头插,最后都会使链表发生改变,所以我们要传二级指针进去。
找尾节点时,while里的循环条件要写成 tail->next !=NULL
请看逻辑结构:
申请新节点 BuySListNode
SLNode* BuySListNode(SLdatatype x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));assert(newnode);newnode->data = x; //x是要插入的数据newnode->next = NULL;return newnode;
}
尾插 SListpushback
void SListpushback(SLNode** pphead,SLdatatype x) //注意传的是二级指针
{SLNode* newnode = BuySListNode(x);if (*pphead == NULL) //判断链表是否为空{*pphead = newnode;}else{SLNode* tail = *pphead; //寻找尾节点while (tail->next != NULL) //注意这里不能写成 while(tail!=NULL){tail = tail->next;}tail->next = newnode;}
}
2.头插 SListpushfront
头插时只需让新节点的 next 指向旧的头节点,然后再把 newnode 赋给头节点,使之成为新的头节点,即使是空表也没关系,newnode 会直接成为头节点。
void SListpushfront(SLNode** pphead, SLdatatype x)
{SLNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}
五.删除
1.尾删 SListpopback
尾删前,我们需要判断:
1.若为空表,则直接结束函数;
2.若链表中只有一个节点,则直接 free 头节点,然后置为NULL;
3.寻找尾节点 tail 和尾节点的前一个节点 pre ,因为我们释放掉尾节点后,pre就成为了新的尾节点,而尾节点的 next 是 NULL ,所以我们需要找到尾节点的前一个节点。
找尾的方法和之前的一样。
void SListpopback(SLNode** pphead)
{if (*pphead == NULL){return;}else if ((*pphead)->next == NULL) //注意这里因为优先级的问题,*pphead 要打括号{free(*pphead);*pphead = NULL;}else{SLNode* pre = NULL;SLNode* tail = *pphead;while (tail->next != NULL){pre = tail; //记录 tail 的前一个节点tail = tail->next;}pre->next = NULL; //next 置为NULL}
}
2.头删 SListpopfront
在头删前:
1.判断是否为空表;
2.定义一个 next 用来保存头节点中的 next ,释放完后,这个 next 就成为了新的头节点。
void SListpopfront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}
六.查找 插入 释放 打印
1.查找 SListfind
在插入和释放前,都需要调用 find 函数,来找到希望插入或是释放的位置。
SLNode* SListfind(SLNode* phead, SLdatatype x)
{SLNode* pos = phead;while (pos){if (pos->data == x){return pos;}pos = pos->next;}
}
2.插入 SListinsert
如果是链表中只有一个节点,就变成了头插,只需要调用头插函数就行了,如果是空表也不用担心,可以设置成不调用函数;
在插入前,需要找到指定位置 pos 的前驱 pre,
使pre->next=newnode , newnode->next=pos
如图所示,假设在3的前一个位置插入数据:
void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{SLNode* newnode = BuySListNode(x);if (pos->next == NULL){SListpushfront(pphead, x);}else{SLNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}pre->next = newnode;newnode->next = pos;}
}
3.释放 SListerase
释放前:
1.如果只有一个节点,则直接释放头节点,再置为空即可;
2.如果不止一个节点,还需找到要释放的位置的前一个节点 pre ,将 pre 的 next 指向 pos 的next,然后再释放;
如图所示,假设要释放掉3这个节点:
void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{if (pos->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* pre = *pphead;while (pre->next !=pos){pre = pre->next;}pre->next = pos->next;free(pos);}
}
4.打印 SListprint
虽然可以直接用头节点 phead 遍历,但博主还是推荐定义一个新的结构体指针 cur ,把phead 的值赋给 cur ,会显得更优雅;
注意这里的 while 里的式子要写成 cur ,如果 写成 cur->next ,那么最终打印出来的结果会少一个节点的数据。
void SListprint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}
七.源码
1.SList.h
#define _CRT_SECURE_NO_WARNINGS#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLdatatype;typedef struct SListNode
{SLdatatype data;struct SListNode* next;
}SLNode;void SListprint(SLNode* phead); //打印void SListpushback(SLNode** pphead,SLdatatype x); //尾插void SListpushfront(SLNode** pphead, SLdatatype x); //头插void SListpopfront(SLNode** pphead); //头删void SListpopback(SLNode** pphead); //尾删SLNode* SListfind(SLNode* phead,SLdatatype x); //查找void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x); //插入void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x); //释放
2.SList.c
#define _CRT_SECURE_NO_WARNINGS#include "SList.h"void SListprint(SLNode* phead)
{SLNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}SLNode* BuySListNode(SLdatatype x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));assert(newnode);newnode->data = x;newnode->next = NULL;return newnode;
}void SListpushback(SLNode** pphead,SLdatatype x)
{SLNode* newnode = BuySListNode(x);if (*pphead == NULL){*pphead = newnode;}else{SLNode* tail = *pphead; //寻找尾节点while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}void SListpushfront(SLNode** pphead, SLdatatype x)
{SLNode* newnode = BuySListNode(x);newnode->next = *pphead;*pphead = newnode;
}void SListpopfront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}void SListpopback(SLNode** pphead)
{if (*pphead == NULL){return;}else if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* pre = NULL;SLNode* tail = *pphead;while (tail->next != NULL){pre = tail;tail = tail->next;}pre->next = NULL;}
}SLNode* SListfind(SLNode* phead, SLdatatype x)
{SLNode* pos = phead;while (pos){if (pos->data == x){return pos;}pos = pos->next;}
}void SListinsert(SLNode** pphead, SLNode* pos,SLdatatype x)
{SLNode* newnode = BuySListNode(x);if (pos->next == NULL){SListpushfront(pphead, x);}else{SLNode* pre = *pphead;while (pre->next != pos){pre = pre->next;}pre->next = newnode;newnode->next = pos;}
}void SListerase(SLNode** pphead, SLNode* pos, SLdatatype x)
{if (pos->next == NULL){free(*pphead);*pphead = NULL;}else{SLNode* pre = *pphead;while (pre->next !=pos){pre = pre->next;}pre->next = pos->next;free(pos);}
}
3.test.c
博主写的主函数只是用来测试单链表的,写起主函数来也不难,大家可以自行编写。
#include "SList.h"void testSList1()
{SLNode* plist = NULL;SListpushback(&plist,1);SListpushback(&plist,2);SListpushback(&plist,3);SListpushback(&plist,4);SListprint(plist);SListpushfront(&plist, 0);SListprint(plist);SListpopfront(&plist);SListpopfront(&plist);SListpopfront(&plist);SListprint(plist);SListpopback(&plist);SListpopback(&plist);SListpopback(&plist);SListprint(plist);
}void testSList2()
{SLNode* plist = NULL;SListpushback(&plist, 1);SListpushback(&plist, 2);SListpushback(&plist, 3);SListpushback(&plist, 4);SLNode* pos = SListfind(plist, 3);if (pos){SListinsert(&plist,pos, 20);SListprint(plist);}pos = SListfind(plist, 2);if (pos){SListerase(&plist,pos,2);SListprint(plist);}}int main()
{//testSList1();testSList2();return 0;
}
八.单链表的一些问题
在单链表中,要想找到某一个数据,就需要从头节点开始,所以单链表是非随机存取的存储结构,且要想对单链表进行一些操作,总是要找到前驱节点,有时还需判断一些特殊情况,有什么办法能解决这些问题呢?
博主将在下篇双向带头循环链表中讲解,敬情期待~
🤩🥰本篇文章到此就结束了,如有错误或是建议,欢迎小伙伴们提出~😍😃
🐲👻希望可以多多支持博主哦~🥰😍
🤖🐯谢谢你的阅读~👻🦁
相关文章:

【数据结构与算法】单链表的增删查改(附源码)
这么可爱的猫猫不值得点个赞吗😽😻 目录 一.链表的概念和结构 二.单链表的逻辑结构和物理结构 1.逻辑结构 2.物理结构 三.结构体的定义 四.增加 1.尾插 SListpushback 2.头插 SListpushfront 五.删除 1.尾删 SListpopback 2.头删 SListpo…...
华为OD机试 - 回文字符串
题目描述 如果一个字符串正读和反渎都一样(大小写敏感),则称它为一个「回文串」,例如: leVel是一个「回文串」,因为它的正读和反读都是leVel;同理a也是「回文串」art不是一个「回文串」,因为它的反读tra与正读不同Level不是一个「回文串」,因为它的反读leveL与正读不…...
C语言太简单?这14道C语言谜题,你能答对几个
14个C语言的迷题以及答案,代码应该是足够清楚的,而且有相当的一些例子可能是我们日常工作可能会见得到的。通过这些迷题,希望你能更了解C语言。 如果你不看答案,不知道是否有把握回答各个谜题?让我们来试试。 下面的…...

Benchmark测试——fio——源码分析
1. main 1.1 parse_options() 解析选项,更新数据结构 1.1.1 fio_init_options() 1.1.2 fio_test_cconv(&def_thread.o) <cconv.c> 1.1.2.1 convert_thread_options_to_cpu() 传递options给数据结构 1.1.3 parse_cmd_line() switch语句多路选择&am…...

测量 R 代码运行时间的 5 种方法
简介 平常在撰写论文时,会需要比较算法之间的计算时间。本篇文章给出几种测量 R 代码运行时间的方法。本文是小编学习过程中的笔记,主要参考博客1,2。 1. 使用 Sys.time() 小编通常使用 Sys.time() 函数来计算时间。首先记录当前运行时刻&…...

Qt 第9课、计算器中缀转后缀算法
计算器核心算法: 1、将中缀表达式进行数字和运算符的分离 2、将中缀表达式转换成后缀表达式 3、通过后缀表达式计算最后的结果 二、计算器中缀转后缀算法 计算器中缀转后缀算法的意义在于把中缀表达式转换成后缀表达式,能够更好地计算 算法的基本思路…...

docker的使用方法
docker技术 同一个操作系统内跑多套不同版本依赖的业务 docker可以使同一个物理机中进程空间,网络空间,文件系统空间相互隔绝 虚拟机弊端:每个需要安装操作系统,太重量级,资源需要提前分配好 部署程序 开发环境 win…...

Kafka(五)生产者向发送消息的执行流程
(1)生产者要往 Kafka 发送消息时,需要创建 ProducerRecoder,代码如下: ProducerRecord<String,String> record new ProducerRecoder<>("CostomerCountry","Precision Products","France&q…...

华为OD机试模拟题 用 C++ 实现 - 简易压缩算法(2023.Q1)
最近更新的博客 【华为OD机试模拟题】用 C++ 实现 - 最多获得的短信条数(2023.Q1)) 文章目录 最近更新的博客使用说明简易压缩算法题目输入输出示例一输入输出说明示例二输入输出说明示例三输入输出说明...

MATLAB R2022b 安装教程
MATLAB R2022b 安装教程MathWorks 于2022年9月发布了 MATLAB 和 Simulink 产品系列的最新版本 Matlab R2022b版本 ,加入两个新产品: Medical Imaging Toolbox — 可视化、配准、分割和标注二维及三维医学图像Simscape Battery — 设计和仿真电池和储能系…...

PCI子系统
很多网络接口卡都是外围组件互联(Peripheral Compaonent Interconnect)设备,必须与Linux PCI子系统协同工作,并非所有的网络接口都是PCI设备,很多嵌入式设备的网络接口连接的就不是PCI总线,这些设备的初始化…...
Spring源码之IoC容器的Bean创建和依赖注入,DefaultListableBeanFactory容器为例
接上篇Spring源码之IoC容器初始化过程,以FileSystemXmlApplicationContext容器为例 因为FileSystemXmlApplicationContext使用的容器为DefaultListableBeanFactory,所以该篇基于DefaultListableBeanFactory的实现分析依赖注入过程。 目录获取Bean的总体流…...
解决小程序页面scroll-view块自身滑动问题
修改scroll-view的style样式 本来通过函数限制高度 style"margin-top:200rpx;"height: calc(100vh - 200rpx - env(safe-area-inset-bottom));会出现整个scroll-view块位置不固定滑动里面的内容后,自己本身在整个页面内上移,将样式改为&#…...

PowerCommand康明斯发电机控制屏维修HMI211
康明斯柴油发电机的监控系统分为普通机组控制屏和智能化机组控制界面。普通操作界面实用于普通的康明斯柴油发电机的控制,康明斯柴油发电机的起动与停止、供电与断电、状态调整等均由手动操作;自动化康明斯柴油发电机控制系统适合于智能化康明斯柴油发电…...

ELK + Kafka 测试
配置file beat输出到 Kafkalogstash服务器从kafka获取数据并输出到es集群在es集群上查看索引kibana界面添加索引查看数据1.配置file beat输出到 Kafka 1.1 Filebeat机器配置数据采集和输出目标 做好域名解析 # vim /usr/local/filebeat/filebeat.yml # 修改输出目标为kafka…...

迁移系统:换电脑或者硬盘转移磁盘文件的方法!
为什么要将操作系统迁移到新驱动? “将操作系统转移到新驱动您好,我刚刚为我的台式机订购了一个新的2TB希捷Barracuda硬盘,我想知道如何将我的Windows 10操作系统与我下载的其他一些软件一起转移过来。我使用新的/大的硬盘,然…...

职场性别报告,男女薪酬仍有差距,男性平均薪酬比女性高29.7%
性别是否影响职业?女性求职比男性更加困难?男性薪酬比女性更有优势?人们一说到警察、建筑师通常会想到高大魁梧的男性形象,一说到幼师、护士往往想到的都是温柔的女性形象,职业好似与性别挂钩;女性求职通常…...

5-Azidopentanoic acid,79583-98-5,5-Azidopentanoic COOH具有高效稳定,高特异性
5-Azidopentanoic acid,5-Azidopentanoic COOH,5-叠氮基戊酸产品规格:1.CAS号:79583-98-52.分子式:C5H9N3O23.分子量:143.074.包装规格:1g,5g,10g,包装灵活&a…...
滴滴前端高频react面试题汇总
说说 React组件开发中关于作用域的常见问题。 在 EMAScript5语法规范中,关于作用域的常见问题如下。 (1)在map等方法的回调函数中,要绑定作用域this(通过bind方法)。 (2)父组件传递…...

能在软路由docker给部署搭建teamsperk服务器么?并且设置好ddns
参考链接(4条消息) 【个人学习总结】使用docker搭建Teamspeak服务器_blcurtain的博客-CSDN博客_teamspeak3 docker(⊙﹏⊙)哎呀,崩溃啦! (tdeh.top)TeamSpeak服务器搭建与使用 - 缘梦の镇 (cmsboy.cn)Openwrt X86 docker运行甜糖-软路由,x86系统,openwrt…...
论文解读:交大港大上海AI Lab开源论文 | 宇树机器人多姿态起立控制强化学习框架(二)
HoST框架核心实现方法详解 - 论文深度解读(第二部分) 《Learning Humanoid Standing-up Control across Diverse Postures》 系列文章: 论文深度解读 + 算法与代码分析(二) 作者机构: 上海AI Lab, 上海交通大学, 香港大学, 浙江大学, 香港中文大学 论文主题: 人形机器人…...
Qt Widget类解析与代码注释
#include "widget.h" #include "ui_widget.h"Widget::Widget(QWidget *parent): QWidget(parent), ui(new Ui::Widget) {ui->setupUi(this); }Widget::~Widget() {delete ui; }//解释这串代码,写上注释 当然可以!这段代码是 Qt …...

大数据零基础学习day1之环境准备和大数据初步理解
学习大数据会使用到多台Linux服务器。 一、环境准备 1、VMware 基于VMware构建Linux虚拟机 是大数据从业者或者IT从业者的必备技能之一也是成本低廉的方案 所以VMware虚拟机方案是必须要学习的。 (1)设置网关 打开VMware虚拟机,点击编辑…...

转转集团旗下首家二手多品类循环仓店“超级转转”开业
6月9日,国内领先的循环经济企业转转集团旗下首家二手多品类循环仓店“超级转转”正式开业。 转转集团创始人兼CEO黄炜、转转循环时尚发起人朱珠、转转集团COO兼红布林CEO胡伟琨、王府井集团副总裁祝捷等出席了开业剪彩仪式。 据「TMT星球」了解,“超级…...
鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个生活电费的缴纳和查询小程序
一、项目初始化与配置 1. 创建项目 ohpm init harmony/utility-payment-app 2. 配置权限 // module.json5 {"requestPermissions": [{"name": "ohos.permission.INTERNET"},{"name": "ohos.permission.GET_NETWORK_INFO"…...
关于 WASM:1. WASM 基础原理
一、WASM 简介 1.1 WebAssembly 是什么? WebAssembly(WASM) 是一种能在现代浏览器中高效运行的二进制指令格式,它不是传统的编程语言,而是一种 低级字节码格式,可由高级语言(如 C、C、Rust&am…...

ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
Typeerror: cannot read properties of undefined (reading ‘XXX‘)
最近需要在离线机器上运行软件,所以得把软件用docker打包起来,大部分功能都没问题,出了一个奇怪的事情。同样的代码,在本机上用vscode可以运行起来,但是打包之后在docker里出现了问题。使用的是dialog组件,…...
JAVA后端开发——多租户
数据隔离是多租户系统中的核心概念,确保一个租户(在这个系统中可能是一个公司或一个独立的客户)的数据对其他租户是不可见的。在 RuoYi 框架(您当前项目所使用的基础框架)中,这通常是通过在数据表中增加一个…...

Python基于历史模拟方法实现投资组合风险管理的VaR与ES模型项目实战
说明:这是一个机器学习实战项目(附带数据代码文档),如需数据代码文档可以直接到文章最后关注获取。 1.项目背景 在金融市场日益复杂和波动加剧的背景下,风险管理成为金融机构和个人投资者关注的核心议题之一。VaR&…...