数据结构双向链表

在这里插入图片描述

Hello,好久不见,今天我们讲链表的双向链表,这是一个很厉害的链表,带头双向且循环,学了这个链表,你会发现顺序表的头插头删不再是一个麻烦问题,单链表的尾插尾删也变得简单起来了,那废话不多说,让我们开始我们的学习吧!

首先我们要了解它的物理和逻辑结构,那他们的样子是怎样的呢,首先是一个带头的,那这个难道是我们的哨兵位吗,又是双向,且循环,那让我们来画图了解它吧。

在这里插入图片描述

大致就是这样的一个形状,那我们现在需要这样的一个结构体来实现这样的功能,首先应该有一个存储数据的,就是data,然后就是得有两个指针,一个指向前面的节点,一个就是指向后面的节点,那我们就叫它们一个pre指向前面,一个next指向后面,我们来实现一下吧。

typedef int DListType;
typedef struct DList
{struct DList* pre;struct DList* next;DListType data;}DLNode;

为了方便我们写后面的时候结构体方便一点,我们先定义结构体为DLNode,这样更加方便使用。

现在我们要实现下面的各种接口来完成双链表

首先最重要的就是怎么初始化
初始化的话我们先要想想这个接口函数改的参数和返回值
因为是双向链表,所以得有一个head的头节点,这样才能链接后面的内容

初始化双链表

DLNode* DListInit();

接口函数的名字
这里我们分析首先我们得返回值为什么不是void,而是DLNode*
因为我们要在这里面创建一个头节点,这个节点我们后面都得使用,其次还有一个原因就是这样头节点就不会被销毁,当然我们也可以在外面创建一个节点,然后我们在传它的指针进去,对结构体的内容进行修改,都可以达到相同的作用,废话不多说,我们来实现吧!

DLNode* DListInit()
{DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));assert(pHead);pHead->next = pHead;pHead->pre = pHead;
}

其实很简单,这里必须指针指向自己才可以,如果不这样的话,那我们的循环就不能实现了。
接下来就是怎么打印,打印很简单,我们将它这个指针传过去就行了。

打印双链表

void DListPrint(DLNode* pHead)
{assert(pHead);DLNode* cur = pHead->next;while (cur != pHead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}

打印函数的想法就是我们找head后面的那个节点,然后打印,因为头节点我们不打印,所以取cur开始,因为是循环,所以cur最后会等于pHead,这样的话就是一个循环,所以我们找下一个就行了,然后打印后更新cur。
接下来我们要创建一个节点,这样才能链接起来我们的节点。

DLNode* CreatNewNode(DListType x)
DLNode* CreatNewNode(DListType x)
{DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));assert(newnode);newnode->data = x;newnode->next = NULL;newnode->pre = NULL;return newnode;
}

创造节点好了,接下来就是尾插一个节点进去,我们前面单链表尾插首先要找到尾的位置,然后再去尾插,同时要先找到尾的前一个位置,然后free尾,这样时间复杂度就是O(N),所以效率不是特别高,那我们现在因为head的位置里存放的就是尾的位置,所以不用进行查找了。我们现在来实现一下吧

双链表尾插

void DListPushBACK(DLNode* pHead, DListType x)
{assert(pHead);DLNode* newnode = CreatNewNode(x);DLNode* pre = pHead->pre;pHead->pre = newnode;newnode->next = pHead;pre->next = newnode;newnode->pre = pre;
}

其实尾插也很简单,我们这里先用一个指针保存位置,这样的话下一次插入就可以找到尾的位置,而且还不用注重顺序,这样大大的提升效率

有了尾插那就肯定有头插,一样的办法我们来实现一下

双链表的头插


void DListPushFront(DLNode* pHead, DListType x)
{assert(pHead);DLNode* newnode = CreatNewNode(x);DLNode* next = pHead->next;pHead->next = newnode;newnode->pre = pHead;newnode->next = next;next->pre = newnode;
}

有了头插这些,那肯定还有头删和尾删
那我们也来实现一下吧

尾删

void DListPopBack(DLNode* pHead)
{assert(pHead);if (pHead->next != pHead){DLNode* del = pHead->pre;del->pre->next = pHead;pHead->pre = del->pre;free(del);}
}

前面写的代码都需要测试一下,我们先来测试三个

