双向链表_代码实现

代码实现的专题：只有手撕代码：），附上重点注释；重要的环节，会配上相应的调试截图与运行截图 。

总之，重点在代码，关于基础理论部分：（还在写）

定义双向链表节点的结构

//ListNode.h//定义双向链表节点的结构
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;//表示下一节点的指针struct ListNode* prev;//表示上一节点的指针}LTNode;

双向链表_初始化：

ListNode.h//初始化
void LTInit(LTNode** pphead);
//ListNode.c#include "ListNode.h"//申请空间，创建链表节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->prev = newnode->next = newnode;//双向链表的特殊之处；
}
void LTInit(LTNode** pphead)
{*pphead = LTBuyNode(-1);
}
//test.c#include "ListNode.h"void ListNodeTest01()
{LTNode* plist = NULL;//创建一个节点，先分配无效地址LTInit(&plist);//测试初始化方法
}
int main()
{ListNodeTest01();//测试代码区域专门放入这个函数里return 0;
}

初始化方法调试：

进入初始化方法：

退出BuyNode方法后，*pphead接收返回值：

初始化，传的是&plist,(形参的改变要想影响实参，就得传实参的地址)

 结果看到，plist的值已经与形参的一样---说明初始化成功

另一种写法：

LTNode* Init();
//申请空间，创建链表节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->prev = newnode->next = newnode;//双向链表的特殊之处；
}
LTNode* Init()
{LTNode* phead = LTBuyNode(-1);//创建一个指针接收返回值return phead;//phead此时已经申请好空间，完成初始化
}
//测试
LTNode* plist = Init();//让plist接收返回值

双向链表_打印

为了方便我们后续链表增删查改方法的检验，我们增加双向链表打印的方法

void LTPrint(LTNode* phead);
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;//记得让pcur走，循环条件若不改变，肯定会死循环}printf("\n");}

增

双向链表的尾插
 

void LTPushBack(LTNode* phead,LTDataType x);

//哨兵位节点不能被删除，节点的地址也不能发生改变
//不改变哨兵位的位置，因此传一级即可
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//创建新节点LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;//这两行代码不能交换phead->prev = newnode;//一旦发生交换，就找不到原先的尾节点
}

测试代码：

void ListNodeTest01()
{LTNode* plist = NULL;LTInit(&plist);//测试尾插LTPushBack(plist,1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);
}
int main()
{ListNodeTest01();return 0;
}

结果输出：

双向链表的头插

void LTPushFront(LTNode* phead, LTDataType x)
//头插——插在哨兵位的后面，成为新的第一个有效节点
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//链表必须有效，双链表至少得有个有效的哨兵位，不然甚至称不上是双向链表LTNode* newnode = LTBuyNode(x);// phead newnode phead->nextnewnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;//这两行代码同样不能换顺序phead->next = newnode;//一旦交换，找不到原来的第一个有效节点}
#include "ListNode.h"void ListNodeTest01()
{LTNode* plist = NULL;LTInit(&plist);//测试尾插LTPushBack(plist,1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);//1->2->3->//测试头插LTPushFront(plist, 1);LTPushFront(plist, 2);LTPushFront(plist, 3);LTPrint(plist);
}
int main()
{ListNodeTest01();return 0;
}

运行截图：

删 

双向链表的尾删

void LTPopBack(LTNode* phead);
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表必须有效，且不能删哨兵位（链表不能为空）LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;}
void ListNodeTest01()
{LTNode* plist = NULL;LTInit(&plist);//测试尾插LTPushBack(plist,1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);//1->2->3->//....//测试尾删LTPopBack(plist);LTPrint(plist);
}

运行截图：

双向链表的头删

void LTPopFront(LTNode* phead);
//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}
void ListNodeTest01()
{LTNode* plist = NULL;LTInit(&plist);//测试尾插LTPushBack(plist,1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);//1->2->3->//测试头删LTPopFront(plist);LTPrint(plist);
}

运行截图：

查 

双向链表的查找

//根据数据查找
LTNode* LTFind(LTNode* phead,LTDataType x);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;}

指定位置之后插入数据

//在pos位置之后插入数据
void LTInsert(LTNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos,LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}

//测试在pos之后插入数据LTNode* find = LTFind(plist, 2);//返回下标为2的节点指针LTInsert(find,666);//2后插入666LTPrint(plist);

运行截图：

删除指定位置的节点

//删除指定pos节点
void LTErase(LTNode * pos);
//删除指定pos节点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

    //测试在pos之后插入数据LTNode* find = LTFind(plist, 2);LTInsert(find,666);LTPrint(plist);//测试指定pos删除节点LTErase(find);LTPrint(plist);LTErase(find);LTPrint(plist);

