AcWing
  • 首页
  • 题库
  • 题解
  • 分享
  • 问答
  • 活动
  • 应用
  • 吐槽
  • 登录/注册

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

作者: 作者的头像   大海呀大海 ,  2020-07-13 11:39:40 ,  阅读 547


16


4

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

我太菜了

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

6 评论


用户头像
rickwang   1个月前     回复

加油!!


用户头像
7年级的蒟蒻   7个月前     回复

很棒,学习的正确方式!


用户头像
folly   7个月前     回复

加油~


用户头像
0918k   7个月前     回复

加油~


用户头像
NikolaTesla   7个月前     回复

加油!

用户头像
大海呀大海   7个月前     回复

加油

你确定删除吗?

© 2018-2021 AcWing 版权所有  |  京ICP备17053197号-1
联系我们  |  常见问题
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标
请输入绑定的邮箱地址
请输入注册信息