双链表模板

模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
// e[]表示节点的值，l[]表示节点的左指针，r[]表示节点的右指针，idx表示当前用到了哪个节点
int e[N], l[N], r[N], idx;

// 初始化
void init()
{
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

// 在节点a的右边插入一个数x
void insert(int a, int x)
{
    e[idx] = x;
    l[idx] = a, r[idx] = r[a];
    l[r[a]] = idx, r[a] = idx ++ ;
}

// 删除节点a
void remove(int a)
{
    l[r[a]] = l[a];
    r[l[a]] = r[a];
}



题目描述：

实现一个双链表，双链表初始为空，支持 5 种操作：

  • 1.在最左侧插入一个数；
  • 2.在最右侧插入一个数；
  • 3.将第 k 个插入的数删除；
  • 4.在第 k 个插入的数左侧插入一个数；
  • 5.在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作，进行完所有操作后，从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数，则按照插入的时间顺序，这 n 个数依次为：第 1 个插入的数，第 2 个插入的数，…第 n 个插入的数。

输入格式
第一行包含整数 M，表示操作次数。

接下来 M 行，每行包含一个操作命令，操作命令可能为以下几种：

  • 1.L x，表示在链表的最左端插入数 x。
  • 2.R x，表示在链表的最右端插入数 x。
  • 3.R x，表示在链表的最右端插入数 x。
  • 4.IL k x，表示在第 k 个插入的数左侧插入一个数。
  • 5.IR k x，表示在第 k 个插入的数右侧插入一个数。

输出格式
共一行，将整个链表从左到右输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例：

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
#include<iostream>

using namespace std;

const int N = 100010;

int m;
int e[N], l[N], r[N], idx; //e[N]存点的值,l[N]存左指针,r[N]存右指针,idx下标

//初始化
void init(){
    //0是左端点，1是右端点
    r[0] = 1, l[1] = 0;
    idx = 2;
}

//在节点k的右边插入一个数X
void add(int k, int x){
    e[idx] = x;
    r[idx] = r[k];
    l[idx] = k;
    l[r[k]] = idx;
    r[k] = idx;
    idx ++;
}

//删除节点k
void remove(int k){
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main(){
    scanf("%d",&m);
    
    init();
    
    while(m--){
        string op;
        cin >> op;
        int k,x;
        if(op == "L"){
            cin >> x;
            add(0, x);
        }
        else if (op == "R"){
            cin >> x;
            add(l[1],x);
        }
        else if (op == "D"){
            cin >> k;
            remove(k+1);
        }
        else if (op == "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] << ' ';
    cout << endl;
    
    return 0;
}
/*
总结下我对几个问题的理解，
1. 之所以在 “D”, “IL”, “IR” 要用 k+1 的原因是 双链表的起始点是2. 所以，每个插入位置k的真实位置应该为 k-1+2 = k+1 (在单链表中为 k-1)。
2. 0, 1 节点的作用是边界。0为左边界，1为右边界。他俩在这里有点类似保留字的作用。正因如此，我们的idx也是从2开始
3. 最后遍历输出结果的 for (int i = rn[0]; i != 1; i = rn[i])。从 rn[0] 开始是因为 0 为左边界，而终止条件 i==1是因为1为右边界（如果碰到，说明已经遍历完毕）
*/



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include<stdio.h>
#include<string.h>
#define N 100010

int e[N], l[N], r[N], idx;

//初始化
void init(){
    r[0] = 1, l[1] = 0;
    idx =2;
}

//在k节点的右边插入一个X
void add(int k, int x){
    e[idx] = x;
    l[r[k]] = idx;
    r[idx] = r[k];
    r[k] = idx;
    l[idx++] = k;
}

//删除k节点
void removeitem(int k){
    l[r[k]] = l[k];
    r[l[k]] = r[k];
}

int main (){
    int m;
    scanf("%d",&m);
    
    init(); 
    
    while(m --){
        char s[3];
        int k, x;
        scanf("%s", s);
        
        if(s[0] == 'L'){
            scanf("%d",&x);
            add(0,x);
        }
        else if (s[0] == 'R'){
            scanf("%d",&x);
            add(l[1],x);
        }
        else if (s[0] == 'D'){
            scanf("%d",&k);
            removeitem(k+1);
        }
        else if (!strcmp(s,"IL")){   //C 库函数 - strcmp()  把 str1 所指向的字符串和 str2 所指向的字符串进行比较。
            scanf("%d%d",&k,&x);
            add(l[k+1],x);
        }
        else if (!strcmp(s,"IR")){
            scanf("%d%d",&k,&x);
            add(k+1,x);
        }
    }
    for(int i = r[0]; i != 1; i = r[i]) printf("%d ",e[i]);
    
    return 0;
}