线性数据结构——链表课后讲解
讲解内容：
- 链表与数组的区别。
- 前驱和后继。
- 代码编写前驱和后继。
- 课上例题。
| 性能 | 数组 | 链表 |
|---|---|---|
| 查找 | a_1=1 | for 循环遍历 |
| 删除 ^{1} | for 循环挨个往前移（覆盖） | 连上 a{i-1} 和 a_{i+1} |
| 插入 | for 循环挨个往后移（腾出位置） | 按顺序互相连接 |
| 难度 | 简单 | 思路难，程序简单 |
| 复杂度 | 比较高 | 比较低 |
1:非归 0：1-2-(3)-4-5 -> 1-2-4-5。
前驱和后继
在链表里有一个非常关键的词语：前驱后继。
- 前驱：在数组
1,2,3,4,5中 a_{i-1} 是 a_i 的前驱，例 2 是 3 的前驱。 - 后继：在数组
1,2,3,4,5中 a_{i+1} 是 a_i 的后继，例 4 是 3 的后继。
为什么要知道前驱和后继呢？首先，链表就好比一条锁链，它连接着每个数与数的位置关系，我们可以用 - 来代表锁链。
数组 1-2-3-4-5-6-7 中我们要删除 4，如果用 for 循环解决问题就要用到遍历，将 4 以后的每个数向前挪一位，如果数组庞大，那么复杂度就远远地超出了正常范围。如果用链表，就只用切断 4 与 3 和 5 的锁链，将 3 和 5 连起来，那么就要用到非常重要的东西（不是算法）：指针。
举个例子：有 3 个数 1,2,3 ， 2 是 1 的后继， 3 是 2 的后继； 1 是 2 的前驱， 2 是 3 的前驱。我们利用正向思维（正常人的思维）来看，因为 2 在 1 的后面，所以 1 就指向 2 ，这时如果要把 2 删除，就只用将 1 指向 3 （ 3 变成 1 的后继），然后将 1 成为 3 的后继。
那么怎么设置前驱和后继呢？
后继：我们可以定义数组 a ，将 a_i 定义为 a_{i+1} 的数（ a_i 指向 a_{i+1} ），例 s_2 = 1 , s_{3} = 4 ，则将 a_2 定义为 4 。所以 4 就是 2 的后继。
前驱：我们可以定义数组 b ，将 b_i 定义为 b_{i-1} 的数（ b_i 指向 b_{i-1} ），例 s_2=1,s_{3}=4 ，则将 b_3 定义为 2 。所以 2 就是 4 的前驱。
代码编写前驱和后继
我们得到了一个下标 x ，要连上 a_{x-1} 和 a_{x+1} 。那么先设置后继（ a_{x-1} 链接 a_{x+1} ）提示： a 数组代表后继， b 数组代表前驱，其中数组 1-2-3 删除 2 ：
将 x 的前驱的后继设为 x 的后继：a[b[x]]=a[x]。
这样就实现了 1 连接了 3 。
将 x 的后继的前驱设为 x 的前驱：b[a[x]]=b[x]。
这样就实现了 3 连接了 1 。
课上例题
思路：报数为 m 时 m 归 0 ，删除报数为 m 的那个人，将他的前面和后面互相连接。此处还会更新细讲 6 月 2 日。具体先看代码。
总体代码：
#include<bits/stdc++.h>
using namespace std;
int main(){
int a[101],b[101];
int n,m,s=0;
cin>>n>>m;
for(int i=1;i<=n-1;i++)a[i]=i+1;//设置后继指向。
for(int i=2;i<=n;i++)b[i]=i-1;//设置前驱指向。
a[n]=1,b[1]=n;//环形指向。
int bs=1,xs=1;//报数从1开始，选手从第1个开始报。
while(s<n){
while(bs<m){//报到 m-1。
bs++;//报数。
xs=a[xs];//下一个选手。
}
cout<<xs<<" ";//被淘汰的人。
s++;//淘汰数量 +1。
a[b[xs]]=a[xs];//解释过。
b[a[xs]]=b[xs];//解释过。
xs=a[xs];继续更新下一个将要报道的人。
bs=1;//从新从 1 开始报。
}
return 0;
}