利用C语言编写完整代码。具体要求为: 从键盘任意输入一个由英文字母带空格构成的文本字符串,例如“I like Learning datastructure course”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并做详细注释
时间: 2024-03-07 21:48:21 浏览: 14
很高兴回答您的问题,以下是C语言实现Huffman编码和解码的完整代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>
#define MAX_CHARACTERS 128
#define MAX_CODE_LENGTH 100
typedef struct Node {
char character;
int frequency;
struct Node *left, *right;
} Node;
typedef struct Heap {
int size;
Node **array;
} Heap;
typedef struct Code {
char character;
char *code;
} Code;
// 创建一个新的节点
Node* new_node(char character, int frequency) {
Node* node = (Node*) malloc(sizeof(Node));
node->character = character;
node->frequency = frequency;
node->left = NULL;
node->right = NULL;
return node;
}
// 创建一个新的堆
Heap* new_heap(int capacity) {
Heap* heap = (Heap*) malloc(sizeof(Heap));
heap->size = 0;
heap->array = (Node**) malloc(capacity * sizeof(Node*));
return heap;
}
// 交换两个节点
void swap_nodes(Node **a, Node **b) {
Node *temp = *a;
*a = *b;
*b = temp;
}
// 最小堆化
void heapify(Heap *heap, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < heap->size && heap->array[left]->frequency < heap->array[smallest]->frequency) {
smallest = left;
}
if (right < heap->size && heap->array[right]->frequency < heap->array[smallest]->frequency) {
smallest = right;
}
if (smallest != index) {
swap_nodes(&heap->array[smallest], &heap->array[index]);
heapify(heap, smallest);
}
}
// 插入一个节点到堆中
void insert_node(Heap *heap, Node *node) {
++heap->size;
int i = heap->size - 1;
while (i && node->frequency < heap->array[(i - 1) / 2]->frequency) {
heap->array[i] = heap->array[(i - 1) / 2];
i = (i - 1) / 2;
}
heap->array[i] = node;
}
// 取出堆中最小的节点
Node* extract_min_node(Heap *heap) {
Node *min_node = heap->array[0];
heap->array[0] = heap->array[heap->size - 1];
--heap->size;
heapify(heap, 0);
return min_node;
}
// 建立Huffman树
Node* build_huffman_tree(char *text) {
int freq[MAX_CHARACTERS] = {0};
for (int i = 0; text[i] != '\0'; ++i) {
++freq[text[i]];
}
Heap *heap = new_heap(MAX_CHARACTERS);
for (int i = 0; i < MAX_CHARACTERS; ++i) {
if (freq[i]) {
insert_node(heap, new_node((char) i, freq[i]));
}
}
while (heap->size > 1) {
Node *left = extract_min_node(heap);
Node *right = extract_min_node(heap);
Node *parent = new_node('\0', left->frequency + right->frequency);
parent->left = left;
parent->right = right;
insert_node(heap, parent);
}
return extract_min_node(heap);
}
// 编码Huffman树
void encode_huffman_tree(Node *root, char *code, int depth, Code *codes) {
if (root->left == NULL && root->right == NULL) {
for (int i = 0; i < MAX_CHARACTERS; ++i) {
if (root->character == i) {
codes[i].character = i;
codes[i].code = (char*) malloc((depth + 1) * sizeof(char));
strcpy(codes[i].code, code);
break;
}
}
} else {
code[depth] = '0';
encode_huffman_tree(root->left, code, depth + 1, codes);
code[depth] = '1';
encode_huffman_tree(root->right, code, depth + 1, codes);
}
}
// 编码文本
char* encode_text(char *text, Code *codes) {
int length = strlen(text);
int max_code_length = MAX_CODE_LENGTH;
char *encoded_text = (char*) malloc((length * max_code_length + 1) * sizeof(char));
int encoded_index = 0;
for (int i = 0; i < length; ++i) {
char character = text[i];
for (int j = 0; j < MAX_CHARACTERS; ++j) {
if (codes[j].character == character) {
strcat(encoded_text, codes[j].code);
encoded_index += strlen(codes[j].code);
break;
}
}
}
return encoded_text;
}
// 解码文本
char* decode_text(char *encoded_text, Node *root) {
int length = strlen(encoded_text);
char *decoded_text = (char*) malloc((length + 1) * sizeof(char));
int decoded_index = 0;
Node *current_node = root;
for (int i = 0; i < length; ++i) {
if (encoded_text[i] == '0') {
current_node = current_node->left;
} else {
current_node = current_node->right;
}
if (current_node->left == NULL && current_node->right == NULL) {
decoded_text[decoded_index++] = current_node->character;
current_node = root;
}
}
decoded_text[decoded_index] = '\0';
return decoded_text;
}
int main() {
char text[MAX_CHARACTERS];
printf("请输入一个由英文字母带空格构成的文本字符串:");
fgets(text, sizeof(text), stdin);
text[strcspn(text, "\n")] = '\0';
Node *root = build_huffman_tree(text);
Code codes[MAX_CHARACTERS] = {0};
char code[MAX_CODE_LENGTH] = {0};
encode_huffman_tree(root, code, 0, codes);
printf("\nHuffman编码结果为:\n");
char *encoded_text = encode_text(text, codes);
printf("%s\n", encoded_text);
printf("\n解码结果为:\n");
char *decoded_text = decode_text(encoded_text, root);
printf("%s\n", decoded_text);
return 0;
}
```
解释如下:
1. `MAX_CHARACTERS` 定义了字符集的大小,这里取默认ASCII码表的大小128。
2. `MAX_CODE_LENGTH` 定义了编码的最大长度,这里取100。
3. `Node` 是一个结构体,表示Huffman树的一个节点,包含字符、频率和指向左右子节点的指针。
4. `Heap` 是一个结构体,表示最小堆,包含堆的大小和指向节点指针数组的指针。
5. `Code` 是一个结构体,表示字符和对应的Huffman编码。
6. `new_node` 函数创建一个新的节点。
7. `new_heap` 函数创建一个新的堆。
8. `swap_nodes` 函数交换两个节点。
9. `heapify` 函数将一个节点最小堆化。
10. `insert_node` 函数插入一个节点到堆中。
11. `extract_min_node` 函数取出堆中最小的节点。
12. `build_huffman_tree` 函数根据文本构建Huffman树。
13. `encode_huffman_tree` 函数编码Huffman树。
14. `encode_text` 函数编码文本。
15. `decode_text` 函数解码文本。
16. `main` 函数从键盘输入文本,然后构建Huffman树,进行Huffman编码,解码并输出结果。
注意事项:
1. 在输入文本时,使用了 `fgets` 函数来避免输入字符串过长导致缓冲区溢出。
2. 在输出Huffman编码结果时,直接输出了字符串,不需要使用 `printf` 函数的 `%s` 格式化字符串。
3. 在解码Huffman编码时,需要遍历二叉树来查找对应的字符,而不是直接使用哈希表等数据结构。
4. 如果文本中包含非ASCII字符,需要将 `MAX_CHARACTERS` 和 `MAX_CODE_LENGTH` 更改为更大的值。
希望这个代码能够帮到您!