哈夫曼树实验报告.doc

《哈夫曼树实验报告.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、实验报告1、实验目的：(1)理解哈夫曼树的含义和性质。(2)掌握哈夫曼树的存储结构以及描述方法。(3)掌握哈夫曼树的生成方法。(4)掌握哈夫曼编码的一般方法，并理解其在数据通讯中的应用。2、实验内容：哈夫曼树与哈弗曼编码、译码a.问题描述：哈夫曼问题的提出可以参考教材P.145.利用哈弗曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。b.算法提示：参见教材P.147-148算法6.12、6.13的描述。3、实验要求：建立哈夫曼树，实现编码，译码。.初始化（Initializa

2、tion）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。.编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。.译码（Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。.输出代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。.输出哈夫曼树（TreePrinting）

3、。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据：设权值c=(a,b,c,d,e,f,g,h)w=（5，29，7，8，14，23，3，11），n=8。    按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：    5：0001，29：11，7：1110，8：1111    14：110，23：01，3：0000，11：001。四实验代码#include#include#include#include

4、#includetypedefstruct{intweight,K;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;charstr[50];intwa[50];HuffmanTreeHT;HuffmanCodeHC;intw[50],i,j,n=8;charz[50];intflag=0;intnumb=0;//-----------------求哈夫曼编码-----------------------structcou{chardata;intcount;}cou[50]

5、;voidselect(HuffmanTreeHT,intj,int*s1,int*s2){inti;//找weight最小的结点for(i=1;i<=j;i++)if(HT[i].parent==0){*s1=i;break;}for(;i<=j;i++)if((HT[i].parent==0)&&(HT[i].weight

6、rent==0)&&(i!=*s1)&&(HT[i].weight

7、for(p=HT+1,i=1;i<=n;i++,p++){p->weight=wa[i-1];p->parent=0;p->lchild=0;p->rchild=0;}for(;i<=m;++i,++p)p->parent=0;for(i=n+1;i<=m;++i)//建哈夫曼树{select(HT,i-1,&s1,&s2);HT[s1].parent=HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weig