实验3：哈夫曼编码.pdfVIP

实验 3 ：霍夫曼编码 学生姓名： 学 号： 一、实验室名称：信息与编码课程组 二、实验项目名称：霍夫曼编码 三、实验原理： 1）将q 个信源符号按概率大小递减排列p (s )  p (s )   p (s ) ； 1 2 q 2 ）用 “0 ，1”马符号分别代表概率最小的两个信源符号，并将这两个概率最小的信源 符号合并成一个，从而得到只包含q  1个符号的新信源，称为缩减信源S ； 1 3 ）把缩减信源S1 的符号仍按概率大小递减次序排列，再将其最后两个概率最小的信源 符号分别用 “0 ”和 “1”码符号表示，并且合并成一个符号，这样又形成了q  2 个信源符 号的缩减信源S 2 ； 4 ）依次继续下去，直至信源最后只剩下两个信源符号为止，将这最后两个信源符号分 别用二元码符号“0 ”和“1”表示； 5 ）然后从最后—级缩减信源开始，进行回溯，就得到各信源符号所对应的码符号序列， 即相应的码字。 四、实验目的： (1)进一步熟悉Huffman编码过程；(2)掌握C语言递归程序的设计和调试技术。以巩固课 堂所学编码理论的知识。 五、实验内容： s , s ,  ,s   S   1 2 q  对于给定的信源  ，利用霍夫曼编码方法编出其中一种紧致 P       p (s ),p (s ), , p (s )   1 2 q  码。 六、实验器材（设备、元器件）： PC 机一台，装有 VC++6.0 或其它 C 语言集成开发环境。 七、实验步骤及操作： 1）排序； 2 ）缩减信源； 3 ）递归调用霍夫曼算法得到相应的码字。 八、实验数据及结果分析：    S   s1 s2 s3 s4 s5 s6 s7 s8  题目：已知信源：   ，给出其中一 P       0.20, 0.18, 0.17, 0.15, 0.15, 0.05, 0.05, 0.05 个霍夫曼码，并求其平均码长和编码效率。 #include stdio.h #include stdlib.h #include float.h #include math.h #define n 8 #define m 2*n-1 typedef struct { float weight; int lchild,rchild,parent; }HTNode; typedef HTNode HuffmanTree[m]; void InitHuffmanTree(HuffmanTree T) { for(int i = 0;i m;i++) { T[i].lchild = T[i].rchild = T[i].parent = -1; T[i].weight = 0.0; } } void InputWeight(HuffmanTree T) { float temp[n] = {0.20,0.18,0.17,0.15,0.15,0.05,0.05,0.05}; for(int i = 0;i n;i++) T[i].weight