链表是一种常见且重要的数据结构,在 C 语言中,它通过指针将一系列的节点连接起来,每个节点可以存储不同类型的数据。相比数组,链表在插入和删除元素时不需要移动大量数据,具有更好的灵活性,尤其适合处理动态变化的数据集合。

       当然,既然链表涉及到指针,而且与指针关系密切,所以只有当我们在对于指针有了一定扎实的了解后,才能更好、更轻松的了解链表这一新概念。然而,我认为对于链表这样一类概念来说,增删查改是最好去了解其本质的方法,所以今天,我们来看看链表的增删查改

       首先,我们来看看比较简单的头插、头删、尾插、尾删这四个:

一.前期准备:

对于前期准备我已经老调重弹了很多遍,这里不再过多赘述,首先最关键的就是链表节点的定义

1. 链表节点的定义

       链表由一个个节点组成,每个节点包含两部分:数据域和指针域。数据域用来存储数据,指针域指向下一个节点。所以我们选择用结构体去定义节点:

typedef int SLTDataType;typedef struct SListNode
{SLTDataType data;struct SListNode* next;
}SLTNode;

代码解释:

1. typedef int SLTDataType:

       这行代码定义了一个类型别名 SLTDataType,它实际上是 int 的同义词。也就说可以选择直接在结构体内部用 int data;之所以这样做的目的是:

  • 提高代码可维护性:如果后续需要存储其他类型(如 floatchar*),只需修改这一行,而不必改动整个代码。
  • 增强可读性SLTDataType 比直接用 int 更直观,表示这是链表节点的数据类型。

2. struct SListNode 结构体定义

这个结构体定义了单链表的节点结构,包含两个成员:

SLTDataType data;

  • 数据域,用于存储具体的数据。
  • 由于 SLTDataType 被 typedef 为 int,因此这里实际上存储的是整数。

struct SListNode* next;

  • 指针域,指向下一个节点的地址。
  • 这是实现链表连接的关键:每个节点通过 next 指针指向下一个节点,直到最后一个节点的 next 为 NULL,表示链表结束。
  • 并非一个结构体,是一个结构体类型的指针

3. SLTNode;

这行代码将 struct SListNode 重命名为 SLTNode,目的是简化类型名。

  • 之后可以直接用 SLTNode 声明变量,而不需要写 struct SListNode
  • 例如:SLTNode* node = malloc(sizeof(SLTNode));

二.打印函数:

为了更好地在测试文件里测试函数的可行性,我们首先写一个打印函数。

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

代码解释:

1. 定义遍历指针

SLTNode* cur = phead;
  • 创建一个临时指针 cur(current 的缩写,意为 “当前节点”),并将其初始化为头指针 phead
  • 作用:用 cur 遍历链表,避免直接修改头指针 phead(如果直接移动 phead,会导致链表 “头节点丢失”,无法再访问整个链表)。

2. 遍历链表并打印数据

while (cur)
  • 循环条件 cur 等价于 cur != NULL,表示:只要当前节点 cur 不是空指针(即还没遍历到链表末尾),就继续循环。
printf("%d->", cur->data);
  • 打印当前节点 cur 的数据域 data%d 对应 SLTDataType 为 int 的情况),并在后面加上 -> 符号,模拟链表的 “指向” 关系。
cur = cur->next;
  • 让 cur 指向当前节点的下一个节点(通过指针域 next),实现遍历的 “移动”。

3. 打印链表末尾标识

printf("NULL\n");

  • 当循环结束时(cur 变为 NULL,即遍历到链表末尾),打印 NULL,表示链表的终止。

三.尾插函数:

