哈夫曼树_数据结构课程设计.doc

《哈夫曼树_数据结构课程设计.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《数据结构》课程设计——赫夫曼编码/译码器设计指导教师：孙树森、周维达班级：09数媒（2）班学号：E09700203姓名：林真超一、数据结构课程设计实验报告一、题目：赫夫曼编码/译码器设计二、目的：1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。2、熟悉掌握一门计算机语言，可以进行数据算法的设计。三、要求3.1总体要求1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作。尤其是对编程软件的使用有基本的认识。2、既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于

2、创新。3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。3.2实施要求1、理解赫夫曼编码/译码的确切意义。2、独立进行方案的制定，系统结构设计要合理。3、在程序开发时，则必须清楚主要实现函数的目的和作用，需要在程序书写时说明做适当的注释。在写课设报告时，必须要将主要函数的功能和参数做详细的说明。4、通过多组数据来检测该系统的稳定性和正确性。3.3课程设计报告的内容及要求在完成课题验收后，学生应在规定的时间内

3、完成课程设计报告一份（不少于2000字）。1一、实验目的1．进一步掌握最优二叉树的含义。2．掌握最优二叉树的结构特征，以及各种存储结构的特点及使用范围。3．熟练掌握哈夫曼树的建立和哈夫曼编码方法。4．掌握用指针类型描述、访问和处理运算。二、实验原理哈夫曼（Huffman）编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（codingtree）的技术。算法步骤如下：（1）初始化

4、，根据符号概率的大小按由大到小顺序对符号进行排序。（2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。（3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。（4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。译码的过程是分解电文中字符串，从根出发，按字符“0”或“1”确定找做孩子或右孩子，直至叶子节点，便求得该子串相应的字符。三、实验内容（一）需求分析一个完整的系统应具有以下功能：(1)I：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它

5、存于文件hfmTree中。(2)E：编码。利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。(3)D：译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。(4)P：印代码文件（Print）.将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。(5)T：印哈夫曼树（Treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件

6、TreePrint中。（二）实验步骤1.定义结点结构，定义哈夫曼树结构；2.初始化哈夫曼树，存储哈夫曼树信息；3.定义求哈夫曼编码的函数；4.定义译哈夫曼编码的函数；5.写出主函数。6.测试系统。20（三）概要设计1设计思想赫夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。2函数间的关系函数间的关系如图所示：主函数显示表头初始化树输入字符编码译码打印编码打印赫夫曼树选最小两个权值Select()图3.1函数间的关系3数据结构与算法设计赫夫曼编译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码。在数据通

7、信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。其主要流程图如图3.2所示。20开始结点数是否大于1将data和权值赋给ht输出根结点和权值调用SEL

8、ECT函数计算根结点函数父结点为两子结点之和输出两子结点和已构造的结点是否为根结点？左子是否为空？此时编码为0I<2*N?I++编码为1结束否否否右子是否为空是是否否是是是图3.2赫夫曼树编