huffman encoding and decoding.txt

哈夫曼编码与译码

#include   <graphics.h>   
  #include   <math.h>   
  #include   <iostream.h>   
  #include   <stdio.h>   
  #include   <fstream.h>   
  #include   <string.h>   
  #include   <stdlib.h>   
  #include   <iomanip.h>   
  #include   <conio.h>   
  typedef   int   bool;   
  #define   false   0;   
  #define   true   1;   
  //----------------------------------   
  //二叉链表结点的C++类   
  static   char   S[255]="";   
  char   *code[255];   
  bool   IsCode=false;   
  bool   IsDecode=false;   
  bool   IsInitial=false;   
  int   n;   
  template<class   T>   class   BTree;   
  template<class   T>   
  class   BTNode   
  {   
  public:   
  BTNode()   {lchild=rchild=0;}   
  BTNode(const   T&   e)   
  {   
  element=e;   
  lchild=rchild=0;   
  }   
  BTNode(const   T&   e,BTNode<T>   *l,BTNode<T>   *r)   
  {   
  element=e;   
  lchild=l;   
  rchild=r;   
  }   
  private:   
  T   element;   
  BTNode<T>   *lchild,*rchild;   
  friend   class   BTree<T>;   
  friend   void   Visit(BTNode<T>   *);   
  friend   void   InVisit(BTNode<int>   *p,char   temp[],char   S[],char   e,char   result[]);   
  friend   char   *   HuffmanEncode(BTree<int>   ht,char   S[],char   e);   
  };   
  //---------------------------------   
  template<class   T>   
  void   Visit(BTNode<T>   *p)   
  {   
  cout<<p->element<<"   ";//   
  }   
  //---------------------------------   
  //二叉树的C++类   
  template<class   T>   
  class   BTree   
  {   
  public:   
  BTree()   {root=NULL;}   
  ~BTree()   {};   
  bool   IsEmpty()const;   
  bool   Root(T&   x)const;   
  void   MakeTree(const   T&   e,BTree<T>&   left,BTree<T>&   right);   
  void   BreakTree(T&   e,BTree<T>&   left,BTree<T>&   right);   
  void   PreOrder(void(*Visit)(BTNode<T>   *u))   
  {PreOrder(Visit,root);}   
  void   InOrder(void(*Visit)(BTNode<T>   *u))   
  {InOrder(Visit,root);}   
  void   PostOrder(void(*Visit)(BTNode<T>   *u))   
  {PostOrder(Visit,root);}   
  BTNode<T>   *GetRoot(){return   root;}   
  void   PrintInOrder(ofstream   &fileout,BTNode<T>   *t);   
  void   PrintPreOrder(ofstream   &fileout,BTNode<T>   *t);   
  void   PrintPostOrder(ofstream   &fileout,BTNode<T>   *t);   
  private:   
  BTNode<T>   *root;   
  void   PreOrder(void(*Visit)(BTNode<T>   *u),BTNode<T>   *t);   
  void   InOrder(void(*Visit)(BTNode<T>   *u),BTNode<T>   *t);   
  void   PostOrder(void(*Visit)(BTNode<T>   *u),BTNode<T>   *t);   
  };   
  //----------------------------------   
  template<class   T>   
  bool   BTree<T>::IsEmpty()const   
  {   
  return   root==NULL;   
  }   
  //----------------------------------   
  template<class   T>   
  bool   BTree<T>::Root(T&   x)const   
  {   
  if(root){   
  x=root->element;   
  return   true;   
  }   
  else   return   false;   
  }   
  //---------------------------------   
  template<class   T>   
  void   BTree<T>::MakeTree(const   T&   e,BTree<T>&   left,BTree<T>&   right)   
  {   
  BTNode<T>   *p;   
  p=new   BTNode<T>(e,left.root,right.root);   
  left.root=right.root=0;   
  root=p;   
  }   
  //----------------------------------   
  template<class   T>   
  void   BTree<T>::BreakTree(T&   e,BTree<T>&   left,BTree<T>&   right)   
  {   
  BTNode<T>   *p;   
  p=root;   
  if(p){   
  e=p->element;   
  left.root=p->lchild;   
  right.root=p->rchild;   
  }   
  }   
  //----------------------------------   
  template<class   T>   
  void   BTree<T>::PreOrder(void(*Visit)(BTNode<T>   *u),BTNode<T>   *t)   
  {   
  if(t){   
  Visit(t);   
  PreOrder(Visit,t->lchild);   
  PreOrder(Visit,t->rchild);   
  }   
  }   
  //----------------------------------   
  template<class   T>   
  void   BTree<T>::InOrder(void(*Visit)(BTNode<T>   *u),BTNode<T>   *t)   
  {   
  if(t){   
  InOrder(Visit,t->lchild);   
  Visit(t);   
  InOrder(Visit,t->rchild);   
  }   
  }   
  //----------------------------------   
  template<class   T>   
  void   BTree<T>::PostOrder(void(*Visit)(BTNode<T>   *u),BTNode<T>   *t)   
  {   
  if(t){   
  PostOrder(Visit,t->lchild);   
  PostOrder(Visit,t->rchild);   
  Visit(t);   
  }   
  }   
    
  //优先权队列的C++类   
  template   <class   T>   
  class   PriorityQueue   
  {   
  public:   
  PriorityQueue(int   MaxQSize=10);   
  ~PriorityQueue(){delete[]q;};   
  void   Insert(const   T   &x);   
  void   Delete(T   &x);   
  bool   IsEmpty()const{   return   CurrentSize==0;}   
  bool   IsFull()const   {return   CurrentSize==MaxSize;}   
  private:   
  void   AdjustDown(int   r,int   n);   
  void   AdjustUp(int   n);   
  T   *q;   
  int   CurrentSize,MaxSize;   
  };   
    
  template   <class   T>   
  PriorityQueue<T>::PriorityQueue(int   MaxQSize)   
  {   
  MaxSize=MaxQSize;   
  q=new   T[MaxSize+1];   
  CurrentSize=0;   
  }   
    
  template   <class   T>   
  void   PriorityQueue<T>::AdjustDown(int   r,int   n)   
  {   
  int   child;   
  T   temp=q[r];   child=2*r;   
  while   (child<=n)   
  {   
  if   (child<n&&q[child]>q[child+1])   child++;   
  if   (temp<=q[child])   break;   
  q[child/2]=q[child];   
  child*=2;   
  }   
  q[child/2]=temp;   
  }   
    
  template   <class   T>   
  void   PriorityQueue<T>::AdjustUp(int   n)   
  {   
  int   i=n;   
  T   temp=q[i];   
  while   (i!=1&&temp<q[i/2])   
  {   
  q[i]=q[i/2];   
  i/=2;   
  }   
  q[i]=temp;   
  }   
    
  template   <class   T>   
  void   PriorityQueue<T>::Insert(const   T&x)   
  {   
  if   (CurrentSize==MaxSize)   
  {   
  cerr<<"OverFlow"<<endl;   
  exit(1);   
  }   
  q[++CurrentSize]=x;   
  AdjustUp(CurrentSize);   
  }   
    
  template   <class   T>   
  void   PriorityQueue<T>::Delete(T&x)   
  {   
  if   (CurrentSize==MaxSize)   
  {   
  cerr<<"UnderFlow"<<endl;   
  exit(1);   
  }   
  x=q[1];   
  q[1]=q[CurrentSize--];   
  AdjustDown(1,CurrentSize);   
  }   
    
  //Huffman类和建立哈夫曼树的算法   
  template   <class   T>   
  class   Huffman   
  {   
  public:   
  operator   T()const   {return   weight;}   
  private:   
  BTree<int>   tree;   
  T   weight;   
  friend   BTree<int>   HuffmanTree(T   a[],int   n);   
  };   

