哈夫曼编码报告

1、实验项目：哈夫曼编码1.问题描述：利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这 要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（解码）。对于 双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站设计一个哈夫曼编/译码系统。. 一个完整的系统应具有以下功能：1）初始化（Initialzation ）。读入字符及每个字符的权值，建立哈夫曼树 HuffTree ;2）编码（Encoding ）。用已建好的哈夫曼树，对输入的文本进行编码形成报文，将报文显示出来；3）译码（Decoding）。

2、利用已建好的哈夫曼树，对输入的代码进行解码形成原文，并将结果显示；4）输出（Output ）:输出出现的字符以及各字符出现的频度（或概率）；输出各个字符的编码，输 出代码译出的原文；.实验目的：理解哈夫曼树的特征及其应用；在对哈夫曼树进行理解的基础上，构造哈夫曼树，并用构造的哈夫 曼树进行编码和译码；通过该实验，使学生对数据结构的应用有更深层次的理解。.实验条件 :学院提供公共机房，1台/学生微型计算机。.实验步骤（含实验代码）第1次：完成程序的主框架设计，进行调试，验证其正确性；第2次：详细设计，进行调试，验证其正确性；第3次：进行整体调试，运行程序，对运行结果进行分析，完成实验报告 。#i

3、nclude#include #include#define MAXWORD 100typedef struct unsigned int weight;char data;unsigned int parent,llchild,rrchild;HTNode,*HuffmanTree;arent=0;(*p).llchild=0;(*p).rrchild=0;for(p=HT+1,i=0;in;+i,+p) (*p).data=stri;(*p).weight=si;for(;i=m;+i,+p)(*p).parent=0;for(i=n+1;i=m;+i)arent=HTs2.parent=

4、i;HTi.llchild=s1;HTi.rrchild=s2;HTi.weight=HTs1.weight+HTs2.weight;HC=(HuffmanCode)malloc(n+1)*sizeof(char*);arent;f!=0;c=f,f=HTf.parent)if(HTf.llchild=c)cd-start=0;elsecd-start=1;HCi=(char*)malloc(n -start)*sizeof(char);strcpy(HCi,&cdstart);eightk&tj.parent=0)k=tj.weight,flag=j;tflag.parent=1;retur

5、n flag;void Creatree(BT &p,char c)ata);puts(HCi);void Tran(HuffmanTree HT,int n)lchild;elsei=HTi.rrchild;if(HTi.llchild=0)printf(%c,HTi.data);i=2*n -1; j+; printf(n);void TTranChar(HuffmanTree HT,HuffmanCode HC,int n) char ss50;int i,j;ata!=ssi)&(j=n)j+；printf(%s,HCj);i+；printf(n);.实验结果与总结:产输入要用几种字符

6、：4请输入字符串；aarfffjjjjjjjbbbbb 字符及出现次数： 且的个数为：2匕的个数为：5 尸的个澈为:4 j的个数为：？输出哈夫曼编码： TOC o 1-5 h z 11O10f:111J：0输入发送的（0. 1编码（以为结束标志）t 110101110010101111100 择码后的字符为ahf j北bfaj 输入字符串：jj j j jj j00111111110100000011111100Ptes居key tq continue总结：在实现哈夫曼树编码的过程中，首先构建哈夫曼树，并用动态分配数 组存储，也用动态分配数组存储哈夫曼编码表。程序书上虽然有一部分可借鉴 的代码，自己只需要编写几个函数即可，但在编写程序时也遇到一些问题，开 始统计字符串中出现的各种字符及其次数时，将字母存放数组中，但是考虑到 字母出现的不同，完全初始化再统计其出现的个数，不仅占用空间并且时间复 杂度高。后来采用二叉树统计出现的字母及个数，实现了输入字母种类的灵活 性。通过此次实验，明白了了解数据存储的具体方式的重要性，在这次实验中