单链表专题

单链表

  • 1. 链表的概念
  • 2. 链表的分类
  • 3. 实现无头单向非循环链表（单链表）
    • 3.1 单链表的声明
    • 3.2 单链表的打印
    • 3.3 尾插
    • 3.4 头插
    • 3.5 尾删
    • 3.6 头删
    • 3.7 查找
    • 3.8 在指定位置之前插入数据
    • 3.9 在指定位置之后插入数据
    • 3.10 删除指定节点
    • 3.11 销毁链表
  • 4. 一些细节
    • 4.1 指针与二级指针
    • 4.2 创建一个获取节点的函数
    • 4.3 单链表中可能需要分情况的点
    • 4.4改变结构的处理顺序

🔥 博客主页: 偷心编程
🎥 系列专栏: 《Java学习》 《C语言学习》 《数据结构C语言版》
❤️ 感谢大家点赞👍收藏⭐评论✍️
在这里插入图片描述
在这里插入图片描述

1. 链表的概念

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

  链表也是线性表的一种，特点是：物理上不连续，逻辑上连续。

在这里插入图片描述

2. 链表的分类

1. 单向或者双向

在这里插入图片描述

2. 带头或者不带头

在这里插入图片描述

3. 循环或者非循环

在这里插入图片描述

当然了我们最常用的还是下面两种结构：

在这里插入图片描述

3. 实现无头单向非循环链表（单链表）

3.1 单链表的声明

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

3.2 单链表的打印

//打印这个链表
void SListPrint(SListNode* phead) {if (!phead) {printf("NULL!链表为空!!!");return;}while (phead) {printf("%d ", phead->data);phead = phead->next;}
}

3.3 尾插

  1. 处理一般的单链表（链表不为空）
//尾插
void SListPushBack(SListNode* phead, SLTDataType x) {//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));newnode->data = x;newnode->next = NULL;//尾插，链表必须找尾SListNode* ptail = phead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;return;
}
  1. 考虑链表为空的情况

错误示范

//尾插
void SListPushBack(SListNode* phead, SLTDataType x) {//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);
}newnode->data = x;newnode->next = NULL;//处理空链表的情况if (!phead) {phead = newnode; //我们要改变第一个节点（指向NULL）里面的内容，但是这是传值调用，无法再main里面改变，因此要传递地址，所以最终是二级指针return ;}//尾插，链表必须找尾SListNode* ptail = phead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;return;
}

正确示范

//尾插
void SListPushBack(SListNode** pphead, SLTDataType x) {assert(pphead);//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);
}newnode->data = x;newnode->next = NULL;//处理空链表的情况if (!*pphead) {*pphead = newnode;return ;}//尾插，链表必须找尾SListNode* ptail = *pphead;while (ptail->next) {ptail = ptail->next;}ptail->next = newnode;return;
}//创建了节点(动态开辟了空间)就要给里面的元素初始化
/*SListNode* head = (SListNode*)malloc(sizeof(SListNode));
head->data = 2;
head->next = NULL;*/
//要么就不开辟空间
SListNode* head = NULL;

3.4 头插

  1. 可以跟尾插一样，分类讨论
//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {assert(pphead);//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//处理空链表的情况if (!*pphead) {*pphead = newnode;return;}//处理一般情况newnode->next = *pphead;*pphead = newnode;
}
  1. 也可以合并
//头插
void SListPushFront(SListNode** pphead, SLTDataType x) {assert(pphead);//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;newnode->next = *pphead;*pphead = newnode;
}

3.5 尾删

//尾删
void SListPopBack(SListNode** pphead) {assert(pphead);//处理链表为空的情况if (!*pphead) {printf("链表为空，无法删除！");return;}//处理只有一个节点的情况if (!((*pphead)->next)) {free(*pphead);*pphead = NULL;return;}//处理一般情况//找倒数第二个节点和最后一个节点SListNode* prev = *pphead;SListNode* ptail = *pphead;while (ptail->next) {prev = ptail;ptail = ptail->next;}free(ptail);ptail = NULL;prev->next = NULL;return;
}

3.6 头删

  1. 分类讨论
//头删
void SListPopFront(SListNode** pphead) {assert(pphead);//处理链表为空的情况if (!*pphead) {printf("链表为空，无法删除！");return;}//处理只有一个节点的情况if (!((*pphead)->next)) {free(*pphead);*pphead = NULL;return;}//处理一般情况SListNode* ptem = *pphead;*pphead = (*pphead)->next;free(ptem);ptem = NULL;
}
  1. 合并
//头删
void SListPopFront(SListNode** pphead) {assert(pphead);//处理链表为空的情况if (!*pphead) {printf("链表为空，无法删除！");return;}SListNode* ptem = *pphead;*pphead = (*pphead)->next;free(ptem);ptem = NULL;
}

