IT评测·应用市场-qidao123.com技术社区

标题: AcWing双链表 [打印本页]

---

作者: 惊落一身雪    时间: 2024-8-9 07:43
标题: AcWing双链表

0索引记载头结点，1索引是尾节点，idx从2开始记载
L和R是前面的索引和背面索引的数组，e是存储的元素的数组，k+1的原因：k是表示第k个插入的元素，                                   k                         ∈                         [                         1                         ,                         inf                         ⁡                         ]                              k\in [1,\inf]                  k∈[1,inf].但是                                   i                         d                         x                         ∈                         [                         2                         ,                         inf                         ⁡                         ]                              idx\in [2,\inf]                  idx∈[2,inf],以是如果要对应上数组内里的话，就要k+1
末了的遍历链表，循环制止i!=1的原因是开头设置了0索引是头结点，1索引是尾节点，i代表了索引，以是i!=1的时间就是没有到尾节点！

1. #include<iostream>
2. #include<string>
3. #define N 100086
5. using namespace std;
6. int M,op,k,x,idx;
7. int e[N],l[N],r[N];
8. void init(){
9.     r[0]=1,l[1]=0,idx=2;
10. }
11. void insert(int k,int x){
12.     e[idx]=x;
13.     r[idx]=r[k];
14.     l[idx]=l[r[k]];
15.     l[r[k]]=idx;
16.     r[k]=idx++;
17. }
18. void remove(int k,int x){
19.     r[l[k]]=r[k];
20.     l[r[k]]=l[k];
21. }
22. int main(){
23.     cin>>M;
24.     init();
25.     while(M--){
26.         string op;
27.         cin>>op;
28.         if(op=="L"){
29.             cin>>x;
30.             insert(0,x);
31.         }else if(op=="R"){
32.             cin>>x;
33.             insert(l[1],x);
34.         }else if(op=="D"){
35.             cin>>k;
36.             remove(k+1,x);
37.         }else if(op=="IL"){
38.             cin>>k>>x;
39.             insert(l[k+1],x);
40.         }else if(op=="IR"){
41.             cin>>k>>x;
42.             insert(k+1,x);
43.         }
44.     }
45.     for(int i=r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
46.     cout<<endl;
47.     return 0;
48. }

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 IT评测·应用市场-qidao123.com技术社区 (https://dis.qidao123.com/)

Powered by Discuz! X3.4