【问题解答】用数组模拟单链表_实现一个单链表,链表初始为空,支持三种操作: a.向链表头插入一个数; b.删除第 k

我这里是根据我所遇到和参考大家的问题解答所总结的：
非常推荐大家打卡 y总的算法基础课： 活动 - AcWing
这里的问题也是基于他讲的单链表所总结的。

题目：

实现一个单链表，链表初始为空，支持三种操作：

(1) 向链表头插入一个数；

(2) 删除第k个插入的数后面的数；

(3) 在第k个插入的数后插入一个数

现在要对该链表进行M次操作，进行完所有操作后，从头到尾输出整个链表。

注意:题目中第k个插入的数并不是指当前链表的第k个数。例如操作过程中一共插入了n个数，则按照插入的时间顺序，这n个数依次为：第1个插入的数，第2个插入的数，…第n个插入的数。

输入格式

第一行包含整数M，表示操作次数。

接下来M行，每行包含一个操作命令，操作命令可能为以下几种：

(1) “H x”，表示向链表头插入一个数x。

(2) “D k”，表示删除第k个输入的数后面的数（当k为0时，表示删除头结点）。

(3) “I k x”，表示在第k个输入的数后面插入一个数x（此操作中k均大于0）。

输出格式

共一行，将整个链表从头到尾输出。

数据范围

1≤M≤100000

所有操作保证合法。

<code class="language-cpp language-plaintext hljs">输入样例：
<span class="hljs-number">10</span>
H <span class="hljs-number">9</span>
I <span class="hljs-number">1</span> <span class="hljs-number">1</span>
D <span class="hljs-number">1</span>
D <span class="hljs-number">0</span>
H <span class="hljs-number">6</span>
I <span class="hljs-number">3</span> <span class="hljs-number">6</span>
I <span class="hljs-number">4</span> <span class="hljs-number">5</span>
I <span class="hljs-number">4</span> <span class="hljs-number">5</span>
I <span class="hljs-number">3</span> <span class="hljs-number">4</span>
D <span class="hljs-number">6</span>
输出样例：
<span class="hljs-number">6</span> <span class="hljs-number">4</span> <span class="hljs-number">6</span> <span class="hljs-number">5</span></code>

AC代码：

#include <iostream>
 
using namespace std;
 
const int N = 100010;
 
 
// head 表示头结点的下标
// e[i] 表示节点i的值
// ne[i] 表示节点i的next指针是多少
// idx 存储当前已经用到了哪个点
int head, e[N], ne[N], idx;
 
// 初始化
void init()
{
    head = -1;
    idx = 0;
}
 
// 将x插到头结点
void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx ++ ;
}
 
// 将x插到下标是k的点后面
void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx ++ ;
}
 
// 将下标是k的点后面的点删掉
void remove(int k)
{
    ne[k] = ne[ne[k]];
}
 
int main()
{
    int m;
    cin >> m;
 
    init();
 
    while (m -- )
    {
        int k, x;
        char op;
 
        cin >> op;
        if (op == 'H')
        {
            cin >> x;
            add_to_head(x);
        }
        else if (op == 'D')
        {
            cin >> k;
            if (!k) head = ne[head];
            else remove(k - 1);
        }
        else
        {
            cin >> k >> x;
            add(k - 1, x);
        }
    }
 
    for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
    cout << endl;
 
    return 0;
}

这题如果大家有学过单链表（学校C语言数据结构课程）的基础，再理解这种数组模拟实现的单链表可能会更加容易，因此考虑到部分同学还没学数据结构课程，如下的题解我会写的更加详细一点。

---

• 1、head是什么？它的具体作用又是啥？

答:head应该是一个特殊的指针，一开始指向-1，表示链表里没有内容，为空节点，

当链表里有元素的时候，它变成了一个指向第一个元素的指针。还有就是为了最后遍历链表时，知道链表什么时候结束（因为最后实现的链表，它最后一个节点的ne[i]一定等于-1）

• 2、对于k-1的相关问题？

这个函数含义是 将x插到下标是k的点后面

题目里要将x插入到第k个插入的数后面，第k个插入的数下标是k - 1，所以调用的时候是add(k - 1, x)，remove(k-1)。如果你一开始将idx=1（初始化）,那么下标和k就统一了，就不需要再k-1了。

• 3、关于e[idx]、en[idx]和idx的问题？

idx可以理解为一个结点！！

结点：链表的元素，含e[idx],ne[idx]两个部分

e[idx]:结点编号为idx对应的节点值

ne[idx]：结点编号为idx对应的下一个结点的编号

要明白idx只是记录当前的操作的位置，一般实现的链表idx是乱序的(前后的节点的数组下标不需要连续【不理解，可以带入样例观察】)，需要通过当前的ne[i]找到下一个idx。这也是两者的联系。

• 4、对于删除头节点：head=ne[head]的操作？

删除头结点是head指向的结点，也就是链表中的第一个结点，【head指向可能是一个空结点（e数组不存值），或者是非空结点。指向的空结点叫头结点，指向的非空结点叫首元结点，即后者并没有头结点这种概念】（这句只针对学过单链表的同学，没学过的同学不用理会这句话）。但是y总并没有区分这个概念，所以删除头结点就是删除链表的第一个有值的结点，即首元结点，head指向ne[head]是因为head本来就指向它的下一个结点，所以ne[head]就是头结点的下一个结点。

• 5、为什么最后一个节点的ne[idx]一定等于-1?

首先这个head指的是链表中头节点的下标，当链表中没有节点时head = -1，但当链表中有值插到头节点的时候，head储存的就是这个值的idx1，通过e[idx1]可以求出这个节点的值。而ne[idx1]就等于head之前的值，即-1。如果再在头节点插入一个元素，则head指向这个元素的idx2，而ne[idx2]就等于上一次插入的head值，即idx1。此时，head = idx2，ne[idx2] = idx1，ne[idx1] = -1.

比如：因为初始化head=-1，head指向链表的头节点地址；例如输入H 9后，则有e[0] = 9; ne[0] = -1；head=0;之后无论进行什么操作，链表最后一个节点，其对应的ne数组值一定为-1。

• 6、为什么每次循环输入的字符ch,用cin>>ch可以ac，而scanf(“%c”,&ch)结果就不行？

这个是分情况的。

有一个特殊的格式 %c

当%c格式的时候，会读取任何字符，包括换行和空格。

当其他格式的时候(不包括正则表达式)， 如果空格或者换行出现在前面，会被读取并抛弃

在后面的时候，不会读取，而只是检测

其实这里也可以写成scanf(“ %c”, &ch)【%c前面要加空格】，以过滤空格和回车。

• 7、head=idx++ <=> head=idx , idx++

• 8、根据1、3和5应该也就不难理解这句话了吧：

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

如果还是不理解，可以带入数据样例分析一下。

---

上述就是本节我所遇到的和参考大家的问题解答所总结的，对于像第一次面对这种数据结构的新手来说，反复的去查看评论解答很费时间，因此我再这里大概总结了大家的问题，并归纳了大家的解释，希望能够帮助到大家。

有不懂的问题，欢迎留言评论 (>▽<)

最近我也在更：数据结构复习之路（C语言版），针对的是开设此门课程的学校期末需要掌握的必学知识，有需要的可以看看，当然还没开设这门课程的同学，也可以尝试提前学习一下（写的超级详细）。

最后推荐大家去看大佬的详细题解：

大海呀大海：AcWing 826. 单链表 - AcWing

Hasity：AcWing 826. 单链表---图解 - AcWing