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

做网站能力介绍渠道网

news 2025/7/14 5:32:09

做网站能力介绍,渠道网,重庆便宜做网站的,自己做效果图的网站双链表（数组模拟） 什么是双链表数组模拟双链表题目什么是双链表双链表不同于单链表的是每一个节点不但存储了下一个节点的位置，也存储了上一个节点的位置。数组模拟双链表所以如果用数组的话，就需要创建三个数组。题目 …

双链表（数组模拟）

什么是双链表
数组模拟双链表
题目

什么是双链表

双链表不同于单链表的是每一个节点不但存储了下一个节点的位置，也存储了上一个节点的位置。

数组模拟双链表

所以如果用数组的话，就需要创建三个数组。

题目

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

在最左侧插入一个数；
在最右侧插入一个数；
将第 $k$ 个插入的数删除；
在第 $k$ 个插入的数左侧插入一个数；
在第 $k$ 个插入的数右侧插入一个数

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

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

输入格式

第一行包含整数 $M$ ，表示操作次数。

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

L x，表示在链表的最左端插入数 $x$ 。
R x，表示在链表的最右端插入数 $x$ 。
D k，表示将第 $k$ 个插入的数删除。
IL k x，表示在第 $k$ 个插入的数左侧插入一个数。
IR k x，表示在第 $k$ 个插入的数右侧插入一个数。

输出格式

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

数据范围

$\le M \le 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

在这里插入图片描述
其中数组 e 用于存储元素的值，数组 l 存储上一个节点的位置（下标），数组 r 存储下一个节点的位置。

idx 是下一次即将要用到的点。

对于双链表来说，虽然题目中有5中操作，但是只需要写两个函数就可以了。（不包含初始化函数）

初始化函数：
在这里插入图片描述
在用数组模拟双链表时，我们可以规定数组的前两个点分别指向链表的头和尾，由于刚开始没有节点。

所以让他们互相指向对方，由于前面用了两个点，所以直接让 idx = 2.

在 k 位置后插入一个新节点的函数：

在这里插入图片描述
模拟代码过程：

e[ idx ] = x;

在这里插入图片描述

l[ idx ] = k;
在这里插入图片描述
r[ idx ] = r[ k ];

l[ r [ k ] ] = idx;

r[ k ] = idx;
在这里插入图片描述
最后自增 idx。

删除下标为 k 的数的函数：

在这里插入图片描述
r[ l[ k ] ] = r [ k ];

l [ r [ k ] ] = l [ k ];

在这里插入图片描述

本题目当中的五种操作都可以转换该两种函数。

在这里插入图片描述
输入m，然后循环输入m次，记得写初始化函数。

在这里插入图片描述

因为用scanf读取字符会读取空格或换行符，而%s不会读取这些符号，所以会方便很多

题目的五个操作：

在这里插入图片描述

0下标是一个没有存值（数组e里面没有值，数组 l 有值）的头坐标，所以在下标0的右面插入一个值相当于在整个链表左边插入一个值。
在这里插入图片描述

1下标记录着链表最右边的位置，l [ 1 ] 则代表链表中最右边的点的位置，所以在 l [ 1 ] 后面插入相当于在链表的最右边插入一个值。

在这里插入图片描述

这里唯一注意的点就是传的实参是 k + 1，而不是k ，因为已经用过两个点了。所以插入的第一个数的下标就是从2开始的，以此类推。

在这里插入图片描述

在这里插入图片描述
如果我们想要在 k 位置的左边插入一个节点，那么相当于在 k 的左边节点的右侧插入一个节点。

在这里插入图片描述

那么在右侧就直接调用函数即可。

最后输出整个链表即可

在这里插入图片描述
完整代码如下：

#include <iostream>
#include <cstring>
using namespace std;const int N = 1e5+10;int e[N], l[N], r[N];
int idx;void init()
{r[0] = 1;l[1] = 0;idx = 2;
}//在 k 下标后插入一个数
void insert(int k, int x)
{e[idx] = x;l[idx] = k;r[idx] = r[k];l[r[k]] = idx;r[k] = idx;idx++;
}//删除下标为 k 的节点
void remove(int k)
{r[l[k]] = r[k];l[r[k]] = l[k];
}int main()
{init();int m;scanf("%d", &m);while (m--){char op[5];int k, x;scanf("%s", op);if (op[0] == 'L')//链表最左端插入一个数{scanf("%d", &x);insert(0, x);}else if (op[0] == 'R')//链表最右端插入一个数{scanf("%d", &x);insert(l[1], x);}else if (op[0] == 'D')//将插入的第K个数删除{scanf("%d", &k);remove(k + 1);//数组刚开始会用掉两个点，//那么插入的第一个数下标就为2，所以插入的第k个数就是下标就是k+1.}else if (strcmp(op, "IL") == 0){scanf("%d%d", &k, &x);insert(l[k+1], x); }else {scanf("%d%d", &k, &x);insert(k+1, x);}}for (int i = r[0]; i != 1; i = r[i]) printf("%d ", e[i]);return 0;
}