[初阶数据结构】单链表
前言
📚作者简介:爱编程的小马,正在学习C/C++,Linux及MySQL。
📚本文收录于初阶数据结构系列,本专栏主要是针对时间、空间复杂度,顺序表和链表、栈和队列、二叉树以及各类排序算法,持续更新!
📚相关专栏C++及Linux正在发展,敬请期待!
目录
前言
1. 链表
1.1 链表的定义
1.2 链表与顺序表相比的好处
1.3 链表的结构表示
1.3.1 链表的结构形式
1.3.2 链表的结构性质
1.4 单链表的实现
1.4.1 单链表的创建
1.4.2 单链表的打印
1.4.3 单链表的动态内存申请
1.4.4 单链表的头插
1.4.5 单链表的尾插
1.4.6 单链表的头删
1.4.7 单链表的尾删
1.4.8 单链表的查找
1.4.9 单链表的任意位置插入的前插
1.4.10 单链表任意位置的删除
2.单链表的完整代码
2.1 test.c测试函数代码
2.2 SList.h函数声明代码
2.3 SList.c函数实现代码
总结
1. 链表
1.1 链表的定义
概念:链表是一种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序所决定的
本文只介绍最简单的链表结构:单链表
1.2 链表与顺序表相比的好处
1、顺序表从中间插入/头部插入,时间复杂度是O(N),因为要一次往后挪动,但是单链表是O(1),大大节省了程序运行时间。
2、 顺序表每次需要增容,到后期增容很大的时候,需要拷贝数据、开辟新空间、释放旧空间。会有不小的损耗。链表直接开辟一个结构体大小的空间即可。
3、增容一般是两倍,但是我就想多插入几个仅此而已,会造成空间的大规模浪费。链表同样更加简单且占用空间小。
1.3 链表的结构表示
首先要给大家介绍一下,就是链表中的结点是一个结构体,结点中一个变量是存储数据的,另一个变量是存储结构体地址的,上一个结点存下一个结点的地址,从而链接起来。
1.3.1 链表的结构形式
1.3.2 链表的结构性质
1、从上图可以看出,链表在逻辑上是连续的,在物理地址上是不连续的
2、现实的结点是动态内存在堆区申请出来的
3、堆上申请的空间,是按照一定的规律来的,有些可能相同,有些可能不同。
1.4 单链表的实现
1.4.1 单链表的创建
上文我们提到了,结点是一个结构体,第一个结构体变量是存储数据的,第二个是存储下一个链表的地址的
typedef int SListDataType;typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;
1.4.2 单链表的打印
void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL");
}
为什么是这样子打印的?给大家说一下思想:
1、单链表定义了最后一个链表的地址为空指针,所以我们就定义了一个cur来遍历整个链表
2、每找到一个数据我们就打印,然后遍历链表指针cur就往后走一步, 怎么走?是不是next中存放了下一个结点的地址,那么把cur管理的结构体中next的地址赋值给cur是不是相当于向后走了一步。
1.4.3 单链表的动态内存申请
SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}
比方说,我想申请一块动态内存空间,里面存储x的值,那么这个时候,就通过malloc在堆上申请一块空间,交给newnode管理,这时候把newnode中data的值赋值为x,newnode中next的值赋值为NULL后返回这块空间的地址。这是不是就很好的开辟了一个结点。如果开辟失败了就返回空指针。
1.4.4 单链表的头插
void SListPushFront(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);assert(newnode);newnode->next = *pphead;*pphead = newnode;
}
这里我们用newnode来管理开辟的新结点,如果开辟了失败了就不用往下了,开辟成功了往下走,我画个图来帮助大家理解上面代码的意思
1.4.5 单链表的尾插
我先给大家介绍一下,尾插有两种情况,第一种空链表,第二种,非空链表
先分析第一种情况,如果是空链表,是不是直接把newnode的地址给pphead是不是就可以了,
第二种情况,我给大家画个图一起来分析
void SListPushBack(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);//空链表if (*pphead == NULL){*pphead = newnode;return;}//非空链表SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}
第二种情况,首先我们要尾插,是不是要先找尾部在哪里?尾部在哪里?是不是说tail->next是空指针,这个就是链表中最后一个元素了,找到了之后,就把tail->next存newnode的地址就可以。
1.4.6 单链表的头删
给大家说一下啊,如何删除单链表中的数?是不是只需要让上个结点存下下个结点的地址就好了。
那么头删就是让*pphead指向下下个结点,然后释放第一个结点就好了。
那么,应该这么做,看代码
void SListPopFront(SLTNode** pphead)
{assert(*pphead);//链表只有一个值SLTNode* cur = *pphead;*pphead = cur->next;free(cur);cur = NULL;
}
画个图给大家理解一下:
1.4.7 单链表的尾删
尾删就更简单了,还是第一步,找尾,第二部,释放空间即可。
void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}
1.4.8 单链表的查找
在单链表中查找一个数,找到了就返回这个结点的地址,没找到就返回空指针。
SLTNode* SListFind(SLTNode* pphead, SListDataType x)
{assert(pphead);SLTNode* cur = pphead;while (cur){if (cur->data == x)return cur;elsecur = cur->next;}return NULL;
}
1.4.9 单链表的任意位置插入的前插
void SListInsertbefore(SLTNode** pphead, SLTNode* pos, SListDataType x)
{if (*pphead == NULL){SListPushFront(pphead, x);}//在pos前插入else{SLTNode* newnode = BuySLTNode(x);SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}
首先啊,如果pphead没有值,那么就相当于头插,如果链表中有值,画个图给大家理解
1.4.10 单链表任意位置的删除
void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}
2.单链表的完整代码
2.1 test.c测试函数代码
#include "SList.h"
SLTNode* Phead = NULL;
void Test1()
{//该函数测试头插和尾插SListPushFront(&Phead, 1);SListPushFront(&Phead, 2);SListPushFront(&Phead, 3);SListPushFront(&Phead, 4);SListPushFront(&Phead, 5);SListPushBack(&Phead, 2);SListPushBack(&Phead, 3);SListPushBack(&Phead, 4);PrintSList(Phead);
}void Test2()
{//该函数测试头删和尾删SListPushFront(&Phead, 1);SListPopBack(&Phead);PrintSList(Phead);
}
void Test3()
{//查找SListPushFront(&Phead, 1);SListPushFront(&Phead, 2);SListPushFront(&Phead, 3);SListPushFront(&Phead, 4);SLTNode* find = SListFind(Phead, 3);if (find)find->data = 30;PrintSList(Phead);
}
void Test4()
{//任意位置插入(前插)SListPushFront(&Phead, 1);SListPushFront(&Phead, 2);SListPushFront(&Phead, 3);SListPushFront(&Phead, 4);SLTNode* find1 = SListFind(Phead, 3);SLTNode* find2 = SListFind(Phead, 4);if (find1){SListInsertbefore(&Phead, find1, 40);SListEraseafter(find2);SListEraseafter(find1);}PrintSList(Phead);
}
int main()
{Test1();//Test2();//Test3();//Test4();return 0;
}
2.2 SList.h函数声明代码
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SListDataType;typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;void PrintSList(SLTNode* phead);
//头插
void SListPushFront(SLTNode** pphead, SListDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SListDataType x);
//头删
void SListPopFront(SLTNode** pphead);
//尾删
void SListPopBack(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* pphead, SListDataType x);
//在pos之后插入x
void SListInsertbefore(SLTNode** pphead,SLTNode* pos, SListDataType x);
//在pos之后插入x
void SListInsertafter(SLTNode* pos, SListDataType x);
//删除pos位置上的值
void SListErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的位置
void SListEraseafter(SLTNode* pos);
2.3 SList.c函数实现代码
#include "SList.h"
void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL");
}SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}
void SListPushFront(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);assert(newnode);newnode->next = *pphead;*pphead = newnode;
} void SListPushBack(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);//空链表if (*pphead == NULL){*pphead = newnode;return;}//非空链表SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}void SListPopFront(SLTNode** pphead)
{assert(*pphead);//链表只有一个值SLTNode* cur = *pphead;*pphead = cur->next;free(cur);cur = NULL;
}void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}SLTNode* SListFind(SLTNode* pphead, SListDataType x)
{assert(pphead);SLTNode* cur = pphead;while (cur){if (cur->data == x)return cur;elsecur = cur->next;}return NULL;
}
void SListInsertbefore(SLTNode** pphead, SLTNode* pos, SListDataType x)
{if (*pphead == NULL){SListPushFront(pphead, x);}//在pos前插入else{SLTNode* newnode = BuySLTNode(x);SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}void SListInsertafter(SLTNode* pos, SListDataType x)
{assert(pos);//只有一个SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}void SListEraseafter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* cur = pos->next;pos->next = cur->next;free(cur);cur = NULL;
}
总结
1、单链表其实不难,大家一定要搞清楚指针和结构体
2、一定要动手实践一下
3、其实数据结构就是围绕着数据的增删查改显示这几个点,所以一定要搞清楚每一个代码实现的逻辑。
如果这份博客对大家有帮助,希望各位给小马一个大大的点赞鼓励一下,如果喜欢,请收藏一下,谢谢大家!!!
制作不易,如果大家有什么疑问或给小马的意见,欢迎评论区留言。
相关文章:

[初阶数据结构】单链表
前言 📚作者简介:爱编程的小马,正在学习C/C,Linux及MySQL。 📚本文收录于初阶数据结构系列,本专栏主要是针对时间、空间复杂度,顺序表和链表、栈和队列、二叉树以及各类排序算法,持…...
项目使用git开发流程
第一步 项目初期:领导负责的工作 01 创建仓库:在码云上面创建仓库地址,创建完成后点击初始化README:郝陶涛/vue-tea 02 领导在桌面上将代码克隆下来:将代码克隆下来之后,切换到代码内部,使用g…...

Day 28 MySQL的数据备份与恢复
数据备份及恢复 1.概述 所有备份数据都应放在非数据库本地,而且建议有多份副本 备份: 能够防止由于机械故障以及人为误操作带来的数据丢失,例如将数据库文件保存在了其它地方 冗余: 数据有多份冗余,但不等备份&…...
PackageKit的使用(三)疑问篇
本篇主要是一些疑问归纳,不做具体的函数分析,但是会给出关键点,查看源码就会很清楚了 apt source PackageKit 1. org.freedesktop.PackageKit D-Bus 接口介绍 D-Bus API Reference: PackageKit Reference Manual c库的接口可以看源码。 2.…...

【Linux】17. 进程间通信 --- 管道
1. 什么是进程间通信(进程间通信的目的) 数据传输:一个进程需要将它的数据发送给另一个进程 资源共享:多个进程之间共享同样的资源。 通知事件:一个进程需要向另一个或一组进程发送消息,通知它(它们)发生了…...

有哪些有效的复习方法可以帮助备考软考?
软考目前仍然是一个以记忆为主、理解为辅的考试。学过软考的朋友可能会感到困惑,因为软考的知识在日常工作中有许多应用场景,需要理解的地方也很多。但为什么我说它是理解为辅呢?因为这些知识点只要记住了,都不难理解,…...

【MySQL | 第九篇】重新认识MySQL锁
文章目录 9.重新认识MySQL锁9.1MySQL锁概述9.2锁分类9.2.1锁的粒度9.2.2锁的区间9.2.3锁的性能9.2.4锁的级别 9.3拓展:意向锁9.3.1意向锁概述9.3.2意向锁分类9.3.3意向锁作用(1)意向锁的兼容互斥性(2)例子1(…...

含义:理财风险等级R1、R2、R3、R4、R5
理财风险等级R1、R2、R3代表什么,为什么R1不保本,R2可能亏损 不尔聊投资https://author.baidu.com/home?frombjh_article&app_id1704141696580953 我们购买理财产品的时候,首先都会看到相关产品的风险等级。风险等级约定俗成有5级&…...

ICode国际青少年编程竞赛- Python-2级训练场-列表入门
ICode国际青少年编程竞赛- Python-2级训练场-列表入门 1、 Dev.step(3)2、 Flyer.step(1) Dev.step(-2)3、 Flyer.step(1) Spaceship.step(7)4、 Flyer.step(5) Dev.turnRight() Dev.step(5) Dev.turnLeft() Dev.step(3) Dev.turnLeft() Dev.step(7) Dev.turnLeft() Dev.…...

【设计模式】14、strategy 策略模式
文章目录 十四、strategy 策略模式14.1 map_app14.1.1 map_app_test.go14.1.2 map_app.go14.1.3 navigate_strategy.go 十四、strategy 策略模式 https://refactoringguru.cn/design-patterns/strategy 需求: client 知道很多不同的策略, 希望在运行时切换. 场景示例: 就像高…...

C++类和对象(基础篇)
前言: 其实任何东西,只要你想学,没人能挡得住你,而且其实学的也很快。那么本篇开始学习类和对象(C的,由于作者有Java基础,可能有些东西过得很快)。 struct在C中的含义: …...
Oracle导入数据中文乱码问题处理,修改客户端字符编码跟数据库的一致
前提:SQL文件打开其中中文字符是正常显示,保证导出文件中文字符正常。通过sqlplus命令导入SQL文件出现乱码,这是因为客户端跟数据库的字符集不一致导致出现乱码问题。 要SQL导入的中文正常,要确保执行导入命令的客户端字符编码跟…...

【与 Apollo 共创生态:展望自动驾驶全新未来】
1、引言 历经七年的不懈追求与创新,Apollo开放平台已陆续推出了13个版本,汇聚了来自全球170多个国家与地区的16万名开发者及220多家合作伙伴。随着Apollo开放平台的不断创新与发展,Apollo在2024年4月19日迎来了Apollo开放平台的七周年大会&a…...

【webrtc】MessageHandler 5: 基于线程的消息处理:以PeerConnection信令线程为例
peerconn的信令是通过post 消息到自己的信令线程消息来处理的PeerConnectionMessageHandler 是具体的处理器G:\CDN\rtcCli\m98\src\pc\peer_connection_message_handler.hMachinery for handling messages posted to oneself PeerConnectionMessageHandler 明确服务于 signalin…...
计算机网络 3.2网络体系结构
第二节 网络体系结构 一、网络协议 1.定义: ①通信双方共同遵守的规则。 ②为网络数据交换制定的规则、约定与标准。 ③网络实体之间通信时有关信息传输顺序、信息格式、信息内容的约定或规则。 2.协议三要素: 语法:确定协议元素的格式…...

连接HiveMQ代理器实现MQTT协议传输
先下载MQTTX: MQTTX: Your All-in-one MQTT Client Toolbox 使用线上免费的MQTTX BROKER:The Free Global Public MQTT Broker | Try Now | EMQ 打开MQTTX,创建连接,点击NEW SUBSCRIPTION,创建一个主题,这里使用test/topic,在下面Json中填写…...

springcloud报错:Failed to start bean‘webServerStartStop‘
如果你正在使用nacos进行服务注册,然后报一下错误: 那就说明的nacos没有打开,所以找到你的下载nacos的文件夹 好了,错误完美解决~...
el-checkbox 无法动态设置勾选状态
问题 cheked 值动态变化,但是勾选状态无法动态改变 解决 v-model 与:checked 同时使用 <el-checkbox class"add-shop-check" v-model"renderData[0].isCheck" :checked"renderData[0].isCheck" change"checked > selec…...

车规级低功耗汽车用晶振SG-9101CGA
车规级晶振SG-9101CGA属于爱普生9101系列,是一款可编程晶振。SG-9101CGA车规级晶振采用2.5x2.0mm封装,利用PLL技术生产,此款振荡器的频率范围从0.67M~170MHZ任一频点可选,步进1ppm,采用标准CMOS输出,最大输…...

企业是保留传统的MES还是换新的MES?
在选择上MES系统的时候,企业可以根据自身所处行业不同、当前阶段不同,以及业务需求的差异,对症下药,选择适合自己的解决方案。对于有些企业本来就有MES系统,但是已经过时过旧,就要考虑换新的MES系统了. 保留…...
Spring AI 入门:Java 开发者的生成式 AI 实践之路
一、Spring AI 简介 在人工智能技术快速迭代的今天,Spring AI 作为 Spring 生态系统的新生力量,正在成为 Java 开发者拥抱生成式 AI 的最佳选择。该框架通过模块化设计实现了与主流 AI 服务(如 OpenAI、Anthropic)的无缝对接&…...
Go 语言并发编程基础:无缓冲与有缓冲通道
在上一章节中,我们了解了 Channel 的基本用法。本章将重点分析 Go 中通道的两种类型 —— 无缓冲通道与有缓冲通道,它们在并发编程中各具特点和应用场景。 一、通道的基本分类 类型定义形式特点无缓冲通道make(chan T)发送和接收都必须准备好࿰…...

Golang——6、指针和结构体
指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...
掌握 HTTP 请求:理解 cURL GET 语法
cURL 是一个强大的命令行工具,用于发送 HTTP 请求和与 Web 服务器交互。在 Web 开发和测试中,cURL 经常用于发送 GET 请求来获取服务器资源。本文将详细介绍 cURL GET 请求的语法和使用方法。 一、cURL 基本概念 cURL 是 "Client URL" 的缩写…...

消防一体化安全管控平台:构建消防“一张图”和APP统一管理
在城市的某个角落,一场突如其来的火灾打破了平静。熊熊烈火迅速蔓延,滚滚浓烟弥漫开来,周围群众的生命财产安全受到严重威胁。就在这千钧一发之际,消防救援队伍迅速行动,而豪越科技消防一体化安全管控平台构建的消防“…...

PydanticAI快速入门示例
参考链接:https://ai.pydantic.dev/#why-use-pydanticai 示例代码 from pydantic_ai import Agent from pydantic_ai.models.openai import OpenAIModel from pydantic_ai.providers.openai import OpenAIProvider# 配置使用阿里云通义千问模型 model OpenAIMode…...

如何把工业通信协议转换成http websocket
1.现状 工业通信协议多数工作在边缘设备上,比如:PLC、IOT盒子等。上层业务系统需要根据不同的工业协议做对应开发,当设备上用的是modbus从站时,采集设备数据需要开发modbus主站;当设备上用的是西门子PN协议时…...

【Zephyr 系列 16】构建 BLE + LoRa 协同通信系统:网关转发与混合调度实战
🧠关键词:Zephyr、BLE、LoRa、混合通信、事件驱动、网关中继、低功耗调度 📌面向读者:希望将 BLE 和 LoRa 结合应用于资产追踪、环境监测、远程数据采集等场景的开发者 📊篇幅预计:5300+ 字 🧭 背景与需求 在许多 IoT 项目中,单一通信方式往往难以兼顾近场数据采集…...
window 显示驱动开发-如何查询视频处理功能(三)
D3DDDICAPS_GETPROCAMPRANGE请求类型 UMD 返回指向 DXVADDI_VALUERANGE 结构的指针,该结构包含特定视频流上特定 ProcAmp 控件属性允许的值范围。 Direct3D 运行时在D3DDDIARG_GETCAPS的 pInfo 成员指向的变量中为特定视频流的 ProcAmp 控件属性指定DXVADDI_QUER…...
中国政务数据安全建设细化及市场需求分析
(基于新《政务数据共享条例》及相关法规) 一、引言 近年来,中国政府高度重视数字政府建设和数据要素市场化配置改革。《政务数据共享条例》(以下简称“《共享条例》”)的发布,与《中华人民共和国数据安全法》(以下简称“《数据安全法》”)、《中华人民共和国个人信息…...