哈夫曼树与哈夫曼编码.doc

文档介绍：哈夫曼树与哈夫曼编码实验三:哈夫曼树与哈弗曼编码1、实验目的:(1)理解哈夫曼树的含义和性质。(2)掌握哈夫曼树的存储结构以及描述方法。(3)掌握哈夫曼树的生成方法。(4)掌握哈夫曼编码的一般方法,并理解其在数据通讯中的应用。2、实验内容:哈夫曼树与哈弗曼编码、:,缩短信息传输时间,降低传输成本。但是,这要求在发送端通过一个编码系统对待传数据预先编码,在接收端将传来的数据进行译码。:-、。3、实验要求:建立哈夫曼树,实现编码,译码。(Initialization)。从终端读入字符集大小n,以及n个字符和n个权值,建?立哈夫曼树,并将它存于文件hfmTree中。(Encoding)。利用已建好的哈夫曼树(如不在内存,则从文件hfmTree中读?入),对文件ToBeTran中的正文进行编码,然后将结果存入文件CodeFile中。(Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码,结?果存入文件TextFile中。(Print)。将文件CodeFile以紧凑格式显示在终端上,每行50个代?码。同时将此字符形式的编码文件写入文件CodePrint中。(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入?表形式)显示在终端上,同时将此字符形式的哈夫曼树写入文件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:10,7:1110,8:111114:110,23:01,3:0000,11:0014、实验程序:#include<>#include<>#include<>1#defineN100//赫夫曼树和赫夫曼编码的存储表示typedefstruct{charch;unsignedintweight;unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;intmin(HuffmanTree&HT,inti){//函数voidselect()调用intj,flag;intk=65535;for(j=1;j<=i;j++)if(HT[j].weight<k&&HT[j].parent==0)k=HT[j].weight,flag=j;HT[flag].parent=1;returnflag;}voidSelect(HuffmanTree&HT,inti,int&s1,int&s2){s1=min(HT,i);s2=min(HT,i);}//构造赫夫曼树HT,并求出n个字符的赫夫曼编码HCvoidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,char*cha,intn){charc;intf,i,start,m,s1,s2;HTNode*p;