数据结构

28 0 0

数组模拟单链表

#include <iostream>

using namespace std;

const int N = 1e5+10;

int val[N];
int ptr[N]={-1};
int now=0,head=-1;

void add_node()
{
    cin>>val[now];
    ptr[now]=head;
    head=now++;
}

void delete_node()
{
    int k;
    cin>>k;
    if(k==0)
    {
        head=ptr[head];
    }
    else
    {
        ptr[k-1]=ptr[ptr[k-1]];
        
    }
}

void insert_node()
{
    int n,m;
    cin>>n>>m;
    val[now]=m;
    ptr[now]=ptr[n-1];
    ptr[n-1]=now++;
}

int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char a;
        cin>>a;
        switch(a)
        {
            case 'H':add_node();break;
            case 'D':delete_node();break;
            case 'I':insert_node();break;
        }
    }
    int i=head;

    while(i!=-1)
    {
        printf("%d ",val[i]);
        i=ptr[i];
    }

    return 0;
}

数组模拟双链表

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

const int N = 1e5+10;

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

void init()
{
    l[1]=0;
    r[0]=1;
    idx=2;
}
//L x，表示在链表的最左端插入数 x
void add_start()
{
    cin>>val[idx];
    l[r[0]]=idx;
    r[idx]=r[0];
    l[idx]=0;
    r[0]=idx++;
}
//R x，表示在链表的最右端插入数 x
void add_end()
{
    cin>>val[idx];
    r[l[1]]=idx;
    l[idx]=l[1];
    r[idx]=1;
    l[1]=idx++;
}
//D k，表示将第 k个插入的数删除
void delete_data()
{
    int n;
    scanf("%d",&n);
    r[l[n+1]]=r[n+1];
    l[r[n+1]]=l[n+1];
}
//IR k x，表示在第 k 个插入的数右侧插入一个数。
void insert_right()
{
    int index,value;
    scanf("%d%d",&index,&value);
    val[idx]=value;
    l[r[index+1]]=idx;
    l[idx]=index+1;
    
    r[idx]=r[index+1];
    r[index+1]=idx;
    idx++;
}
//IL k x，表示在第 k 个插入的数左侧插入一个数。
void insert_left()
{
    int index,value;
    scanf("%d%d",&index,&value);
    val[idx]=value;
    r[idx]=r[l[index+1]];
    r[l[index+1]]=idx;
    
    l[idx]=l[index+1];
    l[index+1]=idx;
    idx++;
}

int main()
{
    init();
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string a;
        cin>>a;

        if(a=="R") add_end();
        else if(a=="L") add_start();
        else if(a=="D") delete_data();
        else if(a=="IL") insert_left();
        else if(a=="IR") insert_right();
    }

    for(int i=r[0];i!=1;i=r[i]) printf("%d ",val[i]);
    return 0;
}

数组模拟栈

#include <iostream>
#include <string>

using namespace std;

const int N = 1E5+10;
int ary[N],top;

void init()
{
    top=0;
}

void push()
{
    scanf("%d",&ary[top++]);
}

void query()
{
    printf("%d\n",ary[top-1]);
}

void empty()
{
    if(top!=0) printf("NO\n");
    else printf("YES\n");
}

void pop()
{
    top--;    
}

int main()
{
    init();
    
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
        string a;
        cin>>a;
        if(a=="push") push();
        else if(a=="query") query();
        else if(a=="pop") pop();
        else empty();
    }

    return 0;
}

# 算法