哈夫曼编码解码

1、Huffman编/解码一问题描述1.题目内容：利用Huffman编码进行通信可以大大提高信道的利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据进行预先编码，在接收端进行解码。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/解码系统。2.基本要求：一个完整的系统应该具有以下功能： 1. I：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立Huffman树，并将它存入hfmTree中。 2. E：编码（Encoding）。利用已经建好的Huffman树（如果不在内存，则应从文件hfmTree中读取）

2、，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 3. D：解码（Decoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。 4. P：打印代码文件（Print）。将文件CodeFile以紧凑的格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。5. T：打印Huffman树（Tree Printing）。将已经在内存中的Huffman树以直观的形式（凹入的形式）显示在终端上，同时将此字符形式的Huffman树写入文件TreePrint中。 3.测试数据：用下表给

3、出的字符集和频度的实际统计数据建立Huffman树，并对以下报文进行编码和译码：“THIS PROGRAM IS MY FAVORITE”。 字符 A B C DE FG HI J K L M 频度 186 64 13 22 32103211547571 5 32 20字符 N O P Q R S T U V WX Y Z 频度 57 63 15 1 485180238 181 16 1 二需求分析1. 编码结果以文本的方式存储在文件CodeFile中。 2. 用户界面可以设计为“菜单”方式：显示上述功能符号，再加上“Q”，表示退出（quit）。请用户键入一个选择功能符。此功能执行完毕后再显示

4、此菜单，直至某次用户选择了Q为止。3. 在程序的一次执行过程中，第一次执行I，D，C命令后，Huffman树已经存在在内存中了，不必再读入。每次执行中不一定执行了I命令，因为文件hfmTree可能已经早已建好。4. 测试数据的权值（频度）应为正整数。三概要设计为实现上述程序功能，需要顺序栈一个抽象数据类型。1栈的抽象数据类型定义为：ADT Stack 数据对象：D=ai|aiCharSet,i=1,2.,n 数据关系:R1=|ai-1,aiD,i=2,.,n 基本操作: InitStack（&S）操作结果：构建一个空栈S。 DestroyStack(&S) 操作结果 ：销毁栈S。参数说明：栈S

5、已存在。ClearStack(&S) 操作结果:将栈清空。参数说明：栈S已存在。StackEmpty（S）操作结果: 若栈为空则返回TURE；否则返回FALSE。参数说明：栈S已存在。StackLength（S） 操作结果:返回栈中的元素个数，亦即栈的长度。参数说明：栈S已存在。GetTop(S,&e)操作结果:将e赋值为栈S的栈顶元素。参数说明：栈S已存在且非空。Push(&S, e) 操作结果:将e插入为栈S的新的栈顶元素。参数说明：栈S已存在。Pop(&S,&e) 操作结果:若栈非空，删除栈S的栈顶元素，并将值赋给e。参数说明：栈S已存在。StackTraverse(S) 操作结果:从栈

6、低到栈顶依次输出S的各个元素。参数说明：栈S已存在。2 程序包含三个模块：1）主函数模块2）初始化模块（包括了选择子模块）3）编码模块4）解码模块5）打印代码文件模块6）打印Huffman树模块（包括了打印子模块）各模块之间调用关系如图所示： 主函数模块编码模块解码模块打印代码模块打印树模块初始化模块四详细设计1元素类型、结点类型和指针类型。typedef char * * Huffmancode;哈夫曼编码的类型typedef char * Huffmanco;哈夫曼编码数组元素的类型typedef struct SqStack_typechar * elem;int stacksize;i

7、nt top;SqStack;typedef structchar *elem;int *value;SqNode,*SqNodelist;typedef struct HTNode_type 哈夫曼树结点类型int weight;int parent,lChild,rChild;HTNode,* HuffTree;. 主函数的伪码算法如下：void main()char a; int n=0,num=0 ; int flag=0; int msize=STACK_INIT_SIZE;num记录TOBETRAN中字母个数，flag用于标记是否已经初始化过用于记录用户输入的总的字符数，用于接受指

8、令HuffTree HT; Huffmancode HC; 编码数组SqNode data; 用于记录用户输入的字符集和频度cout请选择:endla;while(a!=Q)switch(a) caseI:if(!flag) Init(HT,n,data); flag=1;break;每次执行中不一定执行了 I 命令，因为文件 hfmTree 可能已经早已建好。 caseE:Encoding(HT,HC,n,data,num);break;caseD:Decoding(HT,HC,n,data,num);break;caseP:Print();break;caseT:TreePrinting(

9、HT,data,n);break;caseQ:break;default: coutDATA ERRORendl; cout请选择:endla; /main3. 初始化（Init）函数的伪码算法如下：void Init(HuffTree &HT,int &n,SqNode &data) 初始化，从终端读入字符集大小 n，以及n个字符和 n个权值，建立 Huffman 树，并将它存入 hfmTree 中。 int i,m,s1,s2; int v; char c; 用于计数，用于接收FILE *fp; 打开hfmTree.txt文件cout请输入字符集大小:n;data.elem=new cha