3.7 查找


//查找
SListNode* SListFind(SListNode* phead, SLTDataType x) {while (phead) {if (phead->data == x) {return phead;}phead = phead->next;}printf("没有找到！");return NULL;
}

3.8 在指定位置之前插入数据

  1. 给的pos是int
//在指定位置之前插入数据（默认链表不为空）
void SListInsert(SListNode** pphead, int pos, SLTDataType x) {assert(pphead && (*pphead));//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//处理在第一个节点的情况（说明是头插）,关键在于没有第pos-1个节点，所以要分类讨论if (pos==1) {SListPushFront(pphead, x);return;}//处理一般情况//找到第pos-1个节点SListNode* prev = *pphead;int i;for (i = 0;i<pos-2; i++) {prev = prev->next;}newnode->next = prev->next;prev->next = newnode;
}
  1. 给的pos是一个指针
//在指定位置之前插入数据(默认链表不为空)
void SListInsert(SListNode** pphead, SListNode* pos, SLTDataType x) {assert(pphead && (*pphead));//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//处理在第一个节点的情况（说明是头插）,关键在于没有第pos-1个节点，所以要分类讨论if (pos==*pphead) {SListPushFront(pphead, x);return;}//处理一般情况//找到第pos-1个节点SListNode* prev = *pphead;while (prev->next != pos) {prev = prev->next;}newnode->next = prev->next;prev->next = newnode;
}

3.9 在指定位置之后插入数据

  1. 给的pos是int
//在指定位置之后插入数据(默认链表不为空)
void SListInsertAfter(SListNode** pphead, int pos, SLTDataType x) {assert(pphead && (*pphead));//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//适用所有情况//找到第pos个节点SListNode* prev = *pphead;int i;for (i = 0; i < pos - 1; i++) {prev = prev->next;}newnode->next = prev->next;prev->next = newnode;
}
  1. 给的pos是一个指针
//在指定位置之后插入数据(默认链表不为空)
void SListInsertAfter( SListNode* pos, SLTDataType x) {//创建一个新的节点用来接收新的数据SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (!newnode) {perror("malloc:");exit(1);}newnode->data = x;newnode->next = NULL;//适用所有情况//找到第pos个节点newnode->next = pos->next;pos->next = newnode;
}

3.10 删除指定节点

//删除pos节点(默认链表不为空)
void SListErase(SListNode** pphead, SListNode* pos) {//pos为第一个节点的情况if (pos == *pphead) {*pphead = pos->next;free(pos);pos = NULL;return;}//处理一般情况//找到第pos-1个节点SListNode* pcur = *pphead;while (pcur->next != pos) {pcur = pcur->next;}pcur->next = pos->next;free(pos);pos = NULL;
}//删除pos之后的节点
void SListEraseAfter(SListNode* pos) {SListNode* ptem = pos->next;pos = ptem->next;free(ptem);ptem = NULL;
}

3.11 销毁链表

//销毁链表
void SListDesTroy(SListNode** pphead) {//处理一般情况SListNode* pnext = (*pphead);while (pnext) {pnext = (*pphead)->next;free(*pphead);*pphead = pnext;}
}

4. 一些细节

4.1 指针与二级指针

  若是涉及到我们需要改变头节点，也就是要改变head指针的内容的时候，我们就要传入二级指针（涉及到“头”的改变就要传二级指针）

4.2 创建一个获取节点的函数

//获取一个新的节点
SListNode* getNode(SLTDataType x) {SListNode* node = (SListNode*)malloc(sizeof(SListNode));if (!node) {perror("malloc:");exit(1);}node->data = x;node->next = NULL;return node;
}

4.3 单链表中可能需要分情况的点

  1. 链表为空链表或者非空链表
  2. 单链表只能由前一个节点得到下一个节点，因此在增 、删的时候prev节点很重要。由于这个特性，我们常常要就处理第一个节点的时候进行讨论（没有prev节点，这时候直接改变头结点）

4.4改变结构的处理顺序

  我们在处理问题的时候，无论是单链表还是双向链表，我们总是先改变外部结构（新创建的节点里面的数据），然后再改变我们原本的内部结构（改变链表内部节点的next指向或者数据等等）

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

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

相关文章

K8S篇（基本介绍）

K8S篇（基本介绍）

目录 一、什么是Kubernetes&#xff1f; 二、Kubernetes管理员认证&#xff08;CKA&#xff09; 1. 简介 2. 考试难易程度 3. 考试时长 4. 多少分及格 5. 考试费用 三、Kubernetes整体架构 Master Nodes 四、Kubernetes架构及和核心组件 五、Kubernetes各个组件及功…
阅读更多...
中国500米分辨率逐月平均EVI数据集（2000-2022）

