14351: 【原4351】linklist
题目
题目描述
author: galaxies 原OJ链接：https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4351
题目描述
众所周知，第 0 次机考总有一道题是单链表，这次也不例外。
你需要实现一个单链表 $L$，一些需要实现的操作如下：
-
利用数组初始化该单链表，该操作只会在初始时被调用 1 次；
-
在单链表第 $i$ 个元素后插入元素 $x$。特别地，如果 $i = 0$，则表示在表头插入元素；如果 $i = |L|$，则表示在表尾插入元素；如果出现除 $0 \leq i \leq |L|$ 之外的其他情况，无视当前操作；
注意：元素从 1 开始编号。
-
删除单链表的第 $i$ 个元素。特别地，如果出现除 $1 \leq i \leq |L|$ 之外的其他情况，无视当前操作；
-
将单链表奇偶交换，也就是说原来编号为 $2k$ 的元素与原来编号为 $2k - 1$ 的元素交换。如果单链表长度为奇数，则剩下的最后一个元素不需要进行交换；你需要在原地进行该操作，也就是说，这个操作只能使用 $O(1)$ 的额外空间；
-
询问单链表的第 $i$ 个元素。特别地，保证不会出现除 $1 \leq i \leq |L|$ 之外的其他情况。
-
询问整个单链表，即按编号顺序输出单链表中所有元素。
-
在程序的最后，你需要释放所有动态申请的内存。
本题提供代码模板，也欢迎直接从头开始写代码的选手。
输入描述
程序开始时，你需要读入一个数 $n$ 和一个有 $n$ 个数的数组；然后调用操作 0 进行初始化。接下来你会读入一个数 $m$ 表示操作个数。接下来 $m$ 行，每行第一个数为 $op$，表示操作类型。
- 如果 $op = 1$，表示当前操作为操作 1，接下来读入两个数 $i,x$，含义如上文所示；
- 如果 $op = 2$，表示当前操作为操作 2，接下来读入一个数 $i$，含义如上文所示；
- 如果 $op = 3$，表示当前操作为操作 3；
- 如果 $op = 4$，表示当前操作为操作 4，接下来读入一个数 $i$，含义如上文所示；
- 如果 $op = 5$，表示当前操作为操作 5。
在所有操作后，将会调用操作 6 来释放动态分配的内存。
输出描述
对于每一个操作 4 或操作 5，在屏幕上输出操作的答案。注意，每次操作 4 或操作 5 完成后，务必在输出后附带换行，以区分每个输出。具体参见样例输入输出。
输入样例
5
2 3 3 3 4
10
3
5
1 2 6
1 5 4
1 10 3
2 7
4 4
4 3
3
5
输出样例
3 2 3 3 4
3
6
2 3 3 6 4 3
数据范围及约定
$1 \leq n, m \leq 3000$，链表中的所有数在 int 范围内。
请务必使用单链表来完成本题！！助教将会人工判断你的代码是否使用单链表，若否则本题计 0 分。
你可以使用如下的代码模板，程序的大部分已帮你写好，你只需要填写 TODO 中的内容即可；当然，你也可以自己从头开始写代码。
```c++
include
include
using namespace std;
struct LinkList { // TODO: Define some variables of struct LinkList here. void Initialize(int *a, int n) { // TODO: use a[0 ... n-1] to initialize the link list. } void Insert(int i, int x) { // TODO: insert element x after i-th element. } void Delete(int i) { // TODO: delete element i } void EvenOddSwap() { // TODO: Swap the even-indexed element with the corresponding odd-indexed element. } void Query(int i) { // TODO: Print the value of the i-th element on the screen. } void QueryAll() { // TODO: Print the link list on the screen. } void ClearMemory() { // TODO: Clear the memory. } };
LinkList L;
int main() { ios :: sync_with_stdio(false); cin.tie(0); cout.tie(0);
int n, *a; cin >> n; a = new int [n]; for (int i = 0; i < n; ++ i) cin >> a[i]; L.Initialize(a, n); delete [] a;
int m, op, i, x; cin >> m; while(m --) { cin >> op; switch(op) { case 1: cin >> i >> x; L.Insert(i, x); break; case 2: cin >> i; L.Delete(i); break; case 3: L.EvenOddSwap(); break; case 4: cin >> i; L.Query(i); break; case 5: L.QueryAll(); break; } }
L.ClearMemory(); return 0; }
```
Oops! 本题目还没有解答！
助教老师们编题的速度，已经超过了解题的速度！
OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。
如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！