Huffman压缩 实验报告 源程序

实验目的

⒈了解有关文件的基本概念

⒉掌握哈夫曼树的概念及其构造方法

⒊正确实现线性链表的插入，删除等运算

⒋掌握遍历二叉树的方法

⒌运用哈夫曼树及其编码

实验环境

实验内容

根据ascii码文件中各ascii字符出现的频率情况创建哈夫曼树，再将各字符对应的哈夫曼编码相连，每八位作为一个字符，写入文件中，同时Huffman树也要压缩后写入压缩文件，以实现文件压缩。

设计概要

压缩部分

1.构造哈夫曼树，对其进行前缀编码

（1）扫描待压缩文件，得出各字符出现频率。

（2）根据给定的n个权值{W1,W2,...Wn}构成n棵二叉树的集合F={T1，T2，…，Tn}，每棵二叉树Ti中只有一个带权为Wi的根节点，其左右子树均空。

（3）在F中选取两棵根节点的权值最小的树作为左右子树构造一棵新的二叉树，且值新的二叉树的根节点的权值为其左右子树上根节点的全值之和。

（4）在F中删除这两棵树。同时将新得到的二叉树加入F中。

重置（2）和（3），直到F只含一棵树为止。这棵树便是哈夫曼树。

2.由Huffman树得到各字符前缀编码。

3.根据前缀编码，对文件中各个字符进行编码，并按每八位一次写入压缩文件。

4.处理剩余不到八位部分，写入压缩文件。

5.将前缀编码及相关信息写入压缩文件。

6.关闭指针，完成压缩。计算压缩率。

解压部分

1. 读入压缩文件长度和源文件长度。读入前缀编码。

2. 对文件中各字符解码，写入解压文件。

3. 判断解压文件是否完好（对比压缩前文件长度），关闭指针，完成解压。

源码部分：

#include

#include

#include

#include

struct head {

       记录字符在数组中的位置

        字符出现频率（权值） 

       定义哈夫曼树指针变量

        定义存储哈夫曼编码的数组

}header[512],tmp;

void compress() 

{

        作计数或暂时存储数据用

  记录最小结点、文件长度

        计算压缩比用

       分别为输入、输出文件指针

 请您输入需要压缩的文件（需要路径）："); 

  文件打开失败!\\n "); 

 请您输入压缩后的文件名（如无路径则默认为桌面文件）："); 

  压缩文件失败!\\n "); 

       字符重复出现频率+1

        字符出现原文件长度+1

       原文件长度用作求压缩率的分母

         将每个哈夫曼码值及其对应的ASCII码

         存放在一维数组header[i]中，且编码表

         中的下标和ASCII码满足顺序存放关系*/

    对结点进行初始化

      按出现权值从大到小排序

      找到第一个空的header结点

      预设的最大权值，即结点出现的最大次数

        说明该结点已存在哈夫曼

         树中，跳出循环重新选择新结点*/

  header[pt1].parent=i;   //哈夫曼无重复前缀编码

      //根结点编码0

   ].lch==j){   //置左分支编码0

//依次存储连接"0""1"编码，此处语句为网络借鉴

         置右分支编码1

   从文件开始位置向前移动0字节，即定位到文件开始位置

   用来将数据写入文件流中，参数flength

    指向欲写入的数据地址，总共写入的字符数

    以参数size*int来决定，返回实际写入的int数目*/ 

   定义缓冲区,它的二进制表示00000000

   假设原文件第一个字符是"A"，8位2进制为01000001，

    编码后为0110识别编码第一个'0'，那么将其左移一位，

    看起来没什么变化。下一个是'1'，应该|1，结果00000001 

    同理4位都做完，应该是00000110，由于字节中的8位并没有

    全部用完，继续读下一个字符，根据编码表继续拼完剩下

    位，如果字符的编码不足4位，还要继续读一个字符，如果

    字符编码超过4位，那么把剩下的位信息拼接到一个新的字节里*/

       找到对应的header[i]

        添加最后一位为1

         添加最后一位为0

         最后不满八位的buf处理

      后加八位0

       逐位输入八位前的二进制符

      指针回到输出文件头部后面四位

    统计了输出文件中的字符个数，包括了最后的'/0'

     统计了权值不为0的header[]数量

    依次写入每个叶子结点的b、长度和内容

        若存储的位数不是8的倍数，则补0

     字符的有效存储不超过8位，则对

          有效位数左移实现两字符编码的连接，

          可理解为前缀编码也被压缩过*/

       以上与上面连接字符一段可相同理解

   计算文件的压缩率

 压缩文件成功!\\n"); 

 压缩率为 %f%%\\n\\n",div*100); 

}

void uncompress(){

 请您输入需要解压缩的文件（如无路径则默认为桌面文件）："); 

  文件打开失败!\\n "); 

 请您输入解压缩后的文件名："); 

  解压缩文件失败!\\n "); 

     读入文件长度flength

      读入header数组的存储地址

      读入header数组中元素的个数

        读入header数组

         此处借鉴网络程序，包括itoa()函数

           函数的作用为，把int型的f

           化为二进制数，再变成char型存入buf*/

         在单字节内对相应位置补0

        按Huffman编码从小到大排序

        对文件其余部分，即真正的文件部分解压缩

      依次比对Huffman前缀编码

                  此函数也为网络借鉴，memcmp函数此处的作用

         是比较bx的相应位是否与header[i].bits相同，

         若前header[i].count均相同，则返回0 */

        用来统计解压缩后文件的长度

       检验是否与源文件长度匹配

 解压缩文件成功!\\n"); 

  解压缩文件与原文件相同!\\n\\n"); 

  解压缩文件与原文件不同!\\n\\n");

}

int main(){

  Huffman前缀编码 压缩＆解压缩 俞映洲\\n");

  压缩 解压缩 退出

         对用户输入进行容错处理

   请选择相应功能编号

    请检查您的输入在0~2之间！ 请再输入一遍！\\n");

         调用压缩子函数

        调用解压缩子函数

return 0;

}

数据测试

文件1：60个a，press1.txt内容为：

解压后文件内容不变。

文件2：本程序源代码

解压后文件内容同样不变。

文件3：带有全角字符的文件（由于文件较短，压缩率很低）

检查后发现文件内容不变。

文件5：本实验报告（DOC文档，未完成）

检查后发现没有错误。

文件6：一份PDF文档（非简单文档）

检查后发现依然没有错误。

容错性检查

若在程序主界面输入“3”，则结果如上图。

若输入了不存在的文件，则结果如上图，解压缩部分的结果类似。

实验小结

1.一开始用的编译器是TURBO C 2.0 ，但由于其中数组元素的上限过小，编译无法通过。后改用VC++ 6.0，才解决了这个问题。

2.本程序的难点有：.前缀编码的生成（位运算）

.压缩、解压缩时字符串的衔接 

.压缩文件中各部分的安排，要让解压缩程序能顺利读取各部分数据

3.程序较长，调试中遇到较多困难；之前写的程序，过几天就会觉得理解不是很顺畅，需要加适当注释。

4.本程序中有几个函数是通过网络借鉴而掌握并使用的，这几个函数在一定程度上简化了程序的复杂度，节省了大量时间。在编程过程中，我的学习能力也获得了提高。

5.由数据测试部分可得出，本压缩程序不仅可以压缩文本文件，也不仅仅能处理半角字符，适用范围较广。