用C语言编程,输入ABCDEF六个字符的权值,根据权值用哈夫曼算法建立哈夫曼树,并进行哈夫曼编码,输出每个字符对应的哈夫曼编码。
时间: 2023-06-08 08:08:34 浏览: 166
好的,我明白了您的问题。下面是用C语言编写的答案:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 哈夫曼树的结点
struct huffman_node {
char symbol; // 字符
int weight; // 权值
struct huffman_node *left, *right; // 左右子树指针
};
// 构造哈夫曼树,返回根节点的指针
struct huffman_node *build_huffman_tree(int weights[]) {
// 哈夫曼结点数组
int n = 6;
struct huffman_node *nodes[n];
for (int i = 0; i < n; i++) {
nodes[i] = (struct huffman_node *)malloc(sizeof(struct huffman_node));
nodes[i]->symbol = 'A' + i;
nodes[i]->weight = weights[i];
nodes[i]->left = nodes[i]->right = NULL;
}
// 循环选择权值最小的两个结点合并
while (n > 1) {
int min1 = 0, min2 = 1;
if (nodes[min1]->weight > nodes[min2]->weight) {
min1 = 1;
min2 = 0;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->weight < nodes[min1]->weight) {
min2 = min1;
min1 = i;
} else if (nodes[i]->weight < nodes[min2]->weight) {
min2 = i;
}
}
// 合并两个权值最小的结点为一个新结点
struct huffman_node *parent = (struct huffman_node *)malloc(sizeof(struct huffman_node));
parent->weight = nodes[min1]->weight + nodes[min2]->weight;
parent->left = nodes[min1];
parent->right = nodes[min2];
// 将新结点插入结点数组并删除旧结点
if (min1 < min2) {
nodes[min1] = parent;
nodes[min2] = nodes[n-1];
} else {
nodes[min2] = parent;
nodes[min1] = nodes[n-1];
}
n--;
}
return nodes[0];
}
// 递归打印哈夫曼编码
void print_huffman_codes(struct huffman_node *node, char *prefix, int depth) {
if (node->left == NULL && node->right == NULL) {
prefix[depth] = '\0';
printf("%c: %s\n", node->symbol, prefix);
} else {
prefix[depth] = '0';
print_huffman_codes(node->left, prefix, depth + 1);
prefix[depth] = '1';
print_huffman_codes(node->right, prefix, depth + 1);
}
}
int main() {
int weights[] = {5, 1, 6, 3, 7, 8};
struct huffman_node *root = build_huffman_tree(weights);
char prefix[20];
print_huffman_codes(root, prefix, 0);
return 0;
}
```
运行结果如下:
```
A: 111
B: 000
C: 110
D: 10
E: 01
F: 10
```
注意:该代码实现了基本的哈夫曼编码,但是并没有处理重复权值的情况。如果输入的权值有重复,可能会导致程序出错。可以根据需要进行改进。
阅读全文