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

【数据结构】双向链表(C语言)

哈喽铁子们,这里是博主鳄鱼皮坡。这篇文章将分享交流双向链表的相关知识,下面正式开始。

1. 双向链表的结构

注意:这里的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严
谨,但是为了老铁们更好的理解就直接称为单链表的头节点。
带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这⾥“放哨
的”。而“哨兵位”存在的意义: 遍历循环链表避免死循环。

2. 双向链表的实现

以尾插为例:

第一步:assert(phead); 防止为空。

第二步:创建新节点,和单链表一样用LTBuyNode()函数即可。

第三步:先将新节点指向原链表,由双向链表的特性,我们就不需要像单链表一样遍历去找。newnode->prev即为上图的d3。

       (1) newnode->prev = phead->prev;先将新节点的头部指向原链表的最后一个节点,即d3。

       (2) newnode->next = phead;而后将新节点的尾部指向原链表的哨兵位。

第四步:将原链表相应的位置指向新节点

       (1)phead->prev->next = newnode;原链表的最后节点尾部指向新节点

       (2)phead->prev = newnode;原链表的哨兵位头部指向新节点

//尾插
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;
}

只要理清楚双向链表节点的指向关系,之后和单链表结构相似。

双链表的代码如下: 

//List.c
#include"List.h"void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d->", pcur->data);pcur = pcur->next;}printf("\n");
}//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail!");exit(1);}node->data = x;node->next = node->prev = node;return node;
}
//初始化
//void LTInit(LTNode** pphead)
//{
//	//给双向链表创建一个哨兵位
//	*pphead = LTBuyNode(-1);
//}
LTNode* LTInit()
{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 LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);//phead newnode phead->nextnewnode->next = phead->next;newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{//链表必须有效且链表不能为空(只有一个哨兵位)assert(phead && phead->next != phead);LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;//删除del节点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;//删除del节点free(del);del = NULL;
}LTNode* LTFind(LTNode* phead, LTDataType x)
{LTNode* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}//没有找到return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTBuyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除pos节点
void LTErase(LTNode* pos)
{//pos理论上来说不能为phead,但是没有参数phead,无法增加校验assert(pos);//pos->prev pos pos->nextpos->next->prev = pos->prev;pos->prev->next = pos->next;free(pos);pos = NULL;
}void LTDesTroy(LTNode* phead)
{assert(phead);LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}//此时pcur指向phead,而phead还没有被销毁free(phead);phead = NULL;
}
//List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>//定义节点的结构
//数据 + 指向下一个节点的指针
typedef int SLTDataType;typedef struct SListNode {SLTDataType data;struct SListNode* next;
}SLTNode;void SLTPrint(SLTNode* phead);//尾插
void SLTPushBack(SLTNode** pphead, SLTDataType x);
//头插
void SLTPushFront(SLTNode** pphead, SLTDataType x);
//尾删
void SLTPopBack(SLTNode** pphead);
//头删
void SLTPopFront(SLTNode** pphead);//查找
SLTNode* SLTFind(SLTNode* phead, SLTDataType x);//在指定位置之前插入数据
void SLTInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(SLTNode* pos, SLTDataType x);//删除pos节点
void SLTErase(SLTNode** pphead, SLTNode* pos);
//删除pos之后的节点
void SLTEraseAfter(SLTNode* pos);//销毁链表
void SListDesTroy(SLTNode** pphead);

 3. 顺序表和双向链表的优缺点分析

不同点
顺序表
链表(单链表)
存储空间上
物理上⼀定连续
逻辑上连续,但物理上不⼀定连续
随机访问
⽀持O(1)
不⽀持:O(N)
任意位置插⼊或者删除元素
可能需要搬移元素,效率低O(N)
只需修改指针指向
插⼊
动态顺序表,空间不够时需要扩容
没有容量的概念
应⽤场景
元素⾼效存储+频繁访问
任意位置插⼊和删除频繁

在接下来我们将会学习利用实现贪吃蛇小游戏等有意思的东西,如果本篇有不理解的地方,欢迎私信我或在评论区指出,期待与你们共同进步。创作不易,望各位大佬一键三连!

相关文章:

【数据结构】双向链表(C语言)

哈喽铁子们&#xff0c;这里是博主鳄鱼皮坡。这篇文章将分享交流双向链表的相关知识&#xff0c;下面正式开始。 1. 双向链表的结构 注意&#xff1a;这里的“带头”跟前面我们说的“头节点”是两个概念&#xff0c;实际前面的在单链表阶段称呼不严 谨&#xff0c;但是为了老…...

