Huffman编码的c语言实现与解释

Huffman编码是一种数据压缩算法，它通过统计待传输数据中各个符号出现的概率，将出现频率较高的符号用较短的编码表示，出现频率较低的符号用较长的编码表示，从而达到压缩数据的目的。

下面是Huffman编码的c语言实现与解释：

1. 定义结构体

首先，我们需要定义一个结构体来存储每个字符的出现频率和编码信息：

struct node {
    char symbol;
    int frequency;
    char *code;
    struct node *left;
    struct node *right;
};

其中，symbol表示字符，frequency表示字符出现的频率，code表示字符的编码，left和right分别表示左子树和右子树。

2. 统计字符频率

接下来，我们需要统计待传输数据中每个字符出现的频率。这里我们采用哈希表来实现：

void count_frequencies(char *data, int length, struct node **freq_array) {
    for (int i = 0; i < length; i++) {
        char c = data[i];
        if (freq_array[c] == NULL) {
            struct node *new_node = (struct node*) malloc(sizeof(struct node));
            new_node->symbol = c;
            new_node->frequency = 1;
            new_node->code = NULL;
            new_node->left = NULL;
            new_node->right = NULL;
            freq_array[c] = new_node;
        } else {
            freq_array[c]->frequency++;
        }
    }
}

其中，freq_array是一个指针数组，用于存储每个字符结点的指针。对于每个字符，如果在数组中不存在对应的结点，则新建一个结点；否则，将对应结点的频率加1。

3. 构建Huffman树

接下来，我们需要构建Huffman树。这里我们采用最小堆来实现：

struct node* build_huffman_tree(struct node **freq_array) {
    struct node *root = NULL;
    struct node *min1, *min2;
    struct heap *h = create_heap();

    for (int i = 0; i < 256; i++) {
        if (freq_array[i] != NULL) {
            insert(h, freq_array[i]);
        }
    }

    while (h->size > 1) {
        min1 = delete_min(h);
        min2 = delete_min(h);
        root = (struct node*) malloc(sizeof(struct node));
        root->symbol = '\0';
        root->frequency = min1->frequency + min2->frequency;
        root->code = NULL;
        root->left = min1;
        root->right = min2;
        insert(h, root);
    }

    root = delete_min(h);
    destroy_heap(h);
    return root;
}

其中，freq_array是一个指针数组，用于存储每个字符结点的指针。我们先将所有非空结点插入最小堆中。每次取出堆中最小的两个结点，将它们合并成一个新的结点，并将新结点插入堆中，直到堆中只剩下一个结点，即Huffman树的根结点。

4. 生成编码

接下来，我们需要生成每个字符的编码。这里我们采用递归方式实现：

void generate_code(struct node *root, char *prefix) {
    if (root == NULL) {
        return;
    }
    if (root->left == NULL && root->right == NULL) {
        root->code = strdup(prefix);
        return;
    }
    char *left_prefix = (char*) malloc(strlen(prefix) + 2);
    char *right_prefix = (char*) malloc(strlen(prefix) + 2);
    sprintf(left_prefix, "%s%c", prefix, '0');
    sprintf(right_prefix, "%s%c", prefix, '1');
    generate_code(root->left, left_prefix);
    generate_code(root->right, right_prefix);
    free(left_prefix);
    free(right_prefix);
}

其中，prefix表示前缀编码，初始值为一个空字符串。对于每个结点，如果它是叶子结点，则将前缀编码赋值给它的code字段；否则，分别递归地生成左子树和右子树的编码，前缀分别加上'0'和'1'，直到遍历完整个树。

5. 压缩数据

最后，我们可以根据生成的编码将原始数据压缩：

void compress_data(char *data, int length, struct node **freq_array) {
    for (int i = 0; i < length; i++) {
        char c = data[i];
        printf("%s", freq_array[c]->code);
    }
}

其中，data表示待压缩的数据，length表示数据长度，freq_array是一个指针数组，存储每个字符结点的指针。对于每个字符，输出它对应的编码即可。

完整代码如下：