哈夫曼树试验评测报告+源程序

1、项目组长学号成员专业班级实验项目名称哈夫曼树指导教师及职称开课学期20182018学年第一学期上课时间2018年9月1日一2018年12月29日、实验设计方案实验名称：哈夫曼树实验时间：2018年12月1日小组合作：是否O小组成员：1、实验目的利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码复原）。对于双工信道即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。2、实验思路实验内容、数据处理方法及实验步骤等）（1I:初始化1

2、nitialization）。从终端读入字符集大小n,以及n个字符和n个权值，建立赫夫曼树，并将它存于文件hfmTree中。（2E：编码Encoding）。利用已建好的赫夫曼树如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。（3D:译码Decoding）。利用已建好的赫夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中（4P:印代码文件vPrint）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。（5T：印赫夫曼树vTreep

3、rinting）。将已在内存中的赫夫曼树以直观的方式比如树）显示在终端上，同时将此字符形式的赫夫曼树写入文件TreePrint中。指导老师对实验设计方案的意见指导老师签名：年月曰二、实验结果与分析1、实验目的、实验思路清输入您舸选择=丄|&342801567612、实验现象、数据及结果权值文件中的信息0代表空格47Q1Z1*事HXMa口亠a口昭魁出阳码出夫AP1FO1EDMBTA.b84R21180H7J027s字权字权字权222321412M3、对实验现象、数据及观察结果的分析与讨论4、结论5、实验总结整体而言，整个程序主要使用了HuffmanCoding（的方式进行哈夫曼编码，在encod

4、ing）里面用了字符串的匹配进行译码，在decode）里进行了重新遍历树的过程，在算法的效率以及如何更为节省空间的存储数据上都要进一步改进。本实验的关键环节及改进措施做好本实验需要把握的关键环节若重做本实验，为实现预期效果，实验步骤应如何改善对实验的自我评价:指导老师评语及得分：签名：年月曰头文件typedefstructunsignedintweight。unsignedintparent,lchild,rchild。HTNode,*HuffmanTree。typedefchar*HuffmanCode。HuffmanTreeHT=NULL。intn=0。HuffmanCodeHC=NULL

