《IT实验2-Huffman编码.doc》由会员分享，可在线阅读，更多相关《IT实验2-Huffman编码.doc（5页珍藏版）》请在金锄头文库上搜索。
1、云南大学数学与统计学院数学系信息与计算科学专业云南大学数学与与统计学院上机实践报告课程名称：信息论基础实验年级：2010上机实践成绩：指导教师：陆正福姓名：上机实践名称：Huffman编码学号：上机实践日期2013/3/13上机实践编号：No.2组号：上机实践时间：一、实验目的1.进一步熟悉Huffman编码过程2.加深对最优码的理解二、实验内容1.编程实现Huffman编码算法三、实验环境Microsoft visual c+6.0和个人计算机四、实验结果Huffman编码原理的实现实现Huffman编码原理的步骤如下：(1)将信源符号的出现概率按减J、的Jl页序j歹0；(2)将两个最小的概
2、率进行组合相加，并继续这一步骤，始终将较高的概率分支放在上部，直到概率达到10为止；(3)对每对组合的上边一个指定为l，下边一个指定为0 (或相反)；(4)画出每个信源符号概率到10的路径，记下沿路径的l和0；(5)对于每个信源符号都写出l、0序列，则从右到左就得到霍夫曼码。C语言编程为：#include#include#include#define N 50 / 叶子节点数目的最大值#define M 2*N-1 /树中结点总数typedef struct char data5; /结点值 int weight; /权重值 int parent; int lchild; int rchild
3、;HTNode;/定义huffman树存储结构typedef char*HuffmanCode;void CreatHT(HTNode ht,int n)char *str=p1,p2,p3,p4,p5;int fnum=25,25,20,15,15;int i,k,lnode,rnode;int min1,min2;for(i=0;in;i+) /初始化ht数组 strcpy(hti.data,stri); hti.weight=fnumi;for(i=0;i2*n-1;i+) hti.parent=-1; hti.lchild=-1; hti.rchild=-1;for(i=n;i2*n-
4、1;i+) min1=32767;min2=32767; /存放最小和次小权重值 lnode=-1;rnode=-1; / 存放最小和次小结点位置 for(k=0;k=i-1;k+) if(htk.parent=-1) if(htk.weightmin1) min2=min1; rnode=lnode; min1=htk.weight; lnode=k; else if(htk.weightrnode) hti.lchild=rnode; hti.rchild=lnode; else if(lnodernode) hti.lchild=lnode; hti.rchild=rnode; void
5、 CreatHCode(HTNode ht,HuffmanCode hcd,int n) int i,f,c,temp; char *hc; for(i=0;in;i+) hc=(char *)malloc(n*sizeof(char); hcn=0; temp=n-1; c=i; f=hti.parent; while(f!=-1) if(htf.lchild=c) hctemp-=0; else hctemp-=1; c=f; f=htf.parent; hcdi=(char *)malloc(n-temp)*sizeof(char); strcpy(hcdi,hc+temp+1); vo
6、id DispHCode(HTNode ht,HuffmanCode hcd,int n) int i,j,sum=0,m=0; printf(输出哈夫曼码:n); for(i=0;in;i+) j=0; printf( %s:t,hti.data); while(hcdij!=0) printf(%c,hcdij); j+; m+=hti.weight; sum+=hti.weight*j; printf(n); printf(n 平均长度=%gn,1.0*sum/m);void Translation(HTNode ht,HuffmanCode hcd,int n) int parent,
7、i,j=0; char k; parent=2*n-2; printf(输出译码:n); for(i=0;in;i+) printf( %s,hcdi); while(htparent.rchild!=-1&htparent.lchild!=-1) k=hcdij; if(k=1) parent=htparent.lchild; else if(k=0) parent=htparent.rchild; j+; printf( %stn,hti.data); j=0; void main() int n=5; HTNode htM; HuffmanCode hcd; hcd=(HuffmanCode)malloc(2*n)*sizeof(char *); CreatHT(ht,n); CreatHCode(ht,hcd,n); DispHCode(ht,hcd,n); Translation(ht,hcd,n); printf(n);在C+中运行得到结果为：第 5 页 共 6 页
