哈夫曼编码译码

1、哈夫曼编码/译码 一、【实验内容】【问题描述】 利用哈夫曼编码进行住处通讯可以大大提高信道利用率,缩短住处传输时间,降低成本,但是,这要求在发送端通过一个编码系统将传输的数据预先编码,在接收端通过一个译码系统对传来的数据进行译码(复原),对于双向传输信息的信道,每端都一个完整的编码译码系统,试为这样的住处收发站写一个哈夫曼友的编码译码系统.【基本要求】：一个完整的系统应以下功能:(1) I. 初始化(Initialization)。从终端读入字符集大小n，以及n个字符和n个权值,建立哈夫曼树,并将它存放在文件hfmTree中.(2) E. 编码(Encoding)。利用已建立好的哈夫曼树（如不

2、在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中.(3) D. 译码(Decoding)。利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,将译码结果存入文件TextFile中. (4) P. 印文件代码(Print)。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T. 印哈夫曼树(TreePrinting)。将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，同时将此字符形式的哈夫曼树写入文件Tr

3、eePrint中。测试数据：(1)利用教科书例6-2中的数据调试程序。(2)用下表给出的字符集和频度的计数据建立哈曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.。字符 A B C D E F G H I J K L M频数186 64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z频数57 63 15 1 48 51 80 23 8 18 1 16 1 二、实验目的树型结构是一种应用极为广泛的非线性数据结构,也是本课程的重点内容,哈夫曼树(最优二叉树)是树型结构的典型应用

4、,本次实验突出了数据结构加操作的程序设计观点,希望能根据树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构的非线性特点,熟悉各种存储结构的特性,达到如何应用树型结构解决具体问题的目的.三、实验文档： 哈夫曼编码/译码一、需求分析1、利用哈夫曼编码进行信息通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（既可以双向传输信息的信道），每端都需要一个完整的编/译码系统。本次设计就是为这样的信息收发站写的一个哈夫曼的编/译码器。本实验要求：2、本演示程序中，用户可以输入

5、键盘中的任意字符，长度为任意长，字符输入顺序不限，且允许出现重码3、演示程序以用户与计算机的对话方式执行，即在计算机终端上显示“提示信息”之后，由用户在键盘上输入演示程序中规定的运算命令，相应的输入数据（可虑去输入中的非法字符）和运算结果显示在其后。4、本演示程序中，当用户选择的功能错误时，系统会输出相应的提示。5、在本系统中，用户可以对任意长的字符串可进行编码/译码。6、程序执行的命令包括：1) 初始化(I)2) 编码(E)3) 译码(D) 4) 印代码文件(P)5) 印哈夫曼树(T)6) 退出(Q)、测试数据：（）利用教科书例6-2中的数据调试程序。（）用下表给出的字符集和频度的计数据建立

6、哈曼树,并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”.。字符 A B C D E F G H I J K L M频数186 64 13 22 32 103 21 15 47 57 1 5 32 20字符N O P Q R S T U V W X Y Z频数57 63 15 1 48 51 80 23 8 18 1 16 1 二、概要设计为实现上述程序功能，应以指针存储结点。为此，需要定义一个抽象数据类型。1. 抽象数据类型定义为：ADT HuffmanTree数据对象：D=ai| aiCharSet,i=1,2,n, n0数据关系：R= ai-1, a

7、iD, ai-1ai ,i=2，3，n基本操作P：HuffmanTree(); 构造函数 HuffmanTree(); 析构函数Initialization(int WeightNum);操作结果：构造哈夫曼树。Encoder()初始条件：哈夫曼树已存在或者哈夫曼树已存到文件中。操作结果：对字符串进行编码Decoder();初始条件：哈夫曼树已存在且已编码。操作结果：对二进制串进行译码Print()初始条件：编码文件已存在。操作结果：把已保存好的编码文件显示在屏幕TreePrinting()初始条件：哈夫曼树已存在。操作结果：将已在内存中的哈夫曼树以直观的方式显示在终端上2.本程序包含三个模块

