哈夫曼树实验报告

第页共页实验报告1、实验目的：(1)理解哈夫曼树的含义和性质。(2)掌握哈夫曼树的存储结构以及描述方法。(3)掌握哈夫曼树的生成方法。(4)掌握哈夫曼编码的一般方法，并理解其在数据通讯中的应用。2、实验内容：哈夫曼树与哈弗曼编码、译码a.问题描述：哈夫曼问题的提出可以参考教材P.145.利用哈弗曼编码进行通信可以大大提高通信利用率，缩短信息传输时间，降低传输成本。但是，这要求在发送端通过一个编码系统对待传数据预先编码，在接收端将传来的数据进行译码。b.算法提示：参见教材P.147-148算法6.12、6.13的描述。3、实验要求：建立哈夫曼树，实现编码，译码。○1.初始化（Initialization）。从终端读入字符集大小n，以及n个字符和n个权值，建立哈夫曼树，并将它存于文件hfmTree中。○2.编码（Encoding）。利用已建好的哈夫曼树（如不在内存，则从文件hfmTree中读入），对文件ToBeTran中的正文进行编码，然后将结果存入文件CodeFile中。○3.译码（Decoding)。利用已建好的哈夫曼树将文件CodeFile中的代码进行译码，结果存入文件TextFile中。○4.输出代码文件（Print）。将文件CodeFile以紧凑格式显示在终端上，每行50个代码。同时将此字符形式的编码文件写入文件CodePrint中。○5.输出哈夫曼树（TreePrinting）。将已在内存中的哈夫曼树以直观的方式（树或凹入表形式）显示在终端上，同时将此字符形式的哈夫曼树写入文件TreePrint中。测试数据：设权值c=(a,b,c,d,e,f,g,h)w=（5，29，7，8，14，23，3，11），n=8。按照字符‘0’或‘1’确定找左孩子或右孩子，则权值对应的编码为：5：0001，29：11，7：1110，8：111114：110，23：01，3：0000，11：001。四实验代码#includeiostream.h#includeiomanip.h#includestring.h#includemalloc.h#includestdio.htypedefstruct{intweight,K;第页共页intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;charstr[50];intwa[50];HuffmanTreeHT;HuffmanCodeHC;intw[50],i,j,n=8;charz[50];intflag=0;intnumb=0;//-----------------求哈夫曼编码-----------------------structcou{chardata;intcount;}cou[50];voidselect(HuffmanTreeHT,intj,int*s1,int*s2){inti;//找weight最小的结点for(i=1;i=j;i++)if(HT[i].parent==0){*s1=i;break;}for(;i=j;i++)if((HT[i].parent==0)&&(HT[i].weightHT[*s1].weight))*s1=i;HT[*s1].parent=1;//找weight次小的结点for(i=1;i=j;i++)if(HT[i].parent==0){*s2=i;break;}for(;i=j;i++)if((HT[i].parent==0)&&(i!=*s1)&&(HT[i].weightHT[*s2].weight))*s2=i;}//--------------算法6.12--------------------------voidHuffmanCoding(HuffmanTree&HT,HuffmanCode&HC,int*w,intn){intm,i,s1,s2,start;intc,f;HuffmanTreep;char*cd;if(n=1)return;//检测结点数是否可以构成树m=2*n-1;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));for(p=HT+1,i=1;i=n;i++,p++){p-weight=wa[i-1];p-parent=0;p-lchild=0;p-rchild=0;}for(;i=m;++i,++p)p-parent=0;for(i=n+1;i=m;++i)//建哈夫曼树{select(HT,i-1,&s1,&s2);第页共页HT[s1].parent=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*));cd=(char*)malloc(n*sizeof(char));cd[n-1]='\0';for(i=1;i=n;i++){start=n-1;for(c=i,f=HT[i].parent;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]);}free(cd);}//---------------------获取报文并写入文件---------------------------------intInputCode(){FILE*tobetran;inti=0;if((tobetran=fopen(tobetran.txt,w))==NULL){printf(不能打开文件\n);return0;}printf(请输入你想要编码的字符\n);scanf(%s,&str);fputs(str,tobetran);printf(请输入你相应编码的权值\n);for(i=0;istrlen(str);i++)scanf(%d,&wa[i]);while(wa[i]!='\0'){fprintf(tobetran,%d,wa[i++]);}printf(获取报文成功\n);fclose(tobetran);returnstrlen(str);}//--------------初始化哈夫曼链表---------------------------------voidInitialization(){inta,k,flag,len;a=0;len=InputCode();for(i=0;ilen;i++){k=0;flag=1;第页共页cou[i-a].data=str[i];cou[i-a].count=wa[i];while(ik){if(str[i]==str[k]){a++;flag=0;}k++;if(flag==0)break;}if(flag){for(j=i+1;jlen;j++){if(str[i]==str[j])++cou[i-a].count;}}}n=len-a;for(i=0;in;i++){printf(%c,cou[i].data);printf();printf(%d\n,cou[i].count);}for(i=0;i=n;i++){*(z+i)=cou[i].data;*(w+i)=cou[i].count;}HuffmanCoding(HT,HC,w,8);//------------------------打印编码-------------------------------------------printf(字符对应的编码为\n:);for(i=1;i=n;i++){puts(HC[i]);}//-------------------------将哈夫曼编码写入文件------------------------printf(下面将哈夫曼编码写入文件\n);FILE*htmTree;charr[]={'','\0'};if((htmTree=fopen(htmTree.txt,w))==NULL){printf(cannotopenfile\n);return;}fputs(z,htmTree);for(i=0;in+1;i++){fprintf(htmTree,%6d,*(w+i));fputs(r,htmTree);}for(i=1;i=n;i++){fputs(HC[i],htmTree);fputs(r,htmTree);}fclose(htmTree);printf(已将字符与对应编码写入根目录下文件htmTree.txt中\n);}//---------------------编码函数---------------------------------voidEncoding(){第页共页printf(下面对目录下文件tobetran.txt中的字符进行编码\n);FILE*tobetran,*codefile;if((tobetran=fopen(tobetran.txt,rb))==NULL){printf(不能打开文件\n);}if((codefile=fopen(codefile.txt,wb))==NULL){printf(不能打开文件\n);}char*tran;i=99;tran=(char*)malloc(100*sizeof(char));while(i==99){if(fgets(tran,100,tobetran)==NULL){printf(不能打开文件\n);break;}for(i=0;*(tran+i)!='\0';i++){for(j=0;j=n;j++){if(*(z+j-1)==*(tran+i)){fputs(HC[j],codefile);if(jn){printf(字符错误，无法编码!\n);break;}}}}}printf(编码工作完成,编码写入目录下的codefile.txt中\n);fclose(tobetran);fclose(codefile);free(tran);}//-----------------译码函数---------------------------------voidDecoding(){printf(下面对根目录下文件codefile.txt中的字符进行译码\n);FILE*codef,*txtfile;if((txtfile=fopen(txtfile.txt,w))==NULL){printf(不能打开文件\n);}if((codef=fopen(codefile.txt,r))==NULL){printf(不能打开文件\n);}第页共页char*work,*work2,i2;inti4=0,i,i3;unsignedlonglength=10000;work=(char*)malloc(length*sizeof(char));fgets(work,length,codef);work2=(char*)malloc(length*sizeof(char));i3=2*n-1;for(i=0;*(work+i-1)!='\0';i++){i2=*(work+i);if(HT[i3].lchild==0){*(work2+i4)=*(z+i3-1);i4++;i3=2*n-1;i--;}elseif(i2=='0')i3=HT[i3].lchild;elseif(i2=='1')i3=HT[i3].rchild;}*(work2+i4)='\0';fputs(work2,txtfile);printf(译码完成\n);printf(内容