haf.zip_haf

#include<iostream> #include<constant.h> #include<string> using namespace std; typedef struct { unsigned int weight; unsigned int parent,lchild,rchild; }HTNode,*HuffmanTree; typedef char * *HuffmanCode; int select(HuffmanTree HT,int n,int &s1,int &s2) { int i,j; s1=s2=0; for(i=1;i<=n;i++) { if(HT[i].parent==0) { s1=s2=i; } if(s1!=0) break; } for(j=i;j<=n;j++) { if(HT[j].parent==0&&HT[j].weight<HT[s1].weight) s1=j; } if(s2!=s1) { for(j=i;j<=n;j++) { if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1) s2=j; } } else { for(i++;i<=n;i++) { if(HT[i].parent==0) { s2=i; } if(s2!=s1) break; } for(j=i;j<=n;j++) { if(HT[j].parent==0&&HT[j].weight<HT[s2].weight&&j!=s1) s2=j; } } return TRUE; } //哈夫曼树的构造算法实现 int weight(int *&w,int n) { w=(int *)malloc((n+1)*sizeof(int)); int i; cout<<"输入权值："<<endl; for(i=1;i<=n;i++) { cin>>w[i]; } return OK; } void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC,int *w,int n) { if(n<=1)return ; HuffmanTree p; int m,i,s1,s2; m=2*n-1;//哈夫曼树结点数 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode)); for(p=HT+1,i=1;i<=n;++i,++p) { (*p).weight=w[i]; (*p).lchild=0; (*p).parent=0; (*p).rchild=0; } for(;i<=m;++i,++p) { (*p).weight=0; (*p).lchild=0; (*p).parent=0; (*p).rchild=0; } for(i=n+1;i<=m;++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*)); char *cd; cd=(char*)malloc(n*sizeof(char)); cd[n-1]='\0'; int start; int c,f; 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'; else cd[--start]='1'; HC[i]=(char*)malloc((n-start)*sizeof(char)); strcpy(HC[i],&cd[start]); } for(i=1;i<=n;i++) { cout<<i<<':'<<'\t'; puts(HC[i]); cout<<endl; } free(cd); } int main() { HuffmanTree HT; int *w; int n; cout<<"输入字符数："<<endl; cin>>n; weight(w,n); HuffmanCode HC; HuffmanCoding(HT,HC,w,n); int a; cin>>a; }