首页 > 其他分享 >数据结构(二)双链表---以题为例

数据结构(二)双链表---以题为例

时间:2024-03-17 12:12:41浏览次数:35  
标签:链表 idx int cin --- 插入 双链 数据结构 op

实现一个双链表,双链表初始为空,支持 5 种操作:

  1. 在最左侧插入一个数;
  2. 在最右侧插入一个数;
  3. 将第 k 个插入的数删除;
  4. 在第 k 个插入的数左侧插入一个数;
  5. 在第 k 个插入的数右侧插入一个数

现在要对该链表进行 M 次操作,进行完所有操作后,从左到右输出整个链表。

注意:题目中第 k 个插入的数并不是指当前链表的第 k 个数。例如操作过程中一共插入了 n 个数,则按照插入的时间顺序,这 n 个数依次为:第 1个插入的数,第 2个插入的数,…第 n 个插入的数。

输入格式

第一行包含整数 M,表示操作次数。

接下来 M 行,每行包含一个操作命令,操作命令可能为以下几种:

  1. L x,表示在链表的最左端插入数 x。
  2. R x,表示在链表的最右端插入数 x。
  3. D k,表示将第 k 个插入的数删除。
  4. IL k x,表示在第 k 个插入的数左侧插入一个数。
  5. IR k x,表示在第 k 个插入的数右侧插入一个数。

输出格式

共一行,将整个链表从左到右输出。

数据范围

1≤M≤100000
所有操作保证合法。

输入样例:

10
R 7
D 1
L 3
IL 2 10
D 3
IL 2 7
L 8
R 9
IL 4 7
IR 2 2

输出样例:

8 7 7 3 2 9
#include<iostream>
using namespace std;

const int N =1000010;

int e[N],l[N],r[N],idx;

void init(){
    l[1]=0,r[0]=1;
    idx =2;
}

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

void remove(int k){
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}

int main(){
    int m;
    cin>>m;
    init();
    while(m--){
        string op;
        int k,x;
        cin>>op;
        
        if(op == "L"){
            cin>>x;
            add(0,x);
        }
        else if(op == "R"){
            cin>>x;
            add(l[1],x);
        }
        else if(op == "D"){
            cin>>k;
            remove(k+1);
        }
        else if(op == "IL"){
            cin>>k>>x;
            add(l[k+1],x);
        }
        else if(op == "IR"){
            cin>>k>>x;
            add(k+1,x);
        }
    }
    for(int i = r[0];i!=1;i=r[i]) cout<<e[i]<<" ";
    return 0;
}

 

标签:链表,idx,int,cin,---,插入,双链,数据结构,op
From: https://www.cnblogs.com/Ghost-Knight/p/18078404

相关文章

  • 本地部署 Langchain-Chatchat & ChatGLM
     一、模型&环境介绍#1.ChatGLM#github地址:https://github.com/THUDM模型地址:https://huggingface.co/THUDM2.m3e#模型地址:https://huggingface.co/moka-ai/m3e-base/3.text2vec#模型地址:https://huggingface.co/GanymedeNil/text2vec-large-chinese/4.Lang......
  • 基于减法平均算法改进的随机森林分类算法 - 附代码
    基于减法平均算法改进的随机森林分类算法-附代码文章目录基于减法平均算法改进的随机森林分类算法-附代码1.数据集2.RF模型3.基于减法平均算法优化的RF4.测试结果5.Matlab代码摘要:为了提高随机森林数据的分类预测准确率,对随机森林中的树木个数和最小叶子点数参......
  • Arthas - Can not read arthas version from: https://arthas.aliyun.com/api/latest_
    问题描述[ERROR]Cannotreadarthasversionfrom: https://arthas.aliyun.com/api/latest_version[ERROR]CannotfindArthasunderlocal:/root/.arthas/libandremoterepomirror:aliyun[ERROR]Unabletodownloadarthasfromremoteserver,pleasedownload......
  • LeetCode精选101刷题必备(C++)-附详细分类及解体说明
    分享一本leetcode刷题必备,互联网就业必备的免费书,非常好,值得推荐。感谢作者高畅无私整理和免费分享。本书介绍    本书分为算法和数据结构两大部分,又细分了十五个章节,详细讲解了刷LeetCode时常用的技巧。我把题目精简到了101道,一是呼应了本书的标题,二是不想让读......
  • 沃伦·巴菲特2023股东书(2024.2.24)-0-查理·芒格——伯克希尔·哈撒韦公司的建筑师
    2023letterhttps://www.berkshirehathaway.com/letters/2023ltr.pdf查理·芒格——伯克希尔·哈撒韦公司的建筑师查理·芒格于11月28日去世,距离他100岁生日仅33天。虽然在奥马哈出生和长大,但他一生中80%的时间都在其他地方定居。因此,直到1959年他35岁时,我才第一次......
  • 探索设计模式的魅力:探索发布-订阅模式的深度奥秘-实现高效、解耦的系统通信
    ​......
  • opencv读取视频采集卡帧-调整分辨率
    VideoCapturecapture;capture.open(0,CAP_DSHOW); capture.set(CAP_PROP_FRAME_WIDTH,1920); capture.set(CAP_PROP_FRAME_HEIGHT,1080); MatmatFrame; capture.read(matFrame); capture.release();imshow("ShowFrame",matFrame);1-......
  • AtCoder-abc345_f题解
    题意简述给定一个无向图。你要在其中选出一些边,使得选出的边所构成的图中,度数为奇数的点有\(K\)个。如果可以,输出选了哪些边,否则输出-1。思路首先在选一条边时,边两端点度数的奇偶性一定都会改变,即要么都变为奇数,要么两个点的奇偶性交换过来,要么都变为偶数。这三种情况时满足......
  • Harris/Shi-Tomasi角点检测
    机器视觉——角点检测什么是角点检测在几何学里,我们会看到各种各样的三角形、多边形等,它们都有一个显著的特征:包含了角点信息。比如在三角形里,我们有三个角;在矩形里,我们有四个角。我们将找到这些图像特征的过程称为特征提取(FeatureExtraction),我们之前所接触的Canny边缘检测......
  • 每日一练:LeeCode-125、验证回文串【字符串+双指针】
    如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个回文串。字母和数字都属于字母数字字符。给你一个字符串s,如果它是回文串,返回true;否则,返回false。示例1:输入:s="Aman,aplan,acana......