【数据结构——单链表】本篇文章通过图文结合的方式能让你轻松的掌握单链表

链表的概念及结构

有了顺序表为什么还会出现链表呢？
链表和数组类似，但是功能比数组强大的多，数组的空间是固定的，在定义数组的时候空间大小就已经固定了，在使用时有可能会造成空间的浪费或者面临空间不够的风险，而链表的空间时动态的，则避免了这一问题。
概念
链表是一种物理上存储结构非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
线性表中的数据结点在内存中的位置是任意的，即逻辑上相邻的数据元素在物理位置（内存存储的位置）上不一定相邻。
链式存储结构的有优点

  • 空间利用率高需要一个空间就分配一个空间
  • 数据元素的逻辑次序靠节点的指针来指示，插入和删除时不需要移动数据结点，任意位置插入和删除时间复杂度为O（1）
    链式存储结构的缺点
  • 存储密度小，每个节点的指针域需要额外占用存储空间。当每个节点的数据域所占字节不多时，指针域所占空间比重显得很大，存储密度大空间利用率越大。
  • 链式存储结构时非随机存取结构，对任一节点的操作都要从头指针依次查找到该节点，算法复杂度比较高。
    链式存储的逻辑结构

从上图可以看出，链式结构在逻辑上是连续的，但是在物理上不一定连续，现实中的节点一般都是从堆上申请出来的。从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续。

链表的分类

实际中的链表的结构非常多样：
1.单向或者双向
在这里插入图片描述

上图就是单向和双向循环的逻辑图
2.带头或不带头
在这里插入图片描述

上图就是带头和不带头的逻辑图
在这里插入图片描述

上图就是循环和非循环的逻辑图
链表的基本组合：
在这里插入图片描述

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接等等。
  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是双向带头循环链表。另外这个结构虽然复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

链表的构成

链表是由一个个节点构成，每个节点一般采用结构体的形式组织，如下：

typedef int SLDataType;
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SListNode;

链表节点分为两个域
数据域：存放各种类型的实际数据。
指针域：存放下一节点的首地址。

链表的操作

链表最大的作用是通过节点把离散的数据链接在一起，组成一个表。链表有那些常规操作呢？有如下操作：尾插、头插、尾删、头删、查找、在pos位置之后插入、删除pos位置之后的值等操作。
下面我们就来慢慢的分析：

动态申请空间：

首先是让链表满的时候动态申请空间，这样就不需要我们自己去手动的管理了。
1.使用malloc来创建新的节点
2.在判断节点是否创建成功
3.在给节点赋值，并把节点中的指针置空
4.返回节点的指针
代码如下：

//动态的申请节点
SListNode* BuySListNode(SLDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode==NULL){perror("malloc");}newnode->data = x;newnode->next = NULL;return newnode;
}

在我们检验链表功能的时候，我们需要打印到屏幕上才能清楚我们写的链表功能是否成功。

单链表的打印：

1.首先判断指针是否是空指针
2.创建一个新的指针来指向结构体，目的就是使用这个指针来遍历
注意：一点不要使用头指针来遍历，这样会导致我们丢失数据的。
代码如下：

//链表的打印
void SListPrint(SListNode* plist)
{assert(plist);SListNode* cur = plist;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}

下图是整个遍历的过程：
在这里插入图片描述

注意：这里有个坑就是循环结束的条件，一定是创建的指针走到空结束，而不是指针指向的next为结束条件。

单链表的尾插：

首先我们要分情况，第一种就是传递过来的指针是空指针，第二种情况就是不是空指针的情况，着两种情况我们都要分别写代码。
1.首先我们新创建一个节点用来存储数据
2.在判断传递过来的指针是否是空指针
1）如果是空指针，那么我们直接返回新的节点
2）要是不是空指针，那么我们就创建一个新的指针来寻找尾节点
代码如下：

//单链表尾插
void SListPushBack(SListNode** pplist, SLDataType x)
{assert(pplist);SListNode* newnode = BuySListNode(x);if (*pplist==NULL){*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next!=NULL){tail = tail->next;}tail->next = newnode;}
}

下图是逻辑图：
在这里插入图片描述

注意：在寻找尾节点的时候要注意当next为空的时候那个节点就是位节点，所以我们使用tail->next来判断。

单链表的头插：

