哈夫曼编码译码

1、数据结构课程设计报告设计题目 哈夫曼编码译码 学院名称 信息工程学院 专 业 班 级 计算机科学与技术2班 姓 名 学 号 摘要Huffman编码是一种可变长编码方式，是二叉树的一种特殊转化形式。它的原理是：将使用次数多的代码转换成长度较短的编码，而使用次数少的可以使用较长的编码，并且保持编码的唯一可解性。本文根据Huffman编码原理，在详细设计中，根据权值和最小的根本原则，我们输入要编码的字符集及其它的权值，再根据在概要设计中提到的节点Node类，算法SuanFa类以及主类JieMian类，建立哈夫曼树，并进行编码，最后输出哈夫曼编码。在完成Huffman编码后，我们利用其构建的哈夫曼编码

2、树来进行译码。与编码过程不同，译码过程中，我们将用户输入的二进制代码串依次与字符集中的每个字符的编码进行比较，译出一个字符后，循环比较下一个字符的编码，直到所有二进制码全部译出为止。在编码和译码的过程中，我们遇到很多问题，诸如算法、语法问题，但我们都通过不断的分析，和调试将这些问题一一解决，最终建立了一个完整的编/译码系统。关键词：Huffman编码树；最优二叉树；编码；译码AbstractHuffman coding is a encoding of variable length and a special transformation form of the binary tree. I

3、ts principle is: the code that be used more often will be changed into the code of shorter lengths, while the codes that be used less often can be transformed into the code of longer lengths and the unique solution of coding will be kept. According to the theory of Huffman coding, firstly we enter t

4、he character set which will be used to coding and their weights. Secondly, according to the fundanmental principle that the sum of the weights needs to be the smallest , the program designs Huffman tree in accordance with these class which are initialized in the outline such as class Node,class Suan

5、Fa,and class JieMian. At last, the computer will output Huffman coding on user interface.And then, we use the Huffman coding tree to decoding after the completion of Huffman coding tree.Here are difference with encoding process. We will compare the binary string that the user input with the characte

6、r set one by one during the processs of decoding .And then, the cycle of the next character encoding will continue which is based on the completion of translation of a character. It will be finished until all the binary code is translated.During the process of coding and decoding, we encounter many

7、problems, such as the problem on arithmetic and grammar. However, we try our best to solve these problems through constant analysis and debugging.Eventually, we achieve the goal that establish a complete system on coding and decoding successfully.Key Words：Huffman coding tree；optimal binary tree；cod

8、ing；decoding目录 摘要IABSTRACT II1. 绪论 1.1设计目的 11.2问题描述 11.3设计思想 12. 概要设计23.需求分析 44.详细设计 55.测试数据与实验结果106.课程设计总结14参考文献15附录（源程序代码）16 绪论1.1设计目的学习数据结构与算法的最终目的是解决实际的应用问题，特别是非数值计算类型的应用问题。本课程设计要求同学独立完成一个较为完整的应用需求分析，在完成设计和编程大型作业的过程中，深化对数据结构与算法课程中基本概念、理论和方法的理解；训练综合运用所学知识处理实际问题的能力，使同学的程序设计与调试水平有一个明显的提高。1.2问题描述利用赫

9、夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降低传输成本。这要求在发送端通过一个编码系统对待传输数据预先编码，在接收端将传来的数据进行译码（复原）。对于双工信道（即可以双向传输信息的信道），每端都需要一个完整的编/译码系统。试为这样的信息收发站编写一个赫夫曼码的编/译码系统。1.3.设计思想 哈夫曼编码(Huffman Coding)是一种编码方式，以哈夫曼树即最优二叉树，带权路径长度最小的二叉树，经常应用于数据压缩。是指使用一张特殊的编码表将源字符（例如某文件中的一个符号）进行编码。这种方法是由David.A.Huffman发展起来的。例如，在英文中，e的出现概率很高，而z的出

10、现概率则最低。当利用哈夫曼编码对一篇英文进行压缩时，e极有可能用一个位(bit)来表示，而z则可能花去25个位（不是26）。用普通的表示方法时，每个英文字母均占用一个字节（byte），即8个位。二者相比，e使用了一般编码的1/8的长度，z则使用了3倍多。倘若我们能实现对于英文中各个字母出现概率的较准确的估算，就可以大幅度提高无损压缩的比例。 2.概要设计总体流程图如下图 开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I<2*N?I+编码为1结束否否否右子是

