AcWing
  • 首页
  • 活动
  • 题库
  • 竞赛
  • 应用
  • 其它
    • 题解
    • 分享
    • 商店
    • 问答
  • 吐槽
  • 登录/注册

AcWing 826. 为什么不用课本上学的结构体来构造链表等细节解答    原题链接    简单

作者: 作者的头像   Hasity ,  2022-02-21 22:23:51 ,  所有人可见 ,  阅读 2875


61


38

为什么不用课本上学的结构体来构造链表??

学过数据结构课的人,对链表的第一反应就是:

链表由节点构成,每个节点保存了 值 和 下一个元素的位置 这两个信息。节点的表示形式如下:

class Node{
public:
    int val;
    Node* next;
};

这样构造出链表节点的是一个好方法,也是许多人一开始就学到的。

使用这种方法,在创建一个值为 x 新节点的时候,语法是:

Node* node = new Node();
node->val = x

看一下创建新节点的代码的第一行:

Node* node = new Node();,中间有一个 new 关键字来为新对象分配空间。

new的底层涉及内存分配,调用构造函数,指针转换等多种复杂且费时的操作。一秒大概能new1w次左右。

在平时的工程代码中,不会涉及上万次的new操作,所以这种结构是一种 见代码知意 的好结构。

但是在算法比赛中,经常碰到操作在10w级别的链表操作,如果使用结构体这种操作,是无法在算法规定时间完成的。

所以,在算法比赛这种有严格的时间要求的环境中,不能频繁使用new操作。也就不能使用结构体来实现数组。


第 k 个插入的元素在哪里?

在本道题目中,有两个问题:

删除第 k 个插入的数后面的数

在第 k 个插入的数后插入一个数

先解释一下什么叫第k个插入的元素:

  • 把插入操作按先后排序,第 k 次执行插入操作的那个元素。
  • 并不是链表中从前往后数第 k 个元素。

在链表中删除指针指向的元素的后一个元素,或者在指针指向的某个元素后面插入一个新元素是很容易实现的。

所以,只要弄明白第 k 个插入的数的指针在哪里,这两个问题就很容易解决。

来分析一下插入操作:

  • 链表为空的时候:idx 的值为 0,
  • 插入第一个元素 a 后:e[0] = a, idx 的值变为 1,
  • 插入第二个元素 b 后:e[1] = b, idx 的值变为 2,
  • 插入第三个元素 c 后:e[2] = c, idx 的值变为 3,

所以: 第 k 个出入元素的索引值 k - 1。

有人会说,如果中间删除了某些元素呢?

在看一下伴随着删除操作的插入:

  • 链表为空的时候:idx 的值为 0,
  • 插入第一个元素 a 后:e[0] = a, idx 的值变为 1,
  • 插入第二个元素 b 后:e[1] = b, idx 的值变为 2,
  • 删除第一个插入的元素 a:head 变为 1, idx 不变,依旧为 2。
  • 删除第二个插入的元素 b:head 变为 2, idx 不变,依旧为 2。
  • 插入第三个元素 c 后:e[2] = c, idx 的值变为 3。

所以删除操作并不改变第 k 个插入元素的索引。

故第 k 个元素的索引一定是 k - 1。


题解:
head 表示头结点,e数组存储元素,ne数组存储下一个节点索引,indx表示下一个可以存储元素的位置索引。

头结点后面添加元素:

  • 在e的idx处存储元素e[ide] = x;

  • 该元素插入到头结点后面 ne[idx] = head;

  • 头结点指向该元素 head = idx;

  • idx 指向下一个可存储元素的位置 idx++。

在索引 k 后插入一个数

  • 在e的idx处存储元素e[index] = x

  • 该元素插入到第k个插入的数后面 ne[idx] = ne[k];

  • 第k个插入的数指向该元素 ne[k] = idx;

  • idx 指向下一个可存储元素的位置 idx++。

删索引为 k 的元素的后一个元素:

  • ne[k] 的值更新为 ne[ne[k]]
#include <iostream>
using namespace std;
const int N = 100010;

int head, e[N], ne[N], idx;

void init()
{
    head = -1;
    idx = 0;
}

void add_to_head(int x)
{
    e[idx] = x, ne[idx] = head, head = idx++;
}

void add(int k, int x)
{
    e[idx] = x, ne[idx] = ne[k], ne[k] = idx++;
}

void remove(int k)
{
    ne[k] = ne[ne[k]];
}

int main()
{
    int m;
    cin >> m;

    init();

    while(m--)
    {
        char op;
        int k, x;
        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);//第k个元素对应的索引为k - 1
        }
        else 
        {
            cin >> k >> x;
            add(k - 1, x);//第k个元素对应的索引为k - 1
        }
    }
    for(int i = head; i != -1; i = ne[i]) cout << e[i] << " ";

    cout<< endl;
}

如果有问题,直接评论,欢迎找bug

完结,撒花。求赞~~

17 评论


用户头像
笨死了   5天前      1    踩      回复

我帮大家大概总结了评论区的问题,欢迎来访问:
https://blog.csdn.net/m0_74215326/article/details/128770930


用户头像
cllll   1个月前      1    踩      回复

解决了删除操作会不会影响k的的疑惑,感谢


用户头像
wangxuzhou   14天前         踩      回复

“课本上”是什么意思


用户头像
ncust202102   20天前         踩      回复

请问头节点跟下标为0的点有什么区别吗


用户头像
ncust202102   20天前         踩      回复

太喜欢海绵宝宝了


用户头像
Sloth.   2个月前         踩      回复

大佬🐂bee


用户头像
rw-chen   4个月前         踩      回复

这就是静态链表,yyds


用户头像
2860251365   4个月前         踩      回复

应该是在头节点前插入


用户头像
xmm   5个月前         踩      回复

很详细,终于想通了idx,感谢


用户头像
路人_7   10个月前         踩      回复

其实可以直接 new 一大堆,或者new 也不用 ,直接 DLNode List(100010);


用户头像
magpieeeee   10个月前         踩      回复

idx 的值由0变为 1
idx 的值由1变为 2
。。。
这么写可能更容易理解一些?

用户头像
rw-chen   4个月前      1    踩      回复

idx就是一个游标,不断向前走,同时它还充当地址,了解一下链式向前星

用户头像
rw-chen   4个月前         踩      回复

其实就是头插法


用户头像
acwing_zzj   10个月前         踩      回复

第 k 个出入元素的索引值 k 吧


用户头像
Fibersensor   11个月前         踩      回复

静态链表也可以用结构体创建吧,一开始就分配好了空间,用数组创建是方便那些不支持指针的语言。


用户头像
time7   11个月前         踩      回复

赞


用户头像
只只觉得不妥   11个月前         踩      回复

刚看完数据结构的链表部分,深受启发,感谢启发思路


你确定删除吗?
1024
x

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