ACM算法训练【单链表双链表的数组实现方法】

简介: ACM算法训练【单链表双链表的数组实现方法】


1.单链表


题目概述


44f7f266c486486a8d83a1dfb61acb90.png


输入样例:


10
H 9
I 1 1
D 1
D 0
H 6
I 3 6
I 4 5
I 4 5
I 3 4
D 6


输出样例:


6 4 6 5


思路


单链表的存储结构

2c9f5830b263414199d4759fffdecb41.png


链表插入操作:


63757aa69efe4bc99bd42ea4d26941d9.png


链表删除操作:


3f473730305f49bfb6c25c5fa79e2f53.png


代码奉上


#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int e[N],ne[N],idx,head=-1;
void removepo(int k)  //删除节点
{
    ne[k]=ne[ne[k]];
}
void add_to_head(int x)  //在头节点插入数据
{
    e[idx]=x;
    ne[idx]=head;
    head=idx++;
}
void add(int k,int x)  //普通插入
{
    e[idx]=x;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        int k,x;
        string op;
        cin>>op;
        if(op=="H")
        {
            scanf("%d",&x);
            add_to_head(x);
        }
        else if(op=="D")
        {
            scanf("%d",&k);
            if(k==0) head=ne[head];  //头节点特判
            else removepo(k-1);
        }
        else
        {
            scanf("%d%d",&k,&x);
            add(k-1,x);
        }
    }
    for(int i=head;i!=-1;i=ne[i])
        printf("%d ",e[i]);
    return 0;
}


2.双链表


题目概述


748a47f54f4e4461a6191d4126aa8160.png


数据范围


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


思路


类似单链表
初始化时偷懒,0表示头节点,1表示尾节点


a932e4ae84024df881830db947c6e555.png


删除操作:


9a60a8fb2f6649caa841e9814f9acc19.png


代码奉上


#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
int l[N],r[N],e[N],idx;
void init()
{
    r[0]=1;
    l[1]=0;
    idx=2;
}
void removepo(int k)
{
    r[l[k]]=r[k];
    l[r[k]]=l[k];
}
void add(int k,int x)
{
    e[idx]=x;
    r[idx]=r[k];
    l[idx]=k;
    l[r[k]]=idx;
    r[k]=idx++;
}
int main()
{
    init();
    int n;
    cin>>n;
    while(n--)
    {
        string m;
        int k,x;
        cin>>m;
        if(m=="L")
        {
            scanf("%d",&x);
            add(0,x);
        }
        else if(m=="R")
        {
            scanf("%d",&x);
            add(l[1],x);
        }
        else if(m=="D")
        {
            scanf("%d",&k);
            removepo(k+1);
        }
        else if(m=="IL")
        {
            scanf("%d%d",&k,&x);
            add(l[k+1],x);
        }
        else
        {
            scanf("%d%d",&k,&x);
            add(k+1,x);
        }
    }
    for(int i=r[0];i!=1;i=r[i])
        printf("%d ",e[i]);
    return 0;
}
目录
相关文章
|
6天前
|
存储 机器学习/深度学习 算法
C 408—《数据结构》算法题基础篇—链表(下)
408考研——《数据结构》算法题基础篇之链表(下)。
70 29
|
6天前
|
存储 算法 C语言
C 408—《数据结构》算法题基础篇—链表(上)
408考研——《数据结构》算法题基础篇之链表(上)。
59 25
|
6天前
|
存储 人工智能 算法
C 408—《数据结构》算法题基础篇—数组(通俗易懂)
408考研——《数据结构》算法题基础篇之数组。(408算法题的入门)
53 23
|
3月前
|
分布式计算 Java 开发工具
阿里云MaxCompute-XGBoost on Spark 极限梯度提升算法的分布式训练与模型持久化oss的实现与代码浅析
本文介绍了XGBoost在MaxCompute+OSS架构下模型持久化遇到的问题及其解决方案。首先简要介绍了XGBoost的特点和应用场景,随后详细描述了客户在将XGBoost on Spark任务从HDFS迁移到OSS时遇到的异常情况。通过分析异常堆栈和源代码,发现使用的`nativeBooster.saveModel`方法不支持OSS路径,而使用`write.overwrite().save`方法则能成功保存模型。最后提供了完整的Scala代码示例、Maven配置和提交命令,帮助用户顺利迁移模型存储路径。
|
3月前
|
算法 安全 搜索推荐
2024重生之回溯数据结构与算法系列学习之单双链表精题详解(9)【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构王道第2.3章之IKUN和I原达人之数据结构与算法系列学习x单双链表精题详解、数据结构、C++、排序算法、java、动态规划你个小黑子;这都学不会;能不能不要给我家鸽鸽丢脸啊~除了会黑我家鸽鸽还会干嘛?!!!
|
3月前
|
存储 Web App开发 算法
2024重生之回溯数据结构与算法系列学习之单双链表【无论是王道考研人还是IKUN都能包会的;不然别给我家鸽鸽丢脸好嘛?】
数据结构之单双链表按位、值查找;[前后]插入;删除指定节点;求表长、静态链表等代码及具体思路详解步骤;举例说明、注意点及常见报错问题所对应的解决方法
|
4月前
|
存储 缓存 算法
经典算法之链表篇(三)
经典算法之链表篇(三)
103 4
|
4月前
|
存储 Java
HashMap之链表转红黑树(树化 )-treefyBin方法源码解读(所有涉及到的方法均有详细解读,欢迎指正)
本文详细解析了Java HashMap中链表转红黑树的机制,包括树化条件(链表长度达8且数组长度≥64)及转换流程,确保高效处理大量数据。
154 1
|
23天前
|
算法 数据安全/隐私保护 计算机视觉
基于Retinex算法的图像去雾matlab仿真
本项目展示了基于Retinex算法的图像去雾技术。完整程序运行效果无水印,使用Matlab2022a开发。核心代码包含详细中文注释和操作步骤视频。Retinex理论由Edwin Land提出,旨在分离图像的光照和反射分量,增强图像对比度、颜色和细节,尤其在雾天条件下表现优异,有效解决图像去雾问题。
|
23天前
|
算法 数据可视化 安全
基于DWA优化算法的机器人路径规划matlab仿真
本项目基于DWA优化算法实现机器人路径规划的MATLAB仿真,适用于动态环境下的自主导航。使用MATLAB2022A版本运行,展示路径规划和预测结果。核心代码通过散点图和轨迹图可视化路径点及预测路径。DWA算法通过定义速度空间、采样候选动作并评估其优劣(目标方向性、障碍物距离、速度一致性),实时调整机器人运动参数,确保安全避障并接近目标。
126 68