11、否为空是是否否是是是 2.1 哈夫曼树的建立赫夫曼树的建立由赫夫曼算法的定义可知，初始森林中共有n棵只含有根结点的二叉树。算法的第二步是：将当前森林中的两棵根结点权值最小的二叉树，合并成一棵新的二叉树；每合并一次，森林中就减少一棵树，产生一个新结点。显然要进行n1次合并，所以共产生n1个新结点，它们都是具有两个孩子的分支结点。由此可知，最终求得的赫夫曼树中一共有2n1个结点，其中n个结点是初始森林的n个孤立结点。并且赫夫曼树中没有度数为1的分支结点。我们可以利用一个大小为2n-1的一维数组来存储赫夫曼树中的结点。2.2哈夫曼编码 要求电文的赫夫曼编码，必须先定义赫夫曼编码类型，根据设计要求和实

12、际需要定义的类型如下： typedet struct char ch; / 存放编码的字符 char bitsN1; / 存放编码位串 int len; / 编码的长度 CodeNode; / 编码结构体类型 2.3代码文件的译码 译码的基本思想是：读文件中编码，并与原先生成的赫夫曼编码表比较，遇到相等时，即取出其对应的字符存入一个新串中。 3.需求分析 3.1：初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。输出哈夫曼树，及各字符对应的编码。3.2：编码（Encoding）与译码（Decoding）。编码（

13、Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。译码（Decoding）。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。印代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码写入文件CodePrint中。3.3：印哈夫曼树（Tree Printing）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。4.详

14、细设计4.1哈夫曼树的存储结构描述typedef structunsigned int weight;unsigned int parent, lchild, rchild;HTNode, *HuffmanTree; 4.2 哈弗曼树的算法void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i<2*n-1;

15、i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weight<min1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=htk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.

