利用C语言编写完整代码。具体要求为: 从键盘任意输入一个由英文字母带空格构成的文本字符串,例如“I like Learning datastructure course”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并做详细注释
时间: 2024-03-07 11:47:06 浏览: 56
C语言实现Huffman树,Huffman编码
5星 · 资源好评率100%
好的,下面是代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
// 定义字符和频率的结构体
struct CharFreq {
char ch;
int freq;
};
// 定义Huffman树的结构体
struct HuffmanTree {
char ch;
int freq;
struct HuffmanTree *left, *right;
};
// 创建字符和频率的数组
struct CharFreq char_freq[256];
// 定义Huffman编码的数组
char huffman_code[256][256];
// 定义Huffman编码的字符串
char huffman_string[1000000];
// 定义Huffman编码字符串的长度
int huffman_string_length = 0;
// 定义Huffman树的根节点
struct HuffmanTree *huffman_root = NULL;
// 交换两个字符和频率结构体
void swap(struct CharFreq *a, struct CharFreq *b) {
struct CharFreq temp = *a;
*a = *b;
*b = temp;
}
// 定义堆排序中的下沉操作
void heapify(struct CharFreq arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l].freq > arr[largest].freq) {
largest = l;
}
if (r < n && arr[r].freq > arr[largest].freq) {
largest = r;
}
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
}
}
// 定义堆排序函数
void heap_sort(struct CharFreq arr[], int n) {
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
}
}
// 创建Huffman树
struct HuffmanTree* create_huffman_tree(struct CharFreq arr[], int n) {
struct HuffmanTree *left, *right, *top;
// 创建一个最小堆
heap_sort(arr, n);
while (n != 1) {
// 取出最小的两个元素作为左右子节点
left = (struct HuffmanTree*) malloc(sizeof(struct HuffmanTree));
left->ch = arr[0].ch;
left->freq = arr[0].freq;
left->left = NULL;
left->right = NULL;
right = (struct HuffmanTree*) malloc(sizeof(struct HuffmanTree));
right->ch = arr[1].ch;
right->freq = arr[1].freq;
right->left = NULL;
right->right = NULL;
// 取出两个最小元素之后,删除它们
int i;
for (i = 2; i < n; i++) {
arr[i - 2] = arr[i];
}
n--;
// 创建一个新的节点,作为左右子节点的父节点
top = (struct HuffmanTree*) malloc(sizeof(struct HuffmanTree));
top->ch = '$';
top->freq = left->freq + right->freq;
top->left = left;
top->right = right;
// 将新的节点插入到数组中
i = n - 1;
while (i >= 0 && arr[i].freq < top->freq) {
arr[i + 1] = arr[i];
i--;
}
arr[i + 1].ch = '$';
arr[i + 1].freq = top->freq;
arr[i + 1].left = top->left;
arr[i + 1].right = top->right;
n--;
}
// 最后剩下的节点就是Huffman树的根节点
return (arr[0].left);
}
// 对Huffman树进行编码
void encode_huffman_tree(struct HuffmanTree* root, char code[], int top) {
// 如果是叶子节点,就输出编码
if (root->left == NULL && root->right == NULL) {
code[top] = '\0';
strcpy(huffman_code[root->ch], code);
return;
}
// 否则遍历左右子树
if (root->left != NULL) {
code[top] = '0';
encode_huffman_tree(root->left, code, top + 1);
}
if (root->right != NULL) {
code[top] = '1';
encode_huffman_tree(root->right, code, top + 1);
}
}
// 对文本字符串进行Huffman编码
void encode_huffman_string(char *text) {
int n = strlen(text);
// 遍历文本字符串,计算每个字符的出现频率
for (int i = 0; i < n; i++) {
char_freq[(int)text[i]].ch = text[i];
char_freq[(int)text[i]].freq++;
}
// 创建Huffman树
huffman_root = create_huffman_tree(char_freq, 256);
// 对Huffman树进行编码
char code[256];
encode_huffman_tree(huffman_root, code, 0);
// 输出Huffman编码结果
for (int i = 0; i < n; i++) {
strcat(huffman_string, huffman_code[(int)text[i]]);
}
huffman_string_length = strlen(huffman_string);
}
// 对0-1码流进行解码
void decode_huffman_string(char *code) {
// 定义Huffman树的当前节点
struct HuffmanTree *current = huffman_root;
// 遍历0-1码流,根据当前节点的左右子节点进行移动
for (int i = 0; i < strlen(code); i++) {
if (code[i] == '0') {
current = current->left;
} else {
current = current->right;
}
// 如果当前节点是叶子节点,就输出字符
if (current->left == NULL && current->right == NULL) {
printf("%c", current->ch);
current = huffman_root;
}
}
}
int main() {
char text[1000000];
// 从键盘输入文本字符串
printf("请输入一个由英文字母带空格构成的文本字符串:\n");
fgets(text, 1000000, stdin);
// 对文本字符串进行Huffman编码
encode_huffman_string(text);
// 输出Huffman编码结果
printf("Huffman编码结果为:\n%s\n", huffman_string);
// 对Huffman编码结果进行解码
printf("解码结果为:\n");
decode_huffman_string(huffman_string);
return 0;
}
```
代码实现的思路如下:
1. 定义字符和频率的结构体,以及Huffman树的结构体。
2. 创建字符和频率的数组,并遍历文本字符串,计算每个字符的出现频率。
3. 创建Huffman树,并对Huffman树进行编码。
4. 遍历文本字符串,输出每个字符的Huffman编码结果。
5. 对Huffman编码结果进行解码,输出原始文本字符串。
需要注意的是,本代码实现中只考虑了英文字母和空格,如果需要支持其他字符,需要对字符和频率的数组进行修改。
阅读全文