数据结构-哈夫曼树及其应用

计算机学院信管专业数据结构课程设计题目：哈夫曼树的应用班级：姓名：学号：同组人姓名：起迄日期：课程设计地点:指导教师：完成日期：2012年12月目录一、需求分析 (3)二、概要设计 (4)三、详细设计 (6)四、调试分析和测试结果 (7)五、心得体会和总结 (10)六、参考文献 (10)七、附录 (11)一、需求分析（一）实验要求要求用到数据结构课上学到的线性表的知识，所以就要充分而清晰的理解关于线性表的知识。

要求实现的基本功能很简单，只有删除和插入，增加功能也不过是加上修改。

这些在数据结构课上已经讲过，只要能够理解关于线性表的几个相关的基本算法就可以了。

问题是将输入的信息保存入文件和从文件输出。

这里基本是自学的内容，而且要考虑到是否要自行选择保存的磁盘。

综上，做这个课题，要具备的知识就是线性表的基本算法，文件的保存和读取算法，必要的C或者C++知识（本次我将使用C++实现），以及丰富的程序调适经验。

（二）实验任务一个完整的系统应具有以下功能：功能1．从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；功能2．利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中，并输出结果，将文件CodeFile以紧凑格式先是在终端上，每行50个代码。

同时将此字符形式的编码文件写入文件CodePrint中。

功能3．利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中，并输出结果。

（三）实验步骤分步实施：1）初步完成总体设计，搭好框架，确定人机对话的界面，确定函数个数；2）完成最低要求：完成功能1；3）进一步要求：完成功能2和3。

有兴趣的同学可以自己扩充系统功能。

要求：1）界面友好，函数功能要划分好2）总体设计应画一流程图3）程序要加必要的注释4) 要提供程序测试方案5）程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。

第三节哈夫曼树及其应用1．哈夫曼树的定义在二叉树中，一个结点到另一个结点之间的分支构成这两个结点之间的路径。

这三棵二叉树的带权路径长度分别为：WPL1=10*2+11*2+3*3+6*3+7*3+9*3=117WPL2=3*1+6*2+7*3+9*4+10*5+11*5=177WPL3=9*1+7*2+6*3+3*4+10*5+11*5=158构造哈夫曼树的过程：（1）将给定的n个权值{w1,w2,...,wn}作为n个根结点的权值构造一个具有n棵二叉树的森林{T1,T2,...,Tn}，其中每棵二叉树只有一个根结点；（2）在森林中选取两棵根结点权值最小的二叉树作为左右子树构造一棵新二叉树，新二叉树的根结点权值为这两棵树根的权值之和；（3）在森林中，将上面选择的这两棵根权值最小的二叉树从森林中删除，并将刚刚新构造的二叉树加入到森林中；（4）重复上面（2）和（3），直到森林中只有一棵二叉树为止。

这棵二叉树就是哈夫曼树。

假设有一组权值{5,29,7,8,14,23,3,11}，下面我们将利用这组权值演示构造哈夫曼树的过程。

这就是以上述8个权值为叶子结点权值构成的哈夫曼树，它的带权的路径长度为：WPL=(23+29)*2+(11+14)*3+(3+5+7+8)*4=2712．判定树在很多问题的处理过程中，需要进行大量的条件判断，这些判断结构的设计直接影响着程序的执行效率。

例如，编制一个程序，将百分制转换成五个等级输出。

大家可能认为这个程序很简单，并且很快就可以用下列形式编写出来：if (socre<60) printf("bad");else if (socre<70) printf("pass");else if (score<80) printf("general");else if (score<90) printf("good");esle printf("very good");在实际应用中，往往各个分数段的分布并不是均匀的。