template   <class   T>   
  BTree<int>   HuffmanTree(T   a[],int   n)   
  {   
  Huffman<T>   *w=new   Huffman<T>[n+1];   
  BTree<int>   z,zero;   
  for   (int   i=1;i<=n;i++)   
  {   
  z.MakeTree(i,zero,zero);   
  w[i].weight=a[i];   w[i].tree=z;   
  }   
  PriorityQueue<   Huffman<T>   >   pq(n+1);   
  for   (i=1;i<=n;i++)   pq.Insert(w[i]);   
  Huffman<T>   x,y;   
  for   (i=1;i<n;i++)   
  {   
  pq.Delete(x);   
  pq.Delete(y);   
  z.MakeTree(0,x.tree,y.tree);   
  x.weight+=y.weight;   
  x.tree=z;   
  pq.Insert(x);   
  }   
  pq.Delete(x);   
  delete[]w;   
  return   x.tree;   
  }   
    
  template   <class   T>   
  char   *   HuffmanEncode(BTree<int>   ht,T   S[],T   e)   
  {   
  static   char   temp[128]="";   
  static   char   result[128]="";   
  strcpy(result,"");   
  BTNode<int>*   p=ht.GetRoot();   
  InVisit(p,temp,S,e,result);   
  return   (char   *)result;   
  }   
    
  template   <class   T>   
  void   InVisit(BTNode<int>*   p,char   temp[],T   S[],T   e,char   result[])   
  {   
  if   (p)   
  {   
  if   (p->lchild==NULL&&p->rchild==NULL&&S[p->element-1]==e)   strncpy(result,temp,127);   
  else   
  if   (strcmp(result,"")==0)   
  {   
  strcat(temp,"0");   
  InVisit(p->lchild,temp,S,e,result);   
  temp[strlen(temp)-1]='\0';   
  strcat(temp,"1");   
  InVisit(p->rchild,temp,S,e,result);   
  temp[strlen(temp)-1]='\0';   
  }   
  }