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

《 数据结构 》课程设计 ——赫夫曼编码/译码器设计 指导教师：孙树森、周维达 班级：09数媒（2）班 学号：姓名：林真超 数据结构课程设计实验报告 一、题目： 赫夫曼编码/译码器设计 二、目的： 1、提高分析问题、解决问题的能力，进一步巩固数据结构各种原理与方法。 2、熟悉掌握一门计算机语言，可以进行数据算法的设计。 三、要求 3.1总体要求 1、要充分认识课程设计对培养自己的重要性，认真做好设计前的各项准备工作。尤其是对编程软件的使用有基本的认识。 2、既要虚心接受老师的指导，又要充分发挥主观能动性。结合课题，独立思考，努力钻研，勤于实践，勇于创新。 3、独立按时完成规定的工作任务，不得弄虚作假，不准抄袭他人内容，否则成绩以不及格计。 4、在设计过程中，要严格要求自己，树立严肃、严密、严谨的科学态度，必须按时、按质、按量完成课程设计。 3.2实施要求 1、理解赫夫曼编码/译码的确切意义。 2、独立进行方案的制定，系统结构设计要合理。 3、在程序开发时，则必须清楚主要实现函数的目的和作用，需要在程序书写时说明做适当的注释。在写课设报告时，必须要将主要函数的功能和参数做详细的说明。 4、通过多组数据来检测该系统的稳定性和正确性。 3.3 课程设计报告的内容及要求 在完成课题验收后，学生应在规定的时间内完成课程设计报告一份（不少于2000字）。 一、实验目的 进一步掌握最优二叉树的含义。 掌握最优二叉树的结构特征，以及各种存储结构的特点及使用范围。 熟练掌握哈夫曼树的建立和哈夫曼编码方法。 掌握用指针类型描述、访问和处理运算。 二、实验原理 哈夫曼（Huffman）编码属于码词长度可变的编码类，是哈夫曼在1952年提出的一种编码方法，即从下到上的编码方法。同其他码词长度可变的编码一样，可区别的不同码词的生成是基于不同符号出现的不同概率。生成哈夫曼编码算法基于一种称为“编码树”（coding tree）的技术。算法步骤如下： （1）初始化，根据符号概率的大小按由大到小顺序对符号进行排序。 （2）把概率最小的两个符号组成一个新符号（节点），即新符号的概率等于这两个符号概率之和。 （3）重复第2步，直到形成一个符号为止（树），其概率最后等于1。 （4）从编码树的根开始回溯到原始的符号，并将每一下分枝赋值为1，上分枝赋值为0。 译码的过程是分解电文中字符串，从根出发，按字符“0”或“1”确定找做孩子或右孩子，直至叶子节点，便求得该子串相应的字符。 三、实验内容 （一）需求分析 一个完整的系统应具有以下功能： (1) I：初始化。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。 (2) E：编码。利用已建好的哈夫曼树，对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。 (3) D：译码。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件Textfile中。 (4) P：印代码文件（Print）.将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin中。 (5) T：印哈夫曼树（Treeprinting）.将已在内存中的哈夫曼树以直观的方式（比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint 中。 （二）实验步骤 1.定义结点结构，定义哈夫曼树结构； 2.初始化哈夫曼树，存储哈夫曼树信息； 3.定义求哈夫曼编码的函数； 4.定义译哈夫曼编码的函数； 5.写出主函数。 6.测试系统。 （三）概要设计 1 设计思想 赫夫曼树用邻接矩阵作为存储结构，借助静态链表来实现遍历。 2 函数间的关系 函数间的关系如图所示： 图3.1 函数间的关系 3 数据结构与算法设计 赫夫曼编\译码器的主要功能是先建立赫夫曼树，然后利用建好的赫夫曼树生成赫夫曼编码后进行译码 。 在数据通信中，经常需要将传送的文字转换成由二进制字符0、1组成的二进制串，称之为编码。构造一棵赫夫曼树，规定赫夫曼树中的左分之代表0，右分支代表1，则从根节点到每个叶子节点所经过的路径分支组成的0和1的序列便为该节点对应字符的编码，称之为赫夫曼编码。 最简单的二进制编码方式是等长编码。若采用不等长编码，让出现频率高的字符具有较短的编码，让出现频率低的字符具有较长的编码，这样可能缩短传送电文的总长度。赫夫曼树课用于构造使电文的编码总长最短的编码方案。 其主要流程图如图3.2所示。 图3.2 赫夫曼树编\译码器流程图 4.功能函数模块划分 void main() void printhead() void printree(HuffmanTree HT,int w) //打印赫夫