2022年Huffman压缩试验报告_共12页

1、数据结构与算法实验与课程设计精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 1 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告1目录一问题描述 .1二基本要求 .1三工具 / 准备工作 .2四分析与实现 .21概要分析 .22算法详细分析 .3（1）构造 hufffman 树的方法 huffman 算法 .3（2）压缩过程的实现.4（3）解压过程类似压缩过程的实现.5

2、（4）输出部分 .5（5）main 函数部分 .53代码实现 .6huffman 树结点的抽象基类模板.6huffman 树叶子节点派生类模板.7huffman 内部结点派生类模板.7huffman 树类模板 .8huffman 压缩类 .94源程序 .10系统中主要函数模板代码实现：.105调试分析与结果.18五总结 .22精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 2 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 2 页，共 25 页 - - -

3、 - - - - - -huffman 压缩软件实验报告2一问题描述用 huffman 编码设计一个压缩软件，要求能对输入的任何类型的文件进行 huffman 编码，产生编码后的文件 压缩文件；也能对输入的压缩文件进行译码，生成压缩前的文件解压文件。二基本要求1、初始化：能够对输入的任意长度的字符串s 进行统计，统计每个字符的频度，并建立huffman 树。2、建立编码表：利用已经建好的huffman 树进行编码。3、编码 (encoding) ：根据编码表对输入的字符串进行编码，并将编码后的字符串输出。4、译码 (decoding) ：利用已经建好的huffman 树对编码后的字符串进行译码

4、，并输出译码结果。5、要求编码 / 译码的效率尽可能的高。6、用户界面可以设计为 “菜单”方式：能够进行交互。三工具 / 准备工作在开始做实验之前，应回顾或复习c+相关内容。需要一台计算机，其中安装有vc6.0、vc+ 2005、vc+ 2005 express、dev-c+ 或 mingw developer studio等集成开发环境软件。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 3 页，共 2

5、5 页 - - - - - - - - -huffman 压缩软件实验报告3四分析与实现1概要分析本次实验采用将字符用长度尽可能短的二进制数位表示的方法，即对于文件中出现的字符，无须全部都用8 位的 ascii 码进行存储，根据他们在文件中出现的频率不同，我们利用huffman 算法使每个字符能以最短的二进制字符进行存储，以达到节省存储空间，压缩文件的目的。解决了压缩需采用的算法，程序的思路已然清晰：1统计需压缩文件中每个字符出现的频率。2将每个字符的出现频率作为叶子结点构建huffman 树，然后将树中结点引向其左孩子的分支标“0” ，引向其右孩子的分支标“1” ；每个字符的编码即为从根到每

6、个叶子的路径上得到的0、1 序列，这样便完成了huffman 编码，将每个字符用最短的二进制字符表示。3打开需压缩文件，再将需压缩文件中的每个ascii 码对应的huffman 编码按 bit单位输出。4文件压缩结束。5打开需要解压的文件，读取压缩文件中的数据，生成解码信息，输出到文件。6文件解压结束。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 4 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 4 页，共 25 页 - - - - - - - - -

7、huffman 压缩软件实验报告42算法详细分析（1）构造 hufffman 树的方法 huffman算法i.根据给定的 n 个权值w1,w2, ?wn，构造 n 棵只有根结点的二叉树，令起权值为wj。ii.在森林中选取两棵根结点权值最小的树作左右子树，构造一棵新的二叉树，置新二叉树根结点权值为其左右子树根结点权值之和。iii.在森林中删除这两棵树，同时将新得到的二叉树加入森林中。iv.重复上述两步，直到只含一棵树为止，这棵树即哈夫曼树。对于 huffman 的创建算法，有以下几点说明：a) 这里的 huffman 树采用的是基于数组的带左右儿子结点及父结点下标作为存储结点的二叉树形式，这种空

8、间上的消耗带来了算法实现上的便捷。b)将各个字符的编码存储在一个数组charcodes 中，为了能快速找到一个字符的编码，用函数（*charindex ）来实现字符位置的映射，使用先序遍历二叉树的方法来求各个字符的编码方案。c）采用小顶堆的方式来存储各个二叉树的根，实际是存储指向根结点的指针。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 5 页，共 25 页 - - - - - - - - -huffm

