c++ - 从最小堆C++创建霍夫曼代码树

假设您有一个C++程序，必须从给定的.txt文件中读取文本。该程序将:

计算文件中每个字符的出现次数，然后将每个唯一字符(及其频率)存储为新的树节点

然后，程序将构建包含这些节点的最小堆，然后使用此最小堆构建霍夫曼代码树。

遍历(预定和有序)将被写入输出文件。树的每个内部节点将具有标签I:xxx，其中xxx是int标签，而叶子具有L:xxx

该程序最终构造一个表，该表包含存储为字符串

的每个字符的编码(基于ASCII，不是真正的.bin版本)

我想我将每个节点存储在像这样的huffman类中:

struct CharNode {

      char value;
      int frequency;
      bool internal;
      int label;
      CharNode *parent;
      CharNode *left_child;
      CharNode *right_child;
};

我不确定在哪里继续。任何帮助将非常感激!

最佳答案

首先使用一个数组，该数组足够长，可以为应用程序应识别的每个字符都有一个元素。现在遍历字符串，以增加与它们的ASCII值相对应的数组元素。 (您可能需要减去初始ASCII值的某个基本数量，因此您开始依靠第一个数组元素为'a')

这部分也可以用C相当容易地完成，因为它使用char和ints作为等效项。

完成后，您将拥有所有字符及其出现的次数。现在，一旦开始构建树节点，就可以遍历数组。然后在那棵树上使用堆算法。

或者只是对数组排序，然后从那里开始构建树。

祝你好运，编码愉快:)

关于c++ - 从最小堆C++创建霍夫曼代码树，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/33688097/