数据结构之单链表详解（C语言手撕）

news/2024/7/26 21:04:05/文章来源:https://blog.csdn.net/2301_77509762/article/details/136551550

​
在这里插入图片描述

🎉个人名片：🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：GOTXX
🐼个人WeChat：ILXOXVJE
🐼本文由GOTXX原创，首发CSDN🎉🎉🎉
🐵系列专栏：零基础学习C语言----- 数据结构的学习之路----C++的学习之路
🐓每日一句：如果没有特别幸运，那就请特别努力！🎉🎉🎉
——————————————————————————————————————————————

🎉文章简介：

🎉本篇文章对      用C语言实现单链表   学习的相关知识进行分享！🎉💕
如果您觉得文章不错，期待你的一键三连哦，你的鼓励是我创作动力的源泉，让我们一起加油，一起奔跑，让我们顶峰相见！！！🎉🎉🎉
————————————————

一.链表的概念及结构

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

在这里插入图片描述从图片中可以看出，链表的每个节点都是一个结构体，该结构体中有一个存储数据的变量和一个指向下一节点的结构体指针；
在逻辑上是连续的，但是在物理空间上不一定连续，因为链表节点都是每次插入数据时在堆上申请出来的；每次申请出来的空间不一定是连续的；

二.无头单向非循环链表的结构

在这里插入图片描述无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等；

二.无头单向非循环链表的结构及实现

一.结构：

在这里插入图片描述

二.功能函数的实现（含性能分析与图解）
  1. 打印链表
  2. 创建节点函数
  3. 头插节点函数
  4. 头删节点函数
  5. 尾插节点函数
  6. 尾删节点函数
  7. 查找函数
  8. 在一节点位置之前插入一个节点
  9. 在一节点位置之后插入一个节点
  10. 在一节点位置之前删除一个节点
  11. 在一节点位置之后删除一个节点
打印链表

图解：遍历访问
在这里插入图片描述先定义一个结点指针指向头节点，往后依次遍历，与数组不同的是，不是cur++，而是让cur指向下一个节点，即cur=cur->next;

代码实现：

void SLPrint(SLNode* pphead)
{assert(pphead);     //断言SLNode* cur = pphead;     //让cur指向头节点进行遍历while (cur)        //注意：条件不是cur->next，因为如果是cur->next为空就不进入循环的话，则最后一个节点就访问不到{printf("%d ", cur->val);cur = cur->next;}printf("NULL");    //最后打印一个NULL、方便观察printf("\n");
}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

创建节点函数

代码实现：

SLNode* BuySLnewnode(SLDateType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));   //注意：创建的是节点，一个结构体，而不是一个数据类型if (newnode == NULL)          //判断{perror("malloc fail");exit(-1);             //开辟失败，以异常退出程序}newnode->next = NULL;     //下一个节点置NULLnewnode->val = x;         //赋值return newnode;           //返回该该结点指针
}
头插节函数

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

代码实现：

