【数据结构初阶】--双向链表(二)

🔥个人主页:@草莓熊Lotso

🎬作者简介:C++研发方向学习者

📖个人专栏: 《C语言》 《数据结构与算法》《C语言刷题集》《Leetcode刷题指南》

⭐️人生格言:生活是默默的坚持,毅力是永久的享受。   

前言:在上篇博客中我们进行了双向链表概念的理解以及哨兵位头节点的初始化,那么我们这次将会继续来实现双向链表中的其它接口,还是一样,分布实现后再把所有的代码展示出来 


目录

 一.双向链表的尾插

二.双向链表的头插 

三. 双向链表的尾删

四.双向链表的头删 

五.双向链表查找

六.双向链表在指定位置之后插入

七.双向链表指定位置删除

八.双向链表的销毁以及初始化部分的优化

九.代码展现

List.h:

List.c:

test.c:


 一.双向链表的尾插

--实现尾插之前,我们需要先实现一个申请新节点的操作,方便后续的使用,具体操作如下:

ListNode* LTBuyNode(LTDataType x)
{ListNode* newcode = (ListNode*)malloc(sizeof(ListNode));newcode->data = x;newcode->next = newcode;newcode->prev = newcode;return newcode;
}

--利用这个我们还可以优化前面的头节点初始化,大家可以自己先尝试一下,接下来我们还是回到尾插的实现

List.c:

//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//申请一个新节点ListNode* newcode = LTBuyNode(x);//phead->prev newcode phead//先连newcodenewcode->prev = phead->prev;newcode->next = phead;//再把phead->prev的先处理掉phead->prev->next = newcode;phead->prev = newcode;
}

重点提示: 

我们先申请一个新节点,再把新节点的前驱指针和后继指针先对应的连上,再处理受到影戏的两个节点,因为要通过头节点找d3,所以我们先处理phead->prev,最后再处理phead

--在测试之前,我们还需要定义一个打印的接口,便于我们观察 

//打印
void LTPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}

--这里的pucr是从第一个节点开始的,也就是哨兵位的下一个节点,直达回到哨兵位结束,哨兵位不打印出来

test.c:

#include"List.h"void test1()
{//初始化,明天优化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);
}
int main()
{test1();return 0;
}

 --测试完成,打印没有问题,退出码为0


二.双向链表的头插 

 --双向链表的头插实现起来也不会很难,但注意这里的头插可不是插入在哨兵位节点的前面哈,而是第一个节点的前面,一定不要搞错了

List.c:

//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newcode = LTBuyNode(x);//phead newcode phead->nextnewcode->prev = phead;newcode->next = phead->next;phead->next->prev = newcode;phead->next = newcode;
}

重点提示: 

这里的大体思路和尾插一样,找到和申请的新节点有关的两个节点,先把newcode的前驱指针和后继指针指向对应位置,再处理需要用phead寻找的phead->next,最后再把phead需要处理的连上就可以了

test.c: 

#include"List.h"void test1()
{//初始化,明天优化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插LTPushFront(plist, 5);LTPrint(plist);
}
int main()
{test1();return 0;
}

--测试完成,打印没有问题,头插了一个5,退出码为0


三. 双向链表的尾删

--实现尾删之前,我们需要先实现一个判空的接口,如果链表为空则不能继续删除了,具体操作如下:

//判空
bool LTEmpty(ListNode* phead)
{assert(phead);return phead->next == NULL;
}

List.c:

