当前位置: 首页 > news >正文

双向链表的实现(详解)

目录

  • 前言
  • 初始化
  • 双向链表的结构
  • 为双向链表的节点开辟空间
  • 头插
  • 尾插
  • 打印链表
  • 尾删
  • 头删
  • 查找
  • 指定位置之后的插入
  • 删除pos节点
  • 销毁双向链表

前言

链表的分类: 带头 不带头 单向 双向 循环 不循环
一共有 (2 * 2 * 2) 种链表

带头指的是:带有哨兵位节点
哨兵位(头结点):可以放随机数据,哨兵位指向的下一个节点就是我们的第一个有效节点,我们指的头节点是哨兵位
在这里插入图片描述
单向:指针只能从前向后遍历
双向:指针既可以从前向后遍历又可以从后向前遍历
循环:可以通过尾节点找到头节点,从而达到循环
在这里插入图片描述

主要使用的链表是单链表和双向链表
单链表:不带头单向不循环
双向链表:带头双向循环

初始化

ListNode* TLInit()
{ListNode* phead = ListByNode(-1);//ListByNode后面会介绍//为头节点开辟一个空间,并将头结点指向的值赋值为-1return phead;//将开辟出的头节点返回我们的主函数,主函数中的头节点就知道我们有一个哨兵位了
}
//初始化
void TLInit(ListNode** pphead)
{//给双向链表创建一个哨兵位*pphead = ListByNode(-1);
}

初始化有两种写法,第二种写法也是可行的,但是用第一种,可以使得接口一致,都是一级指针,使用者也会更方便的使用,不用去记忆那个要用一级指针还是二级指针

双向链表的结构

//定义双向链表的结构
typedef int DataType;
typedef struct ListNode//双向链表
{DataType x;//双向链表中的数据struct ListNode* next;//指向后一个节点,后继指针struct ListNode* prev;//指向前一个节点,前驱指针
}ListNode;

为双向链表的节点开辟空间

ListNode* ListByNode(DataType x)
{ListNode* node = (ListNode*)malloc(sizeof(ListNode));if (node == NULL){perror("malloc");return NULL;}//开辟成功node->next = node->prev = node;//初始化一个哨兵位的下一个节点和前一个节点指向的是自己node->x = x;return node;
}

头插

