huffman encoding and decoding.txt

哈夫曼编码与译码

  }   
    
  template   <class   T>   
  void   BTree<T>::PrintInOrder(ofstream&   fileout,BTNode<T>   *t)   
  {   
  if   (t)   
  {   
  PrintInOrder(fileout,t->lchild);   
  fileout<<t->element<<"   ";   
  PrintInOrder(fileout,t->rchild);   
  }   
  }   
  template   <class   T>   
  void   BTree<T>::PrintPreOrder(ofstream&   fileout,BTNode<T>   *t)   
  {   
  if   (t)   
  {   
  fileout<<t->element<<"   ";   
  PrintInOrder(fileout,t->lchild);   
  PrintInOrder(fileout,t->rchild);   
  }   
  }   
  template   <class   T>   
  void   BTree<T>::PrintPostOrder(ofstream&   fileout,BTNode<T>   *t)   
  {   
  if   (t)   
  {   
  PrintInOrder(fileout,t->lchild);   
  PrintInOrder(fileout,t->rchild);   
  fileout<<t->element<<"   ";   
  }   
  }   
  void   PrintInterface()   
  {   
  cout<<"\n\t\t\t哈夫曼编码和译码系统\n\n"<<endl; cout<<"\t\t\t\t\t\xc9\xe8\xbc\xc6\xd5\xdf\x3a\xcb\xd5\xce\xb0\xbd\xdc\x20\x45\x34\x20\x42\x30\x30\x30\x34\x30\x31\x31\x38"<<endl;   
  cout<<"\n\t\tI:初始化"<<endl;   
  cout<<"\n\t\tU:根据输入字符串初始化"<<endl;   
  cout<<"\n\t\tC:编码"<<endl;   
  cout<<"\n\t\tD:译码"<<endl;   
  cout<<"\n\t\tP:打印"<<endl;   
  cout<<"\n\t\tT:以树形或凹入表形式打印哈夫曼树"<<endl;   
  cout<<"\n\t\tE:退出"<<endl;   
  cout<<"\n\t\t请选择菜单:";   
  }   
  BTree<int>   hft;   
    
  int   match(char   x)   
  {   
  for   (int   i=0;i<n;i++)   
  if   (x==S[i])   return   i;//如果x在字符集中则返回其下标   
  return   -1;   
  }   
  void   encode()   
  {   
  for   (int   i=0;i<n;i++)   
  {   
  char   *codes=new   char[255];   
  strcpy(codes,HuffmanEncode(hft,S,S[i]));   
  code[i]=new   char[sizeof(codes)];   
  strcpy(code[i],codes);   
  }   
  }   
    
  void   InitiateEx()   
  {   
  n=0;strset(S,'\0');   
  ofstream   fileout("hfmtree");   
  if   (!fileout)   {cout<<"不能创建文件!"<<endl;getch();exit(1);}   
  cout<<"请输入字符串:";   
  int   f[255];f[0]=0;   
  char   str[300]="";   
  gets(str);   
  int   len=strlen(str);   
  for   (int   i=0;i<len;i++)   
  {   
  int   where=match(str[i]);   
  if   (where<0)   
  {   
  S[n++]=str[i];   
  f[n]=1;   
  }else   f[where+1]++;   
  }   
  cout<<"不同的字符为:\n";   
  for   (i=0;i<n;i++)   
  cout<<S[i];   
  cout<<endl;   
  cout<<"相应的频度为:\n";   
  for   (i=1;i<=n;i++)   
  cout<<f[i];   
  cout<<endl;   
    
  hft=HuffmanTree(f,n);   
  fileout<<"中序遍历:";hft.PrintInOrder(fileout,hft.GetRoot());fileout<<'\n';   
  fileout<<"前序遍历:";hft.PrintPreOrder(fileout,hft.GetRoot());fileout<<'\n';   
  fileout<<"后序遍历:";hft.PrintPostOrder(fileout,hft.GetRoot());fileout<<'\n';   
  fileout.close();   
  encode();   
  cout<<"初始化完成!"<<endl;   
  getch();   
  IsInitial=true;   
  IsCode=false;   
  IsDecode=false;   
  }   
  void   Initiate()   
  {   
  n=0;strset(S,'\0');   
  cout<<"请输入字符个数:";   
  cin>>n;   
  ofstream   fileout("hfmtree");   
  if   (!fileout)   {cout<<"不能创建文件!"<<endl;getch();exit(1);}   
  cout<<"请输入字符集:";   
  int   f[255];   
  f[0]=0;   
  for   (int   i=0;i<n;i++)   
  cin>>S[i];   
  cout<<"请输入相应的频度:(以空格隔开)";   
  for   (i=1;i<=n;i++)   
  cin>>f[i];   
    
  hft=HuffmanTree(f,n);   
  fileout<<"中序遍历:";hft.PrintInOrder(fileout,hft.GetRoot());fileout<<'\n';   
  fileout<<"前序遍历:";hft.PrintPreOrder(fileout,hft.GetRoot());fileout<<'\n';   
  fileout<<"后序遍历:";hft.PrintPostOrder(fileout,hft.GetRoot());fileout<<'\n';   
  fileout.close();   
  encode();   
  cout<<"初始化完成!"<<endl;   
  getch();   
  IsInitial=true;   
  IsCode=false;   
  IsDecode=false;   
  }   
    
  void   CodeHuffman()   
  {   
  if   (!IsInitial)   {cout<<"请先进行初始化工作!\n"<<endl;getch();return;}   
  ifstream   filein("textfile");   
  if   (!filein)   {cout<<"不能读取文件!"<<endl;getch();exit(1);}   
  ofstream   fileout("codefile");   
  if   (!fileout)   {cout<<"不能写入文件!"<<endl;getch();exit(1);}   
  char   e;   
  while   (!filein.eof())   
  {   
  e=filein.get();   
  fileout<<code[match(e)];   
  // cout<<code[match(e)];   
  }   
  filein.close();   
  fileout.close();   
  cout<<"\n哈夫曼编码完成!"<<endl;   
  getch();   
  IsCode=true;   
  }   
  void   DecodeHuffman()   
  {   
  if   (!IsCode)   {cout<<"请先进行编码!\n"<<endl;getch();return;}   
  ifstream   filein("codefile");   
  if   (!filein)   {cout<<"不能读取文件!"<<endl;getch();exit(1);}   
  ofstream   fileout("result");   
  if   (!fileout)   {cout<<"不能写入文件!"<<endl;getch();exit(1);}   
  while   (!filein.eof())   
  {   
  for   (int   i=0;i<n;i++)   
  {   
  char   *buf=new   char[255];   
  int   len=strlen(code[i]);   
  filein.get(buf,len+1);   
  if   (strcmp(buf,code[i])==0)   
  {   
  //cout<<S[i];   
  fileout<<S[i];break;   
  }   
  else   filein.seekg(-len,ios::cur);   
  }   
  }   
  filein.close();   
  fileout.close();   
  cout<<"\n哈夫曼译码完成!"<<endl;   
  getch();   
  IsDecode=true;   
  }   
    
  void   PrintHuffman()   
  {   
  if   (!IsDecode)   {cout<<"请先进行解码!\n"<<endl;getch();return;}   
  ifstream   filein1("textfile");   
  if   (!filein1)   {cout<<"不能读取文件!"<<endl;getch();exit(1);}   
  ifstream   filein2("result");   
  if   (!filein2)   {cout<<"不能读取文件!"<<endl;getch();exit(1);}   
  while(!filein1.eof())   
  {   
  char   ch=filein1.get();   
  cout<<ch;   
  }   
  cout<<"\n以上为文件textfile中的内容"<<endl;   
  while(!filein2.eof())   
  {   
  char   ch=filein2.get();   
  cout<<ch;   
  }   
  cout<<"\n以上为文件result中的内容"<<endl;   
  getch();   
  filein1.close();   
  filein2.close();   
  }   
    
  void   DrawNode(int   x,int   y)   
  {   
          setcolor(RED);   
          circle(x,y,10);   
          setfillstyle(SOLID_FILL,CYAN);   
          floodfill(x,y,RED);   
  }   
  void   OutputHuffman()   
  {   
  if   (!IsInitial)   {cout<<"请先进行初始化!\n"<<endl;getch();return;}   
  int   tr[100][100];   
  for   (int   i=0;i<100;i++)   
  for   (int   j=0;j<100;j++)   
  tr[i][j]=-1;   
  int   gdriver,gmode;   
  detectgraph(&gdriver,&gmode);   
  initgraph(&gdriver,&gmode,"");   
  int   MaxLevel=strlen(code[0])+1;   
  for   (i=0;i<n;i++)   
  {   
          int   serial=1;   tr[i][0]=1;   
          int   len=strlen(code[i]);   
          if   (len+1>MaxLevel)   MaxLevel=len+1;   
          for   (int   j=0;j<len;j++)   
          {   
  serial*=2;   
  if   (code[i][j]=='1')   serial++;   
  tr[i][j+1]=serial;   
          }   
  }   
  int   Intervaly=400/(MaxLevel-1);   
  setbkcolor(BLUE);   
  for   (i=0;i<n;i++)   
  {   
          int   lx=640/2,ly=20;   
          DrawNode(lx,ly);   
          setcolor(BLACK);   
          outtextxy(lx-2,ly-2,"0");   
          for   (int   j=1;tr[i][j]!=-1;j++)   
          {   
  int   nx,ny;   
  int   Intervalx=640/((int)pow(2,j)+1);   
  ny=j*Intervaly;   
  nx=(tr[i][j]-(int)pow(2,j)+1)*Intervalx;   
  if   (j>=6&&tr[i][j]%2!=0)   {ny+=Intervaly/2;nx+=2*Intervalx;}   
  setcolor(YELLOW);   
  line(lx,ly,nx,ny);   
  DrawNode(lx,ly);   
  DrawNode(nx,ny);   
  setcolor(BLACK);   
  char   str[255];   
  if   (tr[i][j+1]==-1)   sprintf(str,"%c",S[i]);   
  else   sprintf(str,"%c",'0');   
  outtextxy(nx-2,ny-2,str);   
  outtextxy(lx-2,ly-2,"0");   
  lx=nx;ly=ny;   
          }   
  }   
  setcolor(12);   
  outtextxy(0,470,"Press   any   key   to   continue......");   
  getch();   
  closegraph();   
  }   
    
    
  void   main()   
  {   
  char   chioce;   
  while(1)   
  {   
  clrscr();   
  PrintInterface();   
  cin>>chioce;   
  switch(chioce)   
  {   
  case   'I':case   'i':Initiate();break;   
  case   'U':case   'u':InitiateEx();break;   
  case   'C':case   'c':CodeHuffman();break;   
  case   'D':case   'd':DecodeHuffman();break;   
  case   'P':case   'p':PrintHuffman();break;   
  case   'T':case   't':OutputHuffman();break;   
  case   'E':case   'e':return;   
  }   
  }   
  }   
    
  有点长啊,如果单看编码的话请看相关的函数即可，其他什么树，队列的具体实现可以略看