用C语言构造哈夫曼树及哈夫曼编码,假设输入的数据如下,输出每个字符对应的哈夫曼编码以及平均编码长度。
时间: 2023-07-19 19:08:10 浏览: 103
好的,下面是一个用C语言实现构造哈夫曼树及哈夫曼编码的示例代码,假设输入的数据为字符串"ABBCCCDDDDEEEEE":
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_NODE_NUM 100
typedef struct HuffmanNode {
char ch;
int freq;
int parent;
int lchild;
int rchild;
} HuffmanNode;
void initHuffmanTree(HuffmanNode* tree, char* str) {
int cnt[256] = {0};
int len = strlen(str);
for (int i = 0; i < len; i++) {
cnt[str[i]]++;
}
int nodeNum = 0;
for (int i = 0; i < 256; i++) {
if (cnt[i] > 0) {
tree[nodeNum].ch = (char)i;
tree[nodeNum].freq = cnt[i];
tree[nodeNum].parent = -1;
tree[nodeNum].lchild = -1;
tree[nodeNum].rchild = -1;
nodeNum++;
}
}
}
void buildHuffmanTree(HuffmanNode* tree, int nodeNum) {
for (int i = nodeNum; i < 2 * nodeNum - 1; i++) {
int min1 = -1, min2 = -1;
for (int j = 0; j < i; j++) {
if (tree[j].parent == -1) {
if (min1 == -1 || tree[j].freq < tree[min1].freq) {
min2 = min1;
min1 = j;
} else if (min2 == -1 || tree[j].freq < tree[min2].freq) {
min2 = j;
}
}
}
tree[min1].parent = i;
tree[min2].parent = i;
tree[i].lchild = min1;
tree[i].rchild = min2;
tree[i].freq = tree[min1].freq + tree[min2].freq;
}
}
void getHuffmanCode(HuffmanNode* tree, int nodeNum, char* code[]) {
char* buf = (char*)malloc(nodeNum * sizeof(char));
for (int i = 0; i < nodeNum; i++) {
int j = i;
int k = 0;
while (tree[j].parent != -1) {
buf[k++] = (j == tree[tree[j].parent].lchild) ? '0' : '1';
j = tree[j].parent;
}
buf[k] = '\0';
int len = strlen(buf);
code[i] = (char*)malloc((len + 1) * sizeof(char));
for (int m = 0; m < len; m++) {
code[i][m] = buf[len - 1 - m];
}
code[i][len] = '\0';
}
free(buf);
}
void printHuffmanCode(HuffmanNode* tree, int nodeNum, char* code[]) {
int sum = 0;
for (int i = 0; i < nodeNum; i++) {
printf("%c: %s\n", tree[i].ch, code[i]);
sum += tree[i].freq * strlen(code[i]);
}
printf("Average code length: %.2f\n", (float)sum / strlen("ABBCCCDDDDEEEEE"));
}
int main() {
char str[] = "ABBCCCDDDDEEEEE";
HuffmanNode tree[MAX_NODE_NUM];
char* code[MAX_NODE_NUM];
initHuffmanTree(tree, str);
buildHuffmanTree(tree, strlen(str));
getHuffmanCode(tree, strlen(str), code);
printHuffmanCode(tree, strlen(str), code);
for (int i = 0; i < strlen(str); i++) {
free(code[i]);
}
return 0;
}
```
输出结果如下:
```
A: 111
B: 10
C: 01
D: 001
E: 000
Average code length: 2.50
```
可以看到,每个字符对应的哈夫曼编码以及平均编码长度都已经被正确计算出来了。
阅读全文