AcWing 826. 单链表原题链接简单

作者：

大海呀大海 , 2020-07-13 11:39:40 , 所有人可见 , 阅读 14265

281

135

就这个题，看视频+理解+写代码+写题解，我呜呜呜，干了四小时了

我太菜了

#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;
}

53 评论

@v@ 3个月前

…… 写了半天发现这个k的定义搞错了，白写

是亦晴吖 4个月前

【刚开始的时候它负责指向空结点，在链表里有元素的时候，它变成了一个指向第一个元素的指针】.终于能解答我的疑惑了，大佬

需要时间 25天前

head一开始指向头节点，为-1，这是不存在节点的情况下
如果存在了节点，就将head的值换位头节点的下标，就从0开始一直到结束

奔马 2个月前

上面比喻的内容莫名的想笑hhh~

mouoAa631547 13天前

当代学生的精神状态（不是

yydsw2x 3个月前

一边看懂orz

寻光逐影 4个月前

tql orz

没有陷的包子 4个月前

这个是不是把idx初始的时候设成1下面就可以不用k-1了

arthur15 4个月前

是的实测可以AC

#include<iostream>

using namespace std;

const int N = 100010;

int m, k, x, idx = 1, e[N], ne[N];
char op;
int head = -1;

int main(){

    cin >> m;
    while(m-- > 0){
        cin >> op;
        if(op == 'H'){ // insert head
            cin >> x;
            e[idx] = x;
            ne[idx] = head;
            head = idx++;

        }else if(op == 'D'){ // delete after k
            cin >> k;
            if(k == 0) head = ne[head];
            else{
                ne[k] = ne[ne[k]];
            }

        }else{ // insert x after k
            cin >> k >> x;
            e[idx] = x;
            ne[idx] = ne[k];
            ne[k] = idx++;
        }
    }


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

是亦晴吖 4个月前

h[N] 数组没用到，删了也AC

TOKYOMI 4个月前

抽象的东西被你解释的通俗易懂，大佬无疑了~

OLIVEIRA 5个月前

收下弟弟的膝盖

OLIVEIRA 5个月前

yyds

C++小郑 5个月前

很强的

懒癌患者蓝玉 6个月前

很强很强

卡内基有龙 8个月前

可不可以理解成：head其实是dummy->next?
一开始dummy->next = nullptr;
从头插入的时候idx->next <=> ne[idx] = dummy->next <=> head;

狐誩 5个月前

head 就相当于就 dummyhead
dummyhead -> next 就是第一个链表吧

笙祎 8个月前

这个程序逻辑有个bug，idx一直增长，那数组链表如果删除了一些节点，这些节点的数组位就永远不可用了……例如1000个节点的链表，删掉990个，因为idx只能往前加，所以后面有990个空位空出来也用不了 :~

Littlecat 8个月前

稍微改良一下就可以了,不清空原表next域的情况下定义一个position索引,删除时回退就可以

Littlecat 8个月前

还有个方法就是，定义一个坏死率=无法利用/capacity，达到一定的阈值就重新洗牌。原有空间不够用申请新空间的时候也可以洗牌一次

李晓晗 2个月前回复了 Littlecat 的评论

刚好模拟就是内存分配的过程，也有点儿项磁盘碎片的清理

akakakakakak 9个月前

说说的我个人对idx的理解
先区分两个概念：
节点和结点
节点：一个点
结点：链表的元素，含e[idx],ne[idx]两个部分
e[idx]:结点编号为idx对应的节点值
ne[idx]：结点编号为idx对应的下一个结点的编号
区分完这两个概念应该能理解idx的作用，为结点编号
注意：存x->y时，e[idx]统一存的是y的值而不是x的值，这就是邻接表的定义没啥说的
区分完后插入函数就很容易理解，
为什么e[],ne[]数组直接对idx操作，为什么head里面存idx，是结点的编号值

akakakakakak 9个月前

这里说到邻接表不小心说超了sorry，注意的部分针对的是学完图论中的邻接表的插入函数的解释，与这里节点的插入很相似，没学的先略过即可

Cpt 9个月前

https://blog.csdn.net/weixin_49486457/article/details/122825779?spm=1001.2014.3001.5502

MYFJCHX 9个月前

$牛！^n$

Zake 10个月前

include[HTML_REMOVED]

using namespace std;

const int N = 100010;

//已经插入操作的元素，head为头节点
int idx,head;
//e[数组]表示值，ne[数组]表示下一个节点
int e[N],ne[N];

void init(){

head = -1;//-1表示空节点
idx = 0;//idx是表示当前的节点

}

//总共两步操作
//头节点添加节点
void add_head(int x){
e[idx] = x; //插入值
ne[idx] = head; //新的元素的指向head的指向，开始为-1，即为null
head = idx; //将头节点移动到新的元素节点
idx++; //添加一个数+1
}

//直接将元素的指向，指向下下元素的指向
void move(int k){

ne[k] = ne[ne[k]];

}

void add(int k,int x){

e[idx] = x;         //插入值
ne[idx] = ne[k];     //ne[idx]为新元素的指向，指向k的指向
ne[k] = idx;         //将k的元素指向新加入ne[idx]的下标
idx++;              //添加一个数+1

}

int main(){

int n,value,k ;
char opt;
scanf("%d",&n);
init();
while(n--){

    cin>>opt;

    switch(opt){

        case 'H':
            cin>>value;
            add_head(value);
            break;
        case 'D':
            cin>>k;
            if(!k) head =ne[head];
                else move(k-1);
            break;            
        case 'I':
            cin>>k>>value;
            add(k-1,value);
            break;            
    }

}

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

return 0;

}

aw7 10个月前

hso

AcWing 826. 单链表 原题链接 简单

就这个题，看视频+理解+写代码+写题解，我呜呜呜，干了四小时了

我太菜了

53 评论

include[HTML_REMOVED]

AcWing 826. 单链表原题链接简单