霍夫曼问题法.docx

问题解析与解题方法 问题分析： 设计一个哈夫曼编码、译码系统。对一个ASCII编码的文本文件中的字符进行哈夫曼编码，生成编码文件；反过来，可将编码文件译码还原为一个文本文件。（1） 从文件中读入任意一篇英文短文（文件为ASCII编码，扩展名为txt）；（2） 统计并输出不同字符在文章中出现的频率（空格、换行、标点等也按字符处理）；（3） 根据字符频率构造哈夫曼树，并给出每个字符的哈夫曼编码；（4） 将文本文件利用哈夫曼树进行编码，存储成压缩文件（编码文件后缀名.huf）（5） 用哈夫曼编码来存储文件，并和输入文本文件大小进行比较，计算文件压缩率；（6） 进行译码，将huf文件译码为ASCII编码的txt文件，与原txt文件进行比较。根据上述过程可以知道该编码译码器的关键在于字符统计和哈夫曼树的创建以及解码。哈夫曼树的理论创建过程如下：一、构成初始集合对给定的n个权值W1,W2,W3,.,Wi,.,Wn构成n棵二叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn，其中每棵二叉树Ti中只有一个权值为Wi的根结点，它的左右子树均为空。 二、选取左右子树在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。 三、删除左右子树从F中删除这两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。 四、重复二和三两步，重复二和三两步，直到集合F中只有一棵二叉树为止。 因此，有如下分析：1. 我们需要一个功能函数对ASCII码的初始化并需要一个数组来保存它们；2. 定义代表森林的数组，在创建哈夫曼树的过程当中保存被选中的字符，即给定报文中出现的字符,模拟哈夫曼树选取和删除左右子树的过程；3. 自底而上地创建哈夫曼树，保存根的地址和每个叶节点的地址，即字符的地址，然后自底而上检索，首尾对换调整为哈夫曼树实现哈弗曼编码；4. 从哈弗曼编码文件当中读入字符，根据当前字符为0或者1的状况访问左子树或者右孩子，实现解码；5. 使用文件读写操作哈夫曼编码和解码结果的写入； 解题方法： 结构体、数组、类的定义：1. 定义结构体类型的signode 作为哈夫曼树的节点，定义结构体类型的hufnode 作为哈夫曼编码对照表的节点，定义HFM类实现对哈夫曼树的创建，利用其成员函数完成哈夫曼编码译码的工作。2. 定义signode 类型的全局数组SN256（为方便调用，之后的forest256，hufNode256均为全局数组）, 保存ASCII编码的字符，是否在文章中出现（bool类型）以及出现次数（int类型，权重），左右孩子节点位置，父节点位置信息；3. 为节省存储空间，定义signode * 类型的全局数组forest256, 模拟森林，在创建哈夫曼树的过程中保存出现字符的指针，模拟哈夫曼树选取和删除左右子树的过程；4. 定义hufnode 类型的全局数组hufNode256，在编码时最为哈夫曼编码对照表的节点，char 型c保存字符,int code100保存其哈夫曼编码；5. 定义HFM类，主要保存哈夫曼树的根节点指针，但其丰富的功能函数将实现哈夫曼编码译码的工作及其他功能；函数介绍：1. void init(signode * sig) 初始化数组SN；2. void compress()输出压缩对比情况的信息;3. void exchange()用两层for循环实现hufNodei节点的成员哈夫曼编码数组code前后元素的对换，因为在之前的编码过程中由于是从叶节点追溯至根节点，存入code数组的哈夫曼编码与哈夫曼编码的概念反向，故而要调整；4. signode * getroot()返回哈夫曼树的根节点指针；5. signode * HFM:creat()创建哈夫曼树，首先用三个for循环查看forest数组，找到权值最小的两个字符，以int型的min1,min2记录其下标，定义signode * 类型指针pp指向新生成signode节点，用指针操作使pp指向的节点的权值为min1,min2权值之和，pp做孩子指向forestmin1,右孩子指向forestmin2，min1,min2的父指针指向pp，然后将pp存入min1的位置，min2之后的每一个节点依次往前移一个位置，实现从forest数组中清除min1,min2并加入pp的操作；6. void HFM:hufcode()哈夫曼编码，用for循环控制查看hufNode 数组，其初始化已在creat（）的开始完成，对每一个字符实现编码，用while循环从叶节点开始，如果该节点是其父节点的左孩子就将codehufNodei.size+赋值0，否则赋为1，直至当前节点的父节点为空，while循环结束；7. void HFM:savewithhufcode(FILE * inf,FILE * outf)将读入的文章以哈夫曼编码的形式存储，其中inf为读入文件的指针，outf为写入文件的指针,首先调用rewind(inf)函数将光标放置在文章开头，防止文件未关闭导致的错误，每读一个字符就用for循环在hufNode 数组中查找，因为hufNode 数组就是保存出现的字符的，故一定可以找到，然后再用fputc函数将code数组的内容写入文件，直至读入文件结束；8. void HFM:inorder(signode * sig)迭代法遍历树，遍历到叶节点时执行hufNodecount+.sig=sig语句实现hufNode 数组指向文章中出现的字符；9. int HFM:maxc() 计数变量，记录哈夫曼编码最大位数；10. void HFM:hufdecode(FILE* ipf,FILE* opf)解码，从哈夫曼编码到字符，输出到屏幕和指定的文件中；11. void input(FILE * f)初始读入文章，保存出现的字符记录修改其权重；数据结构选择与算法设计 数据结构选择：signode： struct signode /signode节点，哈夫曼树节点/ char c; /字符/ int weight; /权重/ bool b; /文章中是否出现/ signode * parent; signode * left; signode * right; signode() /初始化/ c=NULL; b=false; weight=0; parent=left=right=NULL; ;C weight b parent left right hufnode: struct hufnode /哈夫曼编码对照表节点/ signode * sig; int code100; /保存哈夫曼编码/ int size;bool b; hufnode()sig=NULL;size=0;b=true;Sig code100 size;HFM:class HFM /哈夫曼类/ private: signode * root; /哈夫曼树根/ signode * pt; /编码时做哨兵指针/ int alleaf; public: HFM(int all)root=pt=NULL;alleaf=all; /all是森林中树的个数/ HFM() signode * getroot()return root; signode * creat(); /创建哈夫曼树/ void hufcode(); /编码/ void savewithhufcode(FILE * inf,FILE * outf); /用哈弗曼编码存储文件/ void hufdecode(FILE* ipf,FILE* opf); /解码/ void inorder(signode * sig); int maxc(); /求取哈弗曼编码最大长度/;Root pt alleafcreat() hufcode() savewithhufcode(inf,outf) inorder(sig) getroot()hufdecode(ipf,opf) maxc()算法设计：init(SN)初始化SN数组input（f1）从f1读入字符 输出字符信息及权重 huffman.creat（）创建哈夫曼树 huffman.hufcode(); exchange(); huffman.savewithhufcode(f1,f2);哈夫曼编码并用该编码保存 文件输入数字选择compress（）1. 查看哈夫曼编码3.查看压缩率2.哈夫曼解码huffman.hufdecode(f2,f3)输入数字选择测试结果Doc窗口： 文件读写（部分）： 总结程序分析： 本次哈夫曼编码译码器的课程实验做得还算成功，不仅仅在于程序能够正常运行，实现应有的功能，关键在于过程，在于小组成员的分工合作和一起纠错排错的过程，在完成程序的过程中才能真正理解面向对象和模块化设计的思想，我们不仅仅是说要每人分几个函数，关键在于这些函数代表的是一个个功能模块，任何一个模块出现问题或者模块之间的衔接出现问题都将导致程序运行的失败。哈夫曼编码译码器课程实验我主要负责完成编码译码器数据结构和功能模块框架的设计，结构体和类的定义，以及creat函数，hufcode函数，savewithhufcode函数的实现。在初始设计的时候，我体会到书写流程图的重要性，只有又一个清晰的设计思路才能事半功倍，分工明确，避免无效劳动或者在错误的编程方向上走弯路，也让大家明白自己在程序设计中的位置和职责。初始的创建是哈夫曼编码译码系统成功的关键，我在创建的过程当中多次使用树的先根，配合中根遍历操作，输出接点字符或者权重信息，作为检验，对验证和纠错起到了非常大的作用。在适当的地方调用它们，运行时可以看到验证编写程序的正确性； 通过本次实验，提高了自已调试程序的能力。充分体会到了在程序执行时的提示性输出的重要性。编写大一点的程序，应先写出算法，再写程序，一段一段调试；对于没有实现的操作用空操作代替，这样容易找出错误所在。最忌讳将所有代码写完后再调试，这样若程序有错误，太难找 。需要特别强调的是：1 感觉文件操作自己并不是很熟练，尽管在向显示器输出的时候并没有什么错误但是读写文件的时候就没那么顺利了，比如说当编写savewithhufcode函数时读文件，却总不执行，后来通过断点测试发现每次fgetc()返回值总为-1，于是我考虑是否是文件没有打开或者文件结束的缘故，后来想通了是之前打开的文件光标读操作结束后仍在结尾故每次总返回-1，故调用rewind函数将光标位置移动到文章开始。2. 用哈夫曼编码存储文件的时候还应注意数字0,1与字符0,1的不同，不应直接在fputc()函数中直接写入0,1那么将会是写入的文章中什么都没有，因为0在ASCII码中代表NULL。3.该程序函数清晰功能明确，程序具有通用性，对于不同的输入文章都可进行处理，由于采用哈夫曼编码对照表，使得查看哈夫曼编码是效率较高无需每次遍历哈夫曼树。程序清单.cpp#include#include#include#include#includeHh1.husing namespace std;FILE * f1=fopen(d:pra1.txt,r);FILE * f2=fopen(d:pra2.txt,w);FILE * f3=fopen(d:pra4.huf,w);int main()init(SN); /初始化字符数据库/input(f1); /读入初始文件的字符/for(int i=0;foresti!=NULL;i+)coutc:weightendl; /输出字符及出现次数/ cout出现字符种类 countendl; /输出字符种类/ HFM huffman(count); /创建哈夫曼树实例/ huffman.creat(); /创建哈夫曼树/ count=0;huffman.hufcode(); /哈夫曼编码，此时为逆向/ exchange(); /调整首尾对调哈夫曼编码/ huffman.savewithhufcode(f1,f2); /用哈夫曼编码存储原文件/coutendl;cout1.查看哈夫曼编码endl; cout2.哈夫曼解码endl; cout3.查看压缩率choice;while(choice=1&choice=3) switch(choice)case 1:for(i=0;hufNodei.sig!=NULL;i+)cout字符c的哈夫曼编码:; /输出哈夫曼编码/for(int j=0;jhufNodei.size;j+)couthufNodei.codej;coutendl; cout最大列数:huffman.maxc()endl; break;case 2:fclose(f2);f2=fopen(d:pra2.txt,r); huffman.hufdecode(f2,f3); /哈夫曼解码/coutendl;break;case 3:compress(); /查看压缩情况/coutendl; cout1.查看哈夫曼编码endl; cout2.哈夫曼解码endl;cout3.查看压缩率choice; cout*谢谢使用*endl; /退出操作/ return 0;.h#includeusing namespace std;struct signode /signode节点，哈夫曼树节点/char c; /字符/int weight; /权重/bool b; /文章中是否出现/signode * parent;signode * left;signode * right;signode() /初始化/c=NULL;b=false;weight=0;parent=left=right=NULL;signode SN256; signode * forest256; /森林数组保存出现的字符/ int count=0; /出现字符计数/ float memo1=0,memo2=0; /全局变量记录读入字符数和编码的0 1数/ void init(signode * sig) /SN数组初始化，输入常见字符/ sig0.c=a;sig1.c=b;sig2.c=c;sig3.c=d;sig4.c=e;sig5.c=f;sig6.c=g;sig7.c=h;sig8.c=i;sig9.c=j;sig10.c=k;sig11.c=l;sig12.c=m;sig13.c=n;sig14.c=o;sig15.c=p;sig16.c=q;sig17.c=r;sig18.c=s;sig19.c=t;sig20.c=u;sig21.c=v;sig22.c=w;sig23.c=x;sig24.c=y;sig25.c=z; sig26.c=A;sig27.c=B;sig28.c=C;sig29.c=D;sig30.c=E;sig31.c=F;sig32.c=G;sig33.c=H;sig34.c=I;sig35.c=J;sig36.c=K;sig37.c=L;sig38.c=M;sig39.c=N;sig40.c=O;sig41.c=P;sig42.c=Q;sig43.c=R;sig44.c=S;sig45.c=T;sig46.c=U;sig47.c=V;sig48.c=W;sig49.c=X;sig50.c=Y;sig51.c=Z; sig52.c=0;sig53.c=1;sig54.c=2;sig55.c=3;sig56.c=4;sig57.c=5;sig58.c=6;sig59.c=7;sig60.c=8;sig61.c=9;sig62.c=+;sig63.c=-;sig64.c=*;sig65.c=/;sig66.c=,; sig67.c=.;sig68.c=; sig69.c=;sig70.c=:;sig71.c=;sig72.c=;sig74.c=;sig75.c=?;sig76.c= ;sig77.c=(;sig78.c=);sig79.c=;sig80.c=;sig81.c=;sig82.c=;sig83.c=!;sig84.c=;sig85.c=#;sig86.c=$;sig87.c=%;sig88.c=;sig89.c=&;sig90.c=;sig91.c=10;void compress() /压缩情况对比/ cout压缩前:memo1*8bit 压缩后:memo2bitendl;cout压缩率:memo2/(memo1*8)endl;struct hufnode /哈夫曼编码对照表节点/ signode * sig;int code100; /保存哈夫曼编码/ int size;bool b; hufnode()sig=NULL;size=0;b=true;hufnode hufNode256;void exchange() /调换首尾交换哈夫曼编码/ int temp; for(int i=0;hufNodei.sig!=NULL;i+)for(int s=0,b=hufNodei.size-1;s=b;s+,b-)temp=hufNodei.codes;hufNodei.codes=hufNodei.codeb;hufNodei.codeb=temp class HFM /哈夫曼类/ private:signode * root; /哈夫曼树根/signode * pt; /编码时做哨兵指针/ int alleaf; public:HFM(int all)root=pt=NULL;alleaf=all;/all是森林中树的个数/HFM()signode * getroot()return root;signode * creat(); /创建哈夫曼树/ void hufcode(); /编码/void savewithhufcode(FILE * inf,FILE * outf); /用哈弗曼编码存储文件/ void hufdecode(FILE* ipf,FILE* opf); /解码/ void inorder(signode * sig); int maxc(); /求取哈夫码曼最大长度/;signode * HFM:creat()signode * pp=NULL; for(int i=0;ib=false; /为hufcode函数作准备，与此函数无关/ while(count1)int min=10000;int min1,min2;for(int i=0;foresti!=NULL;i+) /以下三个for循环选出当前森林中的最小两个节点/ if(foresti-weightweight;min1=i; / /min=10000; / for(i=0;foresti!=NULL&i!=min1;i+) /if(foresti-weightweight;min2=i; / for(i=min1+1;foresti!=NULL;i+) /if(foresti-weightweight;min2=i; / /至此找到min1 min2pp=new signode(); /新生成节点，权值为两最小节点权值之和/pp-left=forestmin1;pp-right=forestmin2;forestmin2-b=true; /为hufcode函数作准备，与此函数无关/pp-weight=forestmin1-weight+forestmin2-weight;forestmin1-parent=pp;forestmin2-parent=pp; forestmin1=pp; /新生成节点加入森林for(i=min2;foresti!=NULL;i+)foresti=foresti+1; /min2后的节点依次前移/count-;root=pp;return pp;void HFM:hufcode() /哈夫曼编码，保存在hufNode节点的数组当中/inorder(root);for(int i=0;hufNodei.sig!=NULL;i+)signode * gud=hufNodei.sig;while(gud-parent!=NULL)if(gud-parent-left=gud)hufNodei.codehufNodei.size+=0;else if(gud-parent-right=gud)hufNodei.codehufNodei.size+=1;gud=gud-parent;void HFM:savewithhufcode(FILE * inf,FILE * outf) /用哈