相关文献：
数据结构与算法(一)：基础理论
数据结构与算法(二)：单向链表/单向循环链表/双向链表/双向循环链表的实现
数据结构与算法(三)：线性表算法设计练习
数据结构与算法(四)：斐波那契数列
数据结构与算法(五)：LRU
数据结构与算法(六)：栈
数据结构与算法(七)：栈/队列的算法解题思想
数据结构与算法(八)：队列
数据结构与算法(九)：二叉树/线索化二叉树
数据结构与算法(十)：哈夫曼树
本章节研究内容：
1.哈夫曼思考
2.构建哈夫曼树、哈夫曼编码
3.哈夫曼算法实现
一、哈夫曼思考
假设我是老师去统计学生的成绩评优，并把成绩评级分为如下五个等级：
那么我们的代码就有如下判断:
if( sum < 60)
result = “不及格”;
else if(sum < 70)
result = “及格”;
else if(sum < 80)
result = “中等”;
else if(sum < 90)
result = “良好”;
else
result = “优秀”;
这样的方式虽然简单粗暴，但是会徒增很多没有必要的判断。那么就需要根据一些已知线索来做一些查找优化(线索：比如重点校区成绩肯定偏好)。
根据老师对重点校区的了解学生成绩的分布规律，得到如下图：
重点校区成绩占比
成绩⽐重: 在70~89分之间占⽤了70% 但是都是需要经过3次判断才能得到正确的结果。那么如果数量集⾮常⼤时，这样的⽐较就会出现效率问题。
那我根据这个权重我是不是可以先去判断70~79分的，再去判断80-89分....来减少判断从而达到优化。
注意：这一优化动作的前提是学生成绩分布的规律。
哈弗曼编码一定是现有统计作为前提的。
- 思考问题:
如下图中（A-不及格、B-及格、C-中等、D-良好、E-优秀）
1.结点D(评价良好)的路径⻓度是?
2.树的路径⻓度?
二叉树-优化前
此时二叉树带权重的长度是WPL：
WPL = 1 * 5 + 2 * 15 + 3 *40 +4 * 30 + 4 * 10 = 315
根据学生成绩分布的规律对上图的二叉树进行优化：
二叉树-优化后
WPL = 3 * 5 + 3 * 15 + 2 * 40 + 2 * 30 + 2 * 10 = 220
那么如何利用这种优化去构建哈夫曼树呢？
二、构建哈夫曼树
案例一：(以上面问题为例)
权重升序排序：A-5、E-10、B-15、D-30、C-40
依次对从小到大地去构建二叉树
N1 = 15 = 5 + 10
N2 = 30 = 15 + 15
N3 = 60 = 30 + 30
最终二叉树
WPL = 1 * 40 + 2 * 30 + 3 * 15 + 4 * 10 + 4 * 5 = 205
注意：左子树都是放小的，右子树比左子树的大。
案例二：(注意第⑤步)
假设发送字符数据的编码以及权重如下：
字母 二进制编码 权重值
A 000 27
B 001 8
C 010 15
D 011 15
E 100 30
F 101 5
第①步排序：FBCDAE
字母 二进制编码 权重值
F 101 5
B 001 8
C 010 15
D 011 15
A 000 27
E 100 30
开始构建哈夫曼树：
以最低权重的两个字母节点去构建出新的节点
第⑤步为什么D不和N2构成N3，而是D和A构成N3？
因为N2总权重是28，而A权重是27，所以D和A构成N3更加划算。
于是第⑦步就得到哈夫曼树。（每次都是找到最小的两个值去构成新的节点）
哈夫曼编码
哈夫曼会根据权重来调整字符数据的编码长度，将所有的左子树全部变成0 右子树全部变成1：
于是访问ABCDEF就变成如下：
字母 原编码 新编码
A 000 01
B 001 1001
C 010 101
D 011 00
E 100 11
F 101 1000
数据：BADCADFEED
原编码⼆进制: 001 000 011 010 000 011 101 100 100 011(共30个字符)
新编码⼆进制: 1001 01 00 101 01 00 1001 11 11 00(共25个字符)
数据的解码也是通过哈夫曼树的。
三、哈夫曼算法实现(顺序存储)
哈夫曼树使用顺序存储更为方便，链式会显得更加麻烦。
哈夫曼树的数据结构
哈夫曼编码的数据结构
#include "string.h"
#include "stdio.h"
#include "stdlib.h"
const int MaxValue = 10000;//初始设定的权值最大值
const int MaxBit = 4;//初始设定的最大编码位数
const int MaxN = 10;//初始设定的最大结点个数
// 哈夫曼树节点（顺序存储）
typedef struct HaffNode{
int weight; // 权值
int flag; // 是否已经加入哈夫曼树 0-未加入 1-已加入
int parent; // 双亲节点下标
int leftChild; // 左子树下标
int rightChild; // 右子树下标
}HaffNode;
typedef struct Code//存放哈夫曼编码的数据元素结构
{
int bit[MaxBit];//数组
int start; //编码的起始下标
int weight;//字符的权值
}Code;
//1.根据权重值,构建哈夫曼树
//{2,4,5,7}
//n = 4; 权重值的个数
// haffTree - 被构建的哈夫曼树
void Haffman(int weight[],int n,HaffNode *haffTree){
int j,m1,m2,x1,x2;
//1.哈夫曼树初始化 - 此时haffTree数组里全是叶子节点，都在前面的位置啦
//（不需要排序哟，第二部会帮我们挑选最小值）
//n个叶子结点. 总共有 2n-1 个节点
for(int i = 0; i < 2*n-1;i++) {
if(i<n)
// 是叶子节点 赋值权重值
haffTree[i].weight = weight[i];
else
haffTree[i].weight = 0;
// 全部信息都不知道，并且没有加入到哈夫曼树，先给定初始值
haffTree[i].parent = 0;
haffTree[i].flag = 0;
haffTree[i].leftChild = -1;
haffTree[i].rightChild = -1;
}
//2.构造哈夫曼树haffTree的n-1个非叶结点
for (int i = 0; i < n-1; i++) {
m1 = m2 = MaxValue; // 存储最小的两个权重
x1 = x2 = 0; // 存储最小的两个权重的下标
//2,4,5,7
//循环找出所有权重中，最小的二个值--morgan
for (j = 0; j < n+i; j++) {
if (haffTree[j].weight < m1 && haffTree[j].flag == 0) {
m2 = m1;
x2 = x1;
m1 = haffTree[j].weight;
x1 = j;
} else if (haffTree[j].weight < m2 && haffTree[j].flag == 0) {
m2 = haffTree[j].weight;
x2 = j;
}
}
// 拿到最小的两个节点，去构建新的节点
//（新的节点只需要添加到n+i下标的位置）
// 3.将找出的两棵权值最小的子树合并为一棵子树
haffTree[x1].parent = n + i;
haffTree[x2].parent = n + i;
//将2个结点的flag 标记为1,表示已经加入到哈夫曼树中
haffTree[x1].flag = 1;
haffTree[x2].flag = 1;
//修改n+i结点的权值
haffTree[n + i].weight = haffTree[x1].weight + haffTree[x2].weight;
//修改n+i的左右孩子的值
haffTree[n + i].leftChild = x1;
haffTree[n + i].rightChild = x2;
}
}
/*
2 哈夫曼编码
由n个结点的哈夫曼树haffTree构造哈夫曼编码haffCode
//{2,4,5,7}
*/
void HaffmanCode(HaffNode haffTree[], int n, Code haffCode[]) {
//1.创建一个结点cd
Code *cd = (Code * )malloc(sizeof(Code));
int child, parent;
//2.求n个叶结点的哈夫曼编码
for (int i = 0; i<n; i++) {
//从0开始计数
cd->start = 0;
//取得编码对应权值的字符
cd->weight = haffTree[i].weight;
//当叶子结点i 为孩子结点.
child = i;
//找到child 的双亲结点;
parent = haffTree[child].parent;
//由叶结点向上直到根结点
while (parent != 0) {
if (haffTree[parent].leftChild == child)
cd->bit[cd->start] = 0;//左孩子结点编码0
else
cd->bit[cd->start] = 1;//右孩子结点编码1
//编码自增
cd->start++;
//当前双亲结点成为孩子结点
child = parent;
//找到双亲结点
parent = haffTree[child].parent;
}
int temp = 0;
for (int j = cd->start - 1; j >= 0; j--){
temp = cd->start-j-1;
haffCode[i].bit[temp] = cd->bit[j];
}
//把cd中的数据赋值到haffCode[i]中.
//保存好haffCode 的起始位以及权值;
haffCode[i].start = cd->start;
//保存编码对应的权值
haffCode[i].weight = cd->weight;
}
}
测试代码
int main(int argc, const char * argv[]) {
// insert code here...
printf("Hello, 哈夫曼编码!\n");
int i, j, n = 4, m = 0;
//权值
int weight[] = {2,4,5,7};
//初始化哈夫曼树, 哈夫曼编码
HaffNode *myHaffTree = malloc(sizeof(HaffNode)*2*n-1);
Code *myHaffCode = malloc(sizeof(Code)*n);
//当前n > MaxN,表示超界. 无法处理.
if (n>MaxN) {
printf("定义的n越界，修改MaxN!");
exit(0);
}
//1. 构建哈夫曼树
Haffman(weight, n, myHaffTree);
//2.根据哈夫曼树得到哈夫曼编码
HaffmanCode(myHaffTree, n, myHaffCode);
//3.
for (i = 0; i<n; i++)
{
printf("Weight = %d\n",myHaffCode[i].weight);
for (j = 0; j<myHaffCode[i].start; j++)
printf("%d",myHaffCode[i].bit[j]);
m = m + myHaffCode[i].weight*myHaffCode[i].start;
printf("\n");
}
printf("Huffman's WPS is:%d\n",m);
return 0;
}
网友评论