《哈夫曼实验报告.doc》由会员分享，可在线阅读，更多相关《哈夫曼实验报告.doc（16页珍藏版）》请在三一文库上搜索。
1、哈弗曼编码 / 译码器一、程序的功能分析1构造哈夫曼树及哈夫曼编码：从终端读入字符集大小n、 n 个字符以及n 个对应的权值，建立哈夫曼树；利用已经建好的哈夫曼树求每个叶结点的哈夫曼编码，并保存。2编码： 利用已构造的哈夫曼编码对“明文”文件中的正文进行编码，然后将结果存入“密文”文件中。3译码 ：将“密文”文件中的0、 1 代码序列进行译码。( 读文件 )4打印“密文”文件：将文件以紧凑格式显示在终端上，每行30 个代码；同时，将此字符形式的编码文件保存。5打印哈夫曼树及哈夫曼编码：将已在内存中的哈夫曼树以凹入表形式显示在终端上，同时将每个字符的哈夫曼编码显示出来；并保存到文件。二、基本要求
2、分析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. 主模块的流程及各子模块的主要功能主函数
3、负责提供选项功能，循环调控整个系统。创建模块实现接收字符、权值、构建哈夫曼树，并保存文件，此功能是后续功能的基础。编码模块实现利用已编好的哈夫曼树对每个字符进行哈夫曼编码，即对每个字符译出其密文代码，并保存文件。译码模块实现对用户输入的密文翻译成明文，即用户所需的字符串信息。输出模块实现对已编好的哈夫曼树以凹入表的的形式输出。2、模块之间的层次关系主函数初始化编码译码打印结束递归遍历四、详细设计1. 采用 c 语言定义的相关数据类型（ 1）结点的类型定义描述如下：#define N 叶子结点的个数 typedef strcutint weight;int parent;int lchild;i
4、nt rchild;HNodeType;HNodeType HNode2*N-1;（ 2）编码的类型定义描述如下：#define MAXBIT 10typedef structint bitMAXBIT;int start;HCodeType;HCodeType HCodeN;2. 各模块伪算法（ 1）主函数int main()do:界面友好设计;cout<< 各个选项功能内容;cin>>ch;容错处理 ;switch(ch)case 1:.while();return 0;/* 结点权值 */（ 2）系统初始化模块void create()/系统初始化for(i=0;
5、i<2*N-1;i+)/数组 HNode初始化;从键盘接收字符;for(i=0;i<N;i+)cout<<" 输入字符 "<<endl; cin>>HNodei.data;接收权值 ;构造哈夫曼树 ;for(i=0;i<N-1;i+)找最小和次小两个权值；将找出的两棵子树合并为一棵子数；将已建好的哈夫曼树存入文件hfmtree.txt中 ;调用哈夫曼编码子函数；void HaffmanCode() /对哈夫曼树进行编码从 hfmtree.txt 文件中读出哈夫曼树的信息存入内存 HNodeType a2*N-1 ；求每个
6、叶子结点的哈夫曼编码；for(i=0;i<N;i+)从叶节点回溯，回溯到根结点（parent=-1）;记录回溯路径；打印出每个字符对应的密文；将密文信息存入文件codefile.dat中；（ 3）编码模块void HfmanCode() /对用户输入的字符串进行编码提示输入信息；接收用户输入的要编译的字符串；cin>>s;/ 从文件中读取哈夫曼编码信息infile.open ("F:codefile.dat",ios:in|ios:binary); /读文件for(i=0;i<N;i+) /将文件中的数据读出放在tempi内/ 从文件中读字节到指定的
7、存储器区域。infile.read (char*)&tempi,sizeof(tempi);循环实现将用户输入的字符串转换成对应的密文，并保存；将保存结果存入密文文件；（ 4）译码模块void translate()/译码从文件 hfmtree.txt 中读出哈夫曼信息到内存 temp2*N-1 从密文文件中读取用户输入的字符串的密文信息到内存追溯结点位置初始定位到根结点 temp2*N-2 ；c；for(i=0;i<c.num;i+)if(c.codei=0)在当前结点的左子树下追溯叶子结点；找到叶子结点则输出字符，当前结点重新定位到根结点；else在当前结点的右子树下追溯叶子
8、结点;找到叶子结点则输出字符，当前结点重新定位到根结点；输出并保存明文；（ 5）输出模块void print() /将哈夫曼树以凹入表的形式输出从文件 hfmtree.tet定义 h=1;调用递归输出函数中读出哈夫曼树信息存入内存 print_t(temp,temp2*N-2,h);temp2*N-1；void print_t(HNodeType temp,HNodeType T,int h)/ 叶子结点输出字符，分支结点输出权值if(T.data!='0')cout<<T.data<<endl;elsecout<<T.weight<&
9、lt;endl;递归调用左子树；递归调用右子树；五、调试分析1. 调试过程中遇到的问题和对问题的解决方法对文件的读写操作不熟悉，调试时，将已写入的文件不能读出，以至于后续操作无法实现，对此，我有翻看 C+程序设计课本，了解关于文件操作的具体内容，明白二进制文件和文本文件的读写方式是有很大区别的，不可混淆操作。另外，对于程序的输出阶段开始时出现了问题，递归调用没有分析清楚，递归思想是层次分明，逐层深入。2. 算法的时间复杂度（ 1）创建模块 O （ N3）（ 2）编码模块 O （ N）（ 3）译码模块 O （ n） 其中 n 为用户输入的密文位数（ 4）打印模块 O （ N）六、使用说明及测试结
10、果用户根据提示信息，初次使用本系统时要首先选择创建选项来初始化系统，根据提示信息输入信息，存入文件，使得后续功能顺利实现。非初次使用时，用户可根据自己的需求来选择功能选项，根据提示信息输入、获得所需信息。测试：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自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。字符串： whilwitch
11、hiwwppppp频率统计为whilctp43311154. 可实现多个编码文件共存以及容错处理七、程序代码#include<iostream.h>#include<iomanip.h>#include<fstream.h>#include<string.h>#defineN7 /叶子结点的个数#define MAXBIT 50 /编码位数#define Maxvalue 100 /定义最大权值整数常量/ 结点的类型定义描述如下：typedef structchar data;int weight;/*结点权值*/int parent;int l
12、child;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 Hfman
13、Code();char name5030;/用来记录用户输入的密文文件int filenum=0;int textnum=0;int main()char ch;int h=1;HNodeType *pNode;pNode=HNode;docout<<setw(60)<<""<<endl;cout<<setw(60)<<"-欢迎进入系统！-"<<endl;cout<<setw(50)<<"1:初始化编译系统"<<endl<
14、<setw(40)<<"2:编码 "<<endl<<setw(40)<<"3:译码 "<<endl<<setw(48)<<"4:打印哈弗曼树"<<endl<<setw(40)<<"5:退出 "<<endl;cout<<setw(60)<<"-"<<endl;cout<<"请选择（ 05）： "
15、cin>>ch;while(!(ch<='5'&&ch>='0') /*输入不在0 到 5 之间无效 */cout<<"数据输入错误，请重新选择（07）： "cin>>ch;switch(ch)case '1': create();break; /系统初始化，构造哈夫曼树case '2': HfmanCode();break; /对哈夫曼树进行编码case '3': translate();break;/译码case '4&
16、#39;: print(); /将哈夫曼树以凹入表的形式输出case '5': break;while(ch!='5');return 0;void create()/模块一，系统初始化fstream outfile;int i,j;int m1,m2,x1,x2;for(i=0;i<2*N-1;i+)/数组HNode初始化HNodei.data='0'HNodei.weight=0;HNodei.parent=-1;HNodei.lchild=-1;HNodei.rchild=-1;cout<<" 分别输入"
17、;<<N<<" 个叶子结点的字符。"<<endl;/从键盘接收叶子节点的权值for(i=0;i<N;i+)cout<<"输入字符"<<endl;cin>>HNodei.data;cout<<" 分别输入"<<N<<" 个与字符对应的权值。"<<endl;/从键盘接收叶子节点的权值for(i=0;i<N;i+)cout<<" 输入权值 "<<e
18、ndl;cin>>HNodei.weight;for(i=0;i<N-1;i+)/构造哈夫曼树m1=m2=Maxvalue;x1=x2=0;for(j=0;j<N+i;j+) /找最小和次小两个权值if(HNodej.parent=-1&&HNodej.weight<m1)m2=m1;x2=x1;m1=HNodej.weight;x1=j;elseif(HNodej.parent=-1&&HNodej.weight<m2)m2=HNodej.weight;x2=j;/ 将找出的两棵子树合并为一棵子数HNodex1.parent
19、=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) /没有创建成功则显示相应信息cout<<"hfmtree.txt文件不能打开"<<endl;return;/将内存中从HNode i地址开始的sizeof(HNode i)的内
20、容写入文件中for(i=0;i<2*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 ("
21、F:hfmtree.txt",ios:in|ios:binary);if(!infile)cout<<"hfmtree.dat文件不能打开 "<<endl;return;elsefor(i=0;i<2*N-1;i+) /将文件中的数据读出放在ai内/ 从文件中读字节到指定的存储器区域。infile.read (char*)&ai,sizeof(ai);infile.close();/ 求每个叶子结点的哈夫曼编码for(i=0;i<N;i+)cd.start=N-1;c=i;p=ac.parent;while(p!=-1)
22、if(ap.lchild=c)cd.bitcd.start=0;elsecd.bitcd.start=1;cd.start-;c=p;p=ac.parent;cout<<" 字符对应密文： "<<endl; / 打印出每个字符对应的密文 cout<<ai.data<<"-"for(j=cd.start+1;j<N;j+)/ 保存求出的每个叶节点的哈夫曼编码和编码的起始位HCodei.bitj=cd.bitj;cout<<cd.bitj;cout<<endl;HCodei.sta
23、rt=cd.start;HCodei.s=ai.data;outfile.open("F:codefile.dat",ios:out|ios:binary);/建立进行写入的文件if(!outfile) /没有创建成功则显示相应信息cout<<"codefile.dat文件不能打开 "<<endl;return;/将内存中从HCode i地址开始的sizeof(HCode i)的内容写入文件中for(i=0;i<N;i+)outfile.write(char*)&HCodei,sizeof(HCodei);outfi
24、le.close ();/关闭文件ncout<<"密文信息已存入文件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)cout<<"hfmtree.txt文件不能打开 "<<endl;return;elsefor(i=0;i<
25、2*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;i<h;i+)cout<<""if(T.data!='0')cout<<T.data<<endl;elsecout<<T.we
26、ight<<endl;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<<" 输入字符串 "<<endl;cin>>s;m=st
27、rlen(s);infile.open ("F:codefile.dat",ios:in|ios:binary); /if(!infile)读文件cout<<"codefile.dat文件不能打开"<<endl;return;elsefor(i=0;i<N;i+) /将文件中的数据读出放在tempi内/ 从文件中读字节到指定的存储器区域。infile.read (char*)&tempi,sizeof(tempi);infile.close();cout<<" 输入要将密文存放的文件名"
28、;<<endl;cin>>namefilenum;filenum+;for(i=0;i<m;i+)for(j=0;j<N;j+)if(si=tempj.s)for(k=tempj.start+1;k<N;k+)cout<<tempj.bitk; /输出c.codec.num=tempj.bitk;/将字符对应密文存入c 中c.num+;/记录密文长度n+;if(n=30) /实现每行输出30 个密文cout<<endl;n=0;cout<<endl;outfile.open(namefilenum-1,ios:out
29、|ios:binary);/建立进行写入的文件if(!outfile) /没有创建成功则显示相应信息cout<<namefilenum-1<<".dat文件不能打开 "<<endl;return;/ 将内存中从 c 内容写入文件中elseoutfile.write(char*)&c,sizeof(c);outfile.close ();/关闭文件ncout<<"密文信息已存入文件"<<namefilenum-1<<".dat中 ."<<endl
30、;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<<" 输入要译码的文件"<<endl;cin>>tempname;for(i=0;i<filenum;i+)if(strcmp(tempname,namei)=0)break;if(i=filenum)cout<<" 密文文件中没有"&
31、lt;<tempname<<"文件 "<<endl;return;infile.open (namei,ios:in|ios:binary);if(!infile)cout<<"密文文件不能打开"<<endl;return;else/ 从文件中读字节到指定的存储器区域。infile.read (char*)&c,sizeof(c);infile.close();infile.open ("F:hfmtree.txt",ios:in|ios:binary);if(!infil
32、e)cout<<"hfmtree.dat文件不能打开 "<<endl;return;elsefor( i=0;i<2*N-1;i+) /将文件中的数据读出放在tempi内/ 从文件中读字节到指定的存储器区域。infile.read (char*)&tempi,sizeof(tempi);infile.close();q=temp2*N-2; /将根结点信息赋给qcout<<" 对应的明文信息为： for(i=0;i<c.num;i+) "if(c.codei!=0&&c.codei!
33、=1) /容错处理t=0;break;if(c.codei=0)ch=tempq.lchild.data;if(ch!='0')/到叶子结点cout<<ch;rn+=ch;t=1;q=temp2*N-2;elseq=tempq.lchild;elsech=tempq.rchild.data;if(ch!='0')/到叶子结点cout<<ch;rn+=ch;t=1;q=temp2*N-2;elseq=tempq.rchild;cout<<endl;if(t=0)cout<<" 没有对应明文！"re
34、turn;outfile.open("F:TextFiletextnum.txt",ios:out|ios:binary);/建立进行写入的文件if(!outfile) /没有创建成功则显示相应信息cout<<"TextFiletextnum.txt文件不能打开"<<endl;return;/将内存中内容写入文件中for(i=0;i<n;i+)outfile.write(char*)&ri,sizeof(ri);outfile.close ();/关闭文件ntextnum+;cout<<"明文信息已存入文件TextFile"<<textnum<<".txt"<<endl;