首先我们也要分三种情况：
第一种情况就是直接传递过来的指针是空指针，对于这种情况我直接使用断言来终止程序，
第二种情况就是传递过来的指针里面的内容是空，这种情况直接返回新的节点，
第三种情况就是我们传递过来的指针有指向的数据，那么我们直接插入节点就好了。
代码如下：
1.断言接收到的指针是否位空指针
2.创建一个新的节点，用来存储要插入的数据
3.要是接收到的指针内容为空那么直接返回新的节点
4.要是里面有链表那么直接插入

//单链表的头插
void SListPushFront(SListNode** pplist, SLDataType x)
{assert(pplist);SListNode* newnode = BuySListNode(x);if (*pplist==NULL){*pplist = newnode;}else{newnode->next = *pplist;*pplist = newnode;}
}

下图是头插的逻辑图：
在这里插入图片描述

注意： 在第三步的时候不要把
newnode->next = *pplist;
*pplist = newnode;
这两行代码写反了如果写反了会导致后面的数据丢失。

单链表的尾删：

要考虑的情况：
1.是否接收的指针是空指针
2.是否只有一个节点
3.多个节点
要是为空指针那么直接就终止程序，要是只有一个节点直接释放当前节点，并且把它的头节点置空，要是有多个节点的情况我们就需要找到最后一个节点和倒数第二个节点，我们在释放最后一个节点的时候，也要把倒数第二个节点置空，只有这样才能不导致倒数第二个指针变为也指针。

