用C++实现Huffman文件编码和解码

这些都是相当细节性的问题，另外文件中一般有n多个1024长度的以上的字节数，如何承上启下也是问题。 这一切，都在下面这段代码中解决：

1 char Buffer[128];

2 char DecodeBuffer[1056];//增加了八个缓冲字节 3 DWORD dwReadByte; 4 DWORD dwFlag = 1; 5 DWORD dwDeep = 0; 6 char tmpchar;

7 int EffectiveBufferSize = 0; 8 int nLeftNumberInBuffer = 0; 9 char szSmallBuffer[2] = {0}; 10

11 //创建解压文件

12 HANDLE hDeCompressionFile = QuickCreateFile(\); 13 assert(hDeCompressionFile != INVALID_HANDLE_VALUE); 14

15 while(1) 16 {

17 int i = 0;

18 dwReadByte = ReadHuffCodeFromFile(hHuffFile, Buffer, 128); 19 if(dwReadByte == 0) 20 break;

21 EffectiveBufferSize = ReadBitToBuffer(Buffer, (int)dwReadByte, DecodeBuffer + nLeftNumberInBuffer, 1024);

22 EffectiveBufferSize += nLeftNumberInBuffer; 23 //TextFileFunction(DecodeBuffer, 1024);

24 for(i = 0;(i + dwDeep) < EffectiveBufferSize;i += dwDeep) 25 {

26 dwDeep = 0;

27 tmpchar = DecodeHuffman(&vecHuffmanArray[0], DecodeBuffer + i, EffectiveBufferSize - i, dwDeep, dwFlag); 28 if(dwFlag == 1) 29 {

30 szSmallBuffer[0] = tmpchar;

31 WriteBufferIntoFileNormally(hDeCompressionFile, szSmallBuffer, 1);

32 } 33 else 34 {

35 dwFlag = 1;

36 break; 37 } 38 }

39 nLeftNumberInBuffer = EffectiveBufferSize - i;

40 memcpy(DecodeBuffer, DecodeBuffer + i, nLeftNumberInBuffer); 41 }

这段代码中对于这种问题完成的很好，我上面说的在晚上去吃饭的路上就是想明白了实现承上启下那个问题的。 大致步骤如下：

要注意到参数Deep是引用值，是会修改原值的。这个值同时是递归时使用的字符串偏移地址，这个地址所在的值，决定了下一级是向左子树走还是向右走的方向。也就是根据字符串数据来访问Huffman树，一旦访问到叶子节点，就表明此次的解码完成了，返回这个对应值。虽然是递归调用，但是每一级递归调用只有一条通路选择，所以返回值具有可传递性。

完成一段字符串的解码之后，此时的Deep参数就已经是访问过的字符串个数了，就能用于下一次解码的地址偏移，能够用于循环代码操作。

另外还有个问题就是，我从获取的huffman解码整条字符串，都是8的倍数（因为下级函数时将一个字节的8位数据按位解读，写入字符串），所以到最后的一段字符串解码失败很正常，因为这段字符串码不完全。此时就需要将这段字符码移到首部，然后与下一次读出来的字符码进行拼接。你可以注意到，我的代码中，一般都是在for循环中直接声明int i，但是在这里却是在while循环外声明的i，就是为了实现拼接，使得解码操作能够传递下去。如果一次性创建一个很大很大的缓冲区把整个文件都读进来，我只能说：图样图森破。

具体的操作就看代码吧，我写的时候是有点小纠结的，但是写完了一看，呵呵，就这么简单。

这样，解码也就完成了。

最后说一下文件操作。

首先写文件有一块很重要的就是，需要写一个文件头。而且是一个变长的文件头。 文件头主要内容：（不涉及文件夹） 1 文件原名，以及后缀 2 需要编码的数据的数据个数 3 存在的字符和该字符出现的次数

上面的2 3其实就是把构造Huffman树最基础的数组存入文件中，这样解压文件就能根据文件头来构造Huffman树，从而实现解码了。为此我专门写了一个负责文件头的函数。而且这里有个注意事项就是，写文件的时候，要把排好序的数组写进去，这样解压文件就不需要再次进行排序了，能省则省嘛。 查看文件头数据：

这个是我以前水平还很烂很烂的时候写的一个查看程序，最可笑的就是，我这缓冲区用的是一个CString，现在看看，真是荒唐可笑。

不过现在对于小文件，还是能看一看的。你能看到，前几个都是1的，就是int数据，只有出现1次的字符。后面出现的次数逐渐增加。

再往下拉的话，就是各种乱码了，都是按字节解释起来乱七八糟的东西了。

其实编码解码的文件操作这块，我觉得应该算是计算机中，对最小数据单元的操作了，绝对没有比这更小的了。因为要做的是根据编码结果一位一位的将数据写到char变量中，而在读文件这块，也是整块的读内存，然后按位解析字节，获取到以字节为单位的解码数据。

这块我就贴这几个函数，用于从字节到位，和从位到字节的操作。这活，还真的是挺细致的。记得我昨天调代码的时候，还专门调试这几个函数，因为当时解码出来的是乱码，然后我对照写文件前的Huffman码，还真的找到了问题所在。 Byte to Bit

1 void SetByteBit(char * ByteAddr, int Val, int BitAddr) 2 {

3 int TmpVal = -1; 4 int tmpval = 1;

5 tmpval <<= BitAddr; 6 if(Val == 0) 7 {

8 TmpVal ^= tmpval; 9 *ByteAddr &= TmpVal; 10 } 11 else 12 {

13 *ByteAddr |= tmpval; 14 } 15 } 16 /*

17 将huffman码按位写入文件 18 */

19 void WriteByteToFile(HANDLE hFile, const char * lpszHuffCode, int Mode) 20 {