如有不同观点,请大佬指正
数组模拟链表有几个参数工具需要解释一下是干什么用的,能更好的理解数组模拟链表的内部思想
1.int e[N];int el[N];int er[N];
首当其冲的就是这三个数组,它相当于是模拟计算机内部储存,其中下标表示这段空间的地址,这一大块空间分为三块,一块就是e[N],它用来存储这个节点的数值,第二块就是el[N],他是用来存放左节点的地址的,第三块就是el[N],他是用来存放右节点的地址的。正常这里用一个结构体来写,但是这里为了方便,便用三个数组模拟,达到了同样的效果。其实他们三个应该在一起的。
2.int idx;
然后就是idx了,他是用来模拟分配地址的,你可以认为他就是地址,每存一个节点就更新一次节点,删一个节点就不管了,正常来说应该把正在用的地址标记起来,然后删除的时候,接触标记的,但是为了偷懒,就不管了,直接让idx从2开始,每次更新就加一。为什么从2开始,因为偷懒把头节点和尾节点也放在这里了头节点为0,尾节点为1。
知道了这些后可以结合下方代码观看,应该很容易就能看懂了,这个因为双链表,之前单链表的时候写了太多注释了,这个就从简了,但是我把单链表的代码也贴出来了,他们俩操作差不多。
双链表
带详细注释呦呦呦……^^
#include<iostream>
#include<string>
using namespace std;
const int N=100010;
int e[N];//存放数据的数组
int el[N];//存放左边节点的地址的数组
int er[N];//存放右面节点的地址的数组
int idx=2;//地址
//地址0和1分别用来存放头节点和尾节点
void init_arry();
void insert_L(int x);
void insert_R(int x);
void delete_k(int k);//删除地址为k的节点
void insert_K_R(int k,int x);//在k的右边插入一个数
int main()
{
init_arry();
int m;
cin >>m;
while(m--)
{
string order;
int k,x;
cin >>order;
if(order=="L"){
cin >>x;
insert_L(x);
}else if(order=="R"){
cin >>x;
insert_R(x);
}else if(order=="D"){
cin >>k;
delete_k(k+1);
}else if(order=="IR"){
cin >>k>>x;
insert_K_R(k+1,x);
}else if(order=="IL"){
cin >>k>>x;
insert_K_R(el[k+1],x);
}
}
//遍历链表
for(int i=0;i!=el[1];i=er[i]) cout <<e[er[i]]<<' ';
return 0;
}
//初始化
void init_arry()
{
er[0]=1;//头节点的右面指向尾节点
el[1]=0;//尾节点的左面指向头节点
}
//最左侧插入一个数
void insert_L(int x)
{
int adress=idx;
idx++;
e[adress]=x;
el[adress]=0;
er[adress]=er[0];
//把adress赋给头节点的右和下一个的左
er[0]=adress;
el[er[adress]]=adress;
}
//最右侧插入一个数
void insert_R(int x)
{
int adress=idx;
idx++;
e[adress]=x;
el[adress]=el[1];
er[adress]=1;
//把adress赋给头节点的右和下一个的左
el[1]=adress;
er[el[adress]]=adress;
}
//删除第k个数
void delete_k(int k)
{
er[el[k]]=er[k];
el[er[k]]=el[k];
}
//在k的右边插入一个数
void insert_K_R(int k,int x)
{
int adress=idx;
idx++;
e[adress]=x;
el[adress]=k;
er[adress]=er[k];
er[k]=adress;
el[er[adress]]=adress;
}
单链表
#include<iostream>
using namespace std;
const int N=100010;
int q[N];//存放下一个元素地址的数组(此处的地址是指数据的下标)
int s[N];//存放数据的数组
int head;//头节点指向第一个元素,其实就是第一个元素的下标
int idx;//存的是当前操作元素的下标
void init_arry();
void insert_arry(int x,int l);//在l后方插入x元素
void intsert_head(int x);//在头节点后方插入元素
void delete_arry(int l);//删除地址l后方的元素
int main()
{
init_arry();
int m;
cin >>m;
while(m--)
{
char op;int x,k;
cin >>op;
if(op=='H')
{
cin >>x;
intsert_head(x);
}else if(op=='D'){
cin >>k;
if(!k) head=q[head];
delete_arry(k-1);
}else{
cin >>k>>x;
insert_arry(x,k-1);
}
}
for(int i=head;i!=-1;i=q[i]) cout <<s[i]<<' ';
return 0;
}
void init_arry()
{
head=-1;//此时链表内并没有元素,
idx=0;
}
void intsert_head(int x)
{
int adress=idx;
s[adress]=x;
q[adress]=head;
head=adress;
idx++;
}
void insert_arry(int x,int l)//在l后方插入x元素
{
//首先要分配一个地址(相当于是下标)这个idx只能往前走,相当于是地址了每次分配一个地址后都要加一,作为下一个的地址。
int adress=idx;
//将x放入容器中
s[adress]=x;
//将容器放入链表中
q[adress]=q[l];//把下一个元素的地址赋值给这个元素的地址空间中
q[l]=adress;//把自己的地址赋给上一个的地址空间
idx++;//给下一个元素的地址
}
void delete_arry(int l)
{
q[l]=q[q[l]];
}