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

数据结构之单链表(超详解)

在这里插入图片描述


在这里插入图片描述


文章目录

  • 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 链表的性质

  1. 链式机构在逻辑上是连续的,在物理结构上不一定连续;
  2. 结点⼀般是从堆上申请的;
  3. 从堆上申请来的空间,是按照⼀定策略分配出来的,每次申请的空间可能连续,可能不连续

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. 尾插、头插

创建结点

需要进行尾插,头插的操作首先需要创建结点
在这里插入图片描述

尾插

在尾插的时候需要考虑以下几点:

  1. 如果为空链表该如何处理
  2. 如何让两个结点相连
  3. 如何找到尾部结点
    在这里插入图片描述

在这里插入图片描述

头插

相比于尾插,头插不需要考虑链表是否为空的情况,因为只要让新的结点头插到NULL即可
在这里插入图片描述

4. 尾删、头删

尾删

进行尾删操作需要考虑以下因素:

  1. 链表是否为空,空的话不能进行尾删
  2. 遍历链表找到尾结点
  3. 保存尾结点的前一个结点
  4. 释放尾结点,让前一个结点指向NULL
    在这里插入图片描述
    在这里插入图片描述

头删

头删需要考虑以下因素:

  1. 链表是否为空
  2. 保存第二个有效结点
  3. 释放第一个有效结点,让pphead指向第二个有效结点
    在这里插入图片描述

5. 查找指定结点

在这里插入图片描述
在这里插入图片描述

6. 指定位置之前、之后插入数据

指定位置之前插入数据

  1. 链表是否为空
  2. 指定位置值的结点是否存在
  3. 如果指定位置的结点时头节点,则头插即可
  4. 遍历链表找到指定结点的前一个结点
    在这里插入图片描述

指定位置之后插入数据

在这里插入图片描述

7. 删除指定位置结点

  1. 链表是否为空
  2. 指定位置结点是否存在
  3. 指定位置结点是否是头结点
  4. 遍历链表找到pos结点的前一个结点
  5. 释放pos结点
    在这里插入图片描述

7.1 删除指定位置之后结点

在这里插入图片描述

8. 链表的销毁

在这里插入图片描述

9. 单链表代码实现

Slist.h
#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);

Slist.c
#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;
}

test.c
#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、冯诺依曼、操作系统速通指南

&#x1f31f; 快来参与讨论&#x1f4ac;&#xff0c;点赞&#x1f44d;、收藏⭐、分享&#x1f4e4;&#xff0c;共创活力社区。&#x1f31f; &#x1f6a9;用通俗易懂且不失专业性的文字&#xff0c;讲解计算机领域那些看似枯燥的知识点&#x1f6a9; 目录 前言 一…...

网络分析工具-tcpdump

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

基于AI边缘计算盒子的智慧零售场景智能监控解决方案

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

STM32G431收发CAN

1.硬件连接 PB8作为CAN_RX&#xff0c;PB9作为CAN_TX&#xff0c;连接一个CAN收发器TJA1051T/3 2. CubeMX里配置CAN 设置连接FDCAN1的参数&#xff0c;使用1个标准过滤器&#xff0c;波特率位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个节点&#xff0c;中间层36个节点&#xff0c;输出25个节点 class BP_36(nn.Module):def __init__(self):super(BP_36, self).__init__()self.fc1 nn.Linear(2, 36) # …...

2025年股指期货每月什么时候交割?

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

自从学会Git,感觉打开了一扇新大门

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

Ansys Discovery 中的网格划分方法:探索模式

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

关于 AWTK 和 Weston 在旋转屏幕时的资源消耗问题

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

grouped.get_group((‘B‘, ‘A‘))选择分组

1. df.groupby([team, df.name.str[0]]) df.groupby([team, df.name.str[0]]) 这一部分代码表示对 DataFrame df 按照 两个条件 进行分组&#xff1a; 按照 team 列&#xff08;即团队&#xff09;。按照 name 列的 首字母&#xff08;df.name.str[0]&#xff09;。 df.name.s…...

HTML——66.单选框

<!DOCTYPE html> <html><head><meta charset"UTF-8"><title>单选框</title></head><body><!--input元素的type属性&#xff1a;(必须要有)--> <!--单选框:&#xff08;如所住省会&#xff0c;性别选择&…...

Couchbase 和数据湖技术的区别、联系和相关性分析

Couchbase 和数据湖技术&#xff08;如 Delta Lake、Apache Hudi、Apache Iceberg&#xff09;分别是两类不同的数据存储与管理系统&#xff0c;但它们也可以在特定场景中结合使用&#xff0c;以下是它们的区别、联系和相关性分析&#xff1a; 区别&#xff1a; 1. 核心用途&a…...

springboot3 性能优化

Spring Boot 3 是基于 Spring Framework 6 的最新版本,支持 Java 17,并引入了多项改进,包括原生镜像支持、性能提升和现代化开发支持。以下是对 Spring Boot 3 应用进行全面优化的详细步骤: 一、开发环境优化 1. 使用最新版本 确保依赖版本为最新: Spring Boot 3.x。 J…...

C++之运算符重载详解篇

1.概念 重载概念&#xff1a; C 允许在同一作用域中的某个函数和运算符指定多个定义&#xff0c;分别称为函数重载和运算符重载。 运算符重载概念&#xff1a;对已有的运算符重新进行定义&#xff0c;赋予其另一种功能&#xff0c;以适应不同的数据类型 这里主要介绍…...

