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了，可以的话，请您参考添加页面，与大家一起分享你的题解！