哈夫曼编码译码器

plaodj

设计要求：打开一篇英文文章，统计该文章中每个字符出现的次数，然后以它们作为权值，对每一个字符进行编码，编码完成后再对其编码进行译码。   

整个程序的输出是1.哈夫曼码，将英文文章翻译成的二进制代码，二进制代码翻译成英文文章


// bt.cpp: 主项目文件。

[mw_shl_code=cpp,true]#include "stdafx.h"
#include "iostream"
#include "iterator"
#include "String"
#define max 20
using namespace std;
struct node
{
    char ch;
    int weight;
    int parent;
    int lchild,rchild;
}Ht[2*max];
class htree
{
  private:
      int c[128];
      int j;
      int len;
      char **Hc;
      char code[20];
      char ch[1000];
  public:
      htree()
      { j=1;
        int i=0;
        memset(c,0,sizeof(int)*128);
        istream_iterator<char >  p(cin),eof;
        while(p!=eof)
        {   
           ch[i++]=*p;
           c[*p++]++;
        }
        ch='\0';
        for(int i=0;i<128;i++)
        if(c!=0)
        {
            Ht[j].ch=i;
            Ht[j].weight=c;
            Ht[j].lchild=0;
            Ht[j].rchild=0;
            j++;
        }
        
            
      }
      void Init()
      {
         for(int i=1;i<j-1;i++)
            for(int k=1;k<j-1;k++)
                if(Ht[k].weight>Ht[k+1].weight)
                {
                   struct node tmp=Ht[k];
                           Ht[k]=Ht[k+1];
                           Ht[k+1]=tmp;
                }
        for(int i=1,k=0;i<j-1;i++,k++)
        {   if(k==0)
            {
                Ht[j+k].lchild=i;
                Ht[j+k].rchild=i+1;
                Ht.parent=j+k;
                Ht[i+1].parent=j+k;
                Ht[j+k].weight=Ht[i+1].weight+Ht.weight;
            }
            else
            {
                Ht[j+k].lchild=j+k-1;
                Ht[j+k-1].parent=j+k;
                Ht[j+k].rchild=i+1;
                Ht[i+1].parent=j+k;
                Ht[j+k].weight=Ht[i+1].weight+Ht[j+k-1].weight;
            }
          if(i==j-2)
           len=j+k;
            
        }
      }
      void leafcode()
      {
          int i,p=len,cdlen=0;
          Hc=(char * *)malloc(j*sizeof(char *));
          for(int i=1;i<=p;i++)
              Ht.weight=0;
          while(p)
          {
              if(Ht[p].weight==0)
              {
                  Ht[p].weight=1;
                  if(Ht[p].lchild!=0)
                  {
                      p=Ht[p].lchild;
                      code[cdlen++]='0';
                  }
                  else if(Ht[p].rchild==0)
                  {
                      Hc[p]=(char*)malloc((cdlen+1)*sizeof(char));
                      code[cdlen]='\0';
                      strcpy(Hc[p],code);
                  }
               }
              else if(Ht[p].weight==1)
              {
                  Ht[p].weight=2;
                  if(Ht[p].rchild!=0)
                  {
                      p=Ht[p].rchild;
                      code[cdlen++]='1';
                  }
              }
              else
              {
                  Ht[p].weight=0;
                  p=Ht[p].parent;
                  --cdlen;
              }
          }
          for(int i=1;i<j;i++)
          {
              printf("%s=%c   ",Hc,Ht.ch);
          }
      }
      void ctob()
      {   int i=0;
          while(ch!='\0')
          {
              for(int k=1;k<j;k++)
                  if(ch==Ht[k].ch)
                  {
                      printf("%s  ",Hc[k]);
                      break;
                  }
                  i++;
          }
      }

};
int main()
{
    htree h;
    h.Init();
    h.leafcode();
    h.ctob();
    system("pause");
    return 0;
}[/mw_shl_code]