哈夫曼树的应用课程设计3合1 《数据结构与算法》课程设计指导教师：班级：学号：姓名：《数据结构与算法》课程设计目录一、前言1．摘要2．《数据结构与算法》课程设计任务书二、实验目的三、题目--赫夫曼编码/译码器1．问题描述2．基本要求3．测试要求4．实现提示四、需求分析--具体要求五、概要设计六、程序说明七、详细设计八、实验心得与体会前言1．摘要随着计算机的普遍应用与日益发展，其应用早已不局限于简单的数值运算，而涉及到问题的分析、数据结构框架的设计以及设计最短路线等复杂的非数值处理和操作。

算法与数据结构的学习就是为以后利用计算机资源高效地开发非数值处理的计算机程序打下坚实的理论、方法和技术基础。

算法与数据结构旨在分析研究计算机加工的数据对象的特性，以便选择适当的数据结构和存储结构，从而使建立在其上的解决问题的算法达到最优。

数据结构是在整个计算机科学与技术领域上广泛被使用的术语。

它用来反映一个数据的内部构成，即一个数据由那些成分数据构成，以什么方式构成，呈什么结构。

数据结构有逻辑上的数据结构和物理上的数据结构之分。

逻辑上的数据结构反映成分数据之间的逻辑关系，而物理上的数据结构反映成分数据在计算机内部的存储安排。

数据结构是数据存在的形式。

《数据结构》主要介绍一些最常用的数据结构，阐明各种数据结构内在的逻辑关系，讨论其在计算机中的存储表示，以及在其上进行各种运算时的实现算法，并对算法的效率进行简单的分析和讨论。

数据结构是介于数学、计算机软件和计算机硬件之间的一门计算机专业的核心课程，它是计算机程序设计、数据库、操作系统、编译原理及人工智能等的重要基础，广泛的应用于信息学、系统工程等各种领域。

学习数据结构是为了将实际问题中所涉及的对象在计算机中表示出来并对它们进行处理。

通过课程设计可以提高学生的思维能力，促进学生的综合应用能力和专业素质的提高。

2．《数据结构与算法》课程设计任务书《数据结构与算法》是计算机专业重要的核心课程之一，在计算机专业的学习过程中占有非常重要的地位。

哈夫曼树的实际应用
哈夫曼树（Huffman Tree）是一种重要的数据结构，它在信息编码和压缩、数据传输和存储、图像处理等领域有广泛应用。

1. 数据压缩：哈夫曼树是一种无损压缩的方法，能够有效地减小数据的存储空间。

在进行数据压缩时，可以使用哈夫曼树构建字符编码表，将出现频率较高的字符用较短的编码表示，而出现频率较低的字符用较长的编码表示，从而减小数据的存储空间。

2. 文件压缩：在文件压缩领域，哈夫曼树被广泛应用于压缩算法中。

通过构建哈夫曼树，可以根据字符出现的频率来生成不同长度的编码，从而减小文件的大小。

常见的文件压缩格式如ZIP、GZIP等都使用了哈夫曼树。

3. 图像压缩：在图像处理中，哈夫曼树被用于图像压缩算法中。

通过将图像中的像素值映射为不同长度的编码，可以减小图像的存储空间，提高图像传输和存储的效率。

常见的图像压缩格式如JPEG、PNG等都使用了哈夫曼树。

4. 文件传输：在数据传输中，哈夫曼树被用于数据压缩和传输。

通过对数据进行压缩，可以减小数据的传输时间和带宽占用。

在传输过程中，接收方可以通过哈夫曼树解码接收到的数据。

5. 数据加密：在数据加密中，哈夫曼树可以用于生成密钥，从而实现数据的加密和解密。

通过将字符映射为不同长度的编码，可以实
现对数据的加密和解密操作。

哈夫曼树在信息编码和压缩、数据传输和存储、图像处理等领域有广泛应用，能够有效地减小数据的存储空间、提高数据传输效率、实现数据加密等功能。

哈夫曼树的应用-哈夫曼树代码实现一、简介哈夫曼树又称为最优树。

1、路径和路径长度在一棵树中，从一个结点往下可以达到的孩子或子孙结点之间的通路，称为路径。

通路中分支的数目称为路径长度。

若规定根结点的层数为1，则从根结点到第L层结点的路径长度为L-1。

