当前位置： 首页 > news >正文

【数据结构】单链表

news 来源：原创 2024/9/20 0:11:43

在这里插入图片描述
🔥博客主页： 小羊失眠啦.
🎥系列专栏：《C语言》 《数据结构》 《Linux》《Cpolar》
❤️感谢大家点赞👍收藏⭐评论✍️

在这里插入图片描述

文章目录

  • 前言
  • 一、什么是链表
    • 1.1 链表的概念及结构
    • 1.2 链表的分类
    • 1.3 单链表的结构
  • 二、链表的实现
    • 📖2.1 创建节点
    • 📖2.2 头插
    • 📖2.3 头删
    • 📖2.4 尾插
      • 💭链表不为空
      • 💭链表不为空
    • 📖2.5 尾删
    • 📖2.6 查找
    • 📖2.7 在pos位置之前插入
    • 📖2.8 在pos位置之后插入
    • 📖2.9 删除pos位置
    • 📖2.10 删除pos后面位置
    • 📖2.11 销毁
  • 三、总代码

前言

在上一期中我们学习了顺序表，顺序表可以通过索引（下标）快速地存、取表中元素，但文章末尾提及它有缺点，例如头插或从中间插入效率低等，而链表可以有效的解决这些问题。那么就让我们走进链表的学习~~

一、什么是链表

1.1 链表的概念及结构

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

结构：

在这里插入图片描述

注意：

1.链式结构在逻辑上是连续的，但在物理上不一定连续。

2.节点都是从堆上申请的。

3.从堆上申请空间，是按一定策略分配的，申请的空间可能连续，也可能不连续。

1.2 链表的分类

  • 单向或者双向（单链表或者双链表）
  • 带头或者不带头（带哨兵位和不带哨兵位）
  • 循环或者非循环

1.3 单链表的结构

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

这种链表被称为无头+单向+非循环链表

二、链表的实现

📖2.1 创建节点

我们想使用链表来实现各种功能得先有链表，所以首先使用malloc创建节点。

SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

在这里插入图片描述

📖2.2 头插

要想让链表连起来，就要让newnode->next存放下一个节点的地址，也就是旧链表plist的值，然后将newnode的地址存放在plist中，形成新的链表。无论一开始有没有节点，头插都是相同的。

在这里插入图片描述

// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pplist;//*pplist=plist*pplist = newnode;
}

在这里插入图片描述

📖2.3 头删

头删时如果先释放空间，就会找不到下一个节点的地址；如果先把下一个节点的地址赋给*pplist就会导致无法释放空间，所以我们要创建一个临时变量来存放下一个节点的地址。

// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(*pplist);SListNode* newnode = (*pplist)->next;free(*pplist);*pplist = newnode;
}

在这里插入图片描述

📖2.4 尾插

我们在尾插时，会有两种情况，链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误，接下来就让我们学习学习这两种尾插的情况。

💭链表不为空

在这里插入图片描述

当我们传递的是plist的值，屏幕上并没有打印出我们想要的结果。这是为什么呢？

形参是实参的一份临时拷贝，形参的改变不会影响实参，pplist的改变不会影响plist。 临时变量出作用域销毁，phead和newnode销毁，找不带开辟的节点，会造成内存泄漏。

确做法是要将plist的地址传递过去，我们通过解引用就可以改变plist。plist中存放的是指针，我们传递指针的地址要用二级指针接收。

💭链表不为空

链表不为空时，我们要找到尾节点。这里我们要注意不能使用 tail!=NULL 判断。这样我们无法把链表连接起来。

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{assert(pplist);SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next){tail = tail->next;}tail->next = newnode;}
}

📖2.5 尾删

在尾删时也有两种情况，一种是有很多节点，另一种是只剩一个节点，当删最后一个节点时，要改变plist的值，所以我们要传递plist的指针。我们要使用两个指针，当后面的指针释放后，可以利用前面的指针将最后一个节点的next置为空。

// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(*pplist);//一个if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}//多个else{SListNode* tail = *pplist;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}

在这里插入图片描述

📖2.6 查找

循环判断时不要使用cur->next，这样写最后一个数据要单独处理不方便，找到时就返回此时的地址。

// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return 0;
}

📖2.7 在pos位置之前插入

在pos位置之前插入有一种特殊的情况就是头插，要改变plist的值，我们要传二级指针进去。同时我们要创建一个指针变量，找到pos之前的位置，才能使链表连接起来。

void SListInsertAfter(SListNode** pplist,SListNode* pos, SLTDateType x)
{assert(pos);if (pos == *pplist){SListPushFront(pplist, x);}else{SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}SListNode* newnode = BuySListNode(x);newnode->next = pos;prev->next = newnode;}
}

📖2.8 在pos位置之后插入

这里我们要注意地址赋值的顺序，顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域，就会丢失下一个节点的地址。

void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}

📖2.9 删除pos位置

有可能删除的是头节点，所以要传递二级指针。

// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{assert(pos);if (pos == *pplist){SListPopFront(pplist);}else{SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;pos = NULL;free(pos);}
}

📖2.10 删除pos后面位置

void SListEraseAfter(SListNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SListNode* next = pos->next;pos->next = next->next;free(next);next = NULL;}
}

📖2.11 销毁

void SListDestory(SListNode** pplist)
{assert(pplist);SListNode* cur = *pplist;SListNode* next = NULL;while (cur->next != NULL){next = cur->next;free(cur);cur = NULL;}*pplist = NULL;
}

三、总代码

SList.h

#pragma once
// slist.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>typedef int SLTDateType;
typedef struct SListNode
{SLTDateType data;struct SListNode* next;
}SListNode;// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之前插入x
void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x);
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos,SLTDateType x);
// 删除pos位置
void SLTErase(SListNode** pphead, SListNode* pos);
// 删除pos后面位置
void SListEraseAfter(SListNode* pos);
// 销毁
void SListDestory(SListNode** pplist);

SList.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"SList.h"// 动态申请一个节点
SListNode* BuySListNode(SLTDateType x)
{SListNode* newnode = (SListNode*)malloc(sizeof(SListNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}// 单链表打印
void SListPrint(SListNode* plist)
{SListNode* tail = plist;while (tail){printf("%d->", tail->data);tail = tail->next;}printf("NULL\n");
}// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);if (*pplist == NULL){*pplist = newnode;}else{SListNode* tail = *pplist;while (tail->next){tail = tail->next;}tail->next = newnode;}
}// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x)
{SListNode* newnode = BuySListNode(x);newnode->next = *pplist;*pplist = newnode;
}// 单链表的尾删
void SListPopBack(SListNode** pplist)
{assert(*pplist);if ((*pplist)->next == NULL){free(*pplist);*pplist = NULL;}else{SListNode* tail = *pplist;while (tail->next->next){tail = tail->next;}free(tail->next);tail->next = NULL;}
}// 单链表头删
void SListPopFront(SListNode** pplist)
{assert(*pplist);SListNode* newnode = (*pplist)->next;free(*pplist);*pplist = newnode;}// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x)
{SListNode* cur = plist;while (cur != NULL){if (cur->data == x){return cur;}cur = cur->next;}return 0;
}void SListInsert(SListNode** pplist,SListNode* pos, SLTDateType x)
{assert(pos);if (pos == *pplist){SListPushFront(pplist, x);}else{SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}SListNode* newnode = BuySListNode(x);newnode->next = pos;prev->next = newnode;}
}
// 单链表在pos位置之后插入x
void SListInsertAfter(SListNode* pos, SLTDateType x)
{assert(pos);SListNode* newnode = BuySListNode(x);newnode->next = pos->next;pos->next = newnode;
}// 删除pos位置
void SLTErase(SListNode** pplist, SListNode* pos)
{assert(pos);if (pos == *pplist){SListPopFront(pplist);}else{SListNode* prev = *pplist;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;pos = NULL;free(pos);}
}void SListEraseAfter(SListNode* pos)
{assert(pos);if (pos->next == NULL){return;}else{SListNode* next = pos->next;pos->next = next->next;free(next);next = NULL;}
}void SListDestory(SListNode** pplist)
{assert(pplist);SListNode* cur = *pplist;SListNode* next = NULL;while (cur->next != NULL){next = cur->next;free(cur);cur = NULL;}*pplist = NULL;
}

