Блог

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

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

Решено: Рабочая очередь приоритетов (FIFO) — нуждается в очистке

 #define QUEUE_HEAD_INDICATOR 0.0

namespace
{
    pq* create_node(float priority = 0, const string amp; 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* amp;queue, string text, float priority) {
    if (!queue) return;

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

    if(prev->priority == 0.0 amp;amp; 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 amp;amp; 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* amp;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;
};
  

Здесь мне нужно сделать предположение: queue это ссылка на указатель на головной узел связанного списка. Это кажется разумным предположением из-за способа, которым оно используется в if(queue->next == NULL) случае.

Следующий код перезапишет указатель на головной узел, а впоследствии и на любой другой узел, пропуская его.

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

Вы могли бы использовать копию головного узла, но… Есть гораздо лучшие способы справиться с этим.

Моя рекомендация — не передавать указатель на корневой узел. Передайте указатель на указатель на него. Это обрабатывает регистр head, заставляя head выглядеть точно так же, как любой другой узел, и устраняет большую часть кода. Поскольку мы всегда сохраняем указатель на предыдущий узел 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 amp;text, // ref eliminates copy.
                                     // const because we don't want to change
            float priority) {
    while((*queue) amp;amp; // search while more queues
            (*queue)->key < priority) // and priority is low
    {
        queue = amp;(*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(amp;queue, "c", 5);
    insert(amp;queue, "a", 1);
    insert(amp;queue, "b", 2.5);
    insert(amp;queue, "e", 10);
    insert(amp;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
    }
}
  

Присваивание 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 сравнивает только приоритет элемента, который должен быть вставлен, с приоритетами элементов за пределами первого элемента.