【TensorFlow深度学习】WGAN与DCGAN在图像生成中的应用实例

WGAN与DCGAN在图像生成中的应用实例 WGAN与DCGAN在图像生成中的应用实例&#xff1a;一场深度学习的视觉盛宴DCGAN简介WGAN简介应用实例&#xff1a;基于DCGAN的图像生成应用实例&#xff1a;WGAN的图像生成实践结语 WGAN与DCGAN在图像生成中的应用实例&#xff1a;一场深度学习…...

垫付商贩任务补单平台补单系统网站源码提供

垫付商贩任务补单平台补单系统网站源码提供...

vue富文本wangeditor加@人功能(vue2 vue3都可以)

依赖 "wangeditor/editor": "^5.1.23", "wangeditor/editor-for-vue": "^5.1.12", "wangeditor/plugin-mention": "^1.0.0",RichEditor.vue <template><div style"border: 1px solid #ccc; posit…...

######## redis各章节终篇索引(更新中) ############

其他 父子关系&#xff08;ctx、协程&#xff09;#### golang存在的父子关系 ####_子goroutine panic会导致父goroutine挂掉吗-CSDN博客 参数传递&#xff08;slice、map&#xff09;#### go中参数传递&#xff08;涉及&#xff1a;切片slice、map、channel等&#xff09; ###…...

一个基于MySQL的数据库课程设计的基本框架

数据库课程设计&#xff08;MySQL&#xff09;通常涉及多个步骤&#xff0c;以确保数据库的有效设计、实现和维护。以下是一个基于MySQL的数据库课程设计的基本框架&#xff0c;结合参考文章中的相关信息进行整理&#xff1a; ### 一、引言 * **背景**&#xff1a;简要介绍为…...

架构设计基本原则

开闭原则 开闭原则&#xff08;Open Closed Principle&#xff0c;OCP&#xff09;是面向对象编程&#xff08;OOP&#xff09;中的一个核心原则&#xff0c;主要强调的是软件实体&#xff08;类、模块、函数等&#xff09;应该对扩展开放&#xff0c;对修改封闭。 解释&…...

云原生应用开发培训,开启云计算时代的新征程

在云计算时代&#xff0c;云原生应用开发技术已经成为IT领域的热门话题。如果您想要转型至云原生领域&#xff0c;我们的云原生应用开发培训将帮助您开启新征程。 我们的课程内容涵盖了云原生技术的基础概念、容器技术、微服务架构、持续集成与持续发布&#xff08;CI/CD&#…...

【数据库设计】宠物商店管理系统

目录 &#x1f30a;1 问题的提出 &#x1f30a;2 需求分析 &#x1f30d;2.1 系统目的 &#x1f30d;2.2 用户需求 &#x1f33b;2.2.1 我国宠物行业作为新兴市场&#xff0c;潜力巨大 &#x1f33b;2.2.2 我国宠物产品消费规模逐年增大 &#x1f33b;2.2.3 我国宠物主选…...

前端 JS 经典:node 的模块查找策略

前言&#xff1a;我们引入模块后&#xff0c;node 大概的查找步骤分为 文件查找、文件夹查找、内置模块查找、第三方模块查找&#xff0c;在 node 中使用 ESM 模块语法&#xff0c;需要创建 package.json 文件&#xff0c;并将 type 设置为 module。简单起见&#xff0c;我们用…...

C++中的23种设计模式

目录 摘要 创建型模式 1. 工厂方法模式&#xff08;Factory Method Pattern&#xff09; 2. 抽象工厂模式&#xff08;Abstract Factory Pattern&#xff09; 3. 单例模式&#xff08;Singleton Pattern&#xff09; 4. 生成器模式&#xff08;Builder Pattern&#xff0…...

vue.js+node.js+mysql在线聊天室源码

vue.jsnode.jsmysql在线聊天室源码 技术栈&#xff1a;vue.jsElement UInode.jssocket.iomysql vue.jsnode.jsmysql在线聊天室源码...

浏览器无痕模式和非无痕模式的区别

无痕模式 1. 历史记录&#xff1a;在无痕模式下&#xff0c;浏览器不会保存浏览记录、下载记录、表单数据和Cookies。当你关闭无痕窗口后&#xff0c;这些信息都会被删除。
 2. Cookies&#xff1a;无痕模式会在会话期间临时存储Cookies&#xff0c;但在关闭无痕窗口…...

WPF框架,修改ComboBox控件背景色 ,为何如此困难?

