课程设计+哈夫曼树及哈夫曼编码.doc

课程设计哈夫曼树及哈夫曼编码一(课程设计简介哈夫曼树及哈夫曼编码目的:利用哈夫曼编码进行通信可以大大提高信道利用率,缩短信息传输时间,降低传输成本,试设计一个哈夫曼编码系统。通过本课程设计,应使学生掌握哈夫曼编码的特点、存储方法和基本原理,培养学生运用C语言正确编程及调试的能力,运用数据结构解决简单的实际问题的能力,为后续计算机专业课程的学习打下坚实的基础。题目:一、用下表中给出的字符和频度数据编程建立哈夫曼树,并实现对以下报文进行编码。THISPROGRAMISMYFAVORITE字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161二、编程从键盘任意输入一段报文,统计字符的频度并建立哈夫曼树,并给出报文的编码。二(哈夫曼编码的基本原理和方法哈夫曼编码是根据可变长最佳编码定理,应用哈夫曼算法而产生的一种编码,是消除编码冗余度最常用的方法。它的平均码字长度在具有相同输入概率集合的前提下,比其它任何一种可译码都小,因此,也常被称为紧凑码。1(哈夫曼树原理:一般而言,给定n个实数w1,w2,((((((,wn(n?,),求一个具有n个结点的二叉数,使其带权路径长度最小。所谓树的带权路径长度,就是树中所有的叶结点的权值乘上其到根结点的路径长度(若根结点为0层,叶结点到根结点的路径长度为叶结点的层数)。树的带权路径长度记为WPL=(W1*L1+W2*L2+W3*L3+...+Wn*Ln),N个权值Wi(i=1,2,...n)构成一棵有N个叶结点的二叉树,相应的叶结点的路径长度为Li(i=1,2,...n)。可以证明哈夫曼树的WPL是最小的。哈夫曼在上世纪五十年代初就提出这种编码时,根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。在编码中,若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列,则编码的平均长度是最小的。(注:码字即为符号经哈夫曼编码后得到的编码,其长度是因符号出现的概率而不同,所以说哈夫曼编码是变长的编码。)由于哈夫曼给出了构造这种树的规律,将给定结点构成一棵带权树的路径长度最小的二叉数,因此称为哈夫曼树。方法:(1)根据与n个权值{w1,w2„wn}对应的n个结点构成具有n棵二叉树的森林F={T1,T2„Tn},其中第i棵二叉树Ti(1?i?n)都只有一个权值为wi的根结点,其左、右子树均为空(2)在森林F中选出两棵根结点的权值最小的树作为一棵新树的左、右子树,且置新树的根结点的权值为其左、右子树上根结点权值之和(3)从F中删除构成新树的那两棵,同时把新树加入F中(4)重复第(2)和第(3)步,直到F中只含有一棵为止,此树便为哈夫曼树此部分参考:曲建民刘元红郑陶然编著(数据结构(;语言)(清华大学出版社(2005)(即课本),(哈夫曼编码(,)根据最优二叉树构造哈夫曼编码利用哈夫曼树很容易求出给定字符集及其概率(或频度)分布的最优前缀码。哈夫曼编码正是一种应用广泛且非常有效的数据压缩技术。该技术一般可将数据文件压缩掉20,至90,,其压缩效率取决于被压缩文件的特征。(,)具体做法(1)用字符ci作为叶子,pi或fi做为叶子ci的权,构造一棵哈夫曼树,并将树中左分支和右分支分别标记为0和1;(2)将从根到叶子的路径上的标号依次相连,作为该叶子所表示字符的编码。该编码即为最优前缀码(也称哈夫曼编码)。(,)哈夫曼编码为最优前缀码由哈夫曼树求得编码为最优前缀码的原因:?每个叶子字符ci的码长恰为从根到该叶子的路径长度li,平均码长(或文件总长)又是二叉树的带权路径长度WPL。而哈夫曼树是WPL最小的二叉树,因此编码的平均码长(或文件总长)亦最小。?树中没有一片叶子是另一叶子的祖先,每片叶子对应的编码就不可能是其它叶子编码的前缀。即上述编码是二进制的前缀码。(,)求哈夫曼编码的算法思想方法给定字符集的哈夫曼树生成后,求哈夫曼编码的具体实现过程是:依次以叶子T[i](0?i?n-1)为出发点,向上回溯至根为止。上溯时走左分支则生成代码0,走右分支则生成代码1。注意:?由于生成的编码与要求的编码反序,将生成的代码先从后往前依次存放在一个临时向量中,并设一个指针start指示编码在该向量中的起始位置(start初始时指示向量的结束位置)。?当某字符编码完成时,从临时向量的start处将编码复制到该字符相应的位串bits中即可。?因为字符集大小为n,故变长编码的长度不会超过n,加上一个结束符'[message]',bits的大小应为n+1。(,)文件的编码和解码:有了字符集的哈夫曼编码表之后,对数据文件的编码过程是:依次读人文件中的字符c,在哈夫曼编码表H中找到此字符,=c,则将字符c转