算法打卡：数组模拟单链表

一：模板题

2021/8/24 19:55

题目：

​

思路：

​

代码：

#include <iostream>
using namespace std;

const int N = 100010;

//head 记录头节点下标，e[N] 记录节点数值 ,ne[N] 记录节点next值 ,idx 模拟指针 记录当前正在使用的数组下标
int head, e[N], ne[N], idx; 

void init() // 初始化head 指向空为-1，已使用的数组下标为0
{
    head = -1;
    idx = 0;
}

void add_to_head(int x) //将x插入到头节点
{
    e[idx] = x; //当前idx下标对应的节点 数值赋为 x
    ne[idx] = head; // 当前idx下标对应的节点 的next 指向head 指向的数
    head = idx ++; //head 指向当前指针idx对应的节点， idx ++ 指向下一个待用的数组空间
}

void add(int k, int x)
{
    e[idx] = x;
    ne[idx] = ne[k]; //当前idx下标对应的节点 的next 指向 下标k 的next
    ne[k] = idx ++;  //下标k 的next 指向当前指针idx对应的节点， idx ++ 指向下一个待用的数组空间
}

void remove(int k)
{
    ne[k] = ne[ne[k]]; //k的next 指向 k的next的next； 也就是k指向它的后节点的后节点
}

int main()
{
    int m;
    scanf("%d", &m);
    
    init();
    
    while(m --)
    {
        char op;
        int k, x;
        
        cin >> op;
        
        if(op == 'H')
        {
            scanf("%d", &x);
            add_to_head(x);
        }
        else if(op == 'D')
        {
            scanf("%d", &k);
            if(!k) head = ne[head]; // 当k == 0 ，代表让head指向头结点的后一节点，特判一下
            else
            {
                remove(k - 1); //第k 个数 插入在 数组 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;
}