时间戳

首页 > 解决方案 > 霍夫曼编码的修改

c++ - 霍夫曼编码的修改

问题描述

当我学习霍夫曼编码时，我在处理优先级队列时遇到了一个问题。由于我不太擅长 cpp 请帮助。

这是代码

我试图做一些我迄今为止在 cpp 中学到的改变。在上面的 cpp 程序中，我更改了下面的部分代码

struct Node
{
    char ch;
    int freq;
    Node *left, *right;
};


struct comp
{
    bool operator()(Node* l, Node* r)
    {
        // highest priority item has lowest frequency
        return l->freq > r->freq;
    }

};

并将其用作功能priority_queue<Node*, vector<Node*>, comp> pq。buidingHuffmanTree()

我把它改成

struct Node
{
    char ch; 
    int freq;
    Node *left, *right;
    bool operator<(Node const& other) {
    return freq < other.freq;
}
};

现在我试着像使用它一样 priority_queue<Node*, vector<Node*>> pq

但我得到了错误的答案。在上面的程序输入是静态的，你可以看到答案是准确的（输入输出很大，我不能在这里写）

还试图改变标志freq > other.freq而不是<得到错误的答案

由于两段代码的工作方式不同，我认为它们将以相同的方式工作。

标签： c++priority-queuehuffman-code

解决方案

问题是您的队列存储指向对象的指针，Node而不是实际的Node对象实例本身。

该comp结构使用其函数调用运算符处理它，但您的成员operator<重载不处理指针。

更具体地说，对于成员运算符重载，左侧必须是对象实例（调用函数），而不是指针。

如果您不想使用仿函数对象而是想使用运算符重载，则可以创建一个以两个指针作为参数的非成员函数：

struct Node
{
    char ch; 
    int freq;
    Node *left, *right;

    // By using `friend` we declare this as a non-member function
    friend bool operator<(Node const* left, Node const* right)
        return left->freq < right->freq;
    }
};

推荐阅读