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

#c #pointers #reference

#c #указатели #ссылка

Вопрос:

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

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

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

Комментарии:

1. Почему вы пишете код C на C ?

2. @Yashasn Я не понимаю, почему это имеет значение, поскольку оно отлично соответствует, но не выполняется при вставке в середину.

Ответ №1:

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

Комментарии:

1. @smerlin Это очень помогло! Я не знал, что вы не могли отказаться от ссылок. Итак, если бы я хотел сохранить ту же структуру очереди, мне пришлось бы сделать что-то вроде создания новой функции, которая сохраняла бы каждую ссылку на указатель перед queue = очередь-> следующий

2. @usuer4581301 ^

3. @Garrett То, что я описал выше, должно быть адаптировано к вашей структуре очереди, не требуя вспомогательной функции, но я, возможно, чего-то не хватает в вашем конкретном случае. Подумайте о том, чтобы задать новый вопрос, чтобы вы могли предоставить более полный пример того, что у вас есть в настоящее время.

4. Я обновил основной вопрос. В этом конкретном случае мне действительно приходится использовать ссылку на указатель. Я смог изолировать свою проблему, создав копию связанного списка и вставив новый узел в правильное положение. Теперь моя исходная очередь неизменена, однако я все еще не решил, как вернуть остальную часть списка в правильное положение без перезаписи предыдущих узлов в очереди.

5. Вы не хотите создавать новую очередь. Вы попали в ловушку, имея особый случай для головного узла. Это отстой. Вам никогда не нужны особые случаи, даже если вы не можете этого избежать и должны стиснуть зубы и терпеть это. Мне придется вернуться к этому позже.

Ответ №2:

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