网站空间太小,银川市网站建设,邢台区域最新调整,做网络推广的方法今天我们来用数组来模拟双链表
为什么要数组模拟呢#xff1f; 因为用数组模拟的双链表#xff0c;运行速度更快#xff0c;做算法题更加舒服
用数组模拟双链表的内容 1、同样也有首尾结点 2、相邻的两个节点是相互指向的 3、可以看成两个方向相反的单链表相互连接在一起 …今天我们来用数组来模拟双链表
为什么要数组模拟呢 因为用数组模拟的双链表运行速度更快做算法题更加舒服
用数组模拟双链表的内容 1、同样也有首尾结点 2、相邻的两个节点是相互指向的 3、可以看成两个方向相反的单链表相互连接在一起 首先同样要初始化 1、现在用两个数组来代表左单链表和右单链表即为l[N], r[N] 2、l[N]数组为指向右边的链表r[N]为指向左边的链表 3、e[N]为当前结点的值 4、设r[0]1,l[1]0,因为是相互指向 5、同样用一个idx来储存当前结点用到了哪一点下面给出图和代码 int m;
int e[N],r[N],l[N],idx;void init()
{r[0]1,l[1]0;idx2;
}为什么idx要等于2呢因为初始化左右结点因为各被用了所以 idx为2而且0代表头结点1为尾节点
接下来就是功能的实现 1、任意插入一个数x 2、任意删除某一个结点 讲x插入到第k的右边 1、首先要确定某一个结点e[idx]x; 2、让idx的右边指向k结点的右边r[idx]r[k]; 3、让idx的左边指向k,l[idx]k 4、再让k结点的右边的点指向x即为l[r[k]]idx; 5、再让k结点的左边指向idxr[k]idx; 6、最后当前结点被用过了所以idx要向后移动一位即idx; 而且第四步和第五步不能相互颠倒如果相互颠倒就会改变r[k]的值就会出现错误 代码功能如下
//插入第k个数
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节点的左边呢
就是相当于l[k]的右边插入一个数所以把参数k换成l[k]就行因为l[k]为k左边相邻的结点
2、删除某一个结点
和单链表相似不过这次要左边和右边都要相互操作一遍
因为某一个结点都是相互指向的用第k个结点举例
首先用k结点的左边的结点等于k结点右边的结点即为r[l[k]]r[k];
然后再让k结点的右边的结点等于k结点左边的节点即为l[r[k]]l[k];
//删除第k个数
void remove(int k)
{r[l[k]]r[k];l[r[k]]l[k];
}这样双链表的功能的就实现了
具体问题
实现一个双链表双链表初始为空支持 5 种操作 在最左侧插入一个数在最右侧插入一个数将第 k 个插入的数删除在第 k 个插入的数左侧插入一个数在第 k 个插入的数右侧插入一个数现在要对该链表进行 M 次操作进行完所有操作后从左到右输出整个链表。 现在要对该链表进行 M 次操作进行完所有操作后从左到右输出整个链表。 注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数则按照插入的前后顺序这 n 个数依次为第 1 个插入的数第 2 个插入的数…第 n 个插入的数。
Acwing 827
#include iostream
using namespace std;const int 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[idx] k;r[idx] r[k];l[r[k]] idx;r[k] idx;idx;
}void remove(int k) {r[l[k]] r[k];l[r[k]] l[k];
}int main() {int n;cin n;init();while (n--) {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 if (op IR) {cin k x;add(k 1, x);}}int head r[0];while (head ! 1) {cout e[head] ;head r[head];}return 0;
}