8、：1)主程序模块：void main() 初始化；do 接受命令； 处理命令；while(“命令”=”退出”)2)、建树模块实现定义的抽象数据类型3)、编/译码模块实现字符串的编/译码各模块之间的调用关系如下： 主程序模块 建树模块 编/译码模块三、详细设计程序代码如下/ 程序名：HuffmanTree.h/ 程序功能：哈夫曼树类的头文件(并用其来实现编/译码)/ 作者：刘伟高/ 日期：2006.11.27/ 版本：1.0/对应类实现文件: HuffmanTree.cpp/对应主程序文件: main.cpp#include#include#includeusing namespace std;

9、struct HuffmanNode /定义哈夫曼树各结点int weight; /存放结点的权值，假设只考虑处理权值为整数的情况int parent; /记录结点父亲位置，-1表示为根结点，否则表示为非根结点int lchild,rchild; /分别存放该结点的左、右孩子的所在单元的编号;class HuffmanTree /建立哈夫曼树类private:HuffmanNode *Node; /哈夫曼树中结点的存储结构char *Info; /用来保存各字符信息int LeafNum; /树中的叶子结点总数public:HuffmanTree(); /构造函数HuffmanTree();

10、/析构函数void Initialization(int WeightNum); /初始化函数：根据WeightNum个权值建立一棵哈夫曼树void Encoder(); /编码函数：利用构造好的哈夫曼树对字符进行编码void Decoder(); /译码函数：对二进制串进行译码void Print(); /印文件函数：把已保存好的编码文件显示在屏幕void TreePrinting(); /印哈夫曼树函数：将已在内存中的哈夫曼树以直观的方式显示在终端上;/ 程序名：HuffmanTree.cpp/ 程序功能：实现哈夫曼树类的源文件(并用其来实现编/译码)/ 作者：刘伟高/ 日期：2006.1

11、1.27/ 版本：1.0#includeHuffmanTree.h#includeusing namespace std;/ 构造函数/ 函数功能：将结点指针初始化为NULL/ 函数参数：无/ 参数返回值：无HuffmanTree:HuffmanTree()Node=NULL; /将树结点初始化为空 Info=NULL; /将字符数组初始化为空LeafNum=0; /将叶子数初始化为0/ 析构函数/ 函数功能：将所有结点的空间释放/ 函数参数：无/ 参数返回值：无HuffmanTree:HuffmanTree()delete Node; /释放结点空间delete Info; /释放字符存储空

12、间/ 初始化函数/ 函数功能：从终端读入字符集大小n，以及n个字符和n个权值,/ 建立哈夫曼树,并将它存放在文件hfmTree中./ 函数参数：int WeightNum表示代码个数/ 参数返回值：无 void HuffmanTree:Initialization(int WeightNum) /初始化int i,j,pos1,pos2,max1,max2; /Node=new HuffmanNode2*WeightNum-1; /WeightNum权值对应的哈夫曼树中的结点总数为2*WeightNum-1个Info=new char2*WeightNum-1;for(i=0;iWeightN

13、um;i+)cout请输入第i+1个字符值;getchar(); /丢弃字符t与nInfoi=getchar(); /输入一个字符,主要是考虑输入空格而采用这种形式的getchar();coutNodei.weight; /输入权值Nodei.parent=-1; /为根结点Nodei.lchild=-1; /无左孩子Nodei.rchild=-1; /无右孩子for(i=WeightNum;i2*WeightNum-1;i+) /表示需做WeightNum-1次合并pos1=-1;pos2=-1; /分别用来存放当前最小值和次小值的所在单元编号 max1=32767; /32767为整型数的

14、最大值 max2=32767; /分别用来存放当前找到的最小值和次小值 for(j=0;ji;j+) /在跟节点中选出权值最小的两个if(Nodej.parent=-1) /是否为根结点if(Nodej.weightmax1) /是否比最小值要小 max2=max1; /原最小值变为次小值max1=Nodej.weight; /存放最小值pos2=pos1; /修改次小值所在单元编号pos1=j; /修改最小值所在单元编号elseif(Nodej.weightmax2) /比原最小值大但比原次小值要小max2=Nodej.weight; /存放次小值pos2=j; /修改次小值所在的单元编号