void SListPopBack(SListNode** pplist)
{assert(pplist);SListNode* prev = NULL;SListNode* tail = *pplist;// 1.空、只有一个节点// 2.两个及以上的节点if (tail == NULL || tail->next == NULL){free(tail);*pplist = NULL;}else{while (tail->next){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

下图是单链表的逻辑图：
在这里插入图片描述

注意：在第二种情况下一定要找到倒数第二个指针，不然容易造成野指针的错误。

单链表的头删：

要考虑的情况：
第一种：为空的情况
第二种：就是不为空的情况
代码如下：

//单链表的头删
void SListPopFront(SListNode** pplist)
{assert(pplist);//为空的情况assert(*pplist);//不为空的情况SListNode* newnode = (*pplist)->next;free(*pplist);*pplist = newnode;
}

下图是头删的逻辑图：
在这里插入图片描述

第一种情况就是为空的，对于这种情况我们直接断言终止程序；
第二种情况不为空的，对于这种情况我创建一个新的节点来保存 * pplist 指向的位置，然后再释放 * pplist
,最后再把第二个节点设置为头节点。

单链表查找：

要考虑的情况：
第一种：为空的情况
第二种：遍历完了也没有找到
第三种：找到了返回当前指针
代码如下：

//单链表查找
SListNode* SListFind(SListNode* plist, SLDataType x)
{assert(plist);SListNode* cur = plist;while (cur){if (cur->data==x){return cur;}cur = cur->next;}return NULL;
}

下图就是单链表的查找逻辑图：
在这里插入图片描述

对于为空的情况我直接就是使用断言来解决，要是找到了就返回当前节点的地址，要是没有找到就返回空。

单链表在pos之前插入数据：

要考虑的情况：
第一种：为空的情况
第二种：当pos的位置等于pplist的时候
第二种：就是正常的插入
代码如下：

// 在pos之前插入x
void SLTInsert(SListNode** pplist, SListNode* pos, SLDataType x)
{assert(pplist);assert(pos);if (pos==*pplist){//直接调用头插SListPushFront(pplist, x);}else{//创建新的指针来指向头SListNode* cur = *pplist;//创建新的节点来存储数据SListNode* newnode = BuySListNode(x);//当cur->next不等于pos的时候就继续循环while (cur->next!=pos){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}

下图是单链表在pos之前插入数据的逻辑图：
在这里插入图片描述

首先我使用的断言来判断指针是否为空，然后使用if来判断pos的位置是否等于pplist的位置，最后就是直接插入节点。

在pos位置之后插入数据：

这个比较简单，不需要考虑头尾的问题，只需要考虑，pos位置是否为空指针。
代码如下：

// 在pos以后插入x
void SLTInsertAfter(SListNode* pos, SLDataType x)
{assert(pos);//创建一个新的节点SListNode* newnode = BuySListNode(x);//当在中间插入的时候就需要这个步骤newnode->next=pos->next;pos->next = newnode;
}

下图是在pos位置之后插入数据的逻辑图：
在这里插入图片描述

删除pos位置的值：

第一种情况：当pos位置指向的是头的时候就直接调用头删
第二种情况：在尾和中间的时候，我们之间按照中间的处理方式处理就好了，因为在尾不需要特别处理。
代码如下：

void SLTErase(SListNode** pplist, SListNode* pos)
{assert(pplist);assert(pos);if (pos==*pplist){SListPopFront(pplist);}else{SListNode* pre = *pplist;while (pre->next!=pos){pre = pre->next;}pre->next = pos->next;free(pos);}
}

删除pos位置的数据的逻辑图：
在这里插入图片描述

单链表的销毁：

使用遍历的方式进行处理，边遍历边删除
代码如下：

 // 单链表的销毁
void SListDestroy(SListNode* plist)
{assert(plist);SListNode* del = plist;while (plist){plist = del;del = del->next;free(plist);}
}

总代码

#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"//动态的申请节点
SListNode* BuySListNode(SLDataType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode==NULL){perror("malloc");}newnode->data = x;newnode->next = NULL;return newnode;
}//链表的打印
void SListPrint(SListNode* plist)
{assert(plist);SListNode* cur = plist;while (cur){printf("%d->", cur->data);cur = cur->next;}printf("\n");
}//单链表尾插
void SListPushBack(SListNode** pplist, SLDataType x)
{assert(pplist);SListNode* newnode = BuySListNode(x);if (*pplist==NULL){*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next!=NULL){tail = tail->next;}tail->next = newnode;}
}//单链表的头插
void SListPushFront(SListNode** pplist, SLDataType x)
{assert(pplist);assert(pplist);SListNode* newnode = BuySListNode(x);if (*pplist==NULL){*pplist = newnode;}else{newnode->next = *pplist;*pplist = newnode;}
}
//单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(pplist);assert(*pplist);if ((*pplist)->next==NULL){free(*pplist);*pplist = NULL;}else{SListNode* tail = *pplist;//tail直接向后走两步这样可以避免使用第二个指针while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}//单链表的头删
void SListPopFront(SListNode** pplist)
{assert(pplist);//为空的情况assert(*pplist);//不为空的情况SListNode* newnode = (*pplist)->next;free(*pplist);*pplist = newnode;
}//单链表查找
SListNode* SListFind(SListNode* plist, SLDataType x)
{assert(plist);SListNode* cur = plist;while (cur){if (cur->data==x){return cur;}cur = cur->next;}return NULL;
}// 在pos之前插入x
void SLTInsert(SListNode** pplist, SListNode* pos, SLDataType x)
{assert((*pplist) && pos);if (pos==*pplist){SListPushFront(pplist, x);}else{SListNode* cur = *pplist;SListNode* newnode = BuySListNode(x);while (cur->next!=pos){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}// 在pos以后插入x
void SLTInsertAfter(SListNode* pos, SLDataType x)
{assert(pos);//创建一个新的节点SListNode* newnode = BuySListNode(x);//当在中间插入的时候就需要这个步骤newnode->next = pos->next;pos->next = newnode;
}//删除pos位置的值
void SLTErase(SListNode** pplist, SListNode* pos)
{assert(pplist);assert(pos);if (pos==*pplist){SListPopFront(pplist);}else{SListNode* pre = *pplist;while (pre->next!=pos){pre = pre->next;}pre->next = pos->next;free(pos);}
}// 单链表的销毁
void SListDestroy(SListNode* plist)
{assert(plist);SListNode* del = plist;while (plist){plist = del;del = del->next;free(plist);}
}

以上就是我关于数据结构中的单链表的细节问题和总结，下一篇博客我会写一篇关于单链表的力扣真题，并附上详细的讲解。

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.xdnf.cn/news/143100.html

如若内容造成侵权/违法违规/事实不符，请联系一条长河网进行投诉反馈，一经查实，立即删除！

相关文章

leetcode 23. 合并 K 个升序链表

leetcode 23. 合并 K 个升序链表

2023.9.25 本题要合并k个有序链表，最朴素的方法可以联想到之前做的合并两个有序链表。 用一个for循环遍历lists数组，利用合并两个有序链表的代码，不断合并lists中的链表，最后返回头节点即可。 代码如下： /*** Definit…
阅读更多...
目标分类笔记(二): 利用PaddleClas的框架来完成多标签分类任务（从数据准备到训练测试部署的完整流程）

目标分类笔记(二): 利用PaddleClas的框架来完成多标签分类任务（从数据准备到训练测试部署的完整流程）

文章目录 一、演示多分类效果二、PaddleClas介绍三、代码获取四、数据集获取五、环境搭建六、数据格式分析七、模型训练7.1 模型恢复训练7.2 多卡训练7.3 其他训练指标 八、模型预测九、模型评估十、PaddleClas相关博客 一、演示多分类效果 二、PaddleClas介绍 PaddleClas主要…
阅读更多...
PY32F003F18之RTC

PY32F003F18之RTC

一、RTC振荡器 PY32F003F18实时时钟的振荡器是内部RC振荡器，频率为32.768KHz。它也可以使用HSE时钟，不建议使用。HAL库提到LSE振荡器，但PY32F003F18实际上没有这个振荡器。 缺点：CPU掉电后，需要重新配置RTC&#xff…
阅读更多...
【深度学习】图像去噪（2）——常见网络学习

【深度学习】图像去噪（2）——常见网络学习

【深度学习】图像去噪 是在 【深度学习】计算机视觉 系列文章的基础上，再次针对深度学习（尤其是图像去噪方面）的基础知识有更深入学习和巩固。 1 DnCNN 1.1 网络结构 1.1.1 残差学习 1.1.2 Batch Normalization (BN) 1.1.2.1 背景和目标…
阅读更多...
java项目之人事管理系统（ssm源码+文档）

java项目之人事管理系统（ssm源码+文档）

项目简介 人事管理系统实现了以下功能： 管理员：个人中心、员工管理、部门经理管理、部门信息管理、员工考勤管理、签到管理、请假申请管理、工资查询管理、部门类型管理.部门经理：个人中心、员工管理、部门信息管理、员工考勤管理、签到管理…
阅读更多...
Baichuan2 技术报告笔记

Baichuan2 技术报告笔记

文章目录 预训练预训练数据模型架构TokenizerPositional EmbeddingsAcitivations and NormalizationsOptimizations 对齐Supervised Fine-TuningRLHF 安全性预训练阶段对齐阶段 参考资料 对Baichuan2技术报告阅读后的笔记 Baichuan2 与其他大模型的对比如下表 预训练 预训练数…
阅读更多...
【Linux】C语言实现对文件的加密算法

【Linux】C语言实现对文件的加密算法

异或加密 解密方式是进行第二次加密后自动解密 #define BUF_SIZE (16384) //16k /************************************************************** 功能描述: 加密实现 输入参数: --------------------------------------------------------------- 修改作者: 修改日期…
阅读更多...
山西电力市场日前价格预测【2023-09-27】

山西电力市场日前价格预测【2023-09-27】

日前价格预测 预测说明： 如上图所示，预测明日（2023-09-27）山西电力市场全天平均日前电价为342.48元/MWh。其中，最高日前电价为454.24元/MWh，预计出现在18: 30。最低日前电价为171.32元/MWh，预计…
阅读更多...
如何永久关闭WPS任务窗口？

如何永久关闭WPS任务窗口？

1、按住任务窗口上的浮动按钮，将其拖出来成悬浮窗口。 第二步，使用火绒弹窗拦截，选中弹出的窗口，进行拦截。注意：拦截次数为2次。即进行2次操作。 操作两次后，弹窗被拦截，此时Word文档改为双页显…
阅读更多...
蓝桥杯每日一题20223.9.26

蓝桥杯每日一题20223.9.26

4407. 扫雷 - AcWing题库 题目描述 分析 此题目使用map等都会超时，所以我们可以巧妙的使用哈希模拟散列表，哈希表初始化为-1首先将地雷读入哈希表，找到地雷的坐标在哈希表中对应的下标，如果没有则此地雷的位置第一次出现&#…
阅读更多...
QQ怎么上传大于1G的视频啊？视频压缩这样做

QQ怎么上传大于1G的视频啊？视频压缩这样做

当我们想要在QQ上分享一段大容量的视频时，往往会因为超过1G的限制而感到无助。不过，不用担心，今天我们将为你介绍三种可以压缩视频大小的方法，一起来看看吧~ 一、嗨格式压缩大师 嗨格式压缩大师是一款专业的视频压缩软件&#xf…
阅读更多...
全渠道客服体验：Rocket.Chat 的无缝互动 | 开源日报 No.41

全渠道客服体验：Rocket.Chat 的无缝互动 | 开源日报 No.41

RocketChat/Rocket.Chat Stars: 36.9k License: NOASSERTION Rocket.Chat 是一个完全可定制的开源通信平台，适用于具有高标准数据保护要求的组织。我们是团队沟通场景下的最终免费开源解决方案，可以实现同事之间、公司之间或客户之间的实时对话。提高生…
阅读更多...
13. ShardingSphere-Proxy 数据库代理

13. ShardingSphere-Proxy 数据库代理

Spring Cloud 微服务系列文章，点击上方合集↑ 1. 简介 ShardingSphere-Proxy是ShardingSphere分布式数据库中间件的一部分，它提供了数据库代理功能。通过引入ShardingSphere-Proxy，可以在无需改动应用程序代码的情况下，实现分库…
阅读更多...
使用Process Monitor工具探测日志文件是程序哪个模块生成的

使用Process Monitor工具探测日志文件是程序哪个模块生成的

目录 1、问题描述 2、使用Process Monitor监测目标文件是哪个模块生成的思路说明 3、操作Process Monitor监测日志文件是哪个模块生成的 4、通过screenctach.dll库的时间戳，找到其pdb文件，然后去查看详细的函数调用堆栈 5、最后 VC常用功能开发汇总…
阅读更多...
用智能文字识别技术赋能古彝文数字化之路

用智能文字识别技术赋能古彝文数字化之路

目录 1、前言 2、对古彝文古籍的保护迫在眉睫 3、古彝文识别的难点问题 4、古彝文文字识别的关键技术 4.1、智能高清滤镜技术 4.2、图像矫正 4.3、图像增强 4.4、版面还原 5、合合信息识别技术赋能古彝文数字化 1、前言 古彝文指的是在云南、贵州、四川等地的彝族人之…
阅读更多...
uniapp 可输入可选择的........框

uniapp 可输入可选择的........框

安装 uniapp: uni-combox地址 vue页面 <uni-combox :border"false" input"selectname" focus"handleFocus" blur"handleBlur" :candidates"candidates" placeholder"请选择姓名" v-model"name"&g…
阅读更多...
yolov5及yolov7实战之剪枝

yolov5及yolov7实战之剪枝

之前有讲过一次yolov5的剪枝&#xff1a;yolov5实战之模型剪枝_yolov5模型剪枝-CSDN博客 当时基于的是比较老的yolov5版本&#xff0c;剪枝对整个训练代码的改动也比较多。最近发现一个比较好用的剪枝库&#xff0c;可以在不怎么改动原有训练代码的情况下&#xff0c;实现剪枝的…
阅读更多...
使用自定义注解发布webservice服务

使用自定义注解发布webservice服务

使用自定义注解发布webservice服务 概要代码自定义注解WebService接口服务发布配置使用 结果 概要 在springboot使用webservice&#xff0c;发布webservice服务的时候&#xff0c;我们经常需要手动在添加一些发布的代码&#xff0c;比如&#xff1a; Bean public Endpoint or…
阅读更多...
破信息壁垒，亿发一站式ERP系统建设，打造五金制造信息管理平台

破信息壁垒，亿发一站式ERP系统建设，打造五金制造信息管理平台

五金制造拥有明显的行业特征&#xff0c;如体量小、品种繁多、颜色多样、加工工艺不断演进等&#xff0c;呈现出一种独特的管理挑战。大多数五金企业仍然依赖人工管理和经验决策&#xff0c;如今需要寻求更合理和科学的决策方法&#xff0c;以实现生产、销售、仓储、采购和财务…
阅读更多...
百度SEO优化技巧（选择、网站结构、内容优化、外链建设、数据分析）

百度SEO优化技巧（选择、网站结构、内容优化、外链建设、数据分析）

百度关键词SEO优化介绍 SEO是搜索引擎优化的缩写&#xff0c;是指通过优化网站结构、内容和外部链接等方式&#xff0c;提高网站在搜索引擎中的排名&#xff0c;从而获取更多的访问量和流量。百度是中国最大的搜索引擎之一&#xff0c;对于企业来说&#xff0c;优化百度关键词…
阅读更多...
最新文章

Copyright @ 2022~2023