10信计刘旭东-哈夫曼编码课程设计

《10信计刘旭东-哈夫曼编码课程设计》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、宜春学院本科课程设计说明书学院：数计学院专业年级：10信息与计算科学课程：信息论与编码课程设计设计题Huffman编码白勺设计与实现指导教师：赵志芳2012年12月学生姓名：刘旭东学号：1031303124中文摘要哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩通常在20%〜90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然，还有编码和译码部分。本系统的前端开发工具是VisualC++6.0。具有输入字符集大小及权值大小，构造哈夫曼树，并对

2、用户输入的字符串进行编码以及译码述有退出四种功能。本程序经过测试后，功能均能实现，运行稳定。关键词：呛夫曼树，编码，权值英文摘要Huffmancodingiswidelyusedindeltafilecompressioncodingmethodisveryeffective.Thecompressionusual1ybetween20%、90%in.Huffmanuseofthecharacterencodingalgorithminthedocumentappearedinfrequencytablewith0tobuildastringofoptima

3、leachcharactersaidmeans.Thealgorithm"sconstructionhuffmanextendedbinarytreccalledhuffmancodingtrecorhuffmantree.Ofcourse,therearccodinganddecodingparts.Thissystemthefront-enddevelopmenttoolsisVisualc++6.0.Withinputcharactersetsizeandweithtsize,structuretreehuffman,anduserinputstrin

4、gcodinganddecodingandexitfourfunctions.Thisprocedureaftertesting,functionsarerealized,steadyoperation.目录引言31、问题分析42、算法设计53、算法实现53.1流程图53.2程序代码63.3调试结果103.3.1例题5—7的测试结果103.3.2习题5・12的调试结果114、结论125、参考文献12引言哈夫曼在上世纪五十年代初就提岀这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。

5、在编码屮，若各码字长度严格按照码字所对应符号出现概率的人小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造-•棵哈夫曼树呢？最具有一•般规律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。利用哈夫曼算法的编码和译码功能，重复地显示并处理以下项口，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。木次设计

6、就是为这样的一个哈夫曼的编/译码器。哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是某个需编码的文本屮齐字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与呛夫曼树上标的0,1相匹配，以确定一条从根到叶子结点的路径，一口到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。软件运行环境及开发工具是VisualC++6.0。1、问题分析为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结

7、构体，利用这一结构体，我们定义了一个结构体数组和一个树根指针，数组用来纪录输入数据的多少，树根指针用来连接哈夫曼树。从程序小可以看到使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。在算法执行中，呛夫曼树是由若干棵树组成的森林，通过不断地合作树，最后得到一棵哈夫曼树。为了便于实现哈夫曼树的建树运算，定义程序的哈夫曼树类HfmTree,它包括如下两个私有数据成员tree和weight：其屮，tree是一个二义树BinaryTree类型对象，是一棵哈夫曼树，weight是tree所代表的哈夫曼树的权值。在本课程设计中使用函数Huffma

8、n()。构造哈夫曼树算法：(1)用给定的一组权值{W