利用C语言编写完整代码。具体要求为: 从键盘任意输入一个由英文字母带空格构成的文本字符串,例如“I like Learning datastructure course”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并做详细注释
时间: 2024-03-07 11:46:55 浏览: 12
非常感谢您的提问。针对您的问题,我提供如下的代码实现及注释,希望能够帮到您。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义节点结构体
struct node {
char ch; // 存储字符
int freq; // 存储字符出现的频率
struct node *left; // 左孩子指针
struct node *right; // 右孩子指针
};
// 定义哈夫曼树结构体
struct huffman_tree {
struct node *root; // 哈夫曼树的根节点指针
};
// 定义哈夫曼编码结构体
struct huffman_code {
char ch; // 存储字符
char *code; // 存储字符的哈夫曼编码
};
// 创建节点
struct node *create_node(char ch, int freq) {
struct node *new_node = (struct node *)malloc(sizeof(struct node));
new_node->ch = ch;
new_node->freq = freq;
new_node->left = NULL;
new_node->right = NULL;
return new_node;
}
// 交换节点
void swap_node(struct node **a, struct node **b) {
struct node *temp = *a;
*a = *b;
*b = temp;
}
// 构建哈夫曼树
void build_huffman_tree(struct node **nodes, int n) {
// 选择两个权值最小的节点合并,构建哈夫曼树
for (int i = 0; i < n - 1; i++) {
int min1 = i, min2 = i + 1;
if (nodes[min1]->freq > nodes[min2]->freq) {
swap_node(&nodes[min1], &nodes[min2]);
}
for (int j = i + 2; j < n; j++) {
if (nodes[j]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = j;
} else if (nodes[j]->freq < nodes[min2]->freq) {
min2 = j;
}
}
struct node *new_node = create_node('\0', nodes[min1]->freq + nodes[min2]->freq);
new_node->left = nodes[min1];
new_node->right = nodes[min2];
nodes[min1] = new_node;
nodes[min2] = nodes[n - 1 - i];
}
}
// 生成哈夫曼编码
void generate_huffman_code(struct node *root, char *prefix, struct huffman_code *codes, int *index) {
if (root) {
if (root->left) {
char *left_prefix = (char *)malloc(strlen(prefix) + 1);
strcpy(left_prefix, prefix);
strcat(left_prefix, "0");
generate_huffman_code(root->left, left_prefix, codes, index);
}
if (root->right) {
char *right_prefix = (char *)malloc(strlen(prefix) + 1);
strcpy(right_prefix, prefix);
strcat(right_prefix, "1");
generate_huffman_code(root->right, right_prefix, codes, index);
}
if (!root->left && !root->right) {
struct huffman_code new_code = {root->ch, prefix};
codes[(*index)++] = new_code;
}
}
}
// 获取字符在哈夫曼编码数组中的下标
int get_index(char ch, struct huffman_code *codes, int n) {
for (int i = 0; i < n; i++) {
if (codes[i].ch == ch) {
return i;
}
}
return -1;
}
// 哈夫曼编码
void huffman_encode(char *text, struct huffman_code *codes, int n) {
int len = strlen(text);
for (int i = 0; i < len; i++) {
int index = get_index(text[i], codes, n);
printf("%s", codes[index].code);
}
}
// 哈夫曼解码
void huffman_decode(char *code, struct huffman_node *root) {
int len = strlen(code);
struct node *current = root;
for (int i = 0; i < len; i++) {
if (code[i] == '0') {
current = current->left;
} else {
current = current->right;
}
if (!current->left && !current->right) {
printf("%c", current->ch);
current = root;
}
}
}
int main() {
char text[100];
printf("请输入一个由英文字母带空格构成的文本字符串:");
scanf("%[^\n]s", text);
// 统计字符出现的频率
int freq[128] = {0};
int len = strlen(text);
for (int i = 0; i < len; i++) {
freq[(int)text[i]]++;
}
// 构建节点
int node_count = 0;
struct node *nodes[128];
for (int i = 0; i < 128; i++) {
if (freq[i] > 0) {
nodes[node_count++] = create_node((char)i, freq[i]);
}
}
// 构建哈夫曼树
build_huffman_tree(nodes, node_count);
// 生成哈夫曼编码
struct huffman_code codes[128];
int code_count = 0;
generate_huffman_code(nodes[0], "", codes, &code_count);
// 输出哈夫曼编码
printf("Huffman编码结果为:");
huffman_encode(text, codes, code_count);
printf("\n");
// 哈夫曼解码
printf("请输入一个0-1码流进行解码:");
char code[100];
scanf("%s", code);
printf("解码结果为:");
huffman_decode(code, nodes[0]);
printf("\n");
return 0;
}
```
上述代码实现了从键盘输入一个由英文字母带空格构成的文本字符串,根据该字符串创建哈夫曼树,进行哈夫曼编码,并输出哈夫曼编码结果。同时,还可以利用哈夫曼编码结果对0-1码流进行解码,并输出解码结果。具体实现过程中,我们定义了节点结构体、哈夫曼树结构体、哈夫曼编码结构体,并实现了创建节点、交换节点、构建哈夫曼树、生成哈夫曼编码、获取字符在哈夫曼编码数组中的下标、哈夫曼编码、哈夫曼解码等函数。在主函数中,我们首先从键盘输入一个由英文字母带空格构成的文本字符串,统计字符出现的频率,构建节点,构建哈夫曼树,生成哈夫曼编码,输出哈夫曼编码结果。接着,我们从键盘输入一个0-1码流进行解码,并输出解码结果。