【数据结构七夕专属版】单链表及单链表的实现【附源码和源码讲解】

本篇是博主在学习数据结构时的心得，希望能够帮助到大家，也许有些许遗漏，但博主已经尽了最大努力打破信息差，如果有遗漏还请见谅，嘻嘻，前路漫漫，我们一起前进！！！！

今天是七夕！！！虽然博主没有女朋友，但是在此我也祝各位有情人终成眷属。爱永无止境。 

希望你们都能遇到自己的米子哈和大kin库！！！！！！！！！！！！！！！！！！！！！！！ 

 

目录

 1.单链表的简介

1.1结点

结点申请规则 

单链表和顺序表的对比 

2、单链表的实现及其对应源码：

2.1单链表的创建：

 2.2.链表的申请结点

 2.3.单链表的打印

2.4.链表的尾插

2.5. 链表的头插

2.6.链表的尾删

2.7.链表的头删

2. 8.链表的查找

2.9. 链表的指定位置前的结点插入

2.10. 在指定位置后插入结点

2.11.删除pos结点

2.12.销毁链表

 1.单链表的简介

链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的 指针链接次序实现的

1.1结点

链表中每个结点都是独⽴申请的（即需要插⼊数据时才去申请⼀块结点的空间），我们需要通过指针变量来保存下⼀个结点位置才能从当前结点找到下⼀个结点。

结点申请规则 

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

单链表申请空间：

struct SListNode
{
int data;
SListNode*next;
}

在我们想要存储一个整形数据时，实际先向内存申请一块空间，这个空间不仅要存放当前结点的数据，还存放着下一个结点的地址。（最后的结点存储的地址为NULL） 

单链表和顺序表的对比 

  1. 存储结构：
    单链表的存储结构是非连续，非顺序的依靠地址的来寻找链表中的下一位数据。
    顺序表在物理存储结构上是连续的，内存读取依次访问数据元素。
  2. 逻辑顺序：
    单链表的逻辑顺序是依靠结点相连接的，
    顺序标的逻辑顺序和物理顺序一样是紧挨着的。
     
  3. 代码实现：
    单链表的实现需要依靠指针，
    顺序表可以不用指针，用访问符就能访问到数据。
     
  4. 数据的存储：
    在顺序表中，只需要开辟一系列的相邻的一块空间进行数据的存储。
    在单链表中，每一个数据的位置都要申请，申请下来的空间叫做“结点”。

图解

2、单链表的实现及其对应源码：

单链表包括创建、申请结点、打印、头插、尾插、头删、尾删、链表查找、指定前插入、指定后插入、删除pos结点、删除pos后结点、销毁链表

单链表的实现 ：

2.1单链表的创建：

typedef int SLDataType
typedef struct SListNode
{
SLDataType  Data;
struct SListNode*next;
}sL;

以上代码是对链表结点结构的声明，该链表结点包括一个类型为SLDataType的整形数据和一个地址。

 

 2.2.链表的申请结点

SL*SLTButNode(SLTDataType x)
{
SL*newnode=(SL*)malloc(sizeof(SL));
if(newnode==NULL)
{
perror("malloc fail")；
exit(1);
}
newnode->data=x；
newnode->next=NULLl；
}

我们用图表示一下：

 2.3.单链表的打印

void SLprint(SL*phead)
{
SL*pucr=phead;
while(pcur)
{
printf("%d",pucr->next);}
printf("NULL/n");}

 这下我们用图解：

 这里有几个注意的点：

1.*phead一定是该链表中的第一个结点。

2.对pcur解引用拿到下一个结点的指针才能进入下一次循环，不然pcur走不动，打印陷入死循环。

2.4.链表的尾插

