非常推荐大家打卡 y总的算法基础课: https://www.acwing.com/activity/content/11/
这里的问题也是基于他讲的单链表所总结的。
题目:
实现一个单链表,链表初始为空,支持三种操作:
(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
所有操作保证合法。
输入样例:10H 9I 1 1D 1D 0H 6I 3 6I 4 5I 4 5I 3 4D 6输出样例:6 4 6 5
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;}
head是什么?它的具体作用又是啥?
答:head应该是一个特殊的指针,一开始指向-1,表示链表里没有内容,为空节点,
当链表里有元素的时候,它变成了一个指向第一个元素的指针。还有就是为了最后遍历链表时,知道链表什么时候结束(因为最后实现的链表,它最后一个节点的ne[i]一定等于-1)
对于k-1的相关问题?
这个函数含义是 将x插到下标是k的点后面
题目里要将x插入到第k个插入的数后面,第k个插入的数下标是k - 1,所以调用的时候是add(k - 1, x),remove(k-1)。如果你一开始将idx=1(初始化),那么下标和k就统一了,就不需要再k-1了。
关于e[idx]、en[idx]和idx的问题?
idx可以理解为一个结点!!
结点:链表的元素,含e[idx],ne[idx]两个部分
e[idx]:结点编号为idx对应的节点值
ne[idx]:结点编号为idx对应的下一个结点的编号
要明白idx只是记录当前的操作的位置,一般实现的链表idx是乱序的(前后的节点的数组下标不需要连续【不理解,可以带入样例观察】),需要通过当前的ne[i]找到下一个idx。这也是两者的联系。
对于删除头节点:head=ne[head]的操作?
删除头结点是head指向的结点,也就是链表中的第一个结点,head指向可能是一个空结点(e数组不存值),或者是非空结点。指向空结点的叫头结点,指向非空结点的叫首元结点。但是y总并没有区分这个概念,所以删除头结点就是删除链表的第一个有值的结点,head指向ne[head]是因为head本来就指向它的下一个结点,所以ne[head]就是头结点的下一个结点。
为什么最后一个节点的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。
为什么每次循环输入的字符ch,用cin>>ch可以ac,而scanf(“%c”,&ch)结果就不行?
这个是分情况的。
有一个特殊的格式 %c
当%c格式的时候,会读取任何字符,包括换行和空格。
当其他格式的时候(不包括正则表达式), 如果空格或者换行出现在前面,会被读取并抛弃
在后面的时候,不会读取,而只是检测
其实这里也可以写成scanf(“ %c”, &ch)【%c前面要加空格】,以过滤空格和回车。
head=idx++ <=> head=idx , idx++
根据1、3和5应该也就不难理解这句话了吧:
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ';
如果还是不理解,可以带入数据样例分析一下。
上述就是本节我所遇到的和参考大家的问题解答所总结的,对于像我这样的新手来说,反复的去查看评论解答很费时间,因此我再这里大概总结了大家的问题,并归纳了大家的解释,希望能够帮助到大家。
有不懂的问题,欢迎留言评论 (>▽<)
最后推荐大家去看大佬的详细题解:
大海呀大海:https://www.acwing.com/file_system/file/content/whole/index/content/1088923/
Hasity:https://www.acwing.com/file_system/file/content/whole/index/content/4008335/