算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)

这篇具有很好参考价值的文章主要介绍了算法竞赛基础: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};

其中,lr分别表示上一个和下一个元素的数组下标。

插入操作

插入操作的思路很简单:
先将新元素的lr指向左右两个元素。
再分别让左右两个元素的rl分别指向新元素本身;


//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,直接不对其进行操作
}

第二种方式虽然没有改变lr的值,但是也能够实现链表访问机制的修改而且还支持数据恢复,相当好用。

查找操作

这种方式是基于上面删除操作时的第二种方式实现的:

bool find(int target) {
	return arr[target].key == 1;
}

因为这种特殊的链表结构支持随机访问(正常的链表结构是不支持的),所以查找操作变成检测对应元素的键值是否有效,如果有效,返回一个真值。

遍历操作

以输出全部数值为例:

这里值得一提的是,如果按照这种上文所述的方式去建立双向链表的话,你会发现没有头结点。

具体原因是由于开辟第一个结点时,也就是数组下标为1的时候,结构体中的lr指向的是1本身,那这个时候如果再多插入几个结点,最后一个结点的r会指向1,1的l会指向最后一个结点,这样一来,当你在1之前插入结点时,按理来说头节点会变成新插入的结点,但由于缺少一个指向头节点的指针而丢失链表的头,这显然是我们不想看到的。

解决方法也很简单,我们在数组下标为0的位置创建一个结点作为虚拟头结点,当在真正的头结点之前插入新的结点时,这时候新结点会在0和头节点之间,当我们需要访问头节点的时候,通过0去访问就可以了。

下面是建立的虚拟头节点0之后的遍历输出操作:文章来源地址https://www.toymoban.com/news/detail-821338.html

void bs() {
	// from left to right
	for (int i = arr[0].r; i; i = arr[i].r) {
		cout << arr[i] << " ";
	}

到了这里,关于算法竞赛基础:C++双向链表的结构和实现(普通链表、List、静态链表)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 数据结构:双向链表的实现(C实现)

    个人主页 : 个人主页 个人专栏 : 《数据结构》 《C语言》 本篇博客,将要实现的是 带头双向循环链表 ,该结构实现尾插,尾删只需要O(1)的时间复杂度。 其结构如下所示: 既然要实现的链表是双向循环的,那么对于指针域,我们就需要 指向节点上一个的指针 和 指向节点

    2024年02月14日
    浏览(52)
  • 【数据结构】—带头双向循环链表的实现(完美链表)

    链表结构一共有八种形式,在前面的文章里已经讲完了不带头单向非循环链表的实现,但是我们发现该链表实现尾插与尾删时比较麻烦,要先从头节点进行遍历,找到尾节点,时间复杂度为O(N),而本次所讲的带头双向循环单链表,则可以直接找到尾节点。 虽然该链表看起来

    2024年01月25日
    浏览(63)
  • 【数据结构】双向链表的增删查改(C 代码实现)

    引入双向链表:关于单链表的问题与讨论 单链表存在的毛病: 因为单链表 只能单向 遍历链表, 对于 前插 这个操作,单链表必 须得找到所需前插节点位置的前一个 ,那么这时就得 从头指针重新遍历一次 链表,会造成时间复杂度大大增加。 没有头节点(哨兵位)无法删除

    2024年02月08日
    浏览(54)
  • 青岛大学_王卓老师【数据结构与算法】Week04_04_双向链表的插入_学习笔记

    本文是个人学习笔记,素材来自青岛大学王卓老师的教学视频。 一方面用于学习记录与分享,另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。 如有侵权,请留言作删文处理。 课程视频链接: 数据结构与算法基础–第04周04–2.5.4双向链表2–双向链表

    2024年02月12日
    浏览(58)
  • 【数据结构】链表的分类和双向链表

    本篇是基于上篇单链表所作,推荐与上篇配合阅读,效果更加 http://t.csdnimg.cn/UhXEj 链表的结构非常多样,以下情况组合起来就有8种(2 x 2 x 2)链表结构: 我们一般叫这个头为哨兵位 我们上回讲的单链表就是不带头单项不循环链表。 今天我们要讲带头双向循环的链表。 不过

    2024年01月25日
    浏览(39)
  • 数据结构_链表_双向循环链表的初始化、插入、删除、修改、查询打印(基于C语言实现)

    版本: 2024年4月26日 V1.0 发布于博客园 目录 目录 双向循环链表公式 初始化双向循环链表 构建双向循环链表结点 创建一个空链表(仅头结点) 创建一个新结点 插入数据 头插 中插 尾插 删除数据 头删 中删 尾删 查询打印数据 遍历打印 测试 测试结果: 完整代码 DoubleCirLList.h

    2024年04月27日
    浏览(55)
  • 数据结构---双向链表的基本操作

    头插法 遍历链表 尾插法 头删法 尾删法 按位置插入数据 按位置删除数据 dooublelinklist.c doublelinklist.h doublemain.c

    2024年02月22日
    浏览(53)
  • 探索数据结构:双向链表的灵活优势

    ✨✨ 欢迎大家来到贝蒂大讲堂✨✨ 🎈🎈养成好习惯,先赞后看哦~🎈🎈 所属专栏:数据结构与算法 贝蒂的主页:Betty’s blog 前面我们学习了单链表,它解决了顺序表中插入删除需要挪动大量数据的缺点。但同时也有仍需改进的地方,比如说:我们有时候需要寻找某个节点

    2024年03月16日
    浏览(59)
  • 【数据结构与算法】之双向链表及其实现!

    ​                                                                                 个人主页:秋风起,再归来~                                                                                             数据结构与

    2024年04月23日
    浏览(42)
  • 【数据结构和算法】使用数组的结构实现链表(单向或双向)

    上文我们通过结构体的结构实现了队列 、以及循环队列的实现,我们或许在其他老师的教学中,只学到了用结构体的形式来实现链表、队列、栈等数据结构,本文我想告诉你的是,我们 可以使用数组的结构实现链表、单调栈、单调队列 目录 前言 一、用数组结构的好处 1.数

    2024年01月20日
    浏览(74)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包