算法模版：模拟数据结构之链表【沈七】

算法模版：模拟数据结构之链表

前言

唤我沈七就好啦。
在本专题的绪论部分里已经简单的解释了什么是数据结构，以及有哪些常见的数据结构。
准备工作完毕之后。
接下来我们就开始进入本板块的正文部分，
模拟数据结构之链表
还是那句话。
蒟蒻因为实在是太弱了，肯定免不了错误百出。
欢迎批评指正，期待共同成长！

什么是链表？

回答这个问题，就不得不提一下链表的孪生兄弟—数组了，其实这两者都属于同一种数据结构—线性表。
但因为存储结构的不同而被划分成了两类。
数组是顺序存储结构，而链表则是链式存储。
关于数组想必各位都已经很熟悉了，所以这次主要讲解模拟链表部分。
在此之前先来谈谈数组在使用时存在的问题。
想必最令人头痛的应该就是数组在插入和删除时需要移动大量元素，这显然是非常耗费时间的。
而链表的出现则很好的解决了这个问题。
链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素，这组存储单元可以是连续的，也可以是不连续的。
这就意味着，这些数据元素可以存在内存未被占用的任意位置(如图3-6-1所示)。

实现思路

为什么当插入和删除时，就要移动大量元素，仔细分析后，发现原因就在于相邻两元素的存储位置也具有邻居关系。
它们编号是1，2，3，…，n，它们在内存中的位置也是挨着的，中间没有空隙，当然就无法快速介入，而删除后，当中就会留出空隙，自然需要弥补。问题就出在这里。

那如何解决呢？

我们反正也是要让相邻元素间留有足够余地，那干脆所有的元素都不要考虑相邻位置了。
哪有空位就到哪里，只是让每个元素知道它下一个元素的位置在哪里。这样，我们可以在第一个元素时，就知道第二个元素的位置(内存地址)，而找到它;
在第二个元素时，再找到第三个元素的位置(内存地址)。这样所有的元素我们就都可以通过遍历而找到。

这思路是不是很妙，难点就是如何实现让每一个元素知道它下一个元素的位置在哪里。
而我们恰巧有一个现成的东西----指针。
但考虑到用指针操作略显复杂，
所以我们这里用下标来作为地址，用一个新数组来代替指针储存下标。
我们将两个数组用下标来对应起来也可以达到指针的效果，
只需要用一个数组用来存储数据，新数组在同下标位置记录下一个元素所在的下标，
这样用数组描述的链表也被称为静态链表。

注意：下文为了方便描述，我将记录下一个结点地址（下标）的变量都统称为了指针

一些术语

结点：链表上的某个数据元素我们称为结点。
头指针：链表中第一个结点的存储位置叫做头指针。整个链表的存取必须从头指针开始进行。

实现方法

1 .创建变量

constint N=1e6+10;int e[N];    存储结点的值。
 int ne[N];   存储结点的指针(即下一个结点的下标）。
 int head;    存储链表头，即头指针。
 int idx;     表示当前用到了哪个结点。

关于 head
刚开始的时候它负责指向空结点，在链表里有元素的时候，它变成了一个指向第一个元素的指针。

2 .初始操作

初始化
head=-1;    表示链表没有内容。
idx=0;      链表中还没有元素，故从零开始。

最开始的时候，链表的头节点要指向-1，
为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束。
虽然我们在进行各种操作的时候，元素所在的下标看上去很乱，
但是当我们访问的时候，是靠着指针，也就是靠ne[ ]来访问的，
这样即便下标乱，也与我们要做的事不相关了。
另外，我们遍历链表的时候也是这样，靠的是ne[ ]。

3 .插入操作

链表的插入有两种分别是①头结点插入和②链表中间插入。

①头结点插入。

voidint_to_head(int x){//和链表中间插入的区别就在于它有head头节点
    e[idx]= x;       第一步，先将值放进去
    ne[idx]= head;   head作为一个指针指向空节点，现在ne[idx]= head;做这把交椅的人换了
                      先在只是做到了第一步，将元素x的指针指向了head原本指向的
    head = idx;       head现在表示指向第一个元素了，它不在是空指针了。（不指向空气了）
    idx ++;           结点向下移一位，为下一次插入元素做准备。
}

②将x插入到下标为k的点的后面。

voidadd(int k,int x){
    e[idx]= x;         先将元素插进去
    ne[idx]= ne[k];    让元素x配套的指针，指向它要占位的元素的下一个位置
    ne[k]= idx;        让原来元素的指针指向自己
    idx ++;}           将idx向后挪

所采用的思路就是

将x的指针指向 k 指针指向的结点，也就是 k 的下一个结点。
即 ne[idx] = ne[k]; 现在x的后面就是曾经是 k 后面的结点了。

然后改变k的指针，将其指向指向x
即 ne[k] = idx; 现在 k的后面就是x了。

4 .删除操作

将下标是k的后一个结点删掉

voidremove(int k){
    ne[k]= ne[ne[k]];  让k的指针指向，k下一个人的下一个人，那中间的那位就被挤掉了。
}

实现删除操作的思路也很妙.
其实我们没必要真的删除储存在e[ ]的数据，而是需要对ne[ ]下文章。
只需要将ne[ ]下标为 k 的指针指向原本指向的结点的下一个就可以了。
这种 k 原本的下一个结点就被越过去， k 直接指向了下下个，而遍历是靠指针ne[ ]来做的，所以k 的下一个结点永远不会被遍历到，这样就达到了删除的效果。

5 .链表遍历

for(int i=head;i!=-1;i=ne[i])
cout<<e[i];

通过指针数组ne[ ]来遍历，应该最开始head指向的 -1 。
经过数据不断的插入，-1 仍然是最后一个结点（此节点不存贮具体数据，仅用于链表遍历）。
所以只要指针不等于 -1 就说明链表还没遍历完。

算法模板

constint N=1e6+10;int head, e[N], ne[N], idx;// 初始化voidinit(){ head =-1;  idx =0;}// 在链表头插入一个数avoidhead_add(int a){
    e[idx]= a,ne[idx]= head, head = idx ++;}//在k的后面插入x（k!=0)voidadd(int k,int x){
    e[idx]= x;//先将元素插进去
    ne[idx]= ne[k];//让元素x配套的指针，指向它要占位的元素的下一个位置
    ne[k]= idx;//让原来元素的指针指向自己
    idx ++;//将idx向后挪}//将其他节点删除（k！=0）voidDelete(int k){
    n[k]=ne[ne[k]];}//链表遍历for(int i=head;i!=;i=ne[i])
cout<<e[i];

完结散花

ok以上就是对模拟数据结构之链表的全部讲解啦，很感谢你能看到这儿啦。如果有遗漏、错误或者有更加通俗易懂的讲解,欢迎小伙伴私信我，我后期再补充完善。

参考文章

[1]程杰.大话数据结构[M].北京:清华大学出版社 ,2011：5-14 .
https://www.acwing.com/solution/content/16251/
全部模板链接
https://www.acwing.com/blog/content/404