直接修改Background属性不可行 修改控件背景颜色&#xff0c;很多人第一反应便是修改Background属性&#xff0c;但是修改过后便会发现&#xff0c;控件的颜色没有发生任何变化。 于是在网上搜索答案&#xff0c;便会发现一个异常尴尬的情况&#xff0c;要么就行代码简单但是并…...

Diffusers代码学习: 文本引导深度图像生成

StableDiffusionDepth2ImgPipeline允许传递文本提示和初始图像&#xff0c;以调节新图像的生成。此外&#xff0c;还可以传递depth_map以保留图像结构。如果没有提供depth_map&#xff0c;则管道通过集成的深度估计模型自动预测深度。 # 以下代码为程序运行进行设置 import o…...

网络的下一次迭代:AVS 将为 Web2 带去 Web3 的信任机制

撰文&#xff1a;Sumanth Neppalli&#xff0c;Polygon Ventures 编译&#xff1a;Yangz&#xff0c;Techub News 本文来源香港Web3媒体&#xff1a;Techub News AVS &#xff08;主动验证服务&#xff09;将 Web2 的规模与 Web3 的信任机制相融合&#xff0c;开启了网络的下…...

OpenCV 的模板匹配

OpenCV中的模板匹配 模板匹配&#xff08;Template Matching&#xff09;是计算机视觉中的一种技术&#xff0c;用于在大图像中找到与小图像&#xff08;模板&#xff09;相匹配的部分。OpenCV提供了多种模板匹配的方法&#xff0c;主要包括基于相关性和基于平方差的匹配方法。…...

26.0 Http协议

1. http协议简介 HTTP(Hypertext Transfer Protocol, 超文本传输协议): 是万维网(WWW: World Wide Web)中用于在服务器与客户端(通常是本地浏览器)之间传输超文本的协议.作为一个应用层的协议, HTTP以其简洁, 高效的特点, 在分布式超媒体信息系统中扮演着核心角色. 自1990年提…...

IO流打印流

打印流 IO流打印流是Java中用来将数据打印到输出流的工具。打印流提供了方便的方法来格式化和输出数据&#xff0c;可以用于将数据输出到控制台、文件或网络连接。 分类:打印流一般是指:PrintStream&#xff0c;PrintWriter两个类 特点1:打印流只操作文件目的地&#xff0c;…...

Cohere reranker 一致的排序器

这本notebook展示了如何在检索器中使用 Cohere 的重排端点。这是在 ContextualCompressionRetriever 的想法基础上构建的。 %pip install --upgrade --quiet cohere %pip install --upgrade --quiet faiss# OR (depending on Python version)%pip install --upgrade --quiet…...

MySQL系列-语法说明以及基本操作(二)

1、MySQL数据表的约束 1.1、MySQL主键 “主键&#xff08;PRIMARY KEY&#xff09;”的完整称呼是“主键约束”。 MySQL 主键约束是一个列或者列的组合&#xff0c;其值能唯一地标识表中的每一行。这样的一列或多列称为表的主键&#xff0c;通过它可以强制表的实体完整性。 …...

【STM32】步进电机及其驱动

设计和实现基于STM32微控制器的步进电机驱动系统是一个涉及硬件设计、固件编程和电机控制算法的复杂任务。以下是一个概要设计&#xff0c;包括一些基本的代码示例。 1. 硬件设计 1.1 微控制器选择 选择STM32系列微控制器&#xff0c;因为它提供了丰富的GPIO端口和足够的处理…...

Excel自定义排序和求和

概览 excel作为办公的常备工具&#xff0c;好记性不如烂笔头&#xff0c;在此梳理记录下&#xff0c;此篇文章主要是记录excel的自定义排序和求和 一. 自定义排序 举个例子 1. 填充自定义排序选项 实现步骤&#xff1a; 选定目标排序值&#xff1b;文件->选项->自定…...

若依RuoYi-Vue分离版—免登录直接访问

若依RuoYi-Vue分离版—免登录直接访问 如何不登录直接访问前端&#xff1a;后端:方法1&#xff1a;在SecurityConfig.java中设置httpSecurity配置匿名访问方法2&#xff1a;在对应的方法或类上面使用Anonymous注解。 如何不登录直接访问 官网有说明&#xff1a;如何不登录直接…...

java基础知识漏洞记录一

下面是我在阅读JavaGuide面试资料时遇到的不熟悉的知识点总结 JDK9中JRE与JDK新关系 从 JDK 9 开始&#xff0c;就不需要区分 JDK 和 JRE 的关系了&#xff0c;取而代之的是模块系统&#xff08;JDK 被重新组织成 94 个模块&#xff09; jlink 工具 (随 Java 9 一起发布的新命…...

