C语言实现输入超过10字符的字符串后再输入这些字符的频度,输出这些字符的哈夫曼编码

时间: 2023-06-19 21:05:44 浏览: 64
要实现输入超过10字符的字符串后再输入这些字符的频度,可以使用一个字符数组来存储输入的字符串,然后使用一个整型数组来记录每个字符出现的频度。具体实现可以参考下面的代码: ```c #include <stdio.h> #include <stdlib.h> #include <string.h> #define MAX_LEN 100 // 字符串最大长度 // 哈夫曼树节点 typedef struct node { char ch; // 字符 int freq; // 频度 struct node *left; // 左子节点 struct node *right; // 右子节点 } Node; // 哈夫曼编码表项 typedef struct { char ch; // 字符 char *code; // 编码 } CodeTableItem; // 创建哈夫曼树 Node *createHuffmanTree(Node *nodes[], int count) { while (count > 1) { // 找到频度最小的两个节点 int min1 = 0, min2 = 1; if (nodes[min1]->freq > nodes[min2]->freq) { min1 = 1; min2 = 0; } for (int i = 2; i < count; i++) { if (nodes[i]->freq < nodes[min1]->freq) { min2 = min1; min1 = i; } else if (nodes[i]->freq < nodes[min2]->freq) { min2 = i; } } // 合并两个节点 Node *newNode = (Node *) malloc(sizeof(Node)); newNode->ch = '\0'; newNode->freq = nodes[min1]->freq + nodes[min2]->freq; newNode->left = nodes[min1]; newNode->right = nodes[min2]; nodes[min1] = newNode; nodes[min2] = nodes[count - 1]; count--; } return nodes[0]; } // 生成哈夫曼编码表 void createCodeTable(Node *root, char *prefix, int depth, CodeTableItem *codeTable, int *count) { if (root->left == NULL && root->right == NULL) { // 叶子节点,添加编码表项 CodeTableItem item; item.ch = root->ch; item.code = (char *) malloc((depth + 1) * sizeof(char)); strncpy(item.code, prefix, depth); item.code[depth] = '\0'; codeTable[*count] = item; (*count)++; } else { // 非叶子节点,继续递归 prefix[depth] = '0'; createCodeTable(root->left, prefix, depth + 1, codeTable, count); prefix[depth] = '1'; createCodeTable(root->right, prefix, depth + 1, codeTable, count); } } // 查找字符的哈夫曼编码 char *findCode(CodeTableItem *codeTable, int count, char ch) { for (int i = 0; i < count; i++) { if (codeTable[i].ch == ch) { return codeTable[i].code; } } return NULL; } int main() { char str[MAX_LEN + 1]; // 输入的字符串 int freq[256] = {0}; // 每个字符出现的频度 int len = 0; // 字符串长度 while (1) { printf("请输入一个字符串:"); fgets(str + len, MAX_LEN - len + 1, stdin); // 读取剩余的字符 len = strlen(str); if (str[len - 1] == '\n') { str[len - 1] = '\0'; // 去掉换行符 len--; } if (len >= MAX_LEN) { break; // 字符串已达到最大长度,退出循环 } } for (int i = 0; i < len; i++) { freq[(unsigned char) str[i]]++; // 统计频度 } // 创建哈夫曼树 Node *nodes[256]; int nodeCount = 0; for (int i = 0; i < 256; i++) { if (freq[i] > 0) { Node *node = (Node *) malloc(sizeof(Node)); node->ch = (char) i; node->freq = freq[i]; node->left = NULL; node->right = NULL; nodes[nodeCount] = node; nodeCount++; } } Node *root = createHuffmanTree(nodes, nodeCount); // 生成哈夫曼编码表 CodeTableItem codeTable[256]; int codeCount = 0; char prefix[256] = ""; createCodeTable(root, prefix, 0, codeTable, &codeCount); // 输出编码表和编码后的字符串 printf("编码表:\n"); for (int i = 0; i < codeCount; i++) { printf("%c: %s\n", codeTable[i].ch, codeTable[i].code); } printf("编码后的字符串:\n"); for (int i = 0; i < len; i++) { char *code = findCode(codeTable, codeCount, str[i]); printf("%s", code); } printf("\n"); // 释放内存 for (int i = 0; i < nodeCount; i++) { free(nodes[i]); } for (int i = 0; i < codeCount; i++) { free(codeTable[i].code); } return 0; } ``` 上述代码中,我们使用字符数组 `str` 来存储输入的字符串,使用整型数组 `freq` 来记录每个字符出现的频度。当输入的字符串长度超过10时,程序会停止读取输入,并统计每个字符的频度。然后,我们根据频度创建哈夫曼树,再根据哈夫曼树生成哈夫曼编码表,最后使用哈夫曼编码表对输入字符串进行编码,并输出编码后的字符串和哈夫曼编码表。 需要注意的是,由于 C 语言中没有字符串类型,因此我们要使用字符数组来存储字符串,并使用字符串操作函数来处理字符数组。此外,由于字符数组中可能包含任意字符,因此我们需要使用无符号字符类型 `unsigned char` 来表示字符,以保证程序的正确性。

