AcWing 22. 单链表
原题链接
简单
作者:
第一次的约会
,
2023-11-12 18:27:25
,
所有人可见
,
阅读 46
静态数组模拟单链表
#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 1e6 + 10;
int head;//存储当前头结点的下标(因为使用的头插法,所以要记录每次头插法后的头结点下标)
int e[N], ne[N];//分别存储值和对应的下一个数组元素的下标
int idx;//当前可用的数组下标(因为是按着顺序存储数组下标的,idx之前的数组下标都已被用了)
void init()
{
head = -1;
idx = 0;
}
//头插法
void add_to_head(int x)
{
e[idx] = x;
ne[idx] = head;//接在上一个头结点的前面变成新的头结点
head = idx;//更新现在存储的头结点下标
idx++;//更新新的可用的数组下标
}
//在第k个数后面插入
void add(int k, int x)
{
e[idx] = x;
ne[idx] = ne[k];//第k个数的下标为k-1
ne[k] = idx;
idx++;
}
//删除第k个数后面的数
void remove(int k)
{
if (k == -1)
head = ne[head];
else
ne[k] = ne[ne[k]];
}
void show()
{
int i = head;
while (i != -1)
{
printf("%d ", e[i]);
i = ne[i];
}
}
int main()
{
int m;
cin >> m;
init();
while (m--)
{
int k, x;
char op;
cin>>op;// scanf("%c",&op);读取字符串时最好不要用scanf,因为会将空格一起读入
if (op == 'H')
{
cin >> x;
add_to_head(x);
}
else if (op == 'D')
{
cin >> k;
remove(k - 1);
}
else
{
cin >> k >> x;
add(k - 1, x);
}
}
show();
return 0;
}