c++哈夫曼树的文件压缩解压程序全部代码及设计报告

《c++哈夫曼树的文件压缩解压程序全部代码及设计报告》由会员分享，可在线阅读，更多相关《c++哈夫曼树的文件压缩解压程序全部代码及设计报告（44页珍藏版）》请在装配图网上搜索。

1、#include #include #include /队列容器using namespace std;const int leaf = 256;/最多可能出现的不同字符数const long MAX = 99999999;/表示无穷大typedef struct HTnodelong weight;/记录结点的权值int parent;/记录结点的双亲结点位置int lchild;/结点的左孩子int rchild;/结点的右孩子int *code;/记录该结点的huffman编码int codelen;/记录该结点huffman编码的长度HTnode()weight = MAX;paren

2、t = -1;lchild = -1;rchild = -1;codelen = 0;HTnode;class huffmanTree public:huffmanTree();virtual huffmanTree();bool count(char *input);/统计各字符出现的次数，将其写入对应结点的权值void create();/构造huffman树void code();/计算每个字符的huffman编码void addbit(int bit);/压缩时对一个未满8个bit的byte中加入一个bitvoid resetbyte();/将byte清空bool compress(c

3、har *input, char *output);/压缩函数 成功执行返回 true 失败 falsebool decompress(char *input, char *output);/解压函数 成功执行返回 true 失败 falsevoid compare(char *input, char *output);/将原文件与压缩后的文件比较private:int root;/记录根结点的位置int leafnum;/记录不同字符的个数HTnode HTleaf*2-1;/HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1char byte;/压缩

4、文件时用来缓冲bit的变量int bitsnum;/byte中bit的个数int lacknum;/压缩到最后byte中的bit不满8个时填充的0的个数;huffmanTree:huffmanTree()/初始化成员变量root = 0;leafnum = 0;byte = 0;bitsnum = 0;lacknum = 0;huffmanTree:huffmanTree()for(int i=0; ileaf; i+)if(HTi.codelen != 0)delete HTi.code;/统计各字符出现的次数bool huffmanTree:count(char *input)ifstre

