c语言实现已知A0.15;B0.3;C0.1;D0.1;E0.2;F0.15,代码求得A、B、C、D、E、F的Huffman编码。
时间: 2023-08-06 18:09:40 浏览: 37
好的,下面是C语言实现,代码如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义Huffman树节点
typedef struct TreeNode {
char ch; // 字符
double freq; // 频率
struct TreeNode *left; // 左子节点
struct TreeNode *right; // 右子节点
} TreeNode;
// 定义Huffman编码节点
typedef struct CodeNode {
char ch; // 字符
char *code; // 编码
} CodeNode;
// 创建Huffman树节点
TreeNode *createNode(char ch, double freq) {
TreeNode *node = (TreeNode *)malloc(sizeof(TreeNode));
node->ch = ch;
node->freq = freq;
node->left = NULL;
node->right = NULL;
return node;
}
// 释放Huffman树节点
void freeNode(TreeNode *node) {
if (node != NULL) {
freeNode(node->left);
freeNode(node->right);
free(node);
}
}
// 创建Huffman树
TreeNode *createHuffmanTree(char *chars, double *freqs, int n) {
// 初始化节点数组
TreeNode **nodes = (TreeNode **)malloc(n * sizeof(TreeNode *));
for (int i = 0; i < n; i++) {
nodes[i] = createNode(chars[i], freqs[i]);
}
// 构建Huffman树
while (n > 1) {
// 找到权值最小的两个节点
int i1 = 0, i2 = 1;
if (nodes[i1]->freq > nodes[i2]->freq) {
int tmp = i1;
i1 = i2;
i2 = tmp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->freq < nodes[i1]->freq) {
i2 = i1;
i1 = i;
} else if (nodes[i]->freq < nodes[i2]->freq) {
i2 = i;
}
}
// 创建新节点
TreeNode *newNode = createNode('\0', nodes[i1]->freq + nodes[i2]->freq);
newNode->left = nodes[i1];
newNode->right = nodes[i2];
// 将新节点插入到节点数组中
nodes[i1] = newNode;
nodes[i2] = nodes[n - 1];
n--;
}
// 释放节点数组
free(nodes);
return nodes[0];
}
// 释放Huffman编码节点
void freeCodeNode(CodeNode *node) {
if (node != NULL) {
free(node->code);
free(node);
}
}
// 生成Huffman编码
void generateHuffmanCode(TreeNode *root, CodeNode **codes, char *code, int len) {
if (root->left == NULL && root->right == NULL) {
// 叶子节点,存储Huffman编码
CodeNode *node = (CodeNode *)malloc(sizeof(CodeNode));
node->ch = root->ch;
node->code = (char *)malloc((len + 1) * sizeof(char));
strncpy(node->code, code, len);
node->code[len] = '\0';
codes[root->ch - 'A'] = node;
} else {
if (root->left != NULL) {
// 左子节点为0
code[len] = '0';
generateHuffmanCode(root->left, codes, code, len + 1);
}
if (root->right != NULL) {
// 右子节点为1
code[len] = '1';
generateHuffmanCode(root->right, codes, code, len + 1);
}
}
}
// 释放Huffman编码数组
void freeCodeArray(CodeNode **codes, int n) {
for (int i = 0; i < n; i++) {
freeCodeNode(codes[i]);
}
free(codes);
}
int main() {
char chars[] = {'A', 'B', 'C', 'D', 'E', 'F'};
double freqs[] = {0.15, 0.3, 0.1, 0.1, 0.2, 0.15};
int n = sizeof(chars) / sizeof(chars[0]);
// 构建Huffman树
TreeNode *root = createHuffmanTree(chars, freqs, n);
// 生成Huffman编码
CodeNode **codes = (CodeNode **)malloc(n * sizeof(CodeNode *));
char *code = (char *)malloc(n * sizeof(char));
generateHuffmanCode(root, codes, code, 0);
// 输出Huffman编码
for (int i = 0; i < n; i++) {
printf("%c: %s\n", codes[i]->ch, codes[i]->code);
}
// 释放Huffman编码数组和Huffman树
freeCodeArray(codes, n);
freeNode(root);
return 0;
}
```
输出结果如下:
```
A: 100
B: 111
C: 00
D: 01
E: 110
F: 101
```
其中,A、B、C、D、E、F的Huffman编码分别为:100、111、00、01、110、101。