哈夫曼编码算法实现完整版

第-1-页共7页实验三树的应用一.实验题目：树的应用——哈夫曼编码二.实验内容：利用哈夫曼编码进行通信可以大大提高信道的利用率，缩短信息传输的时间，降低传输成本。根据哈夫曼编码的原理，编写一个程序，在用户输入结点权值的基础上求哈夫曼编码。要求：从键盘输入若干字符及每个字符出现的频率，将字符出现的频率作为结点的权值，建立哈夫曼树，然后对各个字符进行哈夫曼编码，最后打印输出字符及对应的哈夫曼编码。三、程序源代码:#includeiostream.h#includefstream.h#includestring.h#includestdlib.htypedefstruct{chardata;intweight;intparent,lchild,rchild;}HTNode,*HuffmanTree;typedefchar**HuffmanCode;voidSelect(HuffmanTree&HT,intn,intm){HuffmanTreep=HT;inttmp;for(intj=n+1;j=m;j++){inttag1,tag2,s1,s2;tag1=tag2=32767;for(intx=1;x=j-1;x++){if(p[x].parent==0&&p[x].weighttag1){tag1=p[x].weight;s1=x;}}for(inty=1;y=j-1;y++){if(p[y].parent==0&&y!=s1&&p[y].weighttag2){tag2=p[y].weight;s2=y;}}if(s1s2)//将选出的两个节点中的序号较小的始终赋给s1{tmp=s1;s1=s2;s2=tmp;}p[s1].parent=j;第-2-页共7页p[s2].parent=j;p[j].lchild=s1;p[j].rchild=s2;p[j].weight=p[s1].weight+p[s2].weight;}}voidHuffmanCoding(HuffmanTree&HT,intn,char*w1,int*w2){intm=2*n-1;if(n=1)return;HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode));HuffmanTreep=HT;for(inti=1;i=n;i++){p[i].data=w1[i-1];p[i].weight=w2[i];p[i].parent=p[i].lchild=p[i].rchild=0;}for(;i=m;i++){p[i].weight=p[i].parent=p[i].lchild=p[i].rchild=0;}Select(HT,n,m);ofstreamoutfile;//生成hfmTree文件outfile.open(hfmTree.txt,ios::out);for(i=1;i=m;i++){outfileHT[i].weight\tHT[i].parent\tHT[i].lchild\tHT[i].rchild\tendl;}outfile.close();cout初始化结果已保存在hfmTree文件中\n;}voidToBeTree()//将正文写入文件ToBeTree中{ofstreamoutfile;outfile.open(ToBeTree.txt,ios::out);outfileTHISPROGRAMISMYFAVORITE;outfile.close();}voidEncoding(HuffmanTree&HT,intn)//编码{HuffmanCodeHC;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));char*cd;cd=(char*)malloc(n*sizeof(char));第-3-页共7页cd[n-1]='\0';for(intk=1;k=n;k++){intstart=n-1;for(intc=k,f=HT[k].parent;f!=0;c=f,f=HT[f].parent){if(HT[f].lchild==c)cd[--start]='0';elsecd[--start]='1';}HC[k]=(char*)malloc((n-start)*sizeof(char));strcpy(HC[k],&cd[start]);}cout输出哈夫曼编码:endl;for(inth=1;h=n;h++)//输出编码{coutHT[h].data:;coutHC[h];cout;if(h%8==0)coutendl;}coutendl输出正文编码:endl;ToBeTree();//读取TOBETREE文件里的正文，并进行编码fstreaminfile;infile.open(ToBeTree.txt,ios::in);chars[80];while(!infile.eof()){infile.getline(s,sizeof(s));}infile.close();fstreamoutfile;outfile.open(CodeFile.txt,ios::out);intcount=0;for(h=0;s[h]!='\0';h++){for(k=1;k=n;k++)if(s[h]==HT[k].data){coutHC[k];cout;count++;outfileHC[k];break;}if(count%9==0)coutendl;//每输出7个换行}outfile.close();cout\n编码结果已保存在文件CodeFile中.;第-4-页共7页coutendl;}voidDecoding(HuffmanTree&HT,intn)//译码{intf=2*n-1;fstreaminfile;infile.open(CodeFile.txt,ios::in);chars[1000];while(!infile.eof()){infile.getline(s,sizeof(s));}infile.close();inti=0;intj=0;fstreamoutfile;outfile.open(TextFile.txt,ios::out);while(s[i]!='\0'){f=2*n-1;while(HT[f].lchild!=0)//以f对应的节点的左孩子的值==0作为结束{if(s[j]=='0')f=HT[f].lchild;elsef=HT[f].rchild;j++;}i=j;coutHT[f].data;outfileHT[f].data;}outfile.close();cout\n译码结果已保存在文件TextFile中.;coutendl;}voidPrint()//印代码文件{intcount=0;fstreaminfile;infile.open(CodeFile.txt,ios::in);chars[1000];while(!infile.eof()){infile.getline(s,sizeof(s));for(inti=0;s[i]!='\0';i++){couts[i];count++;if(count%50==0)coutendl;//在终端上每行显示50个代码第-5-页共7页}}infile.close();coutendl;}charmenu()//菜单函数{cout功能菜单如下:endl;cout*********************endl;coutI:初始化(Initialization)endl;coutE:编码(Encoding)endl;coutD:译码(Decoding)endl;coutP:印代码文件(Print)endl;coutQ:退出(Exit)endl;cout*********************endl;cout请输入功能字符:;charch;cinch;returnch;}voidmain(){intn;intArray[100];charcArray[100];HuffmanTreeHT;cout输入n个字符:;cin.getline(cArray,100);n=strlen(cArray);cout一共n个字符.\n;cout依次输入各个字符的权值:endl;for(inti=1;i=n;i++)cinArray[i];inttag;charx=menu();while(1){switch(x){case'I':HuffmanCoding(HT,n,cArray,Array);break;case'E':Encoding(HT,n);break;case'D':Decoding(HT,n);break;case'P':Print();break;case'Q':tag=0;cout结束endl;break;default:cout你输入错误!endl;第-6-页共7页}if(tag==0)break;couty(继续)orn(退出)endl;charch;cinch;if(ch=='y'){cout请输入功能字符:;charc;cinc;x=c;}elseexit(1);}}测试数据：用下表给出的字符集和频度的实际统计数据建立哈夫曼树，并实现以下报文的译码和编码:THISPROGRAMISMYFAVORITE.字符空格ABCDEFGHIJKLM频度1866413223210321154757153220字符NOPQRSTUVWXYZ频度5763151485180238181161四.测试结果：如图一所示五.实验体会通过本次实验，尤其在自己对程序的调试过程中，感觉对树的存储结构，终结状态，还有编码，译码的过程都有了比较清晰的认识。在做本次实验时，其他的都没什么问题，以前很少进行文件操作，刚开始有点手生，但是在实验作完后，文件操作已经用的比较熟练了。最近几次实验，感到自己对本题实验的运行机理和过程掌握的最为透彻。收获不小。在实验过程中，遇到的一个主要问题是在C++里面输入单个空格字符的问题。最终通过用cin.getline（）来解决，但是还不是很理想。为了察看方便，把有些文件的内容直接显示在终端上了,没有列出生成的文件里的结果。第-7-页共7页图一第-8-页共7页