15、/forNodepos1.parent=i; /修改父亲位置Nodepos2.parent=i;Nodei.lchild=pos1; /修改儿子位置Nodei.rchild=pos2;Nodei.parent=-1; /表示新结点应该是根结点Nodei.weight=Nodepos1.weight+Nodepos2.weight; /forLeafNum=WeightNum;char ch;coutch;if(ch=y|ch=Y)ofstream fop; /以二进制方式打开hfmTree.dat文件，并当重新运行时覆盖原文件fop.open(hfmTree.dat,ios:out|ios:b

16、inary|ios:trunc);if(fop.fail() /文件打开失败cout文件打开失败！n;fop.write(char*)&WeightNum,sizeof(WeightNum); /写入WeightNumfor(i=0;iWeightNum;i+) /把各字符信息写入文件fop.write(char*)&Infoi,sizeof(Infoi);flush(cout);for(i=0;i2*WeightNum-1;i+) /把个节点内容写入文件fop.write(char*)&Nodei,sizeof(Nodei);flush(cout);fop.close(); /关闭文件cou

17、t哈夫曼树已构造完成。n;/Initialization/ 编码函数/ 函数功能：利用已建立好的哈夫曼树（如不在内存，则从文件hfmTree中读入），/ 对文件ToBeTran中的正文进行编码,然后将结果代码存(传输)到文件CodeFile中./ 函数参数：无/ 参数返回值：无void HuffmanTree:Encoder()if(Node=NULL) /哈夫曼树不在内存，从文件hfmTree中读入ifstream fip; /以二进制方式打开hfmTree.dat文件fip.open(hfmTree.dat,ios:binary|ios:in);if(fip.fail() /文件打开失败c

18、out文件打开失败！n;return; /结束本函数fip.read(char*)&LeafNum,sizeof(LeafNum); /读取叶子数Info=new charLeafNum; Node=new HuffmanNode2*LeafNum-1;for(int i=0;iLeafNum;i+) /读取字符信息fip.read(char*)&Infoi,sizeof(Infoi);for(i=0;i2*LeafNum-1;i+) /读取结点信息fip.read(char*)&Nodei,sizeof(Nodei);char *Tree; /用于存储需编码内容int i=0,num;cha

19、r Choose; /让用户选择读取文件或重新输入需编码内容coutChoose;if(Choose=1) /读取文件ToBeTran.txtifstream fip1(ToBeTran.txt);if(fip1.fail() /文件不存在cout文件打开失败!n;return; /结束本函数char ch;int k=0;while(fip1.get(ch) k+; /计算CodeFile中代码长度 fip1.close(); Tree=new chark+1;ifstream fip2(ToBeTran.txt);k=0; while(fip2.get(ch)Treek=ch; /读取文件

20、内容，并存到Tree中k+;fip2.close();Treek=0; /结束标志cout需编码内容为:;coutTreeendl;/if(Choose=1)else /Choose!=1,重新输入string tree; /用于输入需编码内容，由于string类对象可以输入任意长度， /所以先利用这个对象输入，再转存在Tree中 cin.ignore();cout请输入需要编码的内容(可输入任意长，结束时请按2下回车):n;getline(cin,tree,n); /输入任意长字符串， /getline以回车(n)作为结束符，第一次按回车表示字符串结束，第二次按回车才开始输出。while(t

21、reei!=0)i+;num=i; /计算tree长度i=0;Tree=new charnum+1;while(treei!=0) /将tree中的字符转存到Tree中Treei=treei;i+; Treei=0; /结束标志符ofstream fop(CodeFile.dat,ios:trunc); /存储编码后的代码,并覆盖原文件i=0;int k=0;char *code;code=new charLeafNum; /为所产生编码分配容量为LeafNum的存储空间 /因为不等长编码中最长的编码一定不会超过要求编码的字符个数while(Treek!=0) /对每一个字符编码int j,s

22、tart=0;for(i=0;iLeafNum;i+)if(Infoi=Treek) /求出该文字所在单元的编号break; j=i;while(Nodej.parent!=-1) /结点j非树根j=Nodej.parent; /非结点j的双亲结点if(Nodej.lchild=i) /是左子树，则生成代码0codestart+=0;else /是右子树，则生成代码1codestart+=1;i=j;codestart=0; /置串结束符 for(i=0;istart/2;i+) /对二进制序列进行逆置j=codei;codei=codestart-i-1;codestart-i-1=j; i

23、=0;while(codei!=0) /存储代码fopcodei;i+;k+;fop.close();cout已编码！且存到文件CodeFile.dat中！nn; /Encode/ 译码函数/ 函数功能：利用已建好的哈夫曼树,对传输到达的CodeFile中的数据代码进行译码,/ 将译码结果存入文件TextFile中./ 函数参数：无/ 参数返回值：无void HuffmanTree:Decoder()int i=0,k=0;int j=LeafNum*2-1-1; /表示从根结点开始往下搜索char* BitStr;ifstream fip1(CodeFile.dat); /利用已建好的哈夫曼

24、树将文件CodeFile中的代码进行译码if(fip1.fail() /文件打开失败，还未编码cout 请先编码！n;return;cout经译码,原内容为:;char ch;while(fip1.get(ch) k+; /计算CodeFile中代码长度fip1.close(); BitStr=new chark+1;ifstream fip2(CodeFile.dat);k=0;while(fip2.get(ch)BitStrk=ch; /读取文件内容k+;fip2.close(); BitStrk=0; /结束标志符if(Node=NULL) /还未建哈夫曼树 cout请先编码!n; re

25、turn;ofstream fop(TextFile.dat); /将字符形式的编码文件写入文件CodePrin中while(BitStri!=0)if(BitStri=0)j=Nodej.lchild; /往左走elsej=Nodej.rchild; /往右走if(Nodej.rchild=-1) /到达叶子结点coutInfoj; /输出叶子结点对应的字符j=LeafNum*2-1-1; /表示重新从根结点开始往下搜索fopInfoj; /存入文件/if、i+;/whilefop.close();coutn译码成功且已存到文件TextFile.dat中！nn;/Decoder/ 印文件代码

26、函数/ 函数功能：将文件CodeFile以紧凑格式显示在终端上，/ 每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。/ 函数参数：无/ 参数返回值：无void HuffmanTree:Print()char ch;int i=1;ifstream fip(CodeFile.dat); /读取文件ofstream fop(CodePrin.dat); /存储文件if(fip.fail()cout没有文件，请先编码！n;return;while(fip.get(ch)coutch; /读取文件内容fopch; /存到文件中if(i=50) /每行输出50个字符coutendl

27、;i=0;i+;coutendl;fip.close(); /关闭CodeFile.dat文件fop.close(); /关闭CodePrin.dat文件/ 印哈夫曼树函数/ 函数功能：将已在内存中的哈夫曼树以直观的方式(树或凹入表的形式)显示在终端上，/ 同时将此字符形式的哈夫曼树写入文件TreePrint中。/ 函数参数：无/ 参数返回值：无void HuffmanTree:TreePrinting()if(Node=NULL) /未建立哈夫曼树cout请先建立哈夫曼树！n;return;ofstream fop(TreePrint.dat);cout结点位置(权值) 编码 左孩子 编码右

28、孩子(表示叶子)n;fop结点位置(权值) 编码 左孩子 编码LeafNum-1;i-) /输出哈夫曼树couti(Nodei.weight)-1-Nodei.lchild(NodeNodei.lchild.weight)-0-Nodei.rchild(NodeNodei.rchild.weight)endl;fopi(Nodei.weight)-1-Nodei.lchild(NodeNodei.lchild.weight)-0-Nodei.rchild(NodeNodei.rchild.weight)=0;i-)couti:Nodei.weight(Infoi)-n;fopi:Nodei.w

29、eight(Infoi)-n;/ 程序名：main.cpp/ 程序功能：主函数源文件/ 作者：刘伟高/ 日期：2006.11.27/ 版本：1.0#includeHuffmanTree.h#include#include/ 主函数/参数返回值：无int main()cout 欢迎使用哈夫曼码的编/译码系统!n;cout 刘伟高n;cout 版权所有,盗版必究n; cout在此系统中可以进行以下操作:n;cout(1) 初始化(I);n;cout(2) 编码(E);n;cout(3) 译码(D);n;cout(4) 印代码文件(P);n;cout(5) 印哈夫曼树(T)n;cout(6) 退出(

30、Q)nn;HuffmanTree huftree; /定义哈夫曼树对象int weight;char Choose;while(1)coutChoose;switch(Choose)case I:case i:coutweight;huftree.Initialization(weight); /初始化哈夫曼树break;case E:case e:huftree.Encoder();break;case D:case d:huftree.Decoder();break;case P:case p:huftree.Print();break;case T:case t:huftree.TreePrinting();break;case Q:case q:coutn *感谢使用本系统!*nn; sys