算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)
算法竞赛基础:双向链表
本文将会介绍在算法竞赛中双向链表的几种使用方式,适合有一定基础的人阅读。
双向链表的结构
一般来说,普通的链表结构是这样的:
struct node {int num;node *next;
}
next指针指向下一个链表,这样的结构只能够支持单向查询。
双向链表,顾名思义,就是可以支持双向的访问和查询。
也就是这样的:
struct node {int num;node *l, *r;
}
这种链表为访问前后的元素提供的很大的便利性。
C++的STL模板中也有类似的结构:
List
list<int> lis;
List是连续的容器,而vector是非连续的容器,即list将元素存储在连续的存储器中,而vector存储在不连续的存储器中。
向量(vector)中间的插入和删除是非常昂贵的,因为它需要大量的时间来移动所有的元素。链表克服了这个问题,它是使用list容器实现的。
List支持双向,并为插入和删除操作提供了一种有效的方法。
在列表中遍历速度很慢,因为列表元素是按顺序访问的,而vector支持随机访问。
列表模板
示例
#include<iostream>
#include<list>
using namespace std;
int main()
{list<int> l;
}
它创建一个空的整数类型值列表。
列表也可以使用参数初始化。
示例
#include<iostream>
#include<list>
using namespace std;
int main()
{list<int> l{1,2,3,4};
}
列表可以通过两种方式初始化。
示例
list<int> new_list{1,2,3,4};
or
list<int> new_list = {1,2,3,4};
list支持的操作有以下这些:
| 方法 | 描述 |
|---|---|
| insert() | 它将新元素插入到迭代器指向的位置之前。 |
| push_back() | 它在容器的末尾添加了一个新元素。 |
| push_front() | 它在前面增加了一个新元素。 |
| pop_back() | 删除最后一个元素。 |
| pop_front() | 删除第一个元素。 |
| empty() | 它检查列表是否为空。 |
| size() | 它查找列表中存在的元素数。 |
| max_size() | 它找到列表的最大大小。 |
| front() | 它返回列表的第一个元素。 |
| back() | 它返回列表的最后一个元素。 |
| swap() | 当两个列表的类型相同时,它将交换两个列表。 |
| reverse() | 它反转了列表的元素。 |
| sort() | 它以递增的顺序对列表中的元素进行排序。 |
| merge() | 它合并两个排序的列表。 |
| splice() | 它将新列表插入到调用列表中。 |
| unique() | 它从列表中删除所有重复的元素。 |
| resize() | 它更改列表容器的大小。 |
| assign() | 它将一个新元素分配给列表容器。 |
| emplace() | 它将在指定位置插入一个新元素。 |
| emplace_back() | 它将在容器的末尾插入一个新元素。 |
| emplace_front() | 它将在列表的开头插入一个新元素。 |
| erase() | 删除这个元素 |
但是这种结构往往在大量数据的情况下会超时。我们需要一种更加有效的方式,通常,我们选择空间换时间,因此静态链表通常是更好的选择,接下来介绍一种静态双向循环链表在竞赛中实现的方式。
竞赛方式实现
思路是这样的:
要实现一个静态双向循环链表,需要模拟一个左右指针,在这里,我们选择花费大量空间去用数组的下标代替指针和对应的值:
#include <bits/stdc++.h>
using namespace std;const int MAX_N 1e5 + 10;struct node {int l, r;int key;
} arr[MAX_N] = {0};
其中,l和r分别表示上一个和下一个元素的数组下标。
插入操作
插入操作的思路很简单:
先将新元素的l和r指向左右两个元素。
再分别让左右两个元素的r和l分别指向新元素本身;
//ll:左元素,rr:右元素, new:新元素
void add(int ll, int rr, int new) {arr[new].l = ll;arr[new].r == rr;arr[ll].r == new;arr[rr].l == new;
}
这不是一种唯一的实现方式,其中的参数和需求都可以根据具体情况改变。
删除操作
删除操作提供两种思路:
- 第一种与插入操作类似,实现元素的删除
- 第二种更加快速,通过在节点种的key值,去判断是否输出(如果要求输出链表的话)
第一种方式:
void del(int target) {int l, r;l = arr[target].l;r = arr[target].r;arr[l].r = r;arr[r].l = l;
第二种方式:
void del(int target) {arr[target].key = 0; //在对链表元素进行操作时,检测其key值的真值,如果为0,直接不对其进行操作
}
第二种方式虽然没有改变l和r的值,但是也能够实现链表访问机制的修改而且还支持数据恢复,相当好用。
查找操作
这种方式是基于上面删除操作时的第二种方式实现的:
bool find(int target) {return arr[target].key == 1;
}
因为这种特殊的链表结构支持随机访问(正常的链表结构是不支持的),所以查找操作变成检测对应元素的键值是否有效,如果有效,返回一个真值。
遍历操作
以输出全部数值为例:
这里值得一提的是,如果按照这种上文所述的方式去建立双向链表的话,你会发现没有头结点。
具体原因是由于开辟第一个结点时,也就是数组下标为1的时候,结构体中的
l和r指向的是1本身,那这个时候如果再多插入几个结点,最后一个结点的r会指向1,1的l会指向最后一个结点,这样一来,当你在1之前插入结点时,按理来说头节点会变成新插入的结点,但由于缺少一个指向头节点的指针而丢失链表的头,这显然是我们不想看到的。
解决方法也很简单,我们在数组下标为0的位置创建一个结点作为虚拟头结点,当在真正的头结点之前插入新的结点时,这时候新结点会在0和头节点之间,当我们需要访问头节点的时候,通过0去访问就可以了。
下面是建立的虚拟头节点0之后的遍历输出操作:
void bs() {// from left to rightfor (int i = arr[0].r; i; i = arr[i].r) {cout << arr[i] << " ";}
相关文章:
算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)
算法竞赛基础:双向链表 本文将会介绍在算法竞赛中双向链表的几种使用方式,适合有一定基础的人阅读。 双向链表的结构 一般来说,普通的链表结构是这样的: struct node {int num;node *next; }next指针指向下一个链表ÿ…...
openssl3.2/test/certs - 019 - ca-nonca trust variants: +serverAuth, +anyEKU
文章目录 openssl3.2/test/certs - 019 - ca-nonca trust variants: serverAuth, anyEKU概述笔记 ca-nonca.pem from exp 016openssl3.2/test/certs - 019 - ca-nonca trust variants: serverAuth, anyEKUEND openssl3.2/test/certs - 019 - ca-nonca trust variants: serverAu…...
Unity SRP 管线【第五讲:URP烘培光照】
本节,我们将跟随数据流向讲解UEP管线中的烘培光照。 文章目录 一、URP烘培光照1. 搭建场景2. 烘培光照参数设置MixedLight光照设置:直观感受 Lightmapping Settings参数设置: 3. 我们如何记录次表面光源颜色首先我们提取出相关URP代码&#…...
Mysql运维篇(一) 日志类型
一路走来,所有遇到的人,帮助过我的、伤害过我的都是朋友,没有一个是敌人,如有侵权请留言,我及时删除。 一、mysql相关日志 首先,我们能接触到的,一般我们排查慢查询时,会去看慢查询日志。如果做过数据备份会恢复的,可能接触或用过BinLog。那还有其他的吗?对MySQL原理…...
【C语言】结构体与内存操作函数 总结
结构体 一、结构体简介 C 语言内置的数据类型,除了最基本的几种原始类型,只有数组属于复合类型,可以同时包含多个值,但是只能包含相同类型的数据,实际使用中并不够用。 实际使用中,主要有下面两种情况&a…...
第12章_集合框架(Collection接口,Iterator接口,List,Set,Map,Collections工具类)
文章目录 第12章_集合框架本章专题与脉络1. 集合框架概述1.1 生活中的容器1.2 数组的特点与弊端1.3 Java集合框架体系1.4 集合的使用场景 2. Collection接口及方法2.1 添加2.2 判断2.3 删除2.4 其它 3. Iterator(迭代器)接口3.1 Iterator接口3.2 迭代器的执行原理3.3 foreach循…...
C语言进阶——数据结构之链表(续)
前言 hello,大家好呀,我是Humble,本篇博客承接之前的C语言进阶——数据结构之链表 的内容(没看过的小伙伴可以从我创建的专栏C语言进阶之数据结构 找到那篇文章并阅读后在回来哦~),上次我们重点说了链表中…...
数据库课程设计-图书管理系统数据库设计
目录 一、实验目的 二、实验内容 三、实验要求 四、实验设计 4.1需求分析 4.1.1系统目标 4.1.2功能需求 4.1.3性能需求 4.14界面需求 4.2概念模型设计 4.2.1 实体及联系 4.2.2 E-R图 4.3 逻辑设计 4.3.1 E-R模型向关系模型的转换 4.3.2 数据库逻辑结构 4.3.3数据库模型函数依赖…...
【超简版,代码可用!】【0基础Python爬虫入门——下载歌曲/视频】
安装第三方模块— requests 完成图片操作后输入:pip install requests 科普: get:公开数据 post:加密 ,个人信息 进入某音乐网页,打开开发者工具F12 选择网络,再选择—>媒体——>获取URL【先完成刷新页面】 科…...
CommunityToolkit.Mvvm支持环境
引言 CommunityToolkit.Mvvm 包(又名 MVVM 工具包,以前称为 Microsoft.Toolkit.Mvvm)是一个现代、快速和模块化的 MVVM 库。 它是 .NET 社区工具包的一部分,其中一条原则是: 独立于平台和运行时 - .NET Standard 2.0…...
探讨品牌设计的本质,为企业形象注入活力!
品牌设计作为一个行业,首先需要明确行业的本质和意义。由于越来越多的咨询公司和营销公司对品牌有不同的理解和解释,因为他们服务的内容和专业水平不同,什么是品牌的定义越来越复杂,逐渐成为一种神秘的知识。例如,特劳…...
【Maven】-- 打包添加时间戳的两种方法
一、需求 在执行 mvn clean package -Dmaven.test.skiptrue 后,生成的 jar 包带有自定义系统时间。 二、实现 方法一:使用自带属性(不推荐) 使用系统时间戳,但有一个问题,就是默认使用 UTC0 的时区。举例…...
图片分类: 多类别
最近需要训练一个有200多类的图片分类网络,搜了一遍,发现居然没有很合适用的开源项目,于是自己简单撸了一个轮子,项目地址: https://github.com/xuduo35/imgcls_pytorch。支持如下backbone: alexnetresnet18,resnet34,resnet50,r…...
python 抓包tcp数据拷贝转发
在Python中,你可以使用scapy库进行抓包,使用shutil或io库进行数据的拷贝,以及使用socket库进行数据转发。下面是一个简单的示例,展示了如何进行这些操作: 首先,你需要安装必要的库。你可以使用pip来安装它…...
ubuntu 各版本图形界面和命令行切换快捷键介绍
文章目录 前言一、ubuntu 图形界面和命令行模式切换的快捷键1. ubuntu 16.042. ubuntu 18.043. ubuntu 20.044. ubuntu 22.04 总结 前言 本文主要介绍如何使用快捷键进行ubuntu 的图形界面和命令行模式切换,涉及如下 几个ubuntu 版本 ubuntu16.04 ubuntu18.04 ubun…...
基于SpringBoot Vue博物馆管理系统
大家好✌!我是Dwzun。很高兴你能来阅读我,我会陆续更新Java后端、前端、数据库、项目案例等相关知识点总结,还为大家分享优质的实战项目,本人在Java项目开发领域有多年的经验,陆续会更新更多优质的Java实战项目&#x…...
关于预检请求
基本概述 预检请求(Preflight Request)是一种由浏览器自动发起的请求,用于检查实际请求是否安全可行。这种请求通常在跨域请求(CORS)中出现,并且只在某些特定条件下触发。以下是触发预检请求的具体条件&am…...
cookie in selenium 定时更新token
1.selenium添加cookie访问 需要登录才能访问的链接 selenium 访问 “https://developer.org.com”,如果没登陆,则跳转到"https://console.org.com/login",此时selenium取到的cookie的domain是:.console.org.com。 而domain 是 .c…...
【MIdjourney】一些材质相关的关键词
1.多维剪纸(Multidimensional papercut) "Multidimensional papercut"(多维剪纸)是一种剪纸艺术形式,通过多层次的剪纸技巧和设计来创造出立体感和深度感。这种艺术形式通常涉及在不同的纸层上剪裁不同的图案,并将它们…...
递归组件怎么实现无线滚动
递归组件实现无限滚动的方法通常涉及到对数据的递归处理和组件的自我调用。以下是一个简单的示例,展示如何使用递归组件实现无限滚动: 首先,定义一个递归组件,该组件可以调用自己来渲染下一组数据。假设我们要展示一个滚动列表&a…...
Flask RESTful 示例
目录 1. 环境准备2. 安装依赖3. 修改main.py4. 运行应用5. API使用示例获取所有任务获取单个任务创建新任务更新任务删除任务 中文乱码问题: 下面创建一个简单的Flask RESTful API示例。首先,我们需要创建环境,安装必要的依赖,然后…...
利用ngx_stream_return_module构建简易 TCP/UDP 响应网关
一、模块概述 ngx_stream_return_module 提供了一个极简的指令: return <value>;在收到客户端连接后,立即将 <value> 写回并关闭连接。<value> 支持内嵌文本和内置变量(如 $time_iso8601、$remote_addr 等)&a…...
无法与IP建立连接,未能下载VSCode服务器
如题,在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈,发现是VSCode版本自动更新惹的祸!!! 在VSCode的帮助->关于这里发现前几天VSCode自动更新了,我的版本号变成了1.100.3 才导致了远程连接出…...
LeetCode - 394. 字符串解码
题目 394. 字符串解码 - 力扣(LeetCode) 思路 使用两个栈:一个存储重复次数,一个存储字符串 遍历输入字符串: 数字处理:遇到数字时,累积计算重复次数左括号处理:保存当前状态&a…...
c++ 面试题(1)-----深度优先搜索(DFS)实现
操作系统:ubuntu22.04 IDE:Visual Studio Code 编程语言:C11 题目描述 地上有一个 m 行 n 列的方格,从坐标 [0,0] 起始。一个机器人可以从某一格移动到上下左右四个格子,但不能进入行坐标和列坐标的数位之和大于 k 的格子。 例…...
Element Plus 表单(el-form)中关于正整数输入的校验规则
目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入(联动)2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...
Angular微前端架构:Module Federation + ngx-build-plus (Webpack)
以下是一个完整的 Angular 微前端示例,其中使用的是 Module Federation 和 npx-build-plus 实现了主应用(Shell)与子应用(Remote)的集成。 🛠️ 项目结构 angular-mf/ ├── shell-app/ # 主应用&…...
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)
Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习) 一、Aspose.PDF 简介二、说明(⚠️仅供学习与研究使用)三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...
20个超级好用的 CSS 动画库
分享 20 个最佳 CSS 动画库。 它们中的大多数将生成纯 CSS 代码,而不需要任何外部库。 1.Animate.css 一个开箱即用型的跨浏览器动画库,可供你在项目中使用。 2.Magic Animations CSS3 一组简单的动画,可以包含在你的网页或应用项目中。 3.An…...
SQL慢可能是触发了ring buffer
简介 最近在进行 postgresql 性能排查的时候,发现 PG 在某一个时间并行执行的 SQL 变得特别慢。最后通过监控监观察到并行发起得时间 buffers_alloc 就急速上升,且低水位伴随在整个慢 SQL,一直是 buferIO 的等待事件,此时也没有其他会话的争抢。SQL 虽然不是高效 SQL ,但…...
