哈夫曼编码译码器试验报告免费

1、哈夫曼编码译码器实验报告（免问题解析与解题方法问题分析： 设计一个哈夫曼编码、译码系统。对一个ASCII 编码的文本文件中的字符进行哈夫曼编 码，生成编码文件；反过来，可将编码文件译码 还原为一个文本文件。（ 1） 从文件中读入任意一篇英文短文 （文件为 ASCII 编码，扩展名为 txt ）；（ 2） 统计并输出不同字符在文章中出现的频 率（空格、换行、标点等也按字符处理） ；（ 3） 根据字符频率构造哈夫曼树， 并给出每个 字符的哈夫曼编码；（ 4） 将文本文件利用哈夫曼树进行编码， 存储 成压缩文件（编码文件后缀名 .huf ）（ 5） 用哈夫曼编码来存储文件， 并和输入文本 文件大小进

2、行比较，计算文件压缩率；（ 6） 进行译码，将 huf 文件译码为 ASCII 编 码的 txt 文件，与原 txt 文件进行比较。 根据上述过程可以知道该编码译码器的关键 在于字符统计和哈夫曼树的创建以及解码。哈夫曼树的理论创建过程如下：一、构成初始集合 对给定的 n 个权值 W1,W2,W3,.,Wi,.,Wn 构成 n 棵二 叉树的初始集合F=T1,T2,T3,.,Ti,.,Tn ，其中每棵二 叉树 Ti 中只有一个权值为 Wi 的根结 点，它的左右子树均为空。二、选取左右子树在 F 中选取两棵根结点权值最小的树 作为新构造的二叉树的左右子树，新 二叉树的根结点的权值为其左右子树 的根结

3、点的权值之和。三、删除左右子树从 F 中删除这两棵树，并把这棵新的二 叉树同样以升序排列加入到集合 F 中。四、重复二和三两步，重复二和三两步，直到集合 F 中只有一 棵二叉树为止。因此，有如下分析：1. 我们需要一个功能函数对 ASCII 码的初始 化并需要一个数组来保存它们；2. 定义代表森林的数组，在创建哈夫曼树的 过程当中保存被选中的字符，即给定报文 中出现的字符 ,模拟哈夫曼树选取和删除左 右子树的过程；3. 自底而上地创建哈夫曼树，保存根的地址 和每个叶节点的地址，即字符的地址，然 后自底而上检索，首尾对换调整为哈夫曼 树实现哈弗曼编码；4. 从哈弗曼编码文件当中读入字符，根据当

4、前字符为 0 或者 1 的状况访问左子树或者 右孩子，实现解码；5. 使用文件读写操作哈夫曼编码和解码结果 的写入；解题方法：结构体、数组、类的定义：1. 定义结构体类型的 signode 作为哈夫曼树 的节点，定义结构体类型的 hufnode 作为 哈夫曼编码对照表的节点， 定义 HFM 类实 现对哈夫曼树的创建，利用其成员函数完 成哈夫曼编码译码的工作。2. 定义 signode 类型的全局数组 SN256（为 方便调用，之后的 forest256 ，hufNode256 均为全局数组） , 保存 ASCII 编码的字符， 是否在文章中出现（ bool 类型）以及出现 次数（int 类型，

5、权重），左右孩子节点位置， 父节点位置信息；3. 为节省存储空间， 定义 signode * 类型的全 局数组 forest256, 模拟森林， 在创建哈夫 曼树的过程中保存出现字符的指针，模拟 哈夫曼树选取和删除左右子树的过程；4. 定 义 hufnode 类 型 的 全 局 数 组 hufNode256 ，在编码时最为哈夫曼编码对 照 表 的 节 点 ， char 型 c 保 存 字 符 ,int code100保存其哈夫曼编码；5. 定义 HFM 类，主要保存哈夫曼树的根节点 指针，但其丰富的功能函数将实现哈夫曼 编码译码的工作及其他功能；函数介绍：1. void init（signod

6、e * sig） 初始化数组 SN；2. void compress（） 输出压缩对比情况 的信息;3. void exchange() 用两层 for 循环实现 hufNodei 节点 的成 员哈 夫曼编 码 数组 code 前后元素的对换， 因为在之前的编码 过程中由于是从叶节点追溯至根节点，存 入 code 数组的哈夫曼编码与哈夫曼编码的 概念反向，故而要调整；4. signode * getroot() 返回哈夫曼树的 根节点指针；5. signode * HFM:creat() 创建哈夫曼 树，首先用三个 for 循环查看 forest 数组， 找到权值最小的两个字符，以 int 型

7、的 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 循环控制

8、查看 hufNode 数组，其初始化 已在 creat ()的开始完成，对每一个字符 实现编码， 用 while 循环从叶节点开始， 如 果该节点是其父节点的左孩子就将 codehufNodei.size+ 赋值 0，否则赋为 1， 直至当前节点的父节点为空， while 循环结 束；7. void HFM:savewithhufcode(FILE * inf,FILE * outf) 将读入的文章以哈 夫曼编码的形式存储， 其中 inf 为读入文件 的指针， outf 为写入文件的指针 ,首先调用 rewind(inf) 函数将光标放置在文章开头， 防 止文件未关闭导致的错误，每读一个字符

9、就用 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) 解码，从哈夫曼编码到字符，输 出到屏

10、幕和指定的文件中；11. void input(FILE * f) 初始读入文 章，保存出现的字符记录修改其权重；数据结构选择与算法设计数据结构选择：signode：structsignode /signode 节点，哈夫曼树节点 /charc;/字符 /intweight;/权重 /boolb;/文章中是否出现 / signode * parent; signode * left;signode * right;signode() 化/c=NULL;b=false;weight=0; parent=left=right=NULL; ;Cweightbhufnode:struct hufnod