void SLPushFront(SLNode** pphead, SLDateType x)   
//注意：这里需要节点的二级指针，因为外面调用的时候，如果传的是头指针的话，是传值，
//函数里面改变不影响头指针的指向，所以这里需要二级指针，函数调用的时候需要传二级指针
{SLNode* newnode = BuySLnewnode(x);     //创建新节点if (*pphead == NULL)       //检查，如果为空链表{*pphead = newnode;      //直接将*pphead指向新节点}else{newnode->next = *pphead;    //第二种情况(*pphead) = newnode;}}

性能分析：
时间复杂度：O(1)
空间复杂度：O（1）

头删节点函数

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

代码实现：

void SLPopFront(SLNode** pphead)
{assert(*pphead);    //头指针不能为空if((*pphead)->next==NULL)     //第一种情况{free(*pphead);     *pphead = NULL;return;}SLNode* tmp = (*pphead)->next;   //保存下一个节点free(*pphead);*pphead = tmp;}

性能分析：
时间复杂度：O(1)
空间复杂度：O(1)

尾插节点函数

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

代码实现：

void SLPushBack(SLNode** pphead, SLDateType x)
{SLNode* newnode = BuySLnewnode(x);if (*pphead == NULL)     //空链表{ *pphead = newnode;return;}SLNode* tail = *pphead;     //定义一个尾指针while (tail->next){tail = tail->next;}                           //退出循环后tail->next为NULL；tail->next = newnode;       //链接}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

尾删节点函数

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

代码实现：

在这里插入代码片void SLPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL)   //第一种情况{free(*pphead);*pphead = NULL;return;}SLNode* Prevtail = *pphead;    //记录尾指针前面的一个节点SLNode* tail = *pphead;        //尾指针while (tail->next){Prevtail = tail;           tail = tail->next;}free(tail);             //释放掉尾节点Prevtail->next = NULL;   }

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

查找函数

代码实现：

SLNode* SLFind(SLNode* pphead, SLDateType x)
{assert(pphead);SLNode* cur = pphead;       //遍历查找while (cur){if (cur->val == x){return cur;      //返回节点指针} cur = cur->next;}return NULL;         //没找到，返回NULL
}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

在pos位置之前插入一个节点

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

代码实现：

//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{assert(*pphead);assert(pos);if (pos == *pphead)        //第一种情况：头插{SLPushFront(pphead, x);return;}SLNode* newnode = BuySLnewnode(x);     SLNode* cur = *pphead;     //遍历，找到pos的前一个节点while (cur->next){if (cur->next == pos)      //找到了{newnode->next = cur->next;    //链接cur->next = newnode;return;}cur = cur->next;}}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

在pos位置之后插入一个节点

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

代码实现：

//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x)
{assert(pos);SLNode * newnode = BuySLnewnode(x);     newnode->next = pos->next;   //链接pos->next = newnode;}

性能分析：

删除pos位置之前一个节点

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

代码实现：

//删除pos之前的节点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pos);assert(pos != *pphead);if (pos== (*pphead)->next)  //头删，第一种情况{free(*pphead);(*pphead) = pos;return;}SLNode* cur = *pphead;while (cur){if (cur->next->next == pos)   //找到pos前面的第二个节点{free(cur->next);cur->next = pos;     //链接return;}cur = cur->next;}}

性能分析：
时间复杂度：O(N)
空间复杂度：O(1)

删除pos位置之后一个节点

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

代码实现：

//删除pos之后的节点
void SLEraseAfter(SLNode* pos)
{assert(pos);assert(pos->next);   //当pos后无节点，无意义if (pos->next->next == NULL)   //尾删{pos->next = NULL;return;}SLNode* cur = pos->next->next;   free(pos->next);   pos->next = cur;   //链接cur = NULL;}

性能分析：
时间复杂度：O(1)
空间复杂度：O(1)

二.总代码

```cpp
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLDateType;typedef struct SListNode
{SLDateType val;struct SListNode* next;
}SLNode;SLNode* BuySLnewnode(SLDateType x);
void SLPrint(SLNode* pphead);void SLPushBack(SLNode** pphead, SLDateType x);
void SLPushFront(SLNode** pphead, SLDateType x);void SLPopFront(SLNode** pphead); 
void SLPopBack(SLNode** pphead);SLNode* SLFind(SLNode* pphead,SLDateType x);//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos,SLDateType x);//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x);//删除pos之后的节点
void SLEraseBack(SLNode* pos);//删除pos之前的节点
void SLErase(SLNode** pphead,SLNode* pos);

```cpp
#include"SList.h"SLNode* BuySLnewnode(SLDateType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->val = x;return newnode;
}void SLPrint(SLNode* pphead)
{assert(pphead);SLNode* cur = pphead;while (cur){printf("%d ", cur->val);cur = cur->next;}printf("NULL");printf("\n");
}void SLPushFront(SLNode** pphead, SLDateType x)
{SLNode* newnode = BuySLnewnode(x);if (*pphead == NULL){*pphead = newnode;}else{newnode->next = *pphead;(*pphead) = newnode;}}
void SLPushBack(SLNode** pphead, SLDateType x)
{SLNode* newnode = BuySLnewnode(x);if (*pphead == NULL){*pphead = newnode;return;}SLNode* tail = *pphead;while (tail->next){tail = tail->next;}tail->next = newnode;}void SLPopFront(SLNode** pphead)
{assert(*pphead);if((*pphead)->next==NULL){free(*pphead);*pphead = NULL;return;}SLNode* tmp = (*pphead)->next;free(*pphead);*pphead = tmp;}
void SLPopBack(SLNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;return;}SLNode* Prevtail = *pphead;SLNode* tail = *pphead;while (tail->next){Prevtail = tail;tail = tail->next;}free(tail);Prevtail->next = NULL;}
SLNode* SLFind(SLNode* pphead, SLDateType x)
{assert(pphead);SLNode* cur = pphead;while (cur){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//在pos之前插入
void SLInsert(SLNode** pphead, SLNode* pos, SLDateType x)
{assert(*pphead);assert(pos);if (pos == *pphead){SLPushFront(pphead, x);return;}SLNode* newnode = BuySLnewnode(x);SLNode* cur = *pphead;while (cur->next){if (cur->next == pos){newnode->next = cur->next;cur->next = newnode;return;}cur = cur->next;}}//在pos之后插入
void SLInsertBack(SLNode* pos, SLDateType x)
{assert(pos);SLNode * newnode = BuySLnewnode(x);newnode->next = pos->next;pos->next = newnode;}//删除pos之后的节点
void SLEraseBack(SLNode* pos)
{assert(pos);assert(pos->next);if (pos->next->next == NULL){pos->next = NULL;return;}SLNode* cur = pos->next->next;free(pos->next);pos->next = cur;cur = NULL;}//删除pos之前的节点
void SLErase(SLNode** pphead, SLNode* pos)
{assert(pos);assert(pos != *pphead);if (pos== (*pphead)->next){free(*pphead);(*pphead) = pos;return;}SLNode* cur = *pphead;while (cur){if (cur->next->next == pos){free(cur->next);cur->next = pos;return;}cur = cur->next;}}
三.性能分析

与顺序表相比：
优点：
1.按需申请，没有空间浪费；
2.头插头删效率高

缺点：
1.不支持下标随机访问
2.尾插尾删效率低

在这里插入图片描述

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

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

相关文章

【开源】SpringBoot框架开发数据可视化的智慧河南大屏

【开源】SpringBoot框架开发数据可视化的智慧河南大屏

目录 一、摘要1.1 项目介绍1.2 项目录屏 二、功能模块三、系统展示四、核心代码4.1 数据模块 A4.2 数据模块 B4.3 数据模块 C4.4 数据模块 D4.5 数据模块 E 五、免责说明 一、摘要 1.1 项目介绍 基于JAVAVueSpringBootMySQL的数据可视化的智慧河南大屏&#xff0c;包含了GDP、…
阅读更多...
连接kafka报错：java.io.IOException: Can‘t resolve address：

连接kafka报错：java.io.IOException: Can‘t resolve address：

修改电脑host文件:C:\Windows\System32\drivers\etc\hosts 加上一行 192.168.1.XXX MHA_SLAVE2&#xff08;192.168.1.XXX 这个是安装kafka 的服务器地址&#xff0c;MHA_SLAVE2是kafka的容器id&#xff09;
阅读更多...
【数据结构与算法】二分查找题解(二)

【数据结构与算法】二分查找题解(二)

这里写目录标题 一、81. 搜索旋转排序数组 II二、167. 两数之和 II - 输入有序数组三、441. 排列硬币四、374. 猜数字大小五、367. 有效的完全平方数六、69. x 的平方根 一、81. 搜索旋转排序数组 II 中等 已知存在一个按非降序排列的整数数组 nums &#xff0c;数组中的值不必…
阅读更多...
c++ 二分查找（迭代与递归）

c++ 二分查找（迭代与递归）

二分搜索被定义为一种在排序数组中使用的搜索算法&#xff0c;通过重复将搜索间隔一分为二。二分查找的思想是利用数组已排序的信息&#xff0c;将时间复杂度降低到O(log N)。 二分查找算法示例 何时在数据结构中应用二分查找的条件&#xff1a; 应用二分查找算法&#xff1a;…
阅读更多...
（C语言）sizeof和strlen的对比（详解）

（C语言）sizeof和strlen的对比（详解）

sizeof和strlen的对⽐&#xff08;详解&#xff09; 1. sizeof sizeof是用来计算变量所占内存空间大小的&#xff0c; 单位是字节&#xff0c;如果操作数是类型的话&#xff0c;计算的是用类型创建的变量所占空间的大小。 sizeof 只关注占用内存空间的大小 &#xff0c;不在乎内…
阅读更多...
Rust结构体讲解学习，以及impl结构体方法和结构体关联函数

Rust结构体讲解学习，以及impl结构体方法和结构体关联函数

Rust 中的结构体&#xff08;Struct&#xff09;与元组&#xff08;Tuple&#xff09;都可以将若干个类型不一定相同的数据捆绑在一起形成整体&#xff0c;但结构体的每个成员和其本身都有一个名字&#xff0c;这样访问它成员的时候就不用记住下标了。元组常用于非定义的多值传…
阅读更多...
表单提交 滚动到必填校验位置

表单提交 滚动到必填校验位置

handleCommit(flag) {this.$refs["form"].validate((valid, object) > {if (valid) {this.form.checkState flag;this.form.checkLevel 1;this.form.type 1; //规划this.form.filingsId this.form.id;checkFilings(this.form).then((response) > {this.$mo…
阅读更多...
list链表的创建，排序，插入， test ok

list链表的创建，排序，插入， test ok

1. 链表的建立&#xff0c;打印 #define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <stack> #include <iostream> #include <string.h> #include <string>using namespace std;struct node {int data;s…
阅读更多...
后量子时代，未来密码该何去何从？

后量子时代，未来密码该何去何从？

古有飞鸽&#xff0c;现有网络&#xff0c;在知识经济为基础的信息化社会中&#xff0c;保障网络信息安全无疑成为成为国与国之间无形的较量。小到个人通讯&#xff0c;大到机要信息传输&#xff0c;信息安全对于国家安全和经济活动正常运转至关重要。密码学作为保障网络与信息…
阅读更多...
Windows®、Linux® 和 UNIX® 系统都适用的远程桌面工具 OpenText ETX

Windows®、Linux® 和 UNIX® 系统都适用的远程桌面工具 OpenText ETX

Windows、Linux 和 UNIX 系统都适用的远程桌面工具 OpenText ETX 为 Windows、Linux 和 UNIX 实施精益、经济高效的虚拟化&#xff1b;提供完整的远程 Windows 可用性&#xff1b;以类似本地的性能远程工作&#xff1b;安全地保护系统和知识产权&#xff08;IP&#xff09;&am…
阅读更多...
什么是TikTok账号权重？打破TikTok0播放的方法

什么是TikTok账号权重？打破TikTok0播放的方法

许多TikTok账号运营者都会遇到一个难题&#xff0c;那就是视频要么播放量很低&#xff0c;要么0播放&#xff01;不管内容做的多好&#xff0c;最好都是竹篮打水一场空&#xff01;其实你可能忽略了一个问题&#xff0c;那就是账号权重。下面好好跟大家讲讲这个东西&#xff01…
阅读更多...
【kubernetes】关于k8s集群的配置资源（configmap和secret）

【kubernetes】关于k8s集群的配置资源（configmap和secret）

目录 一、Secret 类型一&#xff1a;kubernetes.io/service-account-token 类型二&#xff1a;普通类型secret&#xff0c; ●Opaque&#xff0c;base64 编码格式的 Secret&#xff0c;用来存储用户自定义的密码、密钥等&#xff0c;默认的 Secret 类型; 类型三&#xff1a;…
阅读更多...
【数据结构】二、线性表：6.顺序表和链表的对比不同（从数据结构三要素讨论：逻辑结构、物理结构（存储结构）、数据运算（基本操作））

【数据结构】二、线性表：6.顺序表和链表的对比不同（从数据结构三要素讨论：逻辑结构、物理结构（存储结构）、数据运算（基本操作））

文章目录 6.对比&#xff1a;顺序表&链表6.1逻辑结构6.2物理结构&#xff08;存储结构&#xff09;6.2.1顺序表6.2.2链表 6.3数据运算&#xff08;基本操作&#xff09;6.3.1初始化6.3.2销毁表6.3.3插入、删除6.3.4查找 6.对比&#xff1a;顺序表&链表 6.1逻辑结构 顺…
阅读更多...
管理技巧 | 提升团队效能：如何与下属进行有效沟通

管理技巧 | 提升团队效能：如何与下属进行有效沟通

本文节选霍格沃兹测试开发学社沟通管理公开课- 某外企PMO Angelia老师的分享 在日常的管理工作中&#xff0c;沟通作为一项基础而关键的技能&#xff0c;往往决定了团队的协作效率和目标达成率。作为一个曾经从基层员工一路成长为管理者的Angelia老师&#xff0c;深知沟通的艺术…
阅读更多...
jmap-各种option参数说明

jmap-各种option参数说明

基本情况 jmap&#xff08;JVM Memory Map&#xff09;&#xff1a;作用一方面是获取dump文件&#xff08;堆转储快照文件&#xff0c;二进制文件&#xff09;&#xff0c;它还可以获取目标Java进程的内存相关信息&#xff0c;包括Java堆各区域的使用情况、堆中对象的统计信息…
阅读更多...
国家妇女节放假是法定的假日

国家妇女节放假是法定的假日

在这个充满活力和希望的春天&#xff0c;我们迎来了一个特殊的节日——国家妇女节。这是一个属于所有女性的节日&#xff0c;是一个庆祝女性成就、关爱女性权益的时刻。在这个特殊的日子里&#xff0c;我们不禁要问&#xff1a;国家妇女节放假是法定假日吗&#xff1f;让我们一…
阅读更多...
ChatGPT数据分析应用——漏斗分析

ChatGPT数据分析应用——漏斗分析

ChatGPT数据分析应用——漏斗分析 ​ 漏斗分析在数据分析中也比较常用&#xff0c;主要是用于发现各个转化流程中哪个环节有问题。接下来我们让ChatGPT解释这个方法的概念并提供相应的案例。发送如下内容给ChatGPT。 ​ ChatGPT收到上述内容后&#xff0c;返回如下结果。 漏斗…
阅读更多...
MutationObserver详解

MutationObserver详解

1.基于之前Chrome游览器插件开发的过程中&#xff0c;会遇到在插件控制台打印被安游览器页面的元素&#xff0c;一直未解决。后来找到了解决了办法可以使用MutationObserver&#xff1b;使用MutationObserver这个可以在被安游览器页面直接打印页面元素等等&#xff0c;可能你会…
阅读更多...
【电路笔记】-RC网络-时间常数

【电路笔记】-RC网络-时间常数

时间常数 文章目录 时间常数1、概述2、RC 电路的时间常数3、示例14、示例25、RC瞬态放电曲线6、示例37、总结Tau τ \tau τ 是 RC 电路在阶跃变化输入条件下从一种稳态条件变为另一种稳态条件所需的时间常数。 1、概述 Tau，符号 τ \tau τ，是电气和电子计算中使用的希腊字…
阅读更多...
【翻译】零信任架构准则(五)Don‘t trust any network

【翻译】零信任架构准则(五)Don‘t trust any network

将监控重点放在用户&#xff0c;设备和服务上 全面监控必不可少&#xff0c;因为设备和服务更容易受到网络攻击。在零信任架构中&#xff0c;随着设备&#xff0c;服务和用户行为的持续评估&#xff0c;我们的监控策略很可能发生改变。我们应该持续进行监控&#xff0c;并将用…
阅读更多...
推荐文章
最新文章

Copyright @ 2022~2023

友情链接： 我的编程经验分享 一条长河网 尧图网站开发 尧图建网站 广利置业