文档介绍：赫夫曼编码
计科132
刘海澍周弘杰徐铭瑶
目录
哈夫曼树的介绍
选题的意义
实验内容
算法及可行性分析
预期结果
赫夫曼编码是哈夫曼树的一个应用
路径上的分支数目称作路径长度
树的路径长度是从树根到每一个结点的路径长度之和
结点的带权路径长度为从该结点到树根之间的路径长度与节点上权的乘积
树的带权路径长度为树中所有叶子结点的带权路径长度之和,通常记作WPL= (W1*L1+W2*L2+W3*L3+...+Wn*Ln)
N个权值构成一棵有N个叶子结点的二叉树,每个叶子结点带权为Wi
相应的叶结点的路径长度为Li(i=1,2,...n)。
最小的二叉树称作最优二叉树或赫夫曼树
构造赫夫曼树
一、对给定的n个权值{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F={T1,T2,T3,...,Ti,...,Tn},其中每棵二叉树Ti中只有一个权值为Wi的根结点,它的左右子树均为空。
二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树,新二叉树的根结点的权值为其左右子树的根结点的权值之和。
三、从F中删除这两棵树,并把这棵新的二叉树同样以升序排列加入到集合F中。
四、重复二和三两步,直到集合F中只有一棵二叉树为止。这棵树便是赫夫曼树。
选题的意义
“哈夫曼编码”是一种一致性编码法(又称“熵编码法”),用于数据的无损耗压缩。这一术语是指使用一张特殊的编码表将源字符(例如某文件中的一个符号)进行编码。
这张编码表的特殊之处在于,它是根据每一个源字符出现的估算概率而建立起来的(出现概率高的字符使用较短的编码,反之出现概率低的则使用较长的编码,这便使编码之后的字符串的平均期望长度降低,从而达到无损压缩数据的目的)
目录
实验内容
【问题描述】
设计一个利用哈夫曼算法的编码和译码系统,重复地显示并处理以下项目,直到选择退出为止。
【选做内容】
(1)显示哈夫曼树;
(2)界面设计的优化。
【基本要求】
(1)初始化:键盘输入字符集大小n、
n个字符和n个权值,建立哈夫曼树;
(2)编码:利用建好的哈夫曼树生成哈夫曼编码;
(3)输出编码;
(4)设字符集及频度如下表:
字符:A B C D E F
频度:4 9 23 2 17 15
字符:G H I J K
频度:1 2 3 3 4
目录
算法及可行性分析
主程序部分
void main()
{
初始化;
构造哈夫曼树;
求哈夫曼编码;
哈夫曼编码输出;
}
哈夫曼树部分
实现哈夫曼树的抽象数据类型
哈夫曼编码部分
实现求哈夫曼编码算法的数据类型
主函数
int main(){
int n;
printf("请输入要输入的字符数量n:");//读入字符的个数
while(scanf("%d",&n),n>=0&&n<=20){ //初始化
printf("请输入n个字符和n个权值\n");
CodeInput(n,ht);//输入数据函数,将读入n个字符和权重
CreateHT(ht,n);//构造哈弗曼树
CreateHCode(ht,hcd,n);//哈弗曼编码算法
CodeOutput(n,hcd);}//打印哈弗曼编码,将打印出编码,和每一个字符的编码
return 0;}
数据类型的定义
哈夫曼树类型
typedef struct{//构造树
char data;//结点权值
int weight;//权重
int parent;//双亲结点
int lchild;//左孩子
int rchild;//右孩子
}HTNode;
HTNode ht[30];
求哈夫曼编码类型
typedef struct{
char cd[30];//存放当前结点的哈弗曼编码
int start;//cd[start]~cd[n]存放哈弗曼码
}HCode;
HCode hcd[30];
程序流程
程序
输入
输出结果