哈夫曼编码:我如何生成一个哈夫曼树的二进制代码表

我想实现一个函数,它给我一个二进制代码为每个字符在霍夫曼树。

为了实现这个函数,我尝试使用递归函数遍历表。但是我不知道如何填充每个 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)

这段代码不适用于您的特定情况,因此您必须重写它。

本站系公益性非盈利分享网址,本文来自用户投稿,不代表边看边学立场,如若转载,请注明出处

(430)
Admin er:ER建模问题(garage modelling)
上一篇
小程序主图尺寸:小程序:窗口以较小的尺寸打开
下一篇

相关推荐

发表评论

登录 后才能评论

评论列表(49条)