深入浅出链表

目录

1.链表的基本概念及结构

1.1基本概念

1.2结构

2.链表的分类

3.链表的实现(循环链表增删查改实现)

1.动态申请节点(结点)​编辑

2.单链表打印

3.单链表尾插

4.单链表头插

5.单链表尾删

6.单链表头删

7.单链表查找

8.在指定位置之前插入数据

9.在指定位置之后插入数据

10.删除pos节点

11.删除pos之后的节点

12.销毁链表


1.链表的基本概念及结构

        链表是一种常见的基础数据结构,它由一系列节点(Node)组成,每个节点包含数据和到下一个节点的引用(指针)。以下是链表的基本概念及其结构:

1.1基本概念

  1. 节点(Node):链表的基本单元,每个节点包含两部分,一部分是存储数据的域(称为数据域),另一部分是存储下一个节点地址的域(称为指针域或链接域)。

  2. 头节点(Head):链表的第一个节点,通常用于表示整个链表。

  3. 尾节点(Tail):链表的最后一个节点,其指针域通常指向NULL,表示链表的结束。

  4. 链表的长度:链表中节点的数量。

  5. 链表的遍历:按照节点间的链接顺序访问链表中的每个节点。

  6. 动态性:链表的大小不是固定的,可以在运行时动态地增加或减少节点。

1.2结构

        在C语言中,链表节点通常使用结构体(struct)来定义。以下是链表节点的一个基本结构:

链表的结构就像是火车一样一节一节的连在一起。

但是每个节点的地址并不像顺序表一样是连续的,而是随机存储的,因此每个节点才需要下一个节点的地址来找到下一节点。

2.链表的分类

  1. 单向链表(Singly Linked List):

    • 每个节点包含一个数据域和一个指向下一个节点的指针。
    • 遍历链表只能从头节点开始,并且只能向一个方向进行。
  2. 双向链表(Doubly Linked List):

    • 每个节点包含一个数据域、一个指向前一个节点的指针和一个指向下一个节点的指针。
    • 可以从两个方向遍历链表。
  3. 循环链表(Circular Linked List):

    • 单向链表的变种,最后一个节点的指针指向头节点,形成一个环。
    • 可以从任意节点开始遍历整个链表。
  4. 双向循环链表(Doubly Circular Linked List):

    • 双向链表的变种,头节点的前一个指针指向最后一个节点,最后一个节点的下一个指针指向头节点,形成一个环。
    • 可以从任意节点开始,向前或向后遍历整个链表。

3.链表的实现(循环链表增删查改实现)

1.动态申请节点(结点)

  • SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));:使用malloc函数动态分配一个SLTNode大小的内存块,并将其强制转换为SLTNode*类型的指针。sizeof(SLTNode)获取SLTNode结构体的大小。

  • if (newnode == NULL):检查malloc是否成功分配了内存。如果newnodeNULL,说明内存分配失败。

  • perror("malloc fail!");:如果内存分配失败,使用perror函数打印错误消息。

  • exit(1);:如果内存分配失败,终止程序执行,返回错误代码1

  • newnode->data = x;:将传入的参数x赋值给新节点的数据域。

  • newnode->next = NULL;:将新节点的指针域初始化为NULL,表示当前节点后面没有其他节点。

  • return newnode;:返回新创建的节点。

2.单链表打印

3.单链表尾插

  • assert(pphead);:使用assert宏来确保传入的头节点指针的指针不是NULL。如果ppheadNULL,程序将终止执行。

  • SLTNode* newnode = SLTBuyNode(x);:调用之前定义的SLTBuyNode函数来创建一个新的节点,并将数据x存储在新节点的数据域。

  • if (*pphead == NULL):检查链表是否为空。如果链表为空(即头节点指针为NULL),则将新节点设置为头节点。

  • else:如果链表不为空,则需要找到链表的最后一个节点。

  • SLTNode* ptail = *pphead;:初始化一个指针ptail,指向头节点。

  • while (ptail->next):遍历链表,直到找到最后一个节点(即节点的next指针为NULL)。

  • ptail = ptail->next;:在循环中,将ptail移动到下一个节点。

  • ptail->next = newnode;:当找到最后一个节点时,将其next指针指向新创建的节点,从而将新节点添加到链表的末尾。