void SLTPushBack(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (*pphead == NULL){*pphead = newnode;}else{//找尾:SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

代码解释:

函数定义解析:

void SLTPushBack(SLTNode** pphead, SLTDataType x)
  • 参数
    • SLTNode** pphead:指向头指针的指针(二级指针)。因为尾插可能改变头指针(当链表为空时),必须通过二级指针修改原头指针的值。
    • SLTDataType x:要插入的数据(类型为 int,因为 SLTDataType 被 typedef 为 int)。
  • 返回值void,只执行插入操作,不返回数据。

函数体详解

1. 断言检查

assert(pphead);
  • 确保传入的二级指针 pphead 不为空(即头指针的地址必须有效)。
  • 若 pphead 为空,程序会触发断言错误并终止(防止野指针)。

2. 创建新节点

SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
if (newnode == NULL)
{perror("malloc fail");return;
}
newnode->data = x;
newnode->next = NULL;
  • 内存分配:用 malloc 动态分配一个节点大小的内存空间。
  • 错误处理:若 malloc 失败(返回 NULL),打印错误信息并提前返回。
  • 初始化节点:将数据 x 存入新节点的数据域 data,并将指针域 next 置为 NULL(因为新节点将成为尾节点)。

3. 处理链表为空的情况

if (*pphead == NULL)
{*pphead = newnode;
}
  • 若链表为空(头指针 *pphead 为 NULL),直接让头指针指向新节点。
  • 关键点:通过 *pphead 修改原头指针的值,使新节点成为链表的第一个节点。

4. 链表不为空时的尾插操作

else
{SLTNode* tail = *pphead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;
}

  • 遍历找尾:从链表头开始,用 tail 指针遍历到最后一个节点(即 tail->next == NULL 的节点)。
  • 插入新节点:将尾节点的 next 指针指向新节点 newnode,使新节点成为新的尾节点。

函数定义进阶解析:

到这里相信很多人仍然对于二级指针那个点感到糊涂:为什么前面打印函数定义时就是一级指针,而到了插入函数开始就用二级指针了呢?下面我先顺着原始思路去解释,认为和打印函数一样用的是一级指针的代码和测试代码会如下:

void SLTPushBack(SLTNode* phead, SLTDataType x)
{SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));if (newnode == NULL){perror("malloc fail");return;}newnode->data = x;newnode->next = NULL;if (phead == NULL){phead = newnode;}else{//找尾:SLTNode* tail = phead;while (tail->next != NULL){tail = tail->next;}tail->next = newnode;}
}

void TestSList1()
{SLTNode* plist = NULL;SLTPushBack(plist, 1);SLTPushBack(plist, 2);SLTPushBack(plist, 3);SLTPushBack(plist, 4);SLTPrint(plist);
}int main()
{TestSList1();return 0;
}

然而这样最终编译结果为:

我们可以看到,结果好像不是我们想要的,这是因为:

问题核心:形参与实参的区别

void SLTPushBack(SLTNode* phead, SLTDataType x) 
  • 参数 phead 是实参的副本:当调用 SLTPushBack(plist, 1) 时,函数内部的 phead 是 plist 的拷贝,它们指向同一块内存,但本身是两个不同的变量。
  • 修改 phead 不影响实参 plist:在函数内部,当链表为空时执行 phead = newnode,只是修改了副本 phead 的值,原头指针 plist 仍为 NULL

示例分析:

SLTNode* plist = NULL;  // plist 指向 NULL

第一次调用 SLTPushBack(plist, 1)

  1. 传值调用phead 是 plist 的副本,初始值为 NULL
  2. 创建新节点newnode 指向新分配的节点(数据为 1,next 为 NULL)。
  3. 执行 phead = newnodephead 指向新节点,但 plist 仍为 NULL因为 phead 是副本)。
  4. 函数返回phead 被销毁,原 plist 未被修改,仍为 NULL

后续调用 SLTPushBack(plist, 2)SLTPushBack(plist, 3) 等:

  • 每次都重复上述过程,plist 始终为 NULL,所有新节点都无法连接到链表中。
  • 最终结果:链表为空,SLTPrint(plist) 输出 NULL

正确做法:使用二级指针

