【数据结构】双链表

【数据结构】双链表

  • 一. 前言
  • 二. 带头双向链表接口实现
      • 1.准备工作
      • 2. 创建一个节点
  • 三. 初始化
      • 4. 打印
      • 5. 尾插
      • 6. 尾删
      • 7. 头插
      • 8. 头删
      • 9. 计算节点个数
      • 10. 查找数据
      • 11. 在任意位置插入数据
      • 12. 在任意位置删除数据
      • 13. 销毁
  • 四. 如何10分钟内完成一个完整双链表

在这里插入图片描述

一. 前言

 带头双向循环链表:结构最复杂,一般用在单独存储数据。实际中使用的链表数据结构,都是带头双向循环链表。另外这个结构虽然结构复杂,但是使用代码实现以后会发现结构会带来很多优势,实现反而简单了。

在这里插入图片描述


二. 带头双向链表接口实现

1.准备工作

 由于实际开发项目中,项目的实现都是采用模块化的方式实现。所以博主在这也采用了模块化的方式。
在这里插入图片描述

#pragma oncetypedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;//下一个节点指针struct ListNode* prev;//上一个节点指针LTDataType data;//数据域
}LTNode;

为了后续函数功能实现过程中数据类型书写方便性,我们将struct ListNode重命名为LTNode
同时后续好修改数据域类型,我们将数据域类型int重命名为LTDataType.


2. 创建一个节点

不管是后续插入数据还是初始化,我们都先要创建一个节点来存储数据。
所以我们在这设计了一个相关函数,从而避免大量重复的工作。

代码实现:

LTNode* BuyLTNode(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;
}

三. 初始化

初始化时,我们支持需要创建一个节点作为哨兵位,并将两个指针同时指向自己即可。

代码实现:

LTNode* LTInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}

4. 打印

打印比较简单。但需要注意我们是从哨兵位的下一个节点开始打印

代码实现:

void LTPrint(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;//哨兵位下一个节点printf("phead<=>");while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}

5. 尾插

带头双链表的尾插比较简单。
我们通过哨兵位向前访问即可得到尾节点。在插入数据即可。

代码实现:

void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;//尾节点LTNode* newnode = BuyLTNode(x);//要插入节点//插入tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}

6. 尾删

【代码思路】:尾删首先要判断是否还有节点可删。若有,找到尾节点以及尾节点的前一个结点。在释放尾节点,并将新的尾节点和哨兵位链接起来即可。

代码实现:

void LTPopBack(LTNode* phead)
{assert(phead);assert(phead != phead->next);//还有节点可删LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;free(tail);tailPrev->next = phead;phead->prev = tailPrev;
}

7. 头插

要实现头插,首先要强调是插到哨兵位的后面。
【代码思路】:直接将哨兵位,哨兵位的下一个节点以及新节点链接起来即可。

代码实现:

void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->next;LTNode* newnode = BuyLTNode(x);phead->next = newnode;newnode->prev = phead;newnode->next = tail;tail->prev = newnode;
}

8. 头删

【代码思路】:头删和尾删一样,需要是否还有节点可删。若还有元素可删,需要保存哨兵位后面两个节点firstsecond。再释放掉first后,将哨兵位和second链接起来。

代码实现:

void LTPopFront(LTNode* phead)
{assert(phead);assert(phead != phead->next);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;
}

9. 计算节点个数

【代码思路】:首先保存哨兵位的下一个节点。然后开始向后遍历访问,每次个数加1,直到某节点的下一个节点指向哨兵位为止。

代码实现:

int LTSize(LTNode* phead)
{LTNode* cur = phead->next;int count = 0;while (cur != phead){count++;cur = cur->next;}return count;
}

Tips:

  • 可能有部分学者已经注意到或在一些书籍上看到过以下思路:哨兵位的数据域是随机值,是否可以将它用于记录节点个数。每次进行增删查改等操作时,对其进行加1/减1。不仅更加方便得知节点个数,同时还避免该接口的实现。
  • 在这里博主不在这建议这样做,又或者说大部分情况是不能这样做的。原因在于:我们在本篇博客中,数据域为整型,可以用于记录节点个数大下。但在实际开发过程中,数据域可能存储的是浮点数或结构体什么的,那上述思路将导致结果错误。