4.单链表头插

  • assert(pphead);:使用assert宏来确保传入的pphead不是NULL。如果ppheadNULL,程序将在这里终止。

  • SLTNode* newnode = SLTBuyNode(x);:调用SLTBuyNode函数创建一个新的节点,并将数据x存储在新节点的数据域中。

  • newnode->next = *pphead;:将新节点的next指针指向原来的头节点。这一步是为了将新节点插入到链表的头部。

  • *pphead = newnode;:更新头节点指针,使其指向新创建的节点。这样,新节点就成为了链表的新头部。

5.单链表尾删

这个接口的实现一开始先要判断链表是否为单节点链表,如果是则直接释放头节点,不是则进行相应的操作。

  • assert(pphead && *pphead);:使用assert宏来确保传入的pphead不是NULL,且链表不为空。如果这些条件不满足,程序将在这里终止。

  • if ((*pphead)->next == NULL):检查链表是否只有一个节点。如果是,直接释放这个节点,并将头节点指针设置为NULL

  • else:如果链表有多个节点,需要遍历链表找到最后一个节点。

  • while (ptail->next):遍历链表直到ptail指向最后一个节点。

  • free(ptail);:释放最后一个节点的内存。

  • ptail = NULL;:将ptail指针设置为NULL,防止野指针。

  • prev->next = NULL;:将倒数第二个节点的next指针设置为NULL,断开与已删除节点的连接。

6.单链表头删

这里的(*pphead)->next不能写成*pphead->next 因为->预算符优先级是高于*的。

  • assert(pphead && *pphead);:使用assert宏来确保传入的pphead不是NULL,且链表不为空。如果这些条件不满足,程序将在这里终止。

  • SLTNode* next = (*pphead)->next;:保存头节点的下一个节点指针。这是因为一旦释放头节点,我们就无法访问链表的其余部分。

  • free(*pphead);:释放头节点的内存。

  • *pphead = next;:更新头节点指针,使其指向原来的第二个节点(现在成为新的头节点)。

7.单链表查找

  • assert(phead);:使用assert宏来确保传入的phead不是NULL。如果pheadNULL,程序将在这里终止。

  • SLTNode* plist = phead;:初始化一个指针plist,使其指向头节点。

  • while (plist):开始循环,当plist不为NULL时继续执行。

  • if (plist->data == x):检查当前节点的数据是否与要查找的值x匹配。

  • return plist;:如果找到匹配的节点,返回该节点。

  • plist = plist->next;:如果没有找到匹配的节点,移动plist到下一个节点。

  • return NULL;:如果在链表中没有找到匹配的节点,返回NULL

8.在指定位置之前插入数据

9.在指定位置之后插入数据

  • assert(pphead && *pphead);:使用assert宏来确保传入的pphead不是NULL,且链表不为空。如果这些条件不满足,程序将在这里终止。

  • assert(pos);:使用assert宏来确保传入的pos不是NULL。如果posNULL,程序将在这里终止。

  • SLTNode* newnode = SLTBuyNode(x);:调用SLTBuyNode函数创建一个新的节点,并将数据x存储在新节点的数据域中。

  • if (pos == *pphead):检查插入的位置是否是头节点。如果是,使用SLTPushFront函数在头节点位置插入新节点。

  • else:如果插入的位置不是头节点,需要找到pos的前一个节点。

  • SLTNode* prev = *pphead;:初始化prev指针指向头节点。

  • while (prev->next != pos):遍历链表直到找到pos的前一个节点。

  • newnode->next = pos;:将新节点的next指针指向pos

  • prev->next = newnode;:将pos的前一个节点的next指针指向新节点。

