杨祖芳huffman.cpp

huffman编码源程序之二

/*   
  HuffmanCode   BY   Visual   C++   6.0     
  Filename:   Huffman.c   
 
     
  */   

#include<iostream.h>   
    
  struct   elem{   
  char   name;   
  float   weight;   
  int   *code;   
  };   
    
  struct   node{   
  node*   leftson;   
  node*   rightson;   
  float   weight;   
  elem   elementary;   
  };   
    
    
  class   Huffman   
  {   
  public:   
  Huffman();   
  ~Huffman();   
  private://viarables   
  int   M;   
  elem   *nodes;   
  node   *tree;   
  int   index;   
  int   *code;   
  int   flag;   
  private://functions   
  void   MakeupTree();   
  void   coding(int,node*);   
  public://functions   
  void   doCode();//coding：编码   
  elem*   deCode(int*);//decode：译码   
    
  };   
    
    
  void   main()   
  {   
  Huffman   huffman;   
  huffman.doCode();   
    
  }   
    
  //fuctions   of   class   Huffman   
  Huffman::Huffman()   
  {   
  char   name;   
  int   i=0;   
  cout<<endl<<"Please   input   the   number   of   codes(if   M<=0   to   use   defualt):";   
  cin>>M;   
  if(M>0)   
  {   
  index=2*M-2;   
  tree=new   node[2*M-1];   
  code=new   int[2*M];   
  nodes=new   elem[M];   
  for(i=0;i<M;i++)   
  {   
  cout<<endl<<"Please   input   name:";   
  cin>>nodes[i].name;   
  cout<<"Please   input   weight:";   
  cin>>nodes[i].weight;   
  }   
  }   
  else   
  {   
  M=5;   
  index=2*M-2;   
  tree=new   node[2*M-1];   
  code=new   int[2*M];   
  nodes=new   elem[M];   
  nodes[0].name='a';   
  nodes[0].weight=2;   
  nodes[1].name='b';   
  nodes[1].weight=54;   
  nodes[2].name='c';   
  nodes[2].weight=16;   
  nodes[3].name='d';   
  nodes[3].weight=9;   
  nodes[4].name='e';   
  nodes[4].weight=34;   
  }   
  //initialize   nodes[i].codes   
  for(i=0;i<M;i++)   
  {   
  nodes[i].code=new   int[2*M];   
  }   
  //initialize   code     
  for   (i=0;i<2*M;i++)   
  code[i]=-1;   
  //sort   
  for(i=0;i<M-1;i++)   
  {   
  for(int   j=i+1;j<M;j++)   
  {   
  if(nodes[j-1].weight>nodes[j].weight)   
  {   
  nodes[j-1].weight=nodes[j-1].weight+nodes[j].weight;   
  nodes[j].weight=nodes[j-1].weight-nodes[j].weight;   
  nodes[j-1].weight=nodes[j-1].weight-nodes[j].weight;   
  name=nodes[j-1].name;   
  nodes[j-1].name=nodes[j].name;   
  nodes[j].name=name;   
  }   
  }   
  }   
  for(i=0;i<M;i++)   
  {   
  tree[i].elementary=nodes[i];   
  tree[i].weight=nodes[i].weight;   
  tree[i].leftson=NULL;   
  tree[i].rightson=NULL;   
  }   
    
  }   
    
  Huffman::~Huffman()   
  {   
  //free   the   recource     
  delete   []tree;   
  delete   []code;   
  for(int   i=0;i<M;i++)   
  {   
  delete   []nodes[i].code;   
  }   
  delete   []nodes;   
  }   
    
  void   Huffman::MakeupTree()   
  {   
  node   node0,node1,node2;   
    
  if(index==2*M-2)flag=M;   
  if(index>0)   
  {   
  node0.weight=tree[0].weight+tree[1].weight;   
  node1=tree[0];   
  node2=tree[1];   
  tree[index]=node1;   
  node0.leftson=&tree[index--];   
  tree[index]=node2;   
  node0.rightson=&tree[index--];   
  for(int   i=0;i<flag-2;i++)   
  {   
  tree[i]=tree[i+2];   
  }   
  flag--;   
  for(i=0;i<flag-1;i++)   
  {   
  if(node0.weight<tree[i].weight)   
  break;   
  }   
  for(int   j=flag-1;i<j;j--)   
  {   
  tree[j]=tree[j-1];   
  }   
  tree[i]=node0;   
  MakeupTree();   
  }   
  return;   
  }   
    
  void   Huffman::coding(int   sign,node   *head)   
  {   
  if(head!=NULL)   
  {   
  code[sign]=0;   
  coding(sign+1,head->leftson);   
  code[sign]=1;   
  coding(sign+1,head->rightson);   
  }   
  else   
  {   
    
  return;   
  }   
  if(head->rightson==NULL)   
  {   
  for(int   i=0;i<=sign;i++)   
  head->elementary.code[i]=code[i];   
  head->elementary.code[sign]=-1;   
  code[sign]=-1;   
  for(int   j=0;head->elementary.name!=nodes[j].name;j++);   
  for(i=0;code[i]>=0;i++)   
  {   
  nodes[j].code[i]=code[i];   
  }   
  nodes[j].code[i]=-1;   
  //cout   
  cout<<endl<<head->elementary.name<<":";   
  //cout   
  for(i=0;head->elementary.code[i]!=-1;i++)   
  cout<<head->elementary.code[i];  
  cout<<"\n";
  return;   
  }   
  }   
    
  void   Huffman::doCode()   
  {   
  MakeupTree();   
  coding(0,&tree[0]);   
  }   
    
  elem*   Huffman::deCode(int*matchingCode)//the   end   of   matchingCode   is   integer   -1     
  {   
  bool   judge=false;   
  for(int   i=0;i<M&&judge==false;i++)   
  {   
  for(int   j=0;matchingCode[j]==nodes[i].code[j]&&matchingCode[j]>=0;j++);   
  if(matchingCode<0)judge=true;   
  }   
  if(judge)return   &nodes[i];   
  else   return   NULL;   
  }