Huffman压缩试验报告

1、Huffman压缩软件实验报告数据结构与算法实验与课程设计目录一问题描述1二基本要求1三工具/准备工作2四分析与实现21概要分析22算法详细分析3（1）构造Hufffman树的方法Huffman算法3（2）压缩过程的实现4（3）解压过程类似压缩过程的实现5（4）输出部分5（5）main 函数部分53代码实现6Huffman树结点的抽象基类模板6Huffman树叶子节点派生类模板7Huffman内部结点派生类模板7Huffman树类模板8Huffman压缩类94源程序10系统中主要函数模板代码实现：105调试分析与结果18五总结22一问题描述用Huffman编码设计一个压缩软件，要求能对输入的任

2、何类型的文件进行Huffman编码，产生编码后的文件压缩文件；也能对输入的压缩文件进行译码，生成压缩前的文件解压文件。二基本要求1、初始化：能够对输入的任意长度的字符串s进行统计，统计每个字符的频度，并建立Huffman树。2、建立编码表：利用已经建好的Huffman树进行编码。3、编码(Encoding)：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码(Decoding)：利用已经建好的Huffman树对编码后的字符串进行译码，并输出译码结果。5、要求编码/译码的效率尽可能的高。6、用户界面可以设计为“菜单”方式：能够进行交互。三工具/准备工作在开始做实验之前，应回顾或复

3、习c+相关内容。需要一台计算机，其中安装有VC6.0、VC+ 2005、VC+ 2005 Express、DEV-C+或MinGW Developer Studio等集成开发环境软件。四分析与实现1概要分析本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用8位的ASCII码进行存储，根据他们在文件中出现的频率不同，我们利用Huffman算法使每个字符能以最短的二进制字符进行存储，以达到节省存储空间，压缩文件的目的。解决了压缩需采用的算法，程序的思路已然清晰：1统计需压缩文件中每个字符出现的频率。2将每个字符的出现频率作为叶子结点构建Huffman树，然

4、后将树中结点引向其左孩子的分支标“0”，引向其右孩子的分支标“1”；每个字符的编码即为从根到每个叶子的路径上得到的0、1序列，这样便完成了Huffman编码，将每个字符用最短的二进制字符表示。3打开需压缩文件，再将需压缩文件中的每个ASCII码对应的Huffman编码按bit单位输出。4文件压缩结束。5打开需要解压的文件，读取压缩文件中的数据，生成解码信息，输出到文件。6文件解压结束。2算法详细分析（1）构造Hufffman树的方法Huffman算法I. 根据给定的n个权值w1,w2,wn，构造n棵只有根结点的二叉树，令起权值为wj。II. 在森林中选取两棵根结点权值最小的树作左右子树，构造一

5、棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。III. 在森林中删除这两棵树，同时将新得到的二叉树加入森林中。IV. 重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。对于Huffman的创建算法，有以下几点说明：a) 这里的Huffman树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空间上的消耗带来了算法实现上的便捷。b)将各个字符的编码存储在一个数组charCodes中，为了能快速找到一个字符的编码，用函数（*CharIndex）来实现字符位置的映射，使用先序遍历二叉树的方法来求各个字符的编码方案。c）采用小顶堆的方式来存储各个二叉树的根，实

6、际是存储指向根结点的指针。（2）压缩过程的实现压缩过程的流程是清晰而简单的：1创建Huffman树2打开需压缩文件3将需压缩文件中的每个ASCII码对应的Huffman编码按bit单位输出4文件压缩结束。其中，步骤1和步骤3是压缩过程的关键。a) 步骤1:这里所要做工作是得到Huffman数中各叶子结点字符出现的频率并进行创建。b) 步骤3: 将需压缩文件中的每个ASCII码对应的Huffman编码按bit单位输出，这是本压缩程序中最关键的部分。需定义一个字符缓存器BufferType，以便自动将比特转化为字节。struct BufferTypechar ch; unsigned int bi