10.删除pos节点

  • assert(pphead && *pphead);:使用assert宏来确保传入的pphead不是NULL,且链表不为空。如果这些条件不满足,程序将在这里终止。

  • assert(pos);:使用assert宏来确保传入的pos不是NULL。如果posNULL,程序将在这里终止。

  • if (pos == *pphead):检查要删除的节点是否是头节点。如果是,使用SLTPopFront函数执行头删操作。

  • else:如果要删除的节点不是头节点,需要找到该节点的前一个节点。

  • SLTNode* prev = *pphead;:初始化prev指针指向头节点。

  • while (prev->next != pos):遍历链表直到找到pos的前一个节点。

  • prev->next = pos->next;:将pos的前一个节点的next指针指向pos的下一个节点,完成删除操作。

  • free(pos);:释放pos节点的内存。

  • pos = NULL;:将pos指针设置为NULL,防止野指针。

11.删除pos之后的节点

  • assert(pos);:使用assert宏来确保传入的pos不是NULL。如果posNULL,程序将在这里终止。

  • SLTNode* newnode = SLTBuyNode(x);:调用SLTBuyNode函数创建一个新的节点,并将数据x存储在新节点的数据域中。

  • newnode->next = pos->next;:将新节点的next指针指向pos的下一个节点,这样新节点就位于pos的后面。

  • pos->next = newnode;:将posnext指针指向新节点,完成新节点的插入操作。

12.销毁链表

  • assert(pphead && *pphead);:使用assert宏来确保传入的pphead不是NULL,且链表不为空。如果这些条件不满足,程序将在这里终止。

  • SLTNode* pcur = *pphead;:初始化一个指针pcur,使其指向头节点。

  • while (pcur):开始循环,当pcur不为NULL时继续执行。

  • SLTNode* next = pcur->next;:保存pcur的下一个节点的指针,因为pcur将被释放。

  • free(pcur);:释放pcur节点的内存。

  • pcur = next;:移动pcur指针到下一个节点。

  • *pphead = NULL;:循环结束后,将头指针设置为NULL,表示链表已被销毁。

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

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

相关文章

如何应对突发技术故障和危机:开发团队的应急策略

开发团队如何应对突发的技术故障和危机? 在数字化时代,软件服务的稳定性对于企业至关重要。然而,即使是大型平台,如网易云音乐,也可能遇到突发的技术故障。网页端出现502 Bad Gateway 报错,且App也无法正常…

亚信科技转型持久战:扎根行业大模型,深耕行业数字化

有人说:“AI大模型时代,每个行业和产品都值得重新做一遍。” 深以为然。自大模型2023年迅速崛起以来,AI技术不断取得突破,并开始深刻影响多个领域。这其中,AI大模型如何从通用走向垂直行业成为当下产业界最为关心的话…

45+用户占比近30%,网文产业如何赋能IP长链?

网文市场加速发展,巨头抢占中老年用户 作者|吕娆炜 排版|张思琪 干货抢先看 1. 我国网文产业市场规模突破3000亿元,在用户方面,截至2023年底,我国网文用户数量达5.37亿,同比增长9%&#xff0c…

【机器学习】线性回归

一、什么是回归 分类任务很好理解,比如去银行贷款,银行会根据贷款人的年龄、工资(特征)去决定贷款(标签1)和不贷款(标签0)。而回归任务,是预测允许贷款的额度&#xff08…

【学习笔记】灰色预测 GM(1,1) 模型 —— Matlab

文章目录 前言一、灰色预测模型灰色预测适用情况GM (1,1)模型 二、示例指数规律检验(原始数据级比检验)级比检验的定义GM(1,1) 模型的级比检验 模型求解求解微分方程 模型评价(检验模型对原始数据的拟合程度)残差检验级比偏差检验 三、代码实现----Matlab级比检验代码模型求解代…

0成本学习Liunx系统【只需要一台笔记本电脑,无需购买云服务器】

【准备工作,需要软件】: 1:MobaXterm 【服务器连接工具(免费开源)】 2:CentOS-7-x86_64-DVD-2009.iso 【CentOS-7 镜像】 3:VirtualBox-7.0.20-163906-Win.exe 【虚拟机壳子】 4&…

20 动态内存管理