//头插
//在第一个有效节点之前插入一个节点
void TLPushFront(ListNode* phead,DataType x)
//用一级指针为了不改变原链表的哨兵位
{assert(phead);//断言一下是不是空链表ListNode* newnode = ListByNode(x);ListNode* pcur = phead->next;newnode->next = pcur;newnode->prev = phead;pcur->prev = newnode;phead->next = newnode;}

在这里插入图片描述

尾插

//尾插
//在头节点之后或者之前插入
//因为在哨兵位前,哨兵位的prev指向尾结点,尾结点的next指向哨兵位
void TLPushBack(ListNode* phead,DataType x)
{assert(phead);//链表不为空ListNode* newnode = ListByNode(x);//为尾插的节点开辟空间ListNode* pcur = phead->prev; newnode->next = phead;newnode->prev = pcur;pcur->next = newnode;phead->prev = newnode;
}

在这里插入图片描述

打印链表

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

尾删

//尾删
//注意哨兵位不能被删除,所以理论上至少有一个节点,才能够删除
void TLPopBack(ListNode* phead)
{assert(phead&&phead->next!=phead);ListNode* pcur = phead->prev;ListNode* del = pcur->prev;del->next = phead;phead->prev = del;free(pcur);pcur = NULL;}

在这里插入图片描述

头删

//头删
//注意哨兵位不能被删除,所以理论上至少有一个节点,才能够删除
void TLPopFront(ListNode* phead)
{assert(phead&&phead->next!=phead);//phead不能为空ListNode* pcur = phead->next;pcur->next->prev = phead;phead->next = pcur->next;free(pcur);pcur = NULL;}

在这里插入图片描述

查找

//查找 x 数据的位置并返回
ListNode* SLFind(DataType x,ListNode* phead)
{ListNode* pcur = phead->next;while (pcur != phead){if (pcur->x == x){return pcur;//找到了}pcur = pcur->next;}return NULL;//找不到了
}

指定位置之后的插入

//指定位置之后的插入
//知道了pos节点,就知道了pos之前的数和之后的数
//指定位置之后的插入和指定位置之前的插入是一样的
void TLInsert(ListNode* pos,DataType x)
{assert(pos);//插入的pos位置不能为空ListNode* newnode = ListByNode(x);//为插入的数据开辟空间ListNode* pcur = pos->next;newnode->next = pcur;newnode->prev = pos;pos->next = newnode;pcur->prev = newnode;}

在这里插入图片描述

删除pos节点

//删除pos节点
void Erase(ListNode* pos)
{assert(pos);//理论上pos不能为phead,因为phead不能被删除,它是双向链表pos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;}

在这里插入图片描述

销毁双向链表

//销毁双向链表
void LTDestroy(ListNode* phead)
{assert(phead);//phead不为空,才销毁,为空,不用销毁//销毁时phead也要释放(销毁)ListNode* pcur = phead->next;ListNode* next = pcur->next;while (pcur != phead){next = pcur->next;free(pcur);pcur = next;}//出来后pcur指向pheadfree(phead);phead = NULL;
}

相关文章:

双向链表的实现(详解)

目录 前言初始化双向链表的结构为双向链表的节点开辟空间头插尾插打印链表尾删头删查找指定位置之后的插入删除pos节点销毁双向链表 前言 链表的分类: 带头 不带头 单向 双向 循环 不循环 一共有 (2 * 2 * 2) 种链表 带头指的是:带有哨兵位节点 哨兵位&a…...

SpringBoot项目中如何使用校验工具

用到hutool提供的校验方法与java提供的校验方法 1. 声明数据 String str "123" String regex "^123456$" Boolean is1_6 mismatch(str, regex);2. 定义校验方法 // 校验是否不符合正则格式 private static boolean mismatch(String str, String rege…...

AI预测小分子与蛋白的相关特征: MegaMolBART, MoFlow,ESM-1, ESM-2

1、小分子:MegaMolBART, MoFlow 1)MegaMolBART https://github.com/NVIDIA/MegaMolBART 基于 SMILES 的小分子药物发现与化学信息学深度学习模型。 2)MoFlow https://github.com/calvin-zcx/moflow 用flow流方式分子生成 2、蛋白质:ESM-1, ESM-2 https://github.com/fa…...

基于深度学习的花卉检测系统(含PyQt界面)

基于深度学习的花卉检测系统(含PyQt界面) 前言一、数据集1.1 数据集介绍1.2 数据预处理 二、模型搭建三、训练与测试3.1 模型训练3.2 模型测试 四、PyQt界面实现参考资料 前言 本项目是基于swin_transformer深度学习网络模型的花卉检测系统,…...

深度学习图像处理基础工具——opencv 实战信用卡数字识别

任务 信用卡数字识别 穿插之前学的知识点 形态学操作 模板匹配 等 总体流程与方法 1.有一个模板 2 用轮廓检测把模板中数字拿出来 外接矩形(模板和输入图像的大小要一致 )3 一系列预处理操作 问题的解决思路 1.分析准备:准备模板&#…...

【HBase】HBase高性能架构:如何保证大规模数据的高可用性

HBase高性能原理 HBase 能够提供高性能的数据处理能力,主要得益于其设计和架构的几个关键方面。这些设计特点使得 HBase 特别适合于大规模、分布式的环境中进行高效的数据读写操作。以下是 HBase 高性能的主要原因: 1. 基于列的存储 HBase 是一个列式…...

JAVA基础两个项目案例代码

1.JAVA使用ArrayList上架菜品案例 视频参考链接 创建一个Food.java类 package org.example;// 菜品类 public class Food {private String name; // 菜品名private double price; // 价格private String desc; // 菜品描述public Food() {}public Food(String name, Double …...

asp.net core 网页接入微信扫码登录

创建微信开放平台账号&#xff0c;然后创建网页应用 获取appid和appsecret 前端使用的vue&#xff0c;安装插件vue-wxlogin 调用代码 <wxlogin :appid"appId" :scope"scope" :redirect_uri"redirect_uri"></wxlogin> <scri…...

【板栗糖GIS】如何给微软拼音输入法加上小鹤双拼

【板栗糖GIS】如何给微软拼音输入法加上小鹤双拼 用过在注册表里新建的方法&#xff0c;结果弄完没有出现小鹤双拼方案&#xff0c;想到了自己写reg表 目录 1. 新建一个txt文件 2. 把.txt的后缀名改成.reg&#xff0c;双击运行 3. 在设置中找到微软输入法-常规 1. 新建一个…...

如何解决微信小程序无法使用css3过度属性transition

由于微信小程序不支持CSS3过度属性transition,所以我们需要利用微信小程序api进行画面过度的展示 首先是官方示例: wxml: <view animation="{{animationData}}" style="background:red;height:100rpx;width:100rpx"></view> js: Page(…...

【软件设计师知识点】九、网络与信息安全基础知识

文章目录 计算机网络的概念网络分类网络拓扑结构网络体系结构ISO/OSI 7层参考模型TCP/IP 4层模型TCP/IP 协议族应用层协议传输层协议网络层协议IP 地址IPV4 数据报IP 地址分类子网划分子网掩码IPv6地址...

广东省道路货物运输资格证照片回执可手机线上办理

广东省道路运输资格证是从事道路运输业务、危险品道路运输人员的必要证件&#xff0c;而在办理该证件的过程中&#xff0c;驾驶员照片回执是一项必不可少的材料。随着科技的发展和移动互联网的普及&#xff0c;现在办理驾驶员照片回执已经不再需要亲自前往照相馆&#xff0c;而…...

【微信小程序——案例——本地生活(列表页面)】

案例——本地生活&#xff08;列表页面&#xff09; 九宫格中实现导航跳转——以汽车服务为案例&#xff08;之后可以全部实现页面跳转——现在先实现一个&#xff09; 在app.json中添加新页面 修改之前的九宫格view改为navitage 效果图&#xff1a; 动态设置标题内容—…...

【设计模式】SOLID设计原则

1、什么是SOLID设计原则 SOLID 是面向对象设计中的五个基本设计原则的首字母缩写&#xff0c;它们是&#xff1a; 单一职责原则&#xff08;Single Responsibility Principle&#xff0c;SRP&#xff09;&#xff1a; 类应该只有一个单一的职责&#xff0c;即一个类应该有且只…...

基于java+springboot+vue实现的智能停车计费系统(文末源码+Lw+ppt)23-30

摘 要 随着人们生活水平的高速发展&#xff0c;智能停车计费信息管理方面在近年来呈直线上升&#xff0c;人们也了解到智能停车计费的实用性&#xff0c;因此智能停车计费的管理也逐年递增&#xff0c;智能停车计费信息的增加加大了在管理上的工作难度。为了能更好的维护智能…...

IntelliJ IDEA 2022.3.2 解决decompiled.class file bytecode version:52.0(java 8)

1 背景 使用idea 打开一个Kotlin语言编写的demo项目&#xff0c;该项目使用gradle构建。其gradle文件如下&#xff1a; plugins {id javaid org.jetbrains.kotlin.jvm version 1.8.20 } group me.administrator version 1.0-SNAPSHOTrepositories {mavenCentral()jcenter()…...

C++11 设计模式1. 模板方法(Template Method)模式学习。UML图

一 什么是 "模板方法&#xff08;Template Method&#xff09;模式" 在固定步骤确定的情况下&#xff0c;通过多态机制在多个子类中对每个步骤的细节进行差异化实现&#xff0c;这就是模板方法模式能够达到的效果。 模板方法模式属于&#xff1a;行为型模式。 二 &…...

HarmonyOS实战开发-自定义分享

介绍 自定义分享主要是发送方将文本&#xff0c;链接&#xff0c;图片三种类型分享给三方应用,同时能够在三方应用中展示。本示例使用数据请求 实现网络资源的获取&#xff0c;使用屏幕截屏 实现屏幕的截取&#xff0c;使用文件管理 实现对文件&#xff0c;文件目录的管理&…...

Spring源码刨析之配置文件的解析和bean的创建以及生命周期

public void test1(){XmlBeanFactory xmlBeanFactory new XmlBeanFactory(new ClassPathResource("applicationContext.xml"));user u xmlBeanFactory.getBean("user",org.xhpcd.user.class);// System.out.println(u.getStu());}先介绍一个类XmlBeanFac…...

如何使用 Grafana 监控文件系统状态

当 JuiceFS 文件系统部署完成并投入生产环境&#xff0c;接下来就需要着手解决一个非常重要的问题 —— 如何实时监控它的运行状态&#xff1f;毕竟&#xff0c;它可能正在为关键的业务应用或容器工作负载提供持久化存储支持&#xff0c;任何小小的故障或性能下降都可能造成不利…...

智能革命:未来人工智能创业的天地

智能革命&#xff1a;未来人工智能创业的天地 一、引言 在这个数字化迅速变革的时代&#xff0c;人工智能(AI)已经从一个边缘科学发展成为推动未来经济和社会发展的关键动力。这一技术领域的飞速进步&#xff0c;不仅影响着科技行业的每一个角落&#xff0c;更是为创业者提供了…...

4月14日总结

java学习 一.多线程 简介&#xff1a;多线程是计算机科学中的一个重要概念&#xff0c;它允许程序同时执行多个任务或操作。在单个程序内部&#xff0c;多线程使得代码可以并行执行&#xff0c;从而提高程序的性能和响应速度。 这里先来介绍一下创建多线程的几种方法。 1.扩展…...

kafka---broker相关配置

一、Broker 相关配置 1、一般配置 broker.id 当前kafka服务的sid(server id)&#xff0c;在kafka集群中&#xff0c;该值是唯一的&#xff08;unique&#xff09;&#xff0c;如果未设置此值&#xff0c;kafka会自动生成一个int值&#xff1b;为了防止自动生成的值与用户设置…...

【Golang学习笔记】从零开始搭建一个Web框架(二)

文章目录 模块化路由前缀树路由 前情提示&#xff1a; 【Golang学习笔记】从零开始搭建一个Web框架&#xff08;一&#xff09;-CSDN博客 模块化路由 路由在kilon.go文件中导致路由和引擎交织在一起&#xff0c;如果要实现路由功能的拓展增强&#xff0c;那将会非常麻烦&…...

高精度地图导航论文汇总

文章目录 2021基于车载激光点云的高精地图矢量化成图[J] 2022基于高精度地图的智能车辆路径规划与跟踪控制研究[M] 2023一种无人驾驶融合决策方案的设计与实现[M] 2021 基于车载激光点云的高精地图矢量化成图[J] 摘要&#xff1a; 针对车载激光点云中对各特征物提取结果后矢量…...

【域适应】基于域分离网络的MNIST数据10分类典型方法实现

关于 大规模数据收集和注释的成本通常使得将机器学习算法应用于新任务或数据集变得异常昂贵。规避这一成本的一种方法是在合成数据上训练模型&#xff0c;其中自动提供注释。尽管它们很有吸引力&#xff0c;但此类模型通常无法从合成图像推广到真实图像&#xff0c;因此需要域…...

从零实现诗词GPT大模型:pytorch框架介绍

专栏规划: https://qibin.blog.csdn.net/article/details/137728228 因为咱们本系列文章主要基于深度学习框架pytorch进行,所以在正式开始之前,现对pytorch框架进行一个简单的介绍,主要面对深度学习或者pytorch还不熟悉的朋友。 一、安装pytorch 这一步很简单,主要通过p…...

[目标检测] OCR: 文字检测、文字识别、text spotter

概述 OCR技术存在两个步骤&#xff1a;文字检测和文字识别&#xff0c;而end-to-end完成这两个步骤的方法就是text spotter。 文字检测数据集摘要 daaset语言体量特色MTWI中英文20k源于网络图像&#xff0c;主要由合成图像&#xff0c;产品描述&#xff0c;网络广告(淘宝)MS…...

Windows环境下删除MySQL

文章目录 一、关闭MySQL服务1、winR打开运行&#xff0c;输入services.msc回车2、服务里找到MySQL并停止 二、卸载MySQL软件1、打开控制模板--卸载程序--卸载MySQL相关的所有组件 三、删除MySQL在物理硬盘上的所有文件1、删除MySQL的安装目录&#xff08;默认在C盘下的Program …...

uniapp:uview-plus的一些记录

customStyle 并不是所有的组件都有customStyle属性来设置自定义属性&#xff0c;有的还是需要通过::v-deep来修改内置样式 form表单 labelStyle 需要的是一个对象 :labelStyle"{color: #333333,fontSize: 32rpx,fontWeight: 500}"dateTimePicker选择器设置默认值…...

网站建设公司 北京/哪里注册域名最便宜

1、什么是 Maven 插件&#xff1f; 上一篇博客我们讲了 Maven 的生命周期&#xff0c;我们知道 Maven 的核心是生命周期&#xff0c;生命周期指定了 Maven 命令执行的流程顺序。但是真正实现流程的工程是由插件来完成的。 我们也可以说 Maven 是一个执行插件的框架&#xff0c;…...

镇江网站建设联系思创/sem是什么电镜

在总部位于新加坡的员工福利初创公司CXA Group对我们的核心Web平台进行评估的过程中&#xff0c;我们决定将方向从陈旧的现有体系结构转向&#xff0c;从头开始重建前端。 该平台面临的挑战之一是创建一个在CXA Group的12个目标国家/地区&#xff08;在整个亚洲&#xff09;都能…...

网站留言效果怎么做/好看的友情链接代码

1、筛选符合条件的记录要筛选顾客为“天津大宇”的所有记录(点击图片动起来)2、筛选符合条件的部分记录要筛选顾客为“天津大宇”的部分记录&#xff0c;可以将“复制到”区域中提前写上需要得到的字段标题。3、筛选同时符合两个条件的记录要筛选同时符合两个条件的记录&#x…...

企业英文网站建设的重要性/百度账户推广登陆

电话号码的字母组合 给定一个仅包含数字 2-9 的字符串&#xff0c;返回所有它能表示的字母组合。答案可以按 任意顺序 返回。 给出数字到字母的映射如下&#xff08;与电话按键相同&#xff09;。注意 1 不对应任何字母。 示例 1&#xff1a; 输入&#xff1a;digits “2…...

wordpress多个视频/怎么做网络营销推广啊

前言Vue是一套用于构建用户界面的渐进式框架,目前有越来越多的开发者在学习和使用.在笔者写完 从0到1教你搭建前端团队的组件系统 之后很多朋友希望了解一下如何搭建基于vue的组件系统,所以作为这篇文章的补充,本文来总结一下如何搭建基于vue的组件库.虽然笔者有近2年没有从事v…...

广东省两学一做网站/油烟机seo关键词

写在前面 对 CSS 布局掌握程度决定你在 Web 开发中的开发页面速度。随着 Web 技术的不断革新&#xff0c;实现各种布局的方式已经多得数不胜数了。 最近利用碎片时间&#xff0c;大概用了半个月的时间整理了一个系列&#xff0c;本系列文章总结了 CSS 中的各种布局&#xff0…...