双链表,顾名思义,就是两个单链表
知道了双链表的本质,事情就好办了,只要把单链表的代码复制两遍就好了
先看代码
#include<bits/stdc++.h>//懒得看我BB的可以直接跳下面正片
using namespace std;
int nex[100010],fa[100010],num[100010];
int ct=1;
void linsert(int k,int x);
void rinsert(int k,int x);
int main()
{
int m;
cin>>m;
while(m--){
string c;
cin>>c;
if(c=="L"){
int x;
cin>>x;
rinsert(0,x);
}
if(c=="R"){
int x;
cin>>x;
linsert(0,x);
}
if(c=="D"){
int k;
cin>>k;
nex[fa[k]]=nex[k];
fa[nex[k]]=fa[k];
}
if(c=="IL"){
int k,x;
cin>>k>>x;
linsert(k,x);
}
if(c=="IR"){
int k,x;
cin>>k>>x;
rinsert(k,x);
}
}
for(int e=nex[0];e;e=nex[e]){
cout<<num[e]<<' ';
}
return 0;
}
void linsert(int k,int x)//这里的两个insert函数是在Ac Saber里仓促打出来的,下文的insert函数更加简洁,不过这两个insert函数更加本质
{
fa[ct]=fa[k];
nex[ct]=k;
nex[fa[ct]]=ct;
fa[nex[ct]]=ct;
num[ct++]=x;
}
void rinsert(int k,int x)
{
fa[ct]=k;
nex[ct]=nex[k];
nex[fa[ct]]=ct;
fa[nex[ct]]=ct;
num[ct++]=x;
}
是不是和网上的题解很不一样?是的!这就是艺术
事实上,这些代码是我在没有看题解,教练也没给我们讲过(就是懒得讲)的情况下完成的
其他的题解,有一说一,我觉得不大好看,然而我们的教练居然写了一个和题解一样的代码
于是,就有了这篇题解
我来 装个逼 展示一下我的写法较为优秀的地方
1. 不进行多余的初始化
你可以在Acwing的题解(包括我们教练代码)里看到许多诸如此类的东西
void init()
{
l[1] = 0, r[0] = 1;
idx = 2;
}
个人认为这种初始化比较多余,影响代码美观性和可读性
2. 对称!!!(划重点)
这是我写这篇题解的根本原因!我当时AC了双链表的时候,自己被自己的代码惊艳到了
这个代码具有惊人的高度对称性,完全不像是人写出来的
众所周知,XX是条狗
而许多题解里表演了一手只用一个插入函数完成了我两个插入函数干完的活
这不艺术!这破坏了双链表的对称之美
多写几行代码不会累死,打得越多,大模拟做得越6,CSP越不容易像我一样爆零~
正片开始
我们来解读一下代码
我们联想单链表:在单链表中,我们用0作为固定的表头,使用nex数组把数串成一个单向的链
那么我们能不能再用另一个数作为固定的表尾,使用另一个数组fa把这条链变成双向的呢?
于是对称性就出来了
nex -> fa
linsert -> rinsert
向表头插入数 -> 向表尾插入数
更神奇的是,如果把0同时作为表头和表尾,整个链表就变成了一个环!
而且由于nex[0]和fa[0]初值就是0,我们连初始化都不用多写了!(这人也太懒了,刚刚还说多打几行代码不会累死)
天哪!我们现在就来实现它!
首先,链表最大的难点在于理解我们口中的数是什么
所以我在此特别声明,下文的数一般指的是我们分配给它的下标,并且,
是在num数组中的下标!!!
初始化的事还是需要一提,本质上我们的初始化是这样的
fa[0] = 0;
nex[0] = 0;
先让表头指向表尾,表尾指向表头,这样才是两条链(一个环)
写这个干啥,反正fa[0]和nex[0]本来就是0
再谈插入
rinsert就是单链表的insert,向表头插入数也和单链表的实现方法完全一致:
如:把a插在b右边
则让a的nex先指向b的nex指向的数,再让b的nex指向a,即
nex[a] = nex[b];
nex[b] = a;//注意,这里的a,b均为下标
不过需要注意的是,由于有了fa数组,记得把fa数组的指向更改,所以rinsert代码如下
void rinsert(int k,int x)
{
nex[ct]=nex[k];//新插入的数令其下标为ct,函数参数里的k是要插在哪个数的左边(k是下标),x是插入的数的值
nex[k]=ct;
fa[ct]=k;
fa[nex[ct]]=ct;
num[ct++]=x;//用num数组储存下标为ct的数的值x,注意ct要++
}
在表头插数当然就是在表头(即0)的右边插入啦,自己看代码,我懒得复制粘贴
linsert和rinsert同理,不过是利用fa的指向去插入
void linsert(int k,int x)
{
fa[ct]=fa[k];//就是把rinsert中的fa换成nex,nex换成fa,这就是linsert和rinsert的对称
fa[k]=ct;
nex[ct]=k;
nex[fa[ct]]=ct;
num[ct++]=x;
}
同理,在表尾插入数就是在0左边插入~
delete也和单链表的delete类似
void delete(int k)//我的原始代码没有这个函数
{
nex[fa[k]]=nex[k];
fa[nex[k]]=fa[k];
}//同样也要注意k是下标,nex和fa也是可以互换~
这样一个对称的双链表就完成啦!针不戳~