哈夫曼树专题总结报告.pdfVIP

专题设计(二叉树)报告 题 目：文件压缩 （哈夫曼树） 小组成员： 吴旭晨 （1120121358 ） 周浩天 （1120121365 ） 熊威博 （1120121359 ） 郝鑫钢 （1120122756 ） 魏 鑫 （1120121357 ） 王俊博 （1120121355 ） 2014/5/7 1. 问题描述 在信息通信过程中，我们需要传输大量文件。在大的文件中有许多 冗余，为了提高信道利用率、缩短信息传输时间、降低传输成本，我们 设计一个编译系统，发送方利用哈夫曼编码对文件进行压缩后传输，接 收方将接收到的数据进行译码。 2. 基本要求 一个完整的系统应具有以下功能： (1) I ：初始化 （Initialization ）。从终端读入字符集大小n ，以及n个字符 和n个权值，建立哈夫曼树，并将它存于文件hfmTree 中。 (2) E ：编码 （Encoding ）。利用已建好的哈夫曼树 （如不在内存，则从 文件hfmTree 中读入），对文件ToBeTran 中的正文进行编码，然后将结 果存入文件CodeFile 中。 (3) D ：译码 （Decoding ）。利用已建好的哈夫曼树将文件CodeFile 中的 代码进行译码，结果存入文件Textfile 中。 (4) P ：印代码文件 （Print ）。将文件CodeFile 以紧凑格式显示在终端 上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrin 中。 (5) T ：印哈夫曼树 （Tree printing ）。将已在内存中的哈夫曼树以直观 的方式 （比如树）显示在终端上，同时将此字符形式的哈夫曼树写入文 件TreePrint 中。 3. 数据结构 利用字符和权值建立哈夫曼树求得哈夫曼编码。利用二叉树先序遍 历输出哈夫曼树。 4. 测试数据 用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下 报文的编码和译码：“THIS PROGRAME IS MY FAVORITE” 。 字 A B C D E F G H I J K L M 符 频 186 64 13 22 32 103 2 1 15 47 57 1 5 32 20 度 字 N O P Q R S T U V W X Y Z 符 频 57 63 15 1 48 51 80 23 8 18 1 16 1 度 5. 实验设计与实现 a、数据结构设计 在程序中要用到两种结构类型，一种是哈夫曼树的节点类 型，另一种是哈夫曼编码的结构类型。 在哈夫曼树的节点类型中应该存放权值、左子链、右子 链，另外为了在生成哈夫曼树时，能方便地由儿子节点找到父 节点，要设置父节点链。 在编码类型中需要设置一个设置bit[]保存由叶节点到根节 点的路径所对应的哈夫曼编码，还要设置一个数据域start表 示哈夫曼编码在数组中的起始位置。这样每个叶节点的哈夫曼 编码是从数组bit[]的起始位置start开始到数组结束位置中存 放的0和1的序列。定义这两个结构类型的代码如下： #define maxlen 100 //最长编码 struct Node //哈夫曼树的节点类型 { int weight; //权重 int parent; int lchild; int rchild;