《实验一哈夫曼编码》由会员分享,可在线阅读,更多相关《实验一哈夫曼编码(12页珍藏版)》请在金锄头文库上搜索。
1、实验一 哈夫曼编码,实验目的 掌握哈夫曼编码原理 理解数据压缩的实现过程,实验要求,根据哈夫曼编码算法,对下列信源实现哈夫曼编码。求出编码后的平均码长。,实验内容与步骤,1、实验内容 对上面信源进行哈夫曼编码。 显示出每个符号的分配代码及平均码长 2、实验步骤 (1)初始化,根据符号概率的大小按由大到小顺序对符号进行排序。 (2)把概率最小的两个符号组成一个节点。 (3)重复步骤(1)(2),直到概率和为1 (4)从根节点开始到相应于每个符号的“树叶”,概率大的标“0”,概率小的标“1” (5)从根节点开始,对符号进行编码。,实验结果要求,1、哈夫曼编码程序。 2、实验报告(含流程图),0.2
2、3 0.21 0.18 0.15 0.13 0.07 0.03,概率,1,0,0.10,1,0,0.23,1,0,0.33,1,0,0.44,1,0,0.56,0,1,1,A1 A2 A3 A4 A5 A6 A7,符号,哈夫曼编码举例,#include #include #define N 15 #define M 2*N-1 typedef struct float weight; int parent,lchild,rchild; HTNode; typedef struct char data; float weight; char codeN; HTCode;,参考程序,void In
3、it(HTCode hc,int *n) int i; printf(“n input n=“); scanf(“%d“, ,参考程序(续),void Select(HTNode ht,int k,int *s1,int *s2) int i; for(i=1;i=k;i+) if(hti.parent=0) *s1=i; break; for(i=1;i=k;i+) if(hti.parent=0 ,参考程序(续),for(i=1;i=k;i+) if(hti.parent=0 ,参考程序(续),void HuffmanCoding(HTNode ht,HTCode hc,int n) ch
4、ar cdN; int i,j,m,c,f,s1,s2,start; m=2*n-1; for(i=1;i=m;i+) if(i=n) hti.weight=hci.weight; else hti.weight=0.0; hti.parent=hti.lchild=hti.rchild=0; for(i=n+1;i=m;i+) Select(ht,i-1, ,参考程序(续),for(i=1;i=m;i+) printf(“n the %d charactor weight is %f:“,i,hti.weight); printf(“n the %d charactor lchild is
5、%d:“,i,hti.lchild); printf(“n the %d charactor rchild is %d:“,i,hti.rchild); printf(“n the %d charactor parent is %d:“,i,hti.parent); for(i=0;iN;i+) cdi= ; cdn-1=0; for(i=1;i=n;i+) start=n-1; for(c=i,f=hti.parent;f;c=f,f=htf.parent) if(htf.lchild=c) cd-start=0; else cd-start=1; strcpy(hci.code, ,参考程序(续),void main() int i,m,n,wN+1; float l=0.0; float arg,*point= ,参考程序(续),