代做视频的网站好,怎么做网页快捷方式,图片优化软件,正规的家居行业网站开发文章目录 题目描述基本思路实现代码 题目描述
实现一个单链表#xff0c;链表初始为空#xff0c;支持三种操作#xff1a;
向链表头插入一个数#xff1b;删除第 k个插入的数后面的一个数#xff1b;在第 k个插入的数后插入一个数。
现在要对该链表进行M次操作#x… 文章目录 题目描述基本思路实现代码 题目描述
实现一个单链表链表初始为空支持三种操作
向链表头插入一个数删除第 k个插入的数后面的一个数在第 k个插入的数后插入一个数。
现在要对该链表进行M次操作进行完所有操作后从头到尾输出整个链表。
注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数则按照插入的时间顺序这n个数依次为第1个插入的数第2个插入的数…第n个插入的数。
输入格式
第一行包含整数M表示操作次数。接下来M行每行包含一个操作命令操作命令可能为以下几种 H x表示向链表头插入一个数x。D k表示删除第k个插入的数后面的数当k为0时表示删除头结点。I k x表示在第k个插入的数后面插入一个数x此操作中k均大于 0。
输出格式
共一行将整个链表从头到尾输出。
数据范围
1 ≤ M ≤ 100000所有操作保证合法。
基本思路
在通常情况下以及我们的课程学习过程中都是使用一个结构体表示链表结点或完整的链表。但是这种方式需要每次使用new运算符创建一个新的链表结点而这实际上是一个非常低效的方式。因此实际的算法竞赛中往往使用一个数组或向量来模拟出一个链表称为静态链表从而避免低效的动态内存分配。单链表的实际作用主要是写邻接表用来存储图和树。
实现代码
#include iostream
#include vector
using namespace std;typedef int value;
typedef int pos;
vector pairvalue, pos List;int head -1;inline void insert_to_head(const int x)
{List.push_back({x, head});head List.size() - 1;
}inline void del_after(const int k)
{if(k 0) head List[head].second;else List[k - 1].second List[List[k - 1].second].second;
}inline void insert_after(const int k, const int x)
{List.push_back({x, List[k - 1].second});List[k - 1].second List.size() - 1;
}int main(void)
{int m;cin m;for(int i 0; i m; i){char operation;cin operation;if(operation H){int x;cin x;insert_to_head(x);}else if(operation D){int k;cin k;del_after(k);}else if(operation I){int k, x;cin k x;insert_after(k, x);}}while(List[head].second ! -1){cout List[head].first ;head List[head].second;}cout List[head].first ;return 0;
}注意事项
这里如果不使用cin进行输入而是使用scanf函数的话会出现奇怪的难以解释的错误。因此以后的算法编程题目中如果不是输入量特别大的话都尽量使用更加简单的cin方式进行输入。
