利用C语言编写软件实现上述功能。具体要求为:从键盘任意输入一个由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-06 17:50:58 浏览: 97
好的,我会给你提供C语言的代码实现,实现从输入文本字符串到生成Huffman编码并输出,再从Huffman编码解码回原始字符串的功能。
首先,构建Huffman树的函数实现如下:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
char ch; // 存储字符
int freq; // 存储字符出现的频率
struct node *left, *right; // 左右子树
} Node;
int freq[26] = {0}; // 存储每个字符出现的频率
// 遍历Huffman树,生成Huffman编码
void encode(Node *root, char *code, int len) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->ch, code);
} else {
code[len] = '0';
encode(root->left, code, len + 1);
code[len] = '1';
encode(root->right, code, len + 1);
}
}
// 构建Huffman树
Node *buildHuffmanTree(char *str) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
freq[str[i] - 'a']++; // 统计每个字符出现的频率
}
// 构建叶子节点
Node *leaves[26];
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
leaves[i] = (Node *)malloc(sizeof(Node));
leaves[i]->ch = 'a' + i;
leaves[i]->freq = freq[i];
leaves[i]->left = NULL;
leaves[i]->right = NULL;
} else {
leaves[i] = NULL;
}
}
// 构建Huffman树
Node *nodes[52];
int n = 0;
for (int i = 0; i < 26; i++) {
if (leaves[i] != NULL) {
nodes[n++] = leaves[i];
}
}
while (n > 1) {
int min1 = 0, min2 = 1;
if (nodes[min1]->freq > nodes[min2]->freq) {
int tmp = min1;
min1 = min2;
min2 = tmp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = i;
} else if (nodes[i]->freq < nodes[min2]->freq) {
min2 = i;
}
}
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
nodes[min1] = newNode;
nodes[min2] = nodes[--n];
}
return nodes[0];
}
```
接下来,实现Huffman编码和解码的函数:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct node {
char ch; // 存储字符
int freq; // 存储字符出现的频率
struct node *left, *right; // 左右子树
} Node;
int freq[26] = {0}; // 存储每个字符出现的频率
// 遍历Huffman树,生成Huffman编码
void encode(Node *root, char *code, int len) {
if (root == NULL) {
return;
}
if (root->left == NULL && root->right == NULL) {
printf("%c: %s\n", root->ch, code);
} else {
code[len] = '0';
encode(root->left, code, len + 1);
code[len] = '1';
encode(root->right, code, len + 1);
}
}
// 构建Huffman树
Node *buildHuffmanTree(char *str) {
int len = strlen(str);
for (int i = 0; i < len; i++) {
freq[str[i] - 'a']++; // 统计每个字符出现的频率
}
// 构建叶子节点
Node *leaves[26];
for (int i = 0; i < 26; i++) {
if (freq[i] > 0) {
leaves[i] = (Node *)malloc(sizeof(Node));
leaves[i]->ch = 'a' + i;
leaves[i]->freq = freq[i];
leaves[i]->left = NULL;
leaves[i]->right = NULL;
} else {
leaves[i] = NULL;
}
}
// 构建Huffman树
Node *nodes[52];
int n = 0;
for (int i = 0; i < 26; i++) {
if (leaves[i] != NULL) {
nodes[n++] = leaves[i];
}
}
while (n > 1) {
int min1 = 0, min2 = 1;
if (nodes[min1]->freq > nodes[min2]->freq) {
int tmp = min1;
min1 = min2;
min2 = tmp;
}
for (int i = 2; i < n; i++) {
if (nodes[i]->freq < nodes[min1]->freq) {
min2 = min1;
min1 = i;
} else if (nodes[i]->freq < nodes[min2]->freq) {
min2 = i;
}
}
Node *newNode = (Node *)malloc(sizeof(Node));
newNode->freq = nodes[min1]->freq + nodes[min2]->freq;
newNode->left = nodes[min1];
newNode->right = nodes[min2];
nodes[min1] = newNode;
nodes[min2] = nodes[--n];
}
return nodes[0];
}
// 从Huffman编码解码回原始字符串
char *decode(Node *root, char *code) {
int len = strlen(code);
Node *p = root;
char *str = (char *)malloc(sizeof(char) * (len + 1));
int j = 0;
for (int i = 0; i < len; i++) {
if (code[i] == '0') {
p = p->left;
} else {
p = p->right;
}
if (p->left == NULL && p->right == NULL) {
str[j++] = p->ch;
p = root;
}
}
str[j] = '\0';
return str;
}
int main() {
char str[100];
printf("请输入一个由小写英文字母组成的字符串:");
scanf("%s", str);
Node *root = buildHuffmanTree(str);
char code[100] = "";
encode(root, code, 0);
char code2[100];
printf("请输入Huffman编码:");
scanf("%s", code2);
char *str2 = decode(root, code2);
printf("解码结果:%s\n", str2);
return 0;
}
```
以上代码实现了从输入文本字符串到生成Huffman编码并输出,再从Huffman编码解码回原始字符串的功能。
阅读全文