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

【数据结构与算法】单链表的增删查改(附源码)

 

这么可爱的猫猫不值得点个赞吗😽😻

目录

一.链表的概念和结构

二.单链表的逻辑结构和物理结构

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;
}

八.单链表的一些问题

在单链表中,要想找到某一个数据,就需要从头节点开始,所以单链表是非随机存取的存储结构,且要想对单链表进行一些操作,总是要找到前驱节点,有时还需判断一些特殊情况,有什么办法能解决这些问题呢?

博主将在下篇双向带头循环链表中讲解,敬情期待~


🤩🥰本篇文章到此就结束了,如有错误或是建议,欢迎小伙伴们提出~😍😃

🐲👻希望可以多多支持博主哦~🥰😍

🤖🐯谢谢你的阅读~👻🦁

 

相关文章:

【数据结构与算法】单链表的增删查改(附源码)

这么可爱的猫猫不值得点个赞吗&#x1f63d;&#x1f63b; 目录 一.链表的概念和结构 二.单链表的逻辑结构和物理结构 1.逻辑结构 2.物理结构 三.结构体的定义 四.增加 1.尾插 SListpushback 2.头插 SListpushfront 五.删除 1.尾删 SListpopback 2.头删 SListpo…...

华为OD机试 - 回文字符串

题目描述 如果一个字符串正读和反渎都一样(大小写敏感),则称它为一个「回文串」,例如: leVel是一个「回文串」,因为它的正读和反读都是leVel;同理a也是「回文串」art不是一个「回文串」,因为它的反读tra与正读不同Level不是一个「回文串」,因为它的反读leveL与正读不…...

C语言太简单?这14道C语言谜题,你能答对几个

14个C语言的迷题以及答案&#xff0c;代码应该是足够清楚的&#xff0c;而且有相当的一些例子可能是我们日常工作可能会见得到的。通过这些迷题&#xff0c;希望你能更了解C语言。 如果你不看答案&#xff0c;不知道是否有把握回答各个谜题&#xff1f;让我们来试试。 下面的…...

Benchmark测试——fio——源码分析

1. main 1.1 parse_options() 解析选项&#xff0c;更新数据结构 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 种方法

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

Qt 第9课、计算器中缀转后缀算法

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

docker的使用方法

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

Kafka(五)生产者向发送消息的执行流程

&#xff08;1&#xff09;生产者要往 Kafka 发送消息时&#xff0c;需要创建 ProducerRecoder,代码如下&#xff1a; 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版本 &#xff0c;加入两个新产品&#xff1a; Medical Imaging Toolbox — 可视化、配准、分割和标注二维及三维医学图像Simscape Battery — 设计和仿真电池和储能系…...

PCI子系统

很多网络接口卡都是外围组件互联&#xff08;Peripheral Compaonent Interconnect&#xff09;设备&#xff0c;必须与Linux PCI子系统协同工作&#xff0c;并非所有的网络接口都是PCI设备&#xff0c;很多嵌入式设备的网络接口连接的就不是PCI总线&#xff0c;这些设备的初始化…...

Spring源码之IoC容器的Bean创建和依赖注入,DefaultListableBeanFactory容器为例

接上篇Spring源码之IoC容器初始化过程&#xff0c;以FileSystemXmlApplicationContext容器为例 因为FileSystemXmlApplicationContext使用的容器为DefaultListableBeanFactory&#xff0c;所以该篇基于DefaultListableBeanFactory的实现分析依赖注入过程。 目录获取Bean的总体流…...

解决小程序页面scroll-view块自身滑动问题

修改scroll-view的style样式 本来通过函数限制高度 style"margin-top:200rpx;"height: calc(100vh - 200rpx - env(safe-area-inset-bottom));会出现整个scroll-view块位置不固定滑动里面的内容后&#xff0c;自己本身在整个页面内上移&#xff0c;将样式改为&#…...

PowerCommand康明斯发电机控制屏维修HMI211

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

ELK + Kafka 测试

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

迁移系统:换电脑或者硬盘转移磁盘文件的方法!

为什么要将操作系统迁移到新驱动&#xff1f; “将操作系统转移到新驱动您好&#xff0c;我刚刚为我的台式机订购了一个新的2TB希捷Barracuda硬盘&#xff0c;我想知道如何将我的Windows 10操作系统与我下载的其他一些软件一起转移过来。我使用新的/大的硬盘&#xff0c;然…...

职场性别报告,男女薪酬仍有差距,男性平均薪酬比女性高29.7%

性别是否影响职业&#xff1f;女性求职比男性更加困难&#xff1f;男性薪酬比女性更有优势&#xff1f;人们一说到警察、建筑师通常会想到高大魁梧的男性形象&#xff0c;一说到幼师、护士往往想到的都是温柔的女性形象&#xff0c;职业好似与性别挂钩&#xff1b;女性求职通常…...

