[初阶数据结构】单链表

前言 

📚作者简介：爱编程的小马，正在学习C/C++，Linux及MySQL。

📚本文收录于初阶数据结构系列，本专栏主要是针对时间、空间复杂度，顺序表和链表、栈和队列、二叉树以及各类排序算法，持续更新！

📚相关专栏C++及Linux正在发展，敬请期待！

目录

前言 

1. 链表

1.1 链表的定义 

1.2 链表与顺序表相比的好处

1.3 链表的结构表示

1.3.1 链表的结构形式

1.3.2 链表的结构性质

1.4 单链表的实现

1.4.1 单链表的创建

 1.4.2 单链表的打印

1.4.3 单链表的动态内存申请

1.4.4 单链表的头插

1.4.5 单链表的尾插

1.4.6 单链表的头删

 1.4.7 单链表的尾删

1.4.8 单链表的查找

1.4.9 单链表的任意位置插入的前插

1.4.10 单链表任意位置的删除

2.单链表的完整代码

2.1 test.c测试函数代码

2.2 SList.h函数声明代码

2.3 SList.c函数实现代码

总结

1. 链表

1.1 链表的定义 

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

本文只介绍最简单的链表结构：单链表

1.2 链表与顺序表相比的好处

1、顺序表从中间插入/头部插入，时间复杂度是O(N)，因为要一次往后挪动，但是单链表是O(1),大大节省了程序运行时间。

2、 顺序表每次需要增容，到后期增容很大的时候，需要拷贝数据、开辟新空间、释放旧空间。会有不小的损耗。链表直接开辟一个结构体大小的空间即可。

3、增容一般是两倍，但是我就想多插入几个仅此而已，会造成空间的大规模浪费。链表同样更加简单且占用空间小。

1.3 链表的结构表示

首先要给大家介绍一下，就是链表中的结点是一个结构体，结点中一个变量是存储数据的，另一个变量是存储结构体地址的，上一个结点存下一个结点的地址，从而链接起来。

1.3.1 链表的结构形式

1.3.2 链表的结构性质

1、从上图可以看出，链表在逻辑上是连续的，在物理地址上是不连续的

2、现实的结点是动态内存在堆区申请出来的

3、堆上申请的空间，是按照一定的规律来的，有些可能相同，有些可能不同。

1.4 单链表的实现

1.4.1 单链表的创建

上文我们提到了，结点是一个结构体，第一个结构体变量是存储数据的，第二个是存储下一个链表的地址的

typedef int SListDataType;typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;

 1.4.2 单链表的打印

void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL");
}

为什么是这样子打印的？给大家说一下思想：

1、单链表定义了最后一个链表的地址为空指针，所以我们就定义了一个cur来遍历整个链表

2、每找到一个数据我们就打印，然后遍历链表指针cur就往后走一步， 怎么走？是不是next中存放了下一个结点的地址，那么把cur管理的结构体中next的地址赋值给cur是不是相当于向后走了一步。

1.4.3 单链表的动态内存申请

SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}

 比方说，我想申请一块动态内存空间，里面存储x的值，那么这个时候，就通过malloc在堆上申请一块空间，交给newnode管理，这时候把newnode中data的值赋值为x，newnode中next的值赋值为NULL后返回这块空间的地址。这是不是就很好的开辟了一个结点。如果开辟失败了就返回空指针。

1.4.4 单链表的头插

void SListPushFront(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);assert(newnode);newnode->next = *pphead;*pphead = newnode;
}

这里我们用newnode来管理开辟的新结点，如果开辟了失败了就不用往下了，开辟成功了往下走，我画个图来帮助大家理解上面代码的意思

1.4.5 单链表的尾插

我先给大家介绍一下，尾插有两种情况，第一种空链表，第二种，非空链表

先分析第一种情况，如果是空链表，是不是直接把newnode的地址给pphead是不是就可以了，

第二种情况，我给大家画个图一起来分析

void SListPushBack(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);//空链表if (*pphead == NULL){*pphead = newnode;return;}//非空链表SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}