2、结点的权及带权路径长度若将树中结点赋给一个有着某种含义的数值，则这个数值称为该结点的权。

结点的带权路径长度为：从根结点到该结点之间的路径长度与该结点的权的乘积。

3、树的带权路径长度树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL二、哈夫曼树的应用1、哈夫曼编码在数据通信中，需要将传送的文字转换成二进制的字符串，用0，1码的不同排列来表示字符。

例如，需传送的报文为“AFTER DATA EAR ARE ART AREA”，这里用到的字符集为“A，E，R，T，F，D”，各字母出现的次数为{8，4，5，3，1，1}。

现要求为这些字母设计编码。

要区别6个字母，最简单的二进制编码方式是等长编码，固定采用3位二进制，可分别用000、001、010、011、100、101对“A，E，R，T，F，D”进行编码发送，当对方接收报文时再按照三位一分进行译码。

显然编码的长度取决报文中不同字符的个数。

若报文中可能出现26个不同字符，则固定编码长度为5。

然而，传送报文时总是希望总长度尽可能短。

在实际应用中，各个字符的出现频度或使用次数是不相同的，如A、B、C的使用频率远远高于X、Y、Z，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。

为使不等长编码为前缀编码(即要求一个字符的编码不能是另一个字符编码的前缀)，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。

因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。

哈夫曼树的实际应用
哈夫曼树在实际中有许多应用，以下是一些例子：
1. 数据压缩：哈夫曼树常用于数据压缩算法，如哈夫曼编码。

哈夫曼编码是一种前缀编码，它可以将数据中的字符编码为二进制字符串，使得平均编码长度最短，从而达到数据压缩的效果。

2. 文件存储：在文件存储中，哈夫曼树可以用于数据存储和检索。

例如，可以使用哈夫曼树来存储文件索引，以便快速找到文件。

3. 图像处理：在图像处理中，哈夫曼树可以用于图像压缩和编码。

例如，可以使用哈夫曼树来编码图像中的像素值，从而减小图像文件的大小。

4. 通信网络：在通信网络中，哈夫曼树可以用于数据传输和调度。

例如，可以使用哈夫曼树来优化数据的传输路径和顺序，以提高网络传输的效率和可靠性。

5. 数据库优化：在数据库优化中，哈夫曼树可以用于索引和查询处理。

例如，可以使用哈夫曼树来构建索引，以便快速检索数据库中的数据。

总的来说，哈夫曼树在许多领域中都有广泛的应用，特别是在需要数据压缩、文件存储、图像处理、通信网络和数据库优化的领域中。

数据结构与算法——树的应⽤（哈夫曼编码）1. 哈夫曼编码概括/********************************************** 本⽂图⽚较多，多刷新⼀下才能显⽰ ***********************************************/哈夫曼（Huffman）编码算法是基于⼆叉树构建编码压缩结构的，它是数据压缩中经典的⼀种算法。

算法根据⽂本字符出现的频率，重新对字符进⾏编码。

⾸先以下这段⽂字举例：今天天⽓晴朗，我和乔伊·亚历⼭⼤·⽐基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱⼠·普雷斯顿出去玩！乔伊·亚历⼭⼤·⽐基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱⼠·普雷斯顿贪玩，不⼩⼼摔了⼀跤，乔伊·亚历⼭⼤·⽐基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱⼠·普雷斯顿被摔得哇哇哭了，乔伊·亚历⼭⼤·⽐基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱⼠·普雷斯顿的爸爸闻声赶来，⼜把乔伊·亚历⼭⼤·⽐基·卡利斯勒·达夫·埃利奥特·福克斯·伊维鲁莫·马尔尼·梅尔斯·帕特森·汤普森·华莱⼠·普雷斯顿痛扁了⼀阵。

哈夫曼树及其扩展应用（彭宗山 030420104 0004201班）一、问题描述与分析在数据通讯中，经常需要将传送的文字转换成由二进制字符0，1组成的二进制串，我们称之为编码。

