数据结构哈夫曼编码问题，请高手帮忙

Question

假定用于通信的电文由8个字母A，B，C，D，E，F，G，H组成，各字母在电文中出现的概率为5％，25％，4％，7％，9％，12％，30％，8％，试为这8个字线设计哈夫曼编码

Answer 1

用c编的程序如下

#include <iostream.h>

#define MAX 21

typedef struct

{

 char data;    //节点值

 int weight;   //权重

 int parent;   //父节点

 int left;

 int right;

} huffnode;

typedef struct

{

 char cd[MAX];

 int start;

}huffcode;

void main()

{

 huffnode ht[2*MAX];

 huffcode hcd[MAX],d;

 int i,k,f,l,r,n,c,m1,m2;

 cout<<"元素个素：";

 cin>>n;

 for (i=1;i<=n;i++)

 {

  cout<<"第"<<i<<"个元素=>\t节点值：";

  cin>>ht[i].data;

  cout<<"\t\t权  重：";

  cin>>ht[i].weight;

 }

 for (i=1;i<=2*n-1;i++)

  ht[i].parent=ht[i].left=ht[i].right=0;

 for (i=n+1;i<=2*n-1;i++)   //构造HUFFMAN树

 {

  m1=m2=32767;     //l和r为最小权重的两个节点位置

  l=r=0;

  for(k=1;k<=i-1;k++)

   if(ht[k].parent==0)

    if(ht[k].weight<m1)

    {m2=m1;

    r=l;

    m1=ht[k].weight;

    l=k;

    }

    else if(ht[k].weight<m2)

    {

     m2=ht[k].weight;

     r=k;

    }

    ht[l].parent=i;

    ht[r].parent=i;

    ht[i].weight=ht[l].weight+ht[r].weight;

    ht[i].left=l;

    ht[i].right=r;

    }

 for (i=1;i<=n;i++)  //根据huffman树求huffman编码

 {

  d.start=n+1;

  c=i;

  f=ht[i].parent;

  while (f!=0)

  {

   if(ht[f].left==c)

    d.cd[--d.start]='0';

   else

    d.cd[--d.start]='1';

   c=f;

   f=ht[f].parent;

  }

  hcd[i]=d;

 }

 cout<<"输出huffman编码:\n";

 for(i=1;i<n;i++)

 {

  cout<<" "<<ht[i].data<<":";

  for (k=hcd[i].start;k<=n;k++)

   cout<<hcd[i].cd[k];

  cout<<endl;

 }

}

运行结果见图片