AcWing 826. 单链表-JAVA(注释)
原题链接
简单
作者:
鼠鼠我
,
2021-01-28 20:55:24
,
所有人可见
,
阅读 341
package 第三章搜索与图论;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
public class 单链表数组模拟 {
//数组实现模拟单链表,效率更快
//单链表:邻接表:存储图和树
//双链表:优化某些问题
static int head;//表示头结点的下标
static int idx;//当前下标,初始是0,第一个插入的点是0,其次是1,然后2,3,4...
static int N = 100010;
static int[] e;//表示结点下标为idx的值
static int[] ne;//表示下标为idx+1的idx值,就是当前结点的下一个指针的idx值
public static void main(String[] args) throws IOException {
// TODO Auto-generated method stub
init();
e = new int[N];
ne = new int[N];
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String s[] = br.readLine().split("\\s+");
int m = Integer.parseInt(s[0]);
while(m-- >0)
{
String ss[] = br.readLine().split("\\s+");
if(ss[0].equals("H"))//在头结点插入
{
int x = Integer.parseInt(ss[1]);
head_add(x);
}
else if(ss[0].equals("D"))
//删除操作,删除第k个插入的数后面的数(当k为0时,表示删除头结点)
//第k个的下标是k-1,所以将k-1后面的后面的数删掉
{
int k = Integer.parseInt(ss[1]);
if(k==0)//k为0,删除头结点
{
head = ne[head];
}
else {
remove(k-1);
}
}
else if(ss[0].equals("I"))//普通插入
{
int k = Integer.parseInt(ss[1]);
int x = Integer.parseInt(ss[2]);
//表示在第k个插入的数后面插入一个数x(此操作中k均大于0)
//第k个插入的数的下标是k-1,所以插入到下标为k-1结点的后面
add(k-1, x);
}
}
for(int i=head;i!=-1;i=ne[i])//遍历
{
System.out.print(e[i]+" ");
}
}
static void init()//初始化
{
head = -1;
idx = 0;
}
//将x插到到头结点
static void head_add(int x)
{
e[idx] = x;//当前的值为x
ne[idx] = head;//当前的下标的next指向head的下标(head的值是指向下一个的下标)
head = idx++;//head指向当前的下标
}
//将x插到下标是第k个输入的数的点的后面的点
static void add(int k,int x)
{
e[idx] = x;//当前值是x
ne[idx] = ne[k];//把当前下标的next值指向k点后面点的下标
ne[k] = idx++;//k的下标的next指向当前的下标
}
static void remove(int k)//将下标是k点的后面的点删掉
{
ne[k] = ne[ne[k]];
}
}