深度学习应用工程化中的节能减排最佳实践

文章大纲 简介为什么要在制造业节能减排能耗估算显卡能耗CPU 能耗树莓派能耗加速卡能耗硬件层面的改进边缘端硬件简介树莓派 + 加速卡软件层面的改进检测逻辑的改进算法层面改进深度学习模型训练,推理,量化的优化外网参考参考文献简介 为什么要在制造业节能减排 一、制造业…...

电脑文件msvcp110.d丢失的解决方法

电脑运行故障全解析&#xff1a;从文件丢失到系统报错&#xff0c;打造无忧使用环境 在数字化浪潮中&#xff0c;电脑作为我们工作、学习和娱乐的得力助手&#xff0c;其稳定运行至关重要。然而&#xff0c;在实际使用过程中&#xff0c;我们难免会遇到各种各样的问题&#xf…...

xdoj isbn号码

ISBN 号码 问题描述 每一本正式出版的图书都有一个 ISBN 号码与之对应&#xff0c;ISBN 码包括 9 位数字、1 位识别码和 3 位分隔符&#xff0c;其规定格式如"x-xxx-xxxxx-x"&#xff0c; 其中符号“-”是分隔符&#xff08;键盘上的减号&#xff09;&#xff0c;最…...

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为主配置文件&#xff0c;其他的为子配置&#xff0c;同时配置…...

网络编程(Modbus进阶)

思维导图 Modbus RTU&#xff08;先学一点理论&#xff09; 概念 Modbus RTU 是工业自动化领域 最广泛应用的串行通信协议&#xff0c;由 Modicon 公司&#xff08;现施耐德电气&#xff09;于 1979 年推出。它以 高效率、强健性、易实现的特点成为工业控制系统的通信标准。 包…...

生成 Git SSH 证书

&#x1f511; 1. ​​生成 SSH 密钥对​​ 在终端&#xff08;Windows 使用 Git Bash&#xff0c;Mac/Linux 使用 Terminal&#xff09;执行命令&#xff1a; ssh-keygen -t rsa -b 4096 -C "your_emailexample.com" ​​参数说明​​&#xff1a; -t rsa&#x…...

【Java_EE】Spring MVC

目录 Spring Web MVC ​编辑注解 RestController RequestMapping RequestParam RequestParam RequestBody PathVariable RequestPart 参数传递 注意事项 ​编辑参数重命名 RequestParam ​编辑​编辑传递集合 RequestParam 传递JSON数据 ​编辑RequestBody ​…...

IoT/HCIP实验-3/LiteOS操作系统内核实验(任务、内存、信号量、CMSIS..)

文章目录 概述HelloWorld 工程C/C配置编译器主配置Makefile脚本烧录器主配置运行结果程序调用栈 任务管理实验实验结果osal 系统适配层osal_task_create 其他实验实验源码内存管理实验互斥锁实验信号量实验 CMISIS接口实验还是得JlINKCMSIS 简介LiteOS->CMSIS任务间消息交互…...

基于Java+MySQL实现(GUI)客户管理系统

客户资料管理系统的设计与实现 第一章 需求分析 1.1 需求总体介绍 本项目为了方便维护客户信息为了方便维护客户信息&#xff0c;对客户进行统一管理&#xff0c;可以把所有客户信息录入系统&#xff0c;进行维护和统计功能。可通过文件的方式保存相关录入数据&#xff0c;对…...

【Redis】笔记|第8节|大厂高并发缓存架构实战与优化

缓存架构 代码结构 代码详情 功能点&#xff1a; 多级缓存&#xff0c;先查本地缓存&#xff0c;再查Redis&#xff0c;最后才查数据库热点数据重建逻辑使用分布式锁&#xff0c;二次查询更新缓存采用读写锁提升性能采用Redis的发布订阅机制通知所有实例更新本地缓存适用读多…...

Yii2项目自动向GitLab上报Bug

Yii2 项目自动上报Bug 原理 yii2在程序报错时, 会执行指定action, 通过重写ErrorAction, 实现Bug自动提交至GitLab的issue 步骤 配置SiteController中的actions方法 public function actions(){return [error > [class > app\helpers\web\ErrorAction,],];}重写Error…...

【自然语言处理】大模型时代的数据标注(主动学习)

文章目录 A 论文出处B 背景B.1 背景介绍B.2 问题提出B.3 创新点 C 模型结构D 实验设计E 个人总结 A 论文出处 论文题目&#xff1a;FreeAL: Towards Human-Free Active Learning in the Era of Large Language Models发表情况&#xff1a;2023-EMNLP作者单位&#xff1a;浙江大…...

【Linux应用】Linux系统日志上报服务,以及thttpd的配置、发送函数

【Linux应用】Linux系统日志上报服务&#xff0c;以及thttpd的配置、发送函数 文章目录 thttpd服务安装thttpd配置thttpd服务thttpd函数日志效果和文件附录&#xff1a;开发板快速上手&#xff1a;镜像烧录、串口shell、外设挂载、WiFi配置、SSH连接、文件交互&#xff08;RADX…...

【AI学习】wirelessGPT多任务无线基础模型摘要

收看了关于WirelessGPT多任务无线基础模型的演讲视频&#xff0c;边做一个记录。 应该说&#xff0c;在无线通信大模型的探索方面&#xff0c;有一个非常有益的尝试。 在沈学明院士带领下开展 https://www.chaspark.com/#/live/1125484184592834560...