huffman编码（方法2）.cpp

分别写出了两种Huffman编码的实现过程

  #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插入表头   
  }   
  }