算法竞赛小白进阶之路---洛谷关于链表的两个基本题目的介绍

1.排队问题

下面的这个是来自于洛谷的一道题目：

主要就是说的每一个小朋友都有自己的这个编号，实际上考察的是对于这个链表的遍历；

fig:

下面的这个就是该问题的代码部分：先进行这个输入的过程，这个里面的定义的这个ne数组就是指的我们的这个链表里面的next的含义，也就是指向下一个节点的指针的表示，你按照这个输入数据里面的这个顺序；

我们看一下这个输入的数据，第一个标号是1，然后我们发现他的下一个标号是4，然后这个4小标的下一个位置是2,2下标的下一个位置是6,6下标的下一个位置是5,5下标的下一个位置是3,3下标的下一个位置是0，也就是代表这个过程结束了；

因此这个时候大家就可以理解为什么输入的时候使用的是这个ne[i]数组进行这个输入的过程了，因为我们输入的这个数据实际上就是指向的下一个节点的这个指针，或者是叫做next，也就是我们输入的这个内容的含义表示的就是这个下标对应的孩子的下一个孩子的编号，而不是我们当前的这个小朋友的编号；

#include<iostream> using namespace std; const int N = 1e6 + 10; int n,h; int ne[N]; int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> ne[i]; } cin>>h; for (int i = h; i; i = ne[i]) { cout << i << " "; } return 0; }

输入这个h表示的就是开始时刻的这个小朋友的下标，我们根据这个输入在这个ne数组里面进行寻找即可，这个循环的条件，就是我们的i不可以是0值，通过这个测试用例我们也是非常明显的发现，当这个i是0的时候，实际上这个表示的就是最后一个小朋友的这个编号了，这个时候我们的整个过程就结束了；

因此，这个题目其实就是考察的给定我们的next数组，我们进行数组元素的读入，然后根据他提供的这个下标，也就是头结点，按照这个顺序对于我们的这个链表里面的元素进行遍历的过程，刚开始接触的话，可能会觉得这个有点怪怪的，慢慢理解就好啦；

2.单向链表问题

下面的这个就是我们的单向链表的问题：就是主要描述的三种不同的操作，插入这个节点元素之后，我们的这个1操作相当于是进行这个元素的插入，2表示的就是查询指定的这个元素的下一个位置的元素，3表示的就是删除我们的这个指定元素的下一个位置的元素；

fig:

下面的这个就是我们这个题目的代码：说实在的，下面的这个题目代码我看了很久，有很多的细节，我也踩了很多的坑，总结一下；

1）这个应该是我第二次学习这个链表了，第一次学习的时候当时主要是使用的这个结构体的方式继续拧实现的，也就是经常使用指针；

2）这个是第二次学习，这一次的这个教程里面的老师的风格就是使用到的这个数组，也就是e数组和ne数组，e数组表示的是我们的这个链表里面的这个所有的节点的数据域，然后这个ne数组表示的是我们的这个链表里面的所有的节点的指针域，但是这个并不是真正意义上面的这个指针，而是下一个指向的节点的下标，寓意和指针是类似的；

3）首先进行这个输入的过程，一定是输入两个数据的，无论是1还是2还是3，但是只有1的时候需要输入第三个数据，因此我们下面的这个代码最开始的时候输入两个数据，接下来在这个判断的逻辑里面添加当这个op事1的时候，我们才会输入这个第三个数据；

4）刚开始的这个链表里面的元素是1，因此我们最开始在while函数之前进行这个初始化的操作；

5）插入数据的时候op=1，实际上这个不是单纯的尾插，而是相当于在这个中间的位置进行数据的插入，因此我们需要注意这个指针的变换的顺序，一定是我们的这个插入数据的指针指向后一个节点，前一个节点指向我们的这个插入的数据的位置；

放到下面的这个代码里面，就是我们输入这个y表示我们需要插入的这个元素，输入y,id++这个相当于就是在我们的这个数组里面为这个新加入的元素开空间；

e[id]=y表示的就是在这个e数组里面，也就是我们的这个数值域数组的这个id下标存放我们输入的这个数据，接下来的这个两行代码就是对于这个指针的指向修改的过程，也是我们的这个链表里进行这个节点插入的经典的操作

ne数组就可以理解为是我们的这个next数组，p里面存放的实际上就是x这个元素的下标，也就是我们输入的这个元素，ne[p]就是x后面额这个元素的下标，赋值给这个ne[id]实际上就是id这个节点指针域指向后面的这个节点；

ne[p]=id表示的就是这个的这个id告诉这个ne数组里面的这个下标是p的元素，你应该指向我，你的这个指向的元素更新了，实际上这两行代码就是进行的这个指针的指向的变换的过程，但是很多人想不清楚（其实笔者最开始学习这个不分的时候，也是学习的非常的痛苦，但是这个东西我觉得就是需要多去理解，千万不要死记硬背）

6）op=2的时候就是进行的这个查询的过程，先通过这个ne数组获得下一个一个的下标，在通过这个下标在这个e数组里面找到即可；

7）op=3实际上进行的就是我们的删除的过程，删除的话，实际上就是跳过其中的一个节点，直接指向下下个节点，也就是两次进行这个ne的操作即可，这个ne就是我们的指针数组，存放的就是下一个元素的下标，这个需要知道；

8）你以为到这里就结束了么，实际上远远不是，因为会涉及到这个数据的范围的问题，也就是我们的这个数组的大小问题，我在这个上面就被坑了，我的代码检查了很多遍，但是因为这个数组的表示的范围一直没有通过，这个也是非常的痛苦

#include<iostream> using namespace std; const int N = 1e5 + 10; const int M = 1e6 + 10; int h, id; int ne[N], e[N], mp[M]; int main() { int q; cin >> q; id++; e[id] = 1; mp[1] = id; while (q--) { int op, x; cin >> op >> x; int p = mp[x];//x这个元素存放位置的下标 if (op == 1) { int y; cin >> y; id++; e[id] = y; ne[id] = ne[p]; ne[p] = id; mp[y] = id; } else if (op == 2) { cout << e[ne[p]] << endl; } else { ne[p] = ne[ne[p]]; } } return 0; }