我想实现一个函数，它给我一个二进制代码为每个字符在霍夫曼树。
为了实现这个函数，我尝试使用递归函数遍历表。但是我不知道如何填充每个 char 的二进制代码的结果，以便该函数返回一个包含所有 chars 和二进制代码的 struct 数组
我希望有人能指出我正确的方向。
谢谢提前！
3
好吧，让我们看看一个可能的解决方案：
#include <stdint.h>
typedef struct code {
size_t code_length;
uint32_t code;
} code;
void compute_code_table(tree_t node, code *t, code c)
{
if (node->left == NULL)
t[node->letter] = c;
else {
c.code_length++;
c.code <<= 1;
compute_code_table(node->left, t, c);
c.code += 1;
compute_code_table(node->right, t, c);
}
}
void code_print(code *c)
{
size_t n = c->code_length;
while (n --> 0)
putchar('0' + ((c->code >> n) & 1));
}
int main(void)
{
tree_t root = fixed_tree();
code table[256] = { 0 };
code c = { 0 };
compute_code_table(root, table, c);
for (size_t i = 0; i < 256; ++i) {
if (table[i].code_length) {
printf("%c\t", i);
code_print(table + i);
printf("\n");
}
}
}
如果我们在叶子上,我们只将代码存储在表中,否则我们需要执行递归:增加代码长度,在最低有效位中添加 0 并执行左分支,然后将 0 更改为 1 并执行右分支。
2
我将从compute_code_table递归开始，这使您可以轻松遍历树。
其次，它有助于每个任务或作业在线搜索一些来源，这些来源解释（无论是否使用伪代码）如何执行您的特定任务。
要生成一个 huffman 代码，你遍历树到你想要的值，每次你拿一个左分支时输出一个 0，每次你拿一个右分支时输出一个 1（通常你从你想要的代码向后遍历树，并向后构建二进制 huffman 编码字符串，因为第一位必须从顶部开始）。
siggraph.org在 C 中，这可以实现为：
int compute_code_table_for_node(tree_t tree, node_t target_node, node_t current_node, int code_table) {
// Check for target
if ( current_node == target_node ) {
// Found target
return code_table;
}
// Check if end-node
if ( current_node->left == NULL && current_node->right == NULL ) {
// Is an end node
return -1;
}
// Try left
int left = compute_code_table_for_node(tree, target_node, current_node->left, code_table << 1 + 0);
// Try right
int right = compute_code_table_for_node(tree, target_node, current_node->right, code_table << 1 + 1);
// Find which path was taken
if ( left == -1 ) {
// Left path didn't find it, so it must be the right path:
return code_table << 1 + 1;
} else {
// Left path found it
return code_table << 1 + 0;
}
}
然后，您只需要为tree中的每个node调用compute_code_table_for_node(tree, node, tree->head, 0)。
这段代码不适用于您的特定情况，因此您必须重写它。
本站系公益性非盈利分享网址，本文来自用户投稿，不代表边看边学立场，如若转载，请注明出处
评论列表（21条）