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

​
在这里插入图片描述

🎉个人名片：🐼作者简介：一名乐于分享在学习道路上收获的大二在校生
🙈个人主页🎉：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.rhkb.cn/news/271501.html

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

相关文章

前端实现单点登录

前端实现单点登录

简单概括就是&#xff0c;一个系统登录&#xff0c;跳转多个系统&#xff0c;其他系统不需要再登录&#xff0c;直接进入页面 登录的系统 <template><div><div class"content"><div class"item" v-for"(item,index) in list&q…
阅读更多...
使用Echarts绘制中国七大区地图

使用Echarts绘制中国七大区地图

先上效果图&#xff08;文字是否显示&#xff0c;显示什么字&#xff0c;各种颜色之类的&#xff0c;都能随便改&#xff09; 直接上完整代码 <!DOCTYPE html> <html style"height: 100%"><head><meta charset"utf-8" /></hea…
阅读更多...
windows安装Chocolatey方法注意事项，以及安装openssl方法

windows安装Chocolatey方法注意事项，以及安装openssl方法

chock是一个很强大的软件包管理工具官方&#xff1a;Chocolatey Software | Installing Chocolatey 使用管理员打开powershell工具&#xff1a; 必须以管理员打开&#xff0c;不然安装失败&#xff0c;提示没有权限 然后输入&#xff1a; Get-ExecutionPolicy 如果返回&…
阅读更多...
20个Python函数程序实例

20个Python函数程序实例

前面介绍的函数太简单了&#xff1a; 以下是 20 个不同的 Python 函数实例 下面深入一点点&#xff1a; 以下是20个稍微深入一点的&#xff0c;使用Python语言定义并调用函数的示例程序&#xff1a; 20个函数实例 简单函数调用 def greet():print("Hello!")greet…
阅读更多...
JVM-对象创建与内存分配机制深度剖析 3

JVM-对象创建与内存分配机制深度剖析 3

JVM对象创建过程详解 类加载检查 虚拟机遇到一条new指令时&#xff0c;首先将去检查这个指令的参数是否能在常量池中定位到一个类的符号引用&#xff0c;并且检查这个 符号引用代表的类是否已被加载、解析和初始化过。如果没有&#xff0c;那必须先执行相应的类加载过程。 new…
阅读更多...
“2024杭州智慧城市及安防展会”将于4月在杭州博览中心盛大召开

“2024杭州智慧城市及安防展会”将于4月在杭州博览中心盛大召开

2024杭州国际智慧城市及安防展览会&#xff0c;将于4月24日在杭州国际博览中心盛大开幕。这场备受瞩目的盛会&#xff0c;不仅汇集了全球智慧城市与安防领域的顶尖企业&#xff0c;更是展示最新技术、交流创新理念的重要平台。近日&#xff0c;从组委会传来消息&#xff0c;展会…
阅读更多...
Qt+FFmpeg+opengl从零制作视频播放器-1.项目介绍

Qt+FFmpeg+opengl从零制作视频播放器-1.项目介绍

1.简介 学习音视频开发&#xff0c;首先从做一款播放器开始是比较合理的&#xff0c;每一章节&#xff0c;我都会将源码贴在最后&#xff0c;此专栏你将学习到以下内容&#xff1a; 1&#xff09;音视频的解封装、解码&#xff1b; 2&#xff09;Qtopengl如何渲染视频&#…
阅读更多...
PythonWeb

PythonWeb

例题一 from flask import Flask app Flask(__name__) app.route(/index) def index():return f<h1>这是首页&#xff01;</h1> def second():return f<h1>这是第二页&#xff01;</h1> if __name__ __name__:app.run(host"0.0.0.0",port…
阅读更多...
TypeScript 基础（一）

TypeScript 基础（一）

目录 一、概述 二、开发环境 三、数据类型 1.boolean 2.number 3.string 4.Array 5.type 6.tuple 7.enum 8.any 9.null / undefined 10.never 11.object 结束 一、概述 TypeScript 是一种由微软开发的开源编程语言。它是 JavaScript 的一个超集&#xff0c;这意…
阅读更多...
HTML静态网页成品作业(HTML+CSS)——电影网首页网页设计制作(1个页面)

HTML静态网页成品作业(HTML+CSS)——电影网首页网页设计制作(1个页面)

&#x1f389;不定期分享源码&#xff0c;关注不丢失哦 文章目录 一、作品介绍二、作品演示三、代码目录四、网站代码HTML部分代码 五、源码获取 一、作品介绍 &#x1f3f7;️本套采用HTMLCSS&#xff0c;未使用Javacsript代码&#xff0c;共有1个页面。 二、作品演示 三、代…
阅读更多...
场景问题： VisualVM工具Profiler JDBC不是真实执行的SQL

场景问题： VisualVM工具Profiler JDBC不是真实执行的SQL

