利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-07 11:47:51 浏览: 105
以下是利用C语言编写的完整代码,实现从键盘输入一个带空格的英文字母字符串,创建Huffman树,进行Huffman编码,并输出编码结果:
```
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_INPUT_LEN 1000
#define MAX_CODE_LEN 1000
// Huffman树的节点定义
typedef struct huff_node {
char c; // 字符
int freq; // 频率
struct huff_node *left; // 左子树
struct huff_node *right; // 右子树
} HuffNode;
// Huffman编码表的节点定义
typedef struct code_node {
char c; // 字符
char code[MAX_CODE_LEN]; // 编码
} CodeNode;
// 统计字符串中每个字符出现的频率
void count_freq(char *str, int freq[]) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
freq[str[i]]++;
}
}
// 创建Huffman树
HuffNode* create_huff_tree(int freq[]) {
HuffNode **nodes = (HuffNode**) malloc(sizeof(HuffNode*) * 256);
for (int i = 0; i < 256; i++) {
if (freq[i] > 0) {
HuffNode *node = (HuffNode*) malloc(sizeof(HuffNode));
node->c = i;
node->freq = freq[i];
node->left = NULL;
node->right = NULL;
nodes[i] = node;
} else {
nodes[i] = NULL;
}
}
// 构建Huffman树
while (1) {
int i, j;
int min1 = -1, min2 = -1;
for (i = 0; i < 256; i++) {
if (nodes[i] != NULL && min1 == -1) {
min1 = i;
} else if (nodes[i] != NULL && nodes[i]->freq < nodes[min1]->freq) {
min1 = i;
}
}
for (j = 0; j < 256; j++) {
if (nodes[j] != NULL && min2 == -1 && j != min1) {
min2 = j;
} else if (nodes[j] != NULL && nodes[j]->freq < nodes[min2]->freq && j != min1) {
min2 = j;
}
}
if (min2 == -1) {
break;
}
HuffNode *parent = (HuffNode*) malloc(sizeof(HuffNode));
parent->c = 0;
parent->freq = nodes[min1]->freq + nodes[min2]->freq;
parent->left = nodes[min1];
parent->right = nodes[min2];
nodes[min1] = parent;
nodes[min2] = NULL;
}
HuffNode *root = NULL;
for (int i = 0; i < 256; i++) {
if (nodes[i] != NULL) {
root = nodes[i];
}
}
free(nodes);
return root;
}
// 根据Huffman树生成Huffman编码表
void generate_code_table(HuffNode *root, char code[], int len, CodeNode *table[]) {
if (root->left == NULL && root->right == NULL) {
CodeNode *node = (CodeNode*) malloc(sizeof(CodeNode));
node->c = root->c;
strncpy(node->code, code, len);
table[root->c] = node;
return;
}
code[len] = '0';
code[len + 1] = '\0';
generate_code_table(root->left, code, len + 1, table);
code[len] = '1';
code[len + 1] = '\0';
generate_code_table(root->right, code, len + 1, table);
}
// Huffman编码
void encode(char *str, CodeNode *table[], char *code) {
int len = strlen(str);
int pos = 0;
for (int i = 0; i < len; i++) {
CodeNode *node = table[str[i]];
strcat(code + pos, node->code);
pos += strlen(node->code);
}
}
// 解码Huffman编码
void decode(char *code, HuffNode *root, char *str) {
HuffNode *p = root;
int len = strlen(code);
int pos = 0;
for (int i = 0; i < len; i++) {
if (code[i] == '0') {
p = p->left;
} else if (code[i] == '1') {
p = p->right;
}
if (p->left == NULL && p->right == NULL) {
str[pos++] = p->c;
p = root;
}
}
str[pos] = '\0';
}
int main() {
char input[MAX_INPUT_LEN];
int freq[256] = {0};
CodeNode *table[256] = {NULL};
char code[MAX_INPUT_LEN * 10] = "";
printf("请输入一个带空格的英文字母字符串:\n");
fgets(input, MAX_INPUT_LEN, stdin);
count_freq(input, freq);
HuffNode *root = create_huff_tree(freq);
char huff_code[MAX_CODE_LEN] = "";
generate_code_table(root, huff_code, 0, table);
encode(input, table, code);
printf("Huffman编码结果为:%s\n", code);
char decode_str[MAX_INPUT_LEN] = "";
decode(code, root, decode_str);
printf("解码结果为:%s\n", decode_str);
return 0;
}
```
程序的逻辑如下:
1. 从键盘输入一个带空格的英文字母字符串;
2. 统计字符串中每个字符出现的频率;
3. 根据频率创建Huffman树;
4. 根据Huffman树生成Huffman编码表;
5. 对输入的字符串进行Huffman编码;
6. 输出编码结果;
7. 利用Huffman编码结果对某0-1码流进行解码,得到原字符串。
注释详见代码。
阅读全文