数据结构：单链表(2)

Ne0inhk

— 14 min read
数据结构：单链表(2)

目录

前言 

一、实现单链表

介绍：

1.链表节点查找

2.链表在指定位置之前或之后插入元素

（1）链表在指定位置之前插入元素

举实例：

（2）链表在指定位置之后插入元素

3.链表在指定位置删除或指定位置之后删除

（1）链表在指定位置删除

（2）链表在指定位置之后删除

三、举实例，测试代码（包括所有代码展现）

1.h

1.cpp

main.cpp

四、链表的分类

按节点连接方向分类

按是否有头节点分类

  总结

前言 

上篇文章讲解了单链表的知识，包括：单链表的概念，单链表的结构、实现单链表（单链表的尾插、单链表的头插、单链表的尾删、单链表的头删）知识的相关内容，实现单链表其余的函数、链表的分类、单链表算法题知识的相关内容，为本章节知识的内容。

一、实现单链表

介绍：

1.链表节点查找

在链表中查找节点是基础操作，核心目标是根据指定条件（如值匹配）定位目标节点，本函数以值匹配作为条件：

函数形式：

SListNode* SLTFind(SListNode* h, type x)

代码实现为：

SListNode* SLTFind(SListNode* h, type x) { SListNode* p = h; while (p) { if (p->data == x) { return p; } p = p->next; } return NULL; }

讲解：

函数参数：SListNode* h：指向单链表头节点的指针。type x：要查找的值，type 是一个泛型类型，可以是任意数据类型。

函数返回值：如果找到了值为 x 的节点，则返回指向该节点的指针。如果没有找到，则返回 NULL。

函数实现步骤：初始化一个指针 p，并将其指向链表的头节点 h。使用 while 循环遍历链表，只要 p 不为 NULL，就继续循环。在循环内部，检查当前节点 p 的数据 p->data 是否等于要查找的值 x。如果相等，则返回当前节点的指针 p。如果不相等，则将 p 指向下一个节点，继续循环。如果遍历完整个链表都没有找到值为 x 的节点，则返回 NULL。

简单来说：如果找到对应的元素，返回指针，找不到就返回空。

2.链表在指定位置之前或之后插入元素

（1）链表在指定位置之前插入元素

函数形式：

void SLTInsert(SListNode** h, SListNode* pos, type x)

代码实现为：

void SLTInsert(SListNode** h, SListNode* pos, type x) { if (h == NULL || pos == NULL||*h == NULL) { printf("前插入失败\n"); return; } if (*h == pos) { SLTPushFront(h, x); return; } SListNode* p = *h; while (p!=NULL&&p->next != pos) { p = p->next; } if (p) { SListNode* newnode = SLTBuyNode(x); newnode->next=pos; p->next=newnode ; } else { printf("没有找到该节点\n"); return; } }

讲解：



为什么这两步不可颠倒？
若先执行 p->next = newnode，会丢失 pos 的地址（p->next 原指向 pos），导致无法将 newnode->next 连接到 pos。

插入之后的图示：

举实例：

首先操作的代码：

1.新用到的函数：

SListNode* SLTFind(SListNode* h, type x) { SListNode* p = h; while (p) { if (p->data == x) { return p; } p = p->next; } return NULL; } void SLTInsert(SListNode** h, SListNode* pos, type x) { if (h == NULL || pos == NULL||*h == NULL) { printf("前插入失败\n"); return; } if (*h == pos) { SLTPushFront(h, x); return; } SListNode* p = *h; while (p!=NULL&&p->next != pos) { p = p->next; } if (p) { SListNode* newnode = SLTBuyNode(x); newnode->next=pos; p->next=newnode ; } else { printf("没有找到该节点\n"); return; } }

2.示例代码:

#include"1.h" void test2() { SListNode* h=NULL; SLTPushBack(&h, 10); //10 SLTPushBack(&h, 20); //10 20 SLTPrint(h); SLTPushFront(&h, 30); // 30 10 20 SLTPushFront(&h, 40); // 40 30 10 20 SLTPrint(h); SLTPopBack(&h); //40 30 10 SLTPrint(h); SLTPopFront(&h); //30 10 SLTPrint(h); SListNode *p=SLTFind(h, 10); if (p) { printf("%d\n", p->data); //10 } SLTInsert(&h, p, 1000); SLTPrint(h); //30 1000 10 SListDestroy(&h); } int main() { test2(); }

