(数据结构)哈夫曼编码实现（C语言）

**哈夫曼编码实现**
=====================哈夫曼编码是一种变长的前缀编码，通过构造一个二叉树来压缩数据。这种编码方式可以有效地减少数据的大小，从而提高存储和传输效率。

在本文中，我们将使用C语言实现哈夫曼编码的基本算法和数据结构。

**哈夫曼树**
------------首先，让我们定义一个哈夫曼树的结构：

ctypedef struct Node {
 int freq; // 节点频率 char symbol; // 节点符号 struct Node* left;
 struct Node* right;
} Node;

cvoid build_frequency_table(char* symbols, int num_symbols) {
 // 初始化频率表 for (int i =0; i < num_symbols; i++) {
 frequency_table[symbols[i]].freq =0;
 }

 // 统计符号频率 for (int i =0; i < num_symbols; i++) {
 frequency_table[symbols[i]].freq++;
 }
}

cvoid build_huffman_tree(Node* nodes, int num_nodes) {
 // 初始化哈夫曼树 for (int i =0; i < num_nodes; i++) {
 huffman_tree[i] = nodes[i];
 }

 // 构造哈夫曼树 while (num_nodes >1) {
 // 找到频率最小的两个节点 int min_freq_node1 = -1;
 int min_freq_node2 = -1;
 for (int i =0; i < num_nodes; i++) {
 if (min_freq_node1 == -1 || huffman_tree[i].freq < huffman_tree[min_freq_node1].freq) {
 min_freq_node2 = min_freq_node1;
 min_freq_node1 = i;
 } else if (min_freq_node2 == -1 || huffman_tree[i].freq < huffman_tree[min_freq_node2].freq) {
 min_freq_node2 = i;
 }
 }

 // 合并两个节点 Node* new_node = malloc(sizeof(Node));
 new_node->freq = huffman_tree[min_freq_node1].freq + huffman_tree[min_freq_node2].freq;
 new_node->symbol = '0';
 new_node->left = &huffman_tree[min_freq_node1];
 new_node->right = &huffman_tree[min_freq_node2];

 // 替换频率最小的两个节点 for (int i =0; i < num_nodes; i++) {
 if (i == min_freq_node1 || i == min_freq_node2) {
 huffman_tree[i] = *new_node;
 break;
 }
 }

 // 更新哈夫曼树大小 num_nodes--;
 }
}

cvoid build_huffman_code(Node* root, int code[], char symbol) {
 if (root == NULL) return;

 // 如果是叶子节点，则记录编码 if (root->left == NULL && root->right == NULL) {
 code[symbol] = root->freq;
 return;
 }

 // 递归构造编码 build_huffman_code(root->left, code, symbol);
 build_huffman_code(root->right, code, symbol);
}

cint main() {
 char symbols[] = {'A', 'B', 'C'};
 int num_symbols = sizeof(symbols) / sizeof(symbols[0]);

 // 构造频率表 build_frequency_table(symbols, num_symbols);

 // 构造哈夫曼树 Node nodes[num_symbols];
 for (int i =0; i < num_symbols; i++) {
 nodes[i].freq = frequency_table[symbols[i]].freq;
 nodes[i].symbol = symbols[i];
 nodes[i].left = NULL;
 nodes[i].right = NULL;
 }
 build_huffman_tree(nodes, num_symbols);

 // 构造哈夫曼编码 int code[num_symbols];
 for (int i =0; i < num_symbols; i++) {
 build_huffman_code(&huffman_tree[i], code, symbols[i]);
 }

 // 输出哈夫曼编码 printf("哈夫曼编码:
");
 for (int i =0; i < num_symbols; i++) {
 printf("%c: %d
", symbols[i], code[i]);
 }

 return0;
}