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

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