运行截图：

结果节点2确实被指定删除了

双向链表_销毁

//删除链表
void LTDesTroy(LTNode* phead);
//销毁
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//现在只剩哨兵位节点未释放free(phead);phead = NULL;}
//测试LTDesTroy(plist);plist = NULL;

调试一番，在DesTroy函数结束后，形参phead被释放，但是主调函数里的实参plist可以看到并没有被销毁（即存着有效地址），但是后面的节点已然被删除，需要主动plist = null;不然你还可以利用plist，进行尾插之类的操作——这怎么能叫销毁呢？——原理还是：形参的改变要影响实参，还得传地址

这里传的形参，phead头节点想要被改变，就得传&phead,但是我写的方法里面为什么不传二级指针（&phead），因为：为了保持接口的一致性

前面的增删查改的参数都传的是plist,但是到了初始化和销毁，一旦涉及头结点的改变，就要传二级，这就加大了用户/同事使用接口的记忆量，所以我们尽量保持传参的统一，都传plist，或者像初始化的第二个方法，不传参。

完整代码参考：

ListNode.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
//定义双向链表节点的结构
typedef int LTDataType;
typedef struct ListNode
{LTDataType data;struct ListNode* next;//表示下一节点的指针struct ListNode* prev;//表示上一节点的指针}LTNode;//初始化
void LTInit(LTNode** pphead);
void LTPrint(LTNode* phead);
//尾插和头插
void LTPushBack(LTNode* phead,LTDataType x);
void LTPushFront(LTNode* phead, LTDataType x);
//尾删和头删
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
//在pos位置之后插入数据
void LTInsert(LTNode* phead, LTDataType x);
//根据数据查找
LTNode* LTFind(LTNode* phead,LTDataType x);
//删除指定pos节点
void LTErase(LTNode * pos);
//删除链表
void LTDesTroy(LTNode* phead);

 ListNode.c

#include "ListNode.h"LTNode* LTBuyNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));newnode->data = x;newnode->prev = newnode->next = newnode;//双向链表的特殊之处；
}
void LTInit(LTNode** pphead)
{*pphead = LTBuyNode(-1);//哨兵位节点
}
LTNode* Init()
{LTNode* phead = LTBuyNode(-1);return phead;
}
//哨兵位节点不能被删除，节点的地址也不能发生改变
//不改变哨兵位的位置，因此传一级即可
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);//创建新节点LTNode* newnode = LTBuyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;//这两行代码不能交换phead->prev = newnode;//一旦发生交换，就找不到原先的尾节点
}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->",pcur->data);pcur = pcur->next;//记得让pcur走，循环条件若不改变，肯定会死循环}printf("\n");}
//头插——插在哨兵位的后面，成为新的第一个有效节点
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);//链表必须有效，双链表至少得有个有效的哨兵位，不然甚至称不上是双向链表LTNode* newnode = LTBuyNode(x);// phead newnode phead->nextnewnode->prev = phead;newnode->next = phead->next;phead->next->prev = newnode;//这两行代码同样不能换顺序phead->next = newnode;//一旦交换，找不到原来的第一个有效节点}
//尾删
void LTPopBack(LTNode* phead)
{assert(phead && phead->next != phead);//链表必须有效，且不能删哨兵位（链表不能为空）LTNode* del = phead->prev;del->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;}//头删
void LTPopFront(LTNode* phead)
{assert(phead && phead->next != phead);LTNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos,LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->prev = pos;newnode->next = pos->next;pos->next->prev = newnode;pos->next = newnode;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;}//删除指定pos节点
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//现在只剩哨兵位节点未释放free(phead);phead = NULL;}

test.c 

#include "ListNode.h"void ListNodeTest01()
{LTNode* plist = Init();//测试尾插LTPushBack(plist,1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPrint(plist);//1->2->3->测试头插//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPushFront(plist, 3);//LTPrint(plist);测试尾删//LTPopBack(plist);//LTPrint(plist);测试头删//LTPopFront(plist);//LTPrint(plist);测试在pos之后插入数据//LTNode* find = LTFind(plist, 2);//LTInsert(find,666);//LTPrint(plist);测试指定pos删除节点//LTErase(find);//LTPrint(plist);//测试LTDesTroy(plist);plist = NULL;
}
int main()
{ListNodeTest01();return 0;
}

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Python数据可视化之numpy的11个常用的创建数组的函数

Python数据可视化之numpy的11个常用的创建数组的函数

numpy库 在处理成千上万的数据时&#xff0c;Python的1维列表已经不适合来对数据进行处理&#xff0c;效率会很慢&#xff0c;所以numpy就诞生了&#xff0c;他可以将列表变成数组&#xff0c;而数组可以是1维、2维、3维甚至更高纬度&#xff0c;可用于存储和处理大型的矩阵&a…
阅读更多...
js | Core

js | Core

http://dmitrysoshnikov.com/ecmascript/javascript-the-core/ Object 是什么&#xff1f; 属性[[prototype]]对象。 例如&#xff0c;下面的&#xff0c;son是对象&#xff0c;foo不是对象。打印出来的son&#xff0c;能看到有一个prototype 对象。 prototype vs _proto_ v…
阅读更多...
Kafka消息队列python开发环境搭建

Kafka消息队列python开发环境搭建

目录 引言 Kafka 的核心概念和组件 Kafka 的主要特性 使用场景 申请云服务器 安装docker及docker-compose VSCODE配置 开发环境搭建 搭建Kafka的python编程环境 Kafka的python编程示例 引言 Apache Kafka 是一个分布式流处理平台&#xff0c;由 LinkedIn 开发并在 2…
阅读更多...
【BUG】已解决：WslRegisterDistribution failed with error: 0x800701bc

【BUG】已解决：WslRegisterDistribution failed with error: 0x800701bc

已解决&#xff1a;WslRegisterDistribution failed with error: 0x800701bc 欢迎来到英杰社区https://bbs.csdn.net/topics/617804998 欢迎来到我的主页&#xff0c;我是博主英杰&#xff0c;211科班出身&#xff0c;就职于医疗科技公司&#xff0c;热衷分享知识&#xff0c;武…
阅读更多...
Word文档恢复竟然这么简单？3个推荐方案送上！

Word文档恢复竟然这么简单？3个推荐方案送上！

“我很喜欢用Word进行文字创作&#xff0c;可是我有一次重新打开我的Word文档&#xff0c;却显示文档已丢失&#xff0c;这该怎么办呢&#xff1f;凝聚我多年心血的文章还有可能恢复吗&#xff1f;” 不论是总结学习内容还是汇报工作成果&#xff0c;我们总会用上Word。Word作…
阅读更多...
level 6 day2 网络基础2

level 6 day2 网络基础2

1.socket&#xff08;三种套接字&#xff1a;认真看&#xff09; 套接字就是在这个应用空间和内核空间的一个接口&#xff0c;如下图 原始套接字可以从应用层直接访问到网络层&#xff0c;跳过了传输层&#xff0c;比如在ubtan里面直接ping 一个ip地址,他没有经过TCP或者UDP的数…
阅读更多...
大数据量接口响应慢-传输优化

大数据量接口响应慢-传输优化

问题 接口一次性返回大量数据&#xff0c;导致JSON数据大小过大&#xff0c;带宽大小不足&#xff0c;导致接口响应时间过长 解决方案 通过数据传输压缩来降低传输数据的大小&#xff0c;从而提高传输效率 服务器端压缩 springboot项目配置application文件&#xff0c;通过…
阅读更多...
不懂U盘文件恢复？学会这4个方法点亮技能点！

不懂U盘文件恢复？学会这4个方法点亮技能点！

“向广大网友求助&#xff1a;U盘里的文件意外删除了还有机会恢复吗&#xff1f;工作的时候不小心删除了存储在U盘里的重要文件&#xff0c;撤销也恢复不了&#xff0c;我还有其他的办法吗&#xff1f;” 相信大家在日常生活中&#xff0c;为了储存和随时携带重要的文件信息&a…
阅读更多...
第5章 单片机的中断系统

第5章 单片机的中断系统

5.1 中断的概念 5.2 中断控制系统 5.3 中断处理过程 5.4 中断的编程及应用举例 5.1 中断的概念 日常生活的中断现象举例 中断是指在突发事件到来时先中止当前正在进行的工作&#xff0c;转而去处理突发事件。待处理完成后&#xff0c;再返回到原先被中止的工作处&#xff…
阅读更多...
状态管理的艺术：探索Flutter的Provider库

状态管理的艺术：探索Flutter的Provider库

状态管理的艺术&#xff1a;探索Flutter的Provider库 前言 上一篇文章中&#xff0c;我们详细介绍了 Flutter 应用中的状态管理&#xff0c;以及 StatefulWidget 和 setState 的使用。 本篇我们继续介绍另一个实现状态管理的方式&#xff1a;Provider。 Provider优缺点 基…
阅读更多...
【论文速读】| 涟漪下的漩涡：对启用RAG的应用程序的实证研究

【论文速读】| 涟漪下的漩涡：对启用RAG的应用程序的实证研究

本次分享论文&#xff1a;Vortex under Ripplet: An Empirical Study of RAG-enabled Applications 基本信息 原文作者&#xff1a;Yuchen Shao, Yuheng Huang, Jiawei Shen, Lei Ma, Ting Su, Chengcheng Wan 作者单位&#xff1a;East China Normal University, The Unive…
阅读更多...
JVM基本知识——运行空间

JVM基本知识——运行空间

JVM&#xff08;Java Virtual Machine&#xff09;即Java虚拟机&#xff0c;是负责读取java字节码&#xff0c;并在实际的硬件环境中运行。 JVM可以分为三部分&#xff1a;类装载器&#xff08;ClassLoader&#xff09;子系统、内存空间、执行引擎 内存空间&#xff08;运行时…
阅读更多...
高职院校人工智能人才培养成果导向系统构建、实施要点与评量方法

高职院校人工智能人才培养成果导向系统构建、实施要点与评量方法

一、引言 近年来&#xff0c;人工智能技术在全球范围内迅速发展&#xff0c;对各行各业产生了深远的影响。高职院校作为培养高技能人才的重要基地&#xff0c;肩负着培养人工智能领域专业人才的重任。为了适应社会对人工智能人才的需求&#xff0c;高职院校需要构建一套科学、…
阅读更多...
【STC89C51单片机】定时器/计数器的理解

【STC89C51单片机】定时器/计数器的理解

目录 定时器/计数器1. 定时器怎么定时简单理解&#xff08;加1经过了多少时间&#xff09;什么是时钟周期什么是机器周期 2.如何设置定时基本结构相关寄存器1. TMOD寄存器2. TCON寄存器 代码示例 定时器/计数器 STC89C51单片机的定时器和计数器&#xff08;Timers and Counter…
阅读更多...
基于STM32老人摔倒报警设计

基于STM32老人摔倒报警设计

1.简介 随着我国老年人人口不断上升&#xff0c;我国已经进入人口老龄化&#xff0c;老龄人的人数加剧随着而来的就是基本的健康安全问题成为了如今社会主要解决的问题。随着已经步入信息时代&#xff0c;为了解决老年人的健康问题&#xff0c;相关技术的使用已经成为一个热门话…
阅读更多...
JVM高频面试点

JVM高频面试点

文章目录 JVM内存模型程序计数器Java虚拟机栈本地方法栈Java堆方法区运行时常量池 Java对象对象的创建如何为对象分配内存 对象的内存布局对象头实例数据对齐填充 对象的访问定位 垃圾收集器找到垃圾引用计数法可达性分析&#xff08;根搜索法&#xff09; 引用概念的扩充回收方…
阅读更多...
COD论文学习 ZoomNext

COD论文学习 ZoomNext

现有方法的不足之处 高内在相似性&#xff1a;伪装物体与背景之间的高内在相似性使得检测变得困难&#xff0c;现有方法难以准确区分二者。多样化的规模和模糊的外观&#xff1a;伪装物体在规模和外观上多样化&#xff0c;且可能严重遮挡&#xff0c;导致现有方法难以处理。不…
阅读更多...
【青书学堂】2024年第一学期 保险理论与实务(高起专) 作业

【青书学堂】2024年第一学期 保险理论与实务(高起专) 作业

【青书学堂】2024年第一学期 保险理论与实务(高起专) 作业 为了方便日后复习&#xff0c;青书学堂成人大专试题整理。 若有未整理的课程&#xff0c;请私信我补充&#xff0c;欢迎爱学习的同学们收藏点赞关注&#xff01;文章内容仅限学习使用&#xff01;&#xff01;&#xf…
阅读更多...
「C++」类和对象（1）

「C++」类和对象（1）

欢迎来到海盗猫鸥的博客~~ 本篇我们将学习部分C中的类和对象相关知识沃~ (• ω •)&#xff89;算我一个&#xff5e; 目录 类的定义 类的定义及使用 访问限定符 类域 实例化 实例化概念&#xff1a; 对象大小&#xff1a; 内存对齐规则&#xff1a; 注意点&#xff…
阅读更多...
十二.核心动画 - 动画缓冲①（框架提供的缓存函数）

十二.核心动画 - 动画缓冲①（框架提供的缓存函数）

引言 上一篇博客我们已经讨论了Core Animation中时间的处理&#xff0c;以及CAMediaTiming协议。本篇博客我们就来看一下另外一个和时间有关的机制--缓冲。 缓冲会让动画看起来更平滑更自然&#xff0c;我们在本篇博客将会体验一下CAAnimation提供的缓存函数&#xff0c;UIVi…
阅读更多...
最新文章

Copyright @ 2022~2023