哈夫曼树 编码-数据结构（C语言）
导语
本文使用C语言。对某一输入的字符串，对其构造哈夫曼（）树，并由此树的到字符串中每一个字符的哈夫曼编码
本文哈夫曼树和哈夫曼编码采用顺序存储结构实现
哈夫曼树
给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树( Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
哈夫曼树，图片来源百度百科哈夫曼编码
在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8哈夫曼树 编码，4，5，3，1，1}。
现要求为这些字母设计编码。要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。显然编码的长度取决报文中不同字符的个数。若报文中可能出现26个不同字符，则固定编码长度为5
然而，传送报文时总是希望总长度尽可能短。在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码
为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，显然字使用频率越小权值越小，权值越小叶子就越靠下，于是频率小编码长，频率高编码短，这样就保证了此树的最小带权路径长度效果上就是传送报文的最短长度
因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短，该前缀编码称为哈夫曼编码
哈夫曼编码
如上图所示，对于一个字符串“” 来说，很容易知道每个字符出现的频次{3，2，3，4，1}。根据频次，每次选出频次最小的两个结点进行组合，频次相加得到父结点。不断重复此过程，直到产生一颗哈夫曼树。
通过该哈夫曼树，我们可以得到每个字符的哈夫曼编码 A=10，B=001,C=01,D=11,E=000
容易证明，每个字符的编码都是前缀编码
C语言实现哈夫曼编码
网上许多大佬实现哈夫曼树的结点都是采用链式存储结构，而实现哈夫曼编码则是采用指针。
那鄙人就使用顺序存储结构来实现哈夫曼树结点，给大家提供一些思路吧
哈夫曼结点，放在一个数组中，即 []
typedef struct{ //Huffman树结点结构体
float weight; //结点权值，这里是字符出现的频率，及频次/字符种类数
int parent; //父结点位置索引，初始-1
int lchild; //左孩子位置索引，初始-1
int rchild; //右孩子位置索引，初始-1哈夫曼编码结构哈夫曼树 编码，也采用顺序存储结构（数组）
typedef struct{ //Huffman编码结构体
int bit[MAXBIT]; //字符的哈夫曼编码
int start; //该编码在数组bit中的开始位置接受字符串
void str_input(char str[]) {
//输入可包含空格的字符串，输入字符串存放在str中
gets(str);统计字符频次
int TextStatistics(char text[], char ch[], float weight[]) {
//统计每种字符的出现频次，返回出现的不同字符的个数
//出现的字符存放在ch中，对应字符的出现频次存放在weight中
int text_index = 0; //text字符串索引
int ch_index = 0; //计字符数组增加索引，仅用于出现不同字符时，将该字符加入到ch[]中。仅自增
int weight_index = 0;//频数更新索引。用于指定weight[]要更新频数的位置
while(text[text_index]!='\0'){
//查找ch中，是否存在字符text[text_index]，返回查到的第一个字符的位置
char* pos = strchr(ch,text[text_index]);
//如果ch中无该字符。或者ch为空。就将text[text_index]加入到ch中
if(ch[0]==NULL || pos == NULL ){
//加入到统计字符数组中
ch[ch_index] = text[text_index];
//新增一个字符的频数，当所有字符都统计完之后再计算频率
weight[ch_index] += 1;
ch_index++;
}
//如果字符串中有该字符
else{
//找到该字符的索引位置，更新其频数
weight_index = pos - ch ;
weight[weight_index] += 1;
}
text_index++;
}
ch[ch_index] = '\0';//添加结束符
//根据频数计算频率
int index=0;
while(weight[index]!=0){
weight[index]/=text_index;
index++;
}
//最终 ch_index的值即为text字符串中不同字符的个数
return ch_index;找到权值最小的两个结点
// 从 HuffNodes[0..range]中，找到最小的结点索引赋给s1,s2 。已经找到过的结点索引被储存在out[]中
void select(HNodeType HuffNodes[],int range,int *s1,int *s2){
//先找第一个最小值 。
float min1 = 5;
for(int index1=0;index1lchild
HuffNodes[node_index]->rchild
*/
HuffNodes[node_index].weight = weight[node_index];
HuffNodes[node_index].parent = -1;
HuffNodes[node_index].lchild = -1;
HuffNodes[node_index].rchild = -1;
}
//构造非叶节点
for(;node_index
[1]: https://xuan.ddwoo.top/index.php/archives/242/
[2]: https://xuan.ddwoo.top/index.php/archives/246/
本文共 1342 个字数,平均阅读时长 ≈ 4分钟腾讯云开发者
