Skip to content

14351: 【原4351】linklist

题目

题目描述

author: galaxies 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4351

题目描述

众所周知,第 0 次机考总有一道题是单链表,这次也不例外。

你需要实现一个单链表 $L$,一些需要实现的操作如下:

  1. 利用数组初始化该单链表,该操作只会在初始时被调用 1 次;

  2. 在单链表第 $i$ 个元素后插入元素 $x$。特别地,如果 $i = 0$,则表示在表头插入元素;如果 $i = |L|$,则表示在表尾插入元素;如果出现除 $0 \leq i \leq |L|$ 之外的其他情况,无视当前操作

注意:元素从 1 开始编号

  1. 删除单链表的第 $i$ 个元素。特别地,如果出现除 $1 \leq i \leq |L|$ 之外的其他情况,无视当前操作

  2. 将单链表奇偶交换,也就是说原来编号为 $2k$ 的元素与原来编号为 $2k - 1$ 的元素交换。如果单链表长度为奇数,则剩下的最后一个元素不需要进行交换;你需要在原地进行该操作,也就是说,这个操作只能使用 $O(1)$ 的额外空间;

  3. 询问单链表的第 $i$ 个元素。特别地,保证不会出现除 $1 \leq i \leq |L|$ 之外的其他情况。

  4. 询问整个单链表,即按编号顺序输出单链表中所有元素。

  5. 在程序的最后,你需要释放所有动态申请的内存。

本题提供代码模板,也欢迎直接从头开始写代码的选手。

输入描述

程序开始时,你需要读入一个数 $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了,可以的话,请您参考添加页面,与大家一起分享你的题解!