信息论课程实验报告—哈夫曼编码

实验3：霍夫曼编码学生姓名：学号：一、实验室名称：信息与编码课程组二、实验项目名称：霍夫曼编码三、实验原理：1）将q个信源符号按概率大小递减排列)()()(21qspspsp；2）用“0，1”马符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源符号合并成一个，从而得到只包含1q个符号的新信源，称为缩减信源1S；3）把缩减信源1S的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源符号分别用“0”和“1”码符号表示，并且合并成一个符号，这样又形成了2q个信源符号的缩减信源2S；4）依次继续下去，直至信源最后只剩下两个信源符号为止，将这最后两个信源符号分别用二元码符号“0”和“1”表示；5）然后从最后—级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列，即相应的码字。四、实验目的：(1)进一步熟悉Huffman编码过程；(2)掌握C语言递归程序的设计和调试技术。以巩固课堂所学编码理论的知识。五、实验内容：对于给定的信源)(,),(),(,,,2121qqspspspsssPS，利用霍夫曼编码方法编出其中一种紧致码。六、实验器材（设备、元器件）：PC机一台，装有VC++6.0或其它C语言集成开发环境。七、实验步骤及操作：1）排序；2）缩减信源；3）递归调用霍夫曼算法得到相应的码字。八、实验数据及结果分析：题目：已知信源：05.0,05.0,05.0,15.0,15.0,17.0,18.0,20.087654321ssssssssPS，给出其中一个霍夫曼码，并求其平均码长和编码效率。#includestdio.h#includestdlib.h#includefloat.h#includemath.h#definen8#definem2*n-1typedefstruct{floatweight;intlchild,rchild,parent;}HTNode;typedefHTNodeHuffmanTree[m];voidInitHuffmanTree(HuffmanTreeT){for(inti=0;im;i++){T[i].lchild=T[i].rchild=T[i].parent=-1;T[i].weight=0.0;}}voidInputWeight(HuffmanTreeT){floattemp[n]={0.20,0.18,0.17,0.15,0.15,0.05,0.05,0.05};for(inti=0;in;i++)T[i].weight=temp[i];}voidSelectMin(HuffmanTreeT,inti,int*p1,int*p2){intj;*p1=*p2=m-1;T[m-1].weight=FLT_MAX;for(j=0;j=i;j++){if(T[j].parent!=-1)continue;if(T[j].weightT[*p1].weight){*p2=*p1;*p1=j;}elseif(T[j].weightT[*p2].weight)*p2=j;}}voidCreateHuffmanTree(HuffmanTreeT){inti,p1,p2;InitHuffmanTree(T);InputWeight(T);for(i=n;im;i++){SelectMin(T,i-1,&p1,&p2);T[p1].parent=T[p2].parent=i;T[i].lchild=p1;T[i].rchild=p2;T[i].weight=T[p1].weight+T[p2].weight;}}intPrintHuffmanCode(HuffmanTreeT,inti){printf(s%d\t%f\t,i+1,T[i].weight);intarr[n-1],count=0,j;while(T[i].parent!=-1){arr[count++]=T[T[i].parent].lchild==i?0:1;i=T[i].parent;}for(j=count-1;j=0;j--)printf(%d,arr[j]);printf(\n);returncount;}intmain(){HuffmanTreeT;CreateHuffmanTree(T);floatave=0;for(inti=0;in;i++)ave+=T[i].weight*PrintHuffmanCode(T,i);printf(平均码长:\t%f\n,ave);printf(编码效率:\t%f%%\n,ave/ceil(log((double)n)/log((double)2))*100);system(pause);}九、实验结论：十、总结及心得体会：本实验让我学习了使用霍夫曼编码进行编程的方法，并对霍夫曼编码的知识有了进一步了解。报告评分：指导教师签字：