链表是一种常见且重要的数据结构,在 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/88303.shtml
繁体地址,请注明出处:http://hk.pswp.cn/pingmian/88303.shtml
英文地址,请注明出处:http://en.pswp.cn/pingmian/88303.shtml

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

相关文章

基于Matlab多特征融合的可视化指纹识别系统

针对中小规模&#xff08;百级&#xff09;指纹模板库中常见的脊线断裂、噪声干扰以及结果缺乏可解释性等难点&#xff0c;本文提出并实现了一种基于多特征融合的可视化指纹识别系统。系统整体采用模块化设计&#xff1a;在预处理阶段&#xff0c;先通过改进的灰度归一化与局部…

50天50个小项目 (Vue3 + Tailwindcss V4) ✨ | DoubleVerticalSlider(双垂直滑块)

&#x1f4c5; 我们继续 50 个小项目挑战&#xff01;—— DoubleVerticalSlider组件 仓库地址&#xff1a;https://github.com/SunACong/50-vue-projects 项目预览地址&#xff1a;https://50-vue-projects.vercel.app/ 使用 Vue 3 的 Composition API&#xff08;<scrip…

mysql join语句、全表扫描 执行优化与访问冷数据对内存命中率的影响

文章目录join执行逻辑Index Nested_Loop Join&#xff08;NLJ&#xff09;MMR(Mutli-Range Read) 优化BKA(Batched Key Access)算法Simple Nested_Loop JoinBlock Nested-Loop Join&#xff08;BLJ&#xff09;join buffer 一次放不下 驱动表join buffer优化的影响&#xff1a;…

【LeetCode100】--- 1.两数之和【复习回滚】

题目传送门 解法一&#xff1a;暴力枚举&#xff08;也是最容易想到的&#xff09; class Solution {public int[] twoSum(int[] nums, int target) {int n nums.length;for(int i 0; i < n; i){for(int j i1; j<n; j){if(nums[i] nums[j] target){return new int…

opencv提取png线段

import cv2 import matplotlib.pyplot as plt import numpy as np# 读取图像 image cv2.imread(./data/1.png) if image is None:print("无法读取图像文件") else:# 转换为灰度图像gray cv2.cvtColor(image, cv2.COLOR_BGR2GRAY)# 使用Canny边缘检测edges cv2.Can…

计算机网络:概述层---计算机网络概念解析

计算机网络的概念详解 &#x1f4c5; 更新时间&#xff1a;2025年07月6日 &#x1f3f7;️ 标签&#xff1a;计算机网络 | 网络基础 | 互联网 | TCP/IP | 路由器 文章目录前言一、计算机网络的发展历程二、什么是计算机网络&#xff1f;1. 计算机网络的基本功能2. 计算机网络的…

springMVC04-Filter过滤器与拦截器

一、Filter&#xff08;过滤器&#xff09;和 Interceptor&#xff08;拦截器&#xff09;在 SpringMVC 中&#xff0c;Filter&#xff08;过滤器&#xff09;和 Interceptor&#xff08;拦截器&#xff09;都是对请求和响应进行预处理和后处理的重要工具&#xff0c;但它们存在…

STM32第十九天 ESP8266-01S和电脑实现串口通信(2)

1&#xff1a;UDP 传输UDP 传输不不区分 server 或者 client &#xff0c;由指令 ATCIPSTART 建⽴立传输。 1. 配置 WiFi 模式 ATCWMODE3 // softAPstation mode 响应 : OK 2. 连接路路由器器 ATCWJAP"SSID","password" // SSID and password of router 响…

大健康IP如何用合规运营打破“信任危机”|创客匠人

一、行业乱象下的信任裂痕当前大健康领域私域直播乱象频发&#xff0c;部分机构利用“假专家义诊”“限量抢购”等话术&#xff0c;将低成本保健品高价卖给老人&#xff0c;甚至有技术公司提供“全链路坑老方案”&#xff0c;加剧行业信任危机。这种短视行为不仅损害消费者权益…

MySQL(122)如何解决慢查询问题?

解决慢查询问题通常涉及到多种技术和方法&#xff0c;以确保数据库查询的高效性和响应速度。以下是详细步骤和示例代码&#xff0c;阐述如何解决慢查询问题。 一. 慢查询的常见原因 缺少索引&#xff1a;查询未使用索引或索引未优化。查询不当&#xff1a;查询语句本身书写不合…

