2022年2022年哈夫曼编码与译码 .pdf

建立 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：对文件进行名师资料总结-精品资料欢迎下载-名师精心整理-第 1 页，共 23 页 -解压缩。（2）流程图程序开始程序主界面读取文章并对字符编码哈夫曼编码信息文章编码文章译码退出程序显示文章编码保存文章编码返回上一界面显示文章编码的译码保存文章编码的译码程序结束文件压缩文件解压缩名师资料总结-精品资料欢迎下载-名师精心整理-第 2 页，共 23 页 -（3）程序数据要求及功能实现主界面1.读取文件并对字符进行编码2.哈夫曼编码信息名师资料总结-精品资料欢迎下载-名师精心整理-第 3 页，共 23 页 -3.文件编码名师资料总结-精品资料欢迎下载-名师精心整理-第 4 页，共 23 页 -（1）显示文件编码（2）保存文件编码4.文件译码名师资料总结-精品资料欢迎下载-名师精心整理-第 5 页，共 23 页 -（1）显示文章编码的译码（2）保存文章编码的译码5.文件压缩名师资料总结-精品资料欢迎下载-名师精心整理-第 6 页，共 23 页 -6.文件解压缩附：程序源代码/*File:HUFFMANFUNCTION.h*Author:Administrator*Created on 2011 年 12 月 19 日,下午 6:19*/#ifndef HUFFMANFUNCTION_H#define HUFFMANFUNCTION_H 名师资料总结-精品资料欢迎下载-名师精心整理-第 7 页，共 23 页 -#include#include#include#include#define max1 150#define max2 50#define max3 256 using namespace std;class Htnote public:char name;/字符名double weight;/权重int lchild;/左孩子int rchild;/右孩子int parent;/父亲Htnote()weight=0;lchild=-1;parent=-1;rchild=-1;class Name public:int num;/字符出现的次数char pname;/字符名double lweight;/权值Name()num=0;lweight=0;class GetName public:char namefmax2;int n;/字符的种类int sum;/字符的总数Name lettermax1;/存储字符信息的类的数组名师资料总结-精品资料欢迎下载-名师精心整理-第 8 页，共 23 页 -GetName()sum=0;n=0;void GetWeight()/得到字符的权值 for(int i=0;i n;i+)letteri.lweight=(double)letteri.num/sum;/出现的次数除总数得到权值 int ReadLetter()ifstream input;cout 请输入文件名：namef;input.open(namef);/打开文件if(input.fail()cout 该文件不存在！endl;return 0;char ch;ch=input.get();letter0.pname=ch;letter0.num+;sum+;while(!input.eof()/读取文件中的所有字符int tag=0;ch=input.get();for(int i=0;i n+1;i+)if(letteri.pname=ch)letteri.num+;sum+;tag=1;if(tag=0)n+;lettern.pname=ch;lettern.num+;sum+;sum-;名师资料总结-精品资料欢迎下载-名师精心整理-第 9 页，共 23 页 -input.close();GetWeight();/得到字符权值;class CodeNode/编码类 public:char ch;/存储字符char bitsmax1;/存储编码;class Function public:GetName L;int fn;/定义哈夫曼数组大小Htnote HuffmanTmax3;/哈夫曼数组CodeNode Codemax1;/字符编码数组Function()fn=0;void CharHuffmanTCoding()/编码功能实现 int i,f,c;char cdL.n+1;/暂时存储编码的数组int start;/编码读取起始位置cdL.n=0;for(i=0;i=0)if(HuffmanTf.lchild=c)/如果为左孩子，为0 cd-start=0;else/如果为右孩子，为1 cd-start=1;c=f;strcpy(Codei.bits,&cdstart);/将结果存入对应的编码数组中名师资料总结-精品资料欢迎下载-名师精心整理-第 10 页，共 23 页 -void OutputHuffmanTCode()cout 哈夫曼编码：endl;cout endl;cout 字符 t 权值 tt 哈夫曼编码 endl;for(int i=0;i L.n;i+)/输出字符，权值，哈夫曼编码 cout endl;cout HuffmanTi.name t HuffmanTi.weight t;cout Codei.bits;cout endl;cout endl;void InitHT()/哈夫曼初始化 L.ReadLetter();fn=(L.n)*2-1;for(int i=0;i fn;i+)if(i L.n)HuffmanTi.name=L.letteri.pname;HuffmanTi.weight=L.letteri.lweight;void SelectMin(int m,int&p1,int&p2)/选择最小的两个节点 int i,j;double m1,m2;m1=m2=1;p1=p2=-1;for(i=0;i m;i+)if(HuffmanTi.parent=-1&HuffmanTi.weight m1)/找出为访问过的最小权值节点 m2=m1;p2=p1;m1=HuffmanTi.weight;p1=i;else if(HuffmanTi.parent=-1&HuffmanTi.weight m2)/找出为访问的名师资料总结-精品资料欢迎下载-名师精心整理-第 11 页，共 23 页 -权值第二小结点 m2=HuffmanTi.weight;p2=i;void CreatHT()/建立哈夫曼树 int i,p1,p2;InitHT();for(i=L.n;i fn;i+)SelectMin(i,p1,p2);HuffmanTp1.parent=HuffmanTp2.parent=i;HuffmanTi.lchild=p1;HuffmanTi.rchild=p2;HuffmanTi.weight=HuffmanTp1.weight+HuffmanTp2.weight;int OutArticleCode()/显示文章编码/文章编码操作ifstream input;input.open(L.namef);if(input.fail()cout 文件不存在！endl;return 0;char ch;cout 文章编码如下：endl;while(!input.eof()ch=input.get();for(int i=0;i L.n;i+)if(Codei.ch=ch)cout Codei.bits;cout endl;input.close();int SaveArticleCode()/保存文章编码名师资料总结-精品资料欢迎下载-名师精心整理-第 12 页，共 23 页 -ofstream output;ifstream input;char namef1max2;input.open(L.namef);if(input.fail()cout 该文件不存在！endl;return 0;cout 请输入保存文章编码的文件名：namef1;output.open(namef1);char ch;while(!input.eof()ch=input.get();for(int i=0;i L.n;i+)if(Codei.ch=ch)for(int j=0;j strlen(Codei.bits);j+)output.put(Codei.bitsj);input.close();output.close();cout 保存完毕！endl;int OutTransCode()/文章译码操作ifstream input;char namefmax2;cout 请输入保存文章编码的文件名：namef;input.open(namef);if(input.fail()cout 该文件不存在！=0)c=HuffmanTc.lchild;if(HuffmanTc.lchild=-1)/判断是否到叶子 cout=0)c=HuffmanTc.rchild;if(HuffmanTc.rchild=-1)/判断是否到叶子 cout HuffmanTc.name;/输出字符c=2*L.n-2;/返回根节点 ch=input.get();cout endl;input.close();int SaveTransCode()/保存文章译码ofstream output;ifstream input;char namefmax2;char namef1max2;cout 请输入文章编码所在的文件名：namef;input.open(namef);if(input.fail()cout 该文件不存在！endl;return 0;cout 请输入保存文章译码的文件名：namef1;output.open(namef1);char ch;ch=input.get();int c=2*L.n-2;名师资料总结-精品资料欢迎下载-名师精心整理-第 14 页，共 23 页 -while(!input.eof()if(ch=0)if(HuffmanTc.lchild=0)c=HuffmanTc.lchild;if(HuffmanTc.lchild=-1)output.put(HuffmanTc.name);c=2*L.n-2;if(ch=1)if(HuffmanTc.rchild=0)c=HuffmanTc.rchild;if(HuffmanTc.rchild=-1)output.put(HuffmanTc.name);c=2*L.n-2;ch=input.get();input.close();output.close();cout 保存完毕！endl;int FileCompression()/文件压缩功能CreatHT();CharHuffmanTCoding();/保存编码ofstream output;ifstream input;char namef1=temp.txt;input.open(L.namef);if(input.fail()cout 该文件不存在！endl;return 0;output.open(namef1);char ch;while(!input.eof()ch=input.get();for(int i=0;i L.n;i+)if(Codei.ch=ch)名师资料总结-精品资料欢迎下载-名师精心整理-第 15 页，共 23 页 -for(int j=0;j strlen(Codei.bits);j+)output.put(Codei.bitsj);input.close();output.close();/压缩文件ofstream File1;ifstream File2;char namef2max2;cout 请输入压缩后的文件名：namef2;File1.open(namef2);File2.open(namef1);if(File2.fail()cout 该文件不存在！endl;return 0;char sh;char th;int i=0;char j=0;int count=0;while(!File2.eof()sh=File2.get();if(i 7&sh!=EOF)count=count+(sh-0)*pow(2,i);if(sh=0)j+;else j=0;i+;if(i=7)th=count;File1.put(th);i=0;count=0;if(sh=EOF)th=count;名师资料总结-精品资料欢迎下载-名师精心整理-第 16 页，共 23 页 -File1.put(th);File1.put(j);i=0;count=0;File1.close();File2.close();remove(namef1);cout 文件压缩完毕！endl;int FileDecompression()/文件解压缩/保存编码fstream output;fstream input;char namef2max2;char namef1=temp.txt;cout 请输入待解压缩的文件名：namef2;input.open(namef2,ios:in|ios:binary);output.open(namef1,ios:out|ios:binary);if(input.fail()cout 该文件不存在！endl;return 0;char ch;input.read(reinterpret_cast(&ch),sizeof(ch);char sh;char th=ch;input.read(reinterpret_cast(&ch),sizeof(ch);int count;char num;char t=0;char p=1;while(!input.eof()sh=th;th=ch;input.read(reinterpret_cast(&ch),sizeof(ch);count=sh;if(ch!=EOF)for(int i=0;i 7;i+)num=count%2+0;output.write(reinterpret_cast(&num),sizeof(num);名师资料总结-精品资料欢迎下载-名师精心整理-第 17 页，共 23 页 -count=count/2;if(ch=EOF)for(int i=0;i 7;i+)num=count%2+0;output.write(reinterpret_cast(&num),sizeof(num);count=count/2;if(count=0)break;for(int i=0;i th-0;i+)output.write(reinterpret_cast(&t),sizeof(t);output.close();input.close();/解压文件fstream File1;fstream File2;char namef3max2;cout 请输入解压后的文件名：namef3;File2.open(namef1,ios:in|ios:binary);File1.open(namef3);if(File2.fail()cout 该文件不存在！endl;return 0;cout 解压后的文件内容为：endl;File2.read(reinterpret_cast(&ch),sizeof(ch);int c=2*L.n-2;while(!File2.eof()if(ch=0)if(HuffmanTc.lchild=0)c=HuffmanTc.lchild;if(HuffmanTc.lchild=-1)cout HuffmanTc.name;File1.write(reinterpret_cast(&HuffmanTc.name),sizeof(HuffmanTc.name);c=2*L.n-2;名师资料总结-精品资料欢迎下载-名师精心整理-第 18 页，共 23 页 -if(ch=1)if(HuffmanTc.rchild=0)c=HuffmanTc.rchild;if(HuffmanTc.rchild=-1)cout HuffmanTc.name;File1.write(reinterpret_cast(&HuffmanTc.name),sizeof(HuffmanTc.name);c=2*L.n-2;File2.read(reinterpret_cast(&ch),sizeof(ch);cout endl;File2.close();File1.close();remove(namef1);cout 解压完毕！endl;#endif/*HUFFMANFUNCTION_H*/=/*File:main.cpp*Author:Administrator*Created on 2011 年 12 月 13 日,上午 9:09*/#include#include HUFFMANFUNCTION.h using namespace std;/*/int main(int argc,char*argv)Function*a=new Function;名师资料总结-精品资料欢迎下载-名师精心整理-第 19 页，共 23 页 -while(1)/主界面显示cout endl endl endl;cout endl;cout 【1】读取文章并对字符编码 endl;cout 【2】哈夫曼编码信息 endl;cout 【3】文章编码 endl;cout 【4】文章译码 endl;cout 【5】压缩文件 endl;cout 【6】解压缩文件 endl;cout 【7】退出程序 endl;cout =endl endl;char ch;cout 请选择功能：;cin ch;switch(ch)case 1:/读取文章并对字符编码 delete a;a=new Function;system(cls);a-CreatHT();a-CharHuffmanTCoding();cout 操作完毕！OutputHuffmanTCode();system(pause);system(cls);break;case 3:/文章编码 system(cls);while(1)名师资料总结-精品资料欢迎下载-名师精心整理-第 20 页，共 23 页 -cout endl;cout 1.显示文章编码 endl;cout 2.保存文章编码 endl;cout 3.返回上一界面 endl;char ch1;cout endl 请选择功能：;cin ch1;switch(ch1)case 1:/显示文章编码 system(cls);a-OutArticleCode();system(pause);system(cls);continue;case 2:/保存文章编码 system(cls);a-SaveArticleCode();system(pause);system(cls);continue;case 3:/返回上一界面 break;default:system(cls);cout 输入错误，请重新输入！endl;continue;system(cls);break;break;case 4:/文章译码名师资料总结-精品资料欢迎下载-名师精心整理-第 21 页，共 23 页 -system(cls);while(1)cout endl;cout 1.显示文章编码的译码 endl;cout 2.保存文章编码的译码 endl;cout 3.返回上一界面 endl;char ch1;cout endl 请选择功能：;cin ch1;switch(ch1)case 1:/显示文章编码的译码 system(cls);a-OutTransCode();system(pause);system(cls);continue;case 2:/保存文章编码的译码 system(cls);a-SaveTransCode();system(pause);system(cls);continue;case 3:/返回上一界面 break;default:system(cls);cout 输入错误，请重新输入！FileCompression();system(pause);system(cls);continue;case 6:system(cls);a-FileDecompression();system(pause);system(cls);continue;case 7:return 0;default:system(cls);cout 功能选择错误，请重新输入！endl;break;return 0;名师资料总结-精品资料欢迎下载-名师精心整理-第 23 页，共 23 页 -