V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
zgoing
V2EX  ›  C

C++ 的 queue 队列问题

  •  
  •   zgoing · 2016-03-15 11:50:10 +08:00 · 1794 次点击
    这是一个创建于 2095 天前的主题,其中的信息可能已经有所发展或是发生改变。

    用队列实现广度优先的树搜索,问题是在第一个 root 元素被 pop 之后,·idQueue.push(currentNode->rightNode);· 插入的不是右节点,而是之前被删除的 root 。请教各位朋友,这是什么原因呢。

    Node *findMaxIdNode(int w){
            queue<Node*> idQueue;
            idQueue.push(&root);
    
            while (!idQueue.empty()){
                Node *currentNode = idQueue.front();
                idQueue.pop();
                if (currentNode->weight == w && currentNode != &root){
                    return currentNode;
                }
                if (currentNode->rightNode){
                    idQueue.push(currentNode->rightNode);
                }
                if (currentNode->leftNode){
                    idQueue.push(currentNode->leftNode);
                }
            }
            return NULL;
        }
    
    12 条回复    2016-03-17 11:29:48 +08:00
    neoblackcap
        1
    neoblackcap  
       2016-03-15 12:43:50 +08:00
    我想说,能将代码全贴了吗?
    zgoing
        2
    zgoing  
    OP
       2016-03-15 14:44:00 +08:00
    @neoblackcap 全贴了太长, 200 行。。。
    neoblackcap
        3
    neoblackcap  
       2016-03-15 22:20:59 +08:00 via iPhone
    @zgoing 能贴一个最小可重现例子的代码吗?
    zgoing
        4
    zgoing  
    OP
       2016-03-16 10:33:31 +08:00
    @neoblackcap 谢谢你,问题解决了,是 clang 编译器的问题,换成 gcc 就好了
    araraloren
        5
    araraloren  
       2016-03-16 11:10:11 +08:00
    @zgoing 编译器 怎么会有问题。。严重怀疑。。。
    linghutf
        6
    linghutf  
       2016-03-16 12:37:12 +08:00 via Android
    队列头被你 pop 掉了,理论上说是指针会失效吧,过不过看编译器了
    neoblackcap
        7
    neoblackcap  
       2016-03-16 13:53:52 +08:00
    @linghutf 简单来说就是那个 currentNode 是悬空指针,任何操作都是未定义行为吧。
    @zgoing 你那段代码应该是有 bug ,你应该将 pop 操作放在最后再做或者返回结果前做。
    zgoing
        8
    zgoing  
    OP
       2016-03-16 16:49:01 +08:00 via iPhone
    @araraloren 确实是编译器的问题,两个编译器都没有报错,只是结果不一样。
    @linghutf 在进循环之前是有一个 push 的,不会 pop 队列头吧。这个函数是用队列做的广度优先的树搜索
    @neoblackcap 才开始用 c++,队列的第一个元素不是 push 进入的第一个元素吗
    linghutf
        9
    linghutf  
       2016-03-16 21:10:57 +08:00 via Android
    @zgoing 是第一个元素,但是你 pop 掉了, currentNode 指针你说现在它指向了哪个对象实例?少年感觉你基础没打牢啊
    zgoing
        10
    zgoing  
    OP
       2016-03-17 10:09:47 +08:00
    @linghutf 这个队列本身就是存的指针,用 currentNode 保存第一个元素之后,把队列里的 pop 出来, currentNode 的值不变
    araraloren
        11
    araraloren  
       2016-03-17 10:45:15 +08:00
    @zgoing 我没看你的代码,不过你要清楚,如果你的代码行为有`未定义的行为`,编译器是保证不了正确的。。
    linghutf
        12
    linghutf  
       2016-03-17 11:29:48 +08:00 via Android
    @zgoing 好吧,我看错了-_-||
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   2599 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 23ms · UTC 14:22 · PVG 22:22 · LAX 06:22 · JFK 09:22
    ♥ Do have faith in what you're doing.