哈夫曼树算法实现并输出每个字符的哈夫曼编码
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
推荐阅读
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
- 画解算法（1.|画解算法：1. 两数之和）
- 【生信技能树】R语言练习题|【生信技能树】R语言练习题 - 中级
- Guava|Guava RateLimiter与限流算法
- java中如何实现重建二叉树
- 一个选择排序算法
- 种树郭橐驼传（文言句式+古今异义+词类活用+通假字）
- SG平滑轨迹算法的原理和实现
- 白杨树
- 《算法》-图[有向图]
- 08黑龙江迟淑荣弯柳树网络学院第五期学习赵宗瑞老师主讲的（传统文化与身心健康）教育体系心得体会