用C 实现Huffman文件编码和解码.doc

这个是代码是昨天写完的,一开始的时候还出了点小bug,这个bug在晚上去吃饭的路上想明白的,回来更改之后运行立刻完成最后一步,大获成功。简单说下huffman编码和文件压缩主要的技术。Huffman编码,解码:I创建Huffman树II根据Huffman树实现编码,并将编码结果和要编码的数据建立映射关系。IIIHuffman解码,也就是根据获取的Huffman码来逆向获取解码信息,而且你从解压文件中一次性获取的数据是一个很长的字符串,没有预处理好的成段字符串式Huffman码。1I首先,如何创建Huffman树?在这个我在前天的那篇文章中简单的提了一下,现在好好说一下。如果你不知道什么是Huffman树,请google之~对于获取到的文件,首先要做的就是,建立一个长度为256的int数组,全部置零,然后以字节流的形式读取文件,并对字节流中的字节出现次数进行统计,方法就是以字节数值为数组偏移地址,对应的数组元素进行+1操作。另外这里需要提一下的就是,用于存储文件字节流的缓冲区最好是unsignedchar类型,因为这样能直接使用,如果是char的,在转化为int类型的时候,一旦数值大于127,因为补码问题,你就直接乘上了通往未知数值的高铁~完成统计之后,将这个数组中出现次数不为0的元素添加对应大小的二叉树节点数组中,然后以出现次数为Key值,进行排序。在排序完成之后,就能开始构建Huffman树了。操作如下:1如果数组中元素个数不为1,将前两个元素构造为一个临时节点的子树,此时临时节点的Key值为两个元素Key值之和,然后删除数组中的第一个元素(从数组中删除),再将临时节点赋值给当前数组的第一个元素。(其实就是将前两个元素添加到一个临时节点的左右根节点,然后在原数组中删除这两个元素,,接着再将这个临时节点插入到数组头部,充当新的节点。上面的那段描述我觉得说的不是很清楚,但是那个是我在代码中发现的一个可以优化的地方,减少了一个元素的删除操作)2此时数组依据key值的排序很有可能已经不再有序,而又因为仅有一个乱序元素,所以专门设计了一个函数,一次完成排序,效率,应该是最高的了。重复1这样当数组中只有1个元素的时候,就是Huffman树的根节点了。这样,Huffman树的构造就完成了。我上面说的可能不是很清楚,你看了之后可能会有疑问,所以我在这贴下部分代码,你可以看一下,就是这么简单,而且很巧妙。Huffman树节点,一开始就是一个Struct,但是因为涉及到了STL,所以添加了方法1structHaffmanStruct2{3//asmallstructure4HaffmanStruct():val(0),ncounts(0),lNext(NULL),rNext(NULL){}5booloperator<(HaffmanStruct&);6booloperator>(HaffmanStruct&);7voidReset();8unsignedcharval;9unsignedintncounts;10charHuffmanCode[254];11//usedfortree12HaffmanStruct*lNext;13HaffmanStruct*rNext;14};给他一个数组,他给你一颗Huffman树1voidHuffManEncode(vector<HaffmanStruct>&vecValidNumberArray)2{3HaffmanStructValidStruct;//temporarystruct4//Analysis5while(()!=1)6{();=vecValidNumberArray[0].ncounts+vecValidNumberArray[1].ncounts;=newHaffmanStruct;10*=vecValidNumberArray[0];=newHaffmanStruct;12*=vecValidNumberArray[1];(());14vecValidNumberArray[0]=ValidStruct;15SingleSort(&vecValidNumberArray[0],(),0);16}17}以上就是Huffman树构造的全部过程。 II根据Huffman树获取Huf