用哈夫曼编码实现文件压缩

1、?用哈夫曼编码实现文件压缩?验工程指导书?数据结构?实验教学改革课题组2006年12月一、实验题目用哈夫曼编码实现文件压缩二、实验目的1、了解文件的概念.2、掌握线性链表的插入、删除等算法.3、掌握Huffman树的概念及构造方法.4、掌握二叉树的存储结构及遍历算法.5、利用Huffman树及Huffman编码,掌握实现文件压缩的一般原理.三、实验设备及环境微型计算机、Windows系列操作系统、VisualC+6.0软件四、实验内容根据 ascii 码文件中各 ascii 字符出现的频率情况创立 Haffman 树,再将各字符对应的哈夫曼编码写入文件中,实现文件压缩.五、实验要求1、用C语言

2、编程实现上述实验内容中的结构定义和算法.2、要有main()函数,并且在main()函数中使用检测数据调用上述算法.3、实验完成后撰写实验报告,实验报告的具体格式参见?实验报告样例?.4、实验完成后把打印好的实验报告以及电子版的实验报告和源程序一并上交.六、实验方法或或步骤1、实验的预备知识(1)构造Hufffman树的方法Hufffman算法构造Huffman树步骤：I.根据给定的n个权值w1,w2,wn,构造n棵只有根结点的二叉树,令起权值为wj.II.在森林中选取两棵根结点权值最小的树作左右子树,构造一棵新的二叉树,置新二叉树根结点权值为其左右子树根结点权值之和.III.在森林中删除这两

3、棵树,同时将新得到的二叉树参加森林中.IV.重复上述两步,直到只含一棵树为止,这棵树即哈夫曼树.(2)Huffman编码：数据通信用的二进制编码思想：根据字符出现频率编码,使电文总长最短编码：根据字符出现频率构造Huffman树,然后将树中结点引向其左孩子的分支标“0,引向其右孩子的分支标“1；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列.(3)二叉树的存储结构typedefstructnodedatatypedata;structnode*lchild,*rchild;BinTree;2、实验步骤(1)启动Visualc+6.0,如图2-1所示.图2-1鼠标单击“文件菜单,选择“

4、NeW菜单,如图2-2所示.图2-23、单击鼠标,在出现的“New对话框中,选择“Projects标签下的“Win32ConsoleApplication选项,如图2-3所示.图2-34、在“Projectname中输入工程名称,单击“OK按钮,如图2-4所示.图2-45、单击“Finish按钮,如图2-5所示.图2-56、鼠标单击“OK按钮,完成工程的创立,如图2-6所示.图2-67、选择“工程“添加工程“NeW菜单,如图2-7所示.图2-7（ 8）、单击鼠标,在出现的、New对话框中,选择、Files标签,选择、c+SourceFile选项,在“File框中输入文件名：“code.c,单击

5、“OK按钮,如图2-8所示.图2-8（ 9）、输入代码,如图2-9所示.图2-93、设计思想1下面给出中实现的Haffman树的结构及创立算法,有两点说明：a）这里的Haffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式,这种空间上的消耗带来了算法实现上的便捷.b）由于对于最后生成的Haffman树,其所有叶子结点均为从一个内部树扩充出去的,所以,当外部叶子结点数为m个时,内部结点数为m-1,整个Haffman树的需要的结点数为2m-1./*Code1:HaffmanAlgorithm*/#defineMAXCHAR30000#defineMAXNODE300#d

6、efineMAXNUM150#defineInfoTypecharstructHtNodeEBTreeTypeww;charinfo;intparentIndex;intllinkIndex;intrlinkIndex;structHtTreestructHtNodehtMAXNODE;introotIndex;typedefstructHtTree*PHtTree;PHtTreehaffmanAlgorithmintm,EBTreeType*wPHtTreepht;inti,j;intfirstMinIndex,secondMinIndex;intfirstMinW,secondMinW;p

