1

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

  • 计算文件中每个字符的出现次数，然后每个唯一字符（及其频率）将存储为新的树节点
  • 然后程序构建一个包含这些节点的最小堆，然后使用这个最小堆构建 Huffman 代码树。
  • 遍历（前序和有序）将被写入输出文件。树的每个内部节点都有标签 I:xxx，其中 xxx 是 int 标签，叶子有 L:xxx
  • 程序最终构建了一个表，其中包含存储为字符串的每个字符的编码（基于 ASCII，不是真正的 .bin 版本）

我想我会将每个节点存储在一个霍夫曼类中，如下所示：

struct CharNode {

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

我不确定从哪里开始。任何帮助将非常感激！

4

1 回答 1

1

首先使用一个数组，该数组的长度足以让您的应用程序识别的每个字符都有一个元素。现在遍历字符串，增加对应于它们的 ASCII 值的数组元素。（您可能需要减去初始 ASCII 值的某个基数，因此您开始计算 'a' 的第一个数组元素）

这部分也可以在 C 中相当容易地完成，因为它使用 chars 和 int 作为等价物。

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

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

祝你好运，编码愉快:)

于 2015-11-13T09:29:44.440 回答