void SLTPushBack(SLTNode** pphead, SLTDataType x)

  • 传址调用pphead 是指向头指针 plist 的指针,通过 *pphead 可以直接修改原头指针。
  • 修改 *pphead 影响实参:当链表为空时,*pphead = newnode 直接将原头指针 plist 指向新节点。

 明白了这点之后,后续函数该用一级指针还是二级指针我们就清楚了。

四.新增节点函数:

完成尾插函数以后,我们发现需要开辟新的节点,我们也能预想到,后续函数也会用到新增节点,所以我们不妨封装这个函数,简化代码量:

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

之后在开辟时,直接调用即可;

五.头插函数:

void SLTPushFront(SLTNode** pphead, SLTDataType x)
{assert(pphead);SLTNode* newnode = BuySLTNode(x);newnode->next = *pphead;*pphead = newnode;
}

代码解释: 

1. 断言检查

assert(pphead);
  • 确保传入的二级指针 pphead 不为空(即头指针的地址必须有效)。
  • 若 pphead 为空,程序会触发断言错误并终止(防止野指针)。

2. 创建新节点

SLTNode* newnode = BuySLTNode(x);
  • 调用 BuySLTNode 函数,创建一个新节点并初始化为数据 xnext 指针为 NULL

3. 插入新节点到头部

newnode->next = *pphead;
*pphead = newnode;

  • 关键点

    1. 将新节点的 next 指针指向原头节点(*pphead)。
    2. 将原头指针 *pphead 更新为新节点 newnode,使新节点成为链表的新头。
  • 无论链表是否为空,这两行代码都能正确工作

    • 若链表为空(*pphead == NULL),新节点的 next 为 NULL,并成为唯一节点。
    • 若链表非空,新节点的 next 指向原头节点,实现头插。

头插函数很简约,理解起来也没什么大问题;

六.尾删函数:

void SLTPopBack(SLTNode** pphead)
{//暴力检查:assert(pphead);assert(*pphead);//只有一个节点;// 有多个节点;if ((*pphead)->next == NULL){free(*pphead);*pphead = NULL;}else{//找尾:SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;}
}

代码解释: 

1. 断言检查

assert(pphead);
assert(*pphead);
  • 第一个断言:确保传入的二级指针 pphead 不为空(防止野指针)。
  • 第二个断言:确保链表不为空(*pphead != NULL)。若链表为空时调用此函数,会触发断言错误,终止程序。

2. 处理只有一个节点的情况

if ((*pphead)->next == NULL)
{free(*pphead);*pphead = NULL;
}
  • 若链表只有一个节点(即头节点的 next 为 NULL):
    1. 释放头节点的内存(free(*pphead))。
    2. 将头指针置为 NULL*pphead = NULL),表示链表已空。

3. 处理多个节点的情况

else
{SLTNode* prev = NULL;SLTNode* tail = *pphead;while (tail->next != NULL){prev = tail;tail = tail->next;}free(tail);tail = NULL;prev->next = NULL;
}
  • 遍历找尾
    • tail 指针遍历到最后一个节点,prev 始终指向 tail 的前一个节点。
  • 释放尾节点
    1. 释放 tail 指向的尾节点(free(tail))。
    2. 将 tail 置为 NULL(这一步是多余的,后面会解释)。
  • 更新链表
    将 prev 的 next 置为 NULL,使 prev 成为新的尾节点。
  • 注意对于这段代码,while内的代码逻辑极其重要,不能找到尾以后就直接删去,这样将导致删完以后,尾部出现随机值的情况,需要格外注意!!!

但其实这段代码还存在一点小问题:

存在的问题:

free(tail);
tail = NULL;  // 这一步无效!
  • 问题tail = NULL 仅将局部变量 tail 置为 NULL,无法影响原链表。
  • 原因tail 是局部指针,free(tail) 后内存已释放,但 tail 本身仍保存着被释放内存的地址。将 tail 置为 NULL 只是修改了局部变量,对链表无影响。
  • 修正:删除 tail = NULL 这一行,因为它不影响链表结构,且是多余操作。

七.头删函数:

