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

哈弗曼编码/译码器一、程序的功能分析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）结点的类型定义描述如下：#defineN叶子结点的个数typedefstrcut{intweight;/*结点权值*/intparent;intlchild;intrchild;}HNodeType;HNodeTypeHNode[2*N-1];（2）编码的类型定义描述如下：#defineMAXBIT10typedefstruct{intbit[MAXBIT];intstart;}HCodeType;HCodeTypeHCode[N];2.各模块伪算法（1）主函数intmain(){do:{界面友好设计;cout各个选项功能内容;cinch;容错处理;switch(ch){case1:.....}}while();return0;}（2）系统初始化模块voidcreate()//系统初始化{for(i=0;i2*N-1;i++)//数组HNode初始化{};从键盘接收字符;for(i=0;iN;i++){cout输入字符endl;cinHNode[i].data;}接收权值;构造哈夫曼树;for(i=0;iN-1;i++){找最小和次小两个权值；将找出的两棵子树合并为一棵子数；}将已建好的哈夫曼树存入文件hfmtree.txt中;调用哈夫曼编码子函数；}voidHaffmanCode()//对哈夫曼树进行编码{从hfmtree.txt文件中读出哈夫曼树的信息存入内存HNodeTypea[2*N-1]；求每个叶子结点的哈夫曼编码；for(i=0;iN;i++){从叶节点回溯，回溯到根结点（parent==-1）;记录回溯路径；}打印出每个字符对应的密文；将密文信息存入文件codefile.dat中；}（3）编码模块voidHfmanCode()//对用户输入的字符串进行编码{提示输入信息；接收用户输入的要编译的字符串；cins;//从文件中读取哈夫曼编码信息infile.open(F:\\codefile.dat,ios::in|ios::binary);//读文件for(i=0;iN;i++)//将文件中的数据读出放在temp[i]内//从文件中读字节到指定的存储器区域。infile.read((char*)&temp[i],sizeof(temp[i]));循环实现将用户输入的字符串转换成对应的密文，并保存；将保存结果存入密文文件；}（4）译码模块（5）输出模块voidtranslate()//译码{从文件hfmtree.txt中读出哈夫曼信息到内存temp[2*N-1]；从密文文件中读取用户输入的字符串的密文信息到内存c；追溯结点位置初始定位到根结点temp[2*N-2]；for(i=0;ic.num;i++){if(c.code[i]==0){在当前结点的左子树下追溯叶子结点；找到叶子结点则输出字符，当前结点重新定位到根结点；}else{在当前结点的右子树下追溯叶子结点;找到叶子结点则输出字符，当前结点重新定位到根结点；}}输出并保存明文；}五、调试分析1.调试过程中遇到的问题和对问题的解决方法对文件的读写操作不熟悉，调试时，将已写入的文件不能读出，以至于后续操作无法实现，对此，我有翻看C++程序设计课本，了解关于文件操作的具体内容，明白二进制文件和文本文件的读写方式是有很大区别的，不可混淆操作。另外，对于程序的输出阶段开始时出现了问题，递归调用没有分析清楚，递归思想是层次分明，逐层深入。2.算法的时间复杂度（1）创建模块O（N^3）（2）编码模块O（N）（3）译码模块O（n）其中n为用户输入的密文位数（4）打印模块O（N）六、使用说明及测试结果用户根据提示信息，初次使用本系统时要首先选择创建选项来初始化系统，根据提示信息输入信息，存入文件，使得后续功能顺利实现。非初次使用时，用户可根据自己的需求来选择功能选项，根据提示信息输入、获得所需信息。测试：1.令叶子结点个数N为4，权值集合为{1,3,5,7}，字符集合为{A,B,C,D}，且字符集与权值集合一一对应。voidprint()//将哈夫曼树以凹入表的形式输出{从文件hfmtree.tet中读出哈夫曼树信息存入内存temp[2*N-1]；定义h=1;调用递归输出函数print_t(temp,temp[2*N-2],h);}voidprint_t(HNodeTypetemp[],HNodeTypeT,inth){//叶子结点输出字符，分支结点输出权值if(T.data!='\0')coutT.dataendl;elsecoutT.weightendl;递归调用左子树；递归调用右子树；}2．令叶子结点个数N为7，权值集合为{12,6,8,18,3,20,2}，字符集合为{A,B,C,D,E,F,G}，且字符集与权值集合一一对应。3．自行选定一段英文文本，统计给出的字符集，实际统计字符的频度，建立哈夫曼树，构造哈夫曼编码，并实现其编码和译码。字符串：whilwitchhiwwppppp频率统计为whilctp43311154.可实现多个编码文件共存以及容错处理七、程序代码#includeiostream.h#includeiomanip.h#includefstream.h#includestring.h#defineN7//叶子结点的个数#defineMAXBIT50//编码位数#defineMaxvalue100//定义最大权值整数常量//结点的类型定义描述如下：typedefstruct{chardata;intweight;/*结点权值*/intparent;intlchild;intrchild;}HNodeType;HNodeTypeHNode[2*N-1];//编码类型描述如下：typedefstruct{intbit[MAXBIT];intstart;chars;}HCodeType;HCodeTypeHCode[N];//密文格式类型typedefstruct{intcode[MAXBIT];intnum;}CD;voidcreate();voidHaffmanCode();voidprint();voidprint_t(HNodeTypetemp[],HNodeTypeT,inth);voidtranslate();voidHfmanCode();charname[50][30];//用来记录用户输入的密文文件intfilenum=0;inttextnum=0;intmain(){charch;inth=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;cout请选择（0~5）：;cinch;while(!(ch='5'&&ch='0'))/*输入不在0到5之间无效*/{cout数据输入错误，请重新选择（0~7）：;cinch;}switch(ch){case'1':create();break;//系统初始化，构造哈夫曼树case'2':HfmanCode();break;//对哈夫曼树进行编码case'3':translate();break;//译码case'4':print();//将哈夫曼树以凹入表的形式输出case'5':break;}}while(ch!='5');return0;}voidcreate()//模块一，系统初始化{fstreamoutfile;inti,j;intm1,m2,x1,x2;for(i=0;i2*N-1;i++)//数组HNode初始化{HNode[i].data='\0';HNode[i].weight=0;HNode[i].parent=-1;HNode[i].lchild=-1;HNode[i].rchild=-1;}cout分别输入N个叶子结点的字符。endl;//从键盘接收叶子节点的权值for(i=0;iN;i++){cout输入字符endl;cinHNode[i].data;}cout分别输入N个与字符对应的权值。endl;//从键盘接收叶子节点的权值for(i=0;iN;i++){cout输入权值endl;cinHNode[i].weight;}for(i=0;iN-1;i++)//构造哈夫曼树{m1=m2=Maxvalue;x1=x2=0;for(j=0;jN+i;j++)//找最小和次小两个权值{if(HNode[j].parent==-1&&HNode[j].weightm1){m2=m1;x2=x1;m1=HNode[j].weight;x1=j;}elseif(HNode[j].parent==-1&&HNode[j].weightm2){m2=HNode[j].weight;x2=j;}}//将找出的两棵子树合并为一棵子数HNode[x1].parent=N+i;HNode[x2].parent=N+i;HNode[N+i].weight=HNode[x1].weight+HNode[x2].weight;HNode[N+i].lchild=x1;HNode[N+i].rchild=x2;}outfile.open(F:\\hfmtree.txt,ios::out|ios::binary);//建立进行写入的文件if(!outfile)//没有创建成功则显示相应信息{couthfmtree.tx