数据结构漫游记：静态链表的实现(CPP)
嘿，各位技术潮人！好久不见甚是想念。生活就像一场奇妙冒险，而编程就是那把超酷的万能钥匙。此刻，阳光洒在键盘上，灵感在指尖跳跃，让我们抛开一切束缚，给平淡日子加点料，注入满满的passion。准备好和我一起冲进代码的奇幻宇宙了吗？Let's go！
我的博客：yuanManGan
我的专栏：C++入门小馆 C言雅韵集 数据结构漫游记 闲言碎语小记坊
之前我们了解到动态链表的实现感兴趣的可以点点链接看一看
数据结构漫游记：动态链表的实现-CSDN博客
静态链表的认识
我们知道链表有两部分组成
一部分是数据域
一部分是指针域
我们动态实现链表时每次都会为新的链表申请空间，会搞得很麻烦代码量也很高，运行的时间也会很高，但静态实现完美的解决了这个问题。
我们是不是可以用空间很大的数组来分开存储指针和指针呢？
用数组的下标来找到每个结点。
静态链表的实现
定义两个数组分别为e和ne存储数据和指针。再用h指向哨兵位(指第一个不存储任何有效数据的结点)，id指向最后一个结点。
这是有人就会问了你这个ne数组是不是多余了，我靠一个一个下标就能找到下一个元素啊，根本用不到ne数组啊
小伙子你想的太天真了，那你来实现下面这个呢？
如果你画出来这个结构会发现是A-》D-》E，C去哪里啦？每次C是无效数据，可能被删除了
创建空链表
const int N = 1e5 + 10;
int ne[N], e[N]; // 创建两个很大的数组
int id， h;
int main()
{
return 0;
} 注意这里将数组放在全局变量有两个好处，一个是全局变量的内存更大，溢出问题更少出现；另一个是数组等变量不初始化放在main函数外会自动初始化为0。
这就实现了第一步创建空链表。
头插
无论是头插还是什么基本的思路都和动态的链表无二。我们需要先将新结点指向下一个结点，再将哨兵位的指针指向新节点。顺序不能搞错，不然就不能找到下一个结点了。
代码实现：
void push_front(int x)
{
id++;//指向下一个空的位置
//处理新结点
e[id] = x;//存储数据
ne[id] = ne[h];
//处理哨兵位
ne[h] = id;
}遍历链表打印
遍历链表的思路就是，定义一个指针cur令cur =ne[cur]直到cur等于0就结束了。也和动态链表的思路大差不差。
实现：
void print()
{
for (int i = ne[id]; i; i = ne[i])
{
cout << e[i] << " ->";
}
cout << endl << endl;
}按值查找
实现按值查找一种方法就是遍历链表然后一个一个找，但这种做法时间复杂度是O(N)。这里我们可以先创建一个mp数组，以存储的数据为下标存储每个元素的地址。
const int N = 1e5 + 10;
int ne[N], e[N]; // 创建两个很大的数组
int id， h;
int mp[N];
int main()
{
return 0;
} 然后在插入元素时储存元素的下标
void push_front(int x)
{
id++;//指向下一个空的位置
//处理新结点
e[id] = x;//存储数据
ne[id] = ne[h];
//处理哨兵位
ne[h] = id;
//标记新结点的位置
mp[x] = id;
}就可以实现find函数了
int find(int x)
{
/*int i = ne[h];
while (i)
{
if (e[i] == x) return i;
i = ne[i];
}
return 0;*/
return mp[x];
}注释部分是第一种方法。
这里有一个弊端，当存储两个相同的数时，mp数组就不知道存储谁的下标，当没有重复的数据时使用这个方法的时间复杂度是O(1),大大的优化。
在任意位置之后处插入数据
这个功能要传入的数据是某个位置的下标，如果传入的是数据，也得转化为下标来计算，这个位置之后的插入就和头插的执行过程差不多，这里就简单带过咯
void push_front(int p,int x)
{
id++;//指向下一个空的位置
//处理新结点
e[id] = x;//存储数据
ne[id] = ne[p];
//处理p位置
ne[p] = id;
//标记新结点
mp[x] = id;
}这里就是把h换成了p。
删除任意位后的数据
删除下一个位置就是将这个位置的下一个指针指向下下个元素。
实现也很简单
void erase(int p)
{
if(ne[p]) // 当 p 不是最后一个元素的时候
{
mp[e[ne[p]]] = 0; // 把标记清空
ne[p] = ne[ne[p]];
}
}注意这里的p不能是最后一个元素哦！
这里不实现尾插，在任意位置之前插入，删除任意位置的原因很简单，相对与这些代码要复杂一点，并且时间复杂度都基本上是O(n),我们可以使用其他的数据结构来实现。
比如下期我要写的循环链表，请大家敬请期待！谢谢! ~