Skip to content

1379: A Secret Problem

题目

题目描述

根据ACM班的古老传统,第零次机考总有一道题是单链表,这次当然也不例外。

你需要实现一个单链表 $L$​​​ ,支持以下操作:(以下均为 1 - based )

  1. 在第 i 个数后面插入一个数 x 。
  2. 删除第 i 位的数。
  3. 将单链表的奇偶位相互交换,即,编号为 $2k-1$​​​ 和 $2k$​​​ 的元素交换。若单链表长度为奇数,则剩下的最后一个元素无需交换。你需要在原地进行该操作,也就是说,这个操作只能使用 $O(1)$​​​ 的额外空间。
  4. 将链表从第 i 位开始截断,丢弃后面的所有元素。保留第 i 个元素。注意释放内存
  5. 输出链表第 i 个数。
  6. 输出链表长度。
  7. 输出整个链表,使用空格隔开。

同时,在程序开始时,你应当先读入一个数组,以初始化此链表。

在程序结束后,你应当释放所有动态申请的内存。

我们提供代码模板,同时也欢迎全部自己完成代码。

```c++

include

using namespace std;

struct LinkedList { // todo: some variables here

void initialize() {
    int m;
    cin >> m;
    int *a = new int[m];
    for (int i = 0; i < m; i++) cin >> a[i];
    // todo

    delete[] a;
}

void insert(int i, int x) {
    // todo
}

void erase(int i) {
    // todo
}

void swap() {
    // todo
}

void cut(int i) {
    // todo
}

int query(int i) {
    // todo
}

int size() {
    // todo
}

void print() {
    // todo
}

void freeMemory() {
    // todo
}

};

int main() { LinkedList l; int n, op, i, x; l.initialize(); cin >> n; while (n--) { cin >> op; if (op == 0) { cin >> i >> x; l.insert(i, x); } else if (op == 1) { cin >> i; l.erase(i); } else if (op == 2) { l.swap(); } else if (op == 3) { cin >> i; l.cut(i); } else if (op == 4) { cin >> i; cout << l.query(i) << endl; } else if (op == 5) { cout << l.size() << endl; } else { l.print(); } } l.freeMemory(); return 0; } ```

但请注意,务必使用单链表来完成本题。助教会人工判断你的代码是否合法,若存在问题本题计零分。详细要求如下:

必须使用指针与结构体。

在单链表中,每个结点有一个数据元素和一个后继指针组成,后继指针指向存储该元素直接后继的结点。单链表只保存直接后继的关系

存储一个单链表只应该使用一个指向头结点的指针,并且你只应该定义一个链表类,不应该使用多个单链表完成本题。

可以使用单独的变量记录链表长度。

同时,此题需要你注意提交代码的代码风格。极为糟糕的代码风格(例如改变语法的某些宏定义)会酌情扣分。

输入格式

第一行一个自然数 $m$​ ,代表操作数。

第二行 $m$ 个整数,代表初始化数组。

第三行一个自然数 $n$​​ ,代表操作数。

接下来 $n$ 行每行第一个数为 $op$​ ,表示操作类型。

  • $op = 0$​​​,执行操作0,接下来读入两个整数 i,x,含义如上文。

  • $op = 1$​​​​,执行操作1,接下来读入一个整数 i,含义如上文。

  • $op = 2$​​​,执行操作2。

  • $op = 3$,执行操作3,接下来读入一个整数 i,含义如上文。

  • $op = 4$,执行操作4,接下来读入一个整数 i,含义如上文。

  • $op = 5$​​​,执行操作5。

输出格式

对于每个操作 3,4,5,一行输出操作的答案。(注意对于每一个操作,输出后需要换行

样例输入

``` 10 684 82 231 563 741 238 700 114 995 182 10 2 4 9 2 5 2 1 9 0 9 72 3 8 0 7 325 6

```

样例输出

182 10 82 684 563 231 238 741 114 325 700

数据范围

$1\leq m\leq1000$​

$1\leq n\leq10000$

保证每个链表元素均在int范围内。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!