huffman.c

Huffman 编解码源程序 VC语言开发

          fputc(temp,ofp);

          if(buffer[i][j]==-1)break;

          ++i;

     }

}

/**********************以下是解压缩算法************************/

void decompress(FILE *ifp,FILE *ofp)

{

     int i=0;

     signed ArraySize=0;

     RateTabNode *head;

     CodeNode *codehead,*codetmp;//存储编码的数组首地址]

     OFinal *ofinalhead;

     HuffmanTree *root;//树根

     LeafNode *leafhead;//存储叶子结点的地址，利于编码

     char buffer[MaxSize][8];

 

     buf_init(buffer,MaxSize);

     fread(&ArraySize,sizeof(unsigned),1,ifp);//读字符种类数

     

     codehead=(CodeNode *)malloc(ArraySize*sizeof(CodeNode));

     codetmp=(CodeNode *)malloc(ArraySize*sizeof(CodeNode));

     ofinalhead=(OFinal *)malloc(ArraySize*sizeof(OFinal));

     fread(ofinalhead,sizeof(OFinal),ArraySize,ifp);//读字符和权

 

     head=RebuildLink(ofinalhead,ArraySize);

         

     root=HTCreate(head);//创建Huffman树，返回根结点

         

     leafhead=(LeafNode *)malloc(ArraySize*sizeof(LeafNode));

     codehead=(CodeNode *)malloc(ArraySize*sizeof(CodeNode));

         

     for(i=0;i<ArraySize;++i)

     {

         int j=0;

         for(j=0;j<CodeMaxLen;++j)

              codetmp[i].code[j]='#';

     }

     //初始化编码表全部为'#'

     FindLeaf(root,leafhead,ArraySize);//找出所有叶子结点，记录地址

     HFCoding(leafhead,codetmp,ArraySize);//从叶子到根，从下向上进行编码

/*******以下循环去除#在编码前，以便字符串的匹配********/

     for(i=0;i<ArraySize;++i)

     {

         int j=0,k=0;

         codehead[i].ch=codetmp[i].ch;

         for(j=0,k=0;j<CodeMaxLen;++j)

         {

              if(codetmp[i].code[j]!='#')

              {

                   codehead[i].code[k]=codetmp[i].code[j];

                   ++k;

              }

         }

     }

     free(codetmp);

     while(!feof(ifp))

     {

         deWbuffer(ifp,buffer,MaxSize);

         deRbuffer(ofp,codehead,ArraySize,buffer,MaxSize);

     }

}

RateTabNode *RebuildLink(OFinal *ofinalhead,int ArraySize)//恢复双链表结构

{

     RateTabNode *head,*p,*q;

     int i=0;

 

     q=(RateTabNode *)malloc(sizeof(RateTabNode));

     head=p=q;

     q->next=NULL;

     head->pre=NULL;

     head->LChild=head->RChild=NULL;

 

     for(i=0;i<ArraySize;++i)

     {

         p->ch=ofinalhead[i].ch;

         p->weight=ofinalhead[i].weight;

        if(i==ArraySize-1)break;

         q=(RateTabNode *)malloc(sizeof(RateTabNode));

         p->next=q;

         q->pre=p;

         p=q;

         p->next=NULL;

         p->LChild=p->RChild=NULL;

     }

     return head;

}

void deWbuffer(FILE *ifp,char (*buffer)[8],int size)

{

     char temp;

     int i=0;

 

     buf_init(buffer,MaxSize);

     while(i<size-1&&!feof(ifp))

     {

         int j=0;

         temp=fgetc(ifp);

        if(feof(ifp))return;

         for(j=0;j<8;++j)

              buffer[i][j]=((temp>>(7-j))&1)+48;//写入的是数字，注意转换为字符'1'

         ++i;

     }

}

char CodeMatch(CodeNode *codehead,int ArraySize,char *ch)//在编码中找当前字符串是否是编码，是则返回该编码对应字符，否则返回'\0'

{

     int i;

     for(i=0;i<ArraySize;++i)

         if(strcmp(codehead[i].code,ch)==0)

              return codehead[i].ch;

     return '\0';

}

void deRbuffer(FILE *ofp,CodeNode *codehead,int ArraySize,char (*buffer)[8],int size)//解码，还原文件

{

     int i=0;

     char temp[CodeMaxLen];

     char ch;

    temp[0]='\0';

 

     while(*(*buffer+i)!=-1)//读一个字符

     {

         chstract(temp,*(*buffer+i));//将字符加到字符串temp后

         if((ch=CodeMatch(codehead,ArraySize,temp))!='\0')//匹配则解码，否则字符串继续变长

         {

              fputc(ch,ofp);

              temp[0]='\0';

         }

         ++i;

     }

}

