《用哈夫曼编码实现文件压缩》实验报告

《用哈夫曼编码实现文件压缩》实验报告《数据结构》实验教学改革课题组2006年12月《用哈夫曼编码实现文件压缩》实验报告班级:计算机B05-1学号:20050701姓名:一指导教师:实验日期:成绩:一、一验题目:用哈夫曼编码实现文件压缩实验目的1、了解文件的概念。2、掌握线性链表的插入、删除等算法。3、掌握Huffman树的概念及构造方法。4、掌握ニ叉树的存储结构及遍历算法。5、利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理。三、|实验设备与环与:微型计算机、Windows系列操作系统、VisualC++6.0软件四、|实验内容I：根据ascii码文件中各ascii字符出现的频率情况创建Haffman树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩。五、|概要设计卜(1)构造Hufffman树的方法一Hufffman算法构造Huffman树步骤：.根据给定的n个权值{wl,w2, wn},构造n棵只有根结点的ニ叉树,令起权值为Wjo.在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的ニ叉树,置新ニ叉树根结点权值为其左右子树根结点权值之和。, 在森林中删除这两棵树,同时将新得到的ニ叉树加入森林中。.重复上述两步,直到只含ー棵树为止,这棵树即哈夫曼树。(2)Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码,使电文总长最短编码：根据字符出现频率构造Huffman树,然后将树中结点引向其左孩子的分支标“〇”,引向其右孩子的分支标“1”;每个字符的编码即为从根到每个叶子的路径上得到的0、1序列。(3)ニ叉树的存储结构typedefstructnodedatatypedata;structnode*lchiId,*rchild;｝BinTree;六、I详细设卅:(1)Haffman树的存储结构及创建算法:a)这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的ニ叉树形式,这种空间上的消耗带来了算法实现上的便捷。b)由于对于最后生成的Haffman树,其所有叶子结点均为从ー个内部树扩充出去的,所以,当外部叶子结点数为m个时,内部结点数为m・l,整个Haffman树的需要的结点数为2m-1〇存储结构如下:structHtNode(EBTreeTypeww;charinfo;intparentindex;intllinklndex;intrlinklndex;｝；structHtTree(structHtNodeht[MAXNODE];introotindex;｝；构造Haffman树流程图如下:

(2)将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出,这是本压缩程序中最关键的部分。这里涉及“转换”和“输出”两个关键步骤:“转换”部分大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码,可以将每个Haffman码值及其对应的ascii码存放于结构体中:codeList的创建算法,采用先序遍历的方式进行创建,并且利用递归调用。流程图如输出''部分是最重要的部分,也是最易出错的部分。这里,涉及到c语言的位操作,要求这个算法能处理好以下儿个问题:a）每个字符所对应的haffCode的比特位长度由5~23位不等长，不可少输,多输,输错任何一位,后ー个字符的haffCode要紧跟在前一个字符的haffCode后面。b）最后ー个字符要能合理的结束。这主要是为解压缩考虑的,比如,在最后ー个要输出的halTCode的最后一位,它恰好是位于最后ー个有效字符的第一位,剩下的七个比特位是要用无效的haffCode加以填充的。否则,如果填充的haffCode亦为某个ascii字符的haffCode时,那么在解压缩时,则该在原被压缩文件中不存这显然是不正确的,应在程序中在的字符便会无中生有的在解压后的文件中出现,加以处理。这显然是不正确的,应在程序中编码部分的流程下图所示:(3)main。主函数:通过实验更好的掌握了哈夫曼树,并对哈夫曼树有了深ー步的了解。本程序将字符出现的频率（即权值）放在key.txt文件中,然后将这些权值读取出来保存到ー个数组中,然后再根据此数组构造Huffman树,得出各字符的Huffman编码值,所以如果没有此key.txt文件,压缩就不会成功。压缩过程中,是对ascii码进行ーー对应的转换,没有丢失原文件的信息,是无损压缩。在解压缩压缩后的文件时,文件类型变为・.rer格式,用其他软件都不能打开,必须有key.txt文件,所以本程序除了可以对文件压缩之外还可以用来对・.txt文件进行加密。通过本次实验我更好的掌握了对程序的调试,并从中感受到调试的巨大的力量,特别是当程序不能实现预想结果时通过对程序的反复调试,做到对问题的深入了解。所以大程序对我们的编程有着很大的帮助。但在调试中由于算法推敲不足,使程序调试时费时不少。但总的来说这次程序的调试收获不少,感谢老师给了这么一次机会给我们练习。cミC:\IIND0fS\SysteB32\cBd.exe-codeBainTest.txt 日日inputfileopensuccessoutputfileopensuccesshaffCodeList：2089856,2089857,2089858,2089859,2089860,2089861，2089862,2089863,2089864,57,16,2089865,2089866,17,2089867,2089868,2089869,2089870,2089871,2089872,2089873,2089874,2089875,2089876,2089877,2089878,2089879,2089880,2089881,2089882,2089883,2089884,6,63,310,1234,65309,426,1413,58,316,337,2543,212,54,43,81,309,25,200,338,2041,2537,443,880,2542,1235,1763,201,709,4080,616,107,707,32652,253,508,160,30,101,509,339,311,111,56,52,355,161,27,352,159,8162,24,76,252,59,62,336,1269,708,1270,2824,2536,2825,2089885,32655,2089886,7,85,62,2,14,17,26,9,2,441,51,18,41,0,3,24,1021,30,23,5,45,78,89,1022,16,1023,427,442,1762,32653,2089887haffCodeListLen：21,21,21,21,21,21,21,21,21,9,5,21,21,5,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,21,3,9,9,11,16,12,11,9,9,9,12,11,7,6,7,9,8,9,9,11,12,10,11,12,11,12,9,10,12,10,10,10,15,8,9,8,8,8,9,9,9,8,9,9,9,8,8,9,8,13,8,7,8,9,9,9,11,10,11,12,12,12,21,15,21,4,7,6,5,4,6,6,5,4,10,7,5,6,4,4,6,10,5,5,4,6,7,7,10,6,10,12,10,12,15,21teststart-testends.。后退，の▼落に文件夹 xg区］，地址①)I匕!D:、算法与数据结构实验题目、新建文件夹大小类型修改曰期173KB应用程序2006-1-2420:45229KB应用程序2006-1-2420:5061KB文本文档2007-11-3021:431KB文本文档2007-11-6