当前位置：首页 > news >正文

Acwing 双链表

news 2024/11/20 19:25:45

双链表：数据结构

基本方法： 此时没有头指针，固定数组的前后两个位置的存储，下标0的位置存储链表的第一个节点（即左端点），数组下标1的位置存储链表的末尾节点（即右端点）。三个数组：e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点。

下面直接给出需要背过的板子：

//e[]存储节点的值
//l[]表示节点的左指针
//r[]表示节点的右指针
//idx表示当前用到了哪个节点int e[N],l[N],r[N],idx;void init(){//head = 0,tail = 1l[1] = 0,r[0] = 1;idx = 2;
}//在下标是k的右边插入一个点x
void add(int k,int x){e[idx] = x;//存值r[idx] = r[k];//idx的右边指向r[k]的位置l[idx] = k;//idx的左边指向k的位置l[r[k]] = idx; //r[k]的左边指向idx的位置r[k] = idx++;//k的右边指向idx}
//在下标是k的左边插入一个点x 等价于add(l[k],x)
void add1(int k,int x){e[idx] = x;//存值l[idx] = l[k];//idx的左边指向l[k]的位置r[idx] = k;//idx的右边指向k的位置r[l[k]] = idx; //l[k]的右边指向idx的位置l[k] = idx++;//k的左边指向idx}//删除下标是k的点
void remove(int k){r[l[k]] = r[k];//l[k]的右边指向r[k]l[r[k]] = l[k];//r[k]的左边指向l[k]
}

看一个例题，对双链表进行操作

实现一个双链表，双链表初始为空，支持 5
种操作：
1.在最左侧插入一个数；
2.在最右侧插入一个数；
3.将第 k个插入的数删除；
4.在第 k个插入的数左侧插入一个数；
5.在第 k个插入的数右侧插入一个数
现在要对该链表进行 M次操作，进行完所有操作后，从左到右输出整个链表。

输入格式
输入样例：

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例：

8 7 7 3 2 9

用板子进行操作即可。具体实现代码如下：

#include <iostream>using namespace std;const int N=100010;//e[]存储节点的值
//l[]表示节点的左指针
//r[]表示节点的右指针
//idx表示当前用到了哪个节点int e[N],l[N],r[N],idx;void init(){//head = 0,tail = 1l[1] = 0,r[0] = 1;idx = 2;
}//在下标是k的右边插入一个点x
void add(int k,int x){e[idx] = x;//存值r[idx] = r[k];//idx的右边指向r[k]的位置l[idx] = k;//idx的左边指向k的位置l[r[k]] = idx; //r[k]的左边指向idx的位置r[k] = idx++;//k的右边指向idx}
//在下标是k的左边插入一个点x 等价于add(l[k],x)
void add1(int k,int x){e[idx] = x;//存值l[idx] = l[k];//idx的左边指向l[k]的位置r[idx] = k;//idx的右边指向k的位置r[l[k]] = idx; //l[k]的右边指向idx的位置l[k] = idx++;//k的左边指向idx}//删除下标是k的点
void remove(int k){r[l[k]] = r[k];//l[k]的右边指向r[k]l[r[k]] = l[k];//r[k]的左边指向l[k]
}int main(){int m;cin >> m;init();//一定记得初始化，不然报错！while(m--){string s;cin >> s;int k,x;if(s == "L"){cin >> x;add(0,x);}else if(s == "R"){cin >> x;add(l[1],x);}else if(s == "D"){cin >> k;remove(k+1);//插入的第一个数字下标其实是2，第k个数字下标是k+1}else if(s == "IL"){cin >> k >> x;add(l[k+1],x);}else{cin >> k >> x;add(k+1,x);}}for(int i = r[0] ; i != 1 ;i = r[i]) cout << e[i] <<' ';//输出要特别注意！return 0;
}