10、rn; 动态分配空间data.value=new intn;for(i=0;in;i+) 初始化data数组cout请输入第i+1个字符endl;c=getchar();data.elemi=c;cout请输入第i+1个字符的权值v;getchar(); 接收回车符data.valuei=v;m=n*2-1; 开始构造哈夫曼树HT=new HTNodem+1;for(i=1;i=m;i+) 0号空闲HTi.weight= i=n?data.valuei-1:0;HTi对应datai-1HTi.lChild=HTi.rChild=HTi.parent=0;for(i=n+1;i=m;i+)Sel

11、ect(HT,i,s1,s2);在HT1.i-1中选择parent为0且weight为最小的两个节点，其下标分别为s1和s2HTi.lChild=s1;HTi.rChild=s2;HTi.weight=HTs1.weight+HTs2.weight;HTs1.parent=i;HTs2.parent=i;fp=fopen(hfmTree.txt,wb);for(i=1;i=m;i+)fwrite(&HTi,sizeof(struct HTNode_type),1,fp);fclose(fp);/Init4. 编码（Encoding）函数的伪码算法如下：void Encoding(HuffTre

12、e HT,Huffmancode &HC,int n,SqNode data,int &num)利用已经建好的 Huffman 树（如果不在内存，则应从文件 hfmTree中读取），对文件 ToBeTran 中的正文进行编码，然后将结果存入文件 CodeFile 中。 SqStack S; char ch; int i,j; Huffmancode HCC;FILE *fp1,*fp2;InitStack(S,200);HC=new Huffmancon+1; 指针构成的数组HCC=new Huffmancon+1; 存储文件ToBeTran中的正文的编码for(i=1;i=n;i+)HCi=

13、new char20;HCCi=new char20;Coding(HT,2*n-1,HC,S); 哈夫曼树跟结点下标为2n-1fp1=fopen(ToBeTran.txt,r);ch=fgetc(fp1); 对文件ToBeTran中的正文进行编码while(ch!=-1)for(i=0;in;i+)if(data.elemi=ch) break;strcpy(HCC+num,HCi+1); HCC空闲不用ch=fgetc(fp1);fp2=fopen(CodeFile.txt,w);for(j=1;j0)if(HTroot.lChild=0)Push(S,0);strcpy(HCroot,S

14、.elem)；Pop(S,e)；Push(S,0);Coding(HT,HTroot.lChild,HC,S);Pop(S,e);Push(S,1);Coding(HT,HTroot.rChild,HC,S);Pop(S,e);/Coding5. 解码（Decoding）函数的伪码算法如下：void Decoding(HuffTree HT,Huffmancode HC,int n,SqNode data,int num)解码（Decoding）。利用已经建立好的Huffman树将文件CodeFile中的代码进行解码，结果存入TextFile中。FILE *fp1,*fp2; int i=0,

