самоопределения узла в цикле enqueing

Question

Я реализую кодировщик Хаффмана. Деревья Хаффмана строятся снизу вверх с использованием очереди приоритетов. У меня есть простой класс узлов с указателями на два других узла. Цикл, который строит дерево:

while(q.size() > 1) 
{ 
    huffnode n1 = q.top(); 
    q.pop(); 
    huffnode n2 = q.top(); 
    q.pop(); 

    q.push(huffnode((char)0, n1.freq+n2.freq, &n1, &n2)); 
} 

Оставшийся узел, когда цикл завершается корень дерева.

Этот код выглядит достаточно невинно, но на моем тестовом входе он дает дерево, где правый ребенок корня указывает на себя и на левый дочерний корень, а не на два узла, которые только что выскочили из очереди. Я подтвердил, что очередь сортируется правильно.

Я думаю, что n1 и n2 являются локальными переменными, которые всегда имеют один и тот же адрес, как показано в отладчике. Когда новый узел нажат, он указывает на эти адреса. Когда этот узел появляется позже, его копия попадает в один из этих адресов, один из которых он уже указывает, поэтому он указывает на себя.

Как это исправить? Я не могу сделать n1 и n2 указателей, потому что тогда они должны быть const так сверху() возвращает константную ссылку, и назначая результат сверху() к константной ссылке или константный указатель делает очередь неизменна.

Answer 1

Когда у вас есть фигурные скобки {}, вы находитесь в новом объеме. и переменные, объявленные в этой области, являются локальными для этой области и действительны только внутри этой области. Когда область действия заканчивается, то для вас ваш цикл будет каждый раз, когда цикл будет итерации, область исчезнет, ​​а переменные в этой области будут уничтожены и больше не будут существовать.

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

Answer 2

C++ не содержит сборку мусора и не выделяет объекты на кучу, если вы не сообщите об этом - вам нужно самостоятельно управлять своей памятью.

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

Как уже упоминалось другие, ваши huffnode переменные n1 и n2 локальные переменные и уничтожаются, когда они выходят из области видимости (который, каждый проход вашего while цикла).

Answer 3

гроза - правый. Мне нужно использовать new.

Фиксированный код

while(q.size() > 1) 
{ 
    huffnode* n1 = new huffnode(q.top().data, q.top().freq, q.top().left, q.top().right); 
    q.pop(); 
    huffnode* n2 = new huffnode(q.top().data, q.top().freq, q.top().left, q.top().right); 
    q.pop(); 

    q.push(huffnode((char)0, n1->freq + n2->freq, n1, n2)); 
}