（2）链表在指定位置之后插入元素

函数形式：

void SLTInsertAfter(SListNode* pos, type x)

代码实现为：

void SLTInsertAfter(SListNode* pos, type x) { if (pos == NULL) { printf("后插入失败\n"); return; } SListNode* p = pos->next; SListNode* newnode = SLTBuyNode(x); newnode->next = p; pos->next = newnode; }

讲解：

函数核心逻辑（一句话总结）

在 pos 节点后插入新节点，本质是“切断 pos 与原后继节点的连接，插入新节点作为 pos 的新后继”。
流程：检查 pos 是否有效 → 2. 保存 pos 原后继节点 → 3. 创建新节点 → 4. 新节点连接原后继 → 5. pos 连接新节点。

代码逐行深度解析

1. 边界条件检查作用：pos 是插入位置的基准节点，若 pos 为空（无效），直接报错并返回，避免后续 pos->next 导致空指针崩溃。对比前插函数：后插无需检查头节点（h 或 *h），因为插入位置由 pos 直接确定，与头节点无关。

2. 保存 pos 的原后继节点必要性：若不保存 pos->next，后续 pos->next = newnode 会覆盖原后继地址，导致链表断裂（原后继节点永久丢失）。类比：相当于搬家时先把“当前位置的下一个箱子”挪开，腾出空间放新箱子。

3. 创建新节点核心功能：动态申请新节点内存，并将数据 x 存入新节点。注意：实际工程中需检查 newnode 是否为 NULL（内存分配失败），此处简化未展开。

4. 连接新节点与原后继图示：原链表：pos ——→ p ——→ ... 执行后：newnode ——→ p ——→ ...



5. pos 连接新节点（完成插入）最终链表结构：

3.链表在指定位置删除或指定位置之后删除

（1）链表在指定位置删除

单链表删除指定位置节点包括 “删除指定节点 pos” 和 “删除第 n 个节点” 两种场景，删除第n个节点可通过循环来实现，而删除指定节点 pos较为复杂，所以，本文选取讲解删除指定节点 pos。

void SLTErase(SListNode** h, SListNode* pos)

具体代码：

void SLTErase(SListNode** h, SListNode* pos) { if (h == NULL || *h == NULL || pos == NULL) { return; } if (pos == *h) { SLTPopFront(h); } else {SListNode* p = *h; while (p != NULL && p->next != pos) { p = p->next; } if (p == NULL) { printf("没有该节点\n"); return; } else { p->next = pos->next; free(pos); } } }

讲解：



核心逻辑：分场景处理的底层原理

1. 分支1：删除头节点（pos == *h）触发条件：待删除节点 pos 就是头节点（*h 是头节点指针）。为什么无需 return？
因 if 分支执行后，函数直接进入 else 分支或结束（无 else 时），当前代码通过 else 确保头删后不会执行后续遍历逻辑。

2. 分支2：删除中间/尾节点（pos != *h）核心目标：找到 pos 的 前驱节点 p（即 p->next == pos），通过修改 p->next 跳过 pos 节点。正常终止：p->next == pos → 找到前驱 p，执行 p->next = pos->next（切断 pos 节点）。异常终止：p == NULL → 遍历到链表尾仍未找到 pos（pos 不在链表中），打印提示并返回。

边界场景：覆盖所有可能情况

遍历逻辑：

SListNode* p = *h; // 从新头节点开始遍历（若头节点未删除） while (p != NULL && p->next != pos) { p = p->next; }

处理方式：调用 SLTPopFront(h)，假设该函数实现如下（标准头删逻辑）：

