数组模拟单链表C++

2362471311mars / 2024-02-08 / 原文

（萌新第一次来文章）
数组模拟单链表
注意事项:
全局定义

const int N=100010;
int head=-1;//头指针
int idx=0;//当前位置
int e[N],ne[N]//e表示值，ne表示next

1.头插法

void add_to_head(int  n)
{
   e[idx]=n;
  ne[idx]=head;
  head=idx++;
}

2.删除操作

void Delete(int n)
{
   ne[n]=ne[ne[n]];
}

3插入操作

void Insert(int k,int f)
{
  e[idx]=f;
  ne[idx]=ne[k];
  ne[k]=ne[idx];
}

具体对应体型AcWing826.单链表：[https://www.acwing.com/problem/content/828/]
实现代码：

#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
const int N=100010;
int head=-1, idx=0;
//e存储数据，ne存储指针
int ne[N],e[N];
//头插法建立链表
void H(int n)
{
    e[idx]=n;
    ne[idx]=head;
    head=idx;
    idx++;
}
//删除第k个插入的数后面的数
void Delete(int n)
{
    ne[n]=ne[ne[n]];//可以类比指针实现链表中的n->next=n->next->next;

}
void Insert(int k,int f)//在第k个后面插入一个f
{
    e[idx]=f;
    ne[idx]=ne[k];
    ne[k]=idx++;
}
void Cout()
{
    for(int i=head;i!=-1;i=ne[i])
    {
        cout<<e[i]<<" ";
    }
}
int main()
{
    int n;
    cin>>n;
    while(n--)
    {
        char n1;
        cin>>n1;
        if(n1=='H')
        {
            int num;
            cin>>num;
            H(num);
        }
        if(n1=='D')
        {
            int num;
            cin>>num; 
            if (!num) head=ne[head];
            else 
            Delete(num-1);
        }
        if(n1=='I')
        {
            int k,f;
            cin>>k>>f;
           Insert(k-1,f);
        }
    }
    Cout();
    cout<<endl;
    return 0;
}

值得需要注意的是，在删除操作中，当输入为0的时候，链表全部清零，所以要分类讨论