《课程设计（论文）-哈夫曼编码及其应用》由会员分享，可在线阅读，更多相关《课程设计（论文）-哈夫曼编码及其应用（17页珍藏版）》请在金锄头文库上搜索。
1、图论论文论文题目 学生姓名 专业班级 学 号 邮 箱 2015 年 12 月 20 日目 录摘要 .1第一章 哈夫曼树 .21.1 哈夫曼树的基本概念 .2第二章 哈夫曼算法构造 .32.1 哈夫曼树的构造算法 .32.2 举例说明其构造过程 .3第三章 哈夫曼树的应用 .53.1 用于通信编码 .5第四章 运行结果 .6第五章 总结 .7参考文献: .7附录 .8哈夫曼编码及其应用摘要在现代社会，通信的发展，使得现代社会更加丰富多彩，我们可以随时随地在任何 地方了解到世界各地的信息，而这又必须依赖信息的传递。在信息化高度发达的当今社会，我们必须对信息的传递有着较高的要求，我们希望信息在传递的
2、过程中，能够保持节省性和保密性和无损性，而著名的霍夫曼编码就能够达到这样的要求。因此研究霍夫曼编码对信息的压缩和解压就时相当有必要的，我们用 C+对霍夫曼编码给出简单的算法以实现对文件的压缩和解压。哈夫曼树是由哈夫曼于 1951 年所创立并改进的,他本人也根据哈夫曼树提出了相应的编码.由于哈夫曼树是具有最小加权路径长度的二叉树,故哈夫曼编码能产生较短的码文.基于这个优势,在信息化高度发达的当今社会,对信息的传递也有着较高要求的我们,希望信息在传递过程中,能够保持节省性和保密性,哈夫曼编码则很好的满足了这方面的要求,因而对其的研究是相当有必要的.关键字：哈夫曼树，二叉树，信息压缩编码2第一章 哈
3、夫曼树1.1 哈夫曼树的基本概念首先要了解关于树的一些概念。定义 1.1 在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径.定义 1.2 若将树中结点都赋给一个具有某种含义的数值,则这个数值称为该结点的权.定义 1.3 由根结点到所有叶结点的路径长度之和称为二叉树的路径长度.定义 1.4 从根结点到叶结点的路径长度与相应结点权值之积的和叫做二叉树的带权路径长度.定义 1.5 最优二叉树,也称哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.如果二叉树中的叶结点都具有一定的权值,则可将这一概念推广,设二叉树有 个带权值的叶结点,那么,二叉树的带
4、权路径长度应记为:n,nkkLWP1其中 为第 个叶结点的权值; 为第 个叶结点的路径长度.如下图： kW图 1.在图 中, 即为根结点,而 则为叶结点,若 的权值分别为 则1.ACBCB,4,3二叉树路径长度为 2,二叉树的带权路径长度为 7,即 .713WPL例 下面我们结合实例来说明哈夫曼树.如图 1.2.2)(a)(b)(c.1图3 ;49235168 312; 1WPL按照 的计算方法,经过计算比较后,我们发现,图 的 值最2.1)(bWPL小,它即为哈夫曼树.由此可见,由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度.那么如何找到带权路径长度最小的二叉树呢？根
5、据哈夫曼树的定义,一棵二叉树要使其 值最小,必须使权值越大的叶结点越靠近根结点,PL而权值越小的叶结点越远离根结点,这样计算树的带权路径长度时,自然树会具有最小的带权路径长度,这是生成算法的一种基本思想.第二章 哈夫曼算法构造哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.尽管哈夫曼树可以通过 比较后得出,可是在运算过程中往往WPL会出现一些问题,使其实现起来并不容易,因而我们可以应用编程来有效地解决这个问题.2.1 哈夫曼树的构造算法为了构造权值为 的哈夫曼树,哈夫曼提出了一种构造算法,现n,321L将其陈述如下:步骤 1 根据题目给定的 个权值 构造有下列
6、棵二叉树的集合 nnW,321 n,其中每棵二叉树 中只有一个带权为 的根结点,其 TF,321LiTi左右树均为空;步骤 2 在 中选取两棵根结点的权值最小的树作为左、右子树构造一棵新的二 叉树,且置新的二叉树的根结点的权值为其左、右子树上根结点的权值之 和;步骤 3 在 中删除这两棵树,同时将新得到的二叉树加入 中;F F步骤 4 重复步骤 2 和步骤 3,直到 只含有一棵树为止,这棵树便是哈夫曼树.F2.2 举例说明其构造过程假设叶结点权值集合为 的哈夫曼树的构造4,321W第一步 我们根据给定的 4 个权值来构造 4 棵二叉树的集合 .F4第二步 在 找出权值中最小的两个作为新二叉树的
7、左右子树,且置新的二F叉树根结点权值是其左右结点权值之和.第三步 将次小的树与新生成的树再作为左右子树生成权值为 6 的新树;第四步 再次将权值为 4 的树在同上一个权值为 6 的树再次生成新树即可.从以上过程可以计算出这棵二叉树的带权路径长度为 19.5第三章 哈夫曼树的应用3.1 用于通信编码在电报通讯中,电文是以二进制的 序列传送的.在发送端需要将电文中的1,0字符序列转换成二进制的 序列,而在接收端又需要把接收的 序列转换成对10 1,0应的字符序列.例如给出一段电文:TASSCAT 电文中只使用了 这四种字符,各字符出现的频度分别是 ,若进行S, 5472等长编码,需要两位二进制位,
8、可依次编码为1: ,0: ,1: ,0:TSAC则所发电文是:01 01采用不等长编码要避免译码的二义性.例如, 字符,0:,:,DCBA的编码 是字符 的编码 的前缀部分.这样对于代码串 ,既是AB0的代码, 也是 和 的代码,因此,这样的编码不能保证译码的唯一性.CAD所以,若对某一字符集进行不等长编码,可用该字符集中的每个字符作为叶子结点生成一棵编码二叉树,且约定左子树表示字符 ,右子树表示字符 ,则可01以用从根结点到叶结点路径上的分支字符组成的字符串作为该叶子结点字符的编码.为了获得传送电文的最短长度,可将每个字符出现的频率作为字符结点的权值赋给该结点,从而求出此树的最小带权路径长度
9、就等于求出了传送电文的最短长度.因此,求传送电文的最短长度问题就转化为求由字符集中所有字符作为叶子结点和由字符的出现频度作为其权值所产生的哈夫曼树的问题.例如, ,各字符出现的概率为 ,对各概率TSACD,1854,718取整,得到各字符的权值 ,利用它们构造哈夫曼树,如图 所示,5472，iW3.则各字符的编码为: .0:1:01:TS，61.23图在构造了哈夫曼树之后,为求编码需从叶子结点出发走一条从叶子到根的路径,而为求译码需从根出发走一条根到叶子的路径.故哈夫曼编码成功地应用于离散数学与数据结构中的最优二叉树寻找.第四章 运行结果图 4.1 编码界面7图 4.2 解码界面第五章 总结程
10、序经运行得到很好的实现,但程序中仍存在一些不足之处,需要再加以改进.通过此次论文设计很好的增强了我对编程及二叉树理论的认识和对 C+软件的应用能力,也是将理论知识运用于解决实际问题的一次新尝试.并且对图论这门学科有更深刻的认识，感觉应用范围非常广泛。通过本课程的学习，我也认识了自己还有很多不足，需要进一步学习的地方，在接下来的学习中我会花更多时间，来认真加深知识理解与运用。参考文献:1 张清华.图论及其应用.M.北京:清华大学出版社,2013:134-231.2 严蔚敏.数据结构 M .北京 :清华大学出版社,1995:145-147.3 谭浩强.C+面向对象程序设计 M.北京:清华大学出版社,2007:134-231.8附录#include #include #include #define MAXLEN 100 typedef struct Huffmantree char ch; /*键值*/ int weight,mark; /*weight 为权值,mark 为标志域*/ struct Huffmantree *parent,*lchild,*rchild,*next; Hftree,*linktree