中国500米分辨率逐月平均EVI数据集（2000-2022）

EVI是在归一化植被指数&#xff08;NDVI&#xff09;的基础上进行改进的&#xff0c;通过卫星不同波段探测数据组合而成。EVI考虑了大气校正&#xff0c;包括大气分子、气溶胶、水汽和臭氧等因素&#xff0c;以解决NDVI容易饱和的问题。EVI的计算公式考虑了蓝光和红光波段&…
阅读更多...
二级列表联动

二级列表联动

介绍 本示例主要介绍了List组件实现二级联动&#xff08;Cascading List&#xff09;的场景。 该场景多用于商品种类的选择、照片不同类型选择等场景。 效果图 使用说明&#xff1a; 滑动二级列表侧控件&#xff08;点击没用&#xff09;&#xff0c;一级列表随之滚动。&…
阅读更多...
基于matlab的人民币面额识别

基于matlab的人民币面额识别

本文通过分析第五版人民币的特征&#xff0c;利用纸币中央数字的特征提取和识别的方法&#xff0c;通过matlab软件实现对第五版人民币的100元、50元和20元的识别。 Matlab函数介绍 Imread 函数imread用于读取图片文件中的数据。 调用格式&#xff1a; A imread(filename,…
阅读更多...
Docker篇（实际应用）

Docker篇（实际应用）

目录 一、MySQL 部署 1. 拉取 MySQL 镜像 2. 查看镜像 3. 创建 MySQL 容器 4. 进入 MySQL 容器,登陆 MySQL 5. 远程登陆 MySQL 6. 查看容器 IP 地址 二、tomcat 部署 1. 拉取 tomcat 镜像 2. 创建 tomcat 容器 3. 搭建 Tomcat 服务并部署 web 应用 三、Nginx 部署 …
阅读更多...
别名路径联想设置

别名路径联想设置

如何使用/进行路径提示&#xff1f; 找到jsconfig.json文件&#xff0c;如何项目中没有的话&#xff0c;自行创建 {"compilerOptions": {"paths": {"/*": ["./src/*"]}},"exclude": ["node_modules", "dis…
阅读更多...
osi七层模型

osi七层模型

文章目录 1、网络层1、数据链路层2、以太网和mac地址3、地址解析协议(arp)1、免费arp 4、物理层1、双绞线(网线) 5、总结 1、网络层 路由器就是网络层设备&#xff0c;因为是根据目标ip报文来实现转发的&#xff0c;三层的 1、数据链路层 作用 解决了&#xff0c;ip报文在链路…
阅读更多...
spark （算子 ） groupBykey+Map 和 reduceBykey 的区别

spark （算子 ） groupBykey+Map 和 reduceBykey 的区别

1&#xff09;面试题&#xff1a;groupByKeymap和reduceByKey都能实现分布式分组聚合&#xff0c;有什么区别&#xff1f; - groupByKey没有Map端聚合的操作&#xff0c;只做分组&#xff0c;必须等分区结束才能实现&#xff0c;最终map需要做整体聚合 - reduceByKey是有Map端聚…
阅读更多...
mysql--多表查询

mysql--多表查询

目录 一、联合查询 案例1&#xff0c;UNION 案例2&#xff0c;UNION ALL 二、表连接查询 &#xff08;一&#xff09;内连接 &#xff08;二&#xff09;外连接 1.左外连接 2.右外连接 3.全外连接 去重关键字 distinct 三、自连接 案例1&#xff1a; 案例2&…
阅读更多...
【MyBatis源码】CacheKey缓存键的原理分析

【MyBatis源码】CacheKey缓存键的原理分析

文章目录 Mybatis缓存设计缓存KEY的设计CacheKey类主体CacheKey组成CacheKey如何保证缓存key的唯一性 Mybatis缓存设计 MyBatis 每秒过滤众多数据库查询操作&#xff0c;这对 MyBatis 缓存键的设计提出了很高的要求。MyBatis缓存键要满足以下几点。 无碰撞&#xff1a;必须保证…
阅读更多...
打好“组合拳”，实现国有企业降本增效

打好“组合拳”，实现国有企业降本增效

打好“组合拳”&#xff0c;实现国有企业降本增效 在当前经济不确定性加剧、市场寒意明显的背景下&#xff0c;众多国有企业因历史积累的管理问题而陷入困境。随着经济形势的严峻&#xff0c;各行业普遍出现发展乏力的现象&#xff0c;促使企业开始重视“修炼内功”、“向内挖…
阅读更多...
金媒婚恋相亲系统10.4择爱开源旗舰版支持微信小程和抖音小程序上架