void SLTPopFront(SListNode** h) { SListNode* tmp = *h; // 保存旧头节点 *h = (*h)->next; // 更新头指针为下一个节点 free(tmp); // 释放旧头节点内存 }

（2）链表在指定位置之后删除

操作位删除 pos 节点的下一个节点（若 pos 是尾节点或链表为空，则不操作）。

  • 删除单链表中 pos 节点之后 的第一个节点（即删除 pos->next）。
  • 适用场景：需删除指定位置后续节点时使用（注意：不能删除头节点前的节点，也不能直接删除 pos 自身）。

函数形式：

void SLTEraseAfter(SListNode* pos)

代码实现为：

void SLTEraseAfter(SListNode* pos) { if (pos==NULL || pos->next == NULL) { printf("不可删后节点\n"); return; } SListNode* p = pos->next; pos->next = p->next; free(p); }

讲解：



边界条件 if (pos == NULL || pos->next == NULL) 的必要性结论：两种情况均需提前拦截，避免程序崩溃或无效操作。

SListNode* p = pos->next;   // 步骤1：用 p 暂存待删除节点地址  
pos->next = p->next;        // 步骤2：pos 直接指向 p 的下一个节点（链表"跳过" p）  
free(p);                    // 步骤3：释放 p 指向的内存（避免内存泄漏）  

三、举实例，测试代码（包括所有代码展现）

首先操作的代码，我分为三个文件所写，接下来，我将展示代码内容：

1.h

#include<stdio.h> #include<stdlib.h> typedef int type; typedef struct SListNode { type data; struct SListNode* next; }SListNode; void SLTPrint(SListNode* h); void SListDestroy(SListNode** h); void SLTPushBack(SListNode** h, type x); void SLTPushFront(SListNode** h, type x); void SLTPopBack(SListNode** h); void SLTPopFront(SListNode** h); SListNode* SLTBuyNode(type x); SListNode* SLTFind(SListNode* h, type x); void SLTInsert(SListNode** h, SListNode* pos, type x); void SLTInsertAfter(SListNode* pos, type x); void SLTErase(SListNode** h, SListNode* pos); void SLTEraseAfter(SListNode* pos);

1.cpp

#include"1.h" void SLTPrint(SListNode* h) { if (h == NULL) { printf("链表为空,无值\n"); return; } SListNode* p = h; while (p) { printf("%d ", p->data); p = p->next; } printf("\n"); } void SListDestroy(SListNode** h) { if (*h == NULL) { printf("链表为空\n"); return; } SListNode* p = *h; while(p) { SListNode* q = p; p = p->next; free(q); } } SListNode* SLTBuyNode(type x) { SListNode* p = (SListNode*)malloc(sizeof(SListNode)); if (p) { p->data = x; p->next = NULL; return p; } else { perror("malloc failed"); return NULL; } } void SLTPushBack(SListNode** h, type x) { SListNode* p = SLTBuyNode(x); if (*h == NULL) { *h = p; } else { SListNode* pr = *h; while (pr->next) { pr = pr->next; } pr->next = p; } } void SLTPushFront(SListNode** h, type x) { SListNode* newnode = SLTBuyNode(x); if (*h == NULL) { *h = newnode; } else { newnode->next = *h; *h = newnode; } } void SLTPopBack(SListNode** h) { if (*h == NULL) { return; } if ((*h)->next == NULL) { free(*h); *h = NULL; } else { SListNode* p = *h; SListNode* pr = *h; while (p->next) { pr = p; p = p->next; } free(p); pr->next = NULL; } } void SLTPopFront(SListNode** h) { if (*h == NULL) { return; } SListNode* p = (*h)->next; free(*h); *h = p; } SListNode* SLTFind(SListNode* h, type x) { SListNode* p = h; while (p) { if (p->data == x) { return p; } p = p->next; } return NULL; } void SLTInsert(SListNode** h, SListNode* pos, type x) { if (h == NULL || pos == NULL||*h == NULL) { printf("前插入失败\n"); return; } if (*h == pos) { SLTPushFront(h, x); return; } SListNode* p = *h; while (p!=NULL&&p->next != pos) { p = p->next; } if (p) { SListNode* newnode = SLTBuyNode(x); newnode->next=pos; p->next=newnode ; } else { printf("没有找到该节点\n"); return; } } void SLTInsertAfter(SListNode* pos, type x) { if (pos == NULL) { printf("后插入失败\n"); return; } SListNode* p = pos->next; SListNode* newnode = SLTBuyNode(x); newnode->next = p; pos->next = newnode; } void SLTErase(SListNode** h, SListNode* pos) { if (h == NULL || *h == NULL || pos == NULL) { return; } if (pos == *h) { SLTPopFront(h); } else {SListNode* p = *h; while (p != NULL && p->next != pos) { p = p->next; } if (p == NULL) { printf("没有该节点\n"); return; } else { p->next = pos->next; free(pos); } } } void SLTEraseAfter(SListNode* pos) { if (pos==NULL || pos->next == NULL) { printf("不可删后节点\n"); return; } SListNode* p = pos->next; pos->next = p->next; free(p); }

main.cpp

#include"1.h" void test2() { SListNode* h=NULL; SLTPushBack(&h, 10); //10 SLTPushBack(&h, 20); //10 20 SLTPrint(h); SLTPushFront(&h, 30); // 30 10 20 SLTPushFront(&h, 40); // 40 30 10 20 SLTPrint(h); SLTPopBack(&h); //40 30 10 SLTPrint(h); SLTPopFront(&h); //30 10 SLTPrint(h); SListNode *p=SLTFind(h, 10); if (p) { printf("%d\n", p->data); //10 } SLTInsert(&h, p, 1000); SLTPrint(h); //30 1000 10 SListNode* q = SLTFind(h, 30); if (q) { printf("%d\n", q->data); //30 } SLTErase(&h, q); SLTPrint(h); // 1000 10 SListDestroy(&h); } int main() { test2(); }

结果：

四、链表的分类

链表是一种动态数据结构，通过指针/引用连接节点，根据节点结构和连接方式可分为以下几类：

按节点连接方向分类单链表（Singly Linked List）结构：每个节点含 数据域 和 一个指针域（指向下一节点）。特点：只能从表头向表尾遍历，插入/删除需修改前驱节点指针。图示：

双链表（Doubly Linked List）结构：每个节点含 数据域 和 两个指针域（前驱指针prev和后继指针next）。特点：可双向遍历，插入/删除无需回溯前驱节点，但内存开销略大。图示：

循环链表（Circular Linked List）结构：尾节点指针指向头节点（单循环）或头节点前驱指向尾节点（双循环）。特点：可从任意节点开始遍历，适合实现环形队列、约瑟夫问题等。图示：

按是否有头节点分类带头节点链表结构：首节点为 头节点（不存储数据或存链表长度），后续为数据节点。优势：统一空链表和非空链表的操作逻辑（无需单独处理头节点插入/删除）。图示：

不带头节点链表结构：首节点直接存储数据。劣势：插入/删除首节点时需特殊处理（修改头指针）。图示：

从上面讲解的类型中，我们可以总结一下：

链表的结构多样，总共能组合出来8种类型：

虽然链表的类型有很多种，但他们的结构体类型基本一样，都具有数据域和指针域两部分，根据上面的知识，我们可以得出本单链表为单向不带头不循环链表，而下篇文章，我将会讲解双向带头不循环链表，简称双链表，敬请期待。

  总结

  以上就是今天要讲的内容，本篇文章涉及的知识点为：实现单链表其余的函数、举实例，测试代码（包括所有代码展现）、链表的分类等知识的相关内容，为本章节知识的内容，希望大家能喜欢我的文章，谢谢各位，下篇文章，我将会讲解双向带头不循环链表，简称双链表，接下来的内容我会很快更新。

Read more

Flutter 三方库 metalink_advanced_final 的鸿蒙化适配指南 - 在 OpenHarmony 打造极致、安全的 P2P 下载与资源分发底座

Flutter 三方库 metalink_advanced_final 的鸿蒙化适配指南 - 在 OpenHarmony 打造极致、安全的 P2P 下载与资源分发底座

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 metalink_advanced_final 的鸿蒙化适配指南 - 在 OpenHarmony 打造极致、安全的 P2P 下载与资源分发底座 在大数据传输、大型游戏资源更新以及分布式固件升级场景中，传统的单点 HTTP 下载往往面临带宽压力和校验失效的风险。metalink 协议（RFC 5854）通过整合多个源地址与强校验机制，提供了一套工业级的资源分发方案。metalink_advanced_final 库为 Flutter 开发者提供了该协议的终极解析与执行引擎。本文将深度解析如何在 OpenHarmony（鸿蒙）环境下，结合鸿蒙的并发架构，完美适配这一强大的下载工具。 前言 随着鸿蒙系统（HarmonyOS）跨终端特性的普及，应用在不同设备间流转时的资源同步速度成为了用户体验的“胜负手”。metalink_advanced_final

By Ne0inhk
Flutter 三方库 simple_rsa 的鸿蒙化适配指南 - 实现非线性 RSA 密钥对生成与端侧文本加解密、支持标准公钥指纹验证与高强度数字签名实战

Flutter 三方库 simple_rsa 的鸿蒙化适配指南 - 实现非线性 RSA 密钥对生成与端侧文本加解密、支持标准公钥指纹验证与高强度数字签名实战

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 simple_rsa 的鸿蒙化适配指南 - 实现非线性 RSA 密钥对生成与端侧文本加解密、支持标准公钥指纹验证与高强度数字签名实战 前言 在进行 Flutter for OpenHarmony 的金融、政务或极致隐私通讯类应用开发时，非对称加密（Asymmetric Encryption）是保障核心数据安全（如 Token 传输、敏感配置加签）的最后一道防线。相比于对称加密，RSA 允许用户在不暴露私钥的前提下通过公钥进行加密。simple_rsa 是一款功能完备、API 极简的加密库。本文将探讨如何在鸿蒙端构建稳健的非对称加密体系。 一、原直观解析 / 概念介绍 1.1 基础原理 simple_rsa 封装了标准的 RSA

By Ne0inhk
鸿蒙金融理财全栈项目——生态合作、用户运营、数据变现

鸿蒙金融理财全栈项目——生态合作、用户运营、数据变现

《鸿蒙APP开发从入门到精通》第19篇：鸿蒙金融理财全栈项目——生态合作、用户运营、数据变现 📊🌍💰 内容承接与核心价值 这是《鸿蒙APP开发从入门到精通》的第19篇——生态合作、用户运营、数据变现篇，100%承接第18篇的风险控制、合规审计、产品创新架构，并基于金融场景的生态合作、用户运营、数据变现要求，设计并实现鸿蒙金融理财全栈项目的生态合作、用户运营、数据变现功能。 学习目标： * 掌握鸿蒙金融理财项目的生态合作设计与实现； * 实现金融机构合作、支付渠道合作、数据分析合作； * 理解用户运营在金融场景的核心设计与实现； * 实现用户增长、用户留存、用户转化； * 掌握数据变现在金融场景的设计与实现； * 实现数据服务、数据产品、数据变现； * 优化金融理财项目的用户体验（生态合作、用户运营、数据变现）。 学习重点： * 鸿蒙金融理财项目的生态合作设计原则； * 用户运营在金融场景的应用； * 数据变现在金融场景的设计要点。 一、 生态合作基础 🎯 1.1 生态合作定义 生态合作是指金融理财项目与其他金融机构、

By Ne0inhk
Flutter for OpenHarmony：cli_util 告别手写 print，用专业级日志系统构建你的 Dart 命令行工具 深度解析与鸿蒙适配指南

Flutter for OpenHarmony：cli_util 告别手写 print，用专业级日志系统构建你的 Dart 命令行工具 深度解析与鸿蒙适配指南

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 随着 Flutter 和 Dart 生态的爆发，越来越多的开发者开始使用 Dart 编写命令行工具（CLI）。从官方的 flutter 工具链，到社区的 melos、very_good_cli，Dart 因其 AOT 编译出的独立二进制文件（无需安装运行时）和极快的启动速度，已成为编写跨平台 CLI 的首选语言。 但在开发 CLI 时，我们经常面临一些底层痛点： * SDK 哪里找？ 如何准确找到当前运行环境的 Dart SDK 路径？（用于调用 dart format 或 dart pub）。 * 日志怎么打？ 简单的

By Ne0inhk