优先级队列实现为单链接无法更新插入时的指针引用

问题描述 投票:0回答:2

问题编辑:如何在将指针引用保留为参数的同时插入到我的链表中?我的更新代码如下:

注意:我有一个队列的副本,用于将给定节点插入正确的位置,但是我没有看到更新原始队列,因为无法链接以前的节点。

已解决:工作优先级队列(FIFO) - 需要清理

#define QUEUE_HEAD_INDICATOR 0.0

namespace
{
    pq* create_node(float priority = 0, const string & text = "")
    {
        pq* q = new pq;
        q->priority = priority;
        q->text = text;
        q->next = nullptr;
        return q;
    }
}

pq* init_priority_queue() {
    return create_node(QUEUE_HEAD_INDICATOR);
}


void insert(pq* &queue, string text, float priority) {
    if (!queue) return;

    pq* prev = queue;
    pq* cursor = queue->next;
    int offset = 0;

    if(prev->priority == 0.0 && prev->text == "") {
        prev->priority = priority;
        prev->text = text;
        return;
    }
    if(!cursor) {
        if(prev->priority > priority) {
            pq* node = create_node(priority, text);
            node->next = prev;
            prev = node;
        } else {
            pq* node = create_node(priority, text);
            prev->next = node;
        }
    } else {
        while(cursor && cursor->priority < priority) {
            prev = cursor;
            cursor = cursor->next;
            offset++;
        }
        pq* node = create_node(priority, text);
        if(offset == 0) {
            if(cursor->priority == (int)node->priority) {
                node->next = prev->next;
                prev->next = node;
                queue = prev;
            } else {
                node->next = prev;
                prev = node;
                queue = prev;
            }
        } else if(!cursor) {
            prev->next = node;
        } else {
            node->next = prev->next;
            prev->next = node;
        }
        return;
    }
}


string remove(pq* &queue) {
    pq* prev = queue;
    pq* cursor = queue->next;

    if(!queue->next) {
        string text = queue->text;
        prev = NULL;
        return text;
    }

    while(cursor->next) {
        prev = cursor;
        cursor = cursor->next;
    }

    prev->next = NULL;
    string text = cursor->text;
    return text;
}

这是结构的样子

struct pq {
    float priority;
    string text;
    pq* next;
};
c++ pointers reference
2个回答
0
投票

我需要在这里做一个假设:queue是对指向链表头节点的指针的引用。这似乎是一个合理的假设,因为它在if(queue->next == NULL)案例中的使用方式。

以下代码将覆盖指向头节点的指针,并随后覆盖每个其他节点的指针。

while(queue->next && queue->next->key < priority) {
    queue = queue->next; // bam! previous node leaked back at the caller
}

您可以使用头节点的副本,但是...有更好的方法来处理这个问题。

我的建议是不要将指针传递给根节点。将指针传递给指向它的指针。这通过使头部看起来与每个其他节点完全一样并且消除了大部分代码来处理头部外壳。由于我们始终保持指向前一个节点的next的指针,因此我们可以轻松访问新节点和下一个节点的插入点。

您无法使用引用执行此操作,因为无法重新分配引用。

例:

#include <string>
#include <iostream>

// my best guess at what pq looks like
struct pq
{
    pq* next;
    std::string text;
    float key;
};

void insert(pq ** queue, // cannot reseat ref, so pointer required
            const std::string &text, // ref eliminates copy.
                                     // const because we don't want to change
            float priority) {
    while((*queue) && // search while more queues
            (*queue)->key < priority) // and priority is low
    {
        queue = &(*queue)->next;
    }
    *queue = new pq{*queue, // if queue is null, end of list, if not inserted in middle
                    text, 
                    priority}; 
}

// Demo
int main()
{
    pq * queue = NULL;

    insert(&queue, "c", 5);
    insert(&queue, "a", 1);
    insert(&queue, "b", 2.5);
    insert(&queue, "e", 10);
    insert(&queue, "d", 7.5);

    // print and clean-up.
    while (queue)
    {
        std::cout << queue->text << std::endl;
        pq * temp = queue; // temp so we don't lose queue
        queue = queue->next;
        delete temp; // release node
    }
}

0
投票

赋值queue = new_node指定insert函数的参数,但不指定链表中间的指针(这是前一个元素的next成员变量)。

    pq* qp = new pq;
    insert(qp, "0.1", 0.1f);
    // qp -> 0.1
    insert(qp, "0.3", 0.3f);
    // qp -> 0.1 -> 0.3
    insert(qp, "0.2", 0.2f);
    // qp -> 0.2 -> 0.3
    // qp now points to the 0.2 element, leaving the 0.1 element inaccessible

此外,您的函数永远不会将第一个元素的优先级与要为长度> 1的队列插入的元素的优先级进行比较。您的while循环仅将要插入的元素的优先级与第一个元素的优先级进行比较元件。

© www.soinside.com 2019 - 2024. All rights reserved.