10. 查找数据

【代码思路】:查找数据,从哨兵位的下一个节点开始,遍历查找。找到返回数据地址,否则返回空指针。

代码实现:

LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}

11. 在任意位置插入数据

【代码思路】:首先需要强调的是,不管是链表还是顺序表,插入数据默认都是前插,在这里也一样。插入数据、插入位置节点、以及前一个结点链接起来即可。
我们直接将

代码实现:

void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}

12. 在任意位置删除数据

【代码思路】:将该位置前一个和后一个节点链接起来后,再将该位置节点释放。

代码实现:

void LTErase(LTNode* pos)
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}

13. 销毁

由于上述节点都是动态开辟的,使用往后需要销毁,释放内存。

代码实现:

void LTDestory(LTNode* phead)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

四. 如何10分钟内完成一个完整双链表

在实际开发过程中,我们一般实现实现任意位置插入删除接口的。然后在头插/删和尾插/删等接口中,调用上述两个接口,从而快速达到目的。

List.h:

#pragma once#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int LTDataType;
typedef struct ListNode
{struct ListNode* next;struct ListNode* prev;LTDataType data;
}LTNode;LTNode* BuyLTNode(LTDataType x);//创建节点LTNode* LTInit();//初始化
void LTPrint(LTNode* phead);//打印//在pos之前插入x
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置节点
void LTErase(LTNode* pos);void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删int LTSize(LTNode* phead);//节点大小
LTNode* LTFind(LTNode* phead, LTDataType x);//查找
void LTDestory(LTNode* phead);//销毁

List.c:

#include "List.h"LTNode* BuyLTNode(LTDataType x)//创建节点
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail");exit(-1);}newnode->next = NULL;newnode->prev = NULL;newnode->data = x;return newnode;
}LTNode* LTInit()//初始化
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}void LTPrint(LTNode* phead)//打印
{assert(phead);LTNode* cur = phead->next;printf("phead<=>");while (cur != phead){printf("%d<==>", cur->data);cur = cur->next;}printf("\n");
}void LTInsert(LTNode* pos, LTDataType x)//任意位置插入
{assert(pos);LTNode* posPrev = pos->prev;LTNode* newnode = BuyLTNode(x);posPrev->next = newnode;newnode->prev = posPrev;newnode->next = pos;pos->prev = newnode;
}void LTErase(LTNode* pos)//任意位置删除
{assert(pos);LTNode* posPrev = pos->prev;LTNode* posNext = pos->next;free(pos);posPrev->next = posNext;posNext->prev = posPrev;
}void LTPushBack(LTNode* phead, LTDataType x)//尾插
{assert(phead);LTInsert(phead, x);
}void LTPopBack(LTNode* phead)//尾删
{assert(phead);assert(phead != phead->next);LTErase(phead->prev);
}void LTPushFront(LTNode* phead, LTDataType x)//头插
{assert(phead);LTInsert(phead->next, x);
}void LTPopFront(LTNode* phead)//头删
{assert(phead);assert(phead != phead->next);LTErase(phead->next);
}int LTSize(LTNode* phead)//节点大小
{LTNode* cur = phead->next;int count = 0;while (cur != phead){count++;cur = cur->next;}return count;
}LTNode* LTFind(LTNode* phead, LTDataType x)//查找数据
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->data == x)return cur;cur = cur->next;}return NULL;
}void LTDestory(LTNode* phead)//销毁
{assert(phead);LTNode* cur = phead->next;while (cur != phead){LTNode* next = cur->next;free(cur);cur = next;}free(phead);
}

在这里插入图片描述
在这里插入图片描述

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

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

相关文章

笔记——听听前辈们的教学评一体化

