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

#include<iostream>#include<fstream>#include<queue>//队列容器usingnamespacestd;constintleaf=256;//最多可能出现的不同字符数constlongMAX=99999999;typedefstructHTnode{longweight;intparent;intlchild;intrchild;int*code;intcodelen;//表示无穷大//记录结点的权值//记录结点的双亲结点位置//结点的左孩子//结点的右孩子该结点的huffman编码//记录该结点huffman编码的长度HTnode{weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}}HTnode;classhuffmanTree{chuffmanTree();virtual~huffmanTree();boolcount(char*input);//统计各字符出现的次数，将其写入对应结点的权值voidcreate();voidcode();voidaddbit(intbit);voidresetbyte();n/计算每个字符的huffman编码boolcompress(char*input,char*output);败falsebooldecompress(char*input,char*output);失败falsevoidcompare(char*input,char*output);//压缩函数成功执行返回true失//解压函数成功执行返回true//将原文件与压缩后的文件比较vateintroot;intleafnum;//记录根结点的位置//记录不同字符的个数HTnodeHT[leaf*2-1];charbyte;intbitsnum;intlacknum;//HTnode结构的数组，用来表示huffman树，树的最大结//压缩文件时用来缓冲bit的变量ebithuffmanTree::huffmanTree(){//初始化成员变量root=0;leafnum=0;byte=0;bitsnum=0;lacknum=0;}huffmanTree::~huffmanTree(){for(inti=0;i<leaf;i++){if(HT[i].codelen!=0)delete[]HT[i].code;}}//统计各字符出现的次数boolhuffmanTree::count(char*input){ifstreamifs;charc;ifs.open(input,ios::binary);ififs{cout<<"无法打开文件"<<input<<'!'<<endl;returnfalse;}while(ifs.get(c)){if(HT[c+128].weight==MAX){HT[c+128].weight=0;//若该字符是第一次出现，先初始化权值leafnum++;}HT[c+128].weight++;}ifs.close();//权值+1returntrue;}//选权值最小的两棵树组成新的数voidhuffmanTree::create(){for(inti=leaf;i<2*leaf-1;i++){intloc1=-1,loc2=-1;for(intj=0;j<i;j++){if(HT[j].parent!=-1)continue;if(loc1==-1||HT[j].weight<HT[loc1].weight){loc2=loc1;locj;}elseif(loc2==-1||HT[j].weight<HT[loc2].weight)locj;}if(HT[loc1].weight==MAX||HT[loc2].weight==MAX||loc2==-1)//只剩一棵树，结束HT[i].weight=HT[loc1].weight+HT[loc2].weight;结点的左孩子HT[i].lchild=loc1>loc2?loc2:loc1;HT[i].rchild=loc1>loc2?loc1:loc2;HT[loc1].parent=i;HT[loc2].parent=i;root=i;}}//计算每个字符的huffman编码voidhuffmanTree::code(){for(inti=0;i<leaf;i++){intlen=0;intloc=i;while(HT[loc].parent!=-1){//计算huffman编码长度loc=HT[loc].parent;}HT[i].codelen=len;HT[i].code=newint[len];loc=i;for(intj=len-1;j>=0;j--){//从后往前找，记录结点的huffman编码if(loc==HT[HT[loc].parent].lchild)HT[i].code[j]=0;eHT[i].code[j]=1;loc=HT[loc].parent;}}}voidhuffmanTree::addbit(intbit){if(bit==0)byteebyte=((byte<<1)|1);或运算bitsnum++;}voidhuffmanTree::resetbyte(){byte=0;bitsnum=0;}//压缩函数成功执行返回true失败falseboolhuffmanTree::compress(char*input,char*output){if(!count(input))returnfalse;create();code();ifstreamifs;ofstreamofs;ifs.open(input,ios::binary);ofs.open(output,ios::binary);charc;ifs{cout<<"无法打开文件"<<input<<'!'<<endl;returnfalse;}ifofs{cout<<"无法打开文件"<<output<<'!'<<endl;returnfalse;}ofs.put(0);//预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384);//将根节点的位置-384写入(为使该值不超过char的最大表示范围)for(inti=0;i<leaf*2-1;i++){//写入每个结点的双亲结点位置ofs.put(127);else//否则将双亲结点的位置-384再写入(为使该值不超过char的最大表示范围)ofs.put(HT[i].parent-384);}while(ifs.get(c)){nbyteinttmp=c+128;for(inti=0;i<HT[tmp].codelen;i++){addbit(HT[tmp].code[i]);if(bitsnum==8)yteofs.put(byte);resetbyte();}}}ifbitsnum8个字符的byte，用0填充并记录填充的个数for(inti=bitsnum;i<8;i++){addbit(0);lacknum++;}ofs.put(byte);resetbyte();}ofs.seekp(0,ios::beg);ofs.put(lacknum);ifs.close();ofs.close();returntrue;}//将写指针移动到文件开头//写入最后一个字节缺失的bit个数//解压函数成功执行返回true失败falseboolhuffmanTree::decompress(char*input,char*output){queue<char>q;charc;ifstreamifs;ofstreamofs;ifs.open(input,ios::binary);ofs.open(output,ios::binary);ifs{cout<<"无法打开文件"<<input<<'!'<<endl;returntrue;}ifofs{cout<<"无法打开文件"<<output<<'!'<<endl;returnfalse;}ifs.get(c);lacknum=c;//读出最后一个字节缺失的bit个数ifs.get(c);root=c+384;//读出根结点的位置for(inti=0;i<leaf*2-1;i++){//建立各结点之间的双亲孩子关系ifs.get(c);if(c==127)continue;e{HT[i].parent=c+384;if(HT[c+384].lchild==-1)HT[c+384].lchild=i;eHT[c+384].rchild=i;}}intpoint=root;//为了方便处理最后一个可能有缺失bit的字节，先将读出的数据放入队列while(ifs.get(c))q.push(c);//还原文件过程while(q.size()>1){//还未到最后一个字节c=q.front();for(inti=0;i<8;i++){if(int(c&128)==0){point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}e{point=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}}q.pop();}c=q.front();//最后一个字节for(i=0;i<8-lacknum;i++){if(int(c&128)==0){point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}lsepoint=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}}q.pop();ifs.close();ofs.close();returntrue;}//将原文件与压缩后的文件比较voidhuffmanTree::compare(char*input,char*output){ifstreamorigin,compress;origin.open(input,ios::binary);compress.open(output,ios::binary);if(!origin){cout<<"无法打开文件"<<input<<'!'<<endl;n}if(!compress){cout<<"无法打开文件"<<output<<'!'<<endl;n}doubletotal1=0,total2=0;charc;while(origin.get(c))total1++;while(compress.get(c))total2++;ByteendlByteendlorigin.close();compress.close();}voidmain(){intchoice=1;charinput[255],output[255];huffmanTreeh;while(choice){cout<<"****************************************************"<<endl;cout<<"*基于哈夫曼树的文件压缩/解压程序*"<<endl;cout<<"**"<<endl;cout<<"cout<<"**1)压缩*"<<endl;*"<<endl;cout<<"cout<<"**2)解压*"<<endl;*"<<endl;cout<<"cout<<"**0)退出*"<<endl;*"<<endl;cout<<"*说明：请输入相应的操作序号*"<<endl;cout<<"****************************************************"<<endl;cout<<"请选择:";cin>>choice;switch(choice){case1:{cin>>input;cin>>output;if(press(input,output)){pare(input,output);cout<<"文件压缩成功!"<<endl;{cout<<"文件压缩失败!"<<endl;}}case2:{cin>>input;cin>>output;if(h.decompress(input,output))cout<<"文件解压成功!"<<endl;ecout<<"文件解压失败!"<<endl;}case0:default:cout<<"参数错误！请重新输入"<<endl;}cout<<endl;}}设计题目：基于哈夫曼树的文件压缩/解压程序术班级：11级(1)班指导教师姓名及职称：陈正铭讲师月展，多媒体计算机技术、计算机网络技术以及现息化、高速化、智能化迅速发展。各个领域的应用与越大，给数据的存储、传输以及有效、快速获取信息网和云计算都是对海量的数据进行处理和传输传输所需的带宽要求就很高，物理成本上也信中占有很重要的位置，且涉及领域多，应名称(可带路径)。tD\1\YYY.txt名称(可带路径)。t=D:\XXX.txt树n码码如何使用软件，根据菜单提示选因为各个环节之间有先后顺序。第一步为输入压缩软径和文件名称，读入字符数组中，打开该文件，按照个字符出现的次数，申请一个结构体数n的权值，依次进行下去，直到所有的字符结点始，每读一个字符，指针变化一次(当读取的字符是‘1’时，指针指向当前所指结针所指结点为叶子结点时结束(即当结点的左右孩子均为空时)。将当前叶子结点所//huffman树的结点结构体{的权值的双亲结点位置孩子intcodelen;//记录该结点huffman编码的长度de{weight=MAX;parent=-1;rchild=-1;}{TreehuffmanTreeutvoidcreate();//压缩时根据各结点的权值构造huffman树voidcode();//压缩时利用huffman树计算每个字符的huffman编码voidaddbit(intbit);//压缩时对一个未满8个bit的byte中加入一个bitelsecompresscharinputcharoutputtrue失败falsevoidcomparecharinput,char*output);//将原文件与压缩后的文introot;//记录根结点的位置intbitsnum/byte中bit的个数intlacknum;//压缩到最后byte中的bit不满8个时填充的0的个数routputooldecompresscharinputcharoutput为了详细说明这个问题，特以下面例子来说明:[4]AABCD0000010000010110010001010110010100011110把两个出现次数最小的字符圈到一起，看作一个新字对所有字符的处理。这种操作形成的结构看起来像棵树(下图)，被称为——霍夫曼(Huffman)树。支编号连到它那里，无重复也无遗漏，这AABCD0011000100111110主程序模块:压缩函数ffman主函数菜单对比函数对比函数程序模块码YES编码流程ffman根据哈夫曼编码的长短,对通过哈夫曼编码的长短,依解码,从原来的位存储还置补0解码流程4.调试分析报告经百度后发现：压缩率(Compressionratio)，描述压缩文件的效果名，是文0m的文件压缩后是90m，压缩图7压缩率测试结果图8改正后的测试结果5.用户使用说明2.txt)，图10执行压缩操作图图11执行压缩操作图压缩的文件进行恢复，根据提示输入待恢复的图15解压后的文件333.txt详细测试结果请参见5使用功能。txt件(7kb)pdf文件Mp3文件24图16打开解压后pdf文件的提示jpgmp同样遇到无法打开的提示。[1]严蔚敏，李冬梅，吴伟民.数据结构(C语言版)[M].北京:人民邮电出版社，2011.[3]潘玮华.用Huffman编码进行文件压缩的方法[J].电脑知识与技术,2010年07期.[4]kaikai.数据是怎么被压缩的[OL]./article/46865/,2011.[5]百度百科.[OL]./view/354638.htm.#include<iostream>#include<fstream>#include<queue>//队列容器usingnamespacestd;constintleaf=256;constlongMAX=99999999;typedefstructHTnode{longweight;intparent;intlchild;intrchild;int*code;intcodelen;//最多可能出现的不同字符数//表示无穷大//记录结点的权值//记录结点的双亲结点位置//结点的左孩子//结点的右孩子//记录该结点的huffman编码//记录该结点huffman编码的长度HTnode(){weight=MAX;parent=-1;lchild=-1;rchild=-1;codelen=0;}}HTnode;classhuffmanTree{public:huffmanTree();virtual~huffmanTree();boolcount(char*input);voidcreate();voidcode();voidaddbit(intbit);//统计各字符出现的次数，将其写入对应结点的权值//构造huffman树//计算每个字符的huffman编码//压缩时对一个未满8个bit的byte中加入一个bitvoidresetbyte();//将byte清空boolcompress(char*input,char*output);回true失败falsebooldecompress(char*input,char*output);回true失败falsevoidcompare(char*input,char*output);//压缩函数成功执行返//解压函数成功执行返//将原文件与压缩后的文件比较private:ntrootintleafnum;HTnodeHT[leaf*2-1];结点个数不会超过leaf*2-1charbyte;intbitsnum;intlacknum;//记录根结点的位置//记录不同字符的个数//压缩文件时用来缓冲bit的变量//byte中bit的个数//压缩到最后byte中的bit不满8个时填充的0的个数huffmanTree::huffmanTree(){//初始化成员变量root=0;leafnum=0;byte=0;bitsnum=0;lacknum=0;}huffmanTree::~huffmanTree(){for(inti=0;i<leaf;i++){if(HT[i].codelen!=0)delete[]HT[i].code;}}//统计各字符出现的次数boolhuffmanTree::count(char*input){ifstreamifs;charc;ififs{cout<<"无法打开文件"<<input<<'!'<<endl;returnfalse;}while(ifs.get(c)){if(HT[c+128].weight==MAX){HT[c+128].weight=0;//若该字符是第一次出现，先初始化权值leafnum++;}HT[c+128].weight++;}//权值+1ifs.close();returntrue;}//选权值最小的两棵树组成新的数voidhuffmanTree::create(){for(inti=leaf;i<2*leaf-1;i++){intloc1=-1,loc2=-1;for(intj=0;j<i;j++){if(HT[j].parent!=-1)continue;if(loc1==-1||HT[j].weight<HT[loc1].weight){loc2=loc1;loc1=j;}elseif(loc2==-1||HT[j].weight<HT[loc2].weight)loc2=j;}//只剩if(HT[loc1].weight==MAX||HT[loc2].weight==MAX||loc2==-1)//只剩一棵树，结束break;HT[i].weight=HT[loc1].weight+HT[loc2].weight;//为了减少压缩文件中需要写入的huffman树的信息，约定小标小的结点做为双亲结点的左孩子HT[i].lchild=loc1>loc2?loc2:loc1;HT[i].rchild=loc1>loc2?loc1:loc2;HT[loc1].parent=i;HT[loc2].parent=i;root=i;}}//计算每个字符的huffman编码voidhuffmanTree::code(){for(inti=0;i<leaf;i++){intlen=0;intloc=i;while(HT[loc].parent!=-1){//计算huffman编码长度loc=HT[loc].parent;}HT[i].codelen=len;HT[i].code=newint[len];loc=i;for(intj=len-1;j>=0;j--){//从后往前找，记录结点的huffman编码if(loc==HT[HT[loc].parent].lchild)HT[i].code[j]=0;HT[i].code[j]=1;loc=HT[loc].parent;}}}//压缩时对一个未满8个bit的byte中加入一个bitvoidhuffmanTree::addbit(intbit){if(bit==0)byte=byte<<1;//若新增的bit为0，则直接将byte按位左移byte=((byte<<1)|1);//若新增的bit为1，先将byte按位左移，再与1按位或运算bitsnum++;}//将byte清空voidhuffmanTree::resetbyte(){byte=0;bitsnum=0;}//压缩函数成功执行返回true失败falseboolhuffmanTree::compress(char*input,char*output){if(!count(input))returnfalse;create();code();ifstreamifs;ofstreamofs;charc;fs{cout<<"无法打开文件"<<input<<'!'<<endl;returnfalse;}fs{cout<<"无法打开文件"<<output<<'!'<<endl;returnfalse;}ofs.put(0);//预留一个字符，等压缩完后在该位置写入不足一个byte的bit个数ofs.put(root-384);//将根节点的位置-384写入(为使该值不超过char的最大表示for(inti=0;i<leaf*2-1;i++){//写入每个结点的双亲结点位置if(HT[i].parent==-1)//若该节点没有双亲结点，则写入127(一个字节所能表示的最大值)ofs.put(127);else//否则将双亲结点的位置-384再写入(为使该值不超过char的最大表示ofs.put(HT[i].parent-384);}while(ifs.get(c)){//将字符的huffman编码并加入byte中inttmp=c+128;for(inti=0;i<HT[tmp].codelen;i++){addbit(HT[tmp].code[i]);if(bitsnum==8){//若byte已满8位，则输出该byte并将byte清空ofs.put(byte);resetbyte();}}}if(bitsnum!=0){//处理最后未满8个字符的byte，用0填充并记录填充的个数for(inti=bitsnum;i<8;i++){addbit(0);lacknum++;}ofs.put(byte);resetbyte();}ofs.seekp(0,ios::beg);ofs.put(lacknum);ifs.close();ofs.close();returntrue;}//将写指针移动到文件开头//写入最后一个字节缺失的bit个数//解压函数成功执行返回true失败falseboolhuffmanTree::decompress(char*input,char*output){queue<char>q;charc;ifstreamifs;ofstreamofs;fs{cout<<"无法打开文件"<<input<<'!'<<endl;returntrue;}fs{cout<<"无法打开文件"<<output<<'!'<<endl;returnfalse;}ifs.get(c);lacknum=c;ifs.get(c);root=c+384;//读出最后一个字节缺失的bit个数//读出根结点的位置for(inti=0;i<leaf*2-1;i++){//建立各结点之间的双亲孩子关系ifs.get(c);if(c==127)continue;{HT[i].parent=c+384;if(HT[c+384].lchild==-1)HT[c+384].lchild=i;HT[c+384].rchild=i;}}intpoint=root;//为了方便处理最后一个可能有缺失bit的字节，先将读出的数据放入队列while(ifs.get(c))q.push(c);//还原文件过程while(q.size()>1){//还未到最后一个字节c=q.front();for(inti=0;i<8;i++){if(int(c&128)==0){point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}{point=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}}q.pop();}c=q.front();for(i=0;i<8-lacknum;i++){if(int(c&128)==0)//最后一个字节{point=HT[point].lchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));point=root;}c=c<<1;}sepoint=HT[point].rchild;if(HT[point].lchild==-1&&HT[point].rchild==-1){ofs.put(char(point-128));poin