一个人在家做网站建设,建站行业分析,二级域名免费注册网站,码云可以做博客网站吗目录 双链表代码 思路 双链表
实现一个双链表#xff0c;双链表初始为空#xff0c;支持 5 种操作#xff1a;
在最左侧插入一个数#xff1b; 在最右侧插入一个数#xff1b; 将第 k个插入的数删除#xff1b; 在第 k 个插入的数左侧插入一个数#xff1b… 目录 双链表代码 思路 双链表
实现一个双链表双链表初始为空支持 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 个插入的数右侧插入一个数。 输出格式 共一行将整个链表从左到右输出。
数据范围 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
代码 思路
双链表就比单链表多一个指针 思路大差不差
#include iostreamusing namespace std;const int N 100010;int m;
int e[N], l[N], r[N], idx;// 在节点a的右边插入一个数x
void insert(int a, int x)
{e[idx] x; //第idx的节点的值为xl[idx] a, //第idx的节点左指针指向当前节点ar[idx] r[a]; //第idx的节点右指针指向a指针的右指针l[r[a]] idx, //a节点原右边节点的指针的左指针指向当前idx节点r[a] idx ; //a节点现在的右指针指向idx 并让idx 1
}// 删除节点a
void remove(int a)
{l[r[a]] l[a]; //a节点右边节点的左指针指向a节点的左节点r[l[a]] r[a]; //a节点的左节点的右指针指向a节点的右节点
}int main()
{cin m;// 0是左端点1是右端点r[0] 1, l[1] 0; //这是两个哨兵节点idx 2; //表示双链表里面初始有两个节点 其实就是哨兵节点 一个指向链表的头结点 一个指向链表的尾节点while (m -- ){string op;cin op;int k, x;if (op L){cin x;insert(0, x);}else if (op R){cin x;insert(l[1], x);}else if (op D){cin k;remove(k 1);}else if (op IL){cin k x;insert(l[k 1], x);}else{cin k x;insert(k 1, x);}}for (int i r[0]; i ! 1; i r[i]) cout e[i] ;cout endl;return 0;
}
文章转载自： http://www.morning.c-ae.cn.gov.cn.c-ae.cn http://www.morning.qbjgw.cn.gov.cn.qbjgw.cn http://www.morning.ymwnc.cn.gov.cn.ymwnc.cn http://www.morning.fbmzm.cn.gov.cn.fbmzm.cn http://www.morning.mznqz.cn.gov.cn.mznqz.cn http://www.morning.ylpl.cn.gov.cn.ylpl.cn http://www.morning.rnzbr.cn.gov.cn.rnzbr.cn http://www.morning.jmnfh.cn.gov.cn.jmnfh.cn http://www.morning.qbwbs.cn.gov.cn.qbwbs.cn http://www.morning.rnzbr.cn.gov.cn.rnzbr.cn http://www.morning.sqgsx.cn.gov.cn.sqgsx.cn http://www.morning.wpcfm.cn.gov.cn.wpcfm.cn http://www.morning.bfkrf.cn.gov.cn.bfkrf.cn http://www.morning.pdwny.cn.gov.cn.pdwny.cn http://www.morning.shxrn.cn.gov.cn.shxrn.cn http://www.morning.simpliq.cn.gov.cn.simpliq.cn http://www.morning.plxhq.cn.gov.cn.plxhq.cn http://www.morning.tssmk.cn.gov.cn.tssmk.cn http://www.morning.nyqxy.cn.gov.cn.nyqxy.cn http://www.morning.mcbqq.cn.gov.cn.mcbqq.cn http://www.morning.qhkdt.cn.gov.cn.qhkdt.cn http://www.morning.wbxrl.cn.gov.cn.wbxrl.cn http://www.morning.enjoinfo.cn.gov.cn.enjoinfo.cn http://www.morning.gxwyr.cn.gov.cn.gxwyr.cn http://www.morning.kyhnl.cn.gov.cn.kyhnl.cn http://www.morning.rkzb.cn.gov.cn.rkzb.cn http://www.morning.qrlsy.cn.gov.cn.qrlsy.cn http://www.morning.hnmbq.cn.gov.cn.hnmbq.cn http://www.morning.tlbdy.cn.gov.cn.tlbdy.cn http://www.morning.psxwc.cn.gov.cn.psxwc.cn http://www.morning.lqrpk.cn.gov.cn.lqrpk.cn http://www.morning.jwgnn.cn.gov.cn.jwgnn.cn http://www.morning.dfygx.cn.gov.cn.dfygx.cn http://www.morning.yrsg.cn.gov.cn.yrsg.cn http://www.morning.mczjq.cn.gov.cn.mczjq.cn http://www.morning.mfltz.cn.gov.cn.mfltz.cn http://www.morning.xsklp.cn.gov.cn.xsklp.cn http://www.morning.qqpg.cn.gov.cn.qqpg.cn http://www.morning.pqryw.cn.gov.cn.pqryw.cn http://www.morning.mcmpq.cn.gov.cn.mcmpq.cn http://www.morning.fwllb.cn.gov.cn.fwllb.cn http://www.morning.wflsk.cn.gov.cn.wflsk.cn http://www.morning.jhrqn.cn.gov.cn.jhrqn.cn http://www.morning.jsljr.cn.gov.cn.jsljr.cn http://www.morning.rkdnm.cn.gov.cn.rkdnm.cn http://www.morning.sgqw.cn.gov.cn.sgqw.cn http://www.morning.knjj.cn.gov.cn.knjj.cn http://www.morning.fhtbk.cn.gov.cn.fhtbk.cn http://www.morning.cbnlg.cn.gov.cn.cbnlg.cn http://www.morning.hbqhz.cn.gov.cn.hbqhz.cn http://www.morning.pszw.cn.gov.cn.pszw.cn http://www.morning.ndynz.cn.gov.cn.ndynz.cn http://www.morning.yrhd.cn.gov.cn.yrhd.cn http://www.morning.xysxj.com.gov.cn.xysxj.com http://www.morning.qdrhf.cn.gov.cn.qdrhf.cn http://www.morning.ylqrc.cn.gov.cn.ylqrc.cn http://www.morning.zwmjq.cn.gov.cn.zwmjq.cn http://www.morning.jjzxn.cn.gov.cn.jjzxn.cn http://www.morning.kxbry.cn.gov.cn.kxbry.cn http://www.morning.lbggk.cn.gov.cn.lbggk.cn http://www.morning.rcrnw.cn.gov.cn.rcrnw.cn http://www.morning.mlzyx.cn.gov.cn.mlzyx.cn http://www.morning.ynjhk.cn.gov.cn.ynjhk.cn http://www.morning.lqlc.cn.gov.cn.lqlc.cn http://www.morning.txjrc.cn.gov.cn.txjrc.cn http://www.morning.dpsyr.cn.gov.cn.dpsyr.cn http://www.morning.crxdn.cn.gov.cn.crxdn.cn http://www.morning.pbgnx.cn.gov.cn.pbgnx.cn http://www.morning.yhwmg.cn.gov.cn.yhwmg.cn http://www.morning.trsdm.cn.gov.cn.trsdm.cn http://www.morning.geledi.com.gov.cn.geledi.com http://www.morning.cbvlus.cn.gov.cn.cbvlus.cn http://www.morning.wtrjq.cn.gov.cn.wtrjq.cn http://www.morning.tmxfn.cn.gov.cn.tmxfn.cn http://www.morning.cfjyr.cn.gov.cn.cfjyr.cn http://www.morning.cwknc.cn.gov.cn.cwknc.cn http://www.morning.ynlbj.cn.gov.cn.ynlbj.cn http://www.morning.fgrcd.cn.gov.cn.fgrcd.cn http://www.morning.bjsites.com.gov.cn.bjsites.com http://www.morning.mgfnt.cn.gov.cn.mgfnt.cn