第二种情况，首先我们要尾插，是不是要先找尾部在哪里？尾部在哪里？是不是说tail->next是空指针，这个就是链表中最后一个元素了，找到了之后，就把tail->next存newnode的地址就可以。

1.4.6 单链表的头删

给大家说一下啊，如何删除单链表中的数？是不是只需要让上个结点存下下个结点的地址就好了。

那么头删就是让*pphead指向下下个结点，然后释放第一个结点就好了。 

那么，应该这么做，看代码

void SListPopFront(SLTNode** pphead)
{assert(*pphead);//链表只有一个值SLTNode* cur = *pphead;*pphead = cur->next;free(cur);cur = NULL;
}

画个图给大家理解一下：

 1.4.7 单链表的尾删

尾删就更简单了，还是第一步，找尾，第二部，释放空间即可。

void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}

1.4.8 单链表的查找

在单链表中查找一个数，找到了就返回这个结点的地址，没找到就返回空指针。

SLTNode* SListFind(SLTNode* pphead, SListDataType x)
{assert(pphead);SLTNode* cur = pphead;while (cur){if (cur->data == x)return cur;elsecur = cur->next;}return NULL;
}

1.4.9 单链表的任意位置插入的前插

void SListInsertbefore(SLTNode** pphead, SLTNode* pos, SListDataType x)
{if (*pphead == NULL){SListPushFront(pphead, x);}//在pos前插入else{SLTNode* newnode = BuySLTNode(x);SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}

首先啊，如果pphead没有值，那么就相当于头插，如果链表中有值，画个图给大家理解

1.4.10 单链表任意位置的删除

void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}

2.单链表的完整代码

2.1 test.c测试函数代码

#include "SList.h"
SLTNode* Phead = NULL;
void Test1()
{//该函数测试头插和尾插SListPushFront(&Phead, 1);SListPushFront(&Phead, 2);SListPushFront(&Phead, 3);SListPushFront(&Phead, 4);SListPushFront(&Phead, 5);SListPushBack(&Phead, 2);SListPushBack(&Phead, 3);SListPushBack(&Phead, 4);PrintSList(Phead);
}void Test2()
{//该函数测试头删和尾删SListPushFront(&Phead, 1);SListPopBack(&Phead);PrintSList(Phead);
}
void Test3()
{//查找SListPushFront(&Phead, 1);SListPushFront(&Phead, 2);SListPushFront(&Phead, 3);SListPushFront(&Phead, 4);SLTNode* find = SListFind(Phead, 3);if (find)find->data = 30;PrintSList(Phead);
}
void Test4()
{//任意位置插入（前插）SListPushFront(&Phead, 1);SListPushFront(&Phead, 2);SListPushFront(&Phead, 3);SListPushFront(&Phead, 4);SLTNode* find1 = SListFind(Phead, 3);SLTNode* find2 = SListFind(Phead, 4);if (find1){SListInsertbefore(&Phead, find1, 40);SListEraseafter(find2);SListEraseafter(find1);}PrintSList(Phead);
}
int main()
{Test1();//Test2();//Test3();//Test4();return 0;
}

2.2 SList.h函数声明代码

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SListDataType;typedef struct SListNode
{SListDataType data;struct SListNode* next;
}SLTNode;void PrintSList(SLTNode* phead);
//头插
void SListPushFront(SLTNode** pphead, SListDataType x);
//尾插
void SListPushBack(SLTNode** pphead, SListDataType x);
//头删
void SListPopFront(SLTNode** pphead);
//尾删
void SListPopBack(SLTNode** pphead);
//查找
SLTNode* SListFind(SLTNode* pphead, SListDataType x);
//在pos之后插入x
void SListInsertbefore(SLTNode** pphead,SLTNode* pos, SListDataType x);
//在pos之后插入x
void SListInsertafter(SLTNode* pos, SListDataType x);
//删除pos位置上的值
void SListErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的位置
void SListEraseafter(SLTNode* pos);

2.3 SList.c函数实现代码

