数据结构初阶之单链表

Ne0inhk

— 10 min read
数据结构初阶之单链表

1.单链表的实现

我们不再过的的废话，直接来看关于单链表的一些功能函数：

voidSLTPrint(SLTNode* phead);voidSLTPushBack(SLTNode** phead, SLTDataType x);voidSLTPushFront(SLTNode** phead, SLTDataType x);voidSTLPopBack(SLTNode** phead);voidSLTPopFront(SLTNode** phead); SLTNode*SLTFind(SLTNode* phead, SLTDataType x);voidSLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x);voidSLTInsertAfter(SLTNode* pos, SLTDataType x);voidSLTErase(SLTNode** phead, SLTNode* pos);voidSLTEraseAfter(SLTNode* pos);voidSListDesTroy(SLTNode** phead);

这些是涉及我们这次要实现的函数功能，我们来一一解决它们

不过在此之前，我们首先看一下关于单链表的实现：

1.1实现

typedefint SLTDataType;typedefstructSListNode{ SLTDataType data;structSListNode* next;}SLTNode;

上面的是前置条件，在链表中我们存储data，并存储指向下一个节点的指针，
可视化理解：
一个节点在内存中的样子：

┌───────────────────────┐ │ Node │ ├───────────┬───────────┤ │ data │ next │ │ (值) │ (指针) │ │ e.g.10 │ 0x123456 │ └───────────┴───────────┘

多个节点连接成链表：

节点1(地址:0x1000) 节点2(地址:0x2000) 节点3(地址:0x3000) ┌───────────┬───────────┐ ┌───────────┬───────────┐ ┌───────────┬───────────┐ │ data:1 │ next:0x2000│→ │ data:2 │ next:0x3000│→ │ data:3 │ next:NULL │ └───────────┴───────────┘ └───────────┴───────────┘ └───────────┴───────────┘ 
voidtest1(){ SLTNode* node1 =(SLTNode*)malloc(sizeof(SLTNode)); node1->data =1; SLTNode* node2 =(SLTNode*)malloc(sizeof(SLTNode)); node2->data =2; SLTNode* node3 =(SLTNode*)malloc(sizeof(SLTNode)); node3->data =3; SLTNode* node4 =(SLTNode*)malloc(sizeof(SLTNode)); node4->data =4; node1->next = node2; node2->next = node3; node3->next = node4; node4->next =NULL; SLTNode* plist = node1;SLTPrint(plist);}

链表节点存储两个关键信息：

  • 数据值（data）：节点的实际内容
  • 指向下一个节点的指针（next）：将节点连接成链的关键

2单链表函数

2.1单链表打印

voidSLTPrint(SLTNode* phead){ SLTNode* pcur = phead;while(pcur){printf("%d->", pcur->data); pcur = pcur->next;}printf("NULL\n");}

我们首先定义pcur指向头节点，while循环，依次打印节点中的data值即可

2.2 单链表的尾插

voidSLTPushBack(SLTNode** phead, SLTDataType x){assert(phead); SLTNode* newnode =SLTBuyNode(x);if(*phead ==NULL){*phead = newnode;}else{ SLTNode* ptail =*phead;while(ptail->next){ ptail = ptail->next;} ptail->next = newnode;}}

首先，我们传过来的二级指针不能为空，但是一级指针是可以的，毕竟传过来的链表为空，那我尾插也没什么问题，我们定义新节点为newnode，那么可能会有人说SLTBuyNode(x)是什么玩意，这个其实是因为在函数功能中我们总会用到申请空间的一个功能，所以我们干脆再写一个函数完成这个功能，如下：

SLTNode*SLTBuyNode(SLTDataType x){ SLTNode* newnode =(SLTNode*)malloc(sizeof(SLTNode));if(newnode ==NULL){perror("malloc fail");exit(1);} newnode->data = x; newnode->next =NULL;}

好了，继续我们的思路，如果我们传过来的链表为空，那么走if函数中，直接把新申请的给我们的空链表就可以了，如果不为空链表，那么定义个ptail节点，进入while循环中，直到找到最后一个节点，然后把ptail->next = newnode即可
其实这里还有一个问题，为什么这里要传二级指针呢？

2.2.1为什么要传二级指针？

