【数据结构】保姆级单链表教程（概念、分类与实现）

news/2024/11/20 21:38:59/

目录

🍊前言🍊：

🍈一、链表概述🍈：

1.链表的概念及结构：

2.链表存在的意义：

🍓二、链表的分类🍓：

🥝三、单链表的实现🥝：

1.工程文件：

2.接口实现（本文重点）：

①.打印单链表：

②.申请新节点：

③.单链表尾插：

④.单链表头插：

⑤.单链表尾删：

⑥.单链表头删：

⑦.单链表查找：

⑧.单链表插入：

⑨.单链表删除：

⑩.单链表销毁：

🍉四、链表实现全部源码🍉：

1.SList.h：

2.SList.c：

3.test.c：

🍒总结🍒：

🛰️博客主页：✈️銮同学的干货分享基地

🛰️欢迎关注：👍点赞🙌收藏✍️留言

🛰️系列专栏：🎈 数据结构

                       🎈【进阶】C语言学习

                       🎈  C语言学习

🛰️代码仓库：🎉数据结构仓库

                       🎉VS2022_C语言仓库

        家人们更新不易，你们的👍点赞👍和⭐关注⭐真的对我真重要，各位路过的友友麻烦多多点赞关注，欢迎你们的私信提问，感谢你们的转发！

        关注我，关注我，关注我，你们将会看到更多的优质内容！！

🏡🏡 本文重点 🏡🏡：

🚅 链表概念与结构 🚃 链表分类 🚃 单链表实现🚏🚏

🍊前言🍊：

        在上节课中我们学习了线性表中的顺序表相关知识，掌握了顺序表的相关实现与操作。而在这节课中，我将带领各位小伙伴们继续学习线性表中的另一个重要部分，即链表的相关知识学习。

🍈一、链表概述🍈：

1.链表的概念及结构：

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

2.链表存在的意义：

        通过上节课的学习，我们对顺序表有了较深层次的认知，同时我们发现，顺序表在创建和使用时，存在着一些明显的问题：

  • 当空间不足时，顺序表需要进行增容，但由于顺序表本质为数组，数据在物理上连续存放，因此在进行扩容时要付出较大的空间代价。
  • 为避免频繁扩容，基本每次都扩容 2 倍，当扩容次数增多时，就很有可能会造成一定程度的空间浪费。
  • 由于顺序表内数据连续存储，我们在向顺序表中位置插入或删除数据时，就需要挪动大量的数据，效率不高。

        于是人们针对顺序表的这些缺陷，设计出了链表这个概念来克服这些不足。

        而链表克服这些缺陷的方法是，将每一个节点划分为数据与指针两部分，数据部分用于存储数据而指针部分用于指向下一节点。这样做的好处是通过指针指向下一节点，于是数据的物理存储就可以不必连续，于是无论是在扩容，还是在插入与删除数据时，都能快速、方便的实现，并且不会造成很大的空间浪费。

🍓二、链表的分类🍓：

1.单向或双向：

2.带头或不带头：

3.循环或非循环：

（注：虽然有很多种不同的链表结构，但是最常用的链表结构主要是两种：无头单向非循环链表与带头双向循环链表）

  • 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。
  • 带头双向循环链表：结构最复杂，一般用在单独存储数据。虽然它结构复杂，但在实际使用中使用代码实现后，优秀的结构会带来很多优势，实现反而更加简单。并且在我们的实际中所使用的链表数据结构，一般都是带头双向循环链表。

🥝三、单链表的实现🥝：

1.工程文件：

        与顺序表的实现方式类似，也使用模块化开发格式，使用 SList.h 、SList.c 、test.c 三个文件进行代码书写：

  • SeqList.h：存放函数声明、包含其他头文件、定义宏。
  • SeqList.c：书写函数定义，书写函数实现。
  • test.c：书写程序整体执行逻辑。

        这其中，我们的接口实现主要研究的是函数实现文件 SeqList.c 中的内容，对 test.c 文件中的内容分不关心。

2.接口实现（本文重点）：

        这里是本文重点中的重点，即 SeqList.c 文件中的接口具体实现：

①.打印单链表：

  • 执行操作前无需进行断言，原因是循环条件为空指针，则条件不满足并停止循环，不会出现死循环。
  • 根据指针循环操作，打印数据后使指针指向节点内存放下一节点地址的指针 NEXT。
void SListPrint(SLNode* SLHead)
{SLNode* cur = SLHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}

②.申请新节点：

  • 在各项操作前，需动态申请新节点，再对新申请的节点进行操作。
SLNode* BuyListNode(SLDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("newnode:>");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}

