C语言实现霍夫曼树全代码

以下是C语言实现霍夫曼树的完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODE_NUM 1000

struct huffman_node {
    char ch;
    int freq;
    int left_child;
    int right_child;
};

void swap(struct huffman_node *a, struct huffman_node *b) {
    struct huffman_node temp = *a;
    *a = *b;
    *b = temp;
}

void sort(struct huffman_node *node_list, int node_num) {
    for (int i = 0; i < node_num; i++) {
        for (int j = i + 1; j < node_num; j++) {
            if (node_list[i].freq > node_list[j].freq) {
                swap(&node_list[i], &node_list[j]);
            }
        }
    }
}

void build_huffman_tree(struct huffman_node *node_list, int node_num) {
    int parent = node_num;
    while (1) {
        sort(node_list, node_num);
        if (node_num == 1) {
            break;
        }
        struct huffman_node new_node;
        new_node.ch = '\0';
        new_node.freq = node_list[0].freq + node_list[1].freq;
        new_node.left_child = node_list[0].freq < node_list[1].freq ? 0 : 1;
        new_node.right_child = node_list[0].freq >= node_list[1].freq ? 0 : 1;
        node_list[0] = new_node;
        node_list[1] = node_list[node_num - 1];
        node_num--;
    }
}

void print_huffman_code(struct huffman_node *node_list, int node_index, char *code, int depth) {
    if (node_list[node_index].ch != '\0') {
        printf("%c: %s\n", node_list[node_index].ch, code);
    } else {
        code[depth] = '0';
        print_huffman_code(node_list, node_list[node_index].left_child, code, depth + 1);
        code[depth] = '1';
        print_huffman_code(node_list, node_list[node_index].right_child, code, depth + 1);
    }
}

void huffman_encoding(char *text) {
    int freq_table[256] = {0};
    int len = strlen(text);
    for (int i = 0; i < len; i++) {
        freq_table[text[i]]++;
    }
    int node_num = 0;
    struct huffman_node node_list[MAX_NODE_NUM];
    for (int i = 0; i < 256; i++) {
        if (freq_table[i] > 0) {
            struct huffman_node node;
            node.ch = i;
            node.freq = freq_table[i];
            node.left_child = -1;
            node.right_child = -1;
            node_list[node_num++] = node;
        }
    }
    build_huffman_tree(node_list, node_num);
    char code[256] = "";
    print_huffman_code(node_list, node_num - 1, code, 0);
}

int main() {
    char text[] = "hello, world";
    huffman_encoding(text);
    return 0;
}

代码中包含了几个函数：

- `swap`：交换两个结构体的值
- `sort`：根据结点频率排序
- `build_huffman_tree`：构建霍夫曼树
- `print_huffman_code`：打印霍夫曼编码
- `huffman_encoding`：对给定文本进行霍夫曼编码

在 `main` 函数中，我们指定了要编码的文本为 `"hello, world"`，并调用了 `huffman_encoding` 函数进行编码。编码的结果将会在控制台中输出。