9、an 压缩软件实验报告5（2）压缩过程的实现压缩过程的流程是清晰而简单的：1 创建 huffman 树2打开需压缩文件3 将需压缩文件中的每个 ascii 码对应的 huffman 编码按 bit单位输出4 文件压缩结束。其中，步骤 1 和步骤 3 是压缩过程的关键。a) 步骤 1: 这里所要做工作是得到huffman 数中各叶子结点字符出现的频率并进行创建。b) 步骤 3:将需压缩文件中的每个ascii 码对应的 huffman 编码按 bit 单位输出，这是本压缩程序中最关键的部分。需定义一个字符缓存器 buffertype ，以便自动将比特转化为字节。struct buffertypec

10、har ch; unsigned int bits;（3）解压过程类似压缩过程的实现（4）输出部分1)每个字符所对应的 huffmancode 的比特位长度不等长，不可少输，多输，输错任何一位，后一个字符的huffmancode 要紧跟在前一个字符的huffmancode 后面。精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 6 页，共 25 页 - - - - - - - - -huffman 压缩软件

11、实验报告6 2)最后一个要输出的 huffmancode 的最后一位，它恰好是位于最后一个有效字符的第一位，剩下的七个空位是要用无效的huffmancode 加以填充。否则，如果填充的huffmancode 亦为某个ascii 字符的 huffmancode 时，那么在解压缩时，则该在原被压缩文件中不存在的字符便会无中生有的在解压后的文件中出现，这显然是不正确的，应在程序中加以处理。（5）main 函数部分 n y n y开始是否成功输入要打开文件名称是否找到文件将文件中的值作为叶子结点构建 huffman 树实现huffman 编码输出字符到压缩 / 解压文件文件压缩 /解压结束，关闭打开的

12、文件返回精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 7 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告73代码实现huffman 树结点的抽象基类模板类型成员功能virtual weighttype weight()=0返回权值virtual bool isleaf()=0判断结点是否为叶子节点virtual myhuffmannode* left()=0返回结点

13、的左孩子函数模板virtual myhuffmannode* right()=0返回结点的右孩子virtual void setleft(myhuffmannode*child)=0设置结点的左孩子virtual void setright(myhuffmannode*child)=0设置结点的右孩子huffman 树叶子节点派生类模板类型成员功能chartype ch结点内容数据成员weighttype weight结点权值myleafnode(const chartype &ch, const weighttype &w)构造函数精品学习资料 可选择p d f - - -

14、- - - - - - - - - - - 第 8 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 8 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告8virtualmyleafnode()析构函数chartype char()httype*child)=0返回叶子节点的字符函数模板weighttype weight()返回权值bool isleaf()判断结点是否为叶子节点myhuffmannode* left()、myhuffmannode* right()

15、返回结点的左右孩子void setleft(myhuffmannode*child)、void setright(myhuffmannode*child)设置结点的左右孩子huffman 内部结点派生类模板类型成员功能myhuffmannode *lchild、myhuffmannode *rchild结点的左右孩子数据成员weighttype weight结点权值mynode(myhuffmannode *l, myhuffmannode *r,const weighttype &w)通过左右孩子以及权值构造huffman 树内部结点virtualmynode()析构函数函数weig

16、httype weight()返回权值精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 9 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 9 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告9模板bool isleaf()判断结点是否为叶子节点myhuffmannode* left()、myhuffmannode* right()返回结点的左右孩子void setleft(myhuffmannode*child)、voi

17、d setright(myhuffmannode*child)设置结点的左右孩子huffman 树类模板类型成员功能myhuffmannode* root根结点数据成员string * charcodes字符编码信息myhuffmannode* curcode指向当前结点int num 叶子结点的个数函数模板unsigned int(* charindex)(const chartype &)字符位置映射void creatcode(myhuffmannode *r,char code,int len=0)生成字符编码void clear(myhuffmannode *r)清空树精品学

