数据结构笔记第3篇:双向链表
1、双向链表的结构
注意:这里的 "带头" 跟前面我们说的 "头结点" 是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头结点。
带头链表里的头结点,实际为 "哨兵位" ,哨兵位节点不存储任何有效元素,只是站在这里 "放哨的"。
"哨兵位" 存在的意义:
遍历循环链表避免死循环。
注意:双向链表中,哨兵位的下一个节点是链表的第一个节点(头结点)。哨兵位的前一个节点是链表的最后一个节点(尾结点)。所以双向链表的头插是在哨兵位的后面插入数据。尾插则是在哨兵位之前插入数据。
哨兵位是作为头结点和尾结点的中点,是头结点的起点也是尾节点的终点。这样解释更容易理解。
2、 双向链表的实现
List.h 链表函数和链表节点类型的声明:
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>typedef int SLDataType;
typedef struct ListNode
{SLDataType data;//存储数据struct ListNode* prve;//存储前一个节点的地址struct ListNode* next;//存储下一个节点的地址
}SList;
SList* SLInit();void SLPushBack(SList* phead, SLDataType x);//尾插
void SLPrint(SList* phead);//显示链表数据
void SLPustFront(SList* phead, SLDataType x);//头插
void SLPopBack(SList* phead);//尾删
void SLPopFront(SList* phead);//头删
void SLInsert(SList* pos, SLDataType x);//指定位置插入
SList* SLfind(SList* phead, SLDataType x);//查找节点
void SLEarse(SList* pos);//指定位置删除
void SLDestory(SList** pphead);//链表销毁
List.c 链表函数的实现:
#include "List.h"
//链表初始化
SList* SLInit()
{SList* phead = (SList*)malloc(sizeof(SList));if (phead == NULL){perror("malloc error");return NULL;}phead->data = -1;//因为是循环链表,所以初始化要遵循循环格式phead->next = phead;phead->prve = phead;return phead;
}
//创建链表节点
SList* ListBuyNode(SLDataType x)
{SList* retNode = (SList*)malloc(sizeof(SList));if (retNode == NULL){perror("malloc error");return NULL;}retNode->data = x;retNode->prve = retNode;retNode->next = retNode;return retNode;
}
//链表尾插
void SLPushBack(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->prve = phead->prve;Node->next = phead;phead->prve->next = Node;phead->prve = Node;
}
//链表数据显示
void SLPrint(SList* phead)
{assert(phead);SList* pcur = phead->next;while (pcur != phead)//哨兵位作为结束标识{printf("%d", pcur->data);if (pcur->next != phead)printf("->");pcur = pcur->next;}printf("\n");
}
//链表头插
void SLPustFront(SList* phead, SLDataType x)
{assert(phead);SList* Node = ListBuyNode(x);Node->next = phead->next;Node->prve = phead;phead->next->prve = Node;phead->next = Node;
}
//链表尾删
void SLPopBack(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->prve;del->prve->next = phead;phead->prve = del->prve;free(del);del = NULL;
}
//链表头删
void SLPopFront(SList* phead)
{assert(phead);assert(phead->next != phead);SList* del = phead->next;del->next->prve = phead;phead->next = del->next;free(del);del = NULL;
}
//指定位置插入
void SLInsert(SList* pos, SLDataType x)
{assert(pos);SList* Node = ListBuyNode(x);Node->next = pos->next;Node->prve = pos;pos->next = Node;Node->next->prve = Node;
}
//查找节点
SList* SLfind(SList* phead, SLDataType x)
{assert(phead);SList* pcur = phead->next;while (pcur != phead){if (pcur->data == x){return pcur;}pcur = pcur->next;}return NULL;
}
//指定位置删除
void SLEarse(SList* pos)
{assert(pos);pos->prve->next = pos->next;pos->next->prve = pos->prve;free(pos);pos = NULL;
}
//链表销毁
void SLDestory(SList** pphead)
{assert(pphead && *pphead);SList* pcur = (*pphead)->next;while (pcur != *pphead){SList* next = pcur->next;free(pcur);pcur = next;}free(*pphead);*pphead = NULL;
}
test.c 函数的调用:
#include "List.h"void SLtest()
{SList* plist = NULL;plist = SLInit();//尾插SLPushBack(plist, 1);SLPushBack(plist, 2);SLPushBack(plist, 3);SLPushBack(plist, 4);SLPrint(plist);//打印:1->2->3->4//头插SLPustFront(plist, 5);SLPustFront(plist, 6);SLPustFront(plist, 7);SLPrint(plist);//打印:7->6->5->1->2->3->4//尾删SLPopBack(plist);SLPrint(plist);//打印:7->6->5->1->2->3//头删SLPopFront(plist);SLPrint(plist);//打印:6->5->1->2->3//指定位置插入SList* find = SLfind(plist, 5);SLInsert(find, 11);SLPrint(plist);//打印:6->5->11->1->2->3//指定位置删除find = SLfind(plist, 1);SLEarse(find);SLPrint(plist);//打印:6->5->11->2->3//链表销毁SLDestory(&plist);
}
int main()
{SLtest();return 0;
}
3、顺序表和双向链表的优缺点分析
不同点 | 顺序表 | 链表 |
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持O(N) |
任意位置插入或者删除元素 | 可能需要搬移元素,效率低O(N) | 只需要修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
数据结构第3篇笔记到这里也就结束了,我们下一篇笔记再见-
相关文章:
数据结构笔记第3篇:双向链表
1、双向链表的结构 注意:这里的 "带头" 跟前面我们说的 "头结点" 是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了同学们更好的理解就直接称为单链表的头结点。 带头链表里的头结点,实际为 "哨兵…...
详细对比Java SPI、Spring SPI 和 Dubbo SPI
SPI(Service Provider Interface)概述 定义:SPI是一种动态替换发现机制,用于实现接口与实现的解耦,提高框架的可扩展性。核心思想:解耦和方便扩展。 Java SPI 约定规范: 扩展类文件放在META-…...
CPU的核心数和线程数
CPU的核心数和线程数 一、关系: 1、线程数可以模拟出不同的CPU核心数。 CPU的核心数指的是硬件上存在着几个核心,而线程数可以模拟出多个核心数的功能。线程数越多,越有利于同时运行多个程序,因为线程数等同于在某个瞬间CPU能同…...
电脑游戏录屏,3款实用软件推荐给你
在电竞游戏热潮席卷全球的今天,电脑游戏录屏早已不再是简单的画面捕捉,它成为了记录电竞风采、打造专属游戏记忆的重要手段。通过游戏录屏,我们可以定格游戏中的精彩瞬间,重温那些令人热血沸腾的电竞时刻。那么,在进行…...
C#桌面应用开发:番茄定时器
C#桌面应用开发:番茄定时器 1、环境搭建和工程创建: 步骤一:安装visual studio2022 步骤二:新建工程 2、制作窗体部件 *踩过的坑: (1)找不到工具箱控件,现象如下:…...
PHP智慧门店微信小程序系统源码
🔍【引领未来零售新风尚】🔍 🚀升级启航,智慧零售新篇章🚀 告别传统门店的束缚,智慧门店v3微信小程序携带着前沿科技与人性化设计,正式启航!这个版本不仅是对过往功能的全面优化&a…...
SerDes介绍以及原语使用介绍(2)OSERDESE2原语仿真
文章目录 前言一、SDR模式1.1、设计代码1.2、testbench代码1.3、仿真分析 二、DDR模式下2.1、设计代码2.2、testbench代码2.3、仿真分析 三、OSERDES2级联3.1、设计代码3.2、testbench代码3.3、代码分析 前言 上文通过xilinx ug471手册对OSERDESE有了简单的了解,接…...
【稳定检索/投稿优惠】2024年教育、人文发展与艺术国际会议(EHDA 2024)
2024 International Conference on Education, Humanities Development and Arts 2024年教育、人文发展与艺术国际会议 【会议信息】 会议简称:EHDA 2024 大会时间:点击查看 截稿时间:点击查看 大会地点:中国北京 会议官网&#…...
Docker拉取失败,利用 Git将 Docker镜像重新打 Tag 推送到阿里云等其他公有云镜像仓库里
目录 一、开通阿里云容器镜像服务 二、Git配置 三、去DockerHub找镜像 四、编写images.txt文件 五、演示 六、其他注意事项 最近一段时间 Docker 镜像一直是 Pull 不下来的状态,想直连 DockerHub 是几乎不可能的。更糟糕的是,很多原本可靠的国内…...
【区分vue2和vue3下的element UI Breadcrumb 面包屑组件,分别详细介绍属性,事件,方法如何使用,并举例】
在 Vue 2 中,Element UI 提供了 el-breadcrumb 面包屑组件,而在 Vue 3 中,Element UI 的官方版本并没有直接更新以支持 Vue 3,但有一个类似的库叫做 Element Plus,它是为 Vue 3 设计的。 Vue 2 Element UI 在 Vue 2…...
gdb调试命令大全
基本命令 #gdb test test是要调试的程序,由gcc test.c -g -o test生成。进入后提示符变为(gdb) 。 start : 指令会执行程序至main() 主函数的起始位置,即在main() 函数的第一行语句处停止执行(该行代码尚未执行) cont…...
ESP32之arduino环境安装及点灯
目录 前言 前两天安装了VScode,奈何资源找的困难,于是咨询淘宝客服,他说arduino用的多,资源多.然后就安装了a…...
查看VUE中安装包依赖的版本号
查看VUE中安装包依赖的版本号 全部依赖包版本查看某个依赖的例:查看stompjs 应用命令npm ls stompjs 全部依赖包版本 使用npm命令 使用 npm ls 命令可以列出项目中所有已安装的依赖包及其版本。 使用 npm list --depth1 命令可以列出项目中直接依赖的包及其版本&a…...
博途通讯笔记1:1200与1200之间S7通讯
目录 一、添加子网连接二、创建PUT GET三、各个参数的意义 一、添加子网连接 二、创建PUT GET 三、各个参数的意义...
Kafka搭建(集群版)
Kafka单机版 部署前提 VMware环境 : 两台centos系统 Jdk包:jdk-8u202-linux-x64.tar.gz Kafka包:kafka_2.12-3.5.0.tgz Zookeeper包:apache-zookeeper-3.7.2-bin.tar.gz 百度网盘自取: 链接: https://pan.baidu.com/s/11EWuhBoSmH3musd_3Rgodw?pwde32t 提取码: e32t Kafka搭建…...
【康复学习--LeetCode每日一题】3115. 质数的最大距离
题目: 给你一个整数数组 nums。 返回两个(不一定不同的)质数在 nums 中 下标 的 最大距离。 示例 1: 输入: nums [4,2,9,5,3] 输出: 3 解释: nums[1]、nums[3] 和 nums[4] 是质数。因此答案是…...
【yolov8系列】ubuntu上yolov8的开启训练的简单记录
前言 yolov8的广泛使用,拉取yolov8源码工程,然后配置环境后直接运行,初步验证自己数据的检测效果,在数据集准备OK的情况下 需要信手拈来,以保证开发过程的高效进行。 本篇博客更注意为了方便自己使用时参考。顺便也记录…...
Scala学习笔记15: 文件和正则表达式
目录 第十五章 文件和正则表达式1- 读取行2- 从URL或者其它源读取3- 写入文本文件4- 序列化5- 正则表达式6- 正则表达式验证输入数据格式end 第十五章 文件和正则表达式 1- 读取行 在Scala中读取文件中的行可以通过不同的方法实现 ; 一种常见的方法是使用 scala.io.Source 对…...
外卖员面试现状
说明: 以下身份角色用符号代替 # 面试官 $ 求职者 # 看了您的简历你有两年半的送外卖经验,可以简单说一下您平时是怎么送外卖的吗? $ 我首先在平台接单然后到店里取餐,取到餐后到顾客留下的地址,再通知顾客取餐 # 你们也用电动…...
异步加载与动态加载
异步加载和动态加载在概念上有相似之处,但并不完全等同。 异步加载(Asynchronous Loading)通常指的是不阻塞后续代码执行或页面渲染的数据或资源加载方式。在Web开发中,异步加载常用于从服务器获取数据,而不需要用户等…...
MUNIK解读ISO26262--什么是DFA
我们在学习功能安全过程中,经常会听到很多安全分析方法,有我们熟知的FMEA(Failure Modes Effects Analysis)和FTA(Fault Tree Analysis)还有功能安全产品设计中几乎绕不开的FMEDA(Failure Modes Effects and Diagnostic Analysis),相比于它们…...
启动spring boot项目停止 提示80端口已经被占用
可能的情况: 检查并结束占用进程: 首先,你需要确定哪个进程正在使用80端口。在Windows上,可以通过命令行输入netstat -ano | findstr LISTENING | findstr :80来查看80端口的PID,然后在任务管理器中结束该进程。在...
SOLIDWORKS分期许可(订阅形式),降低前期的投入成本!
SOLIDWORKS 分期许可使您能够降低前期软件成本,同时提供对 SOLIDWORKS 新版本和升级程序的即时访问,以及在每个期限结束时调整产品的灵活性,帮助您跟上市场需求和竞争压力的步伐。 目 录: ★ 1 什么是SOLIDWORKS分期许可 ★ 2 …...
详细分析Spring Boot 数据源配置的基本知识(附配置)
目录 前言1. 基本知识2. 模版3. 实战经验前言 对于Java的基本知识推荐阅读: java框架 零基础从入门到精通的学习路线 附开源项目面经等(超全)【Java项目】实战CRUD的功能整理(持续更新)1. 基本知识 包括数据源的概念、连接池的作用、多数据源的实现与管理、Druid 连接池…...
海思SD3403/SS928V100开发(15)9轴IMU ICM-20948模块SPI接口调试
1.前言 芯片平台: 海思SD3403/SS928V100 操作系统平台: Ubuntu20.04.05【自己移植】 9轴IMU模块:ICM-20948 通讯接口: SPI 模块datasheet手册: https://download.csdn.net/download/jzwjzw19900922/89517096 2. 调试记录 2.1 pinmux配置 #spi0 bspmm 0x0102F01D8 …...
大力出奇迹:大语言模型的崛起与挑战
随着人工智能(AI)技术的迅猛发展,特别是在自然语言处理(NLP)领域,大语言模型(LLM)的出现与应用,彻底改变了我们与机器互动的方式。本文将探讨ChatGPT等大语言模型的定义、…...
【算法 - 哈希表】两数之和
这里写自定义目录标题 两数之和题目解析思路解法一 :暴力枚举 依次遍历解法二 :使用哈希表来做优化 核心逻辑为什么之前的暴力枚举策略不太好用了?所以,这就是 这道题选择 固定一个数,再与其前面的数逐一对比完后&…...
【深度学习】图形模型基础(5):线性回归模型第一部分:认识线性回归模型
1. 回归模型定义 最简单的回归模型是具有单一预测变量的线性模型,其基本形式如下: y a b x ϵ y a bx \epsilon yabxϵ 其中, a a a 和 b b b 被称为模型的系数或更一般地,模型的参数。 ϵ \epsilon ϵ 代表误差项&#…...
2024 年第十四届 APMCM 亚太地区大学生数学建模竞赛B题超详细解题思路+数据预处理问题一代码分享
B题 洪水灾害的数据分析与预测 亚太中文赛事本次报名队伍约3000队,竞赛规模体量大致相当于2024年认证杯,1/3个妈杯,1/10个国赛。赛题难度大致相当于0.6个国赛,0.8个妈杯。该比例仅供大家参考。 本次竞赛赛题难度A:B:C3:1:4&…...
Yarn有哪些功能特点
Yarn是一个由Facebook团队开发,并联合Google、Exponent和Tilde等公司推出的JavaScript包管理工具,旨在提供更优的包管理体验,解决npm(Node Package Manager)的一些痛点。Yarn的功能特点主要包括以下几个方面࿱…...
深度学习算法bert
bert 属于自监督学习的一种(输入x的部分作为label) 1. bert是 transformer 中的 encoder ,不同的bert在encoder层数、注意力头数、隐藏单元数不同 2. 假设我们有一个模型 m ,首先我们为某种任务使用大规模的语料库预训练模型 m …...
PyTorch - 神经网络基础
神经网络的主要原理包括一组基本元素,即人工神经元或感知器。它包括几个基本输入,例如 x1、x2… xn ,如果总和大于激活电位,则会产生二进制输出。 样本神经元的示意图如下所述。 产生的输出可以被认为是具有激活电位或偏差的加权…...
docker-compose搭建minio对象存储服务器
docker-compose搭建minio对象存储服务器 最近想使用oss对象存储进行用户图片上传的管理,了解了一下例如aliyun或者腾讯云的oss对象存储服务,但是呢涉及到对象存储以及经费有限的缘故,决定自己手动搭建一个oss对象存储服务器; 首先…...
vue3使用pinia中的actions,需要调用接口的话
actions,需要调用接口的话,假如页面想要调用actions中的方法获取数据, 必须使用try catch async await 进行包裹,详情看下面代码 import {defineStore} from pinia import {reqCode,reqUserLogin} from ../../api/hospital/i…...
Python酷库之旅-第三方库Pandas(003)
目录 一、用法精讲 4、pandas.read_csv函数 4-1、语法 4-2、参数 4-3、功能 4-4、返回值 4-5、说明 4-6、用法 4-6-1、创建csv文件 4-6-2、代码示例 4-6-3、结果输出 二、推荐阅读 1、Python筑基之旅 2、Python函数之旅 3、Python算法之旅 4、Python魔法之旅 …...
社交电商中的裂变营销利器,二级分销模式,美妆家具成功案例分享
二级分销返佣模式是一种帮助商家迅速扩大市场覆盖的有效营销策略,不仅能降低营销成本,还能提升品牌知名度。下面通过两个具体的案例来说明这种模式的好处和优势。 某知名美妆品牌在市场竞争日益激烈的情况下,决定采用二级分销返佣模式进行市场…...
【国产开源可视化引擎Meta2d.js】图层
独立图层 每个图元都有先后绘画顺序,即每个图元拥有一个独立图层,即meta2d.data().pens的数组索引。 可以通过meta2d.top/bottom/up/down等函数改变独立图层顺序。 分组图层 通过标签可以标识一个分组图层,通过meta2d.find(图层标签)获取…...
基于Redisson实现分布式锁
基于redisson实现分布式锁 之前背过分布式锁几种实现方案的八股文,但是并没有真正自己实操过。现在对AOP有了更深一点的理解,就自己来实现一遍。 1、分布式锁的基础知识 分布式锁是相对于普通的锁的。普通的锁在具体的方法层面去锁,单体应…...
Android Studio下载Gradle特别慢,甚至超时,失败。。。解决方法
使用Android studio下载或更新gradle时超级慢怎么办? 切换服务器,立马解决。打开gradle配置文件 修改服务器路径 distributionUrlhttps\://mirrors.cloud.tencent.com/gradle/gradle-7.3.3-bin.zip 最后,同步,下载,速…...
leetcode--二叉树中的最长交错路径
leetcode地址:二叉树中的最长交错路径 给你一棵以 root 为根的二叉树,二叉树中的交错路径定义如下: 选择二叉树中 任意 节点和一个方向(左或者右)。 如果前进方向为右,那么移动到当前节点的的右子节点&…...
c++ primer plus 第15章友,异常和其他:15.1.3 其他友元关系
c primer plus 第15章友,异常和其他:15.1.3 其他友元关系 提示:这里可以添加系列文章的所有文章的目录,目录需要自己手动添加 15.1.3 其他友元关系 提示:写完文章后,目录可以自动生成,如何生成可…...
uniapp+vue3页面跳转和传参
页面跳转: uni.navigateTo({url: /pages/index}) 返回上一层: uni.navigateBack ({delta: 1 }) 页面跳转时传参: 跳转前的页面: uni.navigateTo({url: "/pages/index?id123"}) 跳转后的页面: onLoa…...
硬链接和软链接
在Linux系统中,链接(Link)是一种特殊的文件,它指向另一个文件或目录。链接分为两种类型:硬链接(Hard Link)和软链接(也称为符号链接,Symbolic Link)。 1. 硬…...
属性描述符初探——Vue实现数据劫持的基础
目录 属性描述符——Vue实现数据劫持的基础 一、属性描述符是什么? 编辑 1.1、属性描述符示例 1.2、用属性描述符定义属性及获取对象的属性描述符 1.3、带有读取器和设置器的属性描述符 二、使用属性描述符的情景 2.1、封装和数据隐藏 使用getter和setter…...
字节也没余粮了?天底下没有永远免费的GPT-4;AI产品用订阅制就不合理!让用户掏钱的N种定价技巧嘿嘿 | ShowMeAI日报
👀日报&周刊合集 | 🎡ShowMeAI官网 | 🧡 点赞关注评论拜托啦! 1. 当 Coze 也开始收费:天底下没有「永远」免费的 GPT-4 注:这里 Coze 指海外版。国内版 扣子 还是免费。 Coze (海外版) 官网链接 → htt…...
【Matlab 路径优化】基于蚁群算法的XX市旅游景点线路优化系统
基于蚁群算法的XX市旅游景点线路优化系统 (一)客户需求: ①考虑旅游景点的空间分布、游客偏好等因素,实现了旅游线路的智能规划 ②游客选择一景点出发经过所要游览的所有景点只一次,最后回到出发点的前提下…...
我关于Excel使用点滴的笔记
本篇笔记是我关于Excel使用点滴的学习笔记,摘要和地址链接列表。临时暂挂,后面可能在不需要时删除。 (笔记模板由python脚本于2024年06月28日 12:23:32创建,本篇笔记适合初通Python,熟悉六大基本数据(str字符串、int整型、float浮…...
【Java安装】windows10+JDK21+IDEA
文章目录 一、JDK安装1. 下载完成后按照自己需要的位置安装2. 配置环境变量2.1 JAVA_HOME变量2.2 PATH配置 3. 验证4. helloworld 二、IDEA安装三、IDEA-HelloWorld 一、JDK安装 JDK安装链接 1. 下载完成后按照自己需要的位置安装 2. 配置环境变量 2.1 JAVA_HOME变量 安装…...
《简历宝典》01 - 一文带你学会如何写一份糟糕透顶的简历
我们每个人几乎都会面对找工作这件事,而找工作或者说求职首先就是要写一份简历。今天狗哥将以一个不同的视角带你写一份无与伦比,糟糕透顶的求职简历,说实话,其实几年前,我就是这么写的。 目录 1. 文件名 2. 基本信…...
多链路聚合通信路由在应急救援活动中的重要性及解决方案
在应急救援指挥活动中,多链路聚合通信设备如同一座坚固的桥梁,将信息快速、准确地传递至每一个角落。面对复杂多变的救援现场,这类设备展现了其卓越的适应性和稳定性。 想象一下,当灾害突然降临,信息的传递变得至关重…...