AcWing 826. 单链表
原题链接
简单
作者:
大海呀大海
,
2020-07-13 11:39:40
,
所有人可见
,
阅读 33555
就这个题,看视频+理解+写代码+写题解,我呜呜呜,干了四小时了
我太菜了
#include <iostream>
using namespace std;
const int N = 100010;
int n;
int h[N], e[N], ne[N], head, idx;
//对链表进行初始化
void init(){
head = -1;//最开始的时候,链表的头节点要指向-1,
//为的就是在后面进行不断操作后仍然可以知道链表是在什么时候结束
/*
插句题外话,我个人认为head其实就是一个指针,是一个特殊的指针罢了。
刚开始的时候它负责指向空结点,在链表里有元素的时候,它变成了一个指向第一个元素的指针
当它在初始化的时候指向-1,来表示链表离没有内容。
*/
idx = 0;//idx在我看来扮演两个角色,第一个是在一开始的时候,作为链表的下标,让我们好找
//第二在链表进行各种插入,删除等操作的时候,作为一个临时的辅助性的所要操作的元素的下
//标来帮助操作。并且是在每一次插入操作的时候,给插入元素一个下标,给他一个窝,感动!
/*
再次插句话,虽然我们在进行各种操作的时候,元素所在的下标看上去很乱,但是当我们访问的
时候,是靠着指针,也就是靠ne[]来访问的,这样下标乱,也就我们要做的事不相关了。
另外,我们遍历链表的时候也是这样,靠的是ne[]
*/
}
//将x插入到头节点上
void int_to_head(int x){//和链表中间插入的区别就在于它有head头节点
e[idx] = x;//第一步,先将值放进去
ne[idx] = head;//head作为一个指针指向空节点,现在ne[idx] = head;做这把交椅的人换了
//先在只是做到了第一步,将元素x的指针指向了head原本指向的
head = idx;//head现在表示指向第一个元素了,它不在是空指针了。(不指向空气了)
idx ++;//指针向下移一位,为下一次插入元素做准备。
}
//将x插入到下标为k的点的后面
void add(int k, int x){
e[idx] = x;//先将元素插进去
ne[idx] = ne[k];//让元素x配套的指针,指向它要占位的元素的下一个位置
ne[k] = idx;//让原来元素的指针指向自己
idx ++;//将idx向后挪
/*
为了将这个过程更好的理解,现在
将指针转变的这个过程用比喻描述一下,牛顿老师为了省事,想插个队,队里有两个熟人
张三和李四,所以,他想插到两个人中间,但是三个人平时关系太好了,只要在一起,就
要让后面的人的手插到前面的人的屁兜里。如果前面的人屁兜里没有基佬的手,将浑身不
适。所以,必须保证前面的人屁兜里有一只手。(张三在前,李四在后)
这个时候,牛顿大步向前,将自己的手轻轻的放入张三的屁兜里,(这是第一步)
然后,将李四放在张三屁兜里的手抽出来放到自己屁兜里。(这是第二步)
经过这一顿骚操作,三个人都同时感觉到了来自灵魂的战栗,打了个哆嗦。
*/
}
//将下标是k的点后面的点个删掉
void remove(int k){
ne[k] = ne[ne[k]];//让k的指针指向,k下一个人的下一个人,那中间的那位就被挤掉了。
}
int main(){
cin >> n;
init();//初始化
for (int i = 0; i < n; i ++ ) {
char s;
cin >> s;
if (s == 'H') {
int x;
cin >> x;
int_to_head(x);
}
if (s == 'D'){
int k;
cin >> k;
if (k == 0) head = ne[head];//删除头节点
else remove(k - 1);//注意删除第k个输入后面的数,那函数里放的是下标,k要减去1
}
if (s == 'I'){
int k, x;
cin >> k >> x;
add(k - 1, x);//同样的,第k个数,和下标不同,所以要减1
}
}
for (int i = head; i != -1; i = ne[i]) cout << e[i] << ' ' ;
cout << endl;
return 0;
}
我帮大家大概总结了评论区的问题,欢迎来访问:
https://blog.csdn.net/m0_74215326/article/details/128770930
可以,总结的很好
顶你上去
棒
棒棒
为什么把cin>>op换成 scanf(“%c”,&op);就只能输入一部分
我就不理解 为什么我用scanf读入数据 只能读取一半的数据 愁死
scanf读入数据遇到换行会停止读入
用cin读就行了
可是我用的c语言 😂😂感谢哥们百忙之中帮我解惑了 感谢
假如有n个数据,每读入一个数据都要换行的话,用scanf读入,你就得读入2n次
哦哦。 感谢老哥 妙
可以加个空格就好了把
6
H 9
H 4
H 6
H 2
H 3
D 1 为什么 D 1 会出现超时呀, D2 就不会, 想不懂
你k是不是减了两次1
上面比喻的内容莫名的想笑hhh~
当代学生的精神状态(不是
【刚开始的时候它负责指向空结点,在链表里有元素的时候,它变成了一个指向第一个元素的指针】
.终于能解答我的疑惑了,大佬你这比喻,,,好闷骚
head一开始指向头节点,为-1,这是不存在节点的情况下
如果存在了节点,就将head的值换位头节点的下标,就从0开始一直到结束
简单明了 顶上去 上面博主罗里吧嗦
### 怎么哪里都有你笑死
…… 写了半天发现这个k的定义搞错了,白写
为啥输入s的时候用scanf(“%c”, &s);会出错啊,其他一模一样
你可能需要再写一个getchar(),因为你的s可能读入你输入整型数据之后输的enter键了\0
if (k == 0) head = ne[head];//删除头节点 是什么原理,大佬求教
删除头结点,那么原来头结点的下一个结点 就会成为 新的头结点。
我听我们老师说是题目表述不清,他说这个头节点是指第一个节点而不是储存空的节点
这个地方把head叫做头指针会更准确一点
原来是删除头指针指向的节点,我还以为是把整个表删除呢?原来如此,阿里嘎多
//head = ne[head];的含义是,将head更新为它当前所指节点(即原头节点)的下一个节点的索引。ne[head]存储了原头节点指向的下一个节点的索引。 比喻的话,就相当于,小红拉着小李拉着小明 变成了,小红拉着小明
https://www.acwing.com/blog/content/8247/
看完双链表后,发现将 ne[0] 设为头节点实在是太方便了!!!
提神醒脑的比喻
6
H 9
H 4
H 6
H 2
H 3
D 1 为什么 D 1 会出现超时呀, D2 就不会, 想不懂
我也发现了
是因为1 是最后一个元素, 删除函数的中语法有错, 会空指针, 所以报错
是的,想了半天,以为题错了
哈哈屁兜里没有基佬的手就不自在
大佬请问main函数里的 init()具体作用是什么呢?
初始化head和idx
太详细了!!需要这种注释!!%%%
说说的我个人对idx的理解
先区分两个概念:
节点和结点
节点:一个点
结点:链表的元素,含e[idx],ne[idx]两个部分
e[idx]:结点编号为idx对应的节点值
ne[idx]:结点编号为idx对应的下一个结点的编号
区分完这两个概念应该能理解idx的作用,为结点编号
注意:存x->y时,e[idx]统一存的是y的值而不是x的值,这就是邻接表的定义没啥说的
区分完后插入函数就很容易理解,
为什么e[],ne[]数组直接对idx操作,为什么head里面存idx,是结点的编号值
这里说到邻接表不小心说超了sorry,注意的部分针对的是学完图论中的邻接表的插入函数的解释,与这里节点的插入很相似,没学的先略过即可
天才的比喻,是我根本想不到的
h[N] 在代码里好像没有用到呀
//head = ne[head];的含义是,将head更新为它当前所指节点(即原头节点)的下一个节点的索引。ne[head]存储了原头节点指向的下一个节点的索引。