答案只有一个！那就是如果传一级指针，那么我们的形参并不会影响实参，这种传递只是传值，它们之间互不影响罢了，可能到这里还是不明白为什么，没关系，我们这里来详细探讨下：

场景一：链表为空时插入第一个节点

SLTNode* plist =NULL;// plist本身是个指针，现在是NULLSLTPushBack(plist,1);// 如果传plist，只是传值

如果SLTPushBack参数是SLTNode* phead

  • phead是plist的副本
  • 你在函数里phead = newnode，只是改了副本
  • 函数返回后，外面的plist还是NULL 😢
    场景二：用二级指针
voidSLTPushBack(SLTNode** pphead, SLTDataType x){// pphead 是 &plist，*pphead 就是 plist// 修改 *pphead = newnode，就是修改了 plist 本身}

"第一个节点"和"指向第一个节点的指针"是什么？

实际内存结构： ┌─────┬─────────────┐ ┌─────┬─────────────┐ │ data│ next │ │ data│ next │ │ 1 │ 0x1000─────▶│ │ 2 │ 0x2000─────▶│ └─────┴─────────────┘ └─────┴─────────────┘ 地址：0x1000 地址：0x2000 plist（指针变量）： ┌─────────────┐ │ 值：0x1000 │ ← 指向第一个节点 └─────────────┘ 地址：0x3000（假设）
  • 第一个节点：内存地址为0x1000的那个结构体
  • 指向第一个节点的指针：变量plist，它存的值是0x1000
  • 指向第一个节点的指针的地址：&plist，值是0x3000
    形象比喻：
  • 一级指针 = 你家的门牌号（知道房子在哪）
  • 二级指针 = 知道你家门牌号写在哪个本子上
  • 要换房子（空链表插入）时，得找到记门牌号的本子（二级指针），改上面的门牌号

简单记忆：

  • 如果函数要修改链表头指针（空链表插入、删除第一个节点等），传二级指针&plist
  • 如果函数只是遍历/读取，传一级指针plist

为什么难理解？
因为指针就像"遥控器"，你手里拿着遥控器（一级指针）。如果你想在另一个房间（函数里）换台（修改链表头），得有人把遥控器给你。但如果只是告诉你现在播什么节目（读取），就不需要给遥控器。
如果有些人到这里还是不太理解，那我们不妨再做个对照实验：
场景1：修改普通变量

voidchangeNumber(int x){ x =100;// 修改副本}intmain(){int a =10;changeNumber(a);// 传值printf("%d", a);// 输出：10，a没变！}

这里大家都明白：传值只是传了副本。
场景2：修改指针指向的值

voidchangeValue(int* p){*p =100;// 通过指针修改原值}intmain(){int a =10;changeValue(&a);// 传地址printf("%d", a);// 输出：100，a变了！}

这里也简单：用一级指针修改指针指向的数据。

场景3：修改指针本身（这才是你的困惑）

// 这个函数想改变指针本身（让它指向新地址）voidchangePointer(int* p){ p =malloc(sizeof(int));// 这只能改变局部副本p*p =200;}intmain(){int* ptr =NULL;// ptr是一个指针changePointer(ptr);// 想改变ptr，让它指向新内存// 问题：ptr仍然是NULL！}

关键来了：ptr本身是一个指针变量，它存着一个地址。当我们说"想修改ptr"，意思是修改ptr这个变量里存的地址值。

  • ptr = 0x1000 → 改成 ptr = 0x2000
  • 但ptr作为参数传给函数时，函数得到的是ptr值的副本
  • 就像int a = 10传值给函数一样
    可视化内存变化：
调用前： plist:[NULL] 地址0x1000 调用SLTPushBack(plist,1): 在栈上创建局部变量phead:[NULL] 地址0x2000(是plist的副本) 在函数里：phead = newnode phead:[0x3000] 地址0x2000(修改了局部变量) 函数返回：phead销毁 plist:[NULL] 地址0x1000(原指针没变！)

总结成一句话：

  • 你想修改谁的"值"，就要传谁的"地址"。
  • 想修改int a的值 → 传&a (一级指针)
  • 想修改int* ptr的值（这个值是个地址） → 传&ptr (二级指针)

在我们的例子中：

  • plist是一个SLTNode*类型的一级指针
  • 你想修改plist这个指针变量的值（从NULL改成新节点地址）
  • 所以要传plist的地址，即&plist，这就是二级指针

再打个比方：

  • plist = 一个信封，里面写着一个地址（现在是空的）
  • SLTPushBack(plist, x) = 我给你这个信封的复印件
  • 你在复印件上写新地址，不影响我的原信封
  • SLTPushBack(&plist, x) = 我给你我放信封的抽屉位置
  • 你打开抽屉，直接在我的原信封上写新地址
    现在大家明白了嘛？

2.3单链表的头插

voidSLTPushFront(SLTNode** phead, SLTDataType x){assert(phead); SLTNode* newnode =SLTBuyNode(x); newnode->next =*phead;*phead = newnode;}

首先还是二级指针不能为空，我让我定义的新节点指向头节点，再让*phead指向新节点，这样新节点就为头节点了

2.4单链表的尾删

voidSTLPopBack(SLTNode** phead){assert(phead &&*phead);//链表中只有一个节点if((*phead)->next ==NULL){free((*phead));*phead =NULL;}else{ SLTNode* prev =*phead; SLTNode* ptail =*phead;while(ptail->next){ prev = ptail; ptail = ptail->next;}free(ptail); prev->next =NULL; ptail =NULL;}}

我们想要尾删是不是需要找到最后一个节点呢？我们这里定义两个指针，当while循环，ptail->next结束后就找到了尾节点，但是我们还需要找到尾节点的前一个节点，为什么呢？如果我们找到尾节点直接释放掉的话，那我们尾节点的前一个节点指向哪里呢？对吧，所以我们需要找到尾节点的前一个节点，当找到这两个节点时，我把尾节点释放掉，前一个节点的next指向空指针，再把尾节点置为空即可。

2.5单链表的头删

voidSLTPopFront(SLTNode** phead){assert(phead &&*phead); SLTNode* next =(*phead)->next;free(*phead);*phead = next;}

这个其实很简单，首先定义个节点指向头节点的下一个节点，然后释放掉头节点，使下一个节点成为头节点即可。

2.6单链表的查找

SLTNode*SLTFind(SLTNode* phead, SLTDataType x){ SLTNode* pcur = phead;while(pcur){if(pcur->data == x){return pcur;} pcur = pcur->next;}returnNULL;}

这个没啥好讲，很简单，过。

2.7单链表关于在指定位置之前插入数据

voidSLTInsert(SLTNode** phead, SLTNode* pos, SLTDataType x){assert(phead &&*phead);assert(pos);if(*phead == pos){SLTPushFront(phead,x);}else{ SLTNode* newnode =SLTBuyNode(x); SLTNode* prev =*phead;while(prev->next != pos){ prev = prev->next;} newnode->next = pos; prev->next = newnode;}}

其实这里就是把前面综合一点而已，既然我们想要再pos节点之前插入数据，那么就先找到pos的前一个节点，然后把新节点的next指向pos，pos的前一个节点的next指向新节点即可，这样不就插入进去了嘛。

在这里插入图片描述


但是当我们注意，*phead == pos时这样的代码是行不通的，所以我们需要单独来讨论一下即可。

2.8单链表关于在指定位置之后插入数据

voidSLTInsertAfter(SLTNode* pos, SLTDataType x){assert(pos); SLTNode* newnode =SLTBuyNode(x); newnode->next = pos->next; pos->next = newnode;}

这个比刚才的更简单，因为在后，所以直接省一个参数，我们把新节点next指向pos->next即可，pos->next = newnode就可以啦，如图：

在这里插入图片描述

2.9单链表关于删除pos节点

voidSLTErase(SLTNode** phead, SLTNode* pos){assert(phead &&*phead);assert(pos);if(pos ==*phead){//头删 SLTNode* next =(*phead)->next;free(pos);(*phead)= next;}else{ SLTNode* pcur =*phead;while(pcur->next != pos){ pcur = pcur->next;} pcur->next = pos->next;free(pos); pos =NULL;}}

后面的跟前面都大同小异，就不说了。

2.10单链表关于删除pos之后的节点

voidSLTEraseAfter(SLTNode* pos){assert(pos&&pos->next); SLTNode* del = pos->next; pos->next = del->next;free(del); del =NULL;}

2.11单链表关于销毁单链表

voidSListDesTroy(SLTNode** phead){assert(phead &&*phead); SLTNode* pcur =*phead;while(pcur){ SLTNode* next = pcur->next;free(pcur); pcur = next;}*phead =NULL;}

Read more

【数据结构】二叉搜索树 C++ 简单实现：增删查改全攻略

【数据结构】二叉搜索树 C++ 简单实现：增删查改全攻略

目录 前言： 1、什么是二叉搜索树？ 2、二叉搜索树性能分析 3、key类型二叉搜索树的实现 节点结构 类结构 3.1、插入 3.2、中序遍历 3.3、查找 3.4、删除 4、key_value类型二叉搜索树的实现 节点结构 类结构 4.1、构造函数 4.1.1 默认构造 4.1.2 拷贝构造 4.2、赋值重载 4.3、析构 4.4、插入 总结 前言： 今天这篇，

By Ne0inhk
C++ string 全面指南

C++ string 全面指南

一、模板 1. 函数模板 什么是模板呢？模板就是一个模具，只需要往这个模具里倒入不同的材料，就可以获得不同材料的铸件。 如果我们要实现一个交换函数呢？这是很容易的事情。 但是这种交换函数只能实现整型之间的交换，如果我想进行浮点数交换呢，字符型交换呢？是不是就不可以了。 虽然我们可以通过函数重载实现不同的交换函数，但是这样做太浪费时间了，没有意义。毕竟只是改变了交换函数参数的类型，代码不需要变化。所以，这种方法是有缺陷的。 1.代码复用率低。 2.可维护性差。 所以，有了函数模板，这是实现泛型编程的基础。 所谓泛型编程就是编写与类型无关的通用代码，是代码复用的一种手段。 template<typename T>就是定义了一个模板，通过一份代码就可以实现多个要求。 这里的typename也可以换成class，这两个的区别会在后面讲解。 这个就叫做函数模板，函数模板代表了一个函数家族，该函数模板与类型无关，在使用时被参数化，根据实参类型产生函数的特定类型版本。 函数模板的格式：template<typename T1, typename

By Ne0inhk
【Linux】Linux 进程通信：System V 共享内存（最快方案）C++ 封装实战 + 通信案例，4 类经典 Bug 快速修复

【Linux】Linux 进程通信：System V 共享内存（最快方案）C++ 封装实战 + 通信案例，4 类经典 Bug 快速修复

前言：欢迎各位光临本博客，这里小编带你直接手撕**，文章并不复杂，愿诸君**耐其心性，忘却杂尘，道有所长！！！！ IF’Maxue：个人主页  🔥 个人专栏: 《C语言》 《C++深度学习》 《Linux》 《数据结构》 《数学建模》 ⛺️生活是默默的坚持，毅力是永久的享受。不破不立！ 文章目录 * 二、System V共享内存：最快的进程间通信 * 1. System V共享内存核心概念 * 2. System V共享内存原理 * （1）进程虚拟地址空间结构 * （2）共享内存映射过程 * （3）共享内存的管理：先描述，再组织 * 3. System V共享内存核心接口 * （1）生成唯一Key：ftok * （2）创建/获取共享内存：shmget

By Ne0inhk
Redis 解锁：C++ 实战深度探索 Set 数据类型

Redis 解锁：C++ 实战深度探索 Set 数据类型

前言 欢迎来到 Redis Set 的终极指南。如果您曾需要管理一组独一无二的元素集合——无论是用户 ID、文章标签还是邮件地址——并希望以闪电般的速度对其执行强大的集合运算，那么您来对地方了。Redis Set 绝不是一个简单的列表，它是一种精妙的数据结构，将数学中强大的集合理论直接带入您的高性能数据库中。 在本文中，我们将从最基础的概念讲起，逐步深入到高级的实际应用。我们将使用优秀的 C++ 库 redis-plus-plus 来演示所有示例，并逐行剖析代码。无论您是 C++ 开发者、后端工程师，还是仅仅对 Redis 感到好奇，读完本文，您都将深刻理解是什么让 Set 成为 Redis 中功能最丰富的工具之一。 Redis Set 究竟是什么？ 在我们深入代码之前，先来建立一个清晰的思维模型。想象你有一个魔力袋，你可以往里面扔东西，但这个袋子有两条非常特殊的规则： 1. 强制保持唯一：这个袋子会自动拒绝重复的物品。如果你想把一个标有“

By Ne0inhk