《哈夫曼树的实验报告1》由会员分享，可在线阅读，更多相关《哈夫曼树的实验报告1（8页珍藏版）》请在金锄头文库上搜索。
1、一、 需求分析1、本演示程序实现Haffman编/译码器的作用，目的是为信息收发站提供一个编/译系统， 从而使信息收发站利用Haffman编码进行通讯，力求达到提高信道利用率，缩短时间, 降低成本等目标。系统要实现的两个基本功能就是：对需要传送的数据预先编码； 对从接收端接收的数据进行译码；2、本演示程序需要在终端上读入n个字符(字符型)及其权值(整形)，用于建立Huffman 树，存储在文件hfmanTree .txt中；如果用户觉得不够清晰还可以打印以凹入表形式显 示的Huffman树；3、本演示程序根据建好的Huffman树，对文件的文本进行编码，结果存入文件CodeFile 中；然后利
2、用建好的Huffman树将文件CodeFile中的代码进行译码，结果存入文件 TextFile中；最后在屏幕上显示代码(每行50个)，同时显示对CodeFile中代码翻译 后的结果；4、本演示程序将综合使用C+和C语言；5、测试数据：(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” .字符空格ABCDEFGH
3、IJ频度18664132232103211547571字符KLMNOPQRSTU频度5322063151485180238字符VWXYZ频度181161一、 概要设计1、设定哈夫曼树的抽象数据类型定义ADT Huffmantree数据对象：D=a | a WCharset,i=1,2,3,n,n三0ii数据关系：R1= a , a | a , a WD, i=2,3,ni-1 ii-1 i基本操作：Initialization(&HT，&HC,w，n,ch)操作结果:根据n个字符及其它们的权值wi，建立Huffman树HT,用字符数组chi作为中间存储变量，最后字符编码存到HC中；Encode
4、ing(n)操作结果：根据建好的Huffman树，对文件进行编码，编码结果存入到文件CodeFile 中Decodeing(HT,n)操作结果：根据已经编译好的包含n个字符的Huffman树HT，将文件的代码进行翻译，结果存入文件TextFile中 ADT Huffmantree2、本程序主要包括三个模块1) 主程序模块void main()输入信息，初始化； 选择需要的操作；生成Huffman树；执行对应的模块程序；输出结果；2) 编码模块根据建成的Huffman树对文件进行编码;3) 译码模块一一根据相关的Huffman树对编码进行翻译; 各模块的调用关系如图所示二、 详细设计1、树类型定
5、义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个字符及其它们的权值wi,建立Huffman树HT,用字符数组chi 作为中间存储变量存储编码，最后转存到HC中；Encode
6、ing(int n)/根据建好的包含n个字符的Huffman树，对文件进行编码，编码结果存入到文件 CodeFile 中Decodeing(HuffmanTree HT,int n)/根据已经编译好的包含n个字符的Huffman树HT,对文件的代码进行翻译，结果 存入文件TextFile中基本操作操作的算法void Initialization(HuffmanTree &HT,HuffmanCode &HC,int *w,int &n ,char *ch) /根据输入n个字符及其权值wi创建哈夫曼树HT和对字符编码HC cinn; /输入包含的字符数cin.ge t( chm); /输入字符集
7、，包括需要的空格 cinwd; /输入对应的权值辻(n=l) ret urn;/出错处理num=2*nT;HT=(HuffmanTree)malloc(num+l)*sizeof(HTNode); /0 号单元未用 /初始化for(p=HT+1,i=1;i=n;i+,p+)p-weight=wi-1; p-lchild=0; p-parent=0; p-rchild=0; p-chl =chi-1; for(;i=num;p+,i+) p-weight=0; p-lchild=0; p-parent=0; p-rchild=0; p-chl = *;for(i=n+1;i=num;i+) se
8、lec t( HT,iT,sl,s2);HTs1.parent=i; HTs2.parent=i; HTi.lchild=s1; HTi.rchild=s2; HTi.weight=HTs1.weight+HTs2.weight;/-从叶子到根逆向求每个字符的哈夫曼编石- HC=(HuffmanCode)malloc(n+1)*sizeof(char *); /分配 n 个字符编码的头指针向量 char * cd=(char *)malloc(n*sizeof(char); /定义 cd 为字符数组，存储编码 cdn-1= 0；/编码结束符for(i=1;is; fin.close(); fo
9、ut .close();主函数及其他函数的算法void selec t(HuffmanTree HT,in t n,in t & sl,int & s2) /依次比较，从哈夫曼树的中 parent为0的节点中选择出两个权值最小的 if(!HTi.parent&! HTS1&!HTS2) if(HTi.weigh t HTsl.weigh t)s2=s1; s1=i;else if(HTi.weightHTs2.weight&i!二si)s2=i;打印翻译得到的 原文和代码用凹入表的形式 打印哈夫曼树void Print() /打印代码文件，显示在终端，每行50个代码, 同时显示翻译后的结果Te
10、xtFile.ifstream fin (CodeFile .txt);ifstream fin1(TextFile.txt);while(fin1.ge t( si)coutsi;fins;for(i=0;si!= 0;i+)coutsi;if(i+1)%50=0) coutendl;coutendl; fin.close(); fin1.close(); void Pri nt Tree( HuffmanTree node,HuffmanTree nodel, int level ) /打印哈夫 曼树形，利用递归的方法if( node = NULL ) return;ofs tream fou t(TreeP