esp32在vscode中仿真调试

此方法可以用在具有usb serial jtag功能的esp32芯片用&#xff0c;支持型号&#xff1a; ESP32-C3 ESP32-S3 ESP32-C6 ESP32-H2 ESP32-C5 USB Serial JTAG功能介绍&#xff1a; 从硬件角度&#xff1a; 它是ESP32芯片内置的硬件功能 不是一个独立的物理接口 是通过USB接口实…

蓝桥云课 矩形切割-Java

目录 题目链接 题目 解题思路 代码 题目链接 竞赛中心 - 蓝桥云课 题目 解题思路 找最大的正方形就是大边-n个小边&#xff0c;直至相等或者小于1 代码 import java.util.Scanner; // 1:无需package // 2: 类名必须Main, 不可修改public class Main {public static voi…

PostgreSQL 锁等待监控,查找等待中的锁

直接贴SQLWITH RECURSIVE l AS (SELECT pid, locktype, mode, granted, ROW(locktype,database,relation,page,tuple,virtualxid,transactionid,classid,objid,objsubid) objFROM pg_locks ), pairs AS (SELECT w.pid waiter, l.pid locker, l.obj, l.modeFROM l wJOIN l ON l.…

Elasticsearch 字符串包含子字符串:高级查询技巧

作者&#xff1a;来自 Elastic Justin Castilla 想要获得 Elastic 认证&#xff1f;看看下一次 Elasticsearch Engineer 培训什么时候开始吧&#xff01; Elasticsearch 拥有大量新功能&#xff0c;可以帮助你为你的使用场景构建最佳的搜索解决方案。深入了解我们的示例 noteb…

Vue、Laravel 项目初始化命令对比 / curl 命令/ CORS 机制总结与案例

前言一个疑问衍生出另一个疑问再衍生出又一个疑问&#xff0c;于是有了这篇文章。一、Vue 项目初始化命令 基于 Vite 创建 Vue 项目 命令&#xff1a;npm create vitelatest my-project -- --template vue适用场景&#xff1a;需轻量级、高速开发环境关键点&#xff1a;使用 Vi…

Jenkins 流水线配置

Jenkinsfile dsl文件:pipeline {// 指定任务在哪个集群节点执行agent any// 声明全局变量environment {keyvalueAPPLICATION_NAMEspringboot-demo // 项目名称HOST_PORT7777 // 宿主机暴露服务端口CONTAINER_PORT8080 // 容器内部服务端口…

服务器重装后如何“复活”旧硬盘上的 Anaconda 环境?—— 一次完整的排错与恢复记录

目录 摘要 一、 背景&#xff1a;熟悉的陌生人 二、 问题浮现&#xff1a;一次次失败的尝试 问题一&#xff1a;source activate 失效&#xff0c;被写死的旧路径 问题二&#xff1a;官方安装器修复失败&#xff0c;神秘的“进程池损坏” 问题三&#xff1a;核心脚本也“背…

Redis的多并发实际业务场景下的使用分析:布隆过滤器

文章目录前言什么是布隆过滤器项目中引入布隆过滤器与缓存结合的最佳实践场景&#xff1a;高并发用户访问商品详情页&#xff08;防止缓存穿透&#xff09;总结&#xff1a;前言 okok 我们已经学完了 所有的redis中的常用的数据结构 下面就是进阶 我会用一系列的例子 去讲解 如…

【AI】人工智能领域关键术语全解析

一、前言 人工智能&#xff08;AI&#xff09;作为当今最热门的技术领域之一&#xff0c;正在深刻改变着我们的生活和工作方式。然而&#xff0c;对于初学者或非技术背景的人士来说&#xff0c;理解AI领域的专业术语可能是一项挑战。本文旨在全面解析人工智能领域的关键术语&a…

【Linux基础知识系列】第四十三篇 - 基础正则表达式与 grep/sed

在Linux系统中&#xff0c;正则表达式是一种强大的文本处理工具&#xff0c;广泛用于文本搜索、替换和批量处理。通过掌握基础正则表达式的语法&#xff0c;结合grep和sed命令&#xff0c;用户可以高效地完成复杂的文本处理任务。无论是数据分析师、软件开发者还是系统管理员&a…