相关推荐

最新推荐

recommend-type

C语言中压缩字符串的简单算法小结

主要介绍了C语言中可用于实现字符串压缩的简单算法小结,列举了包括哈夫曼算法等三个核心的程序实现算法,需要的朋友可以参考下
recommend-type

C语言实现哈夫曼树的构建

主要为大家详细介绍了C语言实现哈夫曼树的构建,文中示例代码介绍的非常详细,具有一定的参考价值,感兴趣的小伙伴们可以参考一下
recommend-type

赫哈曼编码的应用对输入的一串字符实现赫夫曼编码,再对赫夫曼编码生成的代码串进行译码,输出电文字符串

本设计要求是对输入的一串字符实现赫夫曼编码,再对赫夫曼编码生成的代码串进行译码,输出电文字符串。赫夫曼编码是一种将信息转换成二进制编码有效的方法之一,赫夫曼编码是利用赫夫曼树求得的用于通信的二进制编码...
recommend-type

哈夫曼树及哈夫曼编码译码的实现

定义哈夫曼树的存储结构;输入要编码的字符权重,根据权重建立哈夫曼树,并进行编码,最后输出哈夫曼编码。
recommend-type

zigbee-cluster-library-specification

最新的zigbee-cluster-library-specification说明文档。
recommend-type

管理建模和仿真的文件

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

实现实时数据湖架构:Kafka与Hive集成

![实现实时数据湖架构:Kafka与Hive集成](https://img-blog.csdnimg.cn/img_convert/10eb2e6972b3b6086286fc64c0b3ee41.jpeg) # 1. 实时数据湖架构概述** 实时数据湖是一种现代数据管理架构,它允许企业以低延迟的方式收集、存储和处理大量数据。与传统数据仓库不同,实时数据湖不依赖于预先定义的模式,而是采用灵活的架构,可以处理各种数据类型和格式。这种架构为企业提供了以下优势: - **实时洞察:**实时数据湖允许企业访问最新的数据,从而做出更明智的决策。 - **数据民主化:**实时数据湖使各种利益相关者都可
recommend-type

list根据id查询pid 然后依次获取到所有的子节点数据

可以使用递归的方式来实现根据id查询pid并获取所有子节点数据。具体实现可以参考以下代码: ``` def get_children_nodes(nodes, parent_id): children = [] for node in nodes: if node['pid'] == parent_id: node['children'] = get_children_nodes(nodes, node['id']) children.append(node) return children # 测试数
recommend-type

JSBSim Reference Manual

JSBSim参考手册,其中包含JSBSim简介,JSBSim配置文件xml的编写语法,编程手册以及一些应用实例等。其中有部分内容还没有写完,估计有生之年很难看到完整版了,但是内容还是很有参考价值的。
recommend-type

"互动学习:行动中的多样性与论文攻读经历"

多样性她- 事实上SCI NCES你的时间表ECOLEDO C Tora SC和NCESPOUR l’Ingén学习互动,互动学习以行动为中心的强化学习学会互动,互动学习,以行动为中心的强化学习计算机科学博士论文于2021年9月28日在Villeneuve d'Asq公开支持马修·瑟林评审团主席法布里斯·勒菲弗尔阿维尼翁大学教授论文指导奥利维尔·皮耶昆谷歌研究教授:智囊团论文联合主任菲利普·普雷教授,大学。里尔/CRISTAL/因里亚报告员奥利维耶·西格德索邦大学报告员卢多维奇·德诺耶教授,Facebook /索邦大学审查员越南圣迈IMT Atlantic高级讲师邀请弗洛里安·斯特鲁布博士,Deepmind对于那些及时看到自己错误的人...3谢谢你首先,我要感谢我的两位博士生导师Olivier和Philippe。奥利维尔,"站在巨人的肩膀上"这句话对你来说完全有意义了。从科学上讲,你知道在这篇论文的(许多)错误中,你是我可以依