16、parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点4.3哈弗曼编码void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc; for (i=0;i<n;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f

17、!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-='0' else /处理右孩子结点 hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编码的列表 int i,k; printf(" 输出哈夫曼编码:n"); for (i=0;i<n;i+) /输出data

18、中的所有数据，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /输出所有data中数据的编码 printf("%c",hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;scanf("%s",string); /把要进行编码的字符串存入string数组中printf("n输出编码结果:

19、n");for (i=0;stringi!='#'i+) /#为终止标志for (j=0;j<n;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /输出完成后跳出当前for循环4.4哈弗曼译码void deHCode(HTNode ht,HCode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf("

20、%s",code); /把要进行译码的字符串存入code数组中while(code0!='#')for (i=0;i<n;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据printf("%c",hti.data);for(x=0;codex-1!='#'x+) /把已经使用

21、过的code数组里的字符串删除codex=codex+j;4.5主函数void main() int n=26,i; char orz,back,flag=1; char str='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R

22、','S','T','U','V','W','X','Y','Z' /初始化 int fnum=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; /初始化 HTNode htM; /建立结构体 HCode hcdN; /建立结构体 for (i=0;i<n;i+) /把初始化的数据存入ht结构体中 hti.data=stri; hti.weight=fn

23、umi; 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(" 请输入选择的编

24、号:"); 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(&quo

25、t;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按任

26、意键返回."); getch(); system("cls"); break; case 'd': case 'D': flag=0; break; default: system("cls"); 5.测试数据与实验结果用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的编码和译码：“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 字

27、符 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 .5.1初始化界面截图如下5.2选A时的显示结果截图如下 5.3选择B时的显示结果截图如下5.4选C时的显示结果截图如下 6.课程设计总结其实很多细节，只有在去写的时候才会发现，才会暴露出来，书本上的知识是很少的，很多东西，要靠自己平时多去练习，在练习中产生错误，通过上网查找等途径解决错误，以增长自己的知识点和调试能力。程序这种东西，就是写出来就感觉很简单，想着也不能，但是实现的时候，有时候会有这里那里的小错误阻碍程序的正确运行，很多时候，与其说是写程序不如说是对细节

28、的检测。 在我自己课程设计中，就在编写好源代码后的调试中出现了不少的错误，遇到了很多麻烦及困难，我的调试及其中的错误和我最终找出错误，修改为正确的能够执行的程序中，通过分析，我学到了：在定义头文件时可多不可少，即我们可多写些头文件，肯定不会出错，但是若没有定义所引用的相关头文件，必定调试不通过；在执行译码操作时，不知什么原因，总是不能把要编译的二进制数与编译成的字符用连接号连接起来，而是按顺序直接放在一起，视觉效果不是很好。还有就是，很遗憾的是，我们的哈夫曼编码/译码器没有像老师要求的那样完成编一个文件的功能，这是我们设计的失败之处。 通过本次数据结构的课程设计，我学习了很多在上课没懂的知识，

29、并对求哈夫曼树及哈夫曼编码/译码的算法有了更加深刻的了解，更巩固了课堂中学习有关于哈夫曼编码的知识，真正学会一种算法了。当求解一个算法时,不是拿到问题就不加思索地做，而是首先要先对它有个大概的了解，接着再详细地分析每一步怎么做，无论自己以前是否有处理过相似的问题，只要按照以上的步骤，必定会顺利地做出来。这次课程设计，我在编辑中犯了不应有的错误，设计统计字符和合并时忘记应该怎样保存数据，对文件的操作也很生疏。在不断分析后明确并改正了错误和疏漏，我的程序有了更高的质量。 参考文献A：书籍资料1 李春葆 数据结构教程 上机实验指导北京：清华大学出版社2 严蔚敏 吴伟民数据结构（C语言版）北京：清华大

30、学出版社3 苏仕华 数据结构 课程设计 北京：机械工业出版社B：网络资料1 哈夫曼编/译码器(课程设计).html2 哈夫曼编码432169091693efce3bc763ab.html 附录（源程序代码）#include <stdio.h>#include <stdlib.h> /要用system函数要调用的头文件#include<conio.h> /用getch()要调用的头文件#include <string.h>#define N 50 /义用N表示50叶节点数#define M 2*N-1 /用M表示节点总数 当叶节点数位n时总节点数为

31、2n-1#define MAXSIZE 100typedef struct char data; /结点值 int weight; /权值 int parent; /双亲结点 int lchild; /左孩子结点 int rchild; /右孩子结点HTNode; typedef struct char cdN; /存放哈夫曼码 int start; /从start开始读cd中的哈夫曼码HCode;void CreateHT(HTNode ht,int n) /调用输入的数组ht,和节点数n int i,k,lnode,rnode; int min1,min2; for (i=0;i<2

32、*n-1;i+) hti.parent=hti.lchild=hti.rchild=-1; /所有结点的相关域置初值-1 for (i=n;i<2*n-1;i+) /构造哈夫曼树 min1=min2=32767; /int的范围是-3276832767 lnode=rnode=-1; /lnode和rnode记录最小权值的两个结点位置 for (k=0;k<=i-1;k+) if (htk.parent=-1) /只在尚未构造二叉树的结点中查找 if (htk.weight<min1) /若权值小于最小的左节点的权值 min2=min1;rnode=lnode; min1=h

33、tk.weight;lnode=k; else if (htk.weight<min2) min2=htk.weight;rnode=k; htlnode.parent=i;htrnode.parent=i; /两个最小节点的父节点是i hti.weight=htlnode.weight+htrnode.weight; /两个最小节点的父节点权值为两个最小节点权值之和 hti.lchild=lnode;hti.rchild=rnode; /父节点的左节点和右节点void CreateHCode(HTNode ht,HCode hcd,int n) int i,f,c; HCode hc;

34、 for (i=0;i<n;i+) /根据哈夫曼树求哈夫曼编码 hc.start=n;c=i; f=hti.parent; while (f!=-1) /循序直到树根结点结束循环 if (htf.lchild=c) /处理左孩子结点 hc.cdhc.start-='0' else /处理右孩子结点 hc.cdhc.start-='1' c=f;f=htf.parent; hc.start+; /start指向哈夫曼编码hc.cd中最开始字符 hcdi=hc; void DispHCode(HTNode ht,HCode hcd,int n) /输出哈夫曼编

35、码的列表 int i,k; printf(" 输出哈夫曼编码:n"); for (i=0;i<n;i+) /输出data中的所有数据，即A-Z printf(" %c:t",hti.data); for (k=hcdi.start;k<=n;k+) /输出所有data中数据的编码 printf("%c",hcdi.cdk); printf("n"); void editHCode(HTNode ht,HCode hcd,int n) /编码函数char stringMAXSIZE; int i,j,k;

36、scanf("%s",string); /把要进行编码的字符串存入string数组中printf("n输出编码结果:n");for (i=0;stringi!='#'i+) /#为终止标志for (j=0;j<n;j+)if(stringi=htj.data) /循环查找与输入字符相同的编号，相同的就输出这个字符的编码for (k=hcdj.start;k<=n;k+) printf("%c",hcdj.cdk);break; /输出完成后跳出当前for循环void deHCode(HTNode ht,HC

37、ode hcd,int n) /译码函数char codeMAXSIZE;int i,j,l,k,m,x;scanf("%s",code); /把要进行译码的字符串存入code数组中while(code0!='#')for (i=0;i<n;i+)m=0; /m为想同编码个数的计数器 for (k=hcdi.start,j=0;k<=n;k+,j+) /j为记录所存储这个字符的编码个数if(codej=hcdi.cdk) /当有相同编码时m值加1m+;if(m=j) /当输入的字符串与所存储的编码字符串个数相等时则输出这个的data数据print

38、f("%c",hti.data);for(x=0;codex-1!='#'x+) /把已经使用过的code数组里的字符串删除codex=codex+j;void main() int n=26,i; char orz,back,flag=1; char str='A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V&