哈夫曼树的实验报告1.doc

需求分析 本演示程序实现Haffman编/译码器的作用， 目的是为信息收发站提供一个编/译系统，从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间，降低成本等目标。系统要实现的两个基本功能就是：① 对需要传送的数据预先编码；② 对从接收端接收的数据进行译码； 本演示程序需要在终端上读入n个字符（字符型）及其权值（整形），用于建立Huffman树,存储在文件hfmanTree.txt中；如果用户觉得不够清晰还可以打印以凹入表形式显示的Huffman树； 本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile中；然后利用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件TextFile中；最后在屏幕上显示代码（每行50个），同时显示对CodeFile中代码翻译后的结果； 本演示程序将综合使用C++和C语言； 测试数据： (1)教材例6-2中数据：8个字符，概率分别是0.05，0.29，0.07，0.08，0.14，0.23，0.03，0.11，可将其的权值看为5，29，7，8，14，23，3，11 (2)用下表给出的字符集和频度的实际统计数据建立Haffman树，并实现以下报文的编码和译码：“THIS PROGRAM IS MY FAVORITE”. 字符 空格 A B C D E F G H I J 频度 186 64 13 22 32 103 21 15 47 57 1 字符 K L M N O P Q R S T U 频度 5 32 20 63 15 1 48 51 80 23 8 字符 V W X Y Z 频度 18 1 16 1 概要设计 设定哈夫曼树的抽象数据类型定义 ADT Huffmantree{ 数据对象：D={ai| ai ∈Charset,i=1,2,3,……n,n≥0} 数据关系：R1＝{ ai-1, ai | ai-1, ai ∈D, i=2,3,……n}　　基本操作：　　 Initialization(HT，HC,w，n,ch) 操作结果：根据n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量，最后字符编码存到HC中； Encodeing(n) 操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile中 Decodeing(HT,n) 操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 } ADT Huffmantree 2、本程序主要包括三个模块 1）主程序模块 void main() { 输入信息，初始化； 选择需要的操作； 生成Huffman树； 执行对应的模块程序； 输出结果； } 2）编码模块——根据建成的Huffman树对文件进行编码； 3）译码模块——根据相关的Huffman树对编码进行翻译； 各模块的调用关系如图所示 详细设计 1、树类型定义 typedef struct { unsigned int weight; //权值 char ch1; //储存输入的字符 unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; 2、编码类型定义 typedef char **HuffmanCode; 哈夫曼编译器的基本操作设置如下 Initialization(HuffmanTree HT，HuffmanCode HC,int *w，int n,char *ch) //根据输入的n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量存储编码，最后转存到HC中； Encodeing(int n) //根据建好的包含n个字符的Huffman树，对文件进行编码，编码结果存入到文件CodeFile中 Decodeing(HuffmanTree HT,int n) //根据已经编译好的包含n个字符的Huffman树HT，对文件的代码进行翻译，结果存入文件TextFile中 基本操作操作的算法 主函数及其他函数的算法 void main(){ while(TURE){ cin需要的操作请求c; switch(c){ case 1: Initialization(HT,hc,w,n,ch); break; case 2: Encoding(n); break; case 3: Decoding(HT,n); bre