7、ts;（3）解压过程类似压缩过程的实现（4）输出部分1)每个字符所对应的HuffmanCode的比特位长度不等长，不可少输，多输，输错任何一位，后一个字符的HuffmanCode要紧跟在前一个字符的HuffmanCode后面。 2)最后一个要输出的HuffmanCode的最后一位，它恰好是位于最后一个有效字符的第一位，剩下的七个空位是要用无效的HuffmanCode加以填充。否则，如果填充的HuffmanCode亦为某个ascii字符的HuffmanCode时，那么在解压缩时，则该在原被压缩文件中不存在的字符便会无中生有的在解压后的文件中出现，这显然是不正确的，应在程序中加以处理。开始是否成功

8、输入要打开文件名称是否找到文件将文件中的值作为叶子结点构建 Huffman树实现 Huffman编码输出字符到压缩/解压文件文件压缩/解压结束，关闭打开的文件返回（5）main 函数部分 N Y N Y3代码实现Huffman树结点的抽象基类模板类型成员功能virtual WeightType Weight()=0返回权值virtual bool IsLeaf()=0判断结点是否为叶子节点virtual MyHuffmanNode<CharType,WeightType>* Left()=0返回结点的左孩子函数模板virtual MyHuffmanNode<CharType,

9、WeightType>* Right()=0返回结点的右孩子virtual void SetLeft(MyHuffmanNode<CharType,WeightType>*child)=0设置结点的左孩子virtual void SetRight(MyHuffmanNode<CharType,WeightType>*child)=0设置结点的右孩子Huffman树叶子节点派生类模板类型成员功能CharType ch结点内容数据成员WeightType weight结点权值MyLeafNode(const CharType &ch, const Weight

10、Type &w)构造函数virtualMyLeafNode()析构函数CharType Char()htType>*child)=0返回叶子节点的字符函数模板WeightType Weight()返回权值bool IsLeaf()判断结点是否为叶子节点MyHuffmanNode<CharType,WeightType>* Left()、MyHuffmanNode<CharType,WeightType>* Right()返回结点的左右孩子void SetLeft(MyHuffmanNode<CharType,WeightType>*child)

11、、void SetRight(MyHuffmanNode<CharType,WeightType>*child)设置结点的左右孩子Huffman内部结点派生类模板类型成员功能MyHuffmanNode<CharType,WeightType> *lChild、MyHuffmanNode<CharType,WeightType> *rChild结点的左右孩子数据成员WeightType weight结点权值MyNode(MyHuffmanNode<CharType,WeightType> *l, MyHuffmanNode<CharType,

12、WeightType> *r,const WeightType &w)通过左右孩子以及权值构造Huffman树内部结点virtualMyNode()析构函数函数模板WeightType Weight()返回权值bool IsLeaf()判断结点是否为叶子节点MyHuffmanNode<CharType,WeightType>* Left()、MyHuffmanNode<CharType,WeightType>* Right()返回结点的左右孩子void SetLeft(MyHuffmanNode<CharType,WeightType>*chi

13、ld)、void SetRight(MyHuffmanNode<CharType,WeightType>*child)设置结点的左右孩子Huffman树类模板类型成员功能MyHuffmanNode<CharType,WeightType>* root根结点数据成员String * charCodes字符编码信息MyHuffmanNode<CharType,WeightType>* curCode指向当前结点int num 叶子结点的个数函数模板unsigned int(* CharIndex)(const CharType &)字符位置映射void