void SLTPopFront(SLTNode** pphead)
{//暴力检查:assert(pphead);assert(*pphead);SLTNode* first = *pphead;*pphead = first->next;free(first);first = NULL;
}

代码解释: 

1. 断言检查

assert(pphead);
assert(*pphead);
  • 第一个断言:确保传入的二级指针 pphead 不为空(防止野指针)。
  • 第二个断言:确保链表不为空(*pphead != NULL)。若链表为空时调用此函数,会触发断言错误,终止程序。

2. 保存原头节点并更新头指针

SLTNode* first = *pphead;
*pphead = first->next;

  • 关键点
    1. 用临时指针 first 保存原头节点的地址。
    2. 将头指针 *pphead 更新为原头节点的下一个节点(first->next)。
  • 处理单节点情况:若链表只有一个节点,first->next 为 NULL,更新后头指针 *pphead 变为 NULL,链表为空。

3. 释放原头节点的内存

free(first);
first = NULL;

  • 释放内存:调用 free(first) 释放原头节点占用的内存。
  • 置空局部指针:将 first 置为 NULL(这一步是可选的,因为 first 是局部变量,函数返回后会被销毁)。

       这样一来,我们基础的尾插、尾删、头插、头删都已经讲完了,除了上面我们所关注到的细节点以外,还有一个点就是断言我们发现有的地方加入了断言,有的地方没有,有的地方只有一个,而有的地方却有两个,我们来谈谈断言:

断言:

在 C 语言链表操作中,断言(assert) 是一种强大的调试工具,用于确保程序运行时的某些条件始终为真。

一、断言的本质与作用

断言是 C 标准库 <assert.h> 提供的宏,定义为:

void assert(int expression);

  • 功能:若 expression 为假(0),程序会立即终止,并打印错误信息(包括断言失败的位置、表达式内容)。
  • 目的:在开发和测试阶段尽早发现逻辑错误,避免程序在错误状态下继续运行导致更严重的问题。

二、链表操作中常见的断言场景

1. 检查指针有效性

assert(pphead);  // 确保二级指针(头指针的地址)不为NULL
  • 场景:在需要修改头指针的函数中(如 SLTPushBackSLTPopFront),若传入的 pphead 为 NULL,后续解引用 *pphead 会导致野指针错误。
  • 错误示例
    SLTNode* plist = NULL;
    SLTPushBack(NULL, 1);  // 错误:传入NULL作为pphead
    

2. 检查链表非空

assert(*pphead);  // 确保链表不为空(头指针不为NULL)
  • 场景:在删除操作(如 SLTPopBackSLTPopFront)中,若链表为空,删除操作无意义且可能导致崩溃。
  • 错误示例
    SLTNode* plist = NULL;
    SLTPopFront(&plist);  // 错误:对空链表执行头删
    

三、断言的优缺点

优点:

  1. 快速定位错误:断言失败时会直接打印错误位置和表达式,无需调试器即可快速发现问题。
  2. 强制约束条件:明确函数的前置条件(如 “链表必须非空”),提高代码安全性。
  3. 零运行时开销:在发布版本中可通过 #define NDEBUG 禁用断言,消除性能影响。

缺点:

  1. 仅在调试阶段有效:发布版本中断言被禁用,无法检查运行时错误。
  2. 可能掩盖真实问题:若断言条件过于严格,可能导致程序频繁崩溃,需谨慎设置。

所以,链表细节满满,需要大家多花时间去了解,剩下的一些函数,将会放到下一篇博客中,敬请期待......

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.pswp.cn/pingmian/88756.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/88756.shtml
英文地址,请注明出处:http://en.pswp.cn/pingmian/88756.shtml

如若内容造成侵权/违法违规/事实不符,请联系英文站点网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

archive/tar: unknown file mode ?rwxr-xr-x

这个是我在docker build报错的&#xff0c;这是一个node.js项目。我猜你也是一个node.js下的项目&#xff0c;或者前端项目。 解决方法&#xff1a; .dockerignore里面写一下node_modules就行了。 未能解决&#xff1a;archive/tar&#xff1a;未知文件模式&#xff1f;rwxr-…

