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

文档介绍：哈夫曼编码算法实现完整版————————————————————————————————作者:————————————————————————————————日期: :树的应用——:利用哈夫曼编码进行通信可以大大提高信道的利用率,缩短信息传输的时间,降低传输成本。根据哈夫曼编码的原理,编写一个程序,在用户输入结点权值的基础上求哈夫曼编码。要求:从键盘输入若干字符及每个字符出现的频率,将字符出现的频率作为结点的权值,建立哈夫曼树,然后对各个字符进行哈夫曼编码,最后打印输出字符及对应的哈夫曼编码。三、程序源代码:#include<>#include<>#include<>#include<>typedefstruct{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].weight<tag1) {tag1=p[x].weight;s1=x;} }for(inty=1;y<=j-1;y++) {if(p[y].parent==0&&y!=s1&&p[y].weight<tag2) {tag2=p[y].weight;s2=y;} } if(s1>s2)//将选出的两个节点中的序号较小的始终赋给s1 {tmp=s1;s1=s2;s2=tmp;}p[s1].parent=j; 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;//("",ios::out);for(i=1;i<=m;i++){outfile<<HT[i].weight<<"\t"<<HT[i].parent<<"\t"<<HT[i].lchild<<"\t"<<HT[i].rchild<<"\t"<<endl;}();cout<<"初始化结果已保存在hfmTree文件中\n";}voidToBeTree()//将正文写入文件ToBeTree中{ ofstreamoutfile; ("",ios::out); outfile<<"THISPROGRAMISMYFAVORITE"; ();}voidEncoding(HuffmanTree&HT,intn)//编码{HuffmanCodeHC;HC=(HuffmanCode)malloc((n+1)*sizeof(char*));char*cd;cd=(char*)malloc(n*sizeof(char));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