#include "SList.h"
void PrintSList(SLTNode* phead)
{SLTNode* cur = phead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL");
}SLTNode* BuySLTNode(SListDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return NULL;}newnode->data = x;newnode->next = NULL;return newnode;
}
void SListPushFront(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);assert(newnode);newnode->next = *pphead;*pphead = newnode;
}	void SListPushBack(SLTNode** pphead, SListDataType x)
{SLTNode* newnode = BuySLTNode(x);//空链表if (*pphead == NULL){*pphead = newnode;return;}//非空链表SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}void SListPopFront(SLTNode** pphead)
{assert(*pphead);//链表只有一个值SLTNode* cur = *pphead;*pphead = cur->next;free(cur);cur = NULL;
}void SListPopBack(SLTNode** pphead)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next->next != NULL){cur = cur->next;}free(cur->next);cur->next = NULL;}
}SLTNode* SListFind(SLTNode* pphead, SListDataType x)
{assert(pphead);SLTNode* cur = pphead;while (cur){if (cur->data == x)return cur;elsecur = cur->next;}return NULL;
}
void SListInsertbefore(SLTNode** pphead, SLTNode* pos, SListDataType x)
{if (*pphead == NULL){SListPushFront(pphead, x);}//在pos前插入else{SLTNode* newnode = BuySLTNode(x);SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = newnode;newnode->next = pos;}
}void SListInsertafter(SLTNode* pos, SListDataType x)
{assert(pos);//只有一个SLTNode* newnode = BuySLTNode(x);newnode->next = pos->next;pos->next = newnode;
}void SListErase(SLTNode** pphead, SLTNode* pos)
{assert(*pphead);if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{SLTNode* cur = *pphead;while (cur->next != pos){cur = cur->next;}cur->next = pos->next;free(pos);pos = NULL;}
}void SListEraseafter(SLTNode* pos)
{assert(pos);assert(pos->next);SLTNode* cur = pos->next;pos->next = cur->next;free(cur);cur = NULL;
}

总结

1、单链表其实不难，大家一定要搞清楚指针和结构体

2、一定要动手实践一下

3、其实数据结构就是围绕着数据的增删查改显示这几个点，所以一定要搞清楚每一个代码实现的逻辑。

如果这份博客对大家有帮助，希望各位给小马一个大大的点赞鼓励一下，如果喜欢，请收藏一下，谢谢大家！！！
制作不易，如果大家有什么疑问或给小马的意见，欢迎评论区留言。

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

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

相关文章

k8s安装nginx Ingress超详细指南

k8s安装nginx Ingress超详细指南

在本全面的 Ingress 指南中&#xff0c;您将学习如何在 Kubernetes 上设置 Nginx Ingress控制器并使用 DNS 配置 Ingress。 目前有两种 Nginx Ingress 控制器。 kubernetes 社区的 Nginx Ingress 控制器Nginx Inc 开发的 Nginx Ingress 控制器 我们将使用 Kubernetes 社区 N…
阅读更多...
论文分享[cvpr2018]Non-local Neural Networks非局部神经网络

论文分享[cvpr2018]Non-local Neural Networks非局部神经网络

论文 https://arxiv.org/abs/1711.07971 代码https://github.com/facebookresearch/video-nonlocal-net 非局部神经网络 motivation:受计算机视觉中经典的非局部均值方法[4]的启发&#xff0c;非局部操作将位置的响应计算为所有位置的特征的加权和。 非局部均值方法 NLM&#…
阅读更多...
用keras识别狗狗

用keras识别狗狗

一、需求场景 从照片从识别出狗狗 from keras.applications.resnet50 import ResNet50 from keras.preprocessing import image from keras.applications.resnet50 import preprocess_input, decode_predictions import numpy as np# 加载预训练的ResNet50模型 model ResNet5…
阅读更多...
Flask-HTTP请求、响应、上下文、进阶实验

Flask-HTTP请求、响应、上下文、进阶实验

