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

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

1、Huffman编码的设计与实现宜春学院本科课程设计说明书学　院：数计学院专业年级：10信息与计算科学课程：信息论与编码课程设计设计题目：Huffman编码的设计与实现指导教师：赵志芳2012年12月12Huffman编码的设计与实现学生姓名：刘旭东学号：1031303124中文摘要哈夫曼编码是广泛用于数据文件压缩的十分有效的编码方法。其压缩通常在20%~90%之间。哈夫曼编码算法使用字符在文件中出现的频率表来建立一个用0,1串表示各字符的最优表示方式。哈夫曼算法构造的扩充二叉树称为哈夫曼编码树或哈夫曼树。当然

2、，还有编码和译码部分。本系统的前端开发工具是VisualC++6.0。具有输入字符集大小及权值大小，构造哈夫曼树，并对用户输入的字符串进行编码以及译码还有退出四种功能。本程序经过测试后，功能均能实现，运行稳定。关键词：哈夫曼树，编码，权值英文摘要Huffmancodingiswidelyusedindatafilecompressioncodingmethodisveryeffective.Thecompressionusuallybetween20%~90%in.Huffmanuseofthecharact

3、erencodingalgorithminthedocumentappearedinfrequencytablewith0tobuildastringofoptimaleachcharactersaidmeans.Thealgorithm'sconstructionhuffmanextendedbinarytreecalledhuffmancodingtreeorhuffmantree.Ofcourse,therearecodinganddecodingparts.Thissystemthefront-end

4、developmenttoolsisVisualc++6.0.Withinputcharactersetsizeandweithtsize,structuretreehuffman,anduserinputstringcodinganddecodingandexitfourfunctions.Thisprocedureaftertesting,functionsarerealized,steadyoperation.12Huffman编码的设计与实现目录引言31、问题分析42、算法设计53、算法实现63.1流

5、程图63.2程序代码73.3调试结果103.3.1例题5—7的测试结果103.3.2习题5-12的调试结果114、结论135、参考文献1312Huffman编码的设计与实现引言哈夫曼在上世纪五十年代初就提出这种编码时，根据字符出现的概率来构造平均长度最短的编码。它是一种变长的编码。哈夫曼编码应用广泛，如JPEG中就应用了哈夫曼编码。在编码中，若各码字长度严格按照码字所对应符号出现概率的大小的逆序排列，则编码的平均长度是最小的。构造好哈夫曼树后，就可根据哈夫曼树进行编码。然而怎样构造一棵哈夫曼树呢？最具有一般规

6、律的构造方法就是哈夫曼算法。字符根据其出现的概率作为权值构造一棵哈夫曼树后，经哈夫曼编码得到的对应的码值。只要使用同一棵哈夫曼树，就可把编码还原成原来那组字符。显然哈夫曼编码是前缀编码，即任一个字符的编码都不是另一个字符的编码的前缀，否则，编码就不能进行翻译。利用哈夫曼算法的编码和译码功能，重复地显示并处理以下项目，即构造哈夫曼树，编码及译码几项功能，直到选择退出为止。本次设计就是为这样的一个哈夫曼的编/译码器。哈夫曼编码所以能产生较短的码文，是因为哈夫曼树具有最小加权路径长度的二叉树。如果叶结点的权值恰好是

7、某个需编码的文本中各字符出现的次数，则编码后文本的长度就是该哈夫曼树的加权路径长度。译码过程为自做向右逐一扫描码文，并从哈夫曼树的根开始，将扫到的二进制位串中的相邻位与哈夫曼树上标的0，1相匹配，以确定一条从根到叶子结点的路径，一旦到达叶子，则译出了一个字符。再回到树根，从二进位串的下一位开始继续译码。软件运行环境及开发工具是VisualC++6.0。12Huffman编码的设计与实现1、问题分析为了建立哈夫曼树以及实现哈夫曼编码以及译码，因此我们选择了结点结构体，利用这一结构体，我们定义了一个结构体数组和一

8、个树根指针，数组用来纪录输入数据的多少，树根指针用来连接哈夫曼树。从程序中可以看到使用哈夫曼算法构造哈夫曼树过程，是从n棵知识一个根结点的树组成的森林开始的。在算法执行中，哈夫曼树是由若干棵树组成的森林，通过不断地合作树，最后得到一棵哈夫曼树。为了便于实现哈夫曼树的建树运算，定义程序的哈夫曼树类HfmTree，它包括如下两个私有数据成员tree和weight：其中，tree是一个二叉树BinaryT