原创力文档- 1、本文档共24页，可阅读全部内容。
- 2、原创力文档（book118）网站文档一经付费（服务费），不意味着购买了该文档的版权，仅供个人/单位学习、研究之用，不得用于商业用途，未经授权，严禁复制、发行、汇编、翻译或者网络传播等，侵权必究。
- 3、本站所有内容均由合作方或网友上传，本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺！文档内容仅供研究参考，付费前请自行鉴别。如您付费，意味着您自己接受本站规则且自行承担风险，本站不退款、不进行额外附加服务；查看《如何避免下载的几个坑》。如果您已付费下载过本站文档，您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等，请点击“版权申诉”（推荐），也可以打举报电话：400-050-0827(电话支持时间：9:00-18:30)。
- 5、该文档为VIP文档，如果想要下载，成为VIP会员后，下载免费。
- 6、成为VIP后，下载本文档将扣除1次下载权益。下载后，不支持退款、换文档。如有疑问请联系我们。
- 7、成为VIP后，您将拥有八大权益，权益包括：VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
- 8、VIP文档为合作方或网友上传，每下载1次， 网站将根据用户上传文档的质量评分、类型等，对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
.
中南大学
数据结构课程设计报告
题目哈夫曼编译器
学生姓名
指导教师
学院信息科学与工程学院
专业班级计科1302
Word资料
.
目录
实验要求……………3
问题描述……………3
问题解决方法………3
程序模块功能及流程图……………4
调试与测试…………8
测试结果……………9
心得体会……………11
源代码………………12
Word资料
.
一．实验要求
(1)从键盘读入字符集大小n,以及n个字符和权值，建立哈夫曼树。
(2)利用已建好的哈夫曼树对文件正文进行编码，将结果存入相关文件中。
(3)利用已建好的哈夫曼树将编码文件中的代码进行译码，结果存入文件中。
(4)输出代码文件，以紧凑格式显示。
二．问题描述
利用哈夫曼编码进行通信可以大大提高信道利用率，缩短信息传输时间，降
低传输成本。这要求在发送端通过一个编码系统对待传数据预先编码，在接收端
将传来的数据进行译码。对于双向传输信息的信道，每端都需要一个完整的编译
码系统。为这样的信息收发站编写哈夫曼编译系统。
哈夫曼树又称最优二叉树，构造的规则即给定n个权值不同的叶子节点，
构造一棵二叉树，使二叉树的带权路径长度达到最小。具体做法即要使权值较大
的结点离根节点较近，权值较小的结点离根节点较远。
三．问题解决方法
建立哈夫曼树时要进行多次选择，每次选择出权值最小和次小的两个节点,
Word资料
.
将两结点权值相加，作为新生成父节点的权值。并分别将其作为左、右孩子。再
将父节点加入需选择的结点序列中，继续选择，直到将所有节点都选完为止，构
成一颗哈夫曼树。每种字符对应一个节点，将每种字符的出现次数作为对应节点
权值。
在编码过程中，较科学的方法是统计文章中每种字符出现的频率，并以其作
为对应节点的权值，使出现频率较高的节点离根结点较近，从而使出现频率越高
的字符所得的编码位数越少，这样做得到的编码结果是最简练的，也更有利于译
码。
编码需从叶节点向上回溯，若叶节点为其父结点的左孩子，则编码为0，若
为右孩子，则编码为1。然后将父节点作为下一轮循环的子节点，继续重复上述
步骤，直至到达根节点为止，即得到初始叶节点对应的编码。
译码是编码的逆过程，所以译码只需读入编码位串，从根结点开始，若读到
0，则走向左孩子，读到1，则走向右孩子。并将对应的子节点作为下一轮循环
的叶节点，重复上述步骤，直至到达最终叶节点，该叶节点即为编码对应的节点。
四．程序模块功能及流程图
1.主要程序模块及功能
（1）建立哈夫曼树
数据结构：
tree[]为定义在Huffmantree类上的数组对象。
n为节点个数，即字符种类数。
m为建好的哈夫曼树的总节点数，在哈夫曼树中，m=2*n-1。
Smal、small2分别存放每轮循环中权值最小和次小的节点的权值。
Word资料
.
p1,p2分别记住每次合并时权值最小和次小的两个根结点的下标。
对应代码段：
for(i=0;im;i++){
tree[i]=newHuffmantree();
}
floatsmall1,small2;//建立哈夫曼树
文档评论（0）