哈夫曼编码译码

《数据结构》课程设计报告设计题目哈夫曼编码译码学院名称信息工程学院专业班级计算机科学与技术2班姓名学号摘要Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。它的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。本文根据Huffman编码原理，在详细设计中，根据权值和最小的根本原那么，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点Node类，算法SuanFa类以及主类JieMian类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。在完成Huffman编码后，我们利用其构建的哈夫曼编码树来进行译码。与编码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比拟，译出一个字符后，循环比拟下一个字符的编码，直到所有二进制码全部译出为止。在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译码系统。关键词：Huffman编码树；最优二叉树；编码；译码AbstractHuffmancodingisaencodingofvariablelengthandaspecialtransformationformofthebinarytree.Itsprincipleis:thecodethatbeusedmoreoftenwillbechangedintothecodeofshorterlengths,whilethecodesthatbeusedlessoftencanbetransformedintothecodeoflongerlengthsandtheuniquesolutionofcodingwillbekept.AccordingtothetheoryofHuffmancoding,firstlyweenterthecharactersetwhichwillbeusedtocodingandtheirweights.Secondly,accordingtothefundanmentalprinciplethatthesumoftheweightsneedstobethesmallest,theprogramdesignsHuffmantreeinaccordancewiththeseclasswhichareinitializedintheoutlinesuchasclassNode,classSuanFa,andclassJieMian.Atlast,thecomputerwilloutputHuffmancodingonuserinterface.Andthen,weusetheHuffmancodingtreetodecodingafterthecompletionofHuffmancodingtree.Herearedifferencewithencodingprocess.Wewillcomparethebinarystringthattheuserinputwiththecharactersetonebyoneduringtheprocesssofdecoding.Andthen,thecycleofthenextcharacterencodingwillcontinuewhichisbasedonthecompletionoftranslationofacharacter.Itwillbefinisheduntilallthebinarycodeistranslated.Duringtheprocessofcodinganddecoding,weencountermanyproblems,suchastheproblemonarithmeticandgrammar.However,wetryourbesttosolvetheseproblemsthroughconstantanalysisanddebugging.Eventually,weachievethegoalthatestablishacompletesystemoncodinganddecodingsuccessfully.KeyWords：Huffmancodingtree；optimalbinarytree；coding；decoding目录摘要………………IABSTRACT……………………II绪论……………1.1设计目的……………………11.2问题描述……………………11.3设计思想……………………12.概要设计……………23.需求分析……………44.详细设计……………55.测试数据与实验结果………………106.课程设计总结………14参考文献………………15附录〔源程序代码〕…………………16绪论1.1设计目的学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。本课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中根本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，使同学的程序设计与调试水平有一个明显的提高。1.2问题描述利用赫夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输本钱。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码〔复原〕。对于双工信道〔即可以双向传输信息的信道〕，每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。1.3.设计思想哈夫曼编码(HuffmanCoding)是一种编码方式，以哈夫曼树─即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符〔例如某文件中的一个符号〕进行编码。这种方法是由David.A.Huffman开展起来的。例如，在英文中，e的出现概率很高，而z的出现概率那么最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z那么可能花去25个位〔不是26〕。用普通的表示方法时，每个英文字母均占用一个字节〔byte〕，即8个位。二者相比，e使用了一般编码的1/8的长度，z那么使用了3倍多。倘假设我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。2.概要设计总体流程图如下列图开始开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I<2*N?I++编码为1结束否否否右子是否为空是是否否是是是2.1哈夫曼树的建立赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n－1次合并，所以共产生n－1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的赫夫曼树中一共有2n－1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n--1的一维数组来存储赫夫曼树中的结点。2.2哈夫曼编码要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实际需要定义的类型如下：typedetstruct{charch;//存放编码的字符charbits[N＋1];//存放编码位串intlen;//编码的长度}CodeNode;//编码结构体类型2.3代码文件的译码译码的根本思想是：读文件中编码，并与原先生成的赫夫曼编码表比拟，遇到相等时，即取出其对应的字符存入一个新串中。3.需求分析3.1：初始化〔Initialization〕。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。输出哈夫曼树，及各字符对应的编码。3.2：编码〔Encoding〕与译码〔Decoding〕。3.2.1编码〔Encoding〕。利用已建好的哈夫曼树〔如不在内存，那么从文件htmTree中读入〕，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。3.2.2译码〔Decoding〕。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。3.2.3印代码文件〔Print〕。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。3.3：印哈夫曼树〔TreePrinting〕。将已在内存中的哈夫曼树以直观的方式〔树或凹入表形式〕显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。4.详细设计4.1哈夫曼树的存储结构描述typedefstruct{ unsignedintweight; unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;4.2哈弗曼树的算法voidCreateHT(HTNodeht[],intn)//调用输入的数组ht[],和节点数n{inti,k,lnode,rnode;intmin1,min2;for(i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//所有结点的相关域置初值-1for(i=n;i<2*n-1;i++)//构造哈夫曼树 {min1=min2=32767;//int的范围是-32768—32767lnode=rnode=-1;//lnode和rnode记录最小权值的两个结点位置for(k=0;k<=i-1;k++){ if(ht[k].parent==-1)//只在尚未构造二叉树的结点中查找 {if(ht[k].weight<min1)//假设权值小于最小的左节点的权值 {min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k; }elseif(ht[k].weight<min2) {min2=ht[k].weight;rnode=k; } } }ht[lnode].parent=i;ht[rnode].parent=i;//两个最小节点的父节点是iht[i].weight=ht[lnode].weight+ht[rnode].weight;//两个最小节点的父节点权值为两个最小节点权值之和ht[i].lchild=lnode;ht[i].rchild=rnode;//父节点的左节点和右节点 }}4.3哈弗曼编码voidCreateHCode(HTNodeht[],HCodehcd[],intn){inti,f,c;HCodehc;for(i=0;i<n;i++)//根据哈夫曼树求哈夫曼编码{hc.start=n;c=i;f=ht[i].parent;while(f!=-1)//循序直到树根结点结束循环{if(ht[f].lchild==c)//处理左孩子结点hc.cd[hc.start--]='0';else//处理右孩子结点hc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;//start指向哈夫曼编码hc.cd[]中最开始字符hcd[i]=hc;}}voidDispHCode(HTNodeht[],HCodehcd[],intn)//输出哈夫曼编码的列表{inti,k;printf("输出哈夫曼编码:\n");for(i=0;i<n;i++)//输出data中的所有数据，即A-Z{printf("%c:\t",ht[i].data);for(k=hcd[i].start;k<=n;k++)//输出所有data中数据的编码{printf("%c",hcd[i].cd[k]);}printf("\n");}}voideditHCode(HTNodeht[],HCodehcd[],intn)//编码函数{ charstring[MAXSIZE]; inti,j,k; scanf("%s",string);//把要进行编码的字符串存入string数组中 printf("\n输出编码结果:\n"); for(i=0;string[i]!='#';i++)//#为终止标志 { for(j=0;j<n;j++) { if(string[i]==ht[j].data)//循环查找与输入字符相同的编号，相同的就输出这个字符的编码 { for(k=hcd[j].start;k<=n;k++) {printf("%c",hcd[j].cd[k]); } break;//输出完成后跳出当前for循环 } } }}4.4哈弗曼译码voiddeHCode(HTNodeht[],HCodehcd[],intn)//译码函数{ charcode[MAXSIZE]; inti,j,l,k,m,x; scanf("%s",code);//把要进行译码的字符串存入code数组中 while(code[0]!='#') for(i=0;i<n;i++) { m=0;//m为想同编码个数的计数器for(k=hcd[i].start,j=0;k<=n;k++,j++)//j为记录所存储这个字符的编码个数 { if(code[j]==hcd[i].cd[k])//当有相同编码时m值加1 m++; } if(m==j)//当输入的字符串与所存储的编码字符串个数相等时那么输出这个的data数据 { printf("%c",ht[i].data); for(x=0;code[x-1]!='#';x++)//把已经使用过的code数组里的字符串删除 { code[x]=code[x+j]; } } }}4.5主函数voidmain(){intn=26,i;charorz,back,flag=1;charstr[]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z'};//初始化intfnum[]={186,64,13,22,32,103,21,15,47,57,1,2,32,20,57,63,15,1,48,51,80,23,8,18,1,16};//初始化HTNodeht[M];//建立结构体HCodehcd[N];//建立结构体for(i=0;i<n;i++)//把初始化的数据存入ht结构体中{ht[i].data=str[i];ht[i].weight=fnum[i];}while(flag)//菜单函数，当flag为0时跳出循环4.6显示局部源程序：{ printf("\n"); printf("********************************"); printf("\n**1---------------显示编码**"); printf("\n**2---------------进行编码**"); printf("\n**3---------------进行译码**"); printf("\n**4---------------退出**\n"); printf("***********************************"); printf("\n"); printf("请输入选择的编号:"); scanf("%c",&orz); switch(orz) { case'a':case'A': system("cls");//清屏函数 CreateHT(ht,n); CreateHCode(ht,hcd,n); DispHCode(ht,hcd,n); printf("\n按任意键返回..."); getch(); system("cls"); break; case'b': case'B': system("cls"); printf("请输入要进行编码的字符串(以#结束):\n");editHCode(ht,hcd,n); printf("\n按任意键返回..."); getch(); system("cls"); break; case'c': case'C': system("cls"); DispHCode(ht,hcd,n); printf("请输入编码(以#结束):\n"); deHCode(ht,hcd,n); printf("\n按任意键返回..."); getch(); system("cls"); break; case'd': case'D': flag=0; break; default: system("cls"); }}}5.测试数据与实验结果用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE〞。字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度576315148518023818116.5.1初始化界面截图如下5.2选A时的显示结果截图如下5.3选择B时的显示结果截图如下5.4选C时的显示结果截图如下6.课程设计总结其实很多细节，只有在去写的时候才会发现，才会暴露出来，书本上的知识是很少的，很多东西，要靠自己平时多去练习，在练习中产生错误，通过上网查找等途径解决错误，以增长自己的知识点和调试能力。程序这种东西，就是写出来就感觉很简单，想着也不能，但是实现的时候，有时候会有这里那里的小错误阻碍程序的正确运行，很多时候，与其说是写程序不如说是对细节的检测。在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是假设没有定义所引用的相关头文件，必定调试不通过；在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连接号连接起来，而是按顺序直接放在一起，视觉效果不是很好。还有就是，很遗憾的是，我们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能，这是我们设计的失败之处。通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更稳固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高的质量。参考文献A：书籍资料[1]李春葆《数据结构教程上机实验指导》北京：清华大学出版社[2]严蔚敏吴伟民《数据结构〔C语言版〕》北京：清华大学出版社[3]苏仕华《数据结构课程设计》北京：机械工业出版社B：网络资料[1]哈夫曼编/译码器(课程设计).html[2]哈夫曼编码432169091693efce3bc763ab.html附录〔源程序代码〕#include<stdio.h>#include<stdlib.h>//要用system函数要调用的头文件#include<conio.h>//用getch()要调用的头文件#include<string.h>#defineN50//义用N表示50叶节点数#defineM2*N-1//用M表示节点总数当叶节点数位n时总节点数为2n-1#defineMAXSIZE100typedefstruct{chardata;//结点值intweight;//权值intparent;//双亲结点intlchild;//左孩子结点intrchild;//右孩子结点}HTNode;typedefstruct{charcd[N];//存放哈夫曼码intstart;//从start开始读cd中的哈夫曼码}HCode;voidCreateHT(HTNodeht[],intn)//调用输入的数组ht[],和节点数n{inti,k,lnode,rnode;intmin1,min2;for(i=0;i<2*n-1;i++)ht[i].parent=ht[i].lchild=ht[i].rchild=-1;//所有结点的相关域置初值-1for(i=n;i<2*n-1;i++)//构造哈夫曼树 {min1=min2=32767;//int的范围是-32768—32767lnode=rnode=-1;//lnode和rnode记录最小权值的两个结点位置for(k=0;k<=i-1;k++){ if(ht[k].parent==-1)//只在尚未构造二叉树的结点中查找 {if(ht[k].weight<min1)//假设权值小于最小的左节点的权值 {min2=min1;rnode=lnode;min1=ht[k].weight;lnode=k; }elseif(ht[k].weight<min2) {min2=ht[k].weight;rnode=k; } } }ht[lnode].parent=i;ht[rnode].parent=i;//两个最小节点的父节点是iht[i].weight=ht[lnode].weight+ht[rnode].weight;//两个最小节点的父节点权值为两个最小节点权值之和ht[i].lchild=lnode;ht[i].rchild=rnode;//父节点的左节点和右节点 }}voidCreateHCode(HTNodeht[],HCodehcd[],intn){inti,f,c;HCodehc;for(i=0;i<n;i++)//根据哈夫曼树求哈夫曼编码{hc.start=n;c=i;f=ht[i].parent;while(f!=-1)//循序直到树根结点结束循环{if(ht[f].lchild==c)//处理左孩子结点hc.cd[hc.start--]='0';else//处理右孩子结点hc.cd[hc.start--]='1';c=f;f=ht[f].parent;}hc.start++;//start指向哈夫曼编码hc.cd[]中最开始字符hcd[i]=hc;}}voidDispHCode(HTNodeht[],HCodehcd[],intn)//输出哈夫曼编码的列表{inti,k;printf("输出哈夫曼编码:\n");for(i=0;i<n;i++)//输出data中的所有数据，即A-Z{printf("%c:\t",ht[i].data);for(k=hcd[i].start;k<=n;k++)//输出所有data中数据的编码{printf("%c",hcd[i].cd[k]);}printf("\n");}}voideditHCode(HTNodeht[],HCodehcd[],intn)//编码函数{ charstring[MAXSIZE]; inti,j,k; scanf("%s",string);//把要进行编码的字符串存入string数组中 printf("\n输出编码结果:\n"); for(i=0;string[i]!='#';i++)//#为终止标志 { for(j=0;j<n;j++) { if(string[i]==ht[j].data)//循环查找与输入字符相同的编号，相同的就输出这个字符的编码 { for(k=hcd[j].start;k<=n;k++) {printf("%c",hcd[j].cd[k]); } break;//输出完成后跳出当前for循环 } } }}voiddeHCode(HTNodeht[],HCodehcd[],intn)//译码函数{ charcode[MAXSIZE]; inti,j,l,k,m,x; scanf("%s",code);//把要进行译码的字符串存入code数组中 while(code[0]!='#') for(i=0;i<n;i++) { m=0;//m为想同编码个数的计数器for(k=hcd[i].start,j=0;k<=n;k++,j++)//j为记录所存储这个字符的编码个数 { if(code[j]==hcd[i].cd[k])//当有相同编码时m值加1 m++; } if(m==j)//当输入的字符串与所存储的编码字符串个数相等时那么输出这个的data数据 { printf("%c",ht[i].data); for(x=0;code[x-1]!='#';x++)//把已经使用过的code数组里的字符串删除 { code[x]=code[x+j]; } } }}voidmain(){intn=26,i;charorz,bac