【数据结构】双向链表(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语言)
哈喽铁子们,这里是博主鳄鱼皮坡。这篇文章将分享交流双向链表的相关知识,下面正式开始。 1. 双向链表的结构 注意:这里的“带头”跟前面我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严 谨,但是为了老…...
【TensorFlow深度学习】WGAN与DCGAN在图像生成中的应用实例
WGAN与DCGAN在图像生成中的应用实例 WGAN与DCGAN在图像生成中的应用实例:一场深度学习的视觉盛宴DCGAN简介WGAN简介应用实例:基于DCGAN的图像生成应用实例:WGAN的图像生成实践结语 WGAN与DCGAN在图像生成中的应用实例:一场深度学习…...
垫付商贩任务补单平台补单系统网站源码提供
垫付商贩任务补单平台补单系统网站源码提供...
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各章节终篇索引(更新中) ############
其他 父子关系(ctx、协程)#### golang存在的父子关系 ####_子goroutine panic会导致父goroutine挂掉吗-CSDN博客 参数传递(slice、map)#### go中参数传递(涉及:切片slice、map、channel等) ###…...
一个基于MySQL的数据库课程设计的基本框架
数据库课程设计(MySQL)通常涉及多个步骤,以确保数据库的有效设计、实现和维护。以下是一个基于MySQL的数据库课程设计的基本框架,结合参考文章中的相关信息进行整理: ### 一、引言 * **背景**:简要介绍为…...
架构设计基本原则
开闭原则 开闭原则(Open Closed Principle,OCP)是面向对象编程(OOP)中的一个核心原则,主要强调的是软件实体(类、模块、函数等)应该对扩展开放,对修改封闭。 解释&…...
云原生应用开发培训,开启云计算时代的新征程
在云计算时代,云原生应用开发技术已经成为IT领域的热门话题。如果您想要转型至云原生领域,我们的云原生应用开发培训将帮助您开启新征程。 我们的课程内容涵盖了云原生技术的基础概念、容器技术、微服务架构、持续集成与持续发布(CI/CD&#…...
【数据库设计】宠物商店管理系统
目录 🌊1 问题的提出 🌊2 需求分析 🌍2.1 系统目的 🌍2.2 用户需求 🌻2.2.1 我国宠物行业作为新兴市场,潜力巨大 🌻2.2.2 我国宠物产品消费规模逐年增大 🌻2.2.3 我国宠物主选…...
前端 JS 经典:node 的模块查找策略
前言:我们引入模块后,node 大概的查找步骤分为 文件查找、文件夹查找、内置模块查找、第三方模块查找,在 node 中使用 ESM 模块语法,需要创建 package.json 文件,并将 type 设置为 module。简单起见,我们用…...
C++中的23种设计模式
目录 摘要 创建型模式 1. 工厂方法模式(Factory Method Pattern) 2. 抽象工厂模式(Abstract Factory Pattern) 3. 单例模式(Singleton Pattern) 4. 生成器模式(Builder Pattern࿰…...
vue.js+node.js+mysql在线聊天室源码
vue.jsnode.jsmysql在线聊天室源码 技术栈:vue.jsElement UInode.jssocket.iomysql vue.jsnode.jsmysql在线聊天室源码...
浏览器无痕模式和非无痕模式的区别
无痕模式 1. 历史记录:在无痕模式下,浏览器不会保存浏览记录、下载记录、表单数据和Cookies。当你关闭无痕窗口后,这些信息都会被删除。 2. Cookies:无痕模式会在会话期间临时存储Cookies,但在关闭无痕窗口…...
WPF框架,修改ComboBox控件背景色 ,为何如此困难?
直接修改Background属性不可行 修改控件背景颜色,很多人第一反应便是修改Background属性,但是修改过后便会发现,控件的颜色没有发生任何变化。 于是在网上搜索答案,便会发现一个异常尴尬的情况,要么就行代码简单但是并…...
Diffusers代码学习: 文本引导深度图像生成
StableDiffusionDepth2ImgPipeline允许传递文本提示和初始图像,以调节新图像的生成。此外,还可以传递depth_map以保留图像结构。如果没有提供depth_map,则管道通过集成的深度估计模型自动预测深度。 # 以下代码为程序运行进行设置 import o…...
网络的下一次迭代:AVS 将为 Web2 带去 Web3 的信任机制
撰文:Sumanth Neppalli,Polygon Ventures 编译:Yangz,Techub News 本文来源香港Web3媒体:Techub News AVS (主动验证服务)将 Web2 的规模与 Web3 的信任机制相融合,开启了网络的下…...
OpenCV 的模板匹配
OpenCV中的模板匹配 模板匹配(Template Matching)是计算机视觉中的一种技术,用于在大图像中找到与小图像(模板)相匹配的部分。OpenCV提供了多种模板匹配的方法,主要包括基于相关性和基于平方差的匹配方法。…...
26.0 Http协议
1. http协议简介 HTTP(Hypertext Transfer Protocol, 超文本传输协议): 是万维网(WWW: World Wide Web)中用于在服务器与客户端(通常是本地浏览器)之间传输超文本的协议.作为一个应用层的协议, HTTP以其简洁, 高效的特点, 在分布式超媒体信息系统中扮演着核心角色. 自1990年提…...
IO流打印流
打印流 IO流打印流是Java中用来将数据打印到输出流的工具。打印流提供了方便的方法来格式化和输出数据,可以用于将数据输出到控制台、文件或网络连接。 分类:打印流一般是指:PrintStream,PrintWriter两个类 特点1:打印流只操作文件目的地,…...
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主键 “主键(PRIMARY KEY)”的完整称呼是“主键约束”。 MySQL 主键约束是一个列或者列的组合,其值能唯一地标识表中的每一行。这样的一列或多列称为表的主键,通过它可以强制表的实体完整性。 …...
【STM32】步进电机及其驱动
设计和实现基于STM32微控制器的步进电机驱动系统是一个涉及硬件设计、固件编程和电机控制算法的复杂任务。以下是一个概要设计,包括一些基本的代码示例。 1. 硬件设计 1.1 微控制器选择 选择STM32系列微控制器,因为它提供了丰富的GPIO端口和足够的处理…...
Excel自定义排序和求和
概览 excel作为办公的常备工具,好记性不如烂笔头,在此梳理记录下,此篇文章主要是记录excel的自定义排序和求和 一. 自定义排序 举个例子 1. 填充自定义排序选项 实现步骤: 选定目标排序值;文件->选项->自定…...
若依RuoYi-Vue分离版—免登录直接访问
若依RuoYi-Vue分离版—免登录直接访问 如何不登录直接访问前端:后端:方法1:在SecurityConfig.java中设置httpSecurity配置匿名访问方法2:在对应的方法或类上面使用Anonymous注解。 如何不登录直接访问 官网有说明:如何不登录直接…...
java基础知识漏洞记录一
下面是我在阅读JavaGuide面试资料时遇到的不熟悉的知识点总结 JDK9中JRE与JDK新关系 从 JDK 9 开始,就不需要区分 JDK 和 JRE 的关系了,取而代之的是模块系统(JDK 被重新组织成 94 个模块) 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 ,按照它的方法启动 推荐用adb 启动( 电脑连手机 ,使用Qtscrcpy最简洁) 一条指令解决 shell sh /storage/emulated/0/Android/data/moe.shizuku.privileged.ap…...
C#、C++、Java、Python 选择哪个好?
选择哪种编程语言取决于你的需求和偏好,以及你打算做什么类型的项目。我这里有一套编程入门教程,不仅包含了详细的视频 讲解,项目实战。如果你渴望学习编程,不妨点个关注,给个评论222,私信22,我…...
爬虫补环境,ES6 Class在环境模拟中的应用与优势
相比于使用传统的Object实现补环境框架结构,使用 ES6 的 Class 具有以下优势: 代码维护更方便:Class的语法更简洁直观,方便开发者阅读和维护。组织结构更清晰:Class提供了明确的层次结构,有助于代码的模块…...
linuxcentos将本地库JAR/arr批量导入到Nexus3.x
背景 我们现在要搞一个私服maven来管理对应的依赖包,需要上传包。用nexus只能单个文件搞,批量导入不行,而且还要单独配置groupID什么的。不多BB,上教程 建脚本 vi mavenimport.sh内容是这个 #!/bin/bash # copy and run this script to t…...
宜阳建站/百度网站排名规则
IT之家讯 微软在官方网站公布了Win10的开发路线图,其中描述了目前已经实现的功能、正在预览测试以及正在开发中的功能。根据描述,微软正在开发一种全新的Win10电脑解锁方式。首先,你可以使用自己的Windows Phone手机、安卓手机作为远程凭据存…...
怎么做门户网站设计方案/百度快照手机入口
2019独角兽企业重金招聘Python工程师标准>>> 1、背景 Springboot4RabbitMQ为消息的生产者 RabbitProducer为消息的消费者 消息队列为:order-queue 2、问题 生产者生产的消息发送到RabbitMQ后,消费者在读取消息消息时反序列化消息失败 消息类&…...
做网站备案需要哪些材料/百度seo建议
服务器登录密码被人改 内容精选换一换登录Windows操作系统的弹性云服务器时,需使用密码方式登录。因此,用户需先根据创建弹性云服务器时使用的密钥文件,获取该弹性云服务器初始安装时系统生成的管理员密码(Administrator帐户或Cloudbase-init…...
用建站ABC做的网站_怎么营销/百度指数查询官网大数据
大家的车如果在高速公路上坏了,必须把车停靠在应急车道上,车内乘员全部下车并躲到护栏外侧,在车后150米处放置警示牌,然后打122报警,之后高速交警会根据你的车型、故障严重程度等派遣相应的救援车辆去施救的。但是高速…...
二手商品网站的设计与建设论文/服务营销策划方案
查找A文件中,与B文件中内容不重复的内容#!usr/bin/pythonimport sysimport os字符串查找函数,使用二分查找法在列表中进行查询def binarySearch(value, lines):right len(lines) - 1left 0a value.strip()while left < right:middle int((right …...
巩义在线/郑州seo排名公司
之前用的gragle 3.3,插件2.3.0;最近不知道怎么回事,一旦编译过新版本的gradle项目,这个项目必坏,这次在尝试各种办法(自行下载gradle3.3/删除缓存/studio重启、电脑重启、studio卸载重装、换studio版本、换电脑。。。)…...