③.单链表尾插：

  • 如果此时头节点为空指针，说明此时单链表内没有节点，此时只需要将申请来的新节点作为头节点即可。
  • 若头节点不为空，则应当首相找到尾节点，使尾结点指针指向申请来的新节点后，再使新节点指针指向空即可。
void SLPushBack(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找到尾结点SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}
  • 测试尾插接口功能实现：

④.单链表头插：

  • 头插实现非常简单，首先申请新节点，先使新节点的指针指向原来的头节点，再使链表头指向新节点即可。
  • 这里不需要考虑空节点的原因是，就算链表内没有内容，即首节点为空，新节点指针指向空也没有问题（申请新节点时原本就指向空）。
void SLPushFront(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}
  • 测试头插接口功能实现：

⑤.单链表尾删：

  • 执行操作前需要进行非空判断，防止传入空指针。
  • 若链表内只有一个节点，则直接释放并置空即可。
  • 若有一个以上节点，则当执行下面三个步骤：
  1. 首先寻找尾节点，找到后将其释放并置空。
  2. 但在释放前，必须将倒数第二个节点的指针指向空，否则将在指向最后一个被释放的节点时，变成野指针。
  3. 单向链表无法回溯，于是我们应当定义另一个指针，在每次移动尾节点指针前保存当前节点的位置。
void SLPopBack(SLNode** pphead)
{//判断链表是否为空：if (*pphead == NULL){return;}//若只有一个节点，直接释放并置空即可：if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//若有多个节点则执行多步尾删：else{SLNode* tail = *pphead;SLNode* prev = NULL;//找到尾节点：while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}
  • 测试尾删接口功能实现：

⑥.单链表头删：

  • 执行操作前判断指针非空，防止对空指针进行操作。
  • 使链表头指向第二个节点，接着将第一个节点释放并置空即可。
void SLPopFront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}
  • 测试头删接口功能实现：

⑦.单链表查找：

  • 采用遍历思想，依次对每一个节点的数据进行判断，符合条件即进行打印，不符合条件则继续向后遍历，直至指向 NULL，并且因此无需进行非空判断。
void SLFind(SLNode* phead, SLDataType x)
{SLNode* cur = phead;int count = 1;while (cur){if (cur->data == x){printf("第%d个节点：%p -> %d\n", count++, cur, x);}cur = cur->next;}
}
  • 测试查找接口功能实现：

⑧.单链表插入：

        单链表在插入新节点时有两种插入方式，一种是在目标节点前方插入，另一种是在目标节点后方插入，因此需要分别进行实现：

Ⅰ、单链表前插：

  • 前插有两种情况，一种是在首节点处插入，此时即相当于头插操作。
  • 另一种是在非首节点前插入，此时首先申请新节点，接着遍历单链表，找到插入位置后，使新节点指向目标节点后插入其前方。
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{//首先申请新节点SLNode* newnod = BuyListNode(x);if (*pphead == pos){newnod->next = *pphead;*pphead = newnod;}else{//找到目标节点 pos 的前一个节点：SLNode* PostPrev = *pphead;while (PostPrev->next != pos){PostPrev = PostPrev->next;}//找到后插入新节点：PostPrev->next = newnod;newnod->next = pos;}
}
  • 测试前插接口功能实现：

Ⅱ、单链表后插：

  • 在前插操作时，我们需要遍历整个链表来查找插入位置，因此效率较为低下，于是我们通常使用后插的方式插入新节点。
  • 后插直接申请节点，插入目标位置后即可。
void SLInsertAfter(SLNode* pos, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}
  • 测试后插接口功能实现：

⑨.单链表删除：

  • 单链表的删除很简单，分为两种情况进行处理，一种情况是整个链表中只有一个节点，则删除节点相当于释放整个数组并置空。
  • 另一种情况是含有一个以上节点，此时只需要让目标节点的前一个节点指针指向后一个节点，再释放目标节点并置空即可。