void SLTPushBack(SL**pphead,SLTDataType x)
{
assert(pphead);
SL*newnode=SLButNode(x);
if(*pphead==NULL)
{
*pphead=newnode;}
else
{SL*pcur=*pphead;
while(pcur->next)
{
pucr=pucr->next;
}
pcur->next=newnode;}

如果*pphead是NULL时，说明该链表的头结点还没有建立，所以如果从对一个没有头节点的链表进行尾插，头节点就是尾插的目标。

当*pphead不是NULL的时，代表要在链表结点之后插入,为了更直观的感受，我们用图解的方式来解释：

2.5. 链表的头插

void SLTPushFront(SL**pphead,SLDataType x)
{
assert(pphead&&*pphead);
SL*newnode=SLBuynode(x);newnode->next=*pphead;
*pphead=newnode;}

头插相较于尾插简单的多：

只要将先将头结点赋值给新的结点的存储地址，然后在再将新节点newnode当作新的头结点*pphead即可； 

2.6.链表的尾删

void SLTpopBack(SL**pphead)
{
//链表为空：不可以删除
assert(pphead && *pphead);
//处理只有一个结点的情况:要删除的就是头结点
if((*pphead)->next=NULL)
{
free(*pphead);
*pphead=NULL;
}
else
{
SL* ptail = *pphead;
SL* prev = NULL;
while (ptail->next)
{prev = ptail;ptail = ptail->next;
}
prev->next = NULL;
free(ptail);
ptail = NULL;}

这里我们还是用图解的方式来讲解：

尾删详解：这里用prev作为ptail的前一个指针，当ptail找到最后一个结点的时候，prev就是尾删的尾结点，所以先将prev的存储的下一个结点地址（prev->next）置为NULL，再将ptail所指的空间释放，最后ptail指向NULL，这就是尾删的过程

 

2.7.链表的头删

void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SL* next = (*pphead)->next;//*pphead --> nextfree(*pphead);*pphead = next;
}

这里头删就更加简单了，头结点就是要删除的结点，直接将头结点的指向的下一个结点的地址存储到next中，在进行释放头结点空间，最后在对新结点进行操作

2. 8.链表的查找

SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}

查找详解：

  1. 我们用pcur指针对单链表进行遍历，遍历过程中如果找到是否有与x匹配的数据，说明找到了，返回与x相等数据的pcur指针。
  2. 用pcur遍历完之后，如果没有找到与之匹配的数据，说明没有找到，返回NULL 。

2.9. 链表的指定位置前的结点插入

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);//找prev :pos的前一个结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev newnode --> posnewnode->next = pos;prev->next = newnode;}
}

插入（位置前）详解：

  1. 如果pos的位置在头结点，我们直接在头结点头插即可。
  2. 如果pos不在头结点，我们先创建一个新的结点，用prev指针找到pos的前一个结点的地址，pos的本质是一个地址，我们用将新节点存储的地址给pos，newnode的地址给到prev指针所指向结点的存储地址。这样我们就将新节点插入到了pos结点的前面 

2.10. 在指定位置后插入结点

void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode --> pos->nextnewnode->next = pos->next;pos->next = newnode;
}

插入（位置后）详解：

在指定位置后插入数据不需要用循环找pos后的位置了，因为pos所在的结点存储的地址就是下一个结点的地址，所以将pos存储的下一个结点的地址赋值给newnode的存储地址，之后再将pos的存储地址给newnode的地址，这样就完成了位置后插入。

2.11.删除pos结点

void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//头删if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}

删除pos结点详解： 

删除pos结点：用prev指针找到pos前一个结点的位置，用prev所在的结点的存储地址改为pos->next（pos后一个结点）。之后释放pos结点的空间，最后将pos指针置为NULL

删除pos之后的结点：用del代表pos的下一个结点，将pos的下下个结点的地址给pos的存储地址，释放del，将del指针置为NULL；

2.12.销毁链表

void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

超详细源码：

