从键盘接收一串电文字符,输出对应的编码,同时,能翻译由哈夫曼编码生成的代码串,输出对应的电文字符串。用c语言实现,设计要求:
(1)构造一棵哈夫曼树;
(2)输出哈夫曼树的中序遍历序列(字符及其权值);
(3)实现哈夫曼编码,并用哈夫曼编码生成的代码串进行译码;
哈夫曼编码译码,中序遍历
- 写回答
- 好问题 0 提建议
- 追加酬金
- 关注问题
- 邀请回答
-
8条回答 默认 最新
- qq_43629904 2023-04-08 16:03关注
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_TREE_HT 100 //定义哈夫曼树节点结构体 struct MinHeapNode { char data; unsigned freq; struct MinHeapNode *left, *right; }; //定义哈夫曼树结构体 struct MinHeap { unsigned size; unsigned capacity; struct MinHeapNode **array; }; //创建一个新的哈夫曼树节点 struct MinHeapNode* newNode(char data, unsigned freq) { struct MinHeapNode* temp = (struct MinHeapNode*)malloc(sizeof(struct MinHeapNode)); temp->left = temp->right = NULL; temp->data = data; temp->freq = freq; return temp; } //创建一个新的最小堆 struct MinHeap* createMinHeap(unsigned capacity) { struct MinHeap* minHeap = (struct MinHeap*)malloc(sizeof(struct MinHeap)); minHeap->size = 0; minHeap->capacity = capacity; minHeap->array = (struct MinHeapNode**)malloc(minHeap->capacity * sizeof(struct MinHeapNode*)); return minHeap; } //交换两个哈夫曼树节点 void swapMinHeapNode(struct MinHeapNode** a, struct MinHeapNode** b) { struct MinHeapNode* t = *a; *a = *b; *b = t; } //最小堆调整函数 void minHeapify(struct MinHeap* minHeap, int idx) { int smallest = idx; int left = 2 * idx + 1; int right = 2 * idx + 2; if (left < minHeap->size && minHeap->array[left]->freq < minHeap->array[smallest]->freq) smallest = left; if (right < minHeap->size && minHeap->array[right]->freq < minHeap->array[smallest]->freq) smallest = right; if (smallest != idx) { swapMinHeapNode(&minHeap->array[smallest], &minHeap->array[idx]); minHeapify(minHeap, smallest); } } //检查是否只有一个节点 int isSizeOne(struct MinHeap* minHeap) { return (minHeap->size == 1); } //从最小堆中取出最小值 struct MinHeapNode* extractMin(struct MinHeap* minHeap) { struct MinHeapNode* temp = minHeap->array[0]; minHeap->array[0] = minHeap->array[minHeap->size - 1]; --minHeap->size; minHeapify(minHeap, 0); return temp; } //插入节点到最小堆中 void insertMinHeap(struct MinHeap* minHeap, struct MinHeapNode* minHeapNode) { ++minHeap->size; int i = minHeap->size - 1; while (i && minHeapNode->freq < minHeap->array[(i - 1) / 2]->freq) { minHeap->array[i] = minHeap->array[(i - 1) / 2]; i = (i - 1) / 2; } minHeap->array[i] = minHeapNode; }
忘采纳
解决 无用评论 打赏 举报
悬赏问题
- ¥15 电脑蓝屏logfilessrtsrttrail问题
- ¥20 关于wordpress建站遇到的问题!(语言-php)(相关搜索:云服务器)
- ¥15 【求职】怎么找到一个周围人素质都很高不会欺负他人,并且未来月薪能够达到一万以上(技术岗)的工作?希望可以收到写有具体,可靠,已经实践过了的路径的回答?
- ¥15 Java+vue部署版本反编译
- ¥100 对反编译和ai熟悉的开发者。
- ¥15 带序列特征的多输出预测模型
- ¥15 Python 如何安装 distutils模块
- ¥15 关于#网络#的问题:网络是从楼上引一根网线下来,接了2台傻瓜交换机,也更换了ip还是不行
- ¥15 资源泄露软件闪退怎么解决?
- ¥15 CCF-CSP 2023 第三题 解压缩(50%)