5、。char*ch=NULL。voidinitHuffmanTree(。intopenfileInit(。intinputInit(。intHuffmanCoding(int*w。voidSelect(intj,int&s1,int&s2。voidencoding(。voidopenfileEnco(。voidinputEnco(。voiddecode(。voidopenfileDeco(。voidinputDeco(。voiddispHT(HuffmanTreenodeRoot,intlevel#include#include#include哈夫曼树river.husingnamespaces

6、tc。ofstreamoutstuf。voidmain(system(cls。intsel=0。coutttt欢迎进入哈夫曼编码/译码器coutt*coutt*endlcouttt1.构建哈夫曼树tttttendl。couttt2.输出哈夫曼树tttttendl。couttt3.编码ttttttendl。couttt4.译码ttttttendl。couttt5.退出ttttttendl。endlcoutt*coutendlsel。if(sel=5break。switch(sel存在！请先建立哈夫曼树。outstuf.close(。break。case3:encoding(。break。cout

7、endlsel。if(sel=5break。switch(sel存在！请先建立哈夫曼树。outstuf.close(。break。case3:encoding(。break。case1:initHuffmanTree(。break。case2:if(HC=NULLcoutcase4:decode(。break。default:cout对不起，您输入的数据不在1-5内！请重新输入。cout感谢使用本系统！。voidinitHuffmanTree(/选择初始化哈夫曼树intsel=0。system(cls。for(。coutt*coutt*1endlcoutt*字符集及权值来源ttttt*endl

8、。coutt*t1.使用权值文件data.txt进行编码ttt*endl。coutt*t2.自行输入字符集及权值tttt*endl。coutt*t3.返回上层ttttt*endl。coutt*1endlcout请输入您的选择endlsel。if(sel=3break。switch(selcase1:openfileInit(。break。case2:inputInit(。break。default:cout对不起，您输入的数据有误！请重新输入。intopenfileInit(/通过打开的data.txt文件初始化哈夫曼树该文件是为了测试数据2包涵26个字符int*w=(int*malloc(2

9、8*sizeof(intch=(char*malloc(28*sizeof(char。n=27。ifstreaminfile(data.txt,ios:in。system(cls。if(!infilecerropenerror!。cout权值文件中的信息#代表空格)endl=0。i+infilechi。infilewi。cout。cout字符:。for(i=1。icoutchit。cout权值:。for(i=1。icoutwit。cout字符:。for(i=10。icoutchit。cout权值:。for(i=10。icoutwit。cout字符:。for(i=19。icoutchit。cou

10、t权值:。for(i=19。icoutwit。cout。cout各字符编码如下：endl。for(i=1。icoutchit。coutHCi。for(i=1。ioutstufchi。outstuf。return0。system(cls。intinputInit(/通过手动输入字符初始化哈夫曼树system(cls。coutn。int*w=(int*malloc(n+1*sizeof(int。if(!wcoutmalloc(n+1*sizeof(char。if(!chcoutERROR。return0。cout请输入各字符t。for(inti=1。icinchi。cout请输入各权值t。for(

11、i=1。icinwi。/outstuf.close(。outstuf.open(hfmTree.txt,ios:out。for(i=1。ioutstufchi。outstufwi。/将各个字符的权值写入文件hfmTree.txtcout。cout各字符编码如下：。for(i=1。icoutchit。cout。outstuf.open(code.txt,ios:out。for(i=1。ioutstufchi。outstufHCi。/将各个字符的编码写入文件code.txtcout。return0。system(cls。intHuffmanCoding(int*w/哈夫曼编码system(cls。

12、if(nreturn1。intm=2*n-1。HT=(HuffmanTreemalloc(m+1*sizeof(HTNode。if(!HTcoutERROR。return0。for(inti=1。iHTi.weight=wi。HTi.parent=HTi.lchild=HTi.rchild=0。for(。iHTi.weight=HTi.parent=HTi.lchild=HTi.rchild=0。ints1=0。ints2=0。for(i=n+1。iSelect(i-1,s1,s2。HTs1.parent=i。HTs2.parent=i。HTi.lchild=s1。HTi.rchild=s2。

13、HTi.weight=HTs1.weight+HTs2.weight。HC=(HuffmanCodemalloc(n+1*sizeof(char*。char*cd=(char*malloc(n*sizeof(char。if(!cdcoutERROR。return0。cdn-1=0。intstart。for(i=1。istart=n-1。for(intc=i,unsignedintf=HTi.parent。f!=0。c=f,f=HTf.parentif(HTf.lchild=ccd-start=0。elsecd-start=1。HCi=(char*malloc(n-start*sizeof(ch

14、ar。strcpy(HCi,&cdstart。free(cd。return0。system(cls。voidSelect(intj,int&s1,int&s2/选择parent为0，且weight最小的两个节点序号为s1，s2system(cls。for(inth=1。hif(HTh.parent=0s1=h。break。h+。for(。hif(HTh.parent=0s2=h。break。intm。if(HTs1.weightHTs2.weightm=s1。s1=s2。s2=m。h+。for(。hif(HTs1.weightHTh.weight&HTh.parent=0s1=h。for(m=

15、1。mif(HTs2.weightHTm.weight&m!=s1&HTm.parent=0s2=msystem(cls。voidencoding(/选择哈夫曼编码方式system(cls。intsel=0。for(。break。break。if(!HTcout对不起，哈夫曼树不存在！请先建立哈夫曼树。endl。endlcoutt*coutt*要编码的文件来源ttttt*endl。coutt*t1.使用已有文件encode.txt进行编码tt*endl。coutt*t2.自行输入文件进行编码tttt*endl。coutt*t3.返回上层ttttt*endl。coutt*1endlcout请输入

16、您的选择endlsel。if(sel=3break。switch(selcase1:openfileEnco(。break。case2:inputEnco(。break。default:cout对不起，您输入的数据有误！请重新输入。voidopenfileEnco(/通过打开文件encode.txt的方式进行编码system(cls。coutencode.txt文件内容如下#代表空格)：。if(!infilecerropenerror!。char*file=(char*malloc(200*sizeof(char。for(inti=1。infile.eof(=0&i!=200。i+infile

17、filei。coutfile=(char*realloc(file,(200+80*sizeof(char。for(。infile.eof(=0&i!=280。i+infilefilei。cout。coutendl。intm=i。cout编码结果是：。outstuf.open(CodeFile.txt,ios:out。for(i=1。ifor(intj=1。jif(filei=chjcoutHCj。outstufcoutendl此处编码出现错误，含有不可编码的字符！endl。break。cout。system(cls。voidinputEnco(/通过手动输入的方式进行编码system(cls

18、。cout请输入您要编码的文章以$作为文章结尾)malloc(200*sizeof(char。for(inti=1。icinfilei。if(filei=$break。if(i=200file=(char*realloc(file,(200+80*sizeof(char。for(。icinfilei。if(filei=$break。intm=i。cout编码结果是：。outstuf.open(CodeFile.txt,ios:out。for(i=1。ifor(intj=1。jif(filei=chjcoutHCj。outstufcoutendl此处编码出现错误，含有不可编码的字符！endl。b

19、reak。cout。system(cls。voiddecode(/选择译码方式system(cls。intsel=0。for(。endl。break。cout对不起，哈夫曼树不存在！请先建立哈夫曼树。endlcoutt*coutt*要译码的文件来源ttttt*endl。coutt*t1.使用已有文件CodeFile.txt进行译码tt*endl。coutt*t2.自行输入文件进行译码tttt*endl。coutt*t3.返回上层ttttt*endl。coutt*1endlcout请输入您的选择endlcout请输入您的选择endlsel。if(sel=3break。switch(selcase

20、1:openfileDeco(。break。case2:inputDeco(。break。default:cout。voidinputDeco(/通过手动输入的方式进行译码system(cls。intm=2*n-1。malloc(200*sizeof(char。cout请输入要译码的文件(以$结束)endl。for(inti=1。icinpasswordi。if(i=200password=(char*realloc(password,(200+80*sizeof(char。for(。icinpasswordi。cout译码结果为#代表空格)。outstuf.open(TextFile.txt

21、,ios:out。for(i=1。passwordi!=$。charrecord20。for(intj=0,q=i。passwordq!=$。j+,q+if(passwordq=0recordj=0。m=HTm.lchild。elserecordj=1。m=HTm.rchild。if(HTm.rchild=0recordj+1=0。break。if(HTm.rchild!=0coutendl译码在此处出现错误！此处不可译码！endl。for(intp=1。pif(!strcmp(record,HCpoutstufchp。cout。m=2*n-1。cout。system(cls。voidopenfileDeco(/通过打开文件CodeFile.txt的方式进行译码system(cls。intm=2*n-1。break。coutCodeFile.txt文件内容如下：。if(!infilecerropenerror!。char*password=(char*malloc(200*sizeof(char。for(inti=1。infile.eof(=0&i!=200。i+infilepasswordi。cou