静态链表重点分析
相信很多只学过动态链表的同学刚接触到静态链表的时候会一脸懵,但其实只要将两种链表对比来看就很清晰了:
动态链表的逻辑结构与实际结构是一致的;
静态链表的逻辑结构与实际结构是不一致的;
动态链表是利用指针将一个个节点连接起来,而静态链表是用两个数组来实现的;
也即是说,对于动态链表,只要得到其头节点的指针p,按照p = p->next即可进行遍历;
但对于静态链表,如果按照for(int i = 0; i < n; i ++)这样通用的方式去遍历e[N]数组,是无法得到正确的序列的。
对于静态链表的正确遍历方式是,由i = head进入,读取e[i]作为value,ne[i]作为next,直到 i = -1停止;
index作为实际结构的标识,标志着数组存储链表的实际索引。
C++ 代码
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int head, e[N], ne[N], index;//最好不要命名为index,会与string库中的函数冲突
//index实际上是标识头节点的指针,即头节点的下标索引
void init()//初始化
{
head = -1;// -1相当于动态链表里的NULL
index = 0;//两个数组从0开始存储
}
void insert_head(int x)//插到序列起始位置
{
e[index] = x;//插入index处
ne[index] = head;//新节点指向原头节点
head = index;//新节点成为新头结点
index ++ ;//e、ne数组同时指向下一个位置
}
void delete_node(int k)//删除插入的第k个节点后面的节点,注意是插入的第k个而不是链表的第k个
{
//因为index是从0开始取的,所以相当于删除掉下标为k - 1 节点的下一个节点
ne[k - 1] = ne[ne[k - 1]];
//注意这里不能按照动态链表的思想写成ne[k - 1] = ne[k]
//因为ne[k]是ne[k - 1]实际上的下一个位置,而不是逻辑上的下一个位置
}
void insert_node(int k, int x)//在第k个插入的数后再插入一个数
{
e[index] = x;
ne[index] = ne[k - 1];//新节点指向下标为k - 1节点的下一个节点
ne[k - 1] = index;//下标为k - 1节点指向新节点
index ++ ;
}
int main()
{
init();//初始化
int m;
cin >> m;
for(int i = 0; i < m; i ++ )
{
char button;
int x, k;
cin >> button;
if(button == 'H')
{
cin >> x;
insert_head(x);
}
else if(button == 'D')
{
cin >> k;
if(!k) head = ne[head];
else delete_node(k);
}
else if(button == 'I')
{
cin >> k >> x;
insert_node(k, x);
}
}
for(int i = head; i != -1; i = ne[i])//由i == head开始遍历,直至i == -1结束
{
cout << e[i] << ' ';
}
return 0;
}