18、习资料 可选择p d f - - - - - - - - - - - - - - 第 10 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 10 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告10myhuffmantree(chartype ch,weighttype w,int n,unsigned int (*chindex)(const chartype&)构造函数virtualmyhuffmantree()析构函数string encode(ch

19、artype ch)编码linklistdecode(string strcode)解码huffman 压缩类类型成员功能myhuffmantree * pmyhuffmantreehuffman 树数据成员ifstream infp、ofstream outfp输入输出文件流buffertype buf字符缓存器void write(unsigned int bit)向文件中写入信息函数模板void writetooutfp()强制向文件写入信息myhuffmancompress()构造函数myhuffmancompress()析构函数void compress()压缩void decomp

20、ress()解压说明：在小顶堆的实现中要求各元素的大小，因为应重载关系运算符，然而重载运算符的操作数应包含非基本类型，不能全部是指针类型，为此定义一个辅助类结构模板如下：精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 11 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 11 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告11templatestruct myhuffmannodehelpmyhuffmannode*

21、ptr;4源程序系统中主要函数模板代码实现：/ 生成字符编码templatevoid myhuffmantree:creatcode(myhuffmannode *r,char code,int len)if (r = null) return;if(r-isleaf()/如果是叶子节点，则存储编码chartype ch= (myleafnode *)r)-char();codelen=0;string strcode(code);charcodes(*charindex)(ch) = strcode;else/否则分别向左右两边搜索codelen = 0;creatcode(r-left()

22、,code,len+1);/向左分支搜索codelen = 1;creatcode(r-right(),code,len+1);/ 向右分支搜索/ 构造 huffman 树template精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 12 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 12 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告12myhuffmantree:myhuffmantree(chartype c

23、h,weighttype w,int n,unsigned int (*chindex)(const chartype&)charindex = chindex;/ 字符位置映射num=n;charcodes = new stringnum;minpriorityheapqueuemyhuffmannodehelp minheap;/小顶堆int i;for(i=0;inum;i+)myhuffmannodehelp tmp;tmp.ptr = new myleafnode(chi,wi);/生成叶子结点minheap.inqueue(tmp);/入栈for(i=0;inum-1;i+

24、)myhuffmannodehelp t,t1,t2;minheap.outqueue(t1);/出栈minheap.outqueue(t2);/出栈/ 生成新的结点t.ptr = new mynode(t1.ptr,t2.ptr,t1.ptr-weight()+t2.ptr-weight();minheap.inqueue(t);/新的结点入栈myhuffmannodehelp r;minheap.outqueue(r);root=r.ptr;/ 根结点curcode=root;char *code = new charnum;creatcode(root, code);/生成编码delet

25、e code;精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 13 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 13 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告13/ 编码templatestring myhuffmantree:encode(chartype ch)return charcodes(unsigned int)(*charindex)(ch);/ 译码templatelinklist myhuf

26、fmantree:decode(string strcode)linklistcharlist;for(int pos = 0;posleft();/如果为 0 则向左分支搜索elsecurcode=curcode-right();/ 否则向右分支搜索/ 如果到达叶子结点则说明译码完成，记录译码结果if(curcode-isleaf()charlist.insert(charlist.length()+1,(myleafnode*)curcode)-char();curcode = root;return charlist;/ 向目标文件写入一个比特void myhuffmancompress

27、:write(unsigned int bit)buf.bits+;/ 缓存比特数自增1buf.ch=(buf.ch0)for(unsigned int i = 0 ; i8-len;i+)write(0);/ 压缩文件void myhuffmancompress:compress()char infname256,outfname256;/ 文件名l1: cout 请输入需要压缩的文件名 :;cininfname;infp.open(infname,ios:out);/ 打开目标文件if(!infp)/ 打开文件失败cout 打开文件失败 !endl;goto l1;infp.get();i

28、f(infp.eof()/ 如果文件为空则提示用户cout 文件为空 !endl;goto l1;l2: cout 请设置压缩后的文件名称 :;cinoutfname;/ 压缩目标文件outfp.open(outfname,ios:in);精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 15 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 15 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告15if(!outfp)/

29、打开文件失败cout打开文件失败 !endl;goto l2;cout 正在处理，请稍后 .endl;const unsigned long n = 256;/字符个数char chn;/ 字符数组unsigned long wn;/ 字符权值unsigned long i,size = 0;char tmpch;for(i = 0;in;i+)chi = (char)i;/初始化字符值wi = 0;/ 初始化权值infp.seekg(0,ios:beg);/使文件指针指向文件开始处tmpch = infp.get();/从文件中读取一个字符while(!infp.eof()w(unsigne

30、d int)(unsigned char)tmpch)+;/字符 tmpch 的频度自加一size+;/文件大小加一tmpch = infp.get();/读取下一个字符infp.close();/ 关闭文件if(pmyhuffmantree!=null)delete pmyhuffmantree;pmyhuffmantree =new myhuffmantree(ch,w,n,charindex);outfp.write(char *)&size,sizeof(unsigned long);/ 向文件中写入源文件的大小for(i = 0;iencode(tmpch);/ 编码信息fo

31、r( i =0; i(unsigned int )strtmp.length();i+)/ 向文件中写入信息if(strtmpi=0)write(0);elsewrite(1);tmpch = infp.get();writetooutfp();/ 强行写入目标文件infp.close();outfp.close();cout 压缩结束 .endl;/ 解压文件void myhuffmancompress:decompress()char infname256,outfname256;/ 文件名l1: cout 请输入压缩文件名 :;cininfname;infp.open(infname,i

32、os:out);/ 打开文件if(!infp)/ 打开文件失败cout 打开压缩文件失败 !endl;goto l1;infp.get();if(infp.eof()cout 压缩文件为空 !endl;精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 17 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 17 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告17goto l1;l2: cout 请设置解压后文件的名称 :;

33、cinoutfname;outfp.open(outfname,ios:in);/ 打开文件if(!outfp)cout 打开文件失败 !endl;goto l2;cout 正在处理，请稍后 .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;in;i+)

34、chi = (char)i;/初始化 chinfp.read(char *)&wi,sizeof(unsigned long);/ 读取字符频度if(pmyhuffmantree=null)delete pmyhuffmantree;pmyhuffmantree =new myhuffmantree(ch,w,n,charindex);/建立 huffman 树unsigned long len = 0;tmpch = infp.get();while(!infp.eof()/ 对压缩文件进行解码，并将解码后的字符写入目标文件string strtmp=;unsigned char c

35、=(unsigned char)tmpch;for(i = 0;i8;i+)/ 将 c 转换成二进制类型的串if(c128) concat(strtmp,0);精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 18 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 18 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告18else concat(strtmp,1);c=1;linklist text=pmyhuffmantr

36、ee-decode(strtmp);/ 对串进行译码string str(text);for(i = 0;i(unsigned long)str.length();i+)len+;/目标文件长度加一outfp.put(stri);/ 写入目标文件if(len=size) break;if(len=size) break;tmpch = infp.get();/取出下一个字符infp.close();/ 关闭文件outfp.close();cout 处理结束 .endl;/ 主测试函数int main( int argc, char *argv )system(color f3);char fl

37、ag;/ 欢迎界面couttt endl;couttt huffman 压缩endl;couttt endl;couttt (a)添加压缩文件endl;couttt endl;couttt (b)解压文件endl;couttt endl;精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 19 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 19 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告19couttt (c)退出e

38、ndl;couttt endl;while(cinflag)switch(flag)case a:myhuffmancompress compress;compress.compress();/ 压缩break;case b:myhuffmancompress compress;compress.decompress();/解压break;case c:cout;system(pause);return 0;cout;return 0;5调试分析与结果测试数据：i love computer。i will try my best to study it.程序运行的界面如下，通过用户输入指令运行

39、。可用的指令有如下几条：选项 a：添加压缩文件精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 20 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 20 页，共 25 页 - - - - - - - - -huffman 压缩软件实验报告20选项 b：解压文件选项 c：退出程序添加压缩文件：精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 21 页，共 25 页 - - - - - - - - -精品学习资料 可选择p d f - - - - - - - - - - - - - - 第 21 页，共 25 页 -