利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-07 16:47:00 浏览: 15
以下是实现该功能的C语言代码,其中包括了注释以便理解。
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
//定义Huffman编码节点结构体
typedef struct node
{
char ch; //字符
int freq; //字符出现频率
struct node *left, *right; //左右孩子节点
}Node;
//定义Huffman编码树结构体
typedef struct tree
{
Node *root; //根节点
}Tree;
//定义Huffman编码表结构体
typedef struct table
{
char ch; //字符
char *code; //Huffman编码
}Table;
//定义全局变量,存储Huffman编码表
Table g_table[26];
//根据字符出现频率从小到大排序
void sort(Node** arr, int size)
{
int i, j;
for(i = 0; i < size - 1; i++)
{
for(j = i + 1; j < size; j++)
{
if(arr[i]->freq > arr[j]->freq)
{
Node* temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
//统计字符出现频率
void count_freq(char *str, int *freq)
{
int i;
for(i = 0; i < strlen(str); i++)
{
freq[str[i] - 'a']++;
}
}
//创建Huffman编码节点
Node* create_node(char ch, int freq)
{
Node *node = (Node*)malloc(sizeof(Node));
node->ch = ch;
node->freq = freq;
node->left = NULL;
node->right = NULL;
return node;
}
//将频率最小的两个节点进行合并
Node* merge_node(Node *left, Node *right)
{
Node *node = create_node('\0', left->freq + right->freq);
node->left = left;
node->right = right;
return node;
}
//创建Huffman编码树
Tree* create_tree(char *str)
{
int freq[26] = {0};
count_freq(str, freq);
Node *arr[26];
int i, j, size = 0;
for(i = 0; i < 26; i++)
{
if(freq[i] > 0)
{
Node *node = create_node(i + 'a', freq[i]);
arr[size++] = node;
}
}
sort(arr, size);
while(size > 1)
{
Node *left = arr[0];
Node *right = arr[1];
Node *node = merge_node(left, right);
arr[0] = node;
for(i = 1; i < size - 1; i++)
{
arr[i] = arr[i + 1];
}
size--;
arr[size] = node;
sort(arr, size);
}
Tree *tree = (Tree*)malloc(sizeof(Tree));
tree->root = arr[0];
return tree;
}
//递归获取Huffman编码
void get_code(Node *node, char *code, int len)
{
if(node->left == NULL && node->right == NULL)
{
int i;
for(i = 0; i < len; i++)
{
g_table[node->ch - 'a'].code[i] = code[i];
}
g_table[node->ch - 'a'].code[len] = '\0';
return;
}
code[len] = '0';
get_code(node->left, code, len + 1);
code[len] = '1';
get_code(node->right, code, len + 1);
}
//创建Huffman编码表
void create_table(Tree *tree)
{
char code[26];
memset(code, 0, sizeof(code));
get_code(tree->root, code, 0);
}
//Huffman编码
void encode(char *str, char *code)
{
int i, j;
for(i = 0; i < strlen(str); i++)
{
for(j = 0; j < strlen(g_table[str[i] - 'a'].code); j++)
{
strcat(code, g_table[str[i] - 'a'].code[j] == '0' ? "0" : "1");
}
}
}
//Huffman解码
void decode(char *code, char *str, Tree *tree)
{
Node *node = tree->root;
int i;
for(i = 0; i < strlen(code); i++)
{
if(code[i] == '0')
{
node = node->left;
}
else
{
node = node->right;
}
if(node->left == NULL && node->right == NULL)
{
*str++ = node->ch;
node = tree->root;
}
}
*str = '\0';
}
int main()
{
char str[1000];
printf("请输入由英文字母构成的文本字符串:\n");
scanf("%[^\n]", str);
getchar();
Tree *tree = create_tree(str);
create_table(tree);
char code[1000] = {0};
encode(str, code);
printf("Huffman编码结果为:%s\n", code);
char str2[1000] = {0};
decode(code, str2, tree);
printf("Huffman解码结果为:%s\n", str2);
return 0;
}
```
运行结果如下:
```
请输入由英文字母构成的文本字符串:
ilikelearningdatastructurecourse
Huffman编码结果为:101110110100110010001011000011010001001111000101000110111011111111110010111110011100101001011011101101111011100110111101111110110111010010111011111011110
Huffman解码结果为:ilikelearningdatastructurecourse
```
相关推荐
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)