#include<iostream.h>   
  #include<stdlib.h>   
  #define   MAX   21   
    
  struct   Huffnode//Huffman結構定義   
  {   
  char   data;   
  double   weight;   
  Huffnode   *parent;   
  Huffnode   *left;   
  Huffnode   *right;   
  Huffnode   *next;   
  };   
    
  struct   Huffcode//Huffman編碼結構   
  {   
  char   cd[MAX];   
  int   start;   
  };   
    
  void   Select(Huffnode*,Huffnode   *&,Huffnode   *&);   //選取最小的兩個節點的地址,用兩個引用值返回   
  void   Merge(Huffnode*,Huffnode*,Huffnode*);            //合并,建樹   
    
  void   main()   
  {   
  int   n;   
  Huffnode   *LinkList=new   Huffnode;     
  Huffnode   *pGuard=LinkList;   
  Huffnode   *pS;   
    
  cout<<"請您輸入元素的個數:"<<endl;   
  cin>>n;   
    
  Huffnode   **Record=new   Huffnode*[n+1];   
    
  for(int   i=1;i<=n;i++)   
  {   
  if((pS=new   Huffnode)==NULL)   
  {   
  cout<<"無法分配更多的內存了!"<<endl;   
  exit(1);   
  }   
    
  pS->next=NULL;   
  pS->parent=NULL;   
  pS->left=NULL;   
  pS->right=NULL;   
  cout<<"請輸入第"<<i<<"個字符:"<<endl;   
  cin>>pS->data;   
  cout<<"它的概率為:"<<endl;   
  cin>>pS->weight;   
  Record[i]=pS;   
  pGuard->next=pS;   
  pGuard=pGuard->next;   
  }   
  //////////////////////生成Huffman樹   
  Huffnode   *S1,*S2;   
    
  for(int   icount=1;icount<n;icount++)   
  {   
  Select(LinkList,S1,S2);   
  Merge(LinkList,S1,S2);   
  }   
    
  /////////////////////   
    
  Huffnode   *c,*f;   
  Huffcode   hcd[MAX],d;   
    
  for(int   j=1;j<=n;j++)   
  {   
  d.start=n+1;   
  d.cd[d.start+1]=NULL;   
  c=Record[j];   
  f=Record[j]->parent;   
  while(f!=NULL)   
  {   
  if(f->left==c)   
  d.cd[--d.start]='0';   
  else   
  d.cd[--d.start]='1';   
  c=f;   
  f=f->parent;   
  }   
  hcd[j]=d;   
  }   
  system("cls");   
  for(int   k=1;k<=n;k++)   
  {   
  cout<<Record[k]->data<<"的Huffman編碼是:";   
  for(int   l=hcd[k].start;hcd[k].cd[l+1]!=NULL;l++)   
  cout<<hcd[k].cd[l]<<"   ";   
  cout<<endl;   
  }   
  system("pause");   
  }   
    
  void   Select(Huffnode*   LinkList,Huffnode   *&S1,Huffnode   *&S2)   
  {   
  Huffnode   *pGuard;   
  S1=S2=LinkList->next;   
    
  for(pGuard=S1->next;pGuard!=NULL;pGuard=pGuard->next)   
  {   
  if(pGuard->weight<S1->weight)   
  S1=pGuard;   
  }   
    
  if(S1==S2)   
  S2=S2->next;   
    
  for(pGuard=S2->next;pGuard!=NULL;pGuard=pGuard->next)   
  {   
  if(pGuard==S1)   
  continue;   
    
  if(pGuard->weight<S2->weight)   
  S2=pGuard;   
  }   
  }   
    
  void   Merge(Huffnode   *LinkList,Huffnode   *S1,Huffnode   *S2)   
  {   
  Huffnode   *pGuard;   
    
  for(pGuard=LinkList;pGuard->next!=S1;pGuard=pGuard->next)   
  ;                                                                               //找到S1前驅   
  pGuard->next=S1->next;   
  S1->next=NULL;   
    
  for(pGuard=LinkList;pGuard->next!=S2;pGuard=pGuard->next)   
  ;                                                                               //找到S2前驅   
  pGuard->next=S2->next;   
  S2->next=NULL;   
    
  ///////////////////////上面的語句把S1,S2抽出   
  pGuard=new   Huffnode;   
  pGuard->parent=NULL;               
    
  pGuard->left=S1;   
  pGuard->right=S2;   
  S1->parent=pGuard;   
  S2->parent=pGuard;   
  pGuard->weight=S1->weight+S2->weight;   
    
  if(LinkList->next==NULL)                         //表中最后一次合并   
  {   
  LinkList->next=pGuard;   
  pGuard->next=NULL;   
  }   
  else   
  {   
  pGuard->next=LinkList->next;   
  LinkList->next=pGuard;                           //將pGuard插入表頭   
  }   
  }