本次的内容到这里就结束啦。希望大家阅读完可以有所收获，同时也感谢各位铁汁们的支持。文章有任何问题可以在评论区留言，小羊一定认真修改，写出更好的文章~~

在这里插入图片描述

相关文章：

  • 北京网站建设多少钱？
  • 辽宁网页制作哪家好_网站建设
  • 高端品牌网站建设_汉中网站制作
  • 【hcie-cloud】【2】华为云Stack解决方案介绍、缩略语整理 【下】
  • SpringCloudAlibaba系列之Nacos配置管理
  • 视频转码教程：轻松制作GIF动态图，一键高效剪辑操作
  • Luatos Air700 改变BL0942串口波特率
  • 深度学习理论知识入门【EM算法、VAE算法、GAN算法】和【RBM算法、MCMC算法、HMC算法】
  • 合并两个有序链表OJ
  • 浮点数保留指定位数的小数，小数位自动去掉多余的0
  • Mysql高阶语句
  • 【软件逆向】如何逆向Unity3D+il2cpp开发的安卓app【IDA Pro+il2CppDumper+DnSpy+AndroidKiller】
  • 大数据毕业设计选题推荐-市天气预警实时监控平台-Hadoop-Spark-Hive
  • NetworkManager 图形化配置 bond
  • 用 Wireshark 在 Firefox 或 Google Chrome 上使用 SSLKEYLOGFILE 环境变量解密 SSL 流量
  • C语言面试
  • webpack的简单使用
  • python---类与对象
  • 【从零开始安装kubernetes-1.7.3】2.flannel、docker以及Harbor的配置以及作用
  • Angular 响应式表单之下拉框
  • If…else
  • JavaScript 基本功--面试宝典
  • vue--为什么data属性必须是一个函数
  • windows-nginx-https-本地配置
  • 程序员该如何有效的找工作?
  • 高程读书笔记 第六章 面向对象程序设计
  • 手机app有了短信验证码还有没必要有图片验证码？
  • 数据库写操作弃用“SELECT ... FOR UPDATE”解决方案
  • 优秀架构师必须掌握的架构思维
  • 运行时添加log4j2的appender
  • 移动端高清、多屏适配方案
  • ​总结MySQL 的一些知识点：MySQL 选择数据库​
  • # 安徽锐锋科技IDMS系统简介
  • #android不同版本废弃api，新api。
  • #免费 苹果M系芯片Macbook电脑MacOS使用Bash脚本写入(读写)NTFS硬盘教程
  • ${ }的特别功能
  • （10）STL算法之搜索（二） 二分查找
  • （笔记）M1使用hombrew安装qemu
  • （顶刊）一个基于分类代理模型的超多目标优化算法
  • （二）七种元启发算法（DBO、LO、SWO、COA、LSO、KOA、GRO）求解无人机路径规划MATLAB
  • （四）搭建容器云管理平台笔记—安装ETCD(不使用证书)
  • （一）utf8mb4_general_ci 和 utf8mb4_unicode_ci 适用排序和比较规则场景
  • (转) RFS+AutoItLibrary测试web对话框
  • (转贴)用VML开发工作流设计器 UCML.NET工作流管理系统
  • (转载)虚函数剖析
  • .net 8 发布了，试下微软最近强推的MAUI
  • .NET 8.0 中有哪些新的变化？
  • .NET C# 使用 SetWindowsHookEx 监听鼠标或键盘消息以及此方法的坑
  • .NET Micro Framework 4.2 beta 源码探析
  • .NET MVC第五章、模型绑定获取表单数据
  • .Net Remoting(分离服务程序实现) - Part.3
  • .NET 解决重复提交问题
  • .NET/C# 将一个命令行参数字符串转换为命令行参数数组 args
  • .NET/C#⾯试题汇总系列：集合、异常、泛型、LINQ、委托、EF！（完整版）
  • .Net6 Api Swagger配置
  • .net6 当连接用户的shell断掉后,dotnet会自动关闭,达不到长期运行的效果。.NET 进程守护
  • .NET的数据绑定
  • .net中我喜欢的两种验证码