void chstract(char *temp,char ch)//把一个字符加到当前字符串末尾

{

     int i;

     for(i=0;i<CodeMaxLen;++i)

     {

         if(temp[i]=='\0')

         {

              temp[i]=ch;

              temp[i+1]='\0';

              return;

         }

     }

     

}

 

/***************共用算法****************/

HuffmanTree *HTCreate(RateTabNode *head)//双链表形式创建Huffman树

{

     HuffmanTree *p1,*p2,*root;

    RateTabNode *temp,*p;

 

     root=(HuffmanTree *)malloc(sizeof(HuffmanTree));

     //printf("%d\n",SizeAssure(head));

    if(SizeAssure(head)==2)//当只生剩下两个元素，直接将这两棵树作为子树，返回总根结点地址

     {

         root->ch='\0';

         root->LChild=head;

         head->parent=root;

         root->RChild=head->next;

         root->weight=head->weight+head->next->weight;

         head->next->parent=root;

         head=root;

        head->parent=NULL;

 

         return head;

     }

     else

     {

       for(p=temp=head;p!=NULL;p=p->next)//找权最小的结点

       {

         if(temp->weight>p->weight)

              temp=p;

         

       }

       p1=temp;

       /****记下最小结点的地址，将它从链表中移除(分三种情况，头、尾和中间)***/

       if(p1->pre==NULL)//表头

       {

           head=head->next;

           head->pre=NULL;

       }

       else if(p1->next==NULL)//表尾

       {

           p1->pre->next=NULL;

       }

       else

       {

           p1->pre->next=p1->next;

           p1->next->pre=p1->pre;

           

       }//中间　　　

       p1->next=p1->pre=NULL;

       /*********寻找次小权结点，过程同上面完全相同，找去掉最小后的最小，即次小**********/

       for(temp=p=head;p!=NULL;p=p->next)

       {

         if(temp->weight>p->weight)

              temp=p;

       }

       p2=temp;

       if(p2->pre==NULL)

       {

           head=head->next;

           head->pre=NULL;

       }

       else if(p2->next==NULL)

       {

           p2->pre->next=NULL;

       }

       else

       {

           p2->pre->next=p2->next;

           p2->next->pre=p2->pre;

           

       }

       //取次小值

      p2->next=p2->pre=NULL;

       //printf("%d\n",SizeAssure(head));getch();

       /*********将两个最小值建立一棵子树，并将它们的根结点插入双链表**********/

       root->LChild=p1;

       root->RChild=p2;

       p1->parent=root;

       p2->parent=root;

     

       root->ch='\0';

       root->weight=p1->weight+p2->weight;

       root->next=head;

       head->pre=root;

       head=root;

       head->pre=NULL;

 

       head=HTCreate(head);//递归，直到剩两个结点在双链表中

     }

	 return head;

}

 

void FindLeaf(RateTabNode *head,LeafNode *leafhead,int size)//递归查找叶子，记下地址到数组

{

     static int num=0;

     if(head->LChild==NULL&&head->RChild==NULL&&num<size)

     {

         leafhead[num].ch=head->ch;

         leafhead[num].leaf=head;

         ++num;

         return;

     }

     if(head==NULL)return;

     

     FindLeaf(head->LChild,leafhead,size);

     FindLeaf(head->RChild,leafhead,size);

     

}

void HFCoding(LeafNode *leafhead,CodeNode *codehead,int size)//自下向上编码，左右

{

     int i=0,j=CodeMaxLen;

      LeafNode *leaftmp=leafhead;

      while(i<size)

      {

          j=CodeMaxLen;

          codehead[i].ch=leaftmp[i].ch;

          codehead[i].code[--j]='\0';

          while(leaftmp[i].leaf->parent!=NULL&&j>=0)

          {

               if(leaftmp[i].leaf->parent->LChild==leaftmp[i].leaf)

                    codehead[i].code[--j]='0';

               if(leaftmp[i].leaf->parent->RChild==leaftmp[i].leaf)

                    codehead[i].code[--j]='1';

               leaftmp[i].leaf=leaftmp[i].leaf->parent;//向上

          }

          ++i;

      }

}

void buf_init(char (*buffer)[8],int size)//缓冲初始化

{

     int i,j;

     for(i=0;i<size;++i)

         for(j=0;j<8;++j)

              buffer[i][j]=-1;

}