#include"DList.h"
void test()
{DLNode* head = DListInit();DListPushBack(head, 1);DListPushBack(head, 2);DListPushBack(head, 3);DListPushBack(head, 4);DListPrint(head);DListPushFront(head, 111);DListPushFront(head, 111);DListPushFront(head, 111);DListPrint(head);DListPopBack(head);DListPopBack(head);DListPopBack(head);DListPrint(head);
}
int main()
{test();return 0;
}

发现我们的程序没有问题,我们再来实现一下头删

void DListPopFront(DLNode* pHead)
{assert(pHead);if (pHead->next != pHead){DLNode* del = pHead->next;pHead->next = del->next;del->next->pre = pHead;free(del);}
}

接下来就是双链表的查找,有了查找我们才能和在任意位置的删除和插入连用,那我们现在来实现一下吧


DLNode* DListFind(DLNode* pHead, DListType x)
{assert(pHead);DLNode* cur = pHead->next;while (cur != pHead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}

随机插入

void DListInsert(DLNode* pos, DListType x)
{assrt(pos);DLNode* newnode = CreatNewNode(x);DLNode* pospre = pos->pre;pospre->next = newnode;newnode->pre = pospre;newnode->next = pos;pos->pre = newnode;}

也不是随机插入,是在pos位置之前插入,我们直接传pos和x就行,然后在根据之前的想法一步一步的进行插入链接就行

这里可以更新一下头插和尾插,这里就不演示了
那我们在写一个删除pos位置的函数

删除pos位置

void DListPop(DLNode* pos)
{assert(pos);DLNode* pospre = pos->pre;DLNode* posnext = pos->next;pospre->next = posnext;posnext->pre = pospre;free(pos);
}

还有一个destory我们开辟的空间,这个遍历一遍数组, 然后一个一个释放就行,但是会有问题,我们释放的时候必须看要机记住位置,可以从尾巴开始释放,用一个指针记住前面一个的位置,然后释放掉尾巴,然后更新前一个位置,用while控制一下就行了

#include<stdio.h>
#include<assert.h>
#include<stdlib.h>
typedef int DListType;
typedef struct DList
{struct DList* pre;struct DList* next;DListType data;}DLNode;DLNode* DListInit();void DListPrint(DLNode* pHead);DLNode* CreatNewNode(DListType x);void DListPushBack(DLNode* pHead, DListType x);void DListPushFront(DLNode* pHead, DListType x);void DListPopBack(DLNode* pHead);void DListPopFront(DLNode* pHead);DLNode* DListFind(DLNode* pHead, DListType x);void DListInsert(DLNode* pos, DListType x);void DListPop(DLNode* pos);
#include"DList.h"DLNode* DListInit()
{DLNode* pHead = (DLNode*)malloc(sizeof(DLNode));pHead->next = pHead;pHead->pre = pHead;
}void DListPrint(DLNode* pHead)
{assert(pHead);DLNode* cur = pHead->next;while (cur != pHead){printf("%d ", cur->data);cur = cur->next;}printf("\n");
}DLNode* CreatNewNode(DListType x)
{DLNode* newnode = (DLNode*)malloc(sizeof(DLNode));assert(newnode);newnode->data = x;newnode->next = NULL;newnode->pre = NULL;return newnode;
}void DListPushBack(DLNode* pHead, DListType x)
{DLNode* newnode = CreatNewNode(x);DLNode* pre = pHead->pre;pHead->pre = newnode;newnode->next = pHead;pre->next = newnode;newnode->pre = pre;
}void DListPushFront(DLNode* pHead, DListType x)
{DLNode* newnode = CreatNewNode(x);DLNode* next = pHead->next;pHead->next = newnode;newnode->pre = pHead;newnode->next = next;next->pre = newnode;
}void DListPopBack(DLNode* pHead)
{assert(pHead);if (pHead->next != pHead){DLNode* del = pHead->pre;del->pre->next = pHead;pHead->pre = del->pre;free(del);}
}void DListPopFront(DLNode* pHead)
{assert(pHead);if (pHead->next != pHead){DLNode* del = pHead->next;pHead->next = del->next;del->next->pre = pHead;free(del);}
}DLNode* DListFind(DLNode* pHead, DListType x)
{assert(pHead);DLNode* cur = pHead->next;while (cur != pHead){if (cur->data == x){return cur;}cur = cur->next;}return NULL;
}void DListInsert(DLNode* pos, DListType x)
{assrt(pos);DLNode* newnode = CreatNewNode(x);DLNode* pospre = pos->pre;pospre->next = newnode;newnode->pre = pospre;newnode->next = pos;pos->pre = newnode;}void DListPop(DLNode* pos)
{assert(pos);DLNode* pospre = pos->pre;DLNode* posnext = pos->next;pospre->next = posnext;posnext->pre = pospre;free(pos);
}

谢谢大家,我们下期再见

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

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

相关文章

智慧化工地SaaS平台源码,PC端+APP端+智慧数据可视化大屏端,源码完全开源不封装,自主研发,支持二开,项目使用,微服务+Java++vue+mysql

智慧工地管理平台充分运用数字化技术&#xff0c;聚焦施工现场岗位一线&#xff0c;依托物联网、互联网、AI等技术&#xff0c;围绕施工现场管理的人、机、料、法、环五大维度&#xff0c;以及施工过程管理的进度、质量、安全三大体系为基础应用&#xff0c;实现全面高效的工程…

Windows下 MySql通过拷贝data目录迁移数据库的方法

MySQL数据库的文件目录下图所示&#xff0c; 现举例说明通过COPY文件夹data下数据库文件&#xff0c;进行数据拷贝的步骤&#xff1b;源数据库运行在A服务器上&#xff0c;拷贝到B服务器&#xff0c;假定B服务器上MySQL数据库已经安装完成&#xff0c;为空数据库。 首先进入A服…

[Stable Diffusion教程] 第一课 原理解析+配置需求+应用安装+基本步骤

第一课 原理解析配置需求应用安装基本步骤 本次内容记录来源于B站的一个视频 以下是自己安装过程中整理的问题及解决方法&#xff1a; 问题&#xff1a;stable-diffusion-webui启动No Python at ‘C:\xxx\xxx\python.exe‘ 解答&#xff1a;打开webui.bat 把 if not de…

React Diff算法

文章目录 React Diff算法一、它的作用是什么&#xff1f;二、React的Diff算法1.了解一下什么是调和&#xff1f;2.react的diff算法3.React Diff的三大策略4.tree diff&#xff1a;1、如果DOM节点出现了跨层级操作&#xff0c;Diff会怎么办? 5. component diff&#xff1a;6. e…

SEMIDRIVE X9U 插入 USB 不识别调试要点

一、前言 客户用芯驰 X9U 平台做的智能座舱产品&#xff0c;在烧写固件时发现&#xff0c;通过 USB 连接到 SSA 的 USB 接口&#xff0c;Windows 上无法识别出 USB 设备&#xff0c;一直处在 Ready 状态。 二、SEMIDRIVE X9U 插入 USB 不识别调试要点 ① 建议客户测量 SoC 的…

macOS M1使用TensorFlow GPU加速

本人是在pycharm运行代码&#xff0c;安装了tensorflow版本2.13.0 先运行代码查看有没有使用GPU加速&#xff1a; import tensorflow as tf# Press the green button in the gutter to run the script. if __name__ __main__:physical_devices tf.config.list_physical_dev…

【Vue】vue2项目使用swiper轮播图2023年8月21日实战保姆级教程

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、npm 下载swiper二、使用步骤1.引入库声明变量2.编写页面3.执行js 总结 前言 swiper轮播图官网 参考文章&#xff0c;最好先看完他的介绍&#xff0c;再看…

动手学深度学习—深度卷积神经网络AlexNet(代码详解)

AlexNet 1. 学习表征1.1 缺少的成分&#xff1a;数据1.2 缺少的成分&#xff1a;硬件 2. AlexNet2.1 模型设计2.2 激活函数2.3 容量控制和预处理 3. 读取数据集4. 训练AlexNet ImageNet classification with deep convolutional neural networks 原文链接&#xff1a;https://d…

视频云存储/安防监控视频智能分析网关V3:占道经营功能详解

违规占道经营者经常会在人流量大、车辆集中的道路两旁摆摊&#xff0c;导致公路交通堵塞&#xff0c;给居民出行的造成不便&#xff0c;而且违规占路密集的地方都是交通事故频频发生的区域。 TSINGSEE青犀视频云存储/安防监控视频/AI智能分析网关V3运用视频AI智能分析技术&…

YOLOv5算法改进(5)— 添加ECA注意力机制

前言&#xff1a;Hello大家好&#xff0c;我是小哥谈。ECA注意力机制是一种用于图像处理中的注意力机制&#xff0c;是在通道注意力机制的基础上做了进一步的改进。通道注意力机制主要是通过提取权重&#xff0c;作用在原特征图的通道维度上&#xff0c;而ECA注意力机制则使用了…

git常用操作命令(不定时更新)

git常用操作命令 将某个分支的某次提交迁移到另外一个分支查询这次提交的ID号方法一方法二 切换到目标分支执行commitID合并指令 将某个分支的某次提交迁移到另外一个分支 查询这次提交的ID号 方法一 方法二 切换到目标分支 git checkout 目标分支名 执行commitID合并指令 gi…

MySQL视图

一、视图-介绍及基本语法 视图&#xff08;View&#xff09;是一种虚拟存在的表。视图中的数据并不在数据库中实际存在&#xff0c;行和列数据来自定义视图的查询中使用的表&#xff0c;并且是在使用视图时动态生成的。 通俗的讲&#xff0c;视图只保存了查询的SQL逻辑&#xf…

mysql 、sql server trigger 触发器

sql server mySQL create trigger 触发器名称 { before | after } [ insert | update | delete ] on 表名 for each row 触发器执行的语句块## 表名&#xff1a; 表示触发器监控的对象 ## before | after : 表示触发的时间&#xff0c;before : 表示在事件之前触发&am…

mysql基础——认识索引

一、介绍 “索引”是为了能够更快地查询数据。比如一本书的目录&#xff0c;就是这本书的内容的索引&#xff0c;读者可以通过在目录中快速查找自己想要的内容&#xff0c;然后根据页码去找到具体的章节。 二、优缺点 优势&#xff1a;以快速检索&#xff0c;减少I/O次数&am…

低代码赋能| 智慧园区项目开发痛点及解决方案

智慧园区是一个综合体&#xff0c;集技术开发、产业发展和学术研究于一体。作为未来智慧城市建设的核心&#xff0c;智慧园区充当着“产业大脑”和“指挥中心”的角色。它通过整合园区内的制造资源和第三方服务能力&#xff0c;实现园区各组成部分的协调运作、良性循环和相互促…

课程项目设计--项目建立--宿舍管理系统--springboot后端

前要 项目设计–宿舍管理系统 文章目录 项目建立导入依赖配置文件配置目录结构config配置mybatis-plusswagger 生成实体、mapper和servicebaseEntity统一响应实例响应码接口响应码接口实现统一响应result统一分页响应 项目建立 太长了&#xff0c;修改一下 导入依赖 暂时先加…

yyyy-MM-dd‘T‘HH:mm时间格式探索

yyyy-MM-ddTHH:mm:ss 一直以后这个T是为了避免yyyy-MM-dd HH:mm:ss空格出现解析报错 但是这个T实际是一个标识符&#xff0c;作为小时元素的开始。 T代表后面跟着是时间&#xff0c;Z代表0时区&#xff08;相差北京时间8小时&#xff09; T 即代表 UTC&#xff08;Coodinated U…

【面试】一文讲清组合逻辑中的竞争与冒险

竞争的定义&#xff1a;组合逻辑电路中&#xff0c;输入信号的变化传输到电路的各级逻辑门&#xff0c;到达的时间有先后&#xff0c;也就是存在时差&#xff0c;称为竞争。 冒险的定义&#xff1a;当输入信号变化时&#xff0c;由于存在时差&#xff0c;在输出端产生错误&…

Tokenview再度升级:全新Web3开发者APIs数据服务体验!

Tokenview发布全新版本的区块链APIs和数据服务平台&#xff0c;为开发者打造更强大、更便捷的开发体验&#xff01; 此次升级&#xff0c;我们整合了开发者使用习惯以及Tokenview产品优势。我们深知对于开发者来说&#xff0c;时间是非常宝贵的&#xff0c;因此我们努力提供一…

金融市场中的机器学习;快手推出自研语言模型“快意”

&#x1f989; AI新闻 &#x1f680; OpenAI可能面临《纽约时报》的起诉&#xff0c;侵犯知识产权引发争议 摘要&#xff1a;OpenAI使用《纽约时报》的文章和图片来训练AI模型&#xff0c;违反了《纽约时报》的服务条款&#xff0c;可能面临巨大损失。此前&#xff0c;也有其…