本节主要目录如下&#xff1a; 一、请求响应循环 二、HTTP请求 2.1、请求报文 2.2、Request对象 2.3、在Flask中处理请求 2.4、请求钩子 三、HTTP响应 3.1、响应报文 3.2、在Flask中生成响应 3.3、响应格式 3.4、Cookie 3.5、session&#xff1a;安全的Cookie 四、…
阅读更多...
【仪酷LabVIEW AI工具包案例】使用LabVIEW AI工具包+YOLOv5结合Dobot机械臂实现智能垃圾分类

【仪酷LabVIEW AI工具包案例】使用LabVIEW AI工具包+YOLOv5结合Dobot机械臂实现智能垃圾分类

‍‍&#x1f3e1;博客主页&#xff1a; virobotics(仪酷智能)&#xff1a;LabVIEW深度学习、人工智能博主 &#x1f384;所属专栏&#xff1a;『仪酷LabVIEW AI工具包案例』 &#x1f4d1;上期文章&#xff1a;『【YOLOv9】实战二&#xff1a;手把手教你使用TensorRT实现YOLOv…
阅读更多...
数据结构学习——线性表、顺序表

数据结构学习——线性表、顺序表

1.线性表 线性表 &#xff08; linear list &#xff09; 是n个具有相同特性的数据元素的有限序列。 线性表是一种在实际中广泛使 用的数据结构&#xff0c;常见的线性表&#xff1a;顺序表、链表、栈、队列、字符串… 线性表在逻辑上是线性结构&#xff0c;也就说是连续的一…
阅读更多...
项目管理-项目资源管理2/2

项目管理-项目资源管理2/2

项目管理&#xff1a;每天进步一点点~ 活到老&#xff0c;学到老 ヾ(◍∇◍)&#xff89;&#xff9e; 何时学习都不晚&#xff0c;加油 资源管理&#xff1a;6个过程“硅谷火箭管控” ①规划资源管理&#xff1a; 写计划 ②估算活动资源&#xff1a;估算团队资源&…
阅读更多...
渗透之sql盲注（时间/boolean盲注）

渗透之sql盲注（时间/boolean盲注）

sql盲注&#xff1a;sql盲注意思是我们并不能在web页面中看到具体的信息&#xff0c;我们只能通过输入的语句的真假来判断。从而拿到我们想要的信息。 我们通常使用ascii值来进行盲注。 目录 手动注入&#xff1a; 时间盲注&#xff1a; 布尔盲注&#xff1a; python脚本注…
阅读更多...
LabVIEW波浪发电平台浮筒取能效率数据采集系统

LabVIEW波浪发电平台浮筒取能效率数据采集系统

LabVIEW波浪发电平台浮筒取能效率数据采集系统 随着化石能源的逐渐减少以及能源价格的上升&#xff0c;寻找可替代的、可再生的、清洁的能源成为了世界各国的共识。波浪能作为一种重要的海洋能源&#xff0c;因其巨大的潜力和清洁性&#xff0c;近年来受到了广泛关注。开发了一…
阅读更多...
(六)JSP教程——out对象

(六)JSP教程——out对象

out对象是在JSP中经常使用到的对象&#xff0c;它本质上是一个输出流&#xff0c;前面已经多次使用&#xff0c;我们经常使用它的print()和println()方法&#xff0c;这些方法主要用于实现客户端数据的输出。通过out对象也可以直接向客户端发送一个由程序动态生成的HTML文件。 …
阅读更多...
Docker-Compose 容器集群的快速编排

Docker-Compose 容器集群的快速编排

Docker-compose 简介 Docker-Compose项目是Docker官方的开源项目&#xff0c;负责实现对Docker容器集群的快速编排。 Docker-Compose将所管理的容器分为三层&#xff0c;分别是 工程&#xff08;project&#xff09;&#xff0c;服务&#xff08;service&#xff09;以及容器&…
阅读更多...
JavaEE企业级开发中常用的JDK7和JDK8的时间类

JavaEE企业级开发中常用的JDK7和JDK8的时间类

JDK7时间类 全世界的时间有一个统一的计算标准 在同一条经线上的时间是一样的 格林威治时间 简称GMT 计算核心 地球自转一天是24小时 太阳直射正好是12小时 但是误差太大 现在用原子钟来代替 用铯原子震动的频率来计算时间&#xff0c;作为世界的标准时间UTC 中国标准时间…
阅读更多...
在国企分公司做信息宣传新闻投稿的经验分享

