课程设计(论文)-哈夫曼编码及其应用
17页1、图论论文论文题目 学生姓名 专业班级 学 号 邮 箱 2015 年 12 月 20 日目 录摘要 .1第一章 哈夫曼树 .21.1 哈夫曼树的基本概念 .2第二章 哈夫曼算法构造 .32.1 哈夫曼树的构造算法 .32.2 举例说明其构造过程 .3第三章 哈夫曼树的应用 .53.1 用于通信编码 .5第四章 运行结果 .6第五章 总结 .7参考文献: .7附录 .8哈夫曼编码及其应用摘要在现代社会,通信的发展,使得现代社会更加丰富多彩,我们可以随时随地在任何 地方了解到世界各地的信息,而这又必须依赖信息的传递。在信息化高度发达的当今社会,我们必须对信息的传递有着较高的要求,我们希望信息在传递的过程中,能够保持节省性和保密性和无损性,而著名的霍夫曼编码就能够达到这样的要求。因此研究霍夫曼编码对信息的压缩和解压就时相当有必要的,我们用 C+对霍夫曼编码给出简单的算法以实现对文件的压缩和解压。哈夫曼树是由哈夫曼于 1951 年所创立并改进的,他本人也根据哈夫曼树提出了相应的编码.由于哈夫曼树是具有最小加权路径长度的二叉树,故哈夫曼编码能产生较短的码文.基于这个优势,在信息化高度发达的当今社会
2、,对信息的传递也有着较高要求的我们,希望信息在传递过程中,能够保持节省性和保密性,哈夫曼编码则很好的满足了这方面的要求,因而对其的研究是相当有必要的.关键字:哈夫曼树,二叉树,信息压缩编码2第一章 哈夫曼树1.1 哈夫曼树的基本概念首先要了解关于树的一些概念。定义 1.1 在一棵树中,从一个结点往下可以达到的孩子或子孙结点之间的通路,称为路径.定义 1.2 若将树中结点都赋给一个具有某种含义的数值,则这个数值称为该结点的权.定义 1.3 由根结点到所有叶结点的路径长度之和称为二叉树的路径长度.定义 1.4 从根结点到叶结点的路径长度与相应结点权值之积的和叫做二叉树的带权路径长度.定义 1.5 最优二叉树,也称哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.如果二叉树中的叶结点都具有一定的权值,则可将这一概念推广,设二叉树有 个带权值的叶结点,那么,二叉树的带权路径长度应记为:n,nkkLWP1其中 为第 个叶结点的权值; 为第 个叶结点的路径长度.如下图: kW图 1.在图 中, 即为根结点,而 则为叶结点,若 的权值分别为 则1.ACBCB,4,3二叉
3、树路径长度为 2,二叉树的带权路径长度为 7,即 .713WPL例 下面我们结合实例来说明哈夫曼树.如图 1.2.2)(a)(b)(c.1图3 ;49235168 312; 1WPL按照 的计算方法,经过计算比较后,我们发现,图 的 值最2.1)(bWPL小,它即为哈夫曼树.由此可见,由相同权值的一组叶子结点所构成的二叉树有不同的形态和不同的带权路径长度.那么如何找到带权路径长度最小的二叉树呢?根据哈夫曼树的定义,一棵二叉树要使其 值最小,必须使权值越大的叶结点越靠近根结点,PL而权值越小的叶结点越远离根结点,这样计算树的带权路径长度时,自然树会具有最小的带权路径长度,这是生成算法的一种基本思想.第二章 哈夫曼算法构造哈夫曼树,实质是对一组带有确定权值的叶结点,构造的具有最小带权路径长度的二叉树.尽管哈夫曼树可以通过 比较后得出,可是在运算过程中往往WPL会出现一些问题,使其实现起来并不容易,因而我们可以应用编程来有效地解决这个问题.2.1 哈夫曼树的构造算法为了构造权值为 的哈夫曼树,哈夫曼提出了一种构造算法,现n,321L将其陈述如下:步骤 1 根据题目给定的 个权值 构造有下列
《课程设计(论文)-哈夫曼编码及其应用》由会员aa****6分享,可在线阅读,更多相关《课程设计(论文)-哈夫曼编码及其应用》请在金锄头文库上搜索。
罗兰贝格世界一流的通信企业管理方式(ppt50页)课件
小学校本课程《社会礼仪》4
小学六年级品德与社会下册《地球的伤心事——寻找受伤的原因》课件
冀教版二年级品德与生活下第五课诚实孩子人人夸
京改版化学九年级上册522物质的组成表示化学式课件_(共15张ppt)
二下语文快乐宫课件
(人教新课标)二年级语文上册课件称赞_5
工笔画技法19张ppt培训课件
学会自我保护ppt培训课件
党建工作ppt模板下载_1
脚印课件之二北京版一年级语文上册课件
人教二年级下册语文园地一会写生字笔顺演示_1ppt培训课件
一级建造师建筑工程管理与实务考试精讲ppt课件
沙排酷哥-体育主题 ppt模板ppt培训课件
内压容器设计ppt课件
小水萝卜橙色背景-食品主题 模板ppt培训课件
连续时间系统的时域分析ppt培训课件
烧伤临床解析
小学二年级美术下册《头饰设计》课件 (2)
病毒性疾病标本采集、保存与检测
2023-02-11 3页
2022-09-07 4页
2022-09-14 6页
2023-11-10 5页
2023-01-19 5页
2024-01-29 5页
2023-12-19 17页
2022-08-29 33页
2024-02-03 25页
2023-06-22 3页