利用C语言编写软件实现上述功能。具体要求为: 从键盘任意输入一个由英文字母构成的文本字符串,例如“i like learning datastructure course”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并为代码做详细注释
时间: 2024-03-03 20:52:39 浏览: 62
好的,根据您的要求,以下是一份实现Huffman编码和解码的C语言代码,其中注释详细解释了每一步的实现过程。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义哈夫曼树的节点结构体
typedef struct huffman_node {
char data; // 节点存储的字符
int freq; // 节点出现的频率
struct huffman_node *left; // 左子节点
struct huffman_node *right; // 右子节点
} huffman_node;
// 定义哈夫曼编码的结构体
typedef struct huffman_code {
char data; // 编码字符
char *code; // 编码结果(0-1串)
} huffman_code;
// 定义哈夫曼编码表的结构体
typedef struct huffman_table {
int size; // 编码字符个数
huffman_code *codes; // 编码结果数组
} huffman_table;
// 声明哈夫曼编码和解码的函数
huffman_table *huffman_encode(char *str);
char *huffman_decode(char *code, huffman_table *table);
// 声明创建哈夫曼树的函数
huffman_node *create_huffman_tree(char *str);
// 声明对哈夫曼树进行编码的函数
void encode_huffman_tree(huffman_node *root, char *code, huffman_table *table);
// 声明比较函数,用于qsort排序
int cmp(const void *a, const void *b);
int main() {
// 从键盘输入一个字符串
char str[100];
printf("请输入一个由英文字母构成的字符串:");
scanf("%[^\n]", str);
// 执行哈夫曼编码
huffman_table *table = huffman_encode(str);
// 输出哈夫曼编码结果
printf("哈夫曼编码结果为:\n");
for (int i = 0; i < table->size; i++) {
printf("%c: %s\n", table->codes[i].data, table->codes[i].code);
}
// 执行哈夫曼解码
char *code = (char *) malloc(strlen(str) * 8 + 1); // 0-1编码串长度不超过原串长度的8倍
printf("请输入要解码的0-1编码串:");
scanf("%s", code);
char *decoded_str = huffman_decode(code, table);
// 输出解码结果
printf("解码结果为:%s\n", decoded_str);
// 释放内存
free(table->codes);
free(table);
free(decoded_str);
return 0;
}
// 创建哈夫曼树的函数
huffman_node *create_huffman_tree(char *str) {
int freq[26] = {0}; // 统计每个字母出现的频率,26个字母用一个数组存储
int len = strlen(str);
for (int i = 0; i < len; i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
freq[str[i] - 'a']++;
}
}
// 将统计结果存储为哈夫曼树的节点
huffman_node *nodes[26];
int node_count = 0;
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
huffman_node *node = (huffman_node *) malloc(sizeof(huffman_node));
node->data = 'a' + i;
node->freq = freq[i];
node->left = NULL;
node->right = NULL;
nodes[node_count++] = node;
}
}
// 构建哈夫曼树
while (node_count > 1) {
// 对节点按频率从小到大排序
qsort(nodes, node_count, sizeof(huffman_node *), cmp);
// 取出频率最小的两个节点作为左右子节点,构建新节点
huffman_node *left = nodes[0];
huffman_node *right = nodes[1];
huffman_node *parent = (huffman_node *) malloc(sizeof(huffman_node));
parent->data = '#'; // 用#表示内部节点
parent->freq = left->freq + right->freq;
parent->left = left;
parent->right = right;
// 将新节点插入到节点数组中
nodes[0] = parent;
for (int i = 1; i < node_count - 1; i++) {
nodes[i] = nodes[i + 1];
}
node_count--;
}
return nodes[0];
}
// 对哈夫曼树进行编码的函数
void encode_huffman_tree(huffman_node *root, char *code, huffman_table *table) {
if (root->left == NULL && root->right == NULL) { // 叶子节点
// 将叶子节点的编码结果存储到编码表中
table->codes[table->size].data = root->data;
table->codes[table->size].code = (char *) malloc(strlen(code) + 1);
strcpy(table->codes[table->size].code, code);
table->size++;
} else { // 内部节点,递归遍历左右子树
char *left_code = (char *) malloc(strlen(code) + 2);
strcpy(left_code, code);
strcat(left_code, "0");
encode_huffman_tree(root->left, left_code, table);
char *right_code = (char *) malloc(strlen(code) + 2);
strcpy(right_code, code);
strcat(right_code, "1");
encode_huffman_tree(root->right, right_code, table);
}
}
// 哈夫曼编码函数
huffman_table *huffman_encode(char *str) {
huffman_table *table = (huffman_table *) malloc(sizeof(huffman_table));
table->size = 0;
table->codes = (huffman_code *) malloc(26 * sizeof(huffman_code));
// 创建哈夫曼树
huffman_node *root = create_huffman_tree(str);
// 对哈夫曼树进行编码
char code[100];
encode_huffman_tree(root, code, table);
return table;
}
// 哈夫曼解码函数
char *huffman_decode(char *code, huffman_table *table) {
int len = strlen(code);
char *decoded_str = (char *) malloc(len / 8 + 1); // 解码后的字符串长度不超过编码串长度的1/8
int decoded_index = 0;
int code_index = 0;
while (code_index < len) {
// 从编码串中取出一个编码值
char c = code[code_index++];
// 在编码表中查找对应的字符
for (int i = 0; i < table->size; i++) {
if (strcmp(table->codes[i].code, &c) == 0) {
// 找到了对应的字符,将其存储到解码后的字符串中
decoded_str[decoded_index++] = table->codes[i].data;
break;
}
}
}
decoded_str[decoded_index] = '\0';
return decoded_str;
}
// 比较函数,用于qsort排序
int cmp(const void *a, const void *b) {
huffman_node *node_a = *(huffman_node **) a;
huffman_node *node_b = *(huffman_node **) b;
return node_a->freq - node_b->freq;
}
```
在上面的代码中,主函数中先从键盘输入一个字符串,然后调用 `huffman_encode` 函数进行哈夫曼编码,再将编码结果输出到屏幕上。然后再输入一个0-1编码串,调用 `huffman_decode` 函数进行解码,将解码结果输出到屏幕上。在 `huffman_encode` 函数中,先调用 `create_huffman_tree` 函数创建哈夫曼树,然后调用 `encode_huffman_tree` 函数对哈夫曼树进行编码,最后返回编码表。在 `huffman_decode` 函数中,先根据编码表将0-1编码串解码为字符,然后将解码后的字符拼接成一个字符串,并返回该字符串。
阅读全文