Очередь приоритетов реализована как односвязная, не обновляя указатель при вставке

Question

Вопрос отредактирован: как я могу вставить в свой связанный список, сохраняя ссылки на указатели в качестве аргументов?Мой обновленный код выглядит следующим образом:

Примечание. У меня есть копия очереди, которая использовалась при вставке данного узла в правильное место, однако я не вижу возможности обновить исходную очередь, поскольку нет возможностисвязать предыдущие узлы.

Решено: Очередь рабочих приоритетов (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;
};

Answer 1

Мне нужно сделать предположение здесь: 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
    }
}

Answer 2

Назначение queue = new_node присваивает аргумент функции вставки, но не указатель в середине связанного списка (который является 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 сравнивает только приоритет вставляемого элемента с приоритетами элементов за пределамипервый элемент.