haffman.c

哈腹满编码

#include<stdio.h>   
  #include<stdlib.h>   
  #include<string.h>   
  #include<conio.h>   
    
  typedef   struct   htnode{   
                  unsigned   int   weight;   
                  unsigned   int   parent,lchild,rchild;   
                }htnode,*htree;   
  typedef   char   *   *   huffmancode;   
    
  htree   createhtree(int   n)   
  {   
    htree   ht;   
    htnode   *p;   
    int   i,m,*s1,*s2;   
    void   select(htree   ht,int   i,int   *   l,int   *   r);   
    *s1=*s2=0;   
    if(n<=1)   
        return(NULL);   
    m=2*n-1;   
    ht=(htree)malloc((m+1)*sizeof(htnode));   
    for(p=ht+1,i=1;i<=n;i++,p++){   
            printf("\nInput   the   weight(%d):",i);   
            scanf("%d",&p->weight);   
            p->parent=p->lchild=p->rchild=0;   
          }   
    for(;i<=m;i++,p++)   
          p->weight=p->parent=p->lchild=p->rchild=0;   
    for(i=n+1;i<=m;i++){   
            select(ht,i,s1,s2);   
            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;   
          }   
    return(ht);   
  }   
    
    
  void   select(htree   ht,int   i,int   *   l,int   *   r)   
  {   
    int   k,temp1,temp2;   
    temp1=temp2=32767;   
    *l=*r=0;   
    for(k=1;k<=i-1;k++){   
          if(ht[k].parent==0)   
              if(ht[k].weight<temp1){   
                  temp2=temp1;   
                  *r=*l;   
                  temp1=ht[k].weight;   
                  *l=k;   
                }   
              else   if(ht[k].weight<temp2){   
                  temp2=ht[k].weight;   
                  *r=k;   
                }   
      }   
  }   
    
  void   encode(htree   ht,int   n)   
  {   
    int   i,c,f,start;   
    char   *   code;   
    huffmancode   hc;   
    hc=(huffmancode)malloc((n+1)*sizeof(char   *));   
    code=(char   *)malloc(n*sizeof(char));     /*store   the   huffmancode */
    code[n-1]='\0';   
    for(i=1;i<=n;i++){         /*  encode   a   huffman-tree   from   leaf   to   root*/
          start=n-1;   
          for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent)   
                if(ht[f].lchild==c)   
  code[--start]='0';   
                else   
  code[--start]='1';   
          hc[i]=(char   *)malloc((n-start)*sizeof(char));   
          strcpy(hc[i],&code[start]);   
    }   
    free(code);   
    printf("\n\nHuffman-code(with   encode):");   
    for(i=1;i<=n;i++)   
          printf("\n%d:   %s",i,hc[i]);   
  }   
    
  void   decode(htree   ht,int   n)   
  {   
    int   i,m,p,codelen;   
    char   *   code;   
    huffmancode   hc;   
    hc=(huffmancode)malloc((n+1)*sizeof(char   *));   
    code=(char   *)malloc(sizeof(char));   
    m=2*n-1;   codelen=0;p=m;   
    for(i=1;i<=m;++i)   
          ht[i].weight=0;   
    while(p){   
          if(ht[p].weight==0){   
              ht[p].weight=1;   
              if(ht[p].lchild!=0){   
                  p=ht[p].lchild;   
                  code[codelen++]='0';   
              }   
              else   if(ht[p].rchild==0){   
                    hc[p]=(char   *)malloc((codelen+1)*sizeof(char));   
                    code[codelen]='\0';   
                    strcpy(hc[p],code);   
                     printf("\nhc[%d]:%s",p,hc[p]);
              }   
          }   
          else   if(ht[p].weight==1){   
              ht[p].weight=2;   
              if(ht[p].rchild!=0){   
                  p=ht[p].rchild;   
                  code[codelen++]='1';   
              }   
          }   
          else{        ht[p].weight=2;
              ht[p].weight=0;   
              p=ht[p].parent;   
              --codelen;   
          }   
    
    }   
    printf("\n\nHuffman-code(with   denode):");   
    for(i=1;i<=n;i++)   
          printf("\n%d:   %s",i,hc[i]);   
    
  }   
    
    
    
  void   main()   
  {   
    htree   ht;   
    int   n,i;   
    clrscr();   
    printf("\nInput   the   number   of   the   leaf-node");   
    scanf("%d",&n);   
    ht=createhtree(n);   
    printf("\nHT");   
    printf("\n         weight   parent   lchild   rchild");   
    for(i=1;i<=2*n-1;i++){   
        printf("\n");   
        printf("%2d   %6d   %6d   %6d   %6d",i,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);   
      }   
    encode(ht,n);   
    decode(ht,n);   
  }