Блог

Я новичок в C , и я создаю дерево Хаффмана, написанное на c , и у меня проблемы с созданием древовидной структуры. Вот мой код:

     void Huffman::generateTree() {
        std::vector<Node> nodes;
        for (auto itr : freq) {
            nodes.push_back(*(new Node(itr.first, itr.second)));
        }
        while (nodes.size() > 1) {
            Node::sort(amp;nodes);
            Node leftNode = nodes.back();
            nodes.pop_back();
            Node rightNode = nodes.back();
            nodes.pop_back();
            Node newAnode = *new Node();
            newAnode.merge(amp;leftNode,amp;rightNode);
            nodes.push_back(newAnode);
        }
        root = amp;nodes.back();
        displayTree();
    }
 

В конце концов он объединился в один узел, но левый узел и правый узел неверны:
(Для целей отладки каждый узел имеет случайный идентификатор при создании, так что я обнаружил проблему.)

 NODE freq26|id96
|-Left:
   NODE freq10|id17
   |-Left:
   |--ERROR:SELF freq10|id17
   |-Right:
      NODE freq16|id19
      |-Left:
         NODE freq10|id17
         |-Left:
         |--ERROR:SELF freq10|id17
         |-Right:
            NODE freq16|id19
            |-Left:
               NODE freq10|id17
               |-Left:
               |--ERROR:SELF freq10|id17
               |-Right:
                  NODE freq16|id19
...endless loop
 

Так же, как и вывод, начните с первого подузла, левый дочерний узел каждого узла является самостоятельным, а правый узел-другим узлом, но только два переключаются друг с другом и, наконец, зацикливаются.

Я искал и прочитал несколько сообщений об этом, и я знаю, что это может быть вызвано pop_back и push_back элементами вектора, указатель может указывать на другой элемент, но как я могу это решить? Есть ли какой-либо способ получить РЕАЛЬНЫЙ элемент в векторе, на который не влияет рабочий вектор?

Вот некоторые коды моего узла:

 //header
    class Node {
    private:
        char value;
        int frequency;
        Node *left;
        Node *right;
        String code;
...
    class Huffman{
    private:
        Node * root;
        std::map<char,int> freq;// calculated frequency of data
        bool generated;
//source
    bool Node::sortMethod::operator()(const Node amp;nodeA, const Node amp;nodeB) {
        return nodeA.getFrequency() > nodeB.getFrequency();//getFrequency(): simply return node's frequency int
    }
    void Node::sort(std::vector<Node> *nodes) {
        std::sort(nodes->begin(), nodes->end(), sortMethod());
    }
    Node *Node::merge(Node *pLeft, Node *pRight) {
        left = pLeft;
        right = pRight;
        frequency = left->getFrequency()   right->getFrequency();
        return this;
    }
 

Все полезное приветствуется, спасибо!

Как следует из комментариев, вам нужно перестать думать, что C похож на Java, на самом деле это не так.

Объекты в C имеют явное время жизни, и язык не мешает вам удерживать ссылку или указатель на объект после того, как он перестал существовать.

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

К сожалению, вы не можете с пользой std::priority_queue std::unique_ptr использовать значение , так как вы не можете перемещать top и pop не возвращаете значение. В противном случае я бы предложил использовать это, а не повторно внедрять.

Я не думаю, что вам нужно сортировать свои узлы в каждом цикле , так как объединенный узел всегда будет иметь наибольший frequency , поэтому они идут сзади.

 class Node;
// Aliases for types we will use
using NodePtr = std::unique_ptr<Node>;
using Nodes = std::vector<NodePtr>;

class Node {
private:
    char value;
    int frequency;
    NodePtr left;
    NodePtr right;
    std::string code;

    Node(char value, int frequency) : value(value), frequency(frequency) /*, code?*/{}
    Node(NodePtr left, NodePtr right) : /*value? ,*/ frequency(left->frequency   right->frequency), left(std::move(left)), right(std::move(right)) /*, code?*/{}
... 
};

// N.b. not members of Node
bool compareNodePtrs(const NodePtr amp; left, const NodePtr amp; right) {
    return left->getFrequency() > right->getFrequency();
}

void sortNodes(Nodes amp; nodes) {
    std::sort(nodes.begin(), nodes.end(), compareNodePtrs);
}

void Huffman::generateTree() {
    Nodes nodes;
    for (auto itr : freq) {
        nodes.emplace_back(std::make_unique<Node>(itr.first, itr.second));
    }
    sortNodes(nodes);
    while (nodes.size() > 1) {
        auto left = std::move(nodes.back());
        nodes.pop_back();
        auto right = std::move(nodes.back());
        nodes.pop_back();            
        nodes.emplace_back(std::move(left), std::move(right));
    }
    root = std::move(nodes.back());
    displayTree();
}