建立一个文本文件A，统计该文件中各字符频率，对各字符进行Huffman编码，将该文件翻译成Huffman编码文件B，再将Huffman编码文件译码成文件C，并对文件A与C进行比较。
1）能够正确读写文件
2）统计文本文件中各字符频率
3）编码：构造哈夫曼树，得到各字符的哈夫曼编码
4）按照哈夫曼编码将文件A翻译为Huffman编码文件B。
5）译码：对文件B进行译码，得到文件C
6）比对文件C与文件A
1）进一步提高压缩算法效率
2）文件A中含有中文字符，提示：英文字符ASCII编码，范围0-127；中文机内码GB2312，2个字节，每个字节编码范围（160~254）。
为了建立哈夫曼树，首先扫描源文件，统计每类字符出现的次数，然后根据字符频度建立哈夫曼树，接着根据哈夫曼树生成哈夫曼编码。再次扫描文件，每次读取8bits，根据“字符—编码”表，匹配编码，并将编码存入压缩文件，同时存入编码表。解压时，读取编码表，然后读取编码匹配编码表找到对应字符，存入文件，完成解压。
首先需要统计出文本文件的各个字符频率，文件长度。根据出现的频率，将频率为0的字符剔除。通过剩下的字符计算出哈夫曼树需要的结点，分配空间，并将字符与频度存入结点中。然后建立哈夫曼树，得到哈夫曼编码。在编码文件中写入字符种类数、字符及权重、文件长度。读取文件，将字符对应的哈夫曼编码写入编码文件。
读取编码文件中的字符种类数，计算哈夫曼树所需结点，分配空间，读取字符及对应权重，存入哈夫曼树结点中，建立哈夫曼树。然后读取文件长度和编码，进行解码。
图8 B题文件结构
如图8所示，头文件夹中的Custom.h是自定义头文件，里面放着常用的头文件。
源文件夹的Compress.c中，放着函数Compress，实现了文件的压缩功能；Huffman.c中，放着寻找两个权值较小的结点Select函数、建立哈夫曼树的函数CreateTree和生成哈夫曼编码的函数HuffmanCode；Main.c中放着主函数；Node.c中放着统计字符频度结点和哈夫曼树结点的定义；Uncompress.c中放着实现解压功能的函数Uncompress。
资源文件夹中放着用来提供内容的文本文档Decompression.txt。
Main.c中，放着主函数。主函数定义了文件存放路径的字符数组name、names、input_file_name、output_file_name用来给其他功能提供参数，并通过while循环实现了一个菜单功能，来调用各个函数。
Node.c中，定义了统计字符频度的临时结点CharactersFrequency，结点中有保存字符的uchar和保存频度的frequency。uchar为了存储范围更大（0~255），且unsigned long和int在32位下空间占用一样，所以都定义为无符号型。
还定义了哈夫曼树结点Huffman，结点中有保存字符的uchar、保存频度frequency、保存字符哈夫曼编码的code（动态分配空间）和双亲以及左右孩子。
Huffman.c中，放着寻找两个权值较小的结点Select函数、建立哈夫曼树的函数CreateTree和生成哈夫曼编码的函数HuffmanCode。
Select函数参数为Huffman树动态分配空间的首地址、结点数以及两个保存最小结点的变量地址a和b，无返回值。
定义一个最小值min，初始值设为unsigned long型最大值ULONG_MAX。遍历每一个双亲是0的结点，将频度最小的结点传给a，将该结点的双亲结点赋值为1，表示已查找过。然后再找下一个最小值，赋值给b，找到后无需标记双亲结点。
CreateTree函数参数为Huffman树动态分配空间的首地址、字符种类数和哈夫曼树所需节点数，无返回值。
哈夫曼树为二叉树，树结点含有权重（在这里为字符频度，同时也要把频度相关联的字符保存在结点中）、左右孩子、双亲等信息。考虑到建立哈夫曼树所需结点会比较多，也比较大，如果静态分配，会浪费很大空间，故我们打算用动态分配的方法，并且，为了利用数组的随机访问特性，也将所需的所有树节点一次性动态分配，保证其内存的连续性。另外，结点中存储编码的空间由于长度不定，也需要动态分配内存。因此在Node.c中，定义了统计字符频度的临时结点CharactersFrequency，这个结点仅保存字符及对应频度，也用动态分配，但是一次性分配256个空间，统计并将信息转移到树结点后，就将这256个空间释放，既利用了数组的随机访问，也避免了空间的浪费。
定义两个变量a和b，遍历非字符结点（没有保存字符和频度的结点，即for (i = char_kind; i < number_node; ++i)），调用函数Select寻找双亲结点为0，频度为最小值和次小值的结点给a和b，将a和b的双亲赋值为i，i结点的频度为a+b的频度。循环直到哈夫曼树建立完成。如图9所示。
图9 CreateTree函数示意图
HuffmanCode函数参数为Huffman树动态分配空间的首地址、字符种类数，没有返回值。
每类字符对应一串编码，故从叶子结点（字符所在结点）由下往上生成每类字符对应的编码，左0，右1。为了得到正向的编码，设置一个编码缓存数组，从后往前保存，然后从前往后拷贝到叶子结点对应编码域中，再根据得到的编码长度为哈夫曼树的code分配空间。对于缓存数组的大小，由于字符种类最多为256种，构建的哈夫曼树最多有256个叶子结点，树的深度最大为255，故编码最长为255，所以分配256个空间，最后一位用于保存结束标志。
首先给字符数组code_temporarily动态分配256个空间，将code_temporarily[255]设为’\0’。然后从叶子向根遍历，左0右1求编码，倒序存入code_temporarily数组中。然后给哈夫曼树的code动态分配存储空间（256-数组下标），将code_temporarily数组暂存的编码存入哈夫曼树的code中。具体如图10所示。
图10 HuffmanCode函数示意图
Compress.c中，放着Compress函数。函数的参数为指向读取文件地址的文件指针、指向生成文件地址的文件指针，int型的返回值。
要建立哈夫曼树，先要得到各类字符的频度，我想到了两种扫描方案，一种是利用链表存储，每扫描到一类新字符就动态分配内存，另一种是利用数组，静态分配256个空间，对应256类字符，然后用下标随机存储。链表在需要时才分配存储空间，可以节省内存。但是每加入一个新字符都要扫描一次链表，很费时。考虑到最多有256个字符种类，不多，使用静态数组不会造成很大的空间浪费，而可以用数组的下标匹配字符，不需扫描数组就可以找到每类字符的位置，达到随机存储的目的，效率有很大的提高。当然，不一定每类字符都出现，所以，统计完后，需要排序，将字符频度为零的结点剔除。
统计字符频度后，打开要生成的文件，将字符种类写入。当字符种类为1时，只有一个哈夫曼结点，无法构造哈夫曼编码，但是可以直接处理，依次保存字符种类数、字符、字符频度（此时就是文件长度）即可，解压时仍然先读取字符种类数，为1则特殊处理，读取字符和频度（此时就是文件长度），利用频度控制循环，输出字符到文件即可。当字符种类不是1时，根据字符种类数，计算建立哈夫曼树所需结点数（2*字符种类数-1），然后动态分配空间建立哈夫曼树所需结点，并将暂存在CharactersFrequency（暂存字符节点）中的字符和频度存入哈夫曼树中，并将所有节点的双亲值初始化为0。
然后调用CreateTree函数建树，调用HuffmanCode函数算哈夫曼编码。然后打开要生成的编码文件，写入字符和相应的权重。紧接着字符和权重信息后面写入文件长度和字符编码。读取文件时这里以feof来判断文件结束，是由于eof判断的文件类型比较局限，而feof在读完最后一个字节之后，再次读文件时才会设置结束标志，所以需要在while循环之前读一次，然后每次在循环的最后读取文件，这样可以正确判断文件结束。在哈夫曼树节点中，编码的每一位都是以字符形式保存的，占用空间很大，不可以直接写入压缩文件，故需要转为二进制形式写入。可以定义一个函数，将保存编码的字符数组转为二进制，但是比较麻烦，效率也不高；正好，可以利用C语言提供的位操作（与、或、移位）来实现，每匹配一位，用“或”操作存入低位，并左移一位，为下一位腾出空间，依次循环，满足8位就写入一次。以位操作来匹配编码，每次存入最低位，然后左移一位，依次循环处理，满8位保存一次，直到全部字符处理完成。具体如图11和图12所示。
图11 将字符对应的哈夫曼码写入编码文件
图12 哈夫曼码不足8位的处理方法
Uncompress.c中，放着Uncompress函数。函数的参数为指向读取文件地址的文件指针、指向生成文件地址的文件指针，int型的返回值。
以二进制方式打开压缩文件，首先将文件前端的字符种类数读取出来，根据字符种类的数量动态分配空间，然后将随后的字符编码读取处理保存到动态分配的结点中，然后开始译码。
以8位为处理单元，依次读取随后的编码匹配对应的字符，这里对比编码依然用在文件压缩中所用的方法，就是用C语言的位操作，同0x80与操作，判断8bits字符的最高位是否为‘1’，对比一位后，左移一位，将最高位移除，次高位移到最高位，依次对比。这次是从编码到字符反向匹配，与压缩时有一点不同，需要用读取的编码逐位与编码表中的编码进行对比，对比一位后，增加一位再对比，而且每次对比都是一个循环（与每个字符的编码对比），效率很低。
于是，我思考另外的方法，可以将哈夫曼树保存到文件中，解码时，从树根到叶子对比编码，只要一次遍历就可以找到编码对应的存于叶子结点中的字符，极大提高了效率。
然而，我们发现树结点中有字符、编码、左右孩子、双亲，而且孩子和双亲还必须是整型的（树节点最多为256*2-1=511个），占用空间很大，会导致压缩文件变大。
我们进一步考虑，可以仅存储字符及对应频度（频度为unsigned long，一般情况下与int占用空间一样，同为4个字节），解码时读取数据重建哈夫曼树，这样就解决了空间问题。
虽然重建哈夫曼树（双重循环，每个循环的次数最大为511）也要花费一定的时间，但是相对上面的与编码表匹配（每位编码都要循环匹配所有字符（最多为256种）一次，而总的编码位数一般很大，且随着文件变大而增长）所花费的时间更少。具体如图13和图14所示。
图13 举例
图14 译码过程
后来我在初步编码时，发现一些问题：解码后无法得到完全正确的源文件，经过排查，发现以EOF判断压缩文件的结束不可取，因为压缩文件是二进制文件，而EOF一般用来判断非二进制文件的结束，所以我们用文件长度来控制译码结束。
图15 主菜单
图16 压缩功能
图17 压缩文件的内容
图18 原文件与压缩文件对比
图19 解压功能
图20 原文件与解压文件对比一
图21 解压文件与原文件对比二