3

我正在编写霍夫曼编码。这是我的程序的开始:

using namespace std;

//Counting methods
int *CountCharOccurence(string text)
{
    int *charOccurrence = new int[127];
    for(int i = 0; i < text.length(); i++)
    {
        charOccurrence[text[i]]++;
    }
    return charOccurrence;
}

void DisplayCharOccurence(int *charOccurrence)
{
    for(int i = 0; i < 127; i++)
    {
        if(charOccurrence[i] > 0)
        {
            cout << (char)i << ": " << charOccurrence[i] << endl;
        }
    }
}

//Node struct
struct Node
{
    public:
        char character;
        int occurrence;

        Node(char c, int occ) {
            character = c;
            occurrence = occ;
        }

        bool operator < (const Node* node)
        {
            return (occurrence < node->occurrence);
        }
};

void CreateHuffmanTree(int *charOccurrence)
{
    priority_queue<Node*, vector<Node*> > pq;
    for(int i = 0; i < 127; i++)
    {
        if(charOccurrence[i])
        {
            Node* node = new Node((char)i, charOccurrence[i]);
            pq.push(node);
        }
    }

    //Test
    while(!pq.empty())
    {
        cout << "peek: " << pq.top()->character <<  pq.top()->occurrence << endl;
        pq.pop();
    }
}

int main(int argc, char** argv) {

    int *occurrenceArray;
    occurrenceArray = CountCharOccurence("SUSIE SAYS IT IS EASY");
    DisplayCharOccurence(occurrenceArray);
    CreateHuffmanTree(occurrenceArray);

    return (EXIT_SUCCESS);
}

程序首先输出字符及其出现次数。这看起来不错:

: 4
A2
E:2
我:3
小号:6
电话:1
你:1
是:2

但是必须按优先级顺序显示节点内容的测试循环输出:

偷看:Y2
偷看:U1
窥视:S6
偷看:T1
偷看:I3
偷看:E2
窥视:4
窥视:A2

这不是预期的顺序。为什么?

4

3 回答 3

5

优先级队列中的元素是指针。由于您没有提供需要 2 个指向 Node 对象的指针的函数,因此默认比较函数会比较 2 个指针。

bool compareNodes(Node* val1, Node* val2)
{
   return val1->occurence < val2->occurence;
}
priority_queue<Node*, vector<Node*>,compareNodes > pq;

当 Node 与 Node* 进行比较时,使用您的运算符 <

于 2010-03-03T16:49:59.730 回答
1

您正在存储指向队列中节点的指针,但没有提供合适的比较函数,因此通过比较指针对它们进行排序。operator<您提供的会将节点与指针进行比较,这不是您想要的。

有两种选择:

  • 提供一个函数,根据它们的值比较两个节点指针,并将这个函数交给队列,或者
  • 将节点对象存储在队列中,并提供一个operator<比较两个节点。

第二个选项还将修复代码中的内存泄漏,并删除一大堆不必要的内存分配,所以我建议这样做。

于 2010-03-03T16:57:15.373 回答
1

你应该告诉你的优先队列它应该按什么排序。在您的情况下,您必须告诉它按Node::occurence.

于 2010-03-03T16:49:41.663 回答