双链表

一、算法描述

本篇文章讲述的数据结构是双链表,与上一篇文章一样是算法竞赛中常用的用数组模拟的双链表。

//用数组模拟的双链表定义如下:
int e[N], l[N], r[N], idx;

/*
	e[i]表示节点i的值
	l[i]表示节点i的左边一个节点
	r[i]表示节点i的右边一个节点
	idx表示当前用到了哪个节点
*/
  • 跟单链表差不多。
  • 多画图,多思考。

接下来介绍双链表的各种操作:

初始化操作:

void init()
{
    r[0] = 1, l[1] = 0, idx = 2;
}
  • \(0\)\(1\) 为两个界限,初始状态就是 \(0\) 的右边是 \(1\)\(1\) 的左边是 \(0\)
  • 要注意 \(idx\)\(2\) 开始。

在第k个节点右边插入:

void add(int k, int x)	//在第k个节点的右边插入一个新节点
{
    e[idx] = x;
    
    r[idx] = r[k], l[r[k]] = idx;
    
    l[idx] = k, r[k] = idx ++ ;
}
  • \(e[idx] = x\) 表示新节点的值为 \(x\)
  • \(r[idx] = r[k], l[r[k]] = idx;\) 表示新节点的下一个节点指向 \(k\) 节点的下一个节点 \(p\) ,然后 \(p\) 的前一个节点又指向新节点。
  • \(l[idx] = k, r[k] = idx;\) 表示新节点的左节点为 \(k\)\(k\) 节点的右节点指向 新节点。
  • \(idx ++ ;\) 表示当前节点已经被用了,待使用的节点是下一个。
  • 如何在左边插入呢?显然只需要修改一下参数即可:add(l[k], x)
  • 建议画图来理解。

删除第 \(k\) 个节点:

void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}
  • 数组删除不需要管内存泄漏的问题。
  • 假设用 \(p, k, q\) 来表示三个节点:
  • \(r[l[k]] = r[k];\) 表示 \(p\) 的右边指向 \(k\) 的右边,即 \(q\)
  • \(l[r[k]] = l[k];\) 表示 \(q\) 的左边指向 \(k\) 的左边,即 \(p\)
  • 画图来理解。

如何遍历呢?

for (int i = r[0]; i != 1; i = r[i])	cout << e[i] << ' ';
for (int i = l[1]; i != 0; i = l[i])	cout << e[i] << ' ';
  • 第一行是从左往右遍历,第二行是从右往左遍历。
  • \(0\)\(1\) 是两个界限,所以是从 \(r[0]\)\(l[1]\) 开始,而不是从 \(0\)\(1\) 开始。

链表的问题都需要读者多画图、多思考,也要多复习。

二、题目描述

实现一个双链表,双链表初始为空,支持 \(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. D k,表示将第 \(k\) 个插入的数删除。
  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 

三、题目来源

AcWing算法基础课-827.双链表

四、源代码

#include <iostream>
#include <cstring>

using namespace std;

const int N = 100010;

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

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

void add(int k, int x)
{
    e[idx] = x;
    
    r[idx] = r[k], l[r[k]] = idx;
    
    l[idx] = k, r[k] = idx ++ ;
}

void remove(int k)
{
    r[l[k]] = r[k];
    l[r[k]] = l[k];
}

int main()
{
    int m;
    cin >> m;
    
    init();
    
    while (m -- )
    {
        char s[10];
        cin >> s;
        
        int k, x;
        
        if (!strcmp(s, "L"))
        {
            cin >> x;
            add(0, x);
        }
        else if (!strcmp(s, "R"))
        {
            cin >> x;
            add(l[1], x);
        }
        else if (!strcmp(s, "D"))
        {
            cin >> k;
            remove(k + 1);
        }
        else if (!strcmp(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;
}

/*
本题目并非完全照抄以上函数,还是需要处理一些问题的。
例如:删除第k个数,idx是从2开始使用的,所以删除的时候应该是remove(k + 1);
还有其他问题,读者可自行思考。
*/

热门相关:全天下都知道太子爱她   青莲剑说   龙印战神   离婚合约:前妻的秘密   离婚合约:前妻的秘密