数据结构之单链表(超详解)
文章目录
- 1. 单链表
- 1.1 概念、结构
- 1.2 结点
- 1.2.1 链表的性质
- 2. 链表的打印
- 3. 尾插、头插
- 创建结点
- 尾插
- 头插
- 4. 尾删、头删
- 尾删
- 头删
- 5. 查找指定结点
- 6. 指定位置之前、之后插入数据
- 指定位置之前插入数据
- 指定位置之后插入数据
- 7. 删除指定位置结点
- 7.1 删除指定位置之后结点
- 8. 链表的销毁
- 9. 单链表代码实现
1. 单链表
1.1 概念、结构
链表也是线性表的一种。
概念:链表是⼀种物理存储结构上非连续、非顺序的存储结构,数据元素的逻辑顺序是通过链表中的指针链接次序实现的。(即链表在物理结构上不一定连续,在逻辑结构上一定连续)
1.2 结点
每节"车厢"都是独立申请下来的空间,我们称之为“节点/结点”。
结点的组成主要有两个部分:
1. 当前结点要保存的数据
2. 保存下⼀个结点的地址(指针变量)。
上图指针变量 plist保存的是第一个结点的地址,我们称plist此时“指向”第一个结点,如果我们希望plist“指向”第二个结点时,只需要修改plist保存的内容为0x0012FFA0。
链表中每个结点都是独立申请的(即需要插入数据时才去申请一块结点的空间),我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下一个结点。
对应实现结点的结构体代码:
1.2.1 链表的性质
- 链式机构在逻辑上是连续的,在物理结构上不一定连续;
- 结点⼀般是从堆上申请的;
- 从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续
2. 链表的打印
void SLTTest01()
{SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));node1->data = 1;SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));node2->data = 2;SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));node3->data = 3;SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));node4->data = 4;将4个节点连接起来node1->next = node2;node2->next = node3;node3->next = node4;node4->next = NULL;SLTPrint(plist);
}
显然我们每次都要一个接一个创建结点,并让结点连接起来过于麻烦。因此,我们可以考虑封装成一个函数,这个函数用来创建结点。
3. 尾插、头插
创建结点
需要进行尾插,头插的操作首先需要创建结点
尾插
在尾插的时候需要考虑以下几点:
- 如果为空链表该如何处理
- 如何让两个结点相连
- 如何找到尾部结点
头插
相比于尾插,头插不需要考虑链表是否为空的情况,因为只要让新的结点头插到NULL即可
4. 尾删、头删
尾删
进行尾删操作需要考虑以下因素:
- 链表是否为空,空的话不能进行尾删
- 遍历链表找到尾结点
- 保存尾结点的前一个结点
- 释放尾结点,让前一个结点指向NULL
头删
头删需要考虑以下因素:
- 链表是否为空
- 保存第二个有效结点
- 释放第一个有效结点,让pphead指向第二个有效结点
5. 查找指定结点
6. 指定位置之前、之后插入数据
指定位置之前插入数据
- 链表是否为空
- 指定位置值的结点是否存在
- 如果指定位置的结点时头节点,则头插即可
- 遍历链表找到指定结点的前一个结点
指定位置之后插入数据
7. 删除指定位置结点
- 链表是否为空
- 指定位置结点是否存在
- 指定位置结点是否是头结点
- 遍历链表找到pos结点的前一个结点
- 释放pos结点
7.1 删除指定位置之后结点
8. 链表的销毁
9. 单链表代码实现
#define _CRT_SECURE_NO_WARNINGS 1
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
//针对顺序表:中间/头部插入效率低下、增容降低运行效率、增容造成空间浪费
//因此有了单链表
//链表也是线性表的一种
//链表是由一个一-个的节点组成
//组成:数据 指向下一个节点的指针typedef int DataType;//可能存储整形,字符型等等typedef struct SlistNode
{DataType data;//节点数据struct SlistNode* next;//指向下一个节点的指针
}SLTNode;//链表的打印
void SLTPrint(SLTNode* phead);
//创建节点
SLTNode* SLTBuyNode(DataType x);
//尾插
void SLTPushBack(SLTNode** pphead, DataType x);
//头插
void SLTPushFront(SLTNode** pphead, DataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);
//查找
SLTNode* SLTFind(SLTNode* phead, DataType x);
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, DataType x);
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos后节点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SLTDesTroy(SLTNode** pphead);
#define _CRT_SECURE_NO_WARNINGS 1#include"Slist.h"//链表的打印
void SLTPrint(SLTNode* phead)
{SLTNode* pcur = phead;while (pcur){printf("%d->", pcur->data);pcur = pcur->next;}printf("NULL\n");
}
//创建节点
SLTNode* SLTBuyNode(DataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail!");exit(1);}//创建成功newnode->data = x;newnode->next = NULL;return newnode;
}
//尾插
void SLTPushBack(SLTNode** pphead, DataType x)
{assert(pphead);//空链表和非空链表SLTNode* newnode = SLTBuyNode(x);//如果是空链表if (*pphead == NULL){*pphead = newnode;}else {//找尾节点SLTNode* ptail = *pphead;while (ptail->next){ptail = ptail->next;}//ptail指向的就是尾节点ptail->next = newnode;}
}
//头插
void SLTPushFront(SLTNode** pphead, DataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);newnode->next = *pphead;*pphead = newnode;
}
//尾删
void SLTPopBack(SLTNode** pphead)
{//链表不能为空assert(pphead && *pphead);//链表只有一个节点if ((*pphead)->next == NULL) //-> 优先级高于*{free(*pphead);*pphead = NULL;}else {//链表有多个节点SLTNode* prev = *pphead;SLTNode* ptail = *pphead;while (ptail->next){prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;}
}
//头删
void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;
}
//查找
SLTNode* SLTFind(SLTNode* phead, DataType x)
{SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//pcur == NULLreturn NULL;
}
//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, DataType x)
{assert(pphead && *pphead);assert(pos);SLTNode* newnode = SLTBuyNode(x);//若pos == *pphead 说明是头插if (pos == *pphead){SLTPushFront(pphead, x);}else {SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}newnode->next = pos;prev->next = newnode;}
}
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, DataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//先连接后面在前面newnode->next = pos->next;pos->next = newnode;
}
//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//pos是头节点if (pos == *pphead){SLTNode* next = (*pphead)->next;free(*pphead);*pphead = next;}else{//pos不是头节点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos后节点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);SLTNode* del = pos->next;pos->next = del->next;free(del);del = NULL;
}
//销毁链表
void SLTDesTroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}//pcur为NULL*pphead = NULL;
}
#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"//链表是由一个一个的节点组成
//创建几个节点//第一个节点 *plist <---> **pphead
//指向第一个节点的指针 plist <---> *pphead
//指向第一个节点的指针的地址 &plist <---> pphead
void SLTTest01()
{//SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));//node1->data = 1;//SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));//node2->data = 2;//SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));//node3->data = 3;//SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));//node4->data = 4;//将4个节点连接起来//node1->next = node2;//node2->next = node3;//node3->next = node4;//node4->next = NULL;//调用链表的打印SLTNode* plist = NULL;SLTPushBack(&plist, 1);SLTPushBack(&plist, 2);SLTPushBack(&plist, 3);SLTPushBack(&plist, 4);SLTPushFront(&plist, 5);SLTPrint(plist);//SLTPopBack(&plist);//SLTPopBack(&plist);//SLTPopBack(&plist);SLTPopBack(&plist);SLTPopBack(&plist);//SLTPrint(plist);//SLTPopFront(&plist);//SLTPopFront(&plist);SLTPrint(plist);//测试查找SLTNode* find = SLTFind(plist, 5);if (find == NULL){printf("没有找到\n");}else {printf("找到了\n");}SLTInsert(&plist, find, 6);//SLTErase(&plist, find);//SLTEraseAfter(find);//SLTErase(&plist, find);SLTPrint(plist);SLTDesTroy(&plist);SLTPrint(plist);}int main()
{SLTTest01();return 0;
}
相关文章:

数据结构之单链表(超详解)
文章目录 1. 单链表1.1 概念、结构1.2 结点1.2.1 链表的性质 2. 链表的打印3. 尾插、头插创建结点尾插头插 4. 尾删、头删尾删头删 5. 查找指定结点6. 指定位置之前、之后插入数据指定位置之前插入数据指定位置之后插入数据 7. 删除指定位置结点7.1 删除指定位置之后结点8. 链表…...

告别编程困惑:GDB、冯诺依曼、操作系统速通指南
🌟 快来参与讨论💬,点赞👍、收藏⭐、分享📤,共创活力社区。🌟 🚩用通俗易懂且不失专业性的文字,讲解计算机领域那些看似枯燥的知识点🚩 目录 前言 一…...

网络分析工具-tcpdump
文章目录 前言一、tcpdump基础官网链接命令选项详解常规过滤规则tcpdump输出 一、tcpdump实践HTTP协议ICMP状态抓包 前言 当遇到网络疑难问题的时候,抓包是最基本的技能,通过抓包才能看到网络底层的问题 一、tcpdump基础 tcpdump是一个常用的网络分析工…...

基于AI边缘计算盒子的智慧零售场景智能监控解决方案
一、方案背景 随着零售业的快速发展,传统零售模式面临着诸多挑战,如人力成本高、管理效率低、顾客体验不佳等。智慧零售借助人工智能、物联网等技术手段,实现对零售场景的全面感知和智能管理。AI边缘计算盒子作为智慧零售的关键技术之一&…...

STM32G431收发CAN
1.硬件连接 PB8作为CAN_RX,PB9作为CAN_TX,连接一个CAN收发器TJA1051T/3 2. CubeMX里配置CAN 设置连接FDCAN1的参数,使用1个标准过滤器,波特率位500K 使能FDCAN1的中断 3 自动生成代码 3.1 初始化 static void MX_FDCAN1_In…...
如何得到深度学习模型的参数量和计算复杂度
1.准备好网络模型代码 import torch import torch.nn as nn import torch.optim as optim# BP_36: 输入2个节点,中间层36个节点,输出25个节点 class BP_36(nn.Module):def __init__(self):super(BP_36, self).__init__()self.fc1 nn.Linear(2, 36) # …...

2025年股指期货每月什么时候交割?
股指期货交割日是指期货合约到期时,买卖双方根据合约规定的指数价值进行现金结算的日期。在中国市场中,股指期货的交割日通常是合约到期月份的第三个星期五。这一规律适用于所有股指期货合约,无论是当月、下月合约,还是季度月合约…...

自从学会Git,感觉打开了一扇新大门
“同事让我用 Git 提交代码,我居然直接把项目文件压缩发过去了……”相信很多初学者都经历过类似的窘境。而当你真正掌握 Git 时,才会发现它就像一本魔法书,轻松解决代码管理的种种难题。 为什么 Git 能成为程序员的标配工具?它究…...

Ansys Discovery 中的网格划分方法:探索模式
本篇博客文章将介绍 Ansys Discovery 中可用于在探索模式下进行分析的网格划分方法。我们将在下一篇博客中介绍 Refine 模式下的网格划分技术。 了解 Discovery Explore 模式下的网格划分 网格划分是将几何模型划分为小单元以模拟系统在不同条件下的行为的过程。这是通过创建…...

关于 AWTK 和 Weston 在旋转屏幕时的资源消耗问题
关于 AWTK 和 Weston 在旋转屏幕时的资源消耗问题,首先需要理解这两者旋转的本质区别及其资源开销。 AWTK的屏幕旋转: AWTK旋转的实现方式: AWTK 是一个用户界面工具包,它通过图形渲染系统处理所有控件和窗口的旋转。当你使用 w…...

grouped.get_group((‘B‘, ‘A‘))选择分组
1. df.groupby([team, df.name.str[0]]) df.groupby([team, df.name.str[0]]) 这一部分代码表示对 DataFrame df 按照 两个条件 进行分组: 按照 team 列(即团队)。按照 name 列的 首字母(df.name.str[0])。 df.name.s…...

HTML——66.单选框
<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>单选框</title></head><body><!--input元素的type属性:(必须要有)--> <!--单选框:(如所住省会,性别选择&…...
Couchbase 和数据湖技术的区别、联系和相关性分析
Couchbase 和数据湖技术(如 Delta Lake、Apache Hudi、Apache Iceberg)分别是两类不同的数据存储与管理系统,但它们也可以在特定场景中结合使用,以下是它们的区别、联系和相关性分析: 区别: 1. 核心用途&a…...
springboot3 性能优化
Spring Boot 3 是基于 Spring Framework 6 的最新版本,支持 Java 17,并引入了多项改进,包括原生镜像支持、性能提升和现代化开发支持。以下是对 Spring Boot 3 应用进行全面优化的详细步骤: 一、开发环境优化 1. 使用最新版本 确保依赖版本为最新: Spring Boot 3.x。 J…...
C++之运算符重载详解篇
1.概念 重载概念: C 允许在同一作用域中的某个函数和运算符指定多个定义,分别称为函数重载和运算符重载。 运算符重载概念:对已有的运算符重新进行定义,赋予其另一种功能,以适应不同的数据类型 这里主要介绍…...
深度学习应用工程化中的节能减排最佳实践
文章大纲 简介为什么要在制造业节能减排能耗估算显卡能耗CPU 能耗树莓派能耗加速卡能耗硬件层面的改进边缘端硬件简介树莓派 + 加速卡软件层面的改进检测逻辑的改进算法层面改进深度学习模型训练,推理,量化的优化外网参考参考文献简介 为什么要在制造业节能减排 一、制造业…...

电脑文件msvcp110.d丢失的解决方法
电脑运行故障全解析:从文件丢失到系统报错,打造无忧使用环境 在数字化浪潮中,电脑作为我们工作、学习和娱乐的得力助手,其稳定运行至关重要。然而,在实际使用过程中,我们难免会遇到各种各样的问题…...
xdoj isbn号码
ISBN 号码 问题描述 每一本正式出版的图书都有一个 ISBN 号码与之对应,ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符,其规定格式如"x-xxx-xxxxx-x", 其中符号“-”是分隔符(键盘上的减号),最…...
qt的utc时间转本地时间
代码如下: #include <QCoreApplication> #include <QDateTime> #include <QDebug>int main(int argc...

mariadb变更数据存放目录
1、停止mariadb服务 # systemctl stop maraidb.server 2、创建数据目录 # mkdir /opt/mysql # chown -R mysql:mysql /opt/mysql 3、配置mariadb 3.1 配置文件说明 # cd /etc/mysql/ && ls -l my.cnf为主配置文件,其他的为子配置,同时配置…...
云原生核心技术 (7/12): K8s 核心概念白话解读(上):Pod 和 Deployment 究竟是什么?
大家好,欢迎来到《云原生核心技术》系列的第七篇! 在上一篇,我们成功地使用 Minikube 或 kind 在自己的电脑上搭建起了一个迷你但功能完备的 Kubernetes 集群。现在,我们就像一个拥有了一块崭新数字土地的农场主,是时…...
synchronized 学习
学习源: https://www.bilibili.com/video/BV1aJ411V763?spm_id_from333.788.videopod.episodes&vd_source32e1c41a9370911ab06d12fbc36c4ebc 1.应用场景 不超卖,也要考虑性能问题(场景) 2.常见面试问题: sync出…...

大话软工笔记—需求分析概述
需求分析,就是要对需求调研收集到的资料信息逐个地进行拆分、研究,从大量的不确定“需求”中确定出哪些需求最终要转换为确定的“功能需求”。 需求分析的作用非常重要,后续设计的依据主要来自于需求分析的成果,包括: 项目的目的…...

智慧工地云平台源码,基于微服务架构+Java+Spring Cloud +UniApp +MySql
智慧工地管理云平台系统,智慧工地全套源码,java版智慧工地源码,支持PC端、大屏端、移动端。 智慧工地聚焦建筑行业的市场需求,提供“平台网络终端”的整体解决方案,提供劳务管理、视频管理、智能监测、绿色施工、安全管…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

ESP32读取DHT11温湿度数据
芯片:ESP32 环境:Arduino 一、安装DHT11传感器库 红框的库,别安装错了 二、代码 注意,DATA口要连接在D15上 #include "DHT.h" // 包含DHT库#define DHTPIN 15 // 定义DHT11数据引脚连接到ESP32的GPIO15 #define D…...

深入理解JavaScript设计模式之单例模式
目录 什么是单例模式为什么需要单例模式常见应用场景包括 单例模式实现透明单例模式实现不透明单例模式用代理实现单例模式javaScript中的单例模式使用命名空间使用闭包封装私有变量 惰性单例通用的惰性单例 结语 什么是单例模式 单例模式(Singleton Pattern&#…...
Java 加密常用的各种算法及其选择
在数字化时代,数据安全至关重要,Java 作为广泛应用的编程语言,提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景,有助于开发者在不同的业务需求中做出正确的选择。 一、对称加密算法…...

Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决
Spring Cloud Gateway 中自定义验证码接口返回 404 的排查与解决 问题背景 在一个基于 Spring Cloud Gateway WebFlux 构建的微服务项目中,新增了一个本地验证码接口 /code,使用函数式路由(RouterFunction)和 Hutool 的 Circle…...

招商蛇口 | 执笔CID,启幕低密生活新境
作为中国城市生长的力量,招商蛇口以“美好生活承载者”为使命,深耕全球111座城市,以央企担当匠造时代理想人居。从深圳湾的开拓基因到西安高新CID的战略落子,招商蛇口始终与城市发展同频共振,以建筑诠释对土地与生活的…...