526互联

数组模拟双链表

发布时间 2023-03-22 21:11:18作者: 风乐

https://www.acwing.com/problem/content/829/
与数组模拟单链表相似
但是与之相比多一个l[N],r[N]用这两个向量表示每个结点的前驱和后继

初始状态:
令head为0,tail为1,初始就这两个点,开头和结尾

插入:

删除:



#include<iostream>

using namespace std;

const int N = 100010;

int k;
int m;
int e[N],l[N],r[N],idx,num;


void init()
{
	r[0]=1,l[1]=0;//指明head和tail的r与l
	idx=2;//0与1被head和tail占用了
}


void add(int k,int x)//下标为k的点右边插入点
//若要在k点左边插入,则add(l[k],x)即是在l[k]的右边插入点
{
	//新点
	e[idx]=x;//新点赋值
	r[idx]=r[k];//新点的r指针指向k点的右指针
	l[idx]=k;//新点l指针指向k
	//旧两端点
	l[r[k]]=idx;//设置右边旧点左指针指向新点
	r[k]=idx;//设置左边旧点又指针指向新点  
	idx++;
}

void remove(int k)//删除第k个点
{
	r[l[k]]=r[k];//设置k点的左点的右指针为k点的右点
	l[r[k]]=l[k];//设置k点的右点的左指针为k点的左点
}
int main()
{
	cin >> m;
	
	init();
	
	while(m--)
	{
		string cmd;
		int x;
		cin >> cmd;
		if(cmd == "L")
		{
			cin >> x;
			add(0,x);//0表示head,即在head的右端插入点为第一个点
		}
		else if(cmd == "R")
		{
			cin >> x;
			add(l[1],x);//1表示tail,在tail的左端插入点为最后一个点
		}
		else if(cmd == "D")
		{
			cin >> k;
			remove(k+1);//第k个点,因为idx从2开始分配,第1个点为2,第2个点为3,那么第k个点为下标为k+1
		}
		else if(cmd == "IL")
		{
			cin >> k >> x;
			add(l[k+1],x);//与D同理,k+1为第k个点idx下标,在k+1左段的点的右边插入点
		}
		else
		{
			cin >> k >> x;
			add(k+1,x);//在k的右侧插入点
		}
	}
	
	for(int i=r[0];i != 1;i=r[i]) cout << e[i] << ' ';
	cout << endl;
	return 0;
}