7、ht=(PHtTree)malloc(sizeof(structHtTree);assertF(pht!=NULL,inhaffmanalgorithm,memapplyfailuren);/*Initializethetreearray*/for(i=0;ihti.llinkIndex=-1;pht-hti.rlinkIndex=-1;pht-hti.parentIndex=-1;if(ihti.ww=wi;=(char)i;elsepht-hti.ww=-1;for(i=0;im-1;i+)/newInnerNodeNum:m-1firstMinW=MAXCHAR;

8、firstMinIndex=-1;secondMinW=MAXCHAR;secondMinIndex=-1;for(j=0;jhtj.wwhtj.parentIndex=-1)/transminFirstinfotominSecondinfosecondMinIndex=firstMinIndex;secondMinW=firstMinW;/setnewfirstminnode.firstMinIndex=j;firstMinW=pht-htj.ww;elseif(pht-htj.wwhtj.parentIndex=-1)/*updatesecondnodeinfo*/secondMinW=p

9、ht-htj.ww;secondMinIndex=j;/Constructanewnode.m+iiscurrentnewnodesindexpht-htfirstMinIndex.parentIndex=m+i;pht-htsecondMinIndex.parentIndex=m+i;pht-htm+i.ww=firstMinW+secondMinW;pht-htm+i.llinkIndex=firstMinIndex;pht-htm+i.rlinkIndex=secondMinIndex;pht-rootIndex=m+i;returnpht;(2)压缩过程的实现：压缩过程的流程是清楚而简

10、单的：1创立Haffman树2翻开需压缩文件3将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出4文件压缩结束.其中,步骤1和步骤3是压缩过程的关键.a)步骤1:这里所要做工作是得到Haffman数中各叶子结点字符出现的频率并进行创立.统计字符出现的频率可以有很多方法:如每次创立前扫描被创立的文件,“实时的生成各字符的出现频率；或者是创立前即做好统计.本文采用后一种的方案,统计了十篇不同的文章中字符出现的频率.当前,也可以根据被压缩文件的特性有针对性的进行统计,如要压缩C语言的源文件,那么可事先对多篇C语言源文件中出现的字符进行统计,这样,会创立出高度相对较“矮的Haff

11、man树,从而提升压缩效果.b)步骤3:将需压缩文件中的每个ascii码对应的haffman编码按bit单位输出,这是本压缩程序中最关键的局部.这里涉及“转换和“输出两个关键步骤：“转换局部大可不必去通过遍历Haffman树来找到每个字符对应的哈夫曼编码,可以将每个Haffman码值及其对应的ascii码存放于如下所示的结构体中：typedefstructcharasciiCode;unsignedlonghaffCode;inthaffCodeLen;HaffCode;创立由该结构体结点所组成的,长度为128的一维数组codeList128且codeList中的下标和asciiCode满足下

12、面的顺序存放关系：codeListi.asciiCode=i;这样的话,查找某个字符inChar的haffman编码的工作便变得相当轻松了,如下：sHaffCode=codeListinChar.haffCode;数组codeList128的创立可以采用某种遍历方式下的按找到的字符进行置数的方式,十分的方便./*Code2:codeList的创立算法,采用前序遍历的方式进行创立.*/voidpreHaffListMake(PHtTreeinTree,introotIndex,unsignedlongyouBiao,intsDepth,HaffCode*inList)if(inTree-htro

13、otIndex.llinkIndex=-1&inTree-htrootIndex.rlinkIndex=-1)inListinTree-htrootI.haffCode=youBiao;inListinTree-htrootI.haffCodeLen=sDepth;elsepreHaffListMake(inTree,inTree-htrootIndex.llinkIndex,youBiaohtrootIndex.rlinkIndex,(youBiao1)|0 x01,sDepth+1,inList);“输出局部是最重要的局部,也是最易出错的局部.这

14、里,涉及到C语言的位操作,要求这个算法能处理好以下几个问题：1)每个字符所对应的hafCode的比特位长度由523位不等长,不可少输,多输,输错任何一位,后一个字符的haffCode要紧跟在前一个字符的haffCode后面.2)最后一个字符要能合理的结束.这主要是为解压缩考虑的,比方,在最后一个要输出的haffCode的最后一位,它恰好是位于最后一个有效字符的第一位,剩下的七个比特位是要用无效的haffCode加以填充的.否那么,如果填充的haffCode亦为某个ascii字符的haffCode时,那么在解压缩时,那么该在原被压缩文件中不存在的字符便会无中生有的在解压后的文件中出现,这显然是不

15、正确的,应在程序中加以处理.编码局部的流程如图3-1所示：图3-1/*Code3:压缩局部的核心代码*/#defineREARPOS80curIndex=curLen=0;rearCode=haffListREARPOS.haffCode;rearCodeLen=haffListREARPOS.haffCodeLen;while(!feof(inputFile)count=0;outputData=0 x01;while(count8)/*/if(curIndex=curLen)/1.getdata.if(feof(inputFile)break;inData=fgetc(inputFile);printf(%c,inData);if(inData=-1&feof(inputFile)if(count=0)outputData=-1;else/*therearoutputadjust*/for(i=0;i8-count;i+)outputData(rearCodeLen-1-i)&0 x01);break;/2.searchtable-Shouldbeaasciifile.curCode=haf