哈夫曼编码与译码(附源码)

建立Huffman树进行编码和译码的设计郝萌1100300423哈尔滨工业大学计算机科学与技术学院1003104班摘要：建立一个简易的系统，对于给定的一篇英文文章，统计字符出现的概率，并根据概率建立Huffman树，利用Huffman编码对文章进行编码和译码。掌握Huffman树的建立与应用，并进一步熟练掌握程序的设计流程。关键词：Huffman树Huffman编码文章译码文件压缩解压缩1.引言：给定一篇文章，统计字符出现的概率，根据概率建立哈夫曼树，并进行哈夫曼编码，进而可以利用哈夫曼编码对文章进行编码与译码和文件压缩、解压缩等操作。2.程序设计流程(1)文字表述开始进入功能选择界面，包含五种操作：1.读取文章并对字符编码，2.哈夫曼编码信息，3.文章编码，4.文章译码，5.文件压缩，6.文件解压缩，7.退出程序。操作1：给定一篇文章，统计字符出现的概率，并根据概率建立Huffman树，并利用Huffman树对字符进行Huffman编码。操作2：显示Huffman编码信息，包括字符，字符出现的概率，Huffman编码。操作3：对文章进行译码，显示译码信息，并保存。操作4：对文章进行译码，显示并保存。操作5：对文件进行压缩，每7位二进制序列对应一个ASCII码。操作6：对文件进行解压缩。（2）流程图程序开始程序主界面读取文章并对字符编码哈夫曼编码信息文章编码文章译码退出程序显示文章编码保存文章编码返回上一界面显示文章编码的译码保存文章编码的译码程序结束文件压缩文件解压缩（3）程序数据要求及功能实现主界面1.读取文件并对字符进行编码2.哈夫曼编码信息3.文件编码（1）显示文件编码（2）保存文件编码4.文件译码（1）显示文章编码的译码（2）保存文章编码的译码5.文件压缩6.文件解压缩附：程序源代码/**File:HUFFMANFUNCTION.h*Author:Administrator**Createdon2011年12月19日,下午6:19*/#ifndefHUFFMANFUNCTION_H#defineHUFFMANFUNCTION_H#includecstdlib#includeiostream#includefstream#includemath.h#definemax1150#definemax250#definemax3256usingnamespacestd;classHtnote{public:charname;//字符名doubleweight;//权重intlchild;//左孩子intrchild;//右孩子intparent;//父亲Htnote(){weight=0;lchild=-1;parent=-1;rchild=-1;}};className{public:intnum;//字符出现的次数charpname;//字符名doublelweight;//权值Name(){num=0;lweight=0;}};classGetName{public:charnamef[max2];intn;//字符的种类intsum;//字符的总数Nameletter[max1];//存储字符信息的类的数组GetName(){sum=0;n=0;}voidGetWeight()//得到字符的权值{for(inti=0;in;i++){letter[i].lweight=(double)letter[i].num/sum;//出现的次数除总数得到权值}}intReadLetter(){ifstreaminput;cout请输入文件名：endl;cinnamef;input.open(namef);//打开文件if(input.fail()){cout该文件不存在！endl;return0;}charch;ch=input.get();letter[0].pname=ch;letter[0].num++;sum++;while(!input.eof()){//读取文件中的所有字符inttag=0;ch=input.get();for(inti=0;in+1;i++){if(letter[i].pname==ch){letter[i].num++;sum++;tag=1;}}if(tag==0){n++;letter[n].pname=ch;letter[n].num++;sum++;}}sum--;input.close();GetWeight();//得到字符权值}};classCodeNode//编码类{public:charch;//存储字符charbits[max1];//存储编码};classFunction{public:GetNameL;intfn;//定义哈夫曼数组大小HtnoteHuffmanT[max3];//哈夫曼数组CodeNodeCode[max1];//字符编码数组Function(){fn=0;}voidCharHuffmanTCoding()//编码功能实现{inti,f,c;charcd[L.n+1];//暂时存储编码的数组intstart;//编码读取起始位置cd[L.n]='\0';for(i=0;iL.n;i++){Code[i].ch=HuffmanT[i].name;//字符信息start=L.n;//起始位置c=i;while((f=HuffmanT[c].parent)=0){if(HuffmanT[f].lchild==c)//如果为左孩子，为‘0’{cd[--start]='0';}else//如果为右孩子，为‘1’{cd[--start]='1';}c=f;}strcpy(Code[i].bits,&cd[start]);//将结果存入对应的编码数组中}}voidOutputHuffmanTCode(){cout哈夫曼编码：endl;cout——————————————————————endl;cout字符\t权值\t\t哈夫曼编码endl;for(inti=0;iL.n;i++)//输出字符，权值，哈夫曼编码{cout——————————————————————endl;coutHuffmanT[i].name\tHuffmanT[i].weight\t;coutCode[i].bits;coutendl;}cout——————————————————————endl;}voidInitHT()//哈夫曼初始化{L.ReadLetter();fn=(L.n)*2-1;for(inti=0;ifn;i++){if(iL.n){HuffmanT[i].name=L.letter[i].pname;HuffmanT[i].weight=L.letter[i].lweight;}}}voidSelectMin(intm,int&p1,int&p2)//选择最小的两个节点{inti,j;doublem1,m2;m1=m2=1;p1=p2=-1;for(i=0;im;i++){if(HuffmanT[i].parent==-1&&HuffmanT[i].weightm1)//找出为访问过的最小权值节点{m2=m1;p2=p1;m1=HuffmanT[i].weight;p1=i;}elseif(HuffmanT[i].parent==-1&&HuffmanT[i].weightm2)//找出为访问的权值第二小结点{m2=HuffmanT[i].weight;p2=i;}}}voidCreatHT()//建立哈夫曼树{inti,p1,p2;InitHT();for(i=L.n;ifn;i++){SelectMin(i,p1,p2);HuffmanT[p1].parent=HuffmanT[p2].parent=i;HuffmanT[i].lchild=p1;HuffmanT[i].rchild=p2;HuffmanT[i].weight=HuffmanT[p1].weight+HuffmanT[p2].weight;}}intOutArticleCode()//显示文章编码{//文章编码操作ifstreaminput;input.open(L.namef);if(input.fail()){cout文件不存在！endl;return0;}charch;cout文章编码如下：endl;while(!input.eof()){ch=input.get();for(inti=0;iL.n;i++){if(Code[i].ch==ch)coutCode[i].bits;}}coutendl;input.close();}intSaveArticleCode()//保存文章编码{ofstreamoutput;ifstreaminput;charnamef1[max2];input.open(L.namef);if(input.fail()){cout该文件不存在！endl;return0;}cout请输入保存文章编码的文件名：endl;cinnamef1;output.open(namef1);charch;while(!input.eof()){ch=input.get();for(inti=0;iL.n;i++){if(Code[i].ch==ch){for(intj=0;jstrlen(Code[i].bits);j++){output.put(Code[i].bits[j]);}}}}input.close();output.close();cout保存完毕！endl;}intOutTransCode(){//文章译码操作ifstreaminput;charnamef[max2];cout请输入保存文章编码的文件名：endl;cinnamef;input.open(namef);if(input.fail()){cout该文件不存在！endl;return0;}charch;ch=input.get();intc=2*L.n-2;while(!input.eof()){if(ch=='0')//遇0搜索左子树{if(HuffmanT[c].lchild=0){c=HuffmanT[c].lchild;}if(HuffmanT[c].lchild==-1)//判断是否到叶子{coutHuffmanT[c].name;//输出字符c=2*L.n-2;//返回根节点}}if(ch=='1')//遇1搜索右子树{if(HuffmanT[c].rchild=0){c=HuffmanT[c].rchild;}if(HuffmanT[c].rchild==-1)//判断是否到叶子{coutHuffmanT[c].name;//输出字符c=2*L.n-2;//返回根节点}}ch=input.get();}coutendl;input.close();}intSaveTransCode(){//保存文章译码ofstreamoutput;ifstreaminput;charnamef[max2];charnamef1[max2];cout请输入文章编码所在的文件名：endl;cinnamef;input.open(namef);if(input.fail()){cout该文件不存在！endl;return0;}cout请输入保存文章译码的文件名：endl;cinnamef1;output.open(namef1);charch;ch=input.get();intc=2*L.n-2;while(!input.eof()){if(ch=='0'){if(HuffmanT[c].lchild=0){c=HuffmanT[c].lchild;}