精选课程内容 强而有力的知识 做中学&#xff0c;用中学&#xff0c;创中学。 这个技术很难做 关于支架的新理解 有价值 有意义 和 趣味性 权衡&#xff0c;不能为了趣味性舍弃价值 举例说明文 被教成了文学作品 导致所教所学 悄然发生了偏移。 所以教学评如何一直&#xff…

Ajax 笔记(一)

笔记目录 1. Ajax 入门1.1 Ajax 概念1.2 axios 使用1.2.1 URL1.2.2 URL 查询参数1.2.3 小案例-查询地区列表1.2.4 常用请求方法和数据提交1.2.5 错误处理 1.3 HTTP 协议1.3.1 请求报文1.3.2 响应报文 1.4 接口文档1.5 案例1.5.1 用户登录&#xff08;主要业务&#xff09;1.5.2…

如何构造一个安全的单例?

为什么要问这个问题&#xff1f; 我们知道&#xff0c;单例是一种很常用的设计模式&#xff0c;主要作用就是节省系统资源&#xff0c;让对象在服务器中只有一份。但是实际开发中可能有很多人压根没有写过单例这种模式&#xff0c;只是看过或者为了面试去写写demo熟悉一下。那…

职责链模式(C++)

定义 使多个对象都有机会处理请求&#xff0c;从而避免请求的发送者和接收者之间的耦合关系。将这些对象连成一条链&#xff0c;并沿着这条链传递请求&#xff0c;直到有一个对象处理它为止。 应用场景 在软件构建过程中&#xff0c;一个请求可能被多个对象处理&#xff0c;…

Redis单机,主从,哨兵,集群四大模式

Redis 单机模式 Redis 单机模式是指 Redis 数据库在单个服务器上以独立的、单一的进程运行的模式。在这种模式下&#xff0c;Redis 不涉及数据分片或集群配置&#xff0c;所有的数据和操作都在一个实例中进行。以下是关于 Redis 单机模式的详细介绍&#xff1a; 单一实例&#…

如何搭建自动化测试框架?资深测试整理的PO模式,一套打通自动化...

目录&#xff1a;导读 前言一、Python编程入门到精通二、接口自动化项目实战三、Web自动化项目实战四、App自动化项目实战五、一线大厂简历六、测试开发DevOps体系七、常用自动化测试工具八、JMeter性能测试九、总结&#xff08;尾部小惊喜&#xff09; 前言 Po模型介绍 1、简…

24届华东理工大学近5年自动化考研院校分析

今天给大家带来的是华东理工大学控制考研分析 满满干货&#xff5e;还不快快点赞收藏 一、华东理工大学 学校简介 华东理工大学原名华东化工学院&#xff0c;1956年被定为全国首批招收研究生的学校之一&#xff0c;1960年起被中共中央确定为教育部直属的全国重点大学&#…

匈牙利算法详解

匈牙利算法(Hungarian Algorithm)是一种组合优化算法(combinatorial optimization algorithm)&#xff0c;用于求解指派问题(assignment problem)&#xff0c;算法时间复杂度为O(N^3)。Harold Kuhn发表于1955年&#xff0c;由于该算法基于两位匈牙利数学家的早期研究成果&#…

基于智慧路灯杆的智慧交通应用示例

智慧路灯杆的身影已经越来越频繁出现在我们的生活之中&#xff0c;无论是我们开车在路上&#xff0c;还是行走在商业街&#xff0c;造型美轮美奂&#xff0c;功能丰富多样的智慧路灯杆&#xff0c;也已经成为了一道独特靓丽的街景。 智慧路灯杆如何发挥其智慧功能&#xff1f;对…

Zabbix6.0监控

文章目录 一、Zabbix简介1&#xff09;zabbix 是什么&#xff1f;2&#xff09;zabbix 监控原理3&#xff09;Zabbix 6.0 新特性1、Zabbix server高可用防止硬件故障或计划维护期的停机2、Zabbix 6.0 LTS新增Kubernetes监控功能&#xff0c;可以在Kubernetes系统从多个维度采集…

The ‘kotlin-android-extensions‘ Gradle plugin is no longer supported.

