利用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` 更改为更大的值。 希望这个代码能够帮到您!

相关推荐

最新推荐

recommend-type

chromedriver-linux64-V124.0.6367.91 稳定版

chromedriver-linux64-V124.0.6367.91稳定版
recommend-type

基于yolov7 加入 depth回归

在官方的基础上改了检测头、导出onnx(适配tensorrt pro 项目)、测试demo等代码。 能够使用清华V2X数据集进行训练和测试。 https://www.bilibili.com/video/BV1Wd4y1G78M/?vd_source=0223c707743ff3013adaeff54aee3506 数据集来源:https://thudair.baai.ac.cn/index 基于Yolov7 tiny,加入了距离回归 模型没收敛完,随便试了下,所以预测有抖动 使用TRT加速,在AGX Xavier上推理大约4ms V2X使用tools/convertlabel2yolo.ipynb 进行数据集转换
recommend-type

基于STM32F101单片机设计Bluetooth Sentinel 主板硬件(原理图+PCB)工程文件.zip

基于STM32F101单片机设计Bluetooth Sentinel 主板硬件(原理图+PCB)工程文件,仅供学习设计参考。
recommend-type

【前端热门框架【vue框架】】——条件渲染和列表渲染的学习的秒杀方式 (2).txt

【前端热门框架【vue框架】】——条件渲染和列表渲染的学习的秒杀方式 (2)
recommend-type

liba2ps1-4.14-bp155.4.9.aarch64.rpm

liba2ps1-4.14-bp155.4.9.aarch64
recommend-type

RTL8188FU-Linux-v5.7.4.2-36687.20200602.tar(20765).gz

REALTEK 8188FTV 8188eus 8188etv linux驱动程序稳定版本, 支持AP,STA 以及AP+STA 共存模式。 稳定支持linux4.0以上内核。
recommend-type

管理建模和仿真的文件

管理Boualem Benatallah引用此版本:布阿利姆·贝纳塔拉。管理建模和仿真。约瑟夫-傅立叶大学-格勒诺布尔第一大学,1996年。法语。NNT:电话:00345357HAL ID:电话:00345357https://theses.hal.science/tel-003453572008年12月9日提交HAL是一个多学科的开放存取档案馆,用于存放和传播科学研究论文,无论它们是否被公开。论文可以来自法国或国外的教学和研究机构,也可以来自公共或私人研究中心。L’archive ouverte pluridisciplinaire
recommend-type

Redis验证与连接:快速连接Redis服务器指南

![Redis验证与连接:快速连接Redis服务器指南](https://img-blog.csdnimg.cn/20200905155530592.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzNTg5NTEw,size_16,color_FFFFFF,t_70) # 1. Redis验证与连接概述 Redis是一个开源的、内存中的数据结构存储系统,它使用键值对来存储数据。为了确保数据的安全和完整性,Redis提供了多
recommend-type

gunicorn -k geventwebsocket.gunicorn.workers.GeventWebSocketWorker app:app 报错 ModuleNotFoundError: No module named 'geventwebsocket' ]

这个报错是因为在你的环境中没有安装 `geventwebsocket` 模块,可以使用下面的命令来安装: ``` pip install gevent-websocket ``` 安装完成后再次运行 `gunicorn -k geventwebsocket.gunicorn.workers.GeventWebSocketWorker app:app` 就不会出现这个报错了。
recommend-type

c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf

校园超市商品信息管理系统课程设计旨在帮助学生深入理解程序设计的基础知识,同时锻炼他们的实际操作能力。通过设计和实现一个校园超市商品信息管理系统,学生掌握了如何利用计算机科学与技术知识解决实际问题的能力。在课程设计过程中,学生需要对超市商品和销售员的关系进行有效管理,使系统功能更全面、实用,从而提高用户体验和便利性。 学生在课程设计过程中展现了积极的学习态度和纪律,没有缺勤情况,演示过程流畅且作品具有很强的使用价值。设计报告完整详细,展现了对问题的深入思考和解决能力。在答辩环节中,学生能够自信地回答问题,展示出扎实的专业知识和逻辑思维能力。教师对学生的表现予以肯定,认为学生在课程设计中表现出色,值得称赞。 整个课程设计过程包括平时成绩、报告成绩和演示与答辩成绩三个部分,其中平时表现占比20%,报告成绩占比40%,演示与答辩成绩占比40%。通过这三个部分的综合评定,最终为学生总成绩提供参考。总评分以百分制计算,全面评估学生在课程设计中的各项表现,最终为学生提供综合评价和反馈意见。 通过校园超市商品信息管理系统课程设计,学生不仅提升了对程序设计基础知识的理解与应用能力,同时也增强了团队协作和沟通能力。这一过程旨在培养学生综合运用技术解决问题的能力,为其未来的专业发展打下坚实基础。学生在进行校园超市商品信息管理系统课程设计过程中,不仅获得了理论知识的提升,同时也锻炼了实践能力和创新思维,为其未来的职业发展奠定了坚实基础。 校园超市商品信息管理系统课程设计的目的在于促进学生对程序设计基础知识的深入理解与掌握,同时培养学生解决实际问题的能力。通过对系统功能和用户需求的全面考量,学生设计了一个实用、高效的校园超市商品信息管理系统,为用户提供了更便捷、更高效的管理和使用体验。 综上所述,校园超市商品信息管理系统课程设计是一项旨在提升学生综合能力和实践技能的重要教学活动。通过此次设计,学生不仅深化了对程序设计基础知识的理解,还培养了解决实际问题的能力和团队合作精神。这一过程将为学生未来的专业发展提供坚实基础,使其在实际工作中能够胜任更多挑战。