假设您有一个 C++ 程序,它必须从给定的 .txt 文件中读取文本。该计划将:
- 计算文件中每个字符出现的次数,然后每个唯一字符(及其出现频率)将存储为一个新的树节点
- 程序然后构建一个包含这些节点的最小堆,然后使用这个最小堆构建霍夫曼代码树。
- 遍历(前序和中序)将写入输出文件。树的每个内部节点都会有标签 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;
};
我不确定从哪里开始。任何帮助将不胜感激!
最佳答案
首先使用一个数组,该数组的长度足以让您的应用程序应识别的每个字符都有一个元素。现在遍历字符串并增加与其 ASCII 值对应的数组元素。 (您可能需要减去初始 ASCII 值的某个基数,因此您开始计算“a”的第一个数组元素)
这部分在 C 中也可以很容易地完成,因为它使用 chars 和 ints 作为等价物。
完成后,您将获得所有字符及其出现次数。现在您可以在开始构建树节点后遍历数组。并在那棵树上使用堆算法。
或者只是对数组进行排序,然后从那里开始构建您的树。
祝你好运,编码愉快:)
关于c++ - 从最小堆 C++ 创建霍夫曼代码树,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33688097/