1. 问题 诡异的问题表象&#xff1a; 前端反馈分页接口的Total字段一直为0 使用Visualvm中的 Profiler 注入到应用后&#xff0c;查看JDBC监控得到了分页接口执行的SQL&#xff0c;复制出来执行是55. 此时还没有注意到 IN 的范围中有一个特别的值 NULL &#x1f928; 2. 排查…
阅读更多...
vscode如何远程到linux python venv虚拟环境开发？（python虚拟环境、vscode远程开发、vscode远程连接）

vscode如何远程到linux python venv虚拟环境开发？（python虚拟环境、vscode远程开发、vscode远程连接）

文章目录 1. 安装VSCode2. 安装扩展插件3. 配置SSH连接4. 输入用户名和密码5. 打开远程文件夹6. 创建/选择Python虚拟环境7. 安装Python插件 Visual Studio Code (VSCode) 提供了一种称为 Remote Development 的功能&#xff0c;允许用户在远程系统、容器或甚至 Windows 子系统…
阅读更多...
【微信小程序】基本语法

【微信小程序】基本语法

目录 一、列表渲染&#xff08;包括wx:for改变默认&#xff09; 二、事件冒泡和事件捕获 三、生命周期 一、列表渲染&#xff08;包括wx:for改变默认&#xff09; 1、列表渲染(wx-for、block 改变默认wx:for item等) <view> {{msg}} </view> //渲染跟普通vu…
阅读更多...
泛型 --java学习笔记

泛型 --java学习笔记

什么是泛型 定义类、接口、方法时&#xff0c;同时声明了一个或者多个类型变量&#xff08;如&#xff1a;<E>&#xff09;&#xff0c;称为泛型类、泛型接口&#xff0c;泛型方法、它们统称为泛型 可以理解为扑克牌中的癞子&#xff0c;给它什么类型它就是什么类型 如…
阅读更多...
设计模式—适配器模式

设计模式—适配器模式

概念: 适配器模式&#xff08;有时候也称包装样式或者包装&#xff09;将一个类的接口适配成用户所期待的。一个适配允许通常因为接口不兼容而不能在一起工作的类工作在一起&#xff0c;做法是将类自己的接口包裹在一个已存在的类中。 本章代码: 小麻雀icknn/设计模式练习 - Gi…
阅读更多...
开源的前端思维导图库介绍

开源的前端思维导图库介绍

在开源社区中&#xff0c;有许多优秀的思维导图库可供开发者使用。这些库通常具有丰富的功能和灵活的API&#xff0c;可以满足不同需求的前端开发。以下是一些流行的开源前端思维导图库&#xff0c;以及它们的特点和区别。 1. **MindMap** 特点&#xff1a; - 基于原生…
阅读更多...
【数据结构】二、线性表：4.循环链表的定义及其基本操作（循环单链表,循环双链表的初始化、判空、判断头结点、尾结点、插入、删除）

【数据结构】二、线性表：4.循环链表的定义及其基本操作（循环单链表,循环双链表的初始化、判空、判断头结点、尾结点、插入、删除）

文章目录 4.循环链表4.1循环单链表4.1.1初始化4.1.2判断单链表是否为空4.1.3判断p结点是否为循环单链表的表尾结点 4.2循环双链表4.2.1初始化4.2.2判断循环链表是否为空4.2.3判断结点p是否为循环双链表的表尾结点4.2.4双链表的插入4.2.5双链表的删除 4.循环链表 4.1循环单链表…
阅读更多...
十堰网站建设公司华想科技具有10年的网站制作经验

十堰网站建设公司华想科技具有10年的网站制作经验

2018年已经结束了。 华翔科技收到了很多客户的咨询&#xff0c;他们都有一个共同的问题&#xff1a;建一个网站需要多少钱&#xff1f; 但是&#xff0c;我们都会问&#xff1a;您有什么具体需求吗&#xff1f; 大多数人的答案是否定的&#xff0c;他们只是想打听一下价格。 十…
阅读更多...
《JAVA与模式》之模板方法模式

《JAVA与模式》之模板方法模式

系列文章目录 文章目录 系列文章目录前言一、模板方法模式的结构二、模板方法模式中的方法三、使用场景四、模板方法模式在Servlet中的应用前言 前些天发现了一个巨牛的人工智能学习网站，通俗易懂，风趣幽默，忍不住分享一下给大家。点击跳转到网站，这篇文章男女通用，看懂了…
阅读更多...
【MySQL 系列】MySQL 起步篇

【MySQL 系列】MySQL 起步篇

MySQL 是一个开放源代码的、免费的关系型数据库管理系统。在 Web 开发领域&#xff0c;MySQL 是最流行、使用最广泛的关系数据库。MySql 分为社区版和商业版&#xff0c;社区版完全免费&#xff0c;并且几乎能满足全部的使用场景。由于 MySQL 是开源的&#xff0c;我们还可以根…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023