哈夫曼树算法实现并输出每个字符的哈夫曼编码算法与数据结构

1.算法设计思想及功能模块
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。对于这种陆续找出两个最小权值的算法可以利用排序的方式，从小到大排序，那么最左边的就是最小的，这样一来最小的权值可以挑选出来了，接下来再利用特定的结构体（都有左孩子和右孩子还有存放权值的data域）让每一个权值结点存在一个数组中。这样子不断的操作数组，从数组中的5个元素到只有1个元素为止，此时的这一个元素就是二叉树的跟。然后再利用遍历方式打印这个二叉树即可。
根据哈夫曼树构建要求，选取权值最小的两个节点结合，新节点加入数组，再继续选取最小的两个节点继续构建。
2.关键模块流程图

文章图片

3.算法时间及空间复杂度分析
取决于叶子节点个数，时间复杂度O（n），空间复杂度O（1）.
4.源代码

#include #define n 5 #define m (2*n-1)//结点总数 #define maxval 10000.0 #define maxsize 100//哈夫曼编码的最大位数 typedef struct { char ch; float weight; int lchild,rchild,parent; }hufmtree; typedef struct { char bits[n]; //位串 int start; //编码在位串中的起始位置 char ch; //字符 }codetype; void huffman(hufmtree tree[]); //建立哈夫曼树 void huffmancode(codetype code[],hufmtree tree[]); //根据哈夫曼树求出哈夫曼编码void main() { printf("——哈夫曼编码——\n"); printf("总共有%d个字符\n",n); hufmtree tree[m]; //建立哈夫曼树 codetype code[n]; //根据哈夫曼树求出哈夫曼编码 int i,j; //循环变量 huffman(tree); //建立哈夫曼树 huffmancode(code,tree); //根据哈夫曼树求出哈夫曼编码 printf("【输出每个字符的哈夫曼编码】\n"); for(i=0; i 【哈夫曼树算法实现并输出每个字符的哈夫曼编码】文章图片参考https://blog.csdn.net/l494926429/article/details/52494926 推荐阅读梦见自己隐婚是什么意思隐婚是什么意思玻尿酸打到血管的症状有哪些华为手机怎么开启SOS紧急求助华为手机怎么关掉sos紧急求助 QQ浏览器图标怎么点亮 QQ浏览器7级金标点亮方法 note9|四款128G存储手机推荐，均价1500元以内，配置十分均衡牙医|吓尿了！牙医要给我“杀神经”！后悔没早看到这组动图 31类商标金融类商标多少类，43类商标哪些人可以做清远新冠抗体检测哪些人可以做清远新冠抗体检测报告 Promise源码渐进式解读（二）艾灸十天瘦三十斤熏艾 it学什么，IT主要是学什么广东汉乐礼俗教育培训机构税收专项教育培训机构有哪些税，教育培训机构税收政策如何拌茄子泥好吃窍门如何拌茄子泥，如何拌茄子泥好吃 2023元旦档票房破亿 2018元旦档票房运输假币罪的犯罪构成要件是什么橘猫喜欢吃什么 cpue5200什么价，e5520cpu价格调音乐频率安卓软件,酷editpro2.0多声道录音软件亮点|iQOO Z5手机23日发布，亮点颇多无短板画解算法（1.|画解算法：1. 两数之和）【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级 Guava|Guava RateLimiter与限流算法 java中如何实现重建二叉树一个选择排序算法种树郭橐驼传（文言句式+古今异义+词类活用+通假字） SG平滑轨迹算法的原理和实现白杨树《算法》-图[有向图] 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会