数据结构：静态链表（编程技巧）

链表的元素用数组存储， 用数组的下标模拟指针。

一、理解

如果有些程序设计语言没有指针类型，如何实现链表？

在使用指针类型实现链表时，我们很容易就可以直接在内存中新建一块地址用于创建下一个结点，在逻辑上，我们好像链表是顺序的一样，我们根本不用管他们在内存中是如何存储的，直接“顺序”地遍历即可。

我们用静态链表，使用数组存储元素和下标，也想实现逻辑上是顺序的。实际上，我们只需要用数组模拟指针，我们在创建一个新结点时，只需要找到一块“空地”即可创建成功，我们在保证data不动的情况下，直接修改next数组就能实现指针的变换，即一旦创建成功数据的值就存在一个固定的位置，而是通过改变“存指针的数组”来改变指向。我们也不需要去考虑到底存在哪，逻辑上一样可以想象成和普通链表一样的。可以模拟为：

int new_place=find_empty();
data[new_place]=new_data;//利用空地“创建新节点”并赋值
next[last_place]=new_place;//链表中最后一个结点指向该结点
next[new_place]=-1;//新建结点指向为-1

同理，实现双向循环静态链表，使用left和right数组的下标就可以实现两个左右指针。

二、例题

例题：有若干个盒子，从左至右依次编号为

1,2,3,...,n。可执行以下指令（保证X不等于Y）：

➢L X Y表示把盒子X移动到盒子Y左边（如果X

已在Y左边，则忽略该指令）。

➢R X Y表示把盒子X移动到盒子Y右边（如果X

已在Y右边，则忽略该指令）。

这里使用双向循环链表来实现。

vector<int> data(n+1);//留出一个头结点
vector<int> left(n+1);
vector<int> right(n+1);
for(int i=1;i<=n;++i){data[i]=i;//创建结点并赋值    if(i!=1)left[i]=i-1;//初始化左指针指向前一个结点(用下标模拟指针)else left[i]=n;if(i!=n)right[i]=i+1;//初始化左指针指向后一个结点(用下标模拟指针)else right[i]=1;
}
while(cin>>Direct>>x>y){//x和y虽然是盒子编号，但是data[x]就是盒子x，所以left[x]就是盒子x左边指向的盒子if(Direct=='L'||Direct=='R')if(Direct=='L'){while(right[x]!=y){//右边指向的盒子不等于y  1--2--1--2right[left[x]]=right[x];left[right[x]]=left[x];left[x]=right[x];right[x]=right[left[x]];left[right[x]]=x;right[left[x]]=x;}}else{while(left[x]!=y){right[left[x]]=right[x];left[right[x]]=left[x];right[x]=left[x];left[x]=left[left[x]];right[left[x]]=x;left[right[x]]=x;}}
}
int i=1;
while(i!=-1){cout<<"盒子编号："<<data[i]<<endl;i=right[i];
}