目录 一、为什么要有动态内存管理 二、malloc 和 free (一)malloc (二)free 三、calloc 和 realloc (一)calloc (二)realloc 四、常见的动态内存错误 (一&#…

前端本地代理配置方式

Whistle 介绍 Whistle 是一个基于 Node.js 的跨平台 Web 调试工具。允许捕获、查看和修改 HTTP/HTTPS 网络请求。通过使用 Whistle,可以轻松地进行接口代理、抓包、模拟数据、修改请求和响应等操作,以便在前端开发中调试网络请求。 Proxy SwitchyOmega…

133-横向移动域控提权NetLogonADCSPACKDC永恒之蓝

除了前面讲到的口令密码进行横向移动,还存在使用系统漏洞进行的横向移动的方式,本节课就是讲一些域内系统的漏洞,主要是域控提权的一些漏洞 1、横向移动-系统漏洞-CVE-2017-0146(ms17-010,永恒之蓝) 2、横…

Java之迭代器的使用

Java之迭代器的使用 摘要基础知识List迭代器Map迭代器 摘要 本博客主要讲解容器的迭代器的使用,包括List、Set和Map等容器 基础知识 这是类的继承关系图 迭代器的原理(一开始迭代器并不指向任何有效元素): List迭代器 public class TestIterator …

World of Warcraft [CLASSIC] the Eye of Eternity [EOE] P1-P2

World of Warcraft [CLASSIC] the Eye of Eternity [EOE] 永恒之眼(蓝龙) 第一阶段 第二阶段 第三阶段 载具1-6技能介绍 World of Warcraft [CLASSIC] the Eye of Eternity [EOE]_永恒之眼 eoe-CSDN博客 永恒之眼怎么出副本呢,战斗结束&am…

【Java】/* 链式队列 和 循环队列 - 底层实现 */

一、链式队列 1. 使用双向链表实现队列,可以采用尾入,头出 也可以采用 头入、尾出 (LinkedList采用尾入、头出) 2. 下面代码实现的是尾入、头出: package bageight;/*** Created with IntelliJ IDEA.* Description:* User: tangyuxiu* Date: …

windows安装android studio

下载 https://developer.android.google.cn/studio?hlzh-cn 安装 打开cmd输入如下命令 android-studio-2024.1.1.12-windows.exe /NCRC 注意 运行命令后可能还报错,但是会出现弹窗 如果还是报错可以选择zip 运行 不设置代理 等待下载即可,…

Linux云计算 |【第二阶段】SECURITY-DAY3

主要内容: Prometheus监控服务器、Prometheus被监控端、Grafana监控可视化 补充:Zabbix监控软件不自带LNMP和DB数据库,需要自行手动安装配置;Prometheus监控软件自带WEB页面和DB数据库;Prometheus数据库为时序数据库&…

Android 14适配

最近刚刚做了Android 14的适配(即targetSdkVersion 升级到 34 ),通过此博客整理下相关注意点。 前台服务类型 当targetSdkVersion > 34 ,应用内的前台服务(Foreground Service)需要指定至少一种前台服务…

k8s - Secret实践练习

参考文档:https://kubernetes.io/zh-cn/docs/concepts/configuration/secret/ 这个和ConfigMap很相似,这里选两个做下测试,就不过多赘述了 简介 Secret 类似于 ConfigMap 但专门用于保存机密数据。 Secret 是一种包含少量敏感信息例如密码…

qt creator自动运行单元测试

qt creator自动运行单元测试 工具-选项-Testing-General,找到Automatically run,选项卡选择All。

[C语言]-基础知识点梳理-编译、链接、预处理

前言 各位师傅大家好,我是qmx_07,今天来给大家讲解以下程序运行会经历哪些事情 翻译环境和运⾏环境 在ANSIC的任何⼀种实现中,存在两个不同的环境 第1种是翻译环境,在这个环境中源代码被转换为可执⾏的机器指令(⼆进制指令&a…

Linux下opencv报错 undefined reference to cv::imread cv::Mat

如果你是和libtorch一起使用,那么请你继续,否则该篇文章不适合你。 正文 在https://pytorch.org/下 下载的时候要选择Cxx11 ABI版 随后正常配置就可以了

Langchain-Chatchat

模型能力定制 微调 智能设备 微调 响应有要求 微调 动态数据 RAG 幻觉 RAG 可解释性 RAG 成本 RAG 依赖生成能力 微调 微调需要几万、几十万条好的数据,否者白调,所以是否需要微调,需要视情况而定。 RAG的落地,可以使用 https:/…