Skip to content

14296: 【原4296】小可怜的双链表

题目

题目描述

author: 小可怜 原OJ链接:https://acm.sjtu.edu.cn/OnlineJudge-old/problem/4296

小可怜的双链表

Description

助教是个小可怜,因为她不知道要出什么机考题了。 然后她发现大家已经学完了指针和结构体,欣喜若狂。 她想让你写一个双链表。 你需要完成以下内容:(注意这里的i都为0-base

  • 0 返回链表长度

  • 1 在位置i插入一个数,注意这里是指插入的数在插入后处于位置i,即插入在现在位置i数字的前面。

  • 2 输出第x个数,如果x超出链表长度,请输出-1.

  • 3 删除位置i的数,整个链表长度--。

  • 4 输出整个list,如果表为空请输出-1。

  • 为防止内存泄漏,你需要在程序最后删除整个列表,此项,我们会通过检查你的代码来确定你是否完成。

要求如下:

  • 必须使用指针和结构体
  • 在双链表中,每个结点有一个数据元素、一个后继指针、一个前驱指针组成,后继指针指向存储该元素直接后继的结点,前驱指针指向存储该元素直接前驱的结点。
  • 存储一个单链表需要一个指向头结点的指针和一个指向尾结点的指针。
  • 可以使用单独的变量记录链表长度
  • 请严格按照以上要求完成此题。我们会检查你提交的代码。虽然有其他的实现方式,但如果你未按照要求写代码,我们不会给你分数。(比如,你没有使用指针和结构体或在每个结点中记录了要求以外的内容等等都会判为0分)。
  • 请不要修改给定的部分。
  • 同时,此题需要你注意提交代码的代码风格!!!极为糟糕的代码风格(例如改变语法的某些宏定义)会酌情扣分!!!

Input Format

第一行一个$n$表示操作数 之后$n$行每行第一个数$op$代表操作编号,分别对应前文中的编号。 如果$op$为$1$,其后会输入两个整数$p,x$,表示在$p$位置插入的数值为$x$ 如果$op$为$2$,其后会输入一个整数$p$,表示你需要输出链表中$p$位置的值,输出要求见上。

(数据保证插入删除操作不会操作无效位置。)

Output Format

对于操作1,3,你不用输出任何东西。 对于操作0,输出一个整数,表示链表长度。 对于操作2,输出一个整数,表示第x个数。 对于操作4,按链表顺序输出一行整数。

SAMPLE INPUT

16
0
1 0 1
1 0 2
1 2 3
4
2 1
1 2 4
4
3 2
4
1 0 5
2 3
2 4
3 0
4
0

SAMPLE OUTPUT

0
2 1 3
1
2 1 4 3
2 1 3
3
-1
2 1 3
3

DATA LIMIT

$n \leq 1000$, 保证链表中所有数字为int范围内正整数。 保证所给部分和所给要求不会产生超时问题。

Hint

测试点编号 | 包含操作号|
-|-| 1 | 0、1 | 2 | 1、2、4 | 3 | 1、3、4 | 4 | all | 5 | all |

本题只有一次提交机会!!!

sample.cpp

#include <iostream>
#include <cstdio>
using namespace std;

namespace LIST
{

struct NODE
{
    // TODO
};

NODE *head = nullptr, *tail = nullptr;
int len = 0;

void Pre()
{
    // TODO
}
NODE* move(int i)
{
    // TODO
}
void insert(int i, int x)
{
    // TODO
}
void remove(int i)
{
    // TODO
}
int Get_length()
{
    // TODO
}
int Query(int i)
{
    // TODO
}

void Print()
{
    // TODO
}

void Clear()
{
    // TODO
}

}
int n;
int main()
{
    cin >> n;
    int op, x, p, ans;
    LIST::Pre();
    for (int _=0;_<n;++_)
    {
        cin >> op;
        switch(op)
        {
            case 0:
                ans = LIST::Get_length();
                cout << ans << endl;
                break;
            case 1:
                cin >> p >> x;
                LIST::insert(p,x);
                break;
            case 2:
                cin >> p;
                ans = LIST::Query(p);
                cout << ans << endl;
                break;
            case 3:
                cin >> p;
                LIST::remove(p);
                break;
            case 4:
                LIST::Print();
                break;
        }
    }
    LIST::Clear();
    return 0;
}

Oops! 本题目还没有解答!

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

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

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