《哈夫曼编译码器》实验报告

哈夫曼编/译码器作者：田正英联系方式：15857162676目录一、实验目的二、实验内容三、语言四、环境五、功能设计概述六、详细设计七、测试结果八、收获与心得九、程序代码哈夫曼编/译码器一、实验目的1.熟练掌握哈夫曼编译原理2.掌握程序设计步骤二、实验内容根据哈夫曼编码原理，设计一个程序，在已知相关字符和字符对应权值（文件中存在或者用户输入）的情况下，根据用户要求对相应内容进行编码、译码等相应操作。三、语言C语言四、编译环境MicrosoftVisualC++五、功能设计概述1.从标准输入端输入相关的字符和权值2.根据相关字符和权值构造哈夫曼树，并将该树的相关信息写入指定文件3.若编译码前未对哈夫曼树进行初始化，则默认为指定文件中已纯在该哈夫曼树，并将其读入到内存（因此未初始化前一定要确定指定文件中存在哈夫曼树，否则会将空树读入内存）4.将编码结果写入指定文件5.将指定文件中编码内容进行哈夫曼译码6.标准端输出已保存到相关文件中的信息（哈夫曼树存储内容、代码、译码后内容）7.输出哈夫曼树直观图并保存到指定文件8.用户选择界面六、详细设计1.哈夫曼树结构体：typedefstructHtnode{intlchild,rchild,parent;floatweight;chardata;}Htnode;分别存储该节点左右孩子、双亲节点、该节点权值、以及该节点对应字符。分别存储相应字符对应代码以及代码开始位置。此处size宏定义为128。2.输入——Input用户根据相关提示输入需要字符和权值（输入‘#’结束）。函数中两处用到getchar()函数，第一处是为吸收从调用方可能引进的回车，第二处是为吸收每次输入完成后的回车。第一处可视情况添加（为保证健壮性，最好添加），第二处必须添加。3.初始化相关函数——CreatHt、CreatHcode、InitializationtypedefstructHcode{charcd[size];intstart;}Hcode;getchar();printf(请输入初始化字符和权值，输入'#'结束\n);do//输入字符及权值{(*n)++;scanf(%c,&t[*n].data);//注意空格也要算字符，也要输入权值if(t[*n].data!='#')scanf(%f,&t[*n].weight);getchar();}while(t[*n].data!='#');for(intj=n;j2*n-1;j++){floatmin1=32000;floatmin2=32000;intnode1=-1;intnode2=-1;for(intk=0;kj;k++){if(b[k].parent==-1){if(b[k].weightmin1){min2=min1;node2=node1;min1=b[k].weight;node1=k;}以上为CreatHt函数部分代码。找出叶子节点中（0~n-1）最小的一个和第二小的一个节点，由这两个节点生成双亲节点（n~2*n-1），双亲节点伪权值为该两节点权值（或伪权值）之和。重复以上操作直到所有节点（2*n-1个）都确定了父子关系。以上为CreatHcode函数部分代码。从叶子节点（存储字符的节点）倒序找双亲节点，判断是双亲左孩子还是右孩子，若是左孩子则在字符代码数组最后一位填0（start标记前移一位），若是右孩子则在字符代码数组最后一位填1（start标记前移一位）。重复以上操作直到找到根结点。elseif(b[k].weightmin2){min2=b[k].weight;node2=k;}}}b[j].lchild=node1;b[j].rchild=node2;b[node1].parent=b[node2].parent=j;b[j].weight=min1+min2;}Hcodech;for(inti=0;in;i++){ch.start=n;intf=b[i].parent;intc=i;while(f!=-1){if(b[f].rchild==c){ch.cd[ch.start--]='1';}elsech.cd[ch.start--]='0';c=f;f=b[f].parent;}ch.start++;cd[i]=ch;}注意start标记的处理，此处一错满盘皆输，而且难发现错误原因。以上是Initialization函数部分代码。将所有节点信息及节点间对应关系保存到指定文件。下次编译时则无需以上繁琐的初始化过程，只需从文件中读取即可。4.编码——Encoding以上为Encoding函数部分代码。将源文件字符读到自定义缓冲区str中，将str中每个字符在初始化字符中查找，若找到则将该字符对应代码写到code中。其中j起到计数的作用，记录源文件字符个数。5.译码——DecodingFILE*fp=fopen(op,wb+);for(inti=0;i2*n-1;i++){if(in)fprintf(fp,%c\t,t[i].data);elsefprintf(fp,#\t,t[i].data);fprintf(fp,%.2f\t,t[i].weight);fprintf(fp,%d\t,t[i].parent);fprintf(fp,%d\t,t[i].lchild);fprintf(fp,%d,t[i].rchild);fprintf(fp,\r\n);}intj=0;while(!feof(bb)){str[j]=fgetc(bb);j++;}intrt=0;for(inti=0;ij;i++)//对str中每个字符进行编译{for(intk=0;kn;k++)//在原码中查找该字符{if(p[k].data==str[i]){for(inta=d[k].start;a=n;a++){code[rt++]=d[k].cd[a];}}}}intcs=0;ip=0;flag1=1;while(ip!=len)以上为Decoding函数部分代码。将初始化字符中每一个字符代码和要编译内容相应位置代码进行比对，若找到符合的，则相对应字符写入字符数组str中。其中ip起计数作用，记录共编译的代码长度。ip=ip+i-d[j].start;将每个已找到字符代码长度累加，ip=len时译码完成。6.文件中哈夫曼树读入到内存——ReadHtFile将指定文件中的哈夫曼树写入到内存，fgetc(fp)是为读取每个数据之间制表符或者回车符，此处要格外小心，极易出错，稍偏差一位后面就全部错位。此处是以文本文件方式读取(若以二进制方式读取应注意回车符处理)。注意：若用二进制方式读文件则行末需读两个字符{flag1=1;for(intj=0;jn&&flag1;j++)//遍历每一个字符，直到找到为止{intflag2=1;inti=d[j].start;for(;i=n&&flag2;i++){if(d[j].cd[i]!=cod[ip+i-d[j].start])flag2=0;}if(flag2==1){ip=ip+i-d[j].start;str[cs++]=p[j].data;flag1=0;}}}*n=0;while(!feof(fp)){fscanf(fp,%c,&t[i].data);if(t[i].data!='#')(*n)++;fgetc(fp);fscanf(fp,%f,&t[i].weight);fgetc(fp);fscanf(fp,%d,&t[i].parent);fgetc(fp);fscanf(fp,%d,&t[i].lchild);fgetc(fp);fscanf(fp,%d,&t[i].rchild);fgetc(fp);i++;}(*n)--;7.标准端输出——Output、OutputHt、OutputCode、OutputFile、OutputT以上为Output函数部分代码。将哈夫曼树直观图（凹入式）输出到标准端，第一个for循环输出叶子节点，第二个for循环输出非叶子节点。叶子节点直接根据代码长度输出，该叶子节点深度等于代码长度加1，而非叶子节点则需逆向找双亲（与叶子节点求代码过程类似），直到找到根结点，将到根结点经过的边数加1即其深度。for(inti=0;in;i++){intlen=n-cod[i].start+1;inth=len+1;printf(%c,at[i].data);printf(%.2f\t,at[i].weight);for(intj=0;jh;j++){printf(▄);}printf(\n);}for(intk=n;k2*n-1;k++){intlen=0;intf=k;while(at[f].parent!=-1){len++;f=at[f].parent;}inth=len+1;printf(%c,at[k].data);printf(%.2f\t,at[k].weight);for(intj=0;jh;j++){printf(▄);}printf(\n);}fgets(str,maxsize-1,pp);while(!feof(pp)){printf(%s,str);fgets(str,maxsize-1,pp);}以上为OutputHt函数的部分代码。将哈夫曼树存储内容输出到标准端（字符、双亲、孩子、权值）。以上为OutputCode函数部分代码。将编码后的代码内容输出到标准端。以上为OutputFile函数部分代码。将译码后的内容输出到标准端。fgets(str,maxsize-1,cdd);while(!feof(cdd)){printf(%s,str);fgets(str,maxsize-1,cdd);}fgets(str,maxsize-1,ott);while(!feof(ott)){fgets(str,maxsize-1,ott);printf(%s,str);}for(inti=0;in;i++)//输入叶子节点{intlen=n-cod[i].start+1;inth=len+1;fprintf(ote,%c,at[i].data);fprintf(ote,%.2f\t,at[i].weight);for(intj=0;jh;j++){fprintf(ote,▄);}fprintf(ote,\n);}for(intk=n;k2*n-1;k++)//输入非叶子节点{intlen=0，f=k;while(at[f].parent!=-1){len++;f=at[f].parent;}inth=len+1;fprintf(ote,%c,at[k].data);fprintf(ote,%.2f\t,at[k].weight);for(intj=0;jh;j++){fprintf(ote,▄);}fprintf(ote,\n);}以上为OutputT函数部分代码。将哈夫曼树直观图（凹入式）输出到指定文件。此函数与Output函数相似，此处不再讲述。8.用户选择界面——mainswitch(flag){case'1'://初始化并保存printf(初始化将会删除原文件中的哈夫曼树，确认初始化吗？是（1）否（2）：);scanf(%d,&yn);switch(yn){getchar();case1://确认初始化Input(op,t,co,&nn);CreatHt(t,nn);//构造哈夫曼树CreatHcode(t,co,nn);Initialization(t,op,nn);//将哈夫曼树写入到指定文件tag=1;break;case2:break;default:printf(选择有误\n);}break;case'2':if(!tag){ReadHtFile(op,t,co,&nn);CreatHt(t,nn);CreatHcode(t,co,nn);tag=1;}Encoding(be,cod,t,co,nn