简述企业网站建设的流程,石家庄外贸网站建设,网站建设计无形资产,长葛网站建设公司算法竞赛基础#xff1a;双向链表
本文将会介绍在算法竞赛中双向链表的几种使用方式#xff0c;适合有一定基础的人阅读。
双向链表的结构
一般来说#xff0c;普通的链表结构是这样的#xff1a;
struct node {int num;node *next;
}next指针指向下一个链表#xff…算法竞赛基础双向链表
本文将会介绍在算法竞赛中双向链表的几种使用方式适合有一定基础的人阅读。
双向链表的结构
一般来说普通的链表结构是这样的
struct node {int num;node *next;
}next指针指向下一个链表这样的结构只能够支持单向查询。
双向链表顾名思义就是可以支持双向的访问和查询。
也就是这样的
struct node {int num;node *l, *r;
}这种链表为访问前后的元素提供的很大的便利性。
C的STL模板中也有类似的结构 List
listint lis;List是连续的容器而vector是非连续的容器即list将元素存储在连续的存储器中而vector存储在不连续的存储器中。
向量vector中间的插入和删除是非常昂贵的因为它需要大量的时间来移动所有的元素。链表克服了这个问题它是使用list容器实现的。
List支持双向并为插入和删除操作提供了一种有效的方法。
在列表中遍历速度很慢因为列表元素是按顺序访问的而vector支持随机访问。
列表模板
示例
#includeiostream
#includelist
using namespace std;
int main()
{listint l;
}它创建一个空的整数类型值列表。
列表也可以使用参数初始化。
示例
#includeiostream
#includelist
using namespace std;
int main()
{listint l{1,2,3,4};
}列表可以通过两种方式初始化。
示例
listint new_list{1,2,3,4};
or
listint 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会指向11的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] ;}
