哈夫曼树的实验报告1

哈夫曼编/译器需求分析本演示程序实现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树，并实现以下报文的编码和译码：“THISPROGRAMISMYFAVORITE”.字符空格ABCDEFGHIJ频度18664132232103211547571字符KLMNOPQRSTU频度5322063151485180238字符VWXYZ频度181161概要设计设定哈夫曼树的抽象数据类型定义ADTHuffmantree{数据对象：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中}ADTHuffmantree2、本程序主要包括三个模块1）主程序模块voidmain(){输入信息，初始化；选择需要的操作；生成Huffman树；执行对应的模块程序；输出结果；}2）编码模块——根据建成的Huffman树对文件进行编码；3）译码模块——根据相关的Huffman树对编码进行翻译；各模块的调用关系如图所示详细设计1、树类型定义typedefstruct{unsignedintweight;//权值charch1;//储存输入的字符unsignedintparent,lchild,rchild;}HTNode,*HuffmanTree;2、编码类型定义typedefchar**HuffmanCode;哈夫曼编译器的基本操作设置如下Initialization(HuffmanTree&HT，HuffmanCode&HC,int*w，int&n,char*ch)//根据输入的n个字符及其它们的权值w[i],建立Huffman树HT,用字符数组ch[i]作为中间存储变量存储编码，最后转存到HC中；Encodeing(intn)//根据建好的包含n个字符的Huffman树，对文件进行编码，编码结果存入到文件CodeFile中Decodeing(HuffmanTreeHT,intn)//根据已经编译好的包含n个字符的Huffman树HT，对文件的代码进行翻译，结果存入文件TextFile中基本操作操作的算法①程序初始化，①程序初始化，建立Huffman树voidInitialization(HuffmanTree&HT,HuffmanCode&HC,int*w,int&n,char*ch){//根据输入n个字符及其权值w[i]创建哈夫曼树HT和对字符编码HCcin>>n;//输入包含的字符数cin.get(ch[m]);//输入字符集,包括需要的空格cin>>w[d];//输入对应的权值if(n<=1)return;//出错处理num=2*n-1;HT=(HuffmanTree)malloc((num+1)*sizeof(HTNode));//0号单元未用//初始化for(p=HT+1,i=1;i<=n;i++,p++){p->weight=w[i-1];p->lchild=0;p->parent=0;p->rchild=0;p->ch1=ch[i-1];}for(;i<=num;p++,i++){p->weight=0;p->lchild=0;p->parent=0;p->rchild=0;p->ch1=‘*';}for(i=n+1;i<=num;i++){select(HT,i-1,s1,s2);HT[s1].parent=i;HT[s2].parent=i;HT[i].lchild=s1;HT[i].rchild=s2;HT[i].weight=HT[s1].weight+HT[s2].weight;}//---从叶子到根逆向求每个字符的哈夫曼编码----HC=(HuffmanCode)malloc((n+1)*sizeof(char*));//分配n个字符编码的头指针向量char*cd=(char*)malloc(n*sizeof(char));//定义cd为字符数组，存储编码cd[n-1]=‘\0’;//for(i=1;i<=n;i++){//逐个字符求哈夫曼编码intstart=n-1;//编码结束符位置for(intf=HT[i].parent,c=i;f!=0;c=f,f=HT[f].parent)//从叶子到根逆向求编码if(HT[f].lchild==c)cd[--start]=‘0’elsecd[--start]=‘1’HC[i]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[i],&cd[start]);}//-----输出文件hfmTree.txt,保存生成树ofstreamfout("hfmTree.txt");fout<<ch[i];//向文件hfmTree.txt输入字符fout<<endl;fout<<HC[j]<<endl;//向文件hfmTree.txt输入编码fout.close();free(cd);}voidEncoding(intn)voidEncoding(intn){//编码：对文件TobeTran.txt进行编码 char*a=(char*)malloc(n*sizeof(char)); char**b=(char**)malloc(n*sizeof(char*)); for(intm=0;m<20;m++)b[m]=(char*)malloc(n*sizeof(char)); //利用c语言的动态分配,用a[g]存储字符,b[g][i]存储字符对应的编码 ifstreamfin("hfmTree.txt",ios::in);//读入文件 fin.get(a[i2]);//从文件中读取字符存入a[i2] fin>>b[j];//从文件中读取编码存入b[j][]中 fin.close(); ifstreamfin1("ToBeTran.txt");ofstreamfout("CodeFile.txt"); while(fin1.get(s)){ for(intg=0;g<n;g++){ if(a[g]==s)//寻找和hfmTree搭配的字符 fout<<b[g];//根据字符存储的位置进行输出相对应的编码 } } fin1.close(); fout.close();}voidDecoding(HuffmanTreeht,intn){//译码：对CodeFile.txt文件进行译码 ifstreamfin("CodeFile.txt"); ofstreamfout("TextFile.txt"); fin>>s; HuffmanTreehead=ht+2*n-1;//从根结点向下求译码 while(s[0]!=‘\0’ while(s[i]!=‘\0’) if(s[i]==‘1')head=ht+head->rchild; elseif(s[i]==‘0')head=ht+head->lchild; if((head->lchild)==0&&(head->rchild)==0) { fout<<(head->ch1); head=ht+2*n-1; } i++; } i=0; fin>>s; } fin.close(); fout.close();}②②编码③③译码主函数及其他函数的算法voidPrint(){//打印代码文件，显示在终端，每行50个代码,voidPrint(){//打印代码文件，显示在终端，每行50个代码,//同时显示翻译后的结果TextFile. ifstreamfin("CodeFile.txt"); ifstreamfin1("TextFile.txt"); while(fin1.get(s1)) cout<<s1;fin>>s; for(i=0;s[i]!=‘\0';i++){ cout<<s[i]; if((i+1)%50==0)cout<<endl; } cout<<endl; fin.close(); fin1.close();}voidselect(HuffmanTreeHT,intn,int&s1,int&s2){//依次比较，从哈夫曼树的中parent为0的节点中选择出两个权值最小的if(!HT[i].parent&&！HT[S1]&&!HT[S2]){if(HT[i].weight<HT[s1].weight){s2=s1;s1=i;}elseif(HT[i].weight<HT[s2].weight&&i!=s1)s2=i;}④④打印翻译得到的原文和代码⑤⑤用凹入表的形式打印哈夫曼树voidPvoidPrintTree(HuffmanTreenode,HuffmanTreenode1,intlevel){//打印哈夫曼树形，利用递归的方法if(node==NULL)return;ofstreamfout("TreePrint.txt",ios::app);//通过在文件的末尾进行输入for(inti=0;i<level;i++){fout<<"";cout<<"";}fout<<node1->ch1<<node1->weight<<endl;cout<<node1->ch1<<node1->weight<<endl;//利用递归的方法，一层一层地打印if(node1->rchild!=0){PrintTree(node,node+node1->rchild,level+1);}if(node1->lchild!=0){PrintTree(node,node+node1->lchild,level+1);}fout.close();}voidmain(){ while(TURE){ cin>>需要的操作请求c; switch(c){ case1: Initialization(HT,hc,w,n,ch);主函数 break;主函数 case2: Encoding(n); break; case3: Decoding(HT,n); break; case4: Print(); break; case5: PrintTree(HT,HT+2*n-1,1); break; case6: m=FALSE; } }}Main()3Main()EncodeingEncodeingDecodingPrintPrintTreeselectInitialization①②③④⑤调试分析本次实习作业最大的难点就是文件的读和写，这需要充分考虑到文件里面的格式，例如空格，换行等等，由于不熟悉C++语言和C语言的文件的输入和输出，给编程带来了很大的麻烦；原本计划将文本中的换行格式也进行编码，也由于设计函数比较复杂，而最终放弃；一开始考虑打印哈夫曼树的凹入表时是顺向思维，希望通过指针的顺序变迁来实现打印，但问题是从根结点到叶子结点的指针不是顺序存储的，所以未能成功，后来查找相关资料，最终利用递归的方法解决问题；程序中的数组均采用了动态分配的方法定义，力求达到减少空间的浪费；时间的复杂度主要是由查树这个步骤决定，因为无论是编码还是译码都需要对Huffman树进行查找和核对，但考虑到英文字母和空格也就是27个字符，影响不是很大；程序无论在屏幕显示还有文件存储方面都达到了不错的效果；程序不足的地方就是在文件文本格式方面处理得还是不够，或许可以通过模仿WORD的实现来改善。用户手册本程序运行于windowsXP,windowsvists,DOS系统，只需要运行“Huffmantree.exe”；进入演示程序后即显示一个有功能操作选择的界面，如下图：用户可以根据不同的需求进行选择操作；如图介绍，选择“1”时，由用户输入信息进行创建Huffman树，得到的Huffman树存在文件hfmTree.txt中；选择“2”时，程序将对文件ToBeTran.txt中的内容进行编码，结果存入CodeFile.txt中；选择“3”时，程序将对文件CodeFile中的代码进行翻译，结果存入文件TextFile中；选择“4”时，将会在屏幕上打印编译“ToBeTran.txt”得到的代码和翻译“CodeFile.txt”后得到的原文;选择“5”时，将会在屏幕上打印哈夫曼树的凹入表形式并存在文件“TreePrint.txt”中；退出程序，选择“6”。测试结果1、权值为5，29，7，8，14，23，3，11创建的哈夫曼树凹入表形式如下：*100*58*29