5、am ifs;char c;ifs.open(input,ios:binary);if(!ifs)cout 无法打开文件 input ! endl;return false;while(ifs.get(c)if(HTc+128.weight=MAX)/若该字符是第一次出现，先初始化权值HTc+128.weight = 0;leafnum+;HTc+128.weight+;/权值+1ifs.close();return true;/选权值最小的两棵树组成新的数void huffmanTree:create()for(int i=leaf; i2*leaf-1; i+)int loc1=-1, l

6、oc2=-1;for(int j=0; ji; j+)if(HTj.parent != -1)continue;if(loc1=-1 | HTj.weight HTloc1.weight)loc2 = loc1;loc1 = j;else if(loc2=-1 | HTj.weight loc2 ? loc2 : loc1;HTi.rchild = loc1loc2 ? loc1 : loc2;HTloc1.parent = i;HTloc2.parent = i;root = i;/计算每个字符的huffman编码void huffmanTree:code()for(int i=0; i=0

7、; j-)/从后往前找，记录结点的huffman编码if(loc=HTHTloc.parent.lchild)HTi.codej = 0;elseHTi.codej = 1;loc = HTloc.parent;/压缩时对一个未满8个bit的byte中加入一个bitvoid huffmanTree:addbit(int bit)if(bit = 0)byte = byte 1;/若新增的bit为0，则直接将byte按位左移elsebyte = (byte 1) | 1);/若新增的bit为1，先将byte按位左移，再与1按位或运算bitsnum+;/将byte清空void huffmanTre

8、e:resetbyte()byte = 0;bitsnum = 0;/压缩函数 成功执行返回 true 失败 falsebool huffmanTree:compress(char *input, char *output)if( !count(input) ) return false;create();code();ifstream ifs;ofstream ofs;ifs.open(input,ios:binary);ofs.open(output,ios:binary);char c;if(!ifs)cout 无法打开文件 input ! endl;return false;if(!o

9、fs)cout 无法打开文件 output ! endl;return false;ofs.put(0);/预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384);/将根节点的位置-384写入（为使该值不超过char的最大表示范围）for(int i=0; ileaf*2-1; i+)/写入每个结点的双亲结点位置if(HTi.parent=-1)/若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)ofs.put(127);else/否则将双亲结点的位置-384再写入（为使该值不超过char的最大表示范围）ofs.put(HTi.paren

10、t-384);while(ifs.get(c)/将字符的huffman编码并加入byte中int tmp = c+128;for(int i=0; iHTtmp.codelen; i+)addbit(HTtmp.codei);if(bitsnum=8)/若byte已满8位，则输出该byte并将byte清空ofs.put(byte);resetbyte();if(bitsnum!=0)/处理最后未满8个字符的byte，用0填充并记录填充的个数for(int i=bitsnum; i8; i+)addbit(0);lacknum+;ofs.put(byte);resetbyte();ofs.see

11、kp(0,ios:beg);/将写指针移动到文件开头ofs.put(lacknum);/写入最后一个字节缺失的bit个数ifs.close();ofs.close();return true;/解压函数 成功执行返回 true 失败 falsebool huffmanTree:decompress(char *input, char *output)queue q;char c;ifstream ifs;ofstream ofs;ifs.open(input,ios:binary);ofs.open(output,ios:binary);if(!ifs)cout 无法打开文件 input !

12、endl;return true;if(!ofs)cout 无法打开文件 output ! endl;return false;ifs.get(c);lacknum = c;/读出最后一个字节缺失的bit个数ifs.get(c);root = c+384;/读出根结点的位置for(int i=0; i1)/还未到最后一个字节c = q.front();for(int i=0; i8; i+)if(int(c&128)=0)point = HTpoint.lchild;if(HTpoint.lchild=-1 & HTpoint.rchild=-1)ofs.put(char(point-128)

13、;point = root;c = c 1;elsepoint = HTpoint.rchild;if(HTpoint.lchild=-1 & HTpoint.rchild=-1)ofs.put(char(point-128);point = root;c = c 1;q.pop();c = q.front();/最后一个字节for(i=0; i8-lacknum; i+)if(int(c&128)=0)point = HTpoint.lchild;if(HTpoint.lchild=-1 & HTpoint.rchild=-1)ofs.put(char(point-128);point =

14、root;c = c 1;elsepoint = HTpoint.rchild;if(HTpoint.lchild=-1 & HTpoint.rchild=-1)ofs.put(char(point-128);point = root;c = c 1;q.pop();ifs.close();ofs.close();return true;/将原文件与压缩后的文件比较void huffmanTree:compare(char *input, char *output)ifstream origin, compress;origin.open(input,ios:binary);compress.

15、open(output,ios:binary);if(!origin)cout 无法打开文件 input ! endl;return;if(!compress)cout 无法打开文件 output ! endl;return;double total1=0, total2=0;char c;while(origin.get(c)total1+;while(compress.get(c)total2+;cout 原文件大小： total1 Byte endl;cout 压缩后大小： total2 Byte endl; cout 压缩率： total2/total1*100 % endl;orig

16、in.close();compress.close();void main()int choice = 1;char input255, output255;huffmanTree h;while(choice)cout*endl;cout* 基于哈夫曼树的文件压缩/解压程序 *endl;cout* *endl;cout* 1) 压缩 *endl;cout* *endl;cout* 2) 解压 *endl;cout* *endl;cout* 0) 退出 *endl;cout* *endl;cout* 说明：请输入相应的操作序号 *endl;cout*endl;cout choice;switc

17、h(choice)case 1:cout input;cout output;if( press(input,output) pare(input,output);cout文件压缩成功!endl;elsecout文件压缩失败!endl;break;case 2:cout input;cout output;if (h.decompress(input,output)cout文件解压成功!endl;elsecout文件解压失败!endl;break;case 0:break;default:cout 参数错误！请重新输入 endl;cout endl;韶关学院计算机科学学院数据结构课程设计题 目

18、：基于哈夫曼树的文件压缩/解压程序学生姓名：曹键明学 号：11115011018专 业：计算机科学与技术班 级：11级（1）班 指导教师姓名及职称：陈正铭 讲师 起止时间： 2013 年 3 月 2013 年 4 月1 需求分析1.1课题背景及意义近年来，随着计算机技术的发展，多媒体计算机技术、计算机网络技术以及现代多媒体通信技术正在向着信息化、高速化、智能化迅速发展。各个领域的应用与发展，各个系统的数据量越来越大，给数据的存储、传输以及有效、快速获取信息带来了严重的障碍。数据压缩技术能够比较有效地解决这个问题。还有在最近几年中兴起的物联网和云计算都是对海量的数据进行处理和传输的，如果不对数据

19、进行压缩，那么数据传输所需的带宽要求就很高，物理成本上也随之上升。所以说数据压缩在计算机通信中占有很重要的位置，且涉及领域多，应用广泛，与我们的生活息息相关。1.2课题要求1.2.1实现一个基于哈夫曼树的文件压缩程序和文件解压程序。1.2.2.压缩程序能输入源文件进行压缩，输出压缩文件；1.2.3解压程序读入压缩文件，根据相应的哈夫曼编码解压还原 ，得到对应的源文件。1.2.4可选做：求出压缩率；打印哈夫曼树；对文件夹压缩；图形图形化窗口操作界面。1.3任务和要求1.3.1选择1时：输入一个待压缩的文本文件名称(可带路径)。如:D:1XXX.txt压缩文件名称= D:1YYY.txt1.3.2

20、选择2时：输入一个待解压的压缩文件名称(可带路径)。如:D:1YYY.txt解压文件名称=D:XXX.txt2概要设计2.1问题解决的思路概述建立哈夫曼树根据哈夫曼树解码对二进制文件进行解码统计字符，得出统计出字符的权值n根据哈夫曼树编码对编码进行压缩生成哈夫曼树生成对应文件生成二进制文件 图1 主程序流程图2.2 算法思想：2.2.1输入要压缩的文件首先运行的时候，用户主界面上有菜单提示该如何使用软件，根据菜单提示选择所要执行的项，依次进行，因为各个环节之间有先后顺序。第一步为输入压缩软件的名称，由键盘输入文件路径和文件名称，读入字符数组中，打开该文件，按照提示进行压缩。若打不开，则继续输入

21、。2.2.2读文件并计算字符频率文件将信息存放在字符数组中；计算每个字符出现的次数，申请一个结构体数组空间， 用读取的字符减去字符结束符作为下标记录字符的频率。2.2.3根据字符的频率，利用Huffman编码思想创建Huffman树将所记录的字符的频率作为权值来创建Huffman树，依次选择权值最小的两个字符作为左右孩子，其和作为父结点的权值，依次进行下去，直到所有的字符结点都成为叶子结点。2.2.4由创建的Huffman树来决定字符对应的编码，进行文件的压缩根据创建的Huffman树来确定个字符的01编码，左孩子为0，右孩子为1。读取文件，依次将每个字符用他们的编码表示，即完成一次编码。2.

22、2.5解码压缩即根据Huffman树进行译码读取编码文件，依据创建的Huffman树，定义一个指针指向根结点。从根结点开始，每读一个字符，指针变化一次（当读取的字符是1时，指针指向当前所指结点的右孩子，当读取的字符是0时，指针指向当前所指结点的左孩子），直至该指针所指结点为叶子结点时结束（即当结点的左右孩子均为空时）。将当前叶子结点所代表的字符值输出到译码文件中，依次读取编码文件中的字符，按照上述方法依次进行下去直至文件2.3数据结构定义/huffman树的结点结构体typedef struct HTnodelong weight;/记录结点的权值int parent;/记录结点的双亲结点位置

23、int lchild;/结点的左孩子int rchild;/结点的右孩子int *code;/记录该结点的huffman编码int codelen;/记录该结点huffman编码的长度HTnode()weight = MAX;parent = -1;lchild = -1;rchild = -1;codelen = 0;HTnode;2.4定义huffman数类及其函数class huffmanTree public:huffmanTree();virtual huffmanTree();bool count(char *input); /压缩时统计各字符出现的次数，将其写入对应结点的权值vo

24、id create();/压缩时根据各结点的权值构造huffman树void code();/压缩时利用huffman树计算每个字符的huffman编码void addbit(int bit); /压缩时对一个未满8个bit的byte中加入一个bitvoid resetbyte();/将byte清空bool compress(char *input, char *output);/压缩函数,成功返回 true 失败 falsebool decompress(char *input, char *output); /解压函数,成功返回 true 失败falsevoid compare(char

25、*input, char *output);/将原文件与压缩后的文件比较private:int root;/记录根结点的位置int leafnum;/记录不同字符的个数HTnode HTleaf*2-1;/HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1char byte;/压缩文件时用来缓冲bit的变量int bitsnum;/byte中bit的个数int lacknum;/压缩到最后byte中的bit不满8个时填充的0的个数;2.5主程序的流程及模块间关系主函数实例化huffmanTree类，并实现菜单工具栏，通过用户的选择输入，用switch语句

26、进行分支执行huffmanTree类中功能函数：1:压缩函数 bool compress(char *input, char *output)2:解压函数 bool decompress(char *input, char *output)并可在完成相应功能后安全退出，压缩或解压的文件在同文件夹下生成。3. 详细设计核心算法-huffman算法：3.1根据给定的n个权值w1,w2,wn构成n棵二叉树的集合F=T1,T2,Tn,其中每棵二叉树T1中只有一个带权的 w1的根据点，其左右子树均空。3.2在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其

27、左右树上根结点的权值之和。3.3在F中删除这两棵树，同时将所得到的二叉树加入F中。3.4重复3.2,3.3,直到F中只含一棵树为止。这棵树便是Huffman树。Huffman树可用于构造代码总长度最短的编码方案。为了详细说明这个问题，特以下面例子来说明:4假设我们有这么一串20个字母的数据： 默认情况下，用2位2进制码来表示这四个字母：ABCD00011011每个字符在字符串中各自出现的次数并不相等：A:6次 B:10次 C:3次 D:1次而在计算机中，数据则是以2进制码的形式储存在硬盘上的：00 00 01 00 00 01 01 10 01 00 01 01 01 10 01 01 00

28、01 11 10压缩过程如下：注明每个字符的出现次数。把两个出现次数最小的字符圈到一起，看作一个新字符，新字符的次数为两个组成字符的次数之和。重复上述操作，直至完成对所有字符的处理。这种操作形成的结构看起来像棵树（下图），被称为霍夫曼(Huffman)树。 图2 构造哈夫曼树在每一层的分支线上，按下图所示分别标上0和1。 图3 哈弗曼编码从最顶端往下读，每个字符都有唯一的分支编号连到它那里，无重复也无遗漏，这样就得到了ABCD这四个字符的新的代码：ABCD100110111用以上新编码代入原字符串中，得到：10 10 0 10 10 0 0 110 0 10 0 0 0 110 0 0 10

29、0 111 110主程序模块:主函数菜 单huffmanTree类压缩函数compress恢复函数decompress 对比函数compare2 图 4 程序模块Huffman编码流程NOYES哈夫曼编码位操作压缩存储压缩文件成功!计算压缩率%打开文本文件统计文件长度初始化节点构建哈夫曼树计算左右分支权值大小,进行无重复前缀编码压缩文件失败图 5 编码流程Huffman解码流程NOYES解压压缩文件成功!解压缩文件失败!打开压缩文件读取原文件长度进行文件定位根据哈夫曼编码的长短,对节点进行排序通过哈夫曼编码的长短,依次解码,从原来的位存储还原到字节存储在单字节内对相应位置补0图 6 解码流程4

30、.调试分析报告实现压缩率时出现了主观上的错误，压缩率=(total1-total2)/total1*100%，经百度后发现：压缩率（Compression ratio），描述压缩文件的效果名，是文件压缩后的大小与压缩前的大小之比，比如你把100m的文件压缩后是90m，压缩率就是90/100*100%=90%，压缩率一般是越小越好，但是压得越小，时间越长。5如下图：图 7 压缩率测试结果将压缩率改正为： total2/total1*100%，再进行测试的结果如下图： 图 8 改正后的测试结果5.用户使用说明在运行程序之前，首先在e盘先建立一个待压缩的文件222.txt，运行程序如下图所示。 图9

31、 版本测试结果图压缩：在命令行下输入1对文件进行压缩，根据提示输入刚刚建的文本文件（222.txt），和要生成的压缩文件名称，按回车确认进行压缩。 图 10 执行压缩操作图成功执行完毕后如下图所示。 图 11 执行压缩操作图解压：在命令行下输入2对本程序压缩的文件进行恢复，根据提示输入待恢复的文件名称和恢复后的文件名称，按回车确定，成功执行后如下图所示。 图12 执行解压操作图对比：原文件222.txt 图 13 待压缩文件222.txt 压缩后的文件111.txt 图14 压缩后的文件111.txt 解压后的文件333.txt 图 15 解压后的文件333.txt6.测试结果详细测试结果请参

32、见 5 使用功能。6.1测试报告原文件压缩后解压后1txt文件(7kb)6 kb7 kb2pdf文件(1080kb)1052 kb无法解压得到原文件3jpg文件(81kb)80 kb无法解压得到原文件4Mp3文件(924kb)913 kb无法解压得到原文件打开解压后的pdf文件时提示如下： 图 16 打开解压后pdf文件的提示打开解压后的jpg和mp3文件同样遇到无法打开的提示。参考文献1严蔚敏，李冬梅，吴伟民 .数据结构(C语言版) M.北京:人民邮电出版社，2011.2谭浩强 .C+面向对象程序设计(第二版) M.北京：中国铁道出版社，2009.3潘玮华 . 用Huffman编码进行文件压

33、缩的方法 J.电脑知识与技术,2010年07期.4kaikai.数据是怎么被压缩的OL. 5百度百科.OL. .附录：源程序#include #include #include /队列容器using namespace std;const int leaf = 256;/最多可能出现的不同字符数const long MAX = 99999999;/表示无穷大typedef struct HTnodelong weight;/记录结点的权值int parent;/记录结点的双亲结点位置int lchild;/结点的左孩子int rchild;/结点的右孩子int *code;/记录该结点的huf

34、fman编码int codelen;/记录该结点huffman编码的长度HTnode()weight = MAX;parent = -1;lchild = -1;rchild = -1;codelen = 0;HTnode;class huffmanTree public:huffmanTree();virtual huffmanTree();bool count(char *input);/统计各字符出现的次数，将其写入对应结点的权值void create();/构造huffman树void code();/计算每个字符的huffman编码void addbit(int bit);/压缩时对

35、一个未满8个bit的byte中加入一个bitvoid resetbyte();/将byte清空bool compress(char *input, char *output);/压缩函数 成功执行返回 true 失败 falsebool decompress(char *input, char *output);/解压函数 成功执行返回 true 失败 falsevoid compare(char *input, char *output);/将原文件与压缩后的文件比较private:int root;/记录根结点的位置int leafnum;/记录不同字符的个数HTnode HTleaf*2

36、-1;/HTnode结构的数组，用来表示huffman树，树的最大结点个数不会超过leaf*2-1char byte;/压缩文件时用来缓冲bit的变量int bitsnum;/byte中bit的个数int lacknum;/压缩到最后byte中的bit不满8个时填充的0的个数;huffmanTree:huffmanTree()/初始化成员变量root = 0;leafnum = 0;byte = 0;bitsnum = 0;lacknum = 0;huffmanTree:huffmanTree()for(int i=0; ileaf; i+)if(HTi.codelen != 0)delete

37、 HTi.code;/统计各字符出现的次数bool huffmanTree:count(char *input)ifstream ifs;char c;ifs.open(input,ios:binary);if(!ifs)cout 无法打开文件 input ! endl;return false;while(ifs.get(c)if(HTc+128.weight=MAX)/若该字符是第一次出现，先初始化权值HTc+128.weight = 0;leafnum+;HTc+128.weight+;/权值+1ifs.close();return true;/选权值最小的两棵树组成新的数void hu

38、ffmanTree:create()for(int i=leaf; i2*leaf-1; i+)int loc1=-1, loc2=-1;for(int j=0; ji; j+)if(HTj.parent != -1)continue;if(loc1=-1 | HTj.weight HTloc1.weight)loc2 = loc1;loc1 = j;else if(loc2=-1 | HTj.weight loc2 ? loc2 : loc1;HTi.rchild = loc1loc2 ? loc1 : loc2;HTloc1.parent = i;HTloc2.parent = i;roo

39、t = i;/计算每个字符的huffman编码void huffmanTree:code()for(int i=0; i=0; j-)/从后往前找，记录结点的huffman编码if(loc=HTHTloc.parent.lchild)HTi.codej = 0;elseHTi.codej = 1;loc = HTloc.parent;/压缩时对一个未满8个bit的byte中加入一个bitvoid huffmanTree:addbit(int bit)if(bit = 0)byte = byte 1;/若新增的bit为0，则直接将byte按位左移elsebyte = (byte 1) | 1);

40、/若新增的bit为1，先将byte按位左移，再与1按位或运算bitsnum+;/将byte清空void huffmanTree:resetbyte()byte = 0;bitsnum = 0;/压缩函数 成功执行返回 true 失败 falsebool huffmanTree:compress(char *input, char *output)if( !count(input) ) return false;create();code();ifstream ifs;ofstream ofs;ifs.open(input,ios:binary);ofs.open(output,ios:bina

41、ry);char c;if(!ifs)cout 无法打开文件 input ! endl;return false;if(!ofs)cout 无法打开文件 output ! endl;return false;ofs.put(0);/预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384);/将根节点的位置-384写入（为使该值不超过char的最大表示范围）for(int i=0; ileaf*2-1; i+)/写入每个结点的双亲结点位置if(HTi.parent=-1)/若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)ofs.put(12

42、7);else/否则将双亲结点的位置-384再写入（为使该值不超过char的最大表示范围）ofs.put(HTi.parent-384);while(ifs.get(c)/将字符的huffman编码并加入byte中int tmp = c+128;for(int i=0; iHTtmp.codelen; i+)addbit(HTtmp.codei);if(bitsnum=8)/若byte已满8位，则输出该byte并将byte清空ofs.put(byte);resetbyte();if(bitsnum!=0)/处理最后未满8个字符的byte，用0填充并记录填充的个数for(int i=bitsnu

43、m; i8; i+)addbit(0);lacknum+;ofs.put(byte);resetbyte();ofs.seekp(0,ios:beg);/将写指针移动到文件开头ofs.put(lacknum);/写入最后一个字节缺失的bit个数ifs.close();ofs.close();return true;/解压函数 成功执行返回 true 失败 falsebool huffmanTree:decompress(char *input, char *output)queue q;char c;ifstream ifs;ofstream ofs;ifs.open(input,ios:binary);ofs.open(output,ios:binary);if(!ifs)cout 无法打开文件 input ! endl;return true;if(!ofs)cout 无法打开文件 output ! endl;return false;ifs.get(c);lacknum = c;/读出最后一个字节缺失的bit个数ifs.get(c);root = c+384;/读出根结点的位置for(int i=0; i1)/还未到最后一个字节c = q.front();for(int i=0; i8; i+)if(int(c&128)=0)