课程设计说明书 No 1
赫夫曼树的建立 1课程设计目的 (1)掌握算法的编写方法。 (2)掌握C语言的算法转换成C程序并上机调试的基本方法。 (3)根据建立好的函数输入二叉树，对其输入的字符出现的频率作为权值输出其相对应的赫夫曼树。 2设计方案论证 2.1 问题描述 2.1.1赫夫曼树的基本概念 相关概念：路径：从树中一个结点到另一个结点所经过的分支序列或者说结点序列。路径长度：路径上面的分支个数。树的路径长度：从树根到每一个结点的路径长度之和。结点的权值：在某些应用中，树中结点往往要和一定的数值联系起来，那么这个数值通常称为该结点的权值，简称权。结点的带权路径长度：该结点到根结点的路径长度与该结点上权的乘积。树的带权路径长度：树中所有叶子结点的带权路径长度之和。 最优二叉树（哈夫曼树）：给定n个权值{w1,w2,…,wn}，试构造一棵有n个叶子结点的二叉树，每个叶子结点带权为wi。构造出来的二叉树的形态可以有多个，我们把其中带权路径长度WPL最小的二叉树称作最优二叉树或者哈夫曼树。按照结构体来存放树的结点的权值，双亲、左孩子、右孩子。通过建立赫夫曼树函数输入二叉树，并输出其赫夫曼树各节点编码。 哈夫曼算法的语言描述 根据给定的n个权值{w1,w2,…,wn}构成n棵二叉树的集合F={T1,T2,…,Tn},其中每棵二叉树Ti中只有一个带权为wi的根结点，其左右子树为空。 在F中选取两棵根结点的权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为其左右子树上根结点的权值之和。 在F中删除这两棵树，同时将新得到的二叉树加入F中。 重复②和③，直到F只含一棵树为止。这棵树便是哈夫曼树。 2.1.2赫夫曼树的应用 哈夫曼树的应用十分广泛，在不同的应用中，对叶子结点的权和带权路径长度有不同的解释。 沈 阳 大 学 课程设计说明书 No 2 哈夫曼树的应用之一是用于优化判断过程，利用哈夫曼树得到最佳判定算法。例如，将百分制转换成五级制的算法。显然，此算法很简单，只需利用if语句描述即可。 if ( x<60) score=’不及格’; else if ( x<70) score=’及格’; else if ( x<80) score=’中’; else if ( x<90) score=’良’; else score=’优’; 如果学生规模很大，该算法需反复多次执行，就应该考虑算法执行的时间问题。在实际应用中，学生的成绩呈正态分布，大部分在70~89分之间，优秀和不及格的概率较小。假设不及格、及格、中、良、优的百分比为5％、12%、40%、35%、8%，则上述算法80%以上的成绩需要进行三次或三次以上的比较才能得到结果。若以这些百分比值5,12,40,35,8为权值，使用哈夫曼算法来构造一棵判定树，则得到判定过程，可使多数成绩经过较少的比较即可得到结果。但由于每个判定框都有两次比较，将两次比较分开，得到判定树，按此判定树构造程序，显然可以大大减少比较次数。 2.1.3哈夫曼树在数据编码中的应用 在数据通信中，需要将传送的文字转换成二进制的字符串，用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，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。但这样长短不等的编 沈 阳 大 学 课程设计说明书 No 3
码又会产生一个新问题，即如何解译成原文？除非设计时能够保证任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，符合此要求的编码称为前缀编码。 为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。 我们用上述各字母出现的次数{8，4，5，3，1，1}作为权构造哈夫曼树，如图6.36所示。约定左分支表示字符“0”，右分支表示字符“1”，则可以从根结点到叶子结点的路径的分支上的字符组成的字符串作为该叶子对应字符的编码。可以证明，如此得到的必为二进制前缀编码，而且是一种最优前缀编码。我们称这样的树为哈夫曼编码树，由此得到的编码称为哈夫曼编码。本例中字母A、E、R、T、F、D的哈夫曼编码分别为11、00、01、011、0100、0101。可以看出，出现次数较多的字母A、E、R，具有最短的编码，长度均为2；而出现次数最少的字母F、D，具有最长的编码，长度均为4。报文的最短传送长度为：6 L=WPL=S(wklk)=4×2+5×2+8×2+3×3+1×4+1×4=51 k=1 若采用等长编码，报文的传送长度为 L=8×3+4×3+5×3+3×3+1×3+1×3=66 显然，哈夫曼编码比等长编码所得到的报文长度要短得多。哈夫曼编码是最优前缀编码。 一个任意长度的编码序列可被唯一地翻译为一个字符序列（单词）。依次取出编码序列中的0或1，从哈夫曼编码树的根结点开始寻找一条路径。若为0，则沿着左分支向下走；若为1，则沿着右分支向下走。每到达一个叶子外结点时，就译出一个相应的字符，然后再回到哈夫曼树的根结点处，依次译出余下的字符，最后得到一个单词。 2.2 数据结构设计 通过建立一个赫夫曼树的简易程序，可以实现建立最优二叉树函数，并且可以建立函数输入二叉树，并输出其赫夫曼树。 沈 阳 大 学 课程设计说明书 No 4 此程序是线性链表式存储结构，这种存储结构便于数据的插入和删除，同时还节约存储空间。 各种编码方式 (1)定长编码 根据出现的字符种数进行编码 (2)变长编码 采取这种变长编码方式，需要遵循一个原则，即每一个字符的编码都不应该是另一个字符编码的前缀。否则就会出现二义性。 一个可用的编码必须满足每个字符的编码不能是其他编码的前缀。 也可以看出，每一个可用的编码都可以转化成二叉树的形式，这样编码理论便可以与二叉树的一些性质结合起来，就可以应用二叉树的理论知识来解决编码问题。 那么总的编码长度为：WPL=w1*L1+w2*L2+w3*L3+w4*L4 可以看出，该公式与哈夫曼树满足的公式一模一样，那么我们可以采取构造哈夫曼树的方式来求编码的长度。 对哈夫曼树进行编码，每一个结点的左分支上面标0，右分支上面标1,从根结点到各个叶子结点，所经分支上面的0、1序列，就是该叶子结点所代表字符的编码。 假设有n个权值{w1，w2，…wn}，每个权值赋给一个叶子，可以构造出多棵含n个叶子结点的二叉树。其中，必存在一棵其带权路径长度WPL取最小值的二叉树，称为最优二叉树。 因为构造这种树的算法最早是哈夫曼1952年提出来的，所以被称为哈夫曼树(Huffman Tree)。 如何构造哈夫曼树？D.A.Huffman 最早研究出一个带有一般规律的构造算法，俗称哈夫曼算法，其基本思想是让权值最大的叶子离根最近。构造方法如下： (1) 由给定的n个权值{w1, w2, …, wn}，构造n棵扩充二叉树的集合F = {T1, T2, …, Tn}，其中每棵扩充二叉树中均只含一个带权值wi的根结点,其左、右子树均为空； (2) 重复下列步骤，直到F中只含一棵树为止：j 在F中选取其根结点的权值为最小的两棵扩充二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;k 从F中删去这两棵树，同时加入刚生成的新树； (3) 按上述步骤得到的二叉树就是哈夫曼树。 沈 阳 大 学 课程设计说明书 No 5
2.3 设计思路及算法设计 2.3.1功能模块图 赫夫曼树的建立 统计字符出现的频率 查找最小的两个权 构造赫夫曼树并输出 图1功能模块图 2.3.2功能模块图思路设计 设需要编码的字符集合为{d1,d2,……,dn},各个字符在电文中出现的次数集合为{w1,w2,……,wn}，以d1,d2,……,dn作为叶结点，以w1,w2,……,wn作为各叶结点的权值构造一棵二叉树，规定赫夫曼树中的左分支为0，右分支为1，则从根结点到每个叶结点所经过的分支对应的0和1组成的序列便为该结点对应字符的编码。这样的代码总长度最短的不等长编码称为赫夫曼编码。 赫夫曼算法： 根据给定的n个权值{w1，w2，w3，……wn}构成n棵二叉树的集合F={T1，T2，T3，……Tn}，其中每棵二叉树Ti中只有一个带权为Wi的根结点，其左右树均空。 在F中选取两棵根结点的 权值最小的树作为左右子树构造一棵新的二叉树，且置新的二叉树的根结点的权值为期左、右子树上根结点的权值之和。 在F中删除这棵树，同时将新得到的二叉树加入F中。 重复(2)和(3)的过程，直到F只含一棵树为止。这棵树便是哈夫曼树。 设给定的权值集合为{5，4，7，2}，构造哈夫曼树的过程如图6.34 所示。首先构造每棵树只有一个结点的森林，如图2(a)所示；然后每次选择两个根结点权值最小的二叉树，以它们为左、右子树构造新的二叉树，步骤参看图2(b)，(c)和(d)，最后得到一棵 沈 阳 大 学