哈夫曼实验报告(附代码).doc

哈弗曼编码/译码器一、程序的功能分析1构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、n个字符以及n个对应的权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存。2编码：利用已构造的哈夫曼编码对“明文”文件中的正文进行编码，然后将结果存入“密文”文件中。3译码：将“密文”文件中的0、1代码序列进行译码。(读文件)4打印“密文”文件：将文件以紧凑格式显示在终端上，每行30个代码；同时，将此字符形式的编码文件保存。5打印哈夫曼树及哈夫曼编码：将已在内存中的哈夫曼树以凹入表形式显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。二、基本要求分析1、输入输出的要求按提示内容从键盘输入命令，系统根据用户输入的需求在保证界面友好的前提下输出用户所需信息，并按要求保存文件，以便保存备份信息。2、测试数据（1）令叶子结点个数N为4，权值集合为1,3,5,7，字符集合为A,B,C,D，且字符集与权值集合一一对应。（2）令叶子结点个数N为7，权值集合为12,6,8,18,3,20,2，字符集合为A,B,C,D,E,F,G，且字符集与权值集合一一对应。（3）请自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。三、概要设计1.主模块的流程及各子模块的主要功能主函数负责提供选项功能，循环调控整个系统。创建模块实现接收字符、权值、构建哈夫曼树，并保存文件，此功能是后续功能的基础。编码模块实现利用已编好的哈夫曼树对每个字符进行哈夫曼编码，即对每个字符译出其密文代码，并保存文件。译码模块实现对用户输入的密文翻译成明文，即用户所需的字符串信息。输出模块实现对已编好的哈夫曼树以凹入表的的形式输出。2、模块之间的层次关系主函数初始化编码译码打印结束递归遍历四、详细设计1.采用c语言定义的相关数据类型（1）结点的类型定义描述如下：#define N 叶子结点的个数typedef strcutint weight; /*结点权值*/int parent;int lchild;int rchild;HNodeType;HNodeType HNode2*N-1;（2）编码的类型定义描述如下：#define MAXBIT 10typedef structint bitMAXBIT;int start;HCodeType;HCodeType HCodeN; 2.各模块伪算法 （1）主函数 int main()do:界面友好设计;coutch;容错处理;switch(ch)case 1:.while();return 0; （2）系统初始化模块 void create() /系统初始化for(i=0;i2*N-1;i+) /数组HNode初始化;从键盘接收字符;for(i=0;iN;i+)cout输入字符HNodei.data; 接收权值;构造哈夫曼树;for(i=0;iN-1;i+)找最小和次小两个权值；将找出的两棵子树合并为一棵子数；将已建好的哈夫曼树存入文件hfmtree.txt中; 调用哈夫曼编码子函数； void HaffmanCode() /对哈夫曼树进行编码从hfmtree.txt文件中读出哈夫曼树的信息存入内存HNodeType a2*N-1；求每个叶子结点的哈夫曼编码；for(i=0;is;/从文件中读取哈夫曼编码信息infile.open (F:codefile.dat,ios:in|ios:binary); /读文件for(i=0;iN;i+) /将文件中的数据读出放在tempi内/从文件中读字节到指定的存储器区域。 infile.read (char*)&tempi,sizeof(tempi);循环实现将用户输入的字符串转换成对应的密文，并保存；将保存结果存入密文文件；void translate()/译码从文件hfmtree.txt中读出哈夫曼信息到内存temp2*N-1； 从密文文件中读取用户输入的字符串的密文信息到内存c； 追溯结点位置初始定位到根结点temp2*N-2；for(i=0;ic.num;i+) if(c.codei=0)在当前结点的左子树下追溯叶子结点；找到叶子结点则输出字符，当前结点重新定位到根结点；else在当前结点的右子树下追溯叶子结点;找到叶子结点则输出字符，当前结点重新定位到根结点；输出并保存明文；（4）译码模块 （5）输出模块void print() /将哈夫曼树以凹入表的形式输出从文件hfmtree.tet中读出哈夫曼树信息存入内存temp2*N-1；定义h=1;调用递归输出函数print_t(temp,temp2*N-2,h);void print_t(HNodeType temp,HNodeType T,int h)/叶子结点输出字符，分支结点输出权值if(T.data!=0) coutT.dataendl;elsecoutT.weightendl;递归调用左子树；递归调用右子树； 五、调试分析1.调试过程中遇到的问题和对问题的解决方法 对文件的读写操作不熟悉，调试时，将已写入的文件不能读出，以至于后续操作无法实现，对此，我有翻看C+程序设计课本，了解关于文件操作的具体内容，明白二进制文件和文本文件的读写方式是有很大区别的，不可混淆操作。另外，对于程序的输出阶段开始时出现了问题，递归调用没有分析清楚，递归思想是层次分明，逐层深入。2.算法的时间复杂度 （1）创建模块 O（N3） （2）编码模块 O（N） （3）译码模块 O（n） 其中n为用户输入的密文位数 （4）打印模块 O（N）六、使用说明及测试结果用户根据提示信息，初次使用本系统时要首先选择创建选项来初始化系统，根据提示信息输入信息，存入文件，使得后续功能顺利实现。非初次使用时，用户可根据自己的需求来选择功能选项，根据提示信息输入、获得所需信息。测试：1. 令叶子结点个数N为4，权值集合为1,3,5,7，字符集合为A,B,C,D，且字符集与权值集合一一对应。2令叶子结点个数N为7，权值集合为12,6,8,18,3,20,2，字符集合为A,B,C,D,E,F,G，且字符集与权值集合一一对应。3自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。字符串：whilwitchhiwwppppp 频率统计为whilctp43311154.可实现多个编码文件共存以及容错处理七、程序代码#include#include#include#include#define N 7 /叶子结点的个数#define MAXBIT 50 /编码位数#define Maxvalue 100 /定义最大权值整数常量/结点的类型定义描述如下：typedef structchar data;int weight; /*结点权值*/int parent;int lchild;int rchild;HNodeType;HNodeType HNode2*N-1;/编码类型描述如下：typedef structint bitMAXBIT;int start;char s; HCodeType;HCodeType HCodeN;/密文格式类型typedef structint codeMAXBIT;int num;CD;void create();void HaffmanCode();void print();void print_t(HNodeType temp,HNodeType T,int h);void translate();void HfmanCode();char name5030;/用来记录用户输入的密文文件int filenum=0;int textnum=0;int main()char ch;int h=1;HNodeType *pNode;pNode=HNode;do coutsetw(60) endl;coutsetw(60)- 欢迎进入系统！-endl;coutsetw(50)1:初始化编译系统endlsetw(40)2:编码endlsetw(40)3:译码endlsetw(48)4:打印哈弗曼树endlsetw(40)5:退出endl; coutsetw(60)-endl;coutch;while(!(ch=0) /*输入不在0到5之间无效*/coutch; switch(ch) case 1: create(); break; /系统初始化，构造哈夫曼树 case 2: HfmanCode(); break; /对哈夫曼树进行编码 case 3: translate(); break; /译码 case 4: print(); /将哈夫曼树以凹入表的形式输出 case 5: break; while(ch!=5);return 0;void create() /模块一，系统初始化fstream outfile;int i,j;int m1,m2,x1,x2;for(i=0;i2*N-1;i+) /数组HNode初始化HNodei.data=0;HNodei.weight=0;HNodei.parent=-1;HNodei.lchild=-1;HNodei.rchild=-1;cout分别输入N个叶子结点的字符。endl; /从键盘接收叶子节点的权值for(i=0;iN;i+)cout输入字符HNodei.data;cout分别输入N个与字符对应的权值。endl; /从键盘接收叶子节点的权值for(i=0;iN;i+)cout输入权值HNodei.weight;for(i=0;iN-1;i+) /构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;jN+i;j+) /找最小和次小两个权值if(HNodej.parent=-1&HNodej.weightm1)m2=m1;x2=x1;m1=HNodej.weight;x1=j;elseif(HNodej.parent=-1&HNodej.weightm2)m2=HNodej.weight;x2=j;/将找出的两棵子树合并为一棵子数HNodex1.parent=N+i;HNodex2.parent=N+i;HNodeN+i.weight=HNodex1.weight+HNodex2.weight;HNodeN+i.lchild=x1;HNodeN+i.rchild=x2;outfile.open(F:hfmtree.txt,ios:out|ios:binary);/建立进行写入的文件if(!outfile) /没有创建成功则显示相应信息couthfmtree.txt文件不能打开endl; return; /将内存中从HNode i地址开始的sizeof(HNode i)的内容写入文件中for(i=0;i2*N-1;i+)outfile.write(char*)&HNodei,sizeof(HNodei);cout哈夫曼树信息已存入文件hfmtree.tet中.endl; outfile.close ();/关闭文件HaffmanCode();/调用函数对哈夫曼树进行编码void HaffmanCode() /对哈夫曼树进行编码fstream outfile,infile;int i,j,c,p;HCodeType cd;HNodeType a2*N-1;infile.open (F:hfmtree.txt,ios:in|ios:binary);if(!infile) couthfmtree.dat文件不能打开endl; return;else for(i=0;i2*N-1;i+) /将文件中的数据读出放在ai内/从文件中读字节到指定的存储器区域。 infile.read (char*)&ai,sizeof(ai); infile.close();/求每个叶子结点的哈夫曼编码for(i=0;iN;i+)cd.start=N-1;c=i;p=ac.parent;while(p!=-1)if(ap.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=ac.parent;cout字符对应密文：endl; /打印出每个字符对应的密文coutai.data-;for(j=cd.start+1;jN;j+)/保存求出的每个叶节点的哈夫曼编码和编码的起始位HCodei.bitj=cd.bitj;coutcd.bitj;coutendl;HCodei.start=cd.start;HCodei.s=ai.data;outfile.open(F:codefile.dat,ios:out|ios:binary);/建立进行写入的文件if(!outfile) /没有创建成功则显示相应信息coutcodefile.dat文件不能打开endl;return; /将内存中从HCode i地址开始的sizeof(HCode i)的内容写入文件中for(i=0;iN;i+)outfile.write(char*)&HCodei,sizeof(HCodei); outfile.close ();/关闭文件n cout密文信息已存入文件codefile.dat中.endl;void print() /将哈夫曼树以凹入表的形式输出int i,h=1;HNodeType temp2*N-1;fstream infile;infile.open (F:hfmtree.txt,ios:in|ios:binary);if(!infile) couthfmtree.txt文件不能打开endl; return;else for(i=0;i2*N-1;i+) /将文件中的数据读出放在tempi内/从文件中读字节到指定的存储器区域。 infile.read (char*)&tempi,sizeof(tempi); infile.close();print_t(temp,temp2*N-2,h);void print_t(HNodeType temp,HNodeType T,int h)int i;for(i=1;ih;i+)cout ;if(T.data!=0) coutT.dataendl;elsecoutT.weightendl;if(T.lchild=-1)return;print_t(temp,tempT.lchild,h+1); /递归遍历左子树print_t(temp,tempT.rchild,h+1); /递归遍历右子树void HfmanCode() /对用户输入的字符串进行编码 char s50=0;int i,j,k,n=0,m;CD c;c.num=0;fstream infile,outfile;HCodeType tempN;cout输入字符串s;m=strlen(s);infile.open (F:codefile.dat,ios:in|ios:binary); /读文件if(!infile) coutcodefile.dat文件不能打开endl; return;else for(i=0;iN;i+) /将文件中的数据读出放在tempi内/从文件中读字节到指定的存储器区域。 infile.read (char*)&tempi,sizeof(tempi); infile.close();cout输入要将密文存放的文件名namefilenum;filenum+;for(i=0;im;i+)for(j=0;jN;j+)if(si=tempj.s)for(k=tempj.start+1;kN;k+)couttempj.bitk; /输出c.codec.num=tempj.bitk;/将字符对应密文存入c中c.num+;/记录密文长度n+;if(n=30) /实现每行输出30个密文coutendl;n=0;coutendl;outfile.open(namefilenum-1,ios:out|ios:binary);/建立进行写入的文件if(!outfile) /没有创建成功则显示相应信息coutnamefilenum-1.dat文件不能打开endl;return; /将内存中从c内容写入文件中elseoutfile.write(char*)&c,sizeof(c); outfile.close ();/关闭文件n cout密文信息已存入文件namefilenum-1.dat中.endl;void translate()/译码CD c;HNodeType temp2*N-1,q;fstream infile,outfile;char ch,r50=0,tempname30=0;int n=0,t=0,i;cout输入要译码的文件tempname;for(i=0;ifilenum;i+)if(strcmp(tempname,namei)=0)break;if(i=filenum)cout密文文件中没有tempname文件endl;return;infile.open (namei,ios:in|ios:binary);if(!infile) cout密文文件不能打开endl; return;else /从文件中读字节到指定的存储器区域。 infile.read (char*)&c,sizeof(c); infi