cpp文件：

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"
void SLprint(SLTNode*phead)
{SLTNode* pcur = phead;while (pcur){printf("%d", pcur->data);}printf("NULL/n");}
SLTNode* SLTBuyNode(SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if(newnode==NULL){perror("malloc fail");exit(1);}newnode->data = x;newnode->next = NULL;
}void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);if (pphead == NULL){*pphead = newnode;}else{//找尾结点SLTNode* pcur = *pphead;while (pcur->next){pcur = pcur->next;}//pcur  newnodepcur->next = newnode;
n	}
}
void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = SLTBuyNode(x);//newnode *ppheadnewnode->next = *pphead;*pphead = newnode;
}
void SLTPopBack(SLTNode** pphead)
{//链表为空：不可以删除assert(pphead && *pphead);//处理只有一个结点的情况:要删除的就是头结点	if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找 prev ptailSLTNode* ptail = *pphead;SLTNode* prev = NULL;while (ptail->next){prev = ptail;ptail = ptail->next;}prev->next = NULL;free(ptail);ptail = NULL;}}void SLTPopFront(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* next = (*pphead)->next;//*pphead --> nextfree(*pphead);*pphead = next;
}SLTNode* SLTFind(SLTNode* phead, SLTDataType x)
{assert(phead);SLTNode* pcur = phead;while (pcur){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{assert(pphead);assert(pos);if (pos == *pphead){SLTPushFront(pphead, x);}else{SLTNode* newnode = SLTBuyNode(x);//找prev :pos的前一个结点SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev newnode --> posnewnode->next = pos;prev->next = newnode;}
}
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x)
{assert(pos);SLTNode* newnode = SLTBuyNode(x);//pos newnode --> pos->nextnewnode->next = pos->next;pos->next = newnode;
}
//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos)
{assert(pphead && *pphead);assert(pos);//头删if (pos == *pphead){SLTPopFront(pphead);}else{SLTNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}//prev pos pos->nextprev->next = pos->next;free(pos);pos = NULL;}
}
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos)
{assert(pos && pos->next);//pos pos->next pos->next->nextSLTNode* del = pos->next;pos->next = pos->next->next;free(del);del = NULL;
}
//销毁链表
void SListDestroy(SLTNode** pphead)
{assert(pphead && *pphead);SLTNode* pcur = *pphead;while (pcur){SLTNode* next = pcur->next;free(pcur);pcur = next;}*pphead = NULL;
}

.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义链表（结点）的结构typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//插入
void SLTPushBack(SLTNode** pphead, SLTDataType x);//尾插
void SLTPushFront(SLTNode** pphead, SLTDataType x);//头插//删除
void SLTPopBack(SLTNode** pphead);
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插⼊数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插⼊数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos结点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的结点
void SLTEraseAfter(SLTNode* pos);
//销毁链表
void SListDestroy(SLTNode** pphead);

结束语： 

本篇单链表的章节到这里就结束了..........

感谢各位能观看到这里，感谢大家支持博主，很开心能和大家一起共同进步，一起学习！！！！！我希望能让更多的人看到这篇文章，希望大家能够多点赞，多交流。可以点波收藏，忘记的时候可以观看，在此wheel down先谢过大家！！！！！
 

时间漫长，我们一起度过，前路未知，我们一起并肩。 

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

超声波眼镜清洗机哪家强？盘点四款精品超声波清洗机机型

超声波眼镜清洗机哪家强？盘点四款精品超声波清洗机机型

超声波清洗机因其卓越的清洁能力&#xff0c;成为了家庭和专业环境中清洁小物件的理想选择。无论是日常佩戴的眼镜、珍贵的珠宝首饰&#xff0c;还是精密的电子设备和实验工具&#xff0c;超声波清洗机都能提供深层、温和且高效的清洁。然而&#xff0c;面对市场上众多品牌和价…
阅读更多...
原神4.8版本升级计划数据表

原神4.8版本升级计划数据表

原神4.8版本角色数据升级计划表 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-scale1.0"><title>原神4.8版本升级计划…
阅读更多...
使用Anaconda安装多个版本的Python并与Pycharm进行对接

使用Anaconda安装多个版本的Python并与Pycharm进行对接

1、参考链接 Anaconda安装使用教程解决多Python版本问题_anaconda安装多个python版本-CSDN博客 基于上面的一篇博客的提示&#xff0c;我做了尝试。并在Pycharm的对接上做了拓展。 2、首先安装Anaconda 这个比较简单&#xff0c;直接安装即可&#xff1a; 3、设置conda.exe的…
阅读更多...
【iOS】SideTable

【iOS】SideTable

目录 SideTablesStripedMapSideTable1. spinlock_t slock2. RefcountMap3. weak_table_t 总结 objc4源码地址&#xff1a; SideTable& table SideTables()[this]; // 获取对象的SideTable size_t& refcntStorage table.refcnts[this];SideTables 查源码SideTables…
阅读更多...
K8s第三节：k8s1.23.1升级为k8s1.30.0

K8s第三节：k8s1.23.1升级为k8s1.30.0

上回书说到我们使用了kubeadm安装了k8s1.23.1,但是在k8s1.24之前还是使用docker作为容器运行时&#xff0c;所以这一节我打算将我安装的k8s集群升级为1.30.0版本&#xff1b; 1、修改containerd 配置 因为我们安装的docker自带containerd&#xff0c;所以我们不需要重新安装con…
阅读更多...
docker拉取MySQL后数据库连接失败解决方案

docker拉取MySQL后数据库连接失败解决方案

如果数据库连接失败&#xff0c;检查以下几个地方&#xff1a; 1&#xff1a;防火墙&#xff0c;查看防火墙是否打开&#xff1a; systemctl status firewalld 关闭状态&#xff1a; 开启状态&#xff1a; 如果是开启状态&#xff0c;则很有可能是防火墙拦截掉了3306端口的访问…
阅读更多...
挖矿木马攻破了服务器

挖矿木马攻破了服务器

最近被国外的挖矿木马攻破了服务器 根据非法登录&#xff0c;用 #last指令查看登录ip 首先删掉登录主机 #kill -9 pts/0 第二步 #top 看看什么占用cpu高 第三步杀死狂刷CPU的服务 过一分钟后&#xff0c;服务又开始狂刷cpu。 第四步根据pid查到服务地址 #systemctl status…
阅读更多...
HarmonyOS Flex布局

HarmonyOS Flex布局

前置知识&#xff1a; 一次开发&#xff0c;多端部署:一套代码工程&#xff0c;一次开发上架&#xff0c;多端按需部署。支撑开发者快速高效的开发支持多种终端设备形态的应用&#xff0c;实现对不同设备兼容的同时&#xff0c;提供跨设备的流转、迁移和协同的分布式体验自适应…
阅读更多...
[FSCTF 2023]细狗2.0

[FSCTF 2023]细狗2.0

尝试输入cat /f* 输入&#xff1b;ls / 过滤了空格 输入 &#xff1b;ls 看到2个php, 空格绕过可以用注释替换空格 &#xff1b;ca\t/*123*/f* 发现不可以&#xff0c;看题解后发现使用${IFS}绕过 $IFS代替空格;$IFS、$IFS2、${IFS}、$IFS$9 Linux下有一个特殊的环境变量…
阅读更多...
Java 文件上传七牛云

Java 文件上传七牛云

Java系列文章目录 文章目录 Java系列文章目录一、前言二、学习内容&#xff1a;三、问题描述四、解决方案&#xff1a;4.1 新建空间4.2 查找密钥4.3 进入开发者中心查找JavaSDK文档4.4 查找文件上传方法4.5 运行测试 五、总结&#xff1a;5.1 学习总结&#xff1a; 一、前言 学…
阅读更多...
数据结构（其六）--树（一般的树）

数据结构（其六）--树（一般的树）

目录 1.树的知识总览 2.树的基本概念 i.部分名词 ii.结点间的关系 iii.属性 3.树的常考性质 i.结点数 ii.度为m的树 与 m叉树 的区别&#xff08;m>0&#xff09; iii.树的第 i 层的结点数&#xff08;i>1&#xff09; ​编辑 iiii. 高度为h的m叉树的结点数 iiiii.高…
阅读更多...
人工智能安全态势和趋势

人工智能安全态势和趋势

吴世忠 中工院士 国家保密科技委主任 重大风险隐患呼唤加强安全研究&#xff0c;人工智能面临未来担忧 1 总体态势 1.1 相对于技术发展&#xff0c;安全研究严重滞后 1.2 我国研究十分活跃&#xff0c;论文数量遥遥领先 1.3 影响力美国排名第一&#xff0c;大厂大学作用大 1…
阅读更多...
C#获取Network的相关信息

C#获取Network的相关信息

1&#xff0c;获取网络的通断。 //方法1&#xff1a;无效果&#xff0c;并不能反映当前网络通断 bool availableSystem.Windows.Forms.SystemInformation.Network//方法2&#xff1a;通过VB获取网络状态&#xff0c;可反映当前网络通断 Microsoft.VisualBasic.Devices.Network…
阅读更多...
高翔【自动驾驶与机器人中的SLAM技术】学习笔记（七）卡尔曼滤波器三：卡尔曼滤波器公式推导【转载】

高翔【自动驾驶与机器人中的SLAM技术】学习笔记（七）卡尔曼滤波器三：卡尔曼滤波器公式推导【转载】

卡尔曼滤波器三&#xff1a;卡尔曼公式推导 转载来源&#xff1a;卡尔曼滤波&#xff1a;从入门到精通 简述 考虑一个SLAM 问题&#xff0c;它由一个运动方程&#xff1a; x t f ( x t − 1 , u t ) ω t (1) \mathbf{x}_{t}f(\mathbf{x}_{t-1},\mathbf{u}_{t}) \omega_…
阅读更多...
在国产芯片上实现YOLOv5/v8图像AI识别-【2.3】RK3588上使用C++启用多线程推理更多内容见视频

在国产芯片上实现YOLOv5/v8图像AI识别-【2.3】RK3588上使用C++启用多线程推理更多内容见视频

本专栏主要是提供一种国产化图像识别的解决方案&#xff0c;专栏中实现了YOLOv5/v8在国产化芯片上的使用部署&#xff0c;并可以实现网页端实时查看。根据自己的具体需求可以直接产品化部署使用。 B站配套视频&#xff1a;https://www.bilibili.com/video/BV1or421T74f 基础…
阅读更多...
算法（数组+链表）

算法（数组+链表）

37.移除元素 数组的删除其实是元素的覆盖 比如刚开始五个元素删除了一个 他变成了四个元素 但是他的空间大小还是五 删除元素是o&#xff08;n&#xff09;erase的时间复杂度是o&#xff08;n&#xff09; 暴力实现 当使用两层for循环去删除元素的时候 比如要删除元素三 …
阅读更多...
JNPF快速开发平台助力企业实现工作流自动化

JNPF快速开发平台助力企业实现工作流自动化

随着企业信息化建设的不断深入&#xff0c;工作流自动化已成为提升企业效率、优化业务流程的关键手段。JNPF快速开发平台凭借其强大的功能和灵活的配置&#xff0c;为众多企业提供了实现工作流自动化的高效解决方案。 关于低代码开发平台的普及应用 随着信息技术的迅猛发展&…
阅读更多...
WEB中间件TomCat详解

WEB中间件TomCat详解

一、JVM 虚拟机常识 1、什么是JAVA虚拟机 所谓虚拟机&#xff0c;就是一台虚拟的计算机。在计算机系统上模拟运行一个完整的计算机系统的技术&#xff0c;他是一款软件&#xff0c;用来执行一系列虚拟计算机指令。大体上&#xff0c;虚拟机可以分为系统虚拟机和程序虚拟机。大…
阅读更多...
自闭症学校康复寄宿：点亮每个孩子的希望——星贝育园

自闭症学校康复寄宿：点亮每个孩子的希望——星贝育园

在繁华都市的一角&#xff0c;有一座充满爱与希望的城堡——星贝育园&#xff0c;这是一所专门为自闭症儿童提供康复寄宿服务的学校。它宛如黑暗中的一盏明灯&#xff0c;为那些迷失在孤独世界里的孩子们照亮了前行的道路&#xff0c;点亮了他们内心深处的希望之光。 走进星贝育…
阅读更多...
流编程思想

流编程思想

流编程思想 程序可以看作流&#xff0c;任何程序执行的过程都可以看成是流动的过程。基于这个思想&#xff0c;我们可以将程序划分为数据流与控制流。 数据流是数据实现的过程&#xff0c;对于相同的任务需求&#xff0c;最终数据流都会流向相同的地方&#xff0c;笔者进行举…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023