用C语言编程。输入ABCDEF六个字符的权值,根据权值用哈夫曼算法建立哈夫曼树,并进行哈夫曼编码,输出每个字符对应的哈夫曼编码。
时间: 2023-06-08 08:06:25 浏览: 62
好的,让我来回答您的问题。下面是一个用C语言编写的实现哈夫曼编码的代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CODE_LEN 256 // 哈夫曼编码最大长度
// 哈夫曼树节点结构体
typedef struct node {
int weight; // 权值
int parent, lchild, rchild; // 父节点、左右孩子节点下标
} node_t;
// 哈夫曼编码结构体
typedef struct code {
char ch; // 字符
char bits[MAX_CODE_LEN]; // 编码
} code_t;
// 选择两个节点中最小的节点
void select(node_t *nodes, int n, int *min1, int *min2) {
int i;
*min1 = *min2 = -1;
for (i = 0; i < n; i++) {
if (nodes[i].parent == -1) {
if (*min1 == -1 || nodes[i].weight < nodes[*min1].weight) {
*min2 = *min1;
*min1 = i;
} else if (*min2 == -1 || nodes[i].weight < nodes[*min2].weight) {
*min2 = i;
}
}
}
}
// 构建哈夫曼树
void huffman(node_t *nodes, int n) {
int i, j, min1, min2;
for (i = n; i < 2 * n - 1; i++) {
select(nodes, i, &min1, &min2);
nodes[min1].parent = nodes[min2].parent = i;
nodes[i].lchild = min1;
nodes[i].rchild = min2;
nodes[i].weight = nodes[min1].weight + nodes[min2].weight;
}
}
// 生成哈夫曼编码
void gen_huffman_code(node_t *nodes, int n, code_t *codes) {
char bits[MAX_CODE_LEN];
int i, j, parent, cur;
for (i = 0; i < n; i++) {
codes[i].ch = i + 'A';
bits[0] = '\0';
cur = i;
parent = nodes[cur].parent;
while (parent != -1) {
if (nodes[parent].lchild == cur) {
strcat(bits, "0");
} else {
strcat(bits, "1");
}
cur = parent;
parent = nodes[cur].parent;
}
// 需要翻转得到正确的哈夫曼编码
strrev(bits);
strcpy(codes[i].bits, bits);
}
}
// 输出哈夫曼编码表
void print_huffman_code_table(code_t *codes, int n) {
int i;
printf("Huffman Code Table:\n");
for (i = 0; i < n; i++) {
printf("%c: %s\n", codes[i].ch, codes[i].bits);
}
}
int main() {
int n = 6, i;
int weights[6] = {7, 5, 2, 4, 9, 8};
node_t nodes[2 * n - 1];
code_t codes[n];
memset(nodes, 0, sizeof(nodes));
memset(codes, 0, sizeof(codes));
for (i = 0; i < n; i++) {
nodes[i].weight = weights[i];
}
huffman(nodes, n);
gen_huffman_code(nodes, n, codes);
print_huffman_code_table(codes, n);
return 0;
}
```
上述代码中,我们先定义了一个`node_t`结构体表示哈夫曼树的节点,其中包括权值、父节点、左右孩子节点的下标信息;定义了一个`code_t`结构体表示哈夫曼编码,其中包括字符和编码信息。然后我们实现了选择两个节点中最小的节点的函数`select`、构建哈夫曼树的函数`huffman`、生成哈夫曼编码的函数`gen_huffman_code`和输出哈夫曼编码表的函数`print_huffman_code_table`。在`main`函数中,我们输入了6个字符的权值,然后调用上述函数进行哈夫曼编码,并输出哈夫曼编码表。
注意:上述代码中包含一些用于字符数组操作的辅助函数,比如`strcat`和`strrev`,可以访问这里了解详细实现。