例如，假设要传送的电文为ABACCDA，电文中只含有A，B，C，D四种字符，若这四种字符采用表1 (a)所示的编码，则电文的代码为000010000100100111 000，长度为21。

在传送电文时，我们总是希望传送时间尽可能短，这就要求电文代码尽可能短，显然，这种编码方案产生的电文代码不够短。

现在讨论能缩短传送电文的总长度，从而缩短传送时间呢？表 1 (b)所示为另一种编码方案，用此编码对上述电文进行编码所建立的代码为00010010101100，长度为14。

在这种编码方案中，四种字符的编码均为两位，是一种等长编码。

我们应该想到，若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样又可能缩短传送电文的总长度。

如果在编码时考虑字符出现的频率，让出现频率高的字符采用尽可能短的编码，出现频率低的字符采用稍长的编码，构造一种不等长编码，则电文的代码就可能更短。

如当字符A，B，C，D采用表1 (c)所示的编码时，上述电文的代码为0110010101110，长度仅为13。

表1 字符的四种不同的编码方案二、数据结构描述哈夫曼树可用于构造使电文的编码总长最短的编码方案。

具体做法如下：设需要编码的字符集合为{d1，d2，…，dn}，它们在电文中出现的次数或频率集合为{w1，w2，…，wn}，以d1，d2，…，dn作为叶结点，w1，w2，…，wn作为它们的权值，构造一棵哈夫曼树，规定哈夫曼树中的左分支代表0，右分支代表1，则从根结点到每个叶结点所经过的路径分支组成的0和1的序列便为该结点对应字符的编码，我们称之为哈夫曼编码。

在哈夫曼编码树中，树的带权路径长度的含义是各个字符的码长与其出现次数的乘积之和，也就是电文的代码总长，所以采用哈夫曼树构造的编码是一种能使电文代码总长最短的不等长编码。

哈夫曼树及其应⽤1、基本概念a、路径和路径长度若在⼀棵树中存在着⼀个结点序列 k1，k2，……，kj，使得 ki是ki+1 的双亲（1<=i<j），则称此结点序列是从 k1 到 kj 的路径。

从 k1 到 kj 所经过的分⽀数称为这两点之间的路径长度，它等于路径上的结点数减1.b、结点的权和带权路径长度在许多应⽤中，常常将树中的结点赋予⼀个有着某种意义的实数，我们称此实数为该结点的权，(如下⾯⼀个树中的蓝⾊数字表⽰结点的权)结点的带权路径长度规定为从树根结点到该结点之间的路径长度与该结点上权的乘积。

c、树的带权路径长度树的带权路径长度定义为树中所有叶⼦结点的带权路径长度之和，公式为：其中，n表⽰叶⼦结点的数⽬，wi 和 li 分别表⽰叶⼦结点 ki 的权值和树根结点到 ki 之间的路径长度。

如下图中树的带权路径长度 WPL = 9 x 2 + 12 x 2 + 15 x 2 + 6 x 3 + 3 x 4 + 5 x 4 = 122d、哈夫曼树哈夫曼树⼜称最优⼆叉树。

它是 n 个带权叶⼦结点构成的所有⼆叉树中，带权路径长度 WPL 最⼩的⼆叉树。

如下图为⼀哈夫曼树⽰意图。

2、构造哈夫曼树假设有n个权值，则构造出的哈夫曼树有n个叶⼦结点。

n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有⼀个结点)；(2) 在森林中选出两个根结点的权值最⼩的树合并，作为⼀棵新树的左、右⼦树，且新树的根结点权值为其左、右⼦树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加⼊森林；(4)重复(2)、(3)步，直到森林中只剩⼀棵树为⽌，该树即为所求得的哈夫曼树。

如：对下图中的六个带权叶⼦结点来构造⼀棵哈夫曼树，步骤如下：注意：为了使得到的哈夫曼树的结构尽量唯⼀，通常规定⽣成的哈夫曼树中每个结点的左⼦树根结点的权⼩于等于右⼦树根结点的权。