哈弗曼编码解码器

〃课程设计：哈弗曼编码解码器及报告书//vc6测试可以〃运行的条件是：“yasuo.txt”，“yima.txt”，“jieya.txt”存在，要压缩的信息已存//在了其他一个文本文档中，然后根据提示输入要压缩的文本文件名，输入的文件名要//加.txt扩展名，如：a.txt。//writebydlnu.ZJY#include<iostream>#include<fstream>#defineMax50#defineMAX10000usingnamespacestd;structtree//存储统计的频率和字母的{charword;intrare;};structBianma//存各字母所对应的编码的{charword;intcode[Max];};structelement//哈弗曼树的{treeweight;intlchild;intrchild;intparent;intflag;intyezi;};// 全局变量elementhuffTree[103];Bianmabianma[52];intzijie,wei,yushu;charfilename[50];//

classHuffmanTree{public:classHuffmanTree{public:voidopen();voidcreat();intselect(intk);voidcoding();voiddecoding();voidoriginal();voidcompare();voidyasuoxianshi();voidjieyaxianshi();voidxianshi();voidmenu();〃构造哈弗曼树函数//找权值最小根节点函数〃编码函数//将编码后信息存入文件函数〃对已压缩文件解压并译码函数〃压缩函数〃显示压缩信息〃显示解压信息〃显示文件压缩比//菜单};// voidHuffmanTree::open()//^J开文件并统计频率{charch;inti,n,j=0,flag=0;for(i=0;i<103;i++)//初始化{huffTree[i].weight.rare=0;huffTree[i].weight.word=0;huffTree[i].yezi=0;}coutvv”请输入您要压缩的文件名："vvendl;cin>>filename;ifstreaminfile(filename,ios::out);//打开文件if(!infile){flag=1;cerrvv"文件打开失败!”<<endl;exit(1);}if(flag==0){coutvv"压缩中，请等待 "vvendlvvendlvvendl;}while(infile.get(ch))//统计频率{if(ch>=65&&ch<=90)//65~90{i=ch-65;huffTree[i].weight.rare++;huffTree[i].yezi=1;}if(ch>=97&&ch<=122)//97~122{n=ch-71;huffTree[n].weight.rare++;huffTree[n].yezi=1;}}infile.close();}// voidHuffmanTree::creat()//构造哈弗曼树{inti,k,i1,i2,n=52,j;for(i=0;i<2*n-1;i++)//初始化{huffTree[i].parent=-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;huffTree[i].flag=0;}for(i=0;i<26;i++)//字母赋值{huffTree[i].weight.word=i+65;}for(j=0;j<26;j++)//字母赋值{huffTree[j+26].weight.word=j+97;}for(k=n;k<2*n-1;k++)/健树{=select(k);=select(k);huffTree[k].weight.rare=huffTree[i1].weight.rare+huffTree[i2].weight.rare;huffTree[i1].parent=k;huffTree[i2].parent=k;huffTree[k].lchild=i1;huffTree[k].rchild=i2;}}// intHuffmanTree::select(intk)//找出所有根节点中权值最小的根节点{inti,n=52,min,rare=10000;for(i=0;i<k;i++){if((huffTree[i].weight.rare<rare)&&(huffTree[i].flag==0)){min=i;rare=huffTree[i].weight.rare;}}huffTree[min].flag=1;returnmin;}// voidHuffmanTree::coding()//对构造出的哈弗曼树编码{inte,a=0,i,j,n=52,p,parent;for(i=0;i<n;i++)//初始化{for(j=0;j<Max;j++){bianma[i].code[j]=-1;}bianma[i].word=95;}for(i=0;i<2*n-1;i++)//根据建好的哈弗曼树对各字母编码，从叶子结点往上查，左1右0，将编好的码存入bianma[]中{if((huffTree[i].flag!=2)&&(huffTree[i].yezi==1)){e=Max-1;huffTree[i].flag=2;bianma[a].word=huffTree[i].weight.word;p=i;while(huffTree[p].parent!=-1){parent=huffTree[p].parent;if(huffTree[parent].lchild==p){bianma[a].code[e]=0;e--;}elseif(huffTree[parent].rchild==p){bianma[a].code[e]=1;e--;}p=huffTree[p].parent;//原来是这里的问题，以前parent两次赋值让每次编码都又往上跳了一级，所有编出的码有重复的}a++;}}}// voidHuffmanTree::decoding()//将原文件重新编码后将编码后的存入文件{inti,j,n=52;charch;ifstreamfile(filename,ios::out);if(!file){cerr<<"文件打开失败!”<<endl;exit(1);}ofstreaminfile("bianma.txt”,ios::inlios::outlios::trunc);//打开文件if(!infile){cerr<<"文件打开失败!”<<endl;exit(1);while(file.get(ch))//将编码后的信息存入bianma.txt文件{for(i=0;i<n;i++){if(ch==bianma[i].word)for(j=0;j<Max;j++)if(bianma[i].code[j]!=-1){infile<<bianma[i].code[j];}}}file.close();infile.close();}// voidHuffmanTree::compare()//ffi缩文件{charch,a,yasuo[1000][8]={95},b[100000]={0};intn=0,i=0,j,k=0,l=0;ifstreaminfile("bianma.txt”,ios::out);//打开文件if(!infile){cerr<<"文件打开失败!”<<endl;exit(1);}ofstreamoutfile("yasuo.txt”,ios::binarylios::trunc);//打开文件if(!outfile){cerr<<"openerror!"<<endl;abort();}while(infile.get(ch))//统计0,1个数{b[i]=ch;i++;}wei=i；zijie=wei/8;yushu=wei%8;if(yushu!=0)zijie++;for(i=0;i<zijie;i++)//将编码后的信息每八个倒着存入yaosuo[][]数组{for(j=7;j>=0;j--){yasuo[i][j]=b[k++];}}for(i=0;i<zijie;i++)//压缩已编码的原文件，八个编码合为一个字节存入二进制文件{a=0;for(j=0;j<8;j++)if(yasuo[i][j]!=95)if(yasuo[i][j]=='0'IIyasuo[i][j]=='1'){if(yasuo[i][j]=='1'){a=(a<<1)I1;}elseif(yasuo[i][j]=='0'){a=a<<1;}}outfile.write((char*)&a,sizeof(a));}infile.close();outfile.close();}// voidHuffmanTree::original()/对已压缩文件解压并译码{inti=0,n=52,p=102,q=102,k,j,f=0,m=0;chara,b,c,d,jieya[100000];ifstreaminfile("yasuo.txt”,ios::binary);//打开文件if(!infile){cerr<<"文件打开失败!”<<endl;abort();}ofstreaminfile1("jieya.txt”,ios::in|ios::out|ios::trunc);//打开文件if(!infile1){cerr<<"文件打开失败!”<<endl;exit(1);}for(k=0;k<zijie;k++)//解压压缩了的二进制文件{infile.read((char*)&a,sizeof(a));for(j=0;j<8;j++){if(m>=wei){break;}b=a;c=((b>>1)<<1);//先右移再左移将最右端的位变为0d=(a-c)+'0';//得出最右端的二进制位a=a>>1;if(d=='0'){jieya[f++]='0';//将解压后的信息先存入jieya[]数组}elseif(d=='1'){jieya[f++]='1';//将解压后的信息先存入jieya[]数组}m++;}}for(intz=0;z<wei+1;z++)//译码，从树的根结点开始判断，左1右0，直到找到叶子结点{if(jieya[z]=='0'){i=huffTree[p].lchild;p=huffTree[p].lchild;if(huffTree[i].weight.word!=0){infile1<<huffTree[i].weight.word;p=q;}}elseif(jieya[z]=='1'){i=huffTree[p].rchild;p=huffTree[p].rchild;if(huffTree[i].weight.word!=0){infile1<<huffTree[i].weight.word;p=q;}}}infile.close();infile1.close();}// voidHuffmanTree::yasuoxianshi()/显示压缩的信息{charch;inti,j,n=52,k=0;ifstreaminfile(filename,ios::out);//打开文件if(!infile){cerr<<"文件打开失败!”<<endl;exit(1);}cout<<"原文件："<<endl;while(infile.get(ch))//输出原文件{cout<<ch;}cout<<endl<<endl;infile.close();cout<<”根据哈弗曼树对字母的编码："<<endl;for(i=0;i<n;i++)//输出各字母对应的编码{if(bianma[i].word!=95){for(j=0;j<Max;j++)if(bianma[i].code[j]!=-1)cout<<bianma[i].code[j];//编码cout<<" "<<bianma[i].word<<endl;//字母}}cout<<endl;ifstreaminfile2("bianma.txt",ios::out);//打开文件if(!infile2){cerr<<"文件打开失败!”<<endl;exit(1);}cout<<"对原文件编码后的文件："<<endl;while(infile2.get(ch))//输出对原文件编码后的信息{cout<<ch;}cout<<endl<<endl;cout<<"压缩成功!"vvendlvvendl;cout<<"压缩后的文件名为："<<"yasuo.txt"<<endl<<endl;}// voidHuffmanTree::jieyaxianshi()//显示解压的信息、{charch;ifstreaminfile3("jieya.txt",ios::out);//打开文件if(!infile3){cerr<<"文件打开失败!”<<endl;exit(1);}cout<<"解压成功!"<<endl<<endl;cout<<"解压后的文件名为：”<<"jieya.txt”<<endl<<endl;cout<<"解压并译码后的文件："<<endl;while(infile3.get(ch))//输出解压后的信息{cout<<ch;}cout<<endl<<endl;}// voidHuffmanTree::xianshi()//显示压缩比的信息{intk=0;charch;ifstreaminfile4(filename,ios::out);//打开文件if(!infile4){cerr<<"文件打开失败!”<<endl;exit(1);}while(infile4.get(ch))//统计原文件字母个数{k++;}cout<<”本次文件的压缩比为："<<endl;cout<<"原文件"<<" "<<"压缩后的文件"<<endl;cout<<""<<k<<" "<<":"<<""<<zijie<<endl<<endl;if(k>zijie)//判断压缩前后文件的大小看压缩是否成功{cout<<"压缩成功!”<<endl<<endl;cout<<"压缩率为： "<<((double)zijie/(double)k)*100<<"%”<<endl<<endl;}elsecout<<"压缩失败!"<<endl<<endl;}// voidHuffmanTree::menu()//主菜单{cout<<" 欢迎使用哈弗曼编码器&译码器"<<endl;cout<<"<< >>"<<endl;cout<<"请选择您需要的操作："<<endl;cout<<1 |<<endl;cout<<"I |"<<endl;cout<<"1 1.压缩文件 |"<<endl;cout<<"I 2.解压文件 |"<<endl;cout<<"I 3.显示压缩比 |"<<endl;cout<<"| 4.退出 |"<<endl;cout<<"I |"<<endl;cout<<"1 1」 1"<<endl<<endl;}// intmain(){HuffmanTreetree;intchoose;while(1){tree.menu();cin>>choose;cout<<endl;switch(choose){case1://压缩文件tree.open();tree.creat();tree.coding();tree.decoding();pare();tree.yasuoxianshi();system("pause");system("cls");break;case2://解压文件tree.original();tree.jieyaxianshi();system("pause");system("cls");break;case3://显示压缩比tree.xianshi();system("pause");system("cls");break;case4://退出cout<<"谢谢使用!"<<endl;exit(0);default:cout<<"输入错误，请重新输入!”<<endl;system("pause");system("cls");break;}}return0;}题目：设计Huffman编码器与解码器（**）TOC\o"1-5"\h\z\o"CurrentDocument"1、 问题描述 15\o"CurrentDocument"2、 需求分析 15\o"CurrentDocument"3、 概要设计 15（1） 抽象数据类型： 15（2） 主程序流程： 15（3） 模块调用关系: 16\o"CurrentDocument"4、 详细设计 17（1） 实现概要设计的数据类型： 17（2） 主程序以及其它模块的算法描述： 17主函数具体代码： 17（3） 其它模块的算法描述 18创建哈弗曼树函数： 19挑选权值最小的根节点函数： 19据建好的哈弗曼树编码函数： 20压缩文件主要代码： 21解压文件主要代码： 21译码主要代码： 225、 编码与调试分析 22编码与调试过程中遇到的问题及解决办法： 22待解决问题： 23\o"CurrentDocument"6、 使用说明 24\o"CurrentDocument"7、 测试结果 24（1） 压缩文件结果： 24（2） 解压文件结果： 25（3） 显示压缩比结果： 26\o"CurrentDocument"8、 自学知识 26\o"CurrentDocument"9、 课程设计心得体会 26参考书： 27问题描述利用哈夫曼编码进行信息通讯可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传输数据预先编码；在接受端将传来的数据进行译码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个哈夫曼码的编/译码系统。基本要求：根据某字符文件统计字符出现频度，构造Huffman树，编制Huffman编码，并将给定字符文件编码，生成编码文件；再将给定编码文件解码，生成字符文件。（要求按二进制位表示编码）提高要求：改进Huffman编码，产生两种以上的编码方案，对同一组测试数据，用不同的编码方案编码，从文件长度、算法复杂度等方面进行比较。测试数据：英文文档文件或中文文档文件。考核要求：（1） 对原文件编码后，保存到新建文件中，将原文件与新文件比较，如果新文件长度大于原文件，则编码失败，成绩不及格。如果达到题目的基本要求，成绩为良好。（2） 达到提高要求，成绩可以为优秀。需求分析软件的基本功能：根据某字符文件生成新的压缩后的二进制编码文件；再将给定编码文件解码，生成原来的字符文件。输入/输出形式：用户可以通过控制台，根据提示输入。输入：按提示输入，有错误过滤性能。输出：统一输出信息，不用选择。测试数据要求：将需要压缩的字符信息存在一个文本文件中后根据提示打开此文件进行压缩，文本文件中的信息内容为大小写字母。概要设计（1）抽象数据类型：结构体数组：elementhuffTree[103];Bianmabianma[52];（2）主程序流程:

（3）模块调用关系：voidopen();//打开要编码文件并统计字母出现的频率数voidcreat();〃构造哈弗曼树函数intselect(intk);〃找出权值最小根结点函数voidcoding();//编码函数voiddecoding();//将原文件重新编码后将编码后的存入文件voidoriginal();〃对已压缩文件解压并译码voidcompare();〃压缩文件voidyasuoxianshi();//显示压缩信息voidjieyaxianshi();//显示解压信息voidxianshi();〃显示文件压缩比voidmenu();〃菜单其函数调用关系如下：详细设计实现概要设计的数据类型：structtree//存储统计的频率和字母的{charword;intrare;}；structBianma//存各字母所对应的编码的{charword;intcode[Max];};structelement//哈弗曼树的{treeweight;intlchild;intrchild;intparent;intflag;intyezi;};主程序以及其它模块的算法描述：主函数具体代码:IntNuffmanTreetree;ir)tchoose;whiie(ijtree.menu();cin»cnoase;cvut«endl;si?Ltch(chou5e><caseE/压瑞文件tree_open();;tree,codings);tree-decoding(>;trpe-CDmpjr&();tpee-^asuaxianehit);£y£tem<"pju&e">;sygtem(,,el5,*);break;case 解压文件tree-original();tree.jieyaxian5hi();systemCpauEe");sygmLclb);br^ak;case□：//£示压缩比tree_xianshi();systemCpause");sysi=eni(''c:ls・');break;case七〃退出cout«"谢谢使用广<<endl;exit(C);default:cout "输入错误，请重新输/J"«endl;systemC'pause");s9stem(''cls・')；break;return0;主函数调用实现各个函数功能。⑶其它模块的算法描述创建哈弗曼树函数：uoidHufFnanTree::creat()//构造哈弗晏树<int1,k,il,i2,n=52,j;for(i=B;i<2*n-1;初始化huffTree[i].parent■-1;huffTree[i].lchild=-1;huffTree[i].rchild=-1;huffTree[i].Flag-8;>for(i=8;i<26;i++)//字母赋值<huffTree[i].weight.word=i+S5;for(j=0;j<26;j++)//字母赋值huffTree[j+26].ueight,uord=j+97;>For(k=n;k<2*n-1;k**)//建树<■select(k);=select(k);huffTree[k].weight.rare=huFFTree[i1].weight.rare+huFfTree[i2].weight.rarehuffTree[i1].parent=k;huffTree[12].parent・k:hufFTree[k].lehild=±1;huFFTree[k].rchild=12;>}此函数根据各个字母的权值建立哈弗曼树，其中select(int)是从还未挑选过的根结点中挑出权值最小的根结点的函数，挑出两个权值最小根结点后将她们的权值相力口，存到第k个结点中，并把k赋为它们的父母，把il，i2赋为k的左右还在，然后继续循环，直至找完所有结点。挑选权值最小的根节点函数：intHufFmanTree::selectCintK)〃找出所有根节点中权值最小的根节点{inti,n=52,min,rare=d9000;For(i=0;i<k;i*+)if((hufFTree[i]-weight.rare<rare)&&(tiufFTree[i]-flag==0))min=i;rare=huFfTree[i].weight.rare;}hufFTree[min].Flag=1;returnmin:此函数为找出权值最小的根结点函数，先将rare赋了一个不可能被超过的值，再将它和huffTree[]中的第一个结点的rare比较，如果huffTree.weight.rare比热热小，则它们交换，像这样循环下去，最后挑出的权值最小的根结点，再找过的结点标志一下，防止重复。据建好的哈弗曼树编码函数：uoidHuffnanTree::coding()//^jt出的哈弗曼树编码<inte,a=B,i,j,n=52,p,parent;for(i=0；i<n;i++)|{For(j=0;j<Max;j++)bianma[i].code[j]=-1;)bianma[i].uord=95;>for(i=B;i<2*n-1;i++){if((huffTree[i].flag!=2)蹦(huffTreefi].yezi==1)){e=Max-1;huffTree[i].flag=2;bianma[a].uord=huffTree[i].weight.uord;P=i；while(huffTree[p].parentT=-1)<parent=huffTree[p].parent;if(huffTree[parent].Ichild==p){bianma[a].code[e]=町e—：}elseif(hufFTree[parent].rchild==p)<bianma[a].code[e]=1;e—；}p=huffTree[p].parent;}a++：)此函数是根据已建好的哈弗曼树编码，每次找到树中的根结点，将其做个标志，从根结点网上查，如果此结点是父母的左孩子，在数组中存入0，如果此结点是父母的右孩子，在数组中存入1，直到它的父母值为-1为止，一直循环，直至把所有的根结点找完。压缩文件主要代码:for(i=8;i<zijie;i++)//压墙已编码的原文件，八个编码合为—个字节存入二进制文件{a=8;For(j=fl;j<8;j++)if(ya5uo[i][j]!=95)if(ija5uo[i][j]=='B'||ya5uo[i][j]=='1'){if(uasuo[i][j]=='1')(a=(a«1)|1;elseiF(yasuo[i][j]=='8'){a=a<<1;}}outfile.write((char*)&a,sizeof(a));}此函数为将编好码的内容压缩为二进制文件。如果遇到1则将a左移加1,如果遇到0则左移不加1，因为运用位操作左移后系统自动在最右位补0，这样0就存入了其中，如果左移一位再加1则1就存入了其中，这样每八位循环就可以将原来的内容都压缩了。解压文件主要代码：子岫=0;k<zijie; 解压压缩了的二进制文件<infile.read((char*)&a,sizeof(a));for(j=0;j<8;j**){if(m>=wei)<break;b=a;c=((b»1)«1);/Z先有移再左移将最右端的位变为。d=(a-c)*B;//得出最右涌的二戒葡莅a=a»1;if(d==侦)<jieya[f^]=0;//将解压后的信息先存入村浊口数组>elseif(d=='1')<jieya[f**]='1';//将解压后的信息先存入j让K□数组>m++:这个函数就是压缩函数的逆过程。译码主要代码：g(intz=0；z<wei*1；5“.从柳的根结点开始判断，左昉1,直到拔到叶子结点if(jieya[z]=='『)(i=huffTree[p].Ichild;p=huFFTree[p].ichild;if(huFfTree[i].weight.word!=B)<infilel«hufFIree[i].weight.word;P=q;))elseiF(jieya[2]=='1')(i=huFFTree[p].rchild;p=huFFTree[p].rchild;if(huFfTree[i].weight.word!=S){infilel«hufflree[i].weight.uord;P=q；)>1此函数为将编过码的信息译回原文，每次从根结点开始往下查找，如果遇到1则指向它的左孩子，如果遇到0则指向它的右孩子，这样继续下去直到所到结点存了字母信息，将字母信息读入译码文件，再回到根结点像这样循环下去，直到再没有0,1的信息了为止，就将编码文件译回原文件了。5、编码与调试分析1.编码与调试过程中遇到的问题及解决办法：【问题一】编码后的文件直接存为ASCII码文件，存储空间放大了。解决办法：将文件先压缩再存为二进制文件核心代码：=0：i<zijie;i++)〃压缩已编码的原文件，八个编码合为一个字节存入二进制文件<=0;for(j-0；j<8；j**)if(ija5ua[i][j]?=95)if(yasLO[l][J]==0-||yasuo[l][j]==T){iF(yasuo[i][j]==1'){a=(a«1)I1；>pIspiF(p^sua[i][j]=='O'){a-a<<1;>outFile.write((char*)&a,sizeoF(a));>【问题二】存为二进制的文件解码操作有问题解决办法：先将压缩顺序改变了，每八位倒着存【问题三】解压操作核心代码：gk=凯k<zijie;k++)//解压压缩了的二谜制文件{infile.read((char*)&a,sizeof(a));for(j=B;j<8;j++)<iF(m>=wei)break;}b=a;c=C(b»1)«1)；//先有移再左移将最有端的位变为日d=(a-o+■&■；//得出最端的二awa=a»1;iF(d=="O')jieya[f++]=10';//将解压后的信息先存人许妙口数组}elseiF(d==111)jie如[W]=W；〃