C++

$\color{#cc33ff}{— > 算法基础课题解}$

初始化图解

在下标是k的点的右边，插入一个点x 图解

删除第k个点 图解

#include<iostream>
using namespace std;

const int N = 1e5 + 10;

//e表示每个点的值
//l表示左边的点是谁，r表示右边的点是谁
//idx表示当前所用之点
int l[N], r[N], e[N], idx;
int m;

// struct Node{
//     int e, l, r;
// }nodes[N];


//初始化
void init(){
    //0表示左端点，1表示右端点
    r[0] = 1, l[1] = 0; // 0号点的右边是1号点，1号点的左边是0号点
    idx = 2; // 因为0和1已经被用了

}

//在下标是k的点的右边，插入一个点x
void add(int k, int x){
    e[idx] = x;//存储这个值x
    r[idx] = r[k]; //这个点x的右边指向k号点的右边
    l[idx] = k; //这个点x的左边指向k
    l[r[k]] = idx; // 原k号点的右边那个点的左边指向插入点x
    r[k] = idx ++; // k号点的右边指向插入点x

}

//如果想要在下标是k的点的左边，插入一个点x
//可以直接 : add(l[k], x); //因为 l[k] 就是k的左边那个点

//删除第k个点
void remove(int k){
    r[l[k]] = r[k]; //让k号点左边那个点的右边直接指向k号点的右边那个点
    l[r[k]] = l[k]; //让k号点右边那个点的左边直接指向k号点的左边那个点
}


int main(){
    cin >> 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"){//将第 k 个插入的数删除；
            cin >> k;
            remove(k + 1);
        }else if (op == "IL"){//在第 k 个插入的数左侧插入一个数；
            cin >> k >> x;
            add(l[k + 1], x);
        }else{//在第 k 个插入的数右侧插入一个数
            cin >> k >> x;
            add(k + 1, x);
        }
    }

    for (int i = r[0]; i != 1; i = r[i]) cout << e[i] << ' ';

    return 0;
}