金媒婚恋相亲系统10.4择爱开源旗舰版支持微信小程和抖音小程序上架

最近大家应该注意到了&#xff0c;金媒婚恋相亲系统已经更新至最新的10.4版本了&#xff01;本人作为商业用户也已经更新至最新的旗舰版了&#xff0c;更新的内容是啥&#xff01;这个官方都有列出&#xff0c;一个方面就是更新了多端的登录逻辑和UI 和后台CRM及很多细节的优化…
阅读更多...
新能源行业必会基础知识-----电力现货市场理论篇-----电力现货市场组织-----配套措施

新能源行业必会基础知识-----电力现货市场理论篇-----电力现货市场组织-----配套措施

新能源行业必会基础知识-----电力现货市场理论篇-----主目录-----持续更新https://blog.csdn.net/grd_java/article/details/143364261 这本书是2023年出版的&#xff0c;是当下了解国内电力市场最好的途径了。还是推荐大家买来这本书进行阅读观看&#xff0c;最好作为随身携带…
阅读更多...
【开源免费】基于SpringBoot+Vue.JS周边产品销售网站（JAVA毕业设计）

【开源免费】基于SpringBoot+Vue.JS周边产品销售网站（JAVA毕业设计）

博主说明&#xff1a;本文项目编号 T 061 &#xff0c;文末自助获取源码 \color{red}{T061&#xff0c;文末自助获取源码} T061&#xff0c;文末自助获取源码 目录 一、系统介绍二、演示录屏三、启动教程四、功能截图五、文案资料5.1 选题背景5.2 国内外研究现状5.3 可行性分析…
阅读更多...
微服务day02

微服务day02

教学文档&#xff1a; 黑马教学文档 Docker Docker的安装 镜像和容器 命令解读 常见命令 案例 查看DockerHub&#xff0c;拉取Nginx镜像&#xff0c;创建并运行容器 搜索Nginx镜像&#xff1a;在 www.hub.docker.com 网站进行查询 拉取镜像&#xff1a; docker pull ngin…
阅读更多...
MySQL 安装与配置

MySQL 安装与配置

MySQL 安装与配置 MySQL 安装 MySQL 一般分为社区版和商业版&#xff0c;我们使用的是社区版&#xff08;因为免费&#xff09;。MySQL 安装的教程在网上有很多&#xff0c;此处就不再进行进行赘述&#xff0c;这里推荐两篇文章&#xff1a;如何在 Windows11 中安装 MySQL 8.…
阅读更多...
ISUP协议视频平台EasyCVR大华设备视频平台高并发情况下FLV协议流无法播放的原因排查

ISUP协议视频平台EasyCVR大华设备视频平台高并发情况下FLV协议流无法播放的原因排查

随着视频监控技术的发展和应用领域的扩大&#xff0c;大中型项目对视频监控系统的需求日益增长&#xff0c;特别是在智慧城市、公共安全、交通管理等领域。这些项目通常涉及跨区域、大规模的视频监控和管理&#xff0c;要求视频监控系统具备高兼容性、高稳定性和高扩展性。ISUP…
阅读更多...
Linux学习笔记之vim入门

Linux学习笔记之vim入门

基本介绍 Linux系统会内置vi文本编辑器&#xff0c;vim具有程序编辑的能力&#xff0c;可看做是vi的增强版本&#xff0c;可以主动以字体颜色辨别语法的正确性&#xff0c;方便程序设计。代码补全、编译以及错误跳转等方便编程的功能特别丰富&#xff0c;在程序员中被广泛使用…
阅读更多...
C# 实现读取Excel文件并设置单元格计算公式再保存

C# 实现读取Excel文件并设置单元格计算公式再保存

背景&#xff1a;需求需要读取数据导出成Excel文件&#xff0c;并且其中有一列需要赋值为公式&#xff0c;用于用户自己修改数据自动计算 导出Excel&#xff0c;我用到开源包MiniExcel Gitee地址MiniExcel源码介绍&#xff0c;功能说明 Nuget安装 搜索MiniExcel 导出代码如下&a…
阅读更多...
数学建模启发式算法篇（一）---遗传算法

数学建模启发式算法篇（一）---遗传算法

文章目录 1.引言2.生物学基础2.1适应度2.2染色体&#xff0c;基因 3.算法介绍3.1算法流程3.2编码和解码3.3轮盘赌选择3.4交叉和变异3.5初始参数的设置 4.实际应用-matlab4.1观察图像4.2初始参数说明4.3init初始化4.4二进制转换为十进制4.5选择,交叉过程4.6情况说明4.7代码 1.引…
阅读更多...
最新文章

Copyright @ 2022~2023