Android使用kotlin开发&#xff0c;运行报错 The kotlin-android-extensions Gradle plugin is no longer supported. Please use this migration guide (https://goo.gle/kotlin-android-extensions-deprecation) to start working with View Binding (https://developer.an…

一文了解 Android Auto 车载开发~

作者&#xff1a;牛蛙点点申请出战 背景 我的的产品作为一个海外音乐播放器&#xff0c;在车载场景听歌是一个很普遍的需求。在用户反馈中&#xff0c;也有很多用户提到希望能在车上播放音乐。同时车载音乐也可以作为提升用户消费时长一个抓手。 出海产品&#xff0c;主要服务…

【单片机】51单片机,晨启科技,板子引脚对应关系

一般引脚: sbit beepP2^4; //将单片机的P2.4端口定义为beep.本口用于屏蔽上电后蜂鸣器响 sbit ledP1^0; //将单片机的P1.0端口定义为led&#xff0c;用于点亮LED-D1 sbit DIG1P0^0; //数码管位选1 sbit DIG2P0^1; //数码管位选2P10xFF;//初始化P1引脚全部置高&a…

Linux中singal信号的作用

void&#xff08;* signal&#xff08;int sig&#xff0c;void&#xff08;* func&#xff09;&#xff08;int&#xff09;&#xff09;&#xff09;&#xff08;int&#xff09;;设置处理信号的功能 头文件为&#xff1a;#include <signal.h> 指定使用sig指定的信号…

时序预测 | MATLAB实现BO-GRU贝叶斯优化门控循环单元时间序列预测

时序预测 | MATLAB实现BO-GRU贝叶斯优化门控循环单元时间序列预测 目录 时序预测 | MATLAB实现BO-GRU贝叶斯优化门控循环单元时间序列预测效果一览基本介绍模型搭建程序设计参考资料 效果一览 基本介绍 MATLAB实现BO-GRU贝叶斯优化门控循环单元时间序列预测。基于贝叶斯(bayes)…

Spring MVC

hi,今天为大家带来Spring MVC相关知识 文章目录 &#x1f33b;1.什么是Spring MVC?&#x1f36c;1.1什么是MVC?&#x1f36c;1.2MVC和Spring MVC的关系 &#x1f33b;2.Spring MVC的意义&#x1f36c;2.1Spring MVC和Spring Boot区别 &#x1f33b;3.Spring MVC的三大要点&a…

用PointNet分类3D点云

在本教程中&#xff0c;我们将学习如何训练PointNet进行分类。 我们将主要关注数据和训练过程&#xff1b; 展示如何从头开始编码 Point Net 的教程位于此处。 本教程的代码位于这个Github库中&#xff0c;我们将使用的笔记本位于这个Github库中。 一些代码的灵感来自于这个Git…

wordpress 打开缓慢处理

gravatar.com 头像网站被墙 追踪发现请求头像时长为21秒 解决方案一 不推荐&#xff0c;容易失效&#xff0c;网址要是要稳定为主&#xff0c;宁愿头像显示异常&#xff0c;也不能网址打不开 网上大部分搜索到的替换的CDN网址都过期了&#xff0c;例如&#xff1a;gravatar.du…

知识付费系统开发:构建高效智能的付费内容平台

随着数字化时代的来临&#xff0c;知识付费正迅速崭露头角&#xff0c;为知识创作者和求知者带来了全新的商机。在这个背景下&#xff0c;开发一款高效智能的知识付费系统成为了一项重要的任务。本文将深入探讨如何基于Python编程语言和相关技术构建一个智能的知识付费内容平台…

备份容灾哪家好怎么样

数字化时代&#xff0c;数据安全是我们不容忽视的问题。云呐容灾备份系统不仅提供了强大的数据保护功能&#xff0c;而且操作简单&#xff0c;使用方便。无论你是企业管理员&#xff0c;还是个人用户&#xff0c;都可以轻松上手。它还提供了丰富的报告和监控功能&#xff0c;让…