14、CreatCode(MyHuffmanNode<CharType,WeightType> *r,char code,int len=0)生成字符编码void Clear(MyHuffmanNode<CharType,WeightType> *r)清空树MyHuffmanTree(CharType ch,WeightType w,int n,unsigned int (*ChIndex)(const CharType&)构造函数virtualMyHuffmanTree()析构函数String Encode(CharType ch)编码LinkList<Cha

15、rType>Decode(String strCode)解码Huffman压缩类类型成员功能MyHuffmanTree<char,unsigned long> * pMyHuffmanTreeHuffman树数据成员ifstream infp、ofstream outfp输入输出文件流BufferType buf字符缓存器void Write(unsigned int bit)向文件中写入信息函数模板void WriteToOutfp()强制向文件写入信息MyHuffmanCompress()构造函数MyHuffmanCompress()析构函数void Compress()

16、压缩void Decompress()解压说明：在小顶堆的实现中要求各元素的大小，因为应重载关系运算符，然而重载运算符的操作数应包含非基本类型，不能全部是指针类型，为此定义一个辅助类结构模板如下：template<class CharType, class WeightType>struct MyHuffmanNodeHelpMyHuffmanNode<CharType,WeightType>* ptr;4源程序系统中主要函数模板代码实现：/生成字符编码template<class CharType, class WeightType>void MyHuff

17、manTree<CharType,WeightType>:CreatCode(MyHuffmanNode<CharType,WeightType> *r,char code,int len)if (r = NULL) return;if(r->IsLeaf()/如果是叶子节点，则存储编码CharType ch= (MyLeafNode<CharType,WeightType> *)r)->Char();codelen='0'String strCode(code);charCodes(*CharIndex)(ch) = strCo

18、de;else/否则分别向左右两边搜索codelen = '0'CreatCode(r->Left(),code,len+1);/向左分支搜索codelen = '1'CreatCode(r->Right(),code,len+1);/向右分支搜索/构造Huffman树template<class CharType, class WeightType>MyHuffmanTree<CharType,WeightType>:MyHuffmanTree(CharType ch,WeightType w,int n,unsigned

19、int (*ChIndex)(const CharType&)CharIndex = ChIndex;/字符位置映射num=n;charCodes = new Stringnum;MinPriorityHeapQueue<MyHuffmanNodeHelp<CharType,WeightType> > minHeap;/小顶堆int i;for(i=0;i<num;i+)MyHuffmanNodeHelp<CharType,WeightType> tmp;tmp.ptr = new MyLeafNode<CharType,WeightTy

20、pe>(chi,wi);/生成叶子结点minHeap.InQueue(tmp);/入栈for(i=0;i<num-1;i+)MyHuffmanNodeHelp<CharType,WeightType> t,t1,t2;minHeap.OutQueue(t1);/出栈minHeap.OutQueue(t2);/出栈/生成新的结点t.ptr = new MyNode<CharType,WeightType>(t1.ptr,t2.ptr,t1.ptr->Weight()+t2.ptr->Weight();minHeap.InQueue(t);/新的结点

21、入栈MyHuffmanNodeHelp<CharType,WeightType> r;minHeap.OutQueue(r);root=r.ptr;/根结点curCode=root;char *code = new charnum;CreatCode(root, code);/生成编码delete code;/编码template<class CharType, class WeightType>String MyHuffmanTree<CharType,WeightType>:Encode(CharType ch)return charCodes(unsi

22、gned int)(*CharIndex)(ch);/译码template<class CharType, class WeightType>LinkList<CharType> MyHuffmanTree<CharType,WeightType>:Decode(String strCode)LinkList<CharType>charList;for(int pos = 0;pos<strCode.Length();pos+)if(strCodepos='0')curCode=curCode->Left();/如果为

23、0则向左分支搜索elsecurCode=curCode->Right();/否则向右分支搜索/如果到达叶子结点则说明译码完成，记录译码结果if(curCode->IsLeaf()charList.Insert(charList.Length()+1,(MyLeafNode<CharType,WeightType>*)curCode)->Char();curCode = root;return charList;/向目标文件写入一个比特void MyHuffmanCompress:Write(unsigned int bit)buf.bits+;/缓存比特数自增1b

24、uf.ch=(buf.ch<<1)|bit;/将比特加入到缓存字符中if(buf.bits=8)/缓存区已满，写入目标文件outfp.put(buf.ch);/写入目标文件buf.bits=0;/初始化比特buf.ch=0;/初始化ch/强行将字符缓存写入目标文件void MyHuffmanCompress:WriteToOutfp()unsigned int len = buf.bits;if(len>0)for(unsigned int i = 0 ; i<8-len;i+)Write(0);/压缩文件void MyHuffmanCompress:Compress(

25、)char infName256,outfName256;/文件名L1:cout<<"tt>>请输入需要压缩的文件名:"cin>>infName;infp.open(infName,ios:out);/打开目标文件if(!infp)/打开文件失败cout<<"tt>>打开文件失败!"<<endl;goto L1;infp.get();if(infp.eof()/如果文件为空则提示用户cout<<"tt>>文件为空!"<<endl

26、;goto L1;L2:cout<<"tt>>请设置压缩后的文件名称:"cin>>outfName;/压缩目标文件outfp.open(outfName,ios:in);if(!outfp)/打开文件失败cout<<">>打开文件失败!"<<endl;goto L2;cout<<"tt>>正在处理，请稍后."<<endl;const unsigned long n = 256;/字符个数char chn;/字符数组unsigne

27、d long wn;/字符权值unsigned long i,size = 0;char tmpCh;for(i = 0;i<n;i+)chi = (char)i;/初始化字符值wi = 0;/初始化权值infp.seekg(0,ios:beg);/使文件指针指向文件开始处tmpCh = infp.get();/从文件中读取一个字符while(!infp.eof()w(unsigned int)(unsigned char)tmpCh)+;/字符tmpCh的频度自加一size+;/文件大小加一tmpCh = infp.get();/读取下一个字符infp.close();/关闭文件if(

28、pMyHuffmanTree!=NULL)delete pMyHuffmanTree;pMyHuffmanTree =new MyHuffmanTree<char,unsigned long>(ch,w,n,CharIndex);outfp.write(char *)&size,sizeof(unsigned long);/向文件中写入源文件的大小for(i = 0;i<n;i+)/向文件中写入字符出现的频度outfp.write(char *)(&wi),sizeof(unsigned long);buf.bits = 0;buf.ch = 0;infp.o

29、pen(infName,ios:out);infp.seekg(0,ios:beg);/使文件指向开始处tmpCh = infp.get();while(!infp.eof()String strTmp = pMyHuffmanTree->Encode(tmpCh);/编码信息for( i =0; i<(unsigned int )strTmp.Length();i+)/向文件中写入信息if(strTmpi='0')Write(0);elseWrite(1);tmpCh = infp.get();WriteToOutfp();/强行写入目标文件infp.close(

30、);outfp.close();cout<<"tt>>压缩结束."<<endl;/解压文件void MyHuffmanCompress:Decompress()char infName256,outfName256;/文件名L1:cout<<"tt>>请输入压缩文件名:"cin>>infName;infp.open(infName,ios:out);/打开文件if(!infp)/打开文件失败cout<<"tt>>打开压缩文件失败!"<

31、<endl;goto L1;infp.get();if(infp.eof()cout<<"tt>>压缩文件为空!"<<endl;goto L1;L2:cout<<"tt>>请设置解压后文件的名称:"cin>>outfName;outfp.open(outfName,ios:in);/打开文件if(!outfp)cout<<"tt>>打开文件失败!"<<endl;goto L2;cout<<"tt>

32、;>正在处理，请稍后."<<endl;const unsigned long n = 256;char chn;unsigned long wn;unsigned long i,size = 0;char tmpCh;infp.seekg(0,ios:beg);/使文件指针指向文件开始处infp.read(char *)&size,sizeof(unsigned long);/读取目标文件大小for(i =0;i<n;i+)chi = (char)i;/初始化chinfp.read(char *)&wi,sizeof(unsigned long

33、);/读取字符频度if(pMyHuffmanTree=NULL)delete pMyHuffmanTree;pMyHuffmanTree =new MyHuffmanTree<char,unsigned long>(ch,w,n,CharIndex);/建立Huffman树unsigned long len = 0;tmpCh = infp.get();while(!infp.eof()/对压缩文件进行解码，并将解码后的字符写入目标文件String strTmp=""unsigned char c=(unsigned char)tmpCh;for(i = 0;i

34、<8;i+)/将c转换成二进制类型的串if(c<128) Concat(strTmp,"0");else Concat(strTmp,"1");c<<=1;LinkList<char> Text=pMyHuffmanTree->Decode(strTmp);/对串进行译码String str(Text);for(i = 0;i<(unsigned long)str.Length();i+)len+;/目标文件长度加一outfp.put(stri);/写入目标文件if(len=size) break;if(l

35、en=size) break;tmpCh = infp.get();/取出下一个字符infp.close();/关闭文件outfp.close();cout<<"tt>>处理结束."<<endl;/主测试函数int main( int argc, char *argv )system("color F3");char flag;/欢迎界面cout<<"tt"<<endl;cout<<"tt Huffman压缩 "<<endl;cout<<"tt "<<endl;cout<<"tt(a)添加压缩文件 "<<endl;cout<<"tt "<<endl;cout<<"tt(b)解压文件 "<<endl;cout<<&q