html的网页制作代码分享

<!-- prj_8_2.html --> <!DOCTYPE html> <html lang "EN"><head><meta charset"utf-8" /><title>页面布局设计</title><style type "text/css">*{padding: 0px;margin:0px;}#header{back…...

【PIXEL】2024年 Pixel 解除 4G限制

首先在谷歌商店下载 Shizuku 和 pixel IMS 两个app 然后打开shizuku &#xff0c;按照它的方法启动 推荐用adb 启动&#xff08; 电脑连手机 &#xff0c;使用Qtscrcpy最简洁&#xff09; 一条指令解决 shell sh /storage/emulated/0/Android/data/moe.shizuku.privileged.ap…...

C#、C++、Java、Python 选择哪个好?

选择哪种编程语言取决于你的需求和偏好&#xff0c;以及你打算做什么类型的项目。我这里有一套编程入门教程&#xff0c;不仅包含了详细的视频 讲解&#xff0c;项目实战。如果你渴望学习编程&#xff0c;不妨点个关注&#xff0c;给个评论222&#xff0c;私信22&#xff0c;我…...

爬虫补环境,ES6 Class在环境模拟中的应用与优势

相比于使用传统的Object实现补环境框架结构&#xff0c;使用 ES6 的 Class 具有以下优势&#xff1a; 代码维护更方便&#xff1a;Class的语法更简洁直观&#xff0c;方便开发者阅读和维护。组织结构更清晰&#xff1a;Class提供了明确的层次结构&#xff0c;有助于代码的模块…...

linuxcentos将本地库JAR/arr批量导入到Nexus3.x

背景 我们现在要搞一个私服maven来管理对应的依赖包&#xff0c;需要上传包。用nexus只能单个文件搞&#xff0c;批量导入不行&#xff0c;而且还要单独配置groupID什么的。不多BB,上教程 建脚本 vi mavenimport.sh内容是这个 #!/bin/bash # copy and run this script to t…...

宜阳建站/百度网站排名规则

IT之家讯 微软在官方网站公布了Win10的开发路线图&#xff0c;其中描述了目前已经实现的功能、正在预览测试以及正在开发中的功能。根据描述&#xff0c;微软正在开发一种全新的Win10电脑解锁方式。首先&#xff0c;你可以使用自己的Windows Phone手机、安卓手机作为远程凭据存…...

怎么做门户网站设计方案/百度快照手机入口

2019独角兽企业重金招聘Python工程师标准>>> 1、背景 Springboot4RabbitMQ为消息的生产者 RabbitProducer为消息的消费者 消息队列为&#xff1a;order-queue 2、问题 生产者生产的消息发送到RabbitMQ后&#xff0c;消费者在读取消息消息时反序列化消息失败 消息类&…...

做网站备案需要哪些材料/百度seo建议

服务器登录密码被人改 内容精选换一换登录Windows操作系统的弹性云服务器时&#xff0c;需使用密码方式登录。因此&#xff0c;用户需先根据创建弹性云服务器时使用的密钥文件&#xff0c;获取该弹性云服务器初始安装时系统生成的管理员密码(Administrator帐户或Cloudbase-init…...

用建站ABC做的网站_怎么营销/百度指数查询官网大数据

大家的车如果在高速公路上坏了&#xff0c;必须把车停靠在应急车道上&#xff0c;车内乘员全部下车并躲到护栏外侧&#xff0c;在车后150米处放置警示牌&#xff0c;然后打122报警&#xff0c;之后高速交警会根据你的车型、故障严重程度等派遣相应的救援车辆去施救的。但是高速…...

二手商品网站的设计与建设论文/服务营销策划方案

查找A文件中&#xff0c;与B文件中内容不重复的内容#!usr/bin/pythonimport sysimport os字符串查找函数&#xff0c;使用二分查找法在列表中进行查询def binarySearch(value, lines):right len(lines) - 1left 0a value.strip()while left < right:middle int((right …...

巩义在线/郑州seo排名公司

之前用的gragle 3.3&#xff0c;插件2.3.0&#xff1b;最近不知道怎么回事&#xff0c;一旦编译过新版本的gradle项目&#xff0c;这个项目必坏&#xff0c;这次在尝试各种办法(自行下载gradle3.3/删除缓存/studio重启、电脑重启、studio卸载重装、换studio版本、换电脑。。。)…...