单链表

美篇视频连接：

视频连接！

前几天写树与图的存储那里是肯定有人要问链表了。

今天cht就带大家捋一捋链表的知识点。

只更单链表，双链表明天~

啥是链表

链表是由元素和指针构成的，相对于数组来说有一下优缺点：

优点：方便插入删除。

缺点：查找元素太慢了。

所以大家要谨慎选择使用链表还是数组啊！

链表的模拟。

链表的模拟主要支持3中功能：
1. 向链表头插入一个数x。
2. 删除第k个输入的数后面的数，注意可以删除头结点head。
3. 第k个输入的数后面插入一个数x。

我们又如何模拟呢？
我们可以用我们的e数组表示链表中每一个元素的值，ne数组表示其所对应的值指向的值,idx表示用到的数。
好那我们如何插入一个元素呢？
请看图：

图片中我们先建立一个节点，然后让前面的点连接它，它和后面的点连接（还是建议大家看视频）。
具体落实到代码上就是:

void add(int k, int x)
{
    e[idx] = x,/*创建出这个点*/ne[idx] = ne[k],/*第一条指针连接完毕*/ne[k] = idx ++;//所有指针连接完毕
}

这里建议大家看视频h，不然确实不太好理解。
那我们如何删除一个数呢？
请看下图：

我们只需把要插入的数前后连接起来即可。
代码就是：

void del(int k)
{
    ne[k] = ne[ne[k]];//ne[ne[k]]就是往前走2个的数。相当于这个数邻居的邻居。
}

单链表模拟的题目

请看题目：单链表
本题刚好符合单链表的三个性质。
然后就可以进行模拟。
前面我们没说add_to_head的模拟，其实很弱，把add里的ne[k]``改成head```即可。
那我们分别模拟：

1.add_to_head

void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++;
}

2.add

void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++;
}

3.remove(这里写的del，一样的原理就是函数的名字不太一样)

void del(int k)
{
    ne[k] = ne[ne[k]];
}

当然还有一个初始化

初始化一般用init表示。
先把head设为-1，idx设为0即可。
代码：

void init()
{
    head = -1;
    idx = 0;
}

完整代码：

#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int m, e[N], ne[N], idx, head;
void init()
{
    head = -1;
    idx = 0;
}
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++;
}
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++;
}
void del(int k)
{
    ne[k] = ne[ne[k]];
}
int main()
{
    cin >> m;
    init();
    while(m --)
    {
        char op;
        cin >> op;
        int k, x;
        if(op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if(op == 'I')
        {
            cin >> k >> x;
            add(k - 1, x);
        }
        else{
            cin >> k;
            if(!k) head = ne[head];
            del(k - 1);
        }
    }
    for(int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
    return 0;
}

今天不留作业了。

今天的分享就到这里了。

未经允许，请勿转载、

这是我的全部分享

bye~