201440410234杜飞杨哈夫曼树的应用

《201440410234杜飞杨哈夫曼树的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、课程设计（论文）编号：B04900083学号：201440410234课程设计教学院计算机学院课程名称数据结构与算法课程设计题目哈夫曼树的应用专业计算机科学与技术班级计算机科学与技术（2）班姓名杜飞杨同组人员罗义飞范永康唐傲指导教师成俊17课程设计（论文）2015年12月27日课程设计任务书2015～2016学年第1学期学生姓名：杜飞杨专业班级：计算机科学与技术（2）班指导教师：成俊工作部门：计算机学院一、课程设计题目：哈夫曼树的应用二、课程设计内容1)从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.

2、将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；2)利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件Text.txt中的正文进行编码，然后将结果存入文件Code.txt中。3)17课程设计（论文）利用已建好的哈夫曼树将文件Code.txt中的代码进行译码，结果存入文件Text.txt中，并输出结果。三、进度安排1．分析问题，给出数学模型，选择数据结构。2．设计算法，给出算法描述，给出源程序清单。3．编辑、编译、调试源程序，撰写课程设计报告。四、基本要求1.界面友好，函数功能要划分好2.总体设计应画一流程图3.

3、程序要加必要的注释4.要提供程序测试方案5.程序一定要经得起测试，宁可功能少一些，也要能运行起来，不能运行的程序是没有价值的。目录一、概述3（一）课程设计目的3（二）课程设计实验要求3二、总体设计4（一）设计思想4（二）数据结构与算法设计4(三)个人任务6三、详细设计7(一)功能函数模块划分7（二）个人任务7四、调试分析和测试结果10五、心得体会与总结13六、参考文献1417课程设计（论文）17课程设计（论文）一、概述1.1课程设计目的1．理解和掌握该课程中的有关基本概念，程序设计思想和方法。2．培养综合运用所学知识独立完成课题的能力。3．培养

4、勇于探索、严谨推理、实事求是、有错必改，用实践来检验理论，全方位考虑问题等科学技术人员应具有的素质。4．掌握从资料文献、科学实验中获得知识的能力，提高学生从别人经验中找到解决问题的新途径的悟性，初步培养工程意识和创新能力。1.2课程设计实验要求从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树并将它存于文件hfmTree中.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上；利用已经建好的哈夫曼树（如不在内存，则从文件htmTree中读入），对文件text.txt中的正文进行编码，然后将结果存入文件Code中，并输出结果，将文件

5、Code以紧凑格式先是在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。利用已建好的哈夫曼树将文件Code中的代码进行译码，结果存入文件Text中，并输出结果。17课程设计（论文）二、总体设计2.1设计思想哈夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。2.2数据结构与算法设计哈夫曼编译码器的主要功能是先建立哈夫曼树，然后利用建好的哈夫曼树生成哈夫曼编码后进行译码。在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵哈夫曼树，规定哈夫曼树中的左分之代表0，右分支

6、代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为哈夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送其主要流程图如下图所示。17课程设计（论文）开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SELECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I<2*N?I++编码为1结束否否否右子是否为空是是否否是是是哈夫曼树编译码器

7、流程图17课程设计（论文）2.3个人任务我在组内负责哈弗曼树的数据结构设计与哈弗曼树的译码和哈夫曼树的数据结构：假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：(1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；(2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；(3)从森林中删除选取的两棵树，并将新树加入森林；(4)重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈

8、夫曼树。构造过程如下：（a） 有权值为1,2,3,4四棵树；（b） 由于树1,2的权值处于最小和次最小，所以选中，并合成为一棵树，小的权值位于左边；（