헤 프 만 트 리 인 코딩

4666 단어 부호화Huffman
헤 프 만 트 리 인 코딩 을 출력 하 는 문자열 을 입력 하 는 코드 를 공유 합 니 다. 테스트 할 때 오류 가 발생 하지 않 았 습 니 다. 오 류 를 테스트 하고 수정 해 주 십시오. 감사합니다!
내 코드 의 클 라 우 드 공유:http://yunpan.cn/csinkSxjb84FQ   추출 코드 2b2a
#include<iostream>

#include<string>

using namespace std;

struct HTNode

{

      char c;            //  

      int weight; //    ,  

      int lchild,rchild,parent;//                 

};//         

#define MAXSIZE 1000//              

class CHTree

{

public:

      CHTree(){ht=NULL;}

      void creat();//          

      void huffmancode();

      int select(int i);//   ht[1] ht[i]   parent 0  weight      ,        

      void Display();

private:

      HTNode* ht;//      

      int m;

      int n;//     

      int s1;

      int s2;

      string a;//        

      string str[MAXSIZE];//            

};//     

void CHTree::creat()

{

      int zfcxcs;//      

      cout<<"      :"<<endl;

      cin>>a;

      int l=a.length();//          

      n=0;

      ht=new HTNode[MAXSIZE];//  MAXSIZE           

      //            ,            

      bool yitongji=false;

      for(int j=0;j<l;j++)

      {

            zfcxcs=1;

            if(j>0)//      

            {

                  for(int i=0;i<j;i++)

                        if(a[i]==a[j])

                        {

                              yitongji=true;

                              break;

                        }

            }

            if(yitongji)//         ,      ,         

            {

                  yitongji=false;

                  continue;

            }

            for(int x=j+1;x<l;x++)

            {

                  if(a[j]==a[x])

                  {

                        zfcxcs++;

                  }

            }

            ht[n+1].c=a[j];

            ht[n+1].weight=zfcxcs;

            n++;

            yitongji=false;

      }

}

int CHTree::select(int i)

{

      int j=1;

      int k=1;

      int s;

      while(ht[j].parent!=0)// parent  0    

      {

            j++;

            s=j;

      }

      k=j+1;

      while(k<=i)

      {

            while(ht[k].parent!=0)

                  k++;

            if(k>i)

                  return s;

            if(ht[j].weight>ht[k].weight)

            {

                  ht[j].parent=0;//                  ht[j]     , ht[j].parent     0

                  j=k;//   “ht[j]”           

                  s=j;

                  ht[j].parent=-1;//  ht[j]      , ht[j] parent   -1,

            }

            else

            {

                  s=j;

                  ht[j].parent=-1;

            }

            k++;

      }

      return s;

}

void CHTree::huffmancode()

{

      if(n<=1)

            return;

      //            

      int i;

      m=2*n-1;//          

      for(i=1;i<=n;i++)//        

      {

            ht[i].parent=0;

            ht[i].lchild=0;

            ht[i].rchild=0;

      }

      for(;i<=m;i++)//         

      {

            ht[i].weight=0;

            ht[i].parent=0;

            ht[i].lchild=0;

            ht[i].rchild=0;

      }

      //----           

      for(i=n+1;i<=m;i++)

      {

            s1=select(i-1);

            s2=select(i-1);

            ht[s1].parent=i;ht[s2].parent=i;

            ht[i].lchild=s1;ht[i].rchild=s2;

            ht[i].weight=ht[s1].weight+ht[s2].weight;

      }

      //                         

      int c,f;

      int j;

      for(j=1;j<=n;j++)

      {

            for(c=j,f=ht[j].parent;f!=0;c=f,f=ht[f].parent)//             

                  if(ht[f].lchild==c)

                  {

                        str[j].insert(0,"0",0,1);

                  }

                  //    str[i]  0       “0”

                  else

                  {

                        str[j].insert(0,"1",0,1);

                  }

                  //    str[i]  0       “1”

      }

}

void CHTree::Display()

{

      cout<<"  "<<'\t'<<"  "<<'\t'<<"     "<<endl;

      for(int i=1;i<=n;i++)

      {

            cout<<ht[i].c<<'\t'<<ht[i].weight<<'\t'<<str[i]<<endl;

      }

      cout<<"    !"<<endl;

      delete ht;

}

int main()

{

      CHTree h;

      cout<<'
'<<"---------------------- -----------------------"<<endl; h.creat(); h.huffmancode(); h.Display(); system("pause"); return 0; }

좋은 웹페이지 즐겨찾기