【前端】ikun-markdown: 纯js实现markdown到富文本html的转换库

文章目录背景界面当前支持的 Markdown 语法不支持的Markdown 语法代码节选背景 出于兴趣,我使用js实现了一个 markdown语法 -> ast语法树 -> html富文本的库, 其速度应当慢于正则实现的同类js库, 但是语法扩展性更好, 嵌套列表处理起来更方便. 界面 基于此js实现vue组…

【echarts踩坑记录】为什么第二个Y轴最大值不整洁

目录问题复现示意图&#xff1a;解决方法有以下几种&#xff1a;1. 在y轴配置中手动设置max属性&#xff1a;2. 使用ECharts提供的坐标轴标签格式化功能&#xff1a;&#x1f680;写在最后问题复现示意图&#xff1a; 今天在用echarts图表的时候&#xff0c;出现了一个小问题。…

Duplicate cleaner pro 的使用技巧

Duplicate cleaner pro 的使用技巧前言文件去重基本介绍经验之谈目录结构修改盘符起因方法手动分配方法‌数据修改方法安装sqlite-web修改数据库GPU加速安装驱动获取驱动和硬件信息安装CUDA配置环境变量&#xff08;如果是自定义安装&#xff09;创建程序<1>获取参数和命…

数字孪生技术引领UI前端设计新趋势:增强现实与虚拟现实的融合应用

hello宝子们...我们是艾斯视觉擅长ui设计和前端数字孪生、大数据、三维建模、三维动画10年经验!希望我的分享能帮助到您!如需帮助可以评论关注私信我们一起探讨!致敬感谢感恩!一、引言&#xff1a;AR 与 VR 的 “割裂” 与数字孪生的 “融合” 契机增强现实&#xff08;AR&…

Qt使用dump文件记录并查找软件奔溃信息详细教程

Qt使用dump文件记录并查找软件奔溃信息一、dump文件概述1、dump文件的基本概念2、dump文件的常见类型3、dump文件的分析工具4、dump文件的应用场景二、具体实现步骤1、下载dbghelp库2、将库添加到自己的工程中3、main.cpp添加代码记录奔溃日志4、编写测试代码5、测试6、结果查看…

UI前端与数字孪生结合案例分享:智慧城市的智慧能源管理系统

hello宝子们...我们是艾斯视觉擅长ui设计、前端开发、数字孪生、大数据、三维建模、三维动画10年经验!希望我的分享能帮助到您!如需帮助可以评论关注私信我们一起探讨!致敬感谢感恩!一、引言&#xff1a;能源管理的 “数字孪生革命”智慧城市的能源系统正面临 “供需失衡、损耗…

Android 16系统源码_SplashScreen窗口的创建流程(一)

一 点击桌面图标触发SplashScreen 1.1 点击桌面图标打开应用 点击桌面的短信图标&#xff0c;然后打开短信页面&#xff0c;使用winscope获取数据。从点击短信图标到应用内容完全展开&#xff0c;中间有出现一个标题带有“Splash Screen”字符串的窗口。 二 Splash Screen窗口创…

线性代数学习笔记

矩阵 矩阵是一种非常重要的数学对象,它通常由一个由数字排成的矩形阵列来定义。一个矩阵由若干行和若干列组成,被称为矩阵的行数和列数。一般情况下,矩阵的行数和列数分别用 n n n 和 m m m 表示。<

2025.7.13总结

每次写日记&#xff0c;总觉得自我感受不是很好&#xff0c;脑子总会有许多消极思想。在网上&#xff0c;我曾看到一个关于“人生是一场巨大的事与愿违”&#xff0c;可能&#xff0c;真的是这个样子吧。以前的我&#xff0c;有上进心&#xff0c;有目标感&#xff0c;脚踏实地…

linux-网络-网络管理发展历程

