利用C语言编写一个完整代码。具体要求为:从键盘任意输入一个带空格由英文字母构成的文本字符串,例如“ilikelearningdatastructurecourse”,首先根据该字符串创建Huffman树,之后进行Huffman编码,然后把该字符串的Huffman编码结果向屏幕输出。能够利用前述的Huffman编码结果对某0-1码流进行解码得到字符串,并作出详细注释
时间: 2024-03-07 16:47:10 浏览: 59
好的,下面是符合要求的完整C代码:
```c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_CHAR 256
//定义Huffman树的节点结构体
struct huff_node {
char data;
unsigned freq;
struct huff_node *left, *right;
};
//定义Huffman编码表的结构体
struct huff_code {
char data;
char *code;
};
//定义Huffman树的优先队列结构体
struct priority_queue {
unsigned size;
unsigned capacity;
struct huff_node **nodes;
};
//创建Huffman树的节点
struct huff_node *create_node(char data, unsigned freq) {
struct huff_node *node = (struct huff_node *) malloc(sizeof(struct huff_node));
node->data = data;
node->freq = freq;
node->left = NULL;
node->right = NULL;
return node;
}
//创建Huffman树的优先队列
struct priority_queue *create_queue(unsigned capacity) {
struct priority_queue *queue = (struct priority_queue *) malloc(sizeof(struct priority_queue));
queue->size = 0;
queue->capacity = capacity;
queue->nodes = (struct huff_node **) malloc(queue->capacity * sizeof(struct huff_node *));
return queue;
}
//交换两个节点的位置
void swap_nodes(struct huff_node **a, struct huff_node **b) {
struct huff_node *temp = *a;
*a = *b;
*b = temp;
}
//调整优先队列,使得队列中的节点按频率从小到大排列
void min_heapify(struct priority_queue *queue, int index) {
int smallest = index;
int left = 2 * index + 1;
int right = 2 * index + 2;
if (left < queue->size && queue->nodes[left]->freq < queue->nodes[smallest]->freq) {
smallest = left;
}
if (right < queue->size && queue->nodes[right]->freq < queue->nodes[smallest]->freq) {
smallest = right;
}
if (smallest != index) {
swap_nodes(&queue->nodes[index], &queue->nodes[smallest]);
min_heapify(queue, smallest);
}
}
//检查优先队列是否为空
int is_empty(struct priority_queue *queue) {
return queue->size == 0;
}
//取出优先队列中频率最小的节点
struct huff_node *extract_min(struct priority_queue *queue) {
struct huff_node *node = queue->nodes[0];
queue->nodes[0] = queue->nodes[queue->size - 1];
queue->size--;
min_heapify(queue, 0);
return node;
}
//插入新节点到优先队列中
void insert_node(struct priority_queue *queue, struct huff_node *node) {
queue->size++;
int i = queue->size - 1;
while (i && node->freq < queue->nodes[(i - 1) / 2]->freq) {
queue->nodes[i] = queue->nodes[(i - 1) / 2];
i = (i - 1) / 2;
}
queue->nodes[i] = node;
}
//检查节点是否是叶子节点
int is_leaf(struct huff_node *node) {
return !(node->left) && !(node->right);
}
//构建Huffman树
struct huff_node *build_tree(char *text) {
int freq[MAX_CHAR] = {0};
int len = strlen(text);
for (int i = 0; i < len; i++) {
freq[(int) text[i]]++;
}
struct priority_queue *queue = create_queue(MAX_CHAR);
for (int i = 0; i < MAX_CHAR; i++) {
if (freq[i]) {
insert_node(queue, create_node((char) i, freq[i]));
}
}
while (queue->size > 1) {
struct huff_node *left = extract_min(queue);
struct huff_node *right = extract_min(queue);
struct huff_node *parent = create_node('$', left->freq + right->freq);
parent->left = left;
parent->right = right;
insert_node(queue, parent);
}
return extract_min(queue);
}
//从根节点开始,对Huffman树进行深度优先遍历,同时记录每个叶子节点的编码
void traverse_tree(struct huff_node *root, char *code, int depth, struct huff_code *codes) {
if (root->left) {
code[depth] = '0';
traverse_tree(root->left, code, depth + 1, codes);
}
if (root->right) {
code[depth] = '1';
traverse_tree(root->right, code, depth + 1, codes);
}
if (is_leaf(root)) {
codes[(int) root->data].data = root->data;
codes[(int) root->data].code = (char *) malloc((depth + 1) * sizeof(char));
strncpy(codes[(int) root->data].code, code, depth);
codes[(int) root->data].code[depth] = '\0';
}
}
//编码输入的字符串
char *encode_text(char *text, struct huff_code *codes) {
int len = strlen(text);
char *encoded = (char *) malloc((len + 1) * sizeof(char));
encoded[0] = '\0';
for (int i = 0; i < len; i++) {
strcat(encoded, codes[(int) text[i]].code);
}
return encoded;
}
//解码0-1编码流
char *decode_text(char *encoded, struct huff_node *root) {
char *decoded = (char *) malloc((strlen(encoded) + 1) * sizeof(char));
int i = 0, j = 0;
while (encoded[i] != '\0') {
struct huff_node *current = root;
while (!is_leaf(current)) {
if (encoded[i] == '0') {
current = current->left;
} else if (encoded[i] == '1') {
current = current->right;
}
i++;
}
decoded[j++] = current->data;
}
decoded[j] = '\0';
return decoded;
}
int main() {
char text[MAX_CHAR];
printf("请输入一个字符串:\n");
fgets(text, MAX_CHAR, stdin);
text[strcspn(text, "\n")] = '\0';
struct huff_node *root = build_tree(text);
char code[MAX_CHAR];
struct huff_code codes[MAX_CHAR] = {0};
traverse_tree(root, code, 0, codes);
printf("Huffman编码结果为:\n");
char *encoded = encode_text(text, codes);
printf("%s\n", encoded);
printf("解码结果为:\n");
char *decoded = decode_text(encoded, root);
printf("%s\n", decoded);
return 0;
}
```
代码的注释比较详细,主要是分为几个部分:
1. 定义Huffman树的节点结构体、Huffman编码表的结构体和Huffman树的优先队列结构体;
2. 创建Huffman树的节点、创建Huffman树的优先队列、交换两个节点的位置、调整优先队列、检查优先队列是否为空、取出优先队列中频率最小的节点、插入新节点到优先队列中、检查节点是否是叶子节点等几个函数;
3. 构建Huffman树的函数,该函数首先统计输入字符串中每个字符出现的频率,然后将频率大于0的字符构成Huffman树的叶子节点,并插入优先队列中,最后通过不断取出队列中频率最小的两个节点,合并成一个新节点,然后插入队列中,直到队列中只剩下一个节点,该节点就是Huffman树的根节点;
4. 对Huffman树进行深度优先遍历,同时记录每个叶子节点的编码的函数;
5. 编码输入的字符串的函数,该函数根据输入的字符串和Huffman编码表,将每个字符编码成0-1编码流;
6. 解码0-1编码流的函数,该函数从Huffman树的根节点开始,对输入的0-1编码流进行遍历,直到遇到叶子节点,然后将该节点的字符加入解码结果中;
7. 主函数,该函数读入输入的字符串,然后构建Huffman树并对输入的字符串进行编码和解码,并将结果输出到屏幕上。
希望能够帮助你完成作业。
阅读全文