数据结构课设_赫夫曼树.doc

PAGE . . . 赫夫曼树的建立 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赫夫曼树的应用 哈夫曼树的应用十分广泛，在不同的应用中，对叶子结点的权和带权路径长度有不同的解释。 哈夫曼树的应用之一是用于优化判断过程，利用哈夫曼树得到最佳判定算法。例如，将百分制转换成五级制的算法。显然，此算法很简单，只需利用if语句描述即可。 if ( x60) score=’不及格’; else if ( x70) score=’及格’; else if ( x80) score=’中’; else if ( x90) 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，自然会想到设计编码时，让使用频率高的用短码，使用频率低的用长码，以优化整个报文编码。但这样长短不等的编码又会产生一个新问题，即如何解译成原文？除非设计时能够保证任何一个字符的编码都不是同一字符集中另一个字符的编码的前缀，符合此要求的编码称为前缀编码。 为使不等长编码为前缀编码，可用字符集中的每个字符作为叶子结点生成一棵编码二叉树，为了获得传送报文的最短长度，可将每个字符的出现频率作为字符结点的权值赋予该结点上，求出此树的最小带权路径长度就等于求出了传送报文的最短长度。因此，求传送报文的最短长度问题转化为求由字符集中的所有字符作为叶子结点，由字符出现频率作为其权值所产生的哈夫曼树的问题。利用哈夫曼树来设计二进制的前缀编码，既满足前缀编码的条件，又保证报文编码总长最短。 我们用上述各字母出现的次数{8，4，5，3，1，1}作为权构造