5-Azidopentanoic acid,79583-98-5,5-Azidopentanoic COOH具有高效稳定,高特异性

5-Azidopentanoic acid&#xff0c;5-Azidopentanoic COOH&#xff0c;5-叠氮基戊酸产品规格&#xff1a;1.CAS号&#xff1a;79583-98-52.分子式&#xff1a;C5H9N3O23.分子量&#xff1a;143.074.包装规格&#xff1a;1g&#xff0c;5g&#xff0c;10g&#xff0c;包装灵活&a…...

滴滴前端高频react面试题汇总

说说 React组件开发中关于作用域的常见问题。 在 EMAScript5语法规范中&#xff0c;关于作用域的常见问题如下。 &#xff08;1&#xff09;在map等方法的回调函数中&#xff0c;要绑定作用域this&#xff08;通过bind方法&#xff09;。 &#xff08;2&#xff09;父组件传递…...

能在软路由docker给部署搭建teamsperk服务器么?并且设置好ddns

参考链接(4条消息) 【个人学习总结】使用docker搭建Teamspeak服务器_blcurtain的博客-CSDN博客_teamspeak3 docker(⊙﹏⊙)哎呀&#xff0c;崩溃啦&#xff01; (tdeh.top)TeamSpeak服务器搭建与使用 - 缘梦の镇 (cmsboy.cn)Openwrt X86 docker运行甜糖-软路由,x86系统,openwrt…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

安宝特方案丨XRSOP人员作业标准化管理平台:AR智慧点检验收套件

在选煤厂、化工厂、钢铁厂等过程生产型企业&#xff0c;其生产设备的运行效率和非计划停机对工业制造效益有较大影响。 随着企业自动化和智能化建设的推进&#xff0c;需提前预防假检、错检、漏检&#xff0c;推动智慧生产运维系统数据的流动和现场赋能应用。同时&#xff0c;…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

mysql已经安装,但是通过rpm -q 没有找mysql相关的已安装包

文章目录 现象&#xff1a;mysql已经安装&#xff0c;但是通过rpm -q 没有找mysql相关的已安装包遇到 rpm 命令找不到已经安装的 MySQL 包时&#xff0c;可能是因为以下几个原因&#xff1a;1.MySQL 不是通过 RPM 包安装的2.RPM 数据库损坏3.使用了不同的包名或路径4.使用其他包…...

Web 架构之 CDN 加速原理与落地实践

文章目录 一、思维导图二、正文内容&#xff08;一&#xff09;CDN 基础概念1. 定义2. 组成部分 &#xff08;二&#xff09;CDN 加速原理1. 请求路由2. 内容缓存3. 内容更新 &#xff08;三&#xff09;CDN 落地实践1. 选择 CDN 服务商2. 配置 CDN3. 集成到 Web 架构 &#xf…...

push [特殊字符] present

push &#x1f19a; present 前言present和dismiss特点代码演示 push和pop特点代码演示 前言 在 iOS 开发中&#xff0c;push 和 present 是两种不同的视图控制器切换方式&#xff0c;它们有着显著的区别。 present和dismiss 特点 在当前控制器上方新建视图层级需要手动调用…...

[大语言模型]在个人电脑上部署ollama 并进行管理,最后配置AI程序开发助手.

ollama官网: 下载 https://ollama.com/ 安装 查看可以使用的模型 https://ollama.com/search 例如 https://ollama.com/library/deepseek-r1/tags # deepseek-r1:7bollama pull deepseek-r1:7b改token数量为409622 16384 ollama命令说明 ollama serve #&#xff1a…...

淘宝扭蛋机小程序系统开发:打造互动性强的购物平台

淘宝扭蛋机小程序系统的开发&#xff0c;旨在打造一个互动性强的购物平台&#xff0c;让用户在购物的同时&#xff0c;能够享受到更多的乐趣和惊喜。 淘宝扭蛋机小程序系统拥有丰富的互动功能。用户可以通过虚拟摇杆操作扭蛋机&#xff0c;实现旋转、抽拉等动作&#xff0c;增…...

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的----NTFS源代码分析--重要

根目录0xa0属性对应的Ntfs!_SCB中的FileObject是什么时候被建立的 第一部分&#xff1a; 0: kd> g Breakpoint 9 hit Ntfs!ReadIndexBuffer: f7173886 55 push ebp 0: kd> kc # 00 Ntfs!ReadIndexBuffer 01 Ntfs!FindFirstIndexEntry 02 Ntfs!NtfsUpda…...

django blank 与 null的区别

1.blank blank控制表单验证时是否允许字段为空 2.null null控制数据库层面是否为空 但是&#xff0c;要注意以下几点&#xff1a; Django的表单验证与null无关&#xff1a;null参数控制的是数据库层面字段是否可以为NULL&#xff0c;而blank参数控制的是Django表单验证时字…...