huffmantree.cpp

使用霍夫曼huffman 編碼方式 對文件進行壓縮 程序很簡單 主要是幫助新人了解霍夫曼編碼的實現方法

#include "huffmantree.h"
huffmantree::huffmantree()
{
     tree=NULL;
     codestree=NULL;
     decode_node=NULL;
     WEP=0;
}
//--------------------------------------------------------
huffmantree::~huffmantree()
{
     freeall();
     codes_freeall();
     
}
//---------------------------------------------------------
void huffmantree::getcodes(char chr,bool *&code,int &length,huffmancode * root)
{
     if(root!=NULL)
     {
           if(chr==root->chr)
           {
                code=root->code;
                length=root->length;
           }
           else
           {
               if(chr<root->chr)
                 getcodes(chr,code,length,root->left);
               else
                 getcodes(chr,code,length,root->right);   
           }
     }    
}
//---------------------------------------------------------
bool huffmantree::codes_get(char chr,bool *&code,int &length)
{
     if(codestree==NULL)
        return false;
     getcodes(chr,code,length,codestree);
        return true;
}
//---------------------------------------------------------
void huffmantree::codes_Insertbychr(char chr,bool *code,int length)
{
     huffmancode *newelem=new huffmancode;
     newelem->code=code;
     newelem->length=length;
     newelem->chr=chr;
     newelem->left=NULL;newelem->right=NULL;newelem->pre=NULL;
     
     huffmancode *p=codestree,*t=NULL;
     bool side;
     if(p==NULL)
         codestree=newelem;
     else
     {
        while(p!=NULL)
        {
            if(chr<p->chr)
            {
                 t=p;
                 p=p->left;
                 side=LEFT;
            }
            else
            {
                 t=p;
                 p=p->right;
                 side=RIGHT;
                 
            }
        }
        newelem->pre=t;
        if(side==LEFT)
          t->left=newelem;
        else
          t->right=newelem;
     }
     
      
}
//---------------------------------------------------------
int huffmantree::codes_freeall()
{
    int sum=0;
    freeallcodes(codestree,sum);
    codestree=NULL;
    return sum;
}
void huffmantree::freeallcodes(huffmancode * root,int &sum)
{
    if(root!=NULL)
    {
        freeallcodes(root->left,sum);
        freeallcodes(root->right,sum);
        delete [] root->code;
        delete root;
        sum++;
    }
}
//------------------------------------------
int huffmantree::freeall()
{
     int c=0;
     nodes *t=NULL,*p=tree;
     while(p!=NULL)
     {
         if(p->left!=NULL)
           p=p->left;
         else
             if(p->right!=NULL)
                p=p->right;
             else
                {
                    t=p->pre;
                    if(t!=NULL)
                       if(t->left==p)
                          t->left=NULL;
                       else
                          t->right=NULL;
                    delete p;
                    c++;
                    p=t;
                }                 
     }
     tree=NULL;
     return c;
}
//------------------------------------------
nodes *huffmantree::newElem()
{
     nodes * p=new nodes;
     p->pre=NULL;
     p->left=NULL;
     p->right=NULL;
     return p;
}
//-----------------------------------------
void huffmantree::Insertbychr(char chr)
{ 
     nodes *newelem=newElem();
     nodes *p=tree,*t=NULL;
     bool side;
     if(p==NULL)
     {
         tree=newelem;
         newelem->key.frequency=1;
         newelem->key.chr=chr;
     }
     else
     {
        while(p!=NULL)
        {
            if(p->key.chr>chr)
            {
                 t=p;
                 p=p->left;
                 side=LEFT;
            }
            else
            {
                 if(p->key.chr<chr)
                 {
                     t=p;
                     p=p->right;
                     side=RIGHT;
                 }
                 else
                 {
                     p->key.frequency++;
                     return;
                 }
            }
        }
        newelem->pre=t;
        newelem->key.frequency=1;
        newelem->key.chr=chr;
        if(side==LEFT)
          t->left=newelem;
        else
          t->right=newelem;
     } 
        
}
//------------------------------------------
void huffmantree::Insertbyfre(str_char &key)
{
     nodes *newelem=newElem();
     nodes *p=tree,*t=NULL;
     bool side;
     if(p==NULL)
     {
         tree=newelem;
         newelem->key.frequency=key.frequency;
         newelem->key.chr=key.chr;
     }
     else
     {
        while(p!=NULL)
        {
            if(p->key.frequency>key.frequency)
            {
                 t=p;
                 p=p->left;
                 side=LEFT;
            }
            else
            {
                 t=p;
                 p=p->right;
                 side=RIGHT;
            }
        }
        newelem->pre=t;
        newelem->key.frequency=key.frequency;
        newelem->key.chr=key.chr;
        if(side==LEFT)
          t->left=newelem;
        else
          t->right=newelem;
     }
}
//-----------------------------------------------------
void huffmantree::inordprint(nodes * root)
{
     if(root!=NULL)
     {
         inordprint(root->left);
         printf("%c:%d|",root->key.chr,root->key.frequency);
         inordprint(root->right);
     }
}
//-----------------------------------------------------
void huffmantree::printall()
{
     inordprint(tree);
     printf("\n");
}
//-----------------------------------------------------
int huffmantree::getnodes()
{
    int sum=0;
    countnodes(tree,sum);
    return sum;
}
//-----------------------------------------------------
void huffmantree::countnodes(nodes * root,int & sum)
{
    if(root!=NULL)
    {
        sum++;
        countnodes(root->left,sum);
        countnodes(root->right,sum);
    }
}
//----------------------------------------------------
bool huffmantree::treetoarray(str_char * &arr,int & size)
{
     size=getnodes();
     if(tree==NULL)
           return false;  
     arr=new str_char[size];
     int index=0;
     fillarray(arr,index,tree);
     return true;
}
//-----------------------------------------------------
void huffmantree::fillarray(str_char * &arr,int & index,nodes * root)
{
     if(root!=NULL)
     {
        fillarray(arr,index,root->left);
        arr[index].frequency=root->key.frequency;
        arr[index].chr=root->key.chr;
        index++;
        fillarray(arr,index,root->right);
     }
}
//-----------------------------------------------------
bool huffmantree::makeHufftree(str_char * ordarr,int size)
{
     if(size<2)
       return false;
     freeall();
     codes_freeall();
     WEP=0;
     nodeslist *head=NULL,*p=NULL,*tmpnode=NULL;
     nodes *left=NULL,*right=NULL,*t=NULL;//t for new node
     int i=0;
     do
     {
         
         if(left!=NULL&&right!=NULL)                                    //-------------------------
         {
             t=newElem();                                               //make a new node
             t->key.frequency=left->key.frequency+right->key.frequency;
             t->left=left;
             t->right=right;
             left->pre=t;
             right->pre=t;
             if(head==NULL)
             {
                head=new nodeslist;
                head->node=t;
                head->next=NULL;
             }
             else
             {
                 p=head;
                 while(p!=NULL&&(t->key.frequency>p->node->key.frequency))
                 {
                    tmpnode=p;                                                      
                    p=p->next;
                 }
                 if(p==head)                                             //insert new node as the head of the nodeslist
                 {
                    head=new nodeslist;
                    head->node=t;
                    head->next=p;
                 }
                 else
                 {
                    tmpnode->next=new nodeslist;
                    tmpnode->next->node=t;
                    tmpnode->next->next=p;
                 }                                             
             }
             left=NULL;
             right=NULL;
             if(i==size&&head->next==NULL)                               //if all elements merged then jump out
                break;
         }                                                              //-------------------------
         
         if(i<size)
         {
             if(head!=NULL)
             {
                 if(ordarr[i].frequency<head->node->key.frequency) //when the element in array smaller than element in list 
                 {                                                //put it into left or right which r ready to merge
                      t=newElem();
                      t->key.chr=ordarr[i].chr;
                      t->key.frequency=ordarr[i].frequency;
                      if(left==NULL)
                         left=t;
                      else
                         right=t;
                      i++;
                 }
                 else                                             //when the elementin in list smaller than element in array
                 {                                                //put it into left or right which r ready to merge
                      if(left==NULL)                              
                         left=head->node;
                      else
                         right=head->node;
                      p=head;
                      head=head->next;
                      delete p;
                 }
                 
             }
             else
             {
                      t=newElem();
                      t->key.chr=ordarr[i].chr;
                      t->key.frequency=ordarr[i].frequency;
                      if(left==NULL)
                         left=t;
                      else
                         right=t;
                      i++;
             }
         }
         else
         {
                      if(left==NULL)                              
                         left=head->node;
                      else
                         right=head->node;
                      p=head;
                      head=head->next;
                      delete p;
         }
     }while(1);
     tree=head->node;
     decode_node=tree;
     delete head;
     return true;
}
//-----------------------------------------------------
bool huffmantree::ifleaf(nodes * node)
{
     if(node->left==NULL&&node->right==NULL)
        return true;
     else
        return false;
}
//-----------------------------------------------------
bool huffmantree::codes_makeCodestree()
{
     if(tree==NULL)
        return false;
     codes_freeall();
     WEP=0;
     makeCodestree(tree,0,WEP);
     if((WEP%8)!=0)
       WEP=(WEP/8)+1;
     else
       WEP=WEP/8;
     return true;
     
}
//-----------------------------------------------------
void huffmantree::makeCodestree(nodes * root,int path,unsigned long &WEP)
{
     if(root!=NULL)
     {
        if(ifleaf(root))
        {
          bool *code=new bool[path];
          codes_Insertbychr(root->key.chr,code,path);
          WEP=WEP+(unsigned long)path*root->key.frequency;
          nodes * p=root->pre;
          while(p!=NULL)
          {
              if(p->left==root)
                code[--path]=false;
              else
                code[--path]=true;
              root=p;
              p=p->pre;
          }
        }
        else
        {
            path++;
            makeCodestree(root->left,path,WEP);
            makeCodestree(root->right,path,WEP);
        }
     }
}

//-----------------------------------------------------
bool huffmantree::getchr(bool code,char & chr)
{
     if(decode_node==NULL)
       return false;
     if(code==false)
       decode_node=decode_node->left;
     else
       decode_node=decode_node->right;
     if(ifleaf(decode_node))
     {
       chr=decode_node->key.chr;
       decode_node=tree;
       return true;
     }
     else
       return false;
        
}
//-----------------------------------------------------
void huffmantree::codes_inordprint(huffmancode * root)
{
     if(root!=NULL)
     {
           codes_inordprint(root->left);
           printf("%c:%d| ",root->chr,root->length);
           codes_inordprint(root->right);
     }
}
//-----------------------------------------------------
void huffmantree::codes_printall()
{
     codes_inordprint(codestree);
}