在国企分公司做信息宣传新闻投稿的经验分享

作为一名国企分公司的信息宣传工作者,我亲历了从传统投稿方式到数字化转型的全过程,这段经历既充满了挑战,也收获了成长。回首最初的日子,那些用邮箱投稿的时光,至今仍让我感慨万千。 初尝辛酸,邮箱投稿的艰难岁月 刚接手信息宣传工作时,我满腔热情,却很快被现实的冷水浇了个透…
阅读更多...
c语言实现贪吃蛇小游戏————附全代码！！！

c语言实现贪吃蛇小游戏————附全代码！！！

目录 1.Win32 API 1.1控制台应用程序 1.2控制台的名称&#xff0c;控制台窗口大小 1.3设置控制台光标位置 COORD - 光标坐标 GetStdHandle - 获取句柄 SetConsoleCursorPosition - 设置光标位置 封装一个设置光标的函数 1.4设置控制台光标的属性 CONSOLE_CURSOR_INFO …
阅读更多...
栈PART 1

栈PART 1

目录 1. 栈 1.1 栈的概念和结构 1.2 栈的实现 1.2.1 栈的顺序储存结构 1.2.2 栈的基本操作 1.3 有效的括号 1. 栈 1.1 栈的概念和结构 堆栈又名栈&#xff08;stack&#xff09;&#xff0c;它是一种运算受限的线性表。 限定仅在表尾进行插入和删除操作的线性表。这一端…
阅读更多...
C++进阶之路：深入理解编程范式，从面向过程到面向对象（类与对象_上篇）

C++进阶之路：深入理解编程范式，从面向过程到面向对象（类与对象_上篇）

✨✨ 欢迎大家来访Srlua的博文&#xff08;づ&#xffe3;3&#xffe3;&#xff09;づ╭❤&#xff5e;✨✨ &#x1f31f;&#x1f31f; 欢迎各位亲爱的读者&#xff0c;感谢你们抽出宝贵的时间来阅读我的文章。 我是Srlua小谢&#xff0c;在这里我会分享我的知识和经验。&am…
阅读更多...
java-函数式编程-语法

java-函数式编程-语法

目录 1、函数表现形式 分类 lambda表达式 参数类型可以全写&#xff0c;也可以全不写&#xff0c;但不能一部分写&#xff0c;一部分不写lambda 的省略策略&#xff1a;凡是可推导&#xff0c;都可以省略 方法引用 练习-判断语法正确性 练习-写出与方法引用等价的lambda表达式…
阅读更多...
TCP三次握手四次挥手 UDP

TCP三次握手四次挥手 UDP

TCP是面向链接的协议&#xff0c;而UDP是无连接的协议 TCP的三次握手 三次传输过程是纯粹的不涉及数据&#xff0c;三次握手的几个数据包中不包含数据内容。它的应用层&#xff0c;数据部分是空的&#xff0c;只是TCP实现会话建立&#xff0c;点到点的连接 TCP的四次挥手 第四…
阅读更多...
VMware虚拟机提示内存不足

VMware虚拟机提示内存不足

VMware虚拟机&#xff0c;k8s集群搭建内存不足的问题 疑问&#xff1a;我的电脑是8G8G双通道的内存&#xff0c;当我在搭建k8s集群时给master-2G内存&#xff0c;node1-3G内存&#xff0c;node2-3G内存&#xff1b; 当依次打开虚拟机到node2时VM提示“物理内存不足&#xff0c;…
阅读更多...
【大学物理】双语合集听课笔记

【大学物理】双语合集听课笔记

7.5 angular momentu(角动量)_哔哩哔哩_bilibili 6.4Energy in Rotation Motion 有质量有速度的物体有动能&#xff0c;是不是很有道理 international system&#xff08;from French systeme international&#xff0c;acronym&#xff0c;SI&#xff09;of ineria kg*m^2 转…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023