Linux 的网络管理机制经历了多个阶段的发展&#xff0c;从早期的静态配置到现代动态管理工具的出现&#xff0c;反映了 Linux 系统在网络连接、自动化和用户体验方面的不断演进。以下是 Linux 网络管理发展的主要阶段&#xff1a;1. 早期的静态网络配置&#xff08;传统方式&am…

华为 GaussDB :技术特性、应用局限与市场争议

3-5月间&#xff0c;老夫在某学校带了这门课&#xff0c;简单总结一下课程外的看法&#xff1a;华为 GaussDB 作为华为云生态中的核心数据库产品&#xff0c;自推出以来便承载着华为在数据基础设施领域的战略野心。其技术路线既延续了开源数据库的兼容性优势&#xff0c;又深度…

从零开始学习深度学习—水果分类之PyQt5App

一、项目背景⭐&#xff1a;本项目是“从零开始学习深度学习”系列中的第二个实战项目&#xff0c;旨在实现第一个简易App(图像分类任务——水果分类)&#xff0c;进一步地落地AI模型应用&#xff0c;帮助初学者初步了解模型落地。基于PyQt5图形界面的水果图像分类系统&#xf…

小架构step系列13:测试用例的加载

1 概述测试用例的编写要有一些基础的规范&#xff0c;在本文先定义文件名称和测试用例方法名的规范。2 文件加载原理先从源码来看一下测试用例的文件加载原理。2.1 文件的匹配主要是通过注解来扫描测试用例。// 在IDEA测试用例启动时&#xff0c;调用junit-platform-launcher-x…

K8S的CNI之calico插件升级至3.30.2

前言宿主机ping不通K8S的pod&#xff0c;一直存在丢包的现象&#xff0c;排查了防火墙、日志、详细信息等没发现什么问题&#xff0c;最后搜索发现&#xff0c;是因为把K8S的版本升级之后&#xff0c;旧版本的CNI插件不适配原因导致的&#xff0c;于是就把calico也一并升级并且…

Spring Boot RESTful API 设计指南:查询接口规范与最佳实践

Spring Boot RESTful API 设计指南&#xff1a;查询接口规范与最佳实践 引言 在 Spring Boot 开发中&#xff0c;查询接口的设计直接影响着系统的可用性、可维护性和性能。本文将深入探讨如何规范设计查询接口&#xff0c;包括 GET/POST 的选择、参数定义、校验规则等&#xff…

ctfshow萌新题集

记录一下前半部分是能自己写出来的&#xff0c;后半部分是需要提示的&#xff0c;感觉自己归来两年仍是萌新 misc部分 知识点 base家族密文特征 Base16 (Hex) 字符集&#xff1a;0-9, A-F&#xff08;不区分大小写&#xff09;。特征&#xff1a; 长度是 2 的倍数&#xff…

2025年语言处理、大数据与人机交互国际会议(DHCI 2025)

&#x1f310;&#x1f916;&#x1f9e0; 语言处理、大数据与人机交互&#xff1a;探索智能未来 —— DHCI 2025国际会议2025年语言处理、大数据与人机交互国际会议&#xff08;DHCI 2025&#xff09; 将于2025年在中国重庆市召开。这次盛会将汇聚全球顶尖专家、学者及行业领袖…

RIP实验以及核心原理

RIP&#xff08;Routing Information Protocol&#xff0c;路由信息协议&#xff09;是一种内部网关协议&#xff0c;基于距离矢量算法&#xff0c;用于在自治系统内交换路由信息。RIP 核心原理距离矢量算法&#xff1a;RIP 使用跳数作为路径选择的唯一度量标准。每经过一个路由…

基于大数据的电力系统故障诊断技术研究

摘要本文提出了一种创新性的基于大数据技术的电力系统故障诊断方法&#xff0c;该方法通过整合先进的机器学习算法和交互式可视化技术&#xff0c;实现了对电力系统各类故障的智能化识别与深度分析。该系统采用随机森林算法作为核心分类器&#xff0c;构建了高精度的故障分类模…