15、j,k=0; char m100,ch; char a20；数组暂存解码后的结果，数组用于读取代码fp1=fopen(CodeFile.txt,r);fp2=fopen(TextFile.txt,w);ch=fgetc(fp1);while(ch!=-1)ai+=ch;ai=0; 字符串结束标记for(j=1;j=n;j+)if(!strcmp(a,HCj)mk+=data.elemj-1; 译码成功后，将字母存入m数组i=0; 清空数组，从开始读入ch=fgetc(fp1);fwrite(&m0,k*sizeof(m0),1,fp2);fclose(fp1);fclose(fp2); /De

16、coding. 打印代码文件（Print）函数的伪码算法如下：void Print()FILE *fp1,*fp2; int i=0,j=0; 用于计数char ch,a1000; 数组控制格式输出fp1=fopen(CodeFile.txt,r);fp2=fopen(CodePrint.txt,w);ch=fgetc(fp1);while(ch!=-1)ai+=ch;ch=fgetc(fp1);fwrite(&a0,i*sizeof(a0),1,fp2);for(j=0;j=i;j+)for(j=0;ji;j+) if(!(j%50) coutendl;else coutaj; 每行50个代

17、码coutendl;fclose(fp1);fclose(fp2); /Print. 打印Huffman树（Tree Printing）函数的伪码算法如下：void TreePrinting(HuffTree HT,SqNode data,int n) int m=2*n-1,i=0； 引入参数tp(HT,m,n,i,data); 调用打印函数TreePrintingvoid tp(HuffTree HT,int m,int n,int i,SqNode data)本函数通过递归调用实现将内存中的Huffman树以直观的形式（凹入的形式）显示在终端上int j; if(m=0) return;

18、 递归结束条件for(j=0;ji;j+)cout ; 控制空格输出个数if(m=n) coutdata.elemm-1endl; 输出结点else coutmendl;tp(HT,HTm.lChild,n,i+1,data); 对左子树递归tp(HT,HTm.rChild,n,i+1,data); 对右子树递归tp7. 函数调用关系 main InitSelect EncodingCodingDecodingPrint TreePrinting tp五调试分析1.整个程序中比较复杂是不断从文件中读取和写入，因此为了简化，对哈夫曼编码在编码函数中分配定长空间，HCi=new char20，可根

19、据需要改变大小，此处已经够用。切记每组编码最后都放入/0,这样才可以循环调用fputs，使CodeFile.txt中为字符形式编码，开始时未注意到此点，导致CodeFile.txt中皆为乱码。2.为避免与初始条件“HTi.lChild=HTi.rChild=HTi.parent=0冲突，HT数组中HT0应空闲。开始为了节省空间把HT0也用上了，使其它函数无法运行，且使叶子节点无法判断。后改正，同时为了便于同步操作，HC中HC0也空闲。从而造成编码HCi与字符data.elemi-1相对应，由于偶尔忘记这点，导致在译码函数中费时调试。3.多次用到用字符数组a不断从编码文件中读取编码，进而译码，充

20、分利用了哈夫曼编码良好的前缀编码唯一性。但为了节省空间，从始至终只用了a一个数组，因此需要不断对前面的记录进行覆盖。4.打印哈夫曼树的函数时通过每次调用时赋值为i+1,而不是在函数体内设置i+，避免递归完左子树时，i值已变化。5.fopen只能打开同义文件夹中的文件，因此目标编码文件应与程序放在同一文件中，否则报错。6.算法的时空分析：main函数中用到了一个用于接受指令的字符型变量，一个标记是否已经初始化了的指示变量和代替宏定义常量的一个变量，因此所需辅助空间为O(3)；而每次回到主函数时只进行输出菜单、读入指令和调用函数三个语句，因此时间复杂度也为O(3)。Init函数中用到了一个计数变量

21、i，一个数组大小变量m，用于打开文件的指针，标记（parent为0且weight为最小）节点下标的指示变量s1和s2，以及用于接收用户输入数据的字符型和整型变量，因此所需辅助空间为O(7)；时间复杂度则为O(2n)。Select函数用到了计数变量 j，跟踪跟踪变量w,v以及标记变量 flag,flag2，故所需辅助空间为O(5)；时间复杂度则为O()。Encoding函数中用到了顺序栈，且初始开辟空间为InitStack(S,200)，用到了暂存表码序列的哈夫曼编码数组HCC和哈夫曼编码数组HC，均开辟空间为n+1；以及用于计数的i，j，从文件中读字符的c和两个文件指针，所需辅助空间为O(2n

22、+207);时间复杂度取决于要编码的文件和用户给定的字符集。 Decoding函数用到了从文件中读字符的变量，两个文件指针和用于计数的i，j，以及两个字符型数组（m100，可根据需要改动大小），一个用于暂时存放编码结果(a20)，另一个从编码文件CodeFile.txt 中依次读取编码。因此需辅助空间为O(125)。它的时间复杂度取决于要解码的文件和用户给定的字符集。 Print函数中用到从文件中读字符的变量,两个文件指针，用于计数的i.j和控制输出格式的字符数组a（a1000，可根据需要改动大小 )，故需辅助空间为O(1005)。它的时间复杂度为O(n)。TreePrinting函数只用到两

23、个整型变量，辅助空间为O(2)。时间复杂度为O(3)。tp函数只用到一个计数变量，辅助空间为O(1)。由于是递归调用，时间复杂度为O(2n-1)。六使用说明用户将要编码/译码的文件存入ToBeTran.txt中，且与程序放入同一文件夹。根据提示输入字符集和频度。其中频度为正整数，各数据之间以回车相隔。七测试结果测试数据：编码和译码：“THIS PROGRAM IS MY FAVORITE”。 字符 A B C DE FG HI J K L M 频度 186 64 13 22 32103211547571 5 32 20字符 N O P Q R S T U V WX Y Z 频度 57 63 1

24、5 1 485180238 181 16 1 请选择:I:初始化 E:编码 D:解码 P:打印代码文件 T:打印 Huffman 树 Q:退出I请输入字符集大小:27请输入第1个字符请输入第1个字符的权值186请输入第2个字符A请输入第2个字符的权值64请输入第3个字符B请输入第3个字符的权值13请输入第4个字符C请输入第4个字符的权值22请输入第5个字符D请输入第5个字符的权值32请输入第6个字符E请输入第6个字符的权值103请输入第7个字符F请输入第7个字符的权值21请输入第8个字符G请输入第8个字符的权值15请输入第9个字符H请输入第9个字符的权值47请输入第10个字符I请输入第10个字符的权值