2024-06-04发表2024-06-27更新8 分钟读完 (大约1172个字)0次访问

单链表

题目：单链表的基本操作

题目描述

实现一个单链表，并支持以下三种操作：

将一个元素插入到链表的头部。
将一个元素插入到链表中指定元素的后面。
删除链表中指定元素的后一个元素。

链表初始为空。每个操作保证合法，且不会删除链表中不存在的元素。

输入格式

第一行包含一个整数 m，表示操作的次数。

接下来 m 行，每行包含一个操作指令，具体形式如下：

H x：将整数 x 插入到链表的头部。
D k：删除链表中第 k 个元素的后一个元素（k 从 1 开始）。
I k x：将整数 x 插入到链表中第 k 个元素的后面（k 从 1 开始）。

输出格式

输出一行，表示最终链表中的所有元素，按顺序用空格隔开。

输入输出示例

示例1

输入

输出

2 4 3

示例2

输入

输出

20 10

题目分析

我们使用一个数组 e 存储链表的元素，数组 ne 存储每个节点的下一个节点的下标。head 存储链表头部节点的下标，idx 表示当前插入元素的下标。具体实现包括初始化链表、在头部插入元素、在指定位置插入元素，以及删除指定位置后的元素。

通过解析输入的操作指令，我们对链表进行相应的操作，最终输出链表中的所有元素。
这段代码实现了一个简单的单链表操作，包括在头部插入节点、在某个节点后插入节点、删除某个节点后的节点以及遍历链表。

代码解释

定义常量和变量：
1
2
const int N = 100010;
int head, e[N], ne[N], idx;
- N 是数组的最大大小。
- head 是链表的头指针。
- e 数组存储节点的值。
- ne 数组存储每个节点的下一个节点的索引。
- idx 是当前节点的索引。
初始化函数：
1
2
3
4
void init() {
head = -1;
idx = 0;
}
初始化链表，将 head 设为 -1 表示链表为空，idx 设为 0。

在头部插入节点：

void add_to_head(int x) {
    e[idx] = x;
    ne[idx] = head;
    head = idx;
    idx++;
}

将值 x 插入到头部节点，更新头指针和 idx。

在节点 k 后插入节点：

void add(int k, int x) {
    e[idx] = x;
    ne[idx] = ne[k];
    ne[k] = idx;
    idx++;
}

在节点 k 后插入值 x 的新节点。

删除节点 k 后的节点：
1
2
3
void remove(int k) {
ne[k] = ne[ne[k]];
}
删除节点 k 后的节点。

主函数：

int main() {
    int m;
    cin >> m;
    init();
    while (m--) {
        int k, x;
        char op;
        cin >> op;
        if (op == 'H') {
            cin >> x;
            add_to_head(x);
        } else if (op == 'D') {
            cin >> k;
            if (!k) head = ne[head];
            remove(k - 1);
        } else {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
    return 0;
}

读取操作数量 m。
初始化链表。
循环处理每个操作，根据操作类型执行相应的链表操作。
最后遍历并输出链表中的所有节点值。

处理流程示例

假设输入如下：

5
H 3
H 2
I 1 4
D 2
H 1

输入解释

第1行：5 表示有5个操作。
第2行：H 3 在头部插入值为3的节点。
第3行：H 2 在头部插入值为2的节点。
第4行：I 1 4 在第1个节点后插入值为4的节点。
第5行：D 2 删除第2个节点后的节点。
第6行：H 1 在头部插入值为1的节点。

按照代码处理流程

初始化链表：
1
2
head = -1;
idx = 0;
执行操作：
- 操作 H 3：
  1
  add_to_head(3);
  更新后 e = [3]，ne = [-1]，head = 0，idx = 1。
- 操作 H 2：
  1
  add_to_head(2);
  更新后 e = [3, 2]，ne = [-1, 0]，head = 1，idx = 2。
- 操作 I 1 4：
  1
  add(0, 4);
  更新后 e = [3, 2, 4]，ne = [2, 0, -1]，head = 1，idx = 3。
- 操作 D 2：
  1
  remove(1);
  更新后 ne = [2, -1, -1]。
- 操作 H 1：
  1
  add_to_head(1);
  更新后 e = [3, 2, 4, 1]，ne = [2, -1, -1, 1]，head = 3，idx = 4。
遍历并输出链表：
1
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
从头指针 head = 3 开始遍历，输出结果为：
1
1 2

总结

通过这个例子，可以看到如何按照输入操作动态地更新链表，并最终输出链表的内容。每个操作都按照代码中的逻辑逐步进行，链表结构在每一步都进行了相应的更新和调整。

单链表

https://mr-xiongyq.github.io/2024/06/04/单链表/

作者

Xiongyuqi

发布于

2024-06-04

更新于

2024-06-27

许可协议

#数据结构

单链表