哈夫曼树 实验报告

共页第页计算机科学与技术学院数据结构实验报告班级2014级计算机1班学号20144138021姓名张建华成绩实验项目简单哈夫曼编/译码的设计与实现实验日期2016.1.5一、实验目的本实验的目的是进一步理解哈夫曼树的逻辑结构和存储结构，进一步提高使用理论知识指导解决实际问题的能力。二、实验问题描述利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码，此实验即设计这样的一个简单编/码系统。系统应该具有如下的几个功能：1、接收原始数据。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmtree.dat中。2、编码。利用已建好的哈夫曼树（如不在内存，则从文件hfmtree.dat中读入），对文件中的正文进行编码，然后将结果存入文件codefile.dat中。3、译码。利用已建好的哈夫曼树将文件codefile.dat中的代码进行译码，结果存入文件textfile.dat中。4、打印编码规则。即字符与编码的一一对应关系。5、打印哈夫曼树，将已在内存中的哈夫曼树以直观的方式显示在终端上。三、实验步骤1、实验问题分析1、构造哈夫曼树时使用静态链表作为哈夫曼树的存储。在构造哈夫曼树时，设计一个结构体数组HuffNode保存哈夫曼树中各结点的信息，根据二叉树的性质可知，具有n个叶子结点的哈夫曼树共有2n-1个结点，所以数组HuffNode的大小设置为2n-1，描述结点的数据类型为：Typedefstrcut{Intweight；/*结点权值*/Intparent；Intlchild；Intrchild；}HNodeType；2、求哈夫曼编码时使用一维结构数组HuffCode作为哈夫曼编码信息的存储。求哈夫曼编码，实质上就是在已建立的哈夫曼树中，从叶子结点开始，沿结点的双亲链域回退到根结点，没回退一步，就走过了哈夫曼树的一个分支，从而得到一位哈夫曼码值，由于一个字符的哈夫曼编码是从根结点到相应叶子结点所经过的路径上各分支所组成的0、1序列，因此先得到的分支代码为所求编码的低位码，后得到的分支代码位所求编码的高位码，所以设计如下数据类型：#defineMAXBIT10共页第页Typedefstruct{Intbit[MAXBIT]；Intstart；}HCodeType；3、文件hfmtree.dat、codefile.dat和textfile.dat。2、功能（函数）设计（1）、初始化功能模块。此功能模块的功能为从键盘接收字符集大小n，以及n个字符和n个权值。（2）、建立哈夫曼树的功能模块。此模块功能为使用1中得到的数据按照教材中的构造哈夫曼树的算法构造哈夫曼树，即将HuffNode数组中的各个位置的各个域都添上相关的值，并将这个结构体数组存于文件hfmtree.dat中。（3）、建立哈夫曼编码的功能模块。此模块功能为从文件hfmtree.dat中读入相关的字符信息进行哈夫曼编码，然后将结果存入codefile.dat中，同时将字符与0、1代码串的一一对应关系打印到屏幕上。（4）、译码的功能模块。此模块功能为接收需要译码的0、1代码串，按照3中建立的编码规则将其翻译成字符集中字符所组成的字符串形式，存入文件textfile.dat，同时将翻译的结果在屏幕上打印输出。（5）、打印哈夫曼树的功能模块。此模块功能为从HuffNode数组中读入相关的结点信息，以图形的方式将各个结点以及叶子结点的权值和左分支上的0和右分支上的1画出来。四、实验结果（程序）及分析1、实验主要代码typedefstruct/*结点结构体*/{stringhfmstr;/*结点内容*/intweight;/*结点权值*/intparent;intlchild;intrchild;}HNodeType;typedefstruct/*编码结构体*/{intbit[MAXBIT];intstart;}HCodeType;voidCreate_HuffMTree(HNodeTypeHFMTree[],intn)/*创建哈夫曼树*/{intm1,x1,m2,x2;inti,j;for(i=0;i2*n-1;i++)共页第页{HFMTree[i].hfmstr=;HFMTree[i].weight=0;HFMTree[i].parent=-1;HFMTree[i].lchild=-1;HFMTree[i].rchild=-1;}for(i=0;in;i++){cout请输入第i+1个权值endl;cinHFMTree[i].weight;cout请输入对应字符endl;cinHFMTree[i].hfmstr;}for(i=0;in-1;i++){x1=x2=MAXVALUE;m1=m2=0;for(j=0;jn+i;j++){if(HFMTree[j].parent==-1&&HFMTree[j].weightx1){x2=x1;m2=m1;x1=HFMTree[j].weight;m1=j;}elseif(HFMTree[j].parent==-1&&HFMTree[j].weightx2){x2=HFMTree[j].weight;m2=j;}}HFMTree[m1].parent=n+i;HFMTree[m2].parent=n+i;HFMTree[n+i].weight=HFMTree[m1].weight+HFMTree[m2].weight;HFMTree[n+i].lchild=m1;HFMTree[n+i].rchild=m2;}cout创建哈夫曼树成功！endl;}voidHaffmanCode(HNodeTypeHFMTree[],HCodeTypeHuffCode[],intn)/*构建哈夫曼编码*/{HCodeTypecd;inti,j,c,p;for(i=0;in;i++)共页第页{cd.start=n-1;c=i;p=HFMTree[c].parent;while(p!=-1){if(HFMTree[p].lchild==c)cd.bit[cd.start]=0;elsecd.bit[cd.start]=1;cd.start--;c=p;p=HFMTree[c].parent;}for(j=cd.start+1;jn;j++)HuffCode[i].bit[j]=cd.bit[j];HuffCode[i].start=cd.start;}}voiddecodeing(charstring[],HNodeTypeHFMTree[],intn)/*解码*/{inti,tmp=0,code[1024];intm=2*n-1;char*nump;charnum[1024];for(i=0;istrlen(string);i++){if(string[i]=='0')num[i]=0;elsenum[i]=1;}i=0;nump=&num[0];while(nump(&num[strlen(string)])){tmp=m-1;while((HFMTree[tmp].lchild!=-1)&&(HFMTree[tmp].rchild!=-1)){if(*nump==0){tmp=HFMTree[tmp].lchild;}elsetmp=HFMTree[tmp].rchild;共页第页nump++;}coutHFMTree[tmp].hfmstr;}coutendl;}2、测试数据与输出