数据结构-哈弗曼树-C++

#include<iostream.h> const int MaxValue=1000; class HaffNode { public: int weight; int flag; int parent; int leftChild; int rightChild; char ch; }; class Code { public: int bit[MaxValue]; int start; int weight; }; void Haffman(int weight[],int n,HaffNode haffTree[],char ch[])//建立叶结点个数为n权值为weight的哈夫曼树 { int i,j,m1,m2,x1=0,x2=0; for( i=0;i<2*n-1;i++)//哈夫曼树的初始化。n个结点的哈夫曼树共有2n-1个结点 { if(i<n)haffTree[i].weight=weight[i]; else haffTree[i].weight=0; haffTree[i].ch=ch[i]; haffTree[i].parent=0; haffTree[i].flag=0; haffTree[i].leftChild=-1; haffTree[i].rightChild=-1; } for(i=0;i<n-1;i++)//构造哈夫曼树的n-1个非叶结点 { m1=m2=MaxValue; for(j=0;j<n+i;j++) { if(haffTree[j].weight<m1 && haffTree[j].flag==0) { m2=m1; x2=x1; m1=haffTree[j].weight; x1=j; } else if(haffTree[j].weight<m2 && haffTree[j].flag==0) { m2=haffTree[j].weight; x2=j; } } haffTree[x1].parent=n+i; haffTree[x2].parent=n+i; haffTree[x1].flag=1; haffTree[x2].flag=1; haffTree[n+i].weight=haffTree[x1].weight+haffTree[x2].weight; haffTree[n+i].leftChild=x1; haffTree[n+i].rightChild=x2; } } void HaffmanCode(HaffNode haffTree[],int n,Code haffCode[]) { Code* cd=new Code; int child,parent; for(int i=0;i<n;i++) { cd->start=n-1; cd->weight=haffTree[i].weight; child=i; parent=haffTree[child].parent; while(parent!=0) { if(haffTree[parent].leftChild==child) cd->bit[cd->start]=0; if(haffTree[parent].rightChild==child) cd->bit[cd->start]=1; cd->start--; child=parent; parent=haffTree[child].parent; } for(int j=cd->start+1;j<n;j++) haffCode[i].bit[j]=cd->bit[j]; haffCode[i].start=cd->start; haffCode[i].weight=cd->weight; } } int main() { int i,j,n=27; char cn; int weight[]={64,13,22,32,103,21,15,47,57,1,5,32,20,57,63,15,1,48,51,80,23,8,18,1,16,1,168}; char ch[]={'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','@'}; HaffNode* h=new HaffNode[2*n-1]; Code* c=new Code[n]; Haffman(weight,n,h,ch); HaffmanCode(h,n,c); for(i=0;i<n;i++) { cout<<"weight="<<h[i].weight<<" "; cout<<endl; cout<<"ch="<<h[i].ch<<" "; cout<<endl; for(j=c[i].start+1;j<n;j++) cout<<c[i].bit[j]; cout<<endl; } cout<<"请输入:"; for(int t=0;;t++) { cin>>cn; switch(cn) { case 'A': for(j=c[0].start+1;j<n;j++) cout<<c[0].bit[j]; cout<<endl; break; case'B': for(j=c[1].start+1;j<n;j++) cout<<c[1].bit[j]; cout<<endl; break; case 'C': for(j=c[2].start+1;j<n;j++) cout<<c[2].bit[j]; cout<<endl; break; case 'D': for(j=c[3].start+1;j<n;j++) cout<<c[3].bit[j]; cout<<endl; break; case 'E': for(j=c[4].start+1;j<n;j++) cout<<c[4].bit[j]; cout<<endl; break; case 'F': for(j=c[5].start+1;j<n;j++) cout<<c[5].bit[j]; cout<<endl; break; case 'G': for(j=c[6].start+1;j<n;j++) cout<<c[6].bit[j]; cout<<endl; break; case 'H': for(j=c[7].start+1;j<n;j++) cout<<c[7].bit[j]; cout<<endl; break; case 'I': for(j=c[8].start+1;j<n;j++) cout<<c[8].bit[j]; cout<<endl; break; case 'J': for(j=c[9].start+1;j<n;j++) cout<<c[9].bit[j]; cout<<endl; break; case 'K': for(j=c[10].start+1;j<n;j++) cout<<c[10].bit[j]; cout<<endl; break; case 'L': for(j=c[11].start+1;j<n;j++) cout<<c[11].bit[j]; cout<<endl; break; case 'M': for(j=c[12].start+1;j<n;j++) cout<<c[12].bit[j]; cout<<endl; break; case 'N': for(j=c[13].start+1;j<n;j++) cout<<c[13].bit[j]; cout<<endl; break; case 'O': for(j=c[14].start+1;j<n;j++) cout<<c[14].bit[j]; cout<<endl; break; case 'P': for(j=c[15].start+1;j<n;j++) cout<<c[15].bit[j]; cout<<endl; break; case 'Q': for(j=c[16].start+1;j<n;j++) cout<<c[16].bit[j]; cout<<endl; break; case 'R': for(j=c[17].start+1;j<n;j++) cout<<c[17].bit[j]; cout<<endl; break; case 'S': for(j=c[18].start+1;j<n;j++) cout<<c[18].bit[j]; cout<<endl; break; case 'T': for(j=c[19].start+1;j<n;j++) cout<<c[19].bit[j]; cout<<endl; break; case 'U': for(j=c[20].start+1;j<n;j++) cout<<c[20].bit[j]; cout<<endl; break; case 'V': for(j=c[21].start+1;j<n;j++) cout<<c[21].bit[j]; cout<<endl; break; case 'W': for(j=c[22].start+1;j<n;j++) cout<<c[22].bit[j]; cout<<endl; break; case 'X': for(j=c[23].start+1;j<n;j++) cout<<c[23].bit[j]; cout<<endl; break; case 'Y': for(j=c[24].start+1;j<n;j++) cout<<c[24].bit[j]; cout<<endl; break; case 'Z': for(j=c[25].start+1;j<n;j++) cout<<c[25].bit[j]; cout<<endl; break; case '@': for(j=c[26].start+1;j<n;j++) cout<<c[26].bit[j]; cout<<endl; break; } } }