Huffman压缩试验报告

数据结构与算法实验与课程设计《Huffman压缩软件实验报告》1目录一．问题描述.........................................................................................2二．基本要求.........................................................................................2三．工具/准备工作...............................................................................2四．分析与实现.....................................................................................31．概要分析.....................................................................................32．算法详细分析.............................................................................4（1）构造Hufffman树的方法—Huffman算法.........................4（2）压缩过程的实现................................................................5（3）解压过程类似压缩过程的实现.........................................5（4）输出部分............................................................................5（5）main函数部分..................................................................63．代码实现.....................................................................................7Huffman树结点的抽象基类模板...............................................7Huffman树叶子节点派生类模板...............................................7Huffman内部结点派生类模板...................................................8Huffman树类模板.......................................................................9Huffman压缩类........................................................................104．源程序.......................................................................................11系统中主要函数模板代码实现：............................................115．调试分析与结果........................................................................19五．总结...............................................................................................23《Huffman压缩软件实验报告》2一．问题描述用Huffman编码设计一个压缩软件，要求能对输入的任何类型的文件进行Huffman编码，产生编码后的文件——压缩文件；也能对输入的压缩文件进行译码，生成压缩前的文件——解压文件。二．基本要求1、初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立Huffman树。2、建立编码表：利用已经建好的Huffman树进行编码。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的Huffman树对编码后的字符串进行译码，并输出译码结果。5、要求编码/译码的效率尽可能的高。6、用户界面可以设计为“菜单”方式：能够进行交互。三．工具/准备工作在开始做实验之前，应回顾或复习c++相关内容。需要一台计算机，其中安装有VC6.0、VC++2005、VC++2005Express、DEV-C++或MinGWDeveloperStudio等集成开发环境软件。《Huffman压缩软件实验报告》3四．分析与实现1．概要分析本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用8位的ASCII码进行存储，根据他们在文件中出现的频率不同，我们利用Huffman算法使每个字符能以最短的二进制字符进行存储，以达到节省存储空间，压缩文件的目的。解决了压缩需采用的算法，程序的思路已然清晰：1．统计需压缩文件中每个字符出现的频率。2．将每个字符的出现频率作为叶子结点构建Huffman树，然后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列，这样便完成了Huffman编码，将每个字符用最短的二进制字符表示。3．打开需压缩文件，再将需压缩文件中的每个ASCII码对应的Huffman编码按bit单位输出。4．文件压缩结束。5．打开需要解压的文件，读取压缩文件中的数据，生成解码信息，输出到文件。6．文件解压结束。《Huffman压缩软件实验报告》42．算法详细分析（1）构造Hufffman树的方法—Huffman算法I.根据给定的n个权值{w1,w2,⋯⋯wn}，构造n棵只有根结点的二叉树，令起权值为wj。II.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。III.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。对于Huffman的创建算法，有以下几点说明：a)这里的Huffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。b)将各个字符的编码存储在一个数组charCodes中，为了能快速找到一个字符的编码，用函数（*CharIndex）来实现字符位置的映射，使用先序遍历二叉树的方法来求各个字符的编码方案。c）采用小顶堆的方式来存储各个二叉树的根，实际是存储指向根结点的指针。《Huffman压缩软件实验报告》5（2）压缩过程的实现压缩过程的流程是清晰而简单的：1创建Huffman树→2打开需压缩文件→3将需压缩文件中的每个ASCII码对应的Huffman编码按bit单位输出→4文件压缩结束。其中，步骤1和步骤3是压缩过程的关键。a)步骤1:这里所要做工作是得到Huffman数中各叶子结点字符出现的频率并进行创建。b)步骤3:将需压缩文件中的每个ASCII码对应的Huffman编码按bit单位输出，这是本压缩程序中最关键的部分。需定义一个字符缓存器BufferType，以便自动将比特转化为字节。structBufferType{charch;unsignedintbits;};（3）解压过程类似压缩过程的实现（4）输出部分1)每个字符所对应的HuffmanCode的比特位长度不等长，不可少输，多输，输错任何一位，后一个字符的HuffmanCode要紧跟在前一个字符的HuffmanCode后面。2)最后一个要输出的HuffmanCode的最后一位，它恰好是位于最后一个有效字符的第一位，剩下的七个空位是要用无效的HuffmanCode加以填充。否则，如果填充的HuffmanCode亦为某个ascii字符的《Huffman压缩软件实验报告》6HuffmanCode时，那么在解压缩时，则该在原被压缩文件中不存在的字符便会无中生有的在解压后的文件中出现，这显然是不正确的，应在程序中加以处理。（5）main函数部分NYNY开始是否成功输入要打开文件名称是否找到文件将文件中的值作为叶子结点构建Huffman树实现Huffman编码输出字符到压缩/解压文件文件压缩/解压结束，关闭打开的文件返回《Huffman压缩软件实验报告》73．代码实现Huffman树结点的抽象基类模板类型成员功能virtualWeightTypeWeight()=0返回权值virtualboolIsLeaf()=0判断结点是否为叶子节点virtualMyHuffmanNodeCharType,WeightType*Left()=0返回结点的左孩子函数模板virtualMyHuffmanNodeCharType,WeightType*Right()=0返回结点的右孩子virtualvoidSetLeft(MyHuffmanNodeCharType,WeightType*child)=0设置结点的左孩子virtualvoidSetRight(MyHuffmanNodeCharType,WeightType*child)=0设置结点的右孩子Huffman树叶子节点派生类模板类型成员功能CharTypech结点内容数据成员WeightTypeweight结点权值MyLeafNode(constCharType&ch,constWeightType&w)构造函数virtual~MyLeafNode(){}析构函数CharTypeChar()htType*child)=0返回叶子节点的字符《Huffman压缩软件实验报告》8函数模板WeightTypeWeight()返回权值boolIsLeaf()判断结点是否为叶子节点MyHuffmanNodeCharType,WeightType*Left()、MyHuffmanNodeCharType,WeightType*Right()返回结点的左右孩子voidSetLeft(MyHuffmanNodeCharType,WeightType*child)、voidSetRight(MyHuffmanNodeCharType,WeightType*child)设置结点的左右孩子Huffman内部结点派生类模板类型成员功能MyHuffmanNodeCharType,WeightType*lChild、MyHuffmanNodeCharType,WeightType*rChild结点的左右孩子数据成员WeightTypeweight结点权值MyNode(MyHuffmanNodeCharType,WeightType*l,MyHuffmanNodeCharType,WeightType*r,constWeightType&w)通过左右孩子以及权值构造Huffman树内部结点virtual~MyNode(){}析构函数函数模板WeightTypeWeight()返回权值《Huffman压缩软件实验报告》9boolIsLeaf()判断结点是否为叶子节点MyHuffmanNodeCharType,WeightType*Left()、MyHuffmanNodeCharType,Weigh