void SLErase(SLNode** pphead, SLNode* pos)
{if (*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}
  • 测试删除接口功能实现：

⑩.单链表销毁：

  • 遍历整个单链表，将每一个节点都进行释放并置空即可。
void SListDestory(SLNode** pphead)
{if (*pphead == NULL){return;}SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

🍉四、链表实现全部源码🍉：

1.SList.h：

#pragma once#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
#include<string.h>typedef int SLDataType;//单链表节点结构：
typedef struct SListNode
{SLDataType data;struct SListNode* next;
}SLNode;void SLPrint(SLNode* SLHead);    //打印单链表
SLNode* BuyListNode(SLDataType x);    //申请新节点
void SLPushBack(SLNode** pphead, SLDataType x);    //单链表尾插
void SLPushFront(SLNode** pphead, SLDataType x);    //单链表头插
void SLPopBack(SLNode** pphead);    //单链表尾删
void SLPopFront(SLNode** pphead);    //单链表头删
void SLFind(SLNode* phead, SLDataType x);    //单链表查找
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x);    //单链表前插
void SLInsertAfter(SLNode* pos, SLDataType x);    //单链表后插
void SLErase(SLNode** pphead, SLNode* pos);    //单链表删除
void SLDestory(SLNode** pphead);    //单链表销毁

2.SList.c：

#define _CRT_SECURE_NO_WARNINGS 1#include"SList.h"//打印单链表：
void SLPrint(SLNode* SLHead)
{SLNode* cur = SLHead;while (cur != NULL){printf("%d->", cur->data);cur = cur->next;}printf("NULL\n");
}//申请节点：
SLNode* BuyListNode(SLDataType x)
{SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));if (newnode == NULL){perror("newnode:>");exit(-1);}newnode->data = x;newnode->next = NULL;return newnode;
}//单链表尾插：
void SLPushBack(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);if (*pphead == NULL){*pphead = newnode;}else{//找到尾结点SLNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}//单链表头插：
void SLPushFront(SLNode** pphead, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = *pphead;*pphead = newnode;
}//单链表尾删：
void SLPopBack(SLNode** pphead)
{//判断链表是否为空：if (*pphead == NULL){return;}//若只有一个节点，直接释放并置空即可：if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}//若有多个节点则执行多步尾删：else{SLNode* tail = *pphead;SLNode* prev = NULL;//找到尾节点：while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}//单链表头删
void SLPopFront(SLNode** pphead)
{if (*pphead == NULL){return;}else{SLNode* next = (*pphead)->next;free(*pphead);*pphead = next;}
}//单链表查找
void SLFind(SLNode* phead, SLDataType x)
{SLNode* cur = phead;int count = 1;while (cur){if (cur->data == x){printf("第%d个节点：%p -> %d\n", count++, cur, x);}cur = cur->next;}
}//单链表前插：
void SLInsertFront(SLNode** pphead, SLNode* pos, SLDataType x)
{//首先申请新节点SLNode* newnod = BuyListNode(x);if (*pphead == pos){newnod->next = *pphead;*pphead = newnod;}else{//找到目标节点 pos 的前一个节点：SLNode* PostPrev = *pphead;while (PostPrev->next != pos){PostPrev = PostPrev->next;}//找到后插入新节点：PostPrev->next = newnod;newnod->next = pos;}
}//单链表后插：
void SLInsertAfter(SLNode* pos, SLDataType x)
{SLNode* newnode = BuyListNode(x);newnode->next = pos->next;pos->next = newnode;
}//单链表删除：
void SLErase(SLNode** pphead, SLNode* pos)
{if (*pphead == pos){*pphead = pos->next;free(pos);pos = NULL;}else{SLNode* prev = *pphead;while (prev->next != pos){prev = prev->next;}prev->next = pos->next;free(pos);pos = NULL;}
}//单链表销毁：
void SLDestory(SLNode** pphead)
{if (*pphead == NULL){return;}SLNode* cur = *pphead;while (cur){SLNode* next = cur->next;free(cur);cur = next;}*pphead = NULL;
}

3.test.c：

#define _CRT_SECURE_NO_WARNINGS 1#include"SList.h"void TestSList1()
{SLNode* plist = NULL;//单链表尾插：SLPushBack(&plist, 1);SLPushBack(&plist, 2);SLPushBack(&plist, 3);SLPushBack(&plist, 4);SLPrint(plist);//单链表后插：SLInsertAfter(plist->next, 5);SLPrint(plist);
}int main()
{TestSList1();return 0;
}//单链表头插：
//SLNode* plist = NULL;
单链表尾插：
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表头插：
//SLPushFront(&plist, 2);
//SLPushFront(&plist, 3);
//SLPushFront(&plist, 4);
//SLPrint(plist);//单链表尾删：
//SLNode* plist = NULL;
单链表尾插：
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表尾删：
//SLPopBack(&plist);
//SLPopBack(&plist);
//SLPopBack(&plist);
//SLPrint(plist);//单链表头删：
//SLNode* plist = NULL;
单链表尾插：
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表头删：
//SLPopFront(&plist);
//SLPrint(plist);
//SLPopFront(&plist);
//SLPrint(plist);
//SLPopFront(&plist);
//SLPrint(plist);
//SLPopFront(&plist);
//SLPrint(plist);//单链表查找：
//SLNode* plist = NULL;
单链表尾插：
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 4);
//SLPushBack(&plist, 2);
//
//SLPrint(plist);
单链表查找：
//SLFind(plist, 2);
//SLPrint(plist);//单链表前插：
//SLNode* plist = NULL;
单链表尾插：
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表前插：
//SLInsertFront(&plist, (plist->next)->next, 3);;
//SLPrint(plist);//单链表后插：//单链表删除：
//SLNode* plist = NULL;
单链表尾插：
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表删除：
//SLErase(&plist, (plist->next)->next);
//SLPrint(plist);//单链表销毁：
//SLNode* plist = NULL;
单链表尾插：
//SLPushBack(&plist, 1);
//SLPushBack(&plist, 2);
//SLPushBack(&plist, 3);
//SLPushBack(&plist, 4);
//SLPrint(plist);
单链表销毁：
//SLDestory(plist);
//SLPrint(plist);

🍒总结🍒：

        今天我们认识并学习了单向无头链表的相关概念、结构与接口实现，并且针对每个常用的功能接口都进行了实现分解，并对各个接口的各项注意点都进行了强调说明，希望能对各位小伙伴们的链表学习提供一些谨小的帮助。

        🔥🔥努力的时间还不够，哪有时间去绝望🔥🔥

        更新不易，辛苦各位小伙伴们动动小手，👍三连走一走💕💕 ~ ~ ~  你们真的对我很重要！最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！


http://www.ppmy.cn/news/12498.html

相关文章

寻找两个正序数组的中位数

寻找两个正序数组的中位数

题目 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。 算法的时间复杂度应该为 O(log (m+n)) 。 示例 1： 输入：nums1 = [1,3], nums2 = [2] 输出：2.00000 解释：合并数组 = [1,2,3] ，中位数 2 示例 2： 输入…
阅读更多...
Java使用Zxing二维码生成

Java使用Zxing二维码生成

目录 1、二维码简介 二维码纠错级别 2、ZXing简介 3、示例 3.1 搭建一个maven项目&#xff0c;引入Zxing依赖包 3.2 创建QrCodeUtil.java 类 1、二维码简介 二维条形码是用某种特定的几何图形按一定规律在平面&#xff08;二维方向上&#xff09;分布的黑白相间的图形记录…
阅读更多...
react受控组件和非受控组件区别

react受控组件和非受控组件区别

一、受控组件 在HTML中&#xff0c;表单元素的标签、、等的值改变通常是根据用户输入进行更新。 在React中&#xff0c;可变状态通常保存在组件的状态属性中&#xff0c;并且只能使用 setState() 进行更新&#xff0c;而呈现表单的React组件也控制着在后续用户输入时该表单中发…
阅读更多...
Python学习笔记-PyQt6消息窗

Python学习笔记-PyQt6消息窗

对话框是界面编程中重要的窗体&#xff0c;一般用于提示或者一些其他特定操作。一、使用QDialog显示通用消息框直接使用QDialog类&#xff0c;可以及通过对话框进行通用对话框显示&#xff0c;亦可以通过自定义设置自己需要的对话框。# _*_ coding:utf-8 _*_import sysfrom PyQ…
阅读更多...
Linux 中断子系统(八)：中断处理流程

Linux 中断子系统(八)：中断处理流程

1、上层中断处理 系统初始化时，已经建立起 硬件中断号 和 软件中断号的 映射表。 中断注册时，我们需要先从设备树中获取硬件中断号，然后调用 API 将硬件中断号转换为软件中断号，根据软件终端号 irq 找到对应的 irq_desc，并将中断处理函数添加到 irq_desc 中（也就是 irq…
阅读更多...
【C语言进阶】使用“动态内存文件处理”实现进阶版通讯录

【C语言进阶】使用“动态内存文件处理”实现进阶版通讯录

目录 前言 改进后的优势 一、test.c 二、contact.h 三、contact.c 1.加载通讯录函数load_contact 2、将数据保存到文件save_contact函数 3、初始化通讯录init_contact函数 4、扩容check_full函数 5、销毁通讯录destory_contact函数 6、其余函数 四、完整源码 总结 …
阅读更多...
java伪随机数生成器

java伪随机数生成器

关于随机数的基本概念 1、对随机数性质分类&#xff1a; 随机性&#xff1a;符合该性质的叫弱伪随机数。这种随机数仅可以用于一般应用&#xff0c;无法用在密码学&#xff0c;例如java中的java.util.Random类不可预测性&#xff1a;符合该性质的叫强伪随机数。在密码学中&am…
阅读更多...
Redis 实现用户积分和积分排行榜微服务优化

Redis 实现用户积分和积分排行榜微服务优化

文章目录修改添加积分方法积分排行控制层redis实现积分排行业务逻辑层Redis排行榜测试使用 JMeter 压测对比在之前的博客中我通过 MySQL数据库实现了积分和积分排行榜功能&#xff0c;在数据量大和并发量高的情况下会有以下缺点&#xff1a;SQL编写复杂&#xff1b;数据量大&am…
阅读更多...
最新文章

Copyright @ 2022~2023