题目描述

链表是数据结构中一种最基本的链式存储线性表，相较于顺序表，其插入和删除操作无需移动后续元素。本题需要你根据输入的初始化序列和一系列操作指令，完成链表的对应操作，并输出指定结果。

参考算法示例

题目提供的单链表操作参考实现如下：

#include <bits/stdc++.h>
using namespace std;

struct node{
    int data; // 节点存储的数据
    node *next; // 指向后继节点的指针
};

// 在index节点后插入值为x的新节点
void insert(node *index, int x){
    node *temp = new node; // 申请新节点内存
    temp->data = x; // 赋值新节点数据
    temp->next = index->next; // 新节点后继指向原index的后继
    index->next = temp; // index的后继指向新节点
}

// 输出从index开始的所有节点数据
void output(node *index){
    while(index != NULL){ // 遍历直到链表末尾
        cout << index->data << " ";
        index = index->next;
    }
    cout << endl;
}

// 查找数据域为num的节点的前驱节点
node* find_above(node *index, int num){
    while(index->next != NULL){ // 遍历到倒数第一个节点为止
        if(index->next->data == num){ // 后继节点数据匹配
            return index; // 返回前驱节点
        }
        index = index->next;
    }
    return NULL; // 未找到匹配节点
}

// 删除数据域为num的节点
void erase(node *front, int num){
    node *above = find_above(front, num); // 查找待删节点的前驱
    if(above == NULL) return; // 未找到待删节点，直接返回
    node *temp = above->next; // 临时存储待删节点地址
    above->next = above->next->next; // 前驱节点后继跳转到待删节点的后继
    delete temp; // 释放待删节点内存
}

// 将数据域为num1的节点修改为num2
void edit(node *front, int num1, int num2){
    node *above = find_above(front, num1); // 查找待修改节点的前驱
    if(above == NULL) return; // 未找到待修改节点，直接返回
    above->next->data = num2; // 修改节点数据
}

int main(){
    node* front = new node; // 申请头节点
    front->next = NULL; // 头节点后继初始化为空
    node* index = front; // 遍历指针初始指向头节点
    // 示例：插入10个节点
    for(int i = 1; i <= 10; i++){
        insert(index, i);
        index = index->next;
    }
    output(front->next); // 输出链表

    int num1, num2, num;
    // 示例删除操作
    cin >> num;
    erase(front, num);
    output(front->next);

    // 示例修改操作
    cin >> num1 >> num2;
    edit(front, num1, num2);
    output(front->next);

    // 示例插入操作：在num1节点后插入num2
    cin >> num1 >> num2;
    node *above = find_above(front, num1);
    if(above != NULL){
        insert(above->next, num2);
    }
    output(front->next);

    return 0;
}

注意：上述示例为按值操作的实现，本题要求实现按位置的增删查操作。

输入描述

输入数据只有一组：

1. 第一行有n+1个整数，第一个整数为n，后续为n个整数，用于初始化链表。注意：输入顺序与链表实际存储顺序相反，例如链表顺序为1、2、3时，输入顺序为3、2、1。
2. 第二行有一个整数m，代表后续有m行操作指令。
3. 每行指令为以下四种之一：
   • get a：获取并输出链表中第a个元素
   • delete a：删除链表中第a个元素
   • insert a e：在第a个位置前插入元素e
   • show：输出当前链表的所有元素

输出描述

根据不同操作输出对应结果：

• get操作：获取成功输出对应元素，失败输出get fail
• delete操作：删除成功输出delete OK，失败输出delete fail
• insert操作：插入成功输出insert OK，失败输出insert fail
• show操作：链表非空时输出所有元素（空格分隔），为空时输出Link list is empty

输入样例1

3 3 2 1
21
show
delete 1
show
delete 2
show
delete 1
show
delete 2
insert 2 5
show
insert 1 5
show
insert 1 7
show
insert 2 5
show
insert 3 6
show
insert 1 8
show
get 2

输出样例1

1 2 3
delete OK
2 3
delete OK
2
delete OK
Link list is empty
delete fail
insert fail
Link list is empty
insert OK
5
insert OK
7 5
insert OK
7 5 5
insert OK
7 5 6 5
insert OK
8 7 5 6 5
7

提示

1. 本题插入和删除操作频繁，必须使用链表实现，否则可能超时。
2. 初始化链表时输入顺序与存储顺序相反，使用头插法即可实现。

总结

本题考查链表的特性与适用场景：顺序表适合随机访问频繁的场景，链表适合插入、删除操作频繁的场景。