哈夫曼树编码译码 数据结构

# include <stdio.h> # include <string.h> # include <iostream.h> # define N 100 //哈夫曼树叶子结点数 # define M 2*N-1 //树中结点数 typedef struct { char data; double weight; int parent; int lchild; int rchild; }HTNode; typedef struct { char cd[N]; //存放哈夫曼码,N值为最大码长,可在定义宏中更改 int start; }HCode; void CreateHT(HTNode ht[],int n) //构造哈夫曼树 { int i,k,lnode,rnode; double min1,min2; for(i=0;i<2*n-1;i++) ht[i].parent=ht[i].lchild=ht[i].rchild=-1; for(i=n;i<2*n-1;i++) { min1=min2=1.0; lnode=rnode=-1; //lnode和rnode为最小权重的两个结点位置 for(k=0;k<i;k++) //在还没构造二叉树的结点中查找 if(ht[k].parent==-1) { if(ht[k].weight<min1) { min2=min1; rnode=lnode; min1=ht[k].weight; lnode=k; } else if(ht[k].weight<min2) { min2=ht[k].weight; rnode=k; } } ht[lnode].parent=i; ht[rnode].parent=i; ht[i].weight=ht[lnode].weight+ht[rnode].weight; ht[i].lchild=lnode; ht[i].rchild=rnode; } } void CreateHCode(HTNode ht[],HCode hcd[],int n) //构造哈夫曼编码 { int i,f,c; HCode hc; for(i=0;i<n;i++) { hc.start=n;c=i; f=ht[i].parent; while(f!=-1) { if(ht[f].lchild==c) //处理左孩子 hc.cd[hc.start--]='1'; else //处理右孩子 hc.cd[hc.start--]='0'; c=f;f=ht[f].parent; } hc.start++; hcd[i]=hc; } } void TransHCode(HTNode ht[],HCode hcd[], char c[],int n,int o) //译码 { int m=2*n-1; int i,j=0,k;//初始化输入码,可更改,为'0,'1'级组合 j=0; //重置为0 printf("\t译码结果为 : "); while(c[j]!='\0'&&j<o) { i=m-1; while(ht[i].lchild!=-1&&ht[i].rchild!=-1) { if(c[j]=='0') i=ht[i].rchild; else if(c[j]=='1') i=ht[i].lchild; j++; } printf("%c",ht[i].data); } printf("\n"); } void DispHCode(HTNode ht[],HCode hcd[],int n) //编码输出 { int i,j,k; printf("\t源码\t频率\t编码\n"); for(i=0;i<n;i++) { j=0; printf("\t%c\t%.0f\t",ht[i].data,ht[i].weight*1000); for(k=hcd[i].start;k<=n;k++) { printf("%c",hcd[i].cd[k]); j++; } printf("\n"); } } double hedui(char a) { int i; char pp[27]={'A','B','C','D','E','F','G','H','I','J','K','L','M','N','O','P','Q','R','S','T','U','V','W','X','Y','Z',' '}; double qq[27]={0.064,0.013,0.022,0.032,0.103,0.021,0.015,0.047,0.057,0.001,0.005,0.032,0.020,0.057,0.063,0.015,0.001,0.048,0.051,0.080,0.023,0.008,0.018,0.001,0.016,0.001,0.002}; for(i=0;i<27;i++) if(a==pp[i]) return qq[i]; } void main() { int n,i=0,m,j,k; char ch[100],aw[100],cc[100]; printf("请输入源码："); gets(ch); m=strlen(ch); n=m; //printf("%d\n",m); double fnum[100]; //权值(信源概率分布) HTNode ht[M]; HCode hcd[N]; for(i=0;i<n;i++) { ht[i].data=ch[i]; fnum[i]=hedui(ch[i]); //printf("%f\n",fnum[i]); ht[i].weight=fnum[i]; } CreateHT(ht,n); //调用函数构造哈夫曼树 CreateHCode(ht,hcd,n); //调用函数构造哈夫曼编码 DispHCode(ht,hcd,n);//调用函数输出哈夫曼编码 j=0; for(i=0;i<n;i++) { for(k=hcd[i].start;k<=n;k++) { aw[j]=hcd[i].cd[k]; j++; } } TransHCode(ht,hcd,aw,n,j);//调用函数译码 }