//尾删
void LTPopBack(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->prev;//del->prev del pheaddel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

重点提示:

我们先进行一下判空,如果链表不为空继续后面的操作,首先我们需要删除的节点通过phead->prev找到,我们定义一个del,然后尾删操作受到影响的其它两个节点一个为del->prev,一个为head,把它们两个需要连的连上,再释放掉del指针就可以了

test.c: 

#include"List.h"void test1()
{//初始化,明天优化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插LTPushFront(plist, 5);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);
}
int main()
{test1();return 0;
}

--测试完成,打印没有问题,删掉了尾部的4,退出码为0


四.双向链表的头删 

List.c:

//头删
void LTPopFront(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}

重点提示: 

头删操作的思路和尾删相似,先还是判空,然后后续需要通过del记录下phead->next这个我们要删除的节点,再找到两个受到影响的节点,对应连上,最后释放掉del就可以了

test.c: 

#include"List.h"void test1()
{//初始化,明天优化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插LTPushFront(plist, 5);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);//头删LTPopFront(plist);LTPrint(plist);
}
int main()
{test1();return 0;
}

--测试完成,打印没有问题,头删掉了5,退出码为0


五.双向链表查找

--在实现指定位置之前插入以及删除之前,我们需要实现一个查找的接口

List.c:

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

重点提示: 

遍历的方法和打印是一样的,如果在遍历过程中找到了我们需要查找的数据就返回当前位置的节点,没有就返回空

test.c: 

#include"List.h"void test1()
{//初始化,明天优化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插LTPushFront(plist, 5);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);//头删LTPopFront(plist);LTPrint(plist);//查找ListNode*pos=LTFind(plist, 2);if (pos)printf("找到了\n");elseprintf("没找到\n");
}
int main()
{test1();return 0;
}

--测试完成,能够找到,退出码为0


六.双向链表在指定位置之后插入

--我们在这里先实现一下在指定位置之后的插入操作,大家后续可以自己再尝试一下在指定位置之前插入

List.c:

//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newcode = LTBuyNode(x);//pos newcode pos->nextnewcode->prev = pos;newcode->next = pos->next;pos->next->prev = newcode;pos->next = newcode;}

重点提示: 

--在指定位置之后的插入操作其实也没有很难,还是先断言,后续就是先申请一个新节点,跟头插尾插一样,先处理newcode的前驱指针和后继指针,然后再是受到影响的两个节点里面先处理需要通过pos节点找到的pos->next节点,最后再处理pos

test.c: 

#include"List.h"void test1()
{//初始化,明天优化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插LTPushFront(plist, 5);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);//头删LTPopFront(plist);LTPrint(plist);//查找ListNode* pos = LTFind(plist, 2);//指定位置之后插入LTInsert(pos, 100);LTPrint(plist);}
int main()
{test1();return 0;
}

--测试完成,打印没有问题,在2后插入了100,退出码为0


七.双向链表指定位置删除

List.c:

//指定位置删除
void LTErase(ListNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

重点提示: 

先断言,后续操作思路和头删尾删也很像,这里是通过pos指针找到两个受到影响的节点,我们直接处理好这两个节点之前的关系就可以了,最后再直接释放掉pos

test.c: 

#include"List.h"void test1()
{//初始化,明天优化ListNode* plist = NULL;LTInit(&plist);//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插LTPushFront(plist, 5);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);//头删LTPopFront(plist);LTPrint(plist);//查找ListNode* pos = LTFind(plist, 2);//指定位置之后插入LTInsert(pos, 100);LTPrint(plist);//指定位置删除LTErase(pos);LTPrint(plist);
}
int main()
{test1();return 0;
}

--测试完成,打印没有问题,退出码为0


八.双向链表的销毁以及初始化部分的优化

--在这里我们先来实现一下双向链表的销毁,具体的遍历操作和之前一样,我们在遍历过程中每次销毁一个节点之前先把它的下一个节点存下来,最后销毁完后利用存下来的使它来到下一个位置,具体操作代码如下

//销毁
void LTDestory(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

 --大家需要注意的是我们这里其实按道理来说是要用二级指针的,但是前面其它接口都用的一级,这里和初始化部分也需要统一比较好点,我们可以在测试文件中最后销毁完手动将头节点置为空,那么我们的初始化操作的优化我也直接给大家展示为代码了,其实就是改变了一下函数的返回类型,测试文件中也有所修改,在最后的代码展现的时候大家可以看看

//头节点初始化的优化
ListNode* LTInit()
{ListNode* phead = LTBuyNode(-1);return phead;
}

九.代码展现

List.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;
typedef struct ListNode
{LTDataType data;//前驱指针,指向前一个指针struct ListNode* prev;//后继指针,指向后一个指针struct ListNode* next;
}ListNode;//初始化头节点
void LTInit(ListNode** pphead);
//ListNode* LTInit();
//打印
void LTPrint(ListNode* phead);
//销毁
void LTDestory(ListNode* phead);
//尾插
void LTPushBack(ListNode* phead, LTDataType x);
//头插
void LTPushFront(ListNode* phead, LTDataType x);
//尾删
void LTPopBack(ListNode* phead);
//头删
void LTPopFront(ListNode* phead);
//查找
ListNode* LTFind(ListNode* phead,LTDataType x);
//判空
bool LTEmpty(ListNode* phead);
//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x);
//指定位置删除
void LTErase(ListNode* pos);

List.c:

#include"List.h"//头节点初始化
void LTInit(ListNode** pphead)
{ListNode* ph = (ListNode*)malloc(sizeof(ListNode));if (ph==NULL){perror("malloc fail!");exit(1);}*pphead = ph;(*pphead)->data = -1;//随便给个不用的就行(*pphead)->prev = *pphead;(*pphead)->next = *pphead;
}//头节点初始化的优化
//ListNode* LTInit()
//{
//	ListNode* phead = LTBuyNode(-1);
//	phead->prev = phead;
//	phead->next = phead;
//	return phead;
//}//打印
void LTPrint(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){printf("%d -> ", pcur->data);pcur = pcur->next;}printf("\n");
}//销毁
void LTDestory(ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){ListNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead =NULL;
}
//判空
bool LTEmpty(ListNode* phead)
{assert(phead);return phead->next == NULL;
}ListNode* LTBuyNode(LTDataType x)
{ListNode* newcode = (ListNode*)malloc(sizeof(ListNode));newcode->data = x;newcode->next =newcode;newcode->prev =newcode;return newcode;
}
//尾插
void LTPushBack(ListNode* phead, LTDataType x)
{assert(phead);//申请一个新节点ListNode* newcode = LTBuyNode(x);//phead->prev newcode phead//先连newcodenewcode->prev = phead->prev;newcode->next = phead;//再把phead->prev的先处理掉phead->prev->next = newcode;phead->prev = newcode;
}//头插
void LTPushFront(ListNode* phead, LTDataType x)
{assert(phead);ListNode* newcode = LTBuyNode(x);//phead newcode phead->nextnewcode->prev = phead;newcode->next = phead->next;phead->next->prev = newcode;phead->next = newcode;
}//尾删
void LTPopBack(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->prev;//del->prev del pheaddel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(ListNode* phead)
{assert(!LTEmpty(phead));ListNode* del = phead->next;//phead del del->nextphead->next = del->next;del->next->prev = phead;free(del);del = NULL;
}//查找
ListNode* LTFind(ListNode* phead,LTDataType x)
{assert(!LTEmpty(phead));ListNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x)return pcur;pcur = pcur->next;}return NULL;
}//指定位置之后插入
void LTInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newcode = LTBuyNode(x);//pos newcode pos->nextnewcode->prev = pos;newcode->next = pos->next;pos->next->prev = newcode;pos->next = newcode;}//指定位置删除
void LTErase(ListNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

test.c:

#include"List.h"void test1()
{//初始化ListNode* plist = NULL;LTInit(&plist);////优化//ListNode* plist = LTInit();//尾插LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插LTPushFront(plist, 5);LTPrint(plist);//尾删LTPopBack(plist);LTPrint(plist);//头删LTPopFront(plist);LTPrint(plist);//查找ListNode* pos = LTFind(plist, 2);/*if (pos)printf("找到了\n");elseprintf("没找到\n");*///指定位置之后插入LTInsert(pos, 100);LTPrint(plist);//指定位置删除LTErase(pos);LTPrint(plist);//销毁LTDestory(plist);plist == NULL;
}
int main()
{test1();return 0;
}

特别补充--顺序表和单链表的对比


往期回顾:

【数据结构初阶】--单链表(一)

【数据结构初阶】--单链表(二)

【数据结构初阶】--双向链表(一)

结语: 在这篇博客中我们实现了双向链表的所有接口,大家下来也可以自己去尝试实现以下,可以通过画图辅助,如果文章对你有帮助的话,欢迎评论,点赞,收藏加关注,感谢大家的支持。

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

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

相关文章

vue-cli 模式下安装 uni-ui

目录 easycom 自定义easycom配置的示例 npm安装 uni-ui 准备 sass 安装 uni-ui 注意 easycom 传统vue组件&#xff0c;需要安装、引用、注册&#xff0c;三个步骤后才能使用组件。easycom将其精简为一步。 只要组件路径符合规范&#xff08;具体见下&#xff09;&#…

JavaSE-接口

概念在Java中&#xff0c;接口可以被看成是一种公共规范&#xff0c;是一种引用数据类型。语法1.接口的定义格式与类的定义格式基本相同&#xff0c;将class关键字替换为interface关键字&#xff1a;public interface IShape {}2.类与接口之间使用implements关键字来实现接口&a…

常用类学习

文章目录字符串相关的类String的特性String对象的创建字符串相关的类String类与其他结构之间的转换StringBuffer,StringBuilderStringBuffer类的常用方法JDK8之前日期时间APIjava.lang.System类java.util.Date类java.text.SimpleDateFormat类java.util.Calendar类JDK8中新日期时…

【Python库包】Gurobi-Optimize (求解 MIP) 安装

目录Step1&#xff1a;注册账号Step2&#xff1a;获取Licence另&#xff1a;完整安装 Gurobi软件参考本博客简介Gurobi-Optimizer的安装&#xff08;Python 环境&#xff09;。 Step1&#xff1a;注册账号 官网-Gurobi-Optimizer ⚠️注意&#xff1a; Gurobi 是商业软件&…

【渗透测试】NmapScanHelper 扫描辅助工具

目录NmapScanHelper 扫描辅助工具一、功能特性二、文件说明三、使用方法1. 安装依赖macOSUbuntu/DebianCentOS/RHEL2. 配置网段3. 运行扫描基本用法常用端口扫描示例扫描模式特殊环境模式选择性扫描自定义文件4. 查看结果四、扫描模式说明标准模式特殊环境模式五、支持的 Nmap …

Python爬虫入门到实战(1)-requests库

一.网络爬虫库网络爬虫通俗来讲就是使用代码将HTML网页的内容下载到本地的过程。爬取网页主要是为了获取网之间需要中的关键信息&#xff0c;例如网页中的数据、图片、视频等。urllib库:是Python自带的标准库&#xff0c;无须下载、安装即可直接使用。urllib库中包含大量的爬虫…

深入理解设计模式之代理模式:原理、实现与应用

在软件开发中&#xff0c;我们经常需要控制对某些对象的访问——可能是为了延迟加载、添加额外功能或保护敏感资源。这正是代理模式大显身手的地方。作为结构型设计模式的重要成员&#xff0c;代理模式在众多知名框架和系统中扮演着关键角色。本文将全面剖析代理模式的方方面面…

VSCode - VSCode 快速跳转标签页

VSCode 快速跳转标签页 1、标签页列表快速跳转 通过快捷键 Ctrl Tab 即可快速跳转标签页 # 操作方式先按住 Ctrl 键&#xff0c;再按 Tab 键&#xff0c;此时&#xff0c;即可打开标签页列表&#xff08;保持 Ctrl 键一直按住&#xff09;然后&#xff0c;再按 Tab 键&#xf…

深入理解设计模式:享元模式(Flyweight Pattern)

在软件开发中&#xff0c;我们经常会遇到需要创建大量相似对象的情况。如果每个对象都独立存储所有数据&#xff0c;将会消耗大量内存资源&#xff0c;导致系统性能下降。享元模式&#xff08;Flyweight Pattern&#xff09;正是为解决这一问题而生的经典设计模式。本文将深入探…

网络大提速,RDMA,IB,iWrap

本章第一节介绍的存储设备方面的创新解决了CPU访问存储设备的性能问题。但在实际的业务当中,数据的传输除了在节点内部的CPU与存储设备间外,节点之间也存在数据传输的需求。本节我们就介绍在网络传输方面是如何提速的。 在介绍新的网络技术之前,我们看看传统网络是如何传输…

【C++】红黑树,“红“与“黑”的较量

各位大佬好&#xff0c;我是落羽&#xff01;一个坚持不断学习进步的大学生。 如果您觉得我的文章有所帮助&#xff0c;欢迎多多互三分享交流&#xff0c;一起学习进步&#xff01; 也欢迎关注我的blog主页: 落羽的落羽 一、红黑树的概念与规则 红黑树是一种更加特殊的平衡二…

【愚公系列】《MIoT.VC》001-认识、安装 MIoT.VC 软件

💎【行业认证权威头衔】 ✔ 华为云天团核心成员:特约编辑/云享专家/开发者专家/产品云测专家 ✔ 开发者社区全满贯:CSDN博客&商业化双料专家/阿里云签约作者/腾讯云内容共创官/掘金&亚马逊&51CTO顶级博主 ✔ 技术生态共建先锋:横跨鸿蒙、云计算、AI等前沿领域…

git:tag标签远程管理

git tag v1&#xff1a;在当前所在分支创建标签v1git tag -a v2 -m release version&#xff1a;创建一个带有附注的标签git tag -d v2&#xff1a;删除本地标签git tag&#xff1a;查看标签git push origin 标签1 标签2……&#xff1a;把多个标签推送到远程git push origin -…

力扣 hot100 Day49

105. 从前序与中序遍历序列构造二叉树 给定两个整数数组 preorder 和 inorder &#xff0c;其中 preorder 是二叉树的先序遍历&#xff0c; inorder 是同一棵树的中序遍历&#xff0c;请构造二叉树并返回其根节点。 //抄的 class Solution { private:unordered_map<int, i…

jvm-sandbox-repeater 录制和回放

https://github.com/alibaba/jvm-sandbox-repeater/blob/master/docs/user-guide-cn.md 快速录制自己应用 step0 安装sandbox和插件到应用服务器 curl -s https://github.com/alibaba/jvm-sandbox-repeater/releases/download/v1.0.0/install-repeater.sh | sh step1 修改repe…

【C++底层剖析】++a vs a++:到底谁是左值,谁是右值?

在 C 编程中&#xff0c;我们经常使用 a 和 a 来实现自增操作。乍一看它们只是“先加还是后加”的语法糖&#xff0c;但你真的理解它们的底层机制、返回值类型和左值右值属性吗&#xff1f;1. a 和 a 的基础区别表达式名称语义返回值类型左值 / 右值a前置自增先将 a 加 1&#…

【世纪龙科技】汽车故障诊断与排除仿真教学软件让课堂更高效安全

随着汽车产业向智能化、电动化快速转型&#xff0c;职业院校汽修专业的教学模式正面临全新挑战。传统实车实训存在成本高、风险大、场景单一等问题&#xff0c;而行业对人才的要求却越来越高——既需要扎实的理论基础&#xff0c;又必须具备熟练的故障诊断能力。如何在保证安全…

网络基础9:按流负载均衡实验(等价路由)

实验eNS拓扑图&#xff1a;1. 网络拓扑与 IP 配置AR5&#xff1a;GE0/0/0: 192.168.1.1/24&#xff08;连接 AR6&#xff09;GE0/0/1: 192.168.3.1/24&#xff08;连接 AR8&#xff09;Loopback0: 1.1.1.1/32&#xff08;源地址&#xff09;AR6&#xff1a;GE0/0/0: 192.168.1.…

4G模块 A7680发送中文短信到手机

命令说明 基础AT指令 ATi显示产品的标志信息 ATCIMI查询IMSI ATCICCID从SIM卡读取ICCID ATCGSN查询产品序列号 ATCPIN查询卡状态 ATCSQ查询信号强度 ATCGATT查询当前PS域状态 ATCREG查询GPRS注册状态 ATCEREG查询4G注册状态 ATCGPADDR查询PDP地址 ATCMGF选择短信格式 ATCMGS发…

深度学习-线性神经网络

文章目录线性回归基本概念随机梯度下降矢量化加速正态分布和平方损失极大似然估计线性回归实现从0开始**torch.no_grad()的两种用途****为什么需要 l.sum().backward()&#xff1f;**调用现成库softmax回归图像数据集从0开始实现softmax利用框架API实现课程学习自李牧老师B站的…