11、e/哈夫曼编码对照表节点 / signode * sig; int/保存哈夫曼编码 /初始code100;int size;bool b;hufnode()sig=NULL;size=0;b=true;SigHFM:classHFM/哈夫曼类 /private:root;pt;signode * /哈夫曼树根 /signode * /编码时做哨兵指针 /int alleaf;public:HFM(int all)root=pt=NULL;alleaf=all; /all 是森林中树的个数 /HFM()signode * getroot()return root;signode/创建哈夫曼树 /

12、voidcreat();hufcode();/编码 /voidinf,FILE * outf); 件/savewithhufcode(FILE/用哈弗曼编码存储文hufdecode(FILE* ipf,FILE*/解码 / void inorder(signode * sig); int maxc();/求取哈弗曼编码最大长度 /;opf);Rootalleafvoidpt算法设计：Doc 窗口：Minininire：TT0T0：IDT:TATATTT0;venw： DIT: KI110W： IHIHRTH：養丿-lm-3了订 44r Jr 亍工4一. j Hr 42 丄I:护-亠r:ii务

13、s 4IB一4r-4l up- A o iHcrHdLlsIwdM 館.吩3;匹佚第蛊応wsM;3J3isu; .二 1 二 一 - 二二匚.二 yyy *辛4.$耳* *=*w書雯*s#s管*wN#=*lr yvg型邹爭，幕型邹歩竽驴审型$卵爭骑型I八yq6nq心皿q叫十册zpxg !汕.力扎文件读写（部分）：总结程序分析： 本次哈夫曼编码译码器的课程实验做得还 算成功， 不仅仅在于程序能够正常运行， 实现应 有的功能， 关键在于过程， 在于小组成员的分工 合作和一起纠错排错的过程， 在完成程序的过程 中才能真正理解面向对象和模块化设计的思想， 我们不仅仅是说要每人分几个函数， 关键在于这

14、些函数代表的是一个个功能模块， 任何一个模块 出现问题或者模块之间的衔接出现问题都将导 致程序运行的失败哈夫曼编码译码器课程实验我主要负责 完成编码译码器数据结构和功能模块框架的设 计，结构体和类的定义， 以及 creat 函数，hufcode 函数， savewithhufcode 函数的实现。在初始设 计的时候， 我体会到书写流程图的重要性， 只有 又一个清晰的设计思路才能事半功倍，分工明 确，避免无效劳动或者在错误的编程方向上走弯 路，也让大家明白自己在程序设计中的位置和职 责。初始的创建是哈夫曼编码译码系统成功 的关键，我在创建的过程当中多次使用树的先 根，配合中根遍历操作， 输出接点

15、字符或者权重 信息，作为检验， 对验证和纠错起到了非常大的 作用。在适当的地方调用它们， 运行时可以看到 验证编写程序的正确性； 通过本次实验，提高了自已调试程序的能 力。充分体会到了在程序执行时的提示性输出的 重要性。编写大一点的程序，应先写出算法，再 写程序， 一段一段调试； 对于没有实现的操作用 空操作代替， 这样容易找出错误所在。 最忌讳将 所有代码写完后再调试， 这样若程序有错误， 太难找需要特别强调的是：1 感觉文件操作自己并不是很熟练， 尽管在 向显示器输出的时候并没有什么错误但是 读写文件的时候就没那么顺利了，比如说 当编写 savewithhufcode 函数时读文件，却 总

16、不执行，后来通过断点测试发现每次 fgetc() 返回值总为 -1 ，于是我考虑是否是 文件没有打开或者文件结束的缘故，后来 想通了是之前打开的文件光标读操作结束 后仍在结尾故每次总返回 -1 ，故调用 rewind 函数将光标位置移动到文章开始。 2. 用哈夫曼编码存储文件的时候还应注 意数字 0,1 与字符 0,1的不同，不应直接 在fputc() 函数中直接写入 0,1 那么将 会是写入的文章中什么都没有，因为 0 在ASCII码中代表 NULL。3. 该程序函数清晰功能明确， 程序具有通 用性，对于不同的输入文章都可进行处 理，由于采用哈夫曼编码对照表， 使得 查看哈夫曼编码是效率较高

17、无需每次 遍历哈夫曼树。程序清单.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 出现

18、字符种类countendl;/输出字符种类 / 创 建 哈 夫 曼 树 实 例 / huffman.creat();/哈夫曼编码，此时为逆向 / 调 整 首 尾 对 调 哈 夫 曼 编 码 / 用哈夫曼编码存储原文件 /HFM huffman(count);/ 创建哈夫曼树 / count=0;huffman.hufcode();exchange(); huffman.savewithhufcode(f1,f2);coutendl;cout1. 查看哈夫曼编码 endl;cout2. 哈夫曼解码 endl;cout3. 查看压缩率 choice;while(choice=1&choice=3)

19、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. 哈

20、夫曼解码 endl;cout3. 查看压缩率 choice;cout* 谢谢使用 *endl;return 0;/输出哈夫曼编码 / 哈夫曼解码 / 查看压缩情况 / 退出操作 /.h#include using 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=r

21、ight=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;

22、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;sig4

23、3.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=;sig

24、74.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/ 哈夫曼编码对照表节点 /signod

25、e * 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=tempclass HFM/哈夫曼类 /p

26、rivate: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);

27、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;forest

28、i!=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;

29、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