huffman.txt

流传很广很经典的哈夫曼编码和译码

#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <malloc.h>

#define NULL 0
#define OK 1
#define ERROR 0
#define OVERFLOW -2
#define MAX_NUM 10000
#define MAX 60

typedef int Status;
typedef char **HuffmanCode;

typedef struct{
     unsigned int    weight;
     unsigned int    parent,lchild,rchild;
}HTNode,*HuffmanTree;

typedef struct{
     HuffmanTree HT;
     char         *c;
     int          longth;
     HuffmanCode HC;
}Huffman;

void Select(HuffmanTree HT,int end,int *s1,int *s2)
{
   int i;
   int min1=MAX_NUM;
   int min2;
   for (i=1;i<=end;i++)
   {
     if (HT[i].parent==0&&HT[i].weight<min1)
     {
       *s1=i;
       min1=HT[i].weight;
     }
   }
   min2=MAX_NUM;
   for(i=1;i<=end;i++)
   {
     if(HT[i].parent==0&&(*s1!=i)&&min2>HT[i].weight)
     {
       *s2=i;
       min2=HT[i].weight;
     }
   }
}

Huffman HuffmanCoding(Huffman Hfm)
{
   /*---------------------------------*/
   int i,n,m,s1,s2,start;
   int c,f;
   char *cd;
   n=Hfm.longth;
   if(n<=1)   return Hfm;
   m=2*n-1;
  
   for(i=n+1;i<=m;++i)
   {
     Select(Hfm.HT,i-1,&s1,&s2);
     Hfm.HT[s1].parent=i;
     Hfm.HT[s2].parent=i;
     Hfm.HT[i].lchild=s1;
     Hfm.HT[i].rchild=s2;
     Hfm.HT[i].weight=Hfm.HT[s1].weight+Hfm.HT[s2].weight;
   }
   /*------------------------------------------*/
   Hfm.HC=(HuffmanCode)malloc((n+1)*sizeof(char *));
   cd=(char *)malloc(n*sizeof(char));
   cd[n-1]='\0';

   for(i=1;i<=n;++i)
   {
     start=n-1;
     for(c=i,f=Hfm.HT[i].parent;f!=0;c=f,f=Hfm.HT[f].parent)
     {
       if(c==Hfm.HT[f].lchild)   cd[--start]='0';
       else cd[--start]='1';
     }
     Hfm.HC[i]=(char *)malloc((n-start)*sizeof(char));
     strcpy(Hfm.HC[i],&cd[start]);
   }
   free(cd);
   return Hfm;
}

Huffman InputHuffman(Huffman Hfm)
{
     int i,n;
     clrscr();
     printf("\n\n\t\t********************Initial*********************\n");
     printf("\tThe chars and weights will be saved in the file \"hfmTree\"\n");
     printf("Please input the number of the chars: ");
     scanf("%d",&n);
     Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
     Hfm.c=(char *)malloc((n+1)*sizeof(char));
     for(i=1;i<=n;i++)
     {
       printf("Please input the char: ");
       scanf("%s",&Hfm.c[i]);
       printf("Please input the weight of the char: ");
       scanf("%d",&Hfm.HT[i].weight);
       Hfm.HT[i].parent=0;
       Hfm.HT[i].lchild=0;
       Hfm.HT[i].rchild=0;
     }
     for(;i<=2*n-1;++i)
     {
       Hfm.HT[i].weight=0;
       Hfm.HT[i].parent=0;
       Hfm.HT[i].lchild=0;
       Hfm.HT[i].rchild=0;
     }
     Hfm.longth=n;
     return Hfm;
}

Huffman InitHuffman(Huffman Hfm)
{
   int n,i;
   FILE *fp;
   fp=fopen("hfmTree","rt");
   if(fp==NULL)
   {
     Hfm=InputHuffman(Hfm);
     fp=fopen("hfmTree","wt");
     fprintf(fp,"%d\n",Hfm.longth);
     for(i=1;i<=Hfm.longth;i++)
       fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
     rewind(fp);
   }
   else
   {
     fscanf(fp,"%d\n",&n);
     Hfm.c=(char *)malloc((n+1)*sizeof(char));
     Hfm.HT=(HuffmanTree)malloc((2*n)*sizeof(HTNode));
     for(i=1;i<=n;i++)
       fscanf(fp,"%s %d",&Hfm.c[i],&Hfm.HT[i].weight);
     for(i=1;i<=n;i++)
     {
       Hfm.HT[i].parent=0;
       Hfm.HT[i].lchild=0;
       Hfm.HT[i].rchild=0;
     }
     for(;i<=2*n-1;++i)
     {
       Hfm.HT[i].weight=0;
       Hfm.HT[i].parent=0;
       Hfm.HT[i].lchild=0;
       Hfm.HT[i].rchild=0;
     }
     Hfm.longth=n;
   }
   fclose(fp);
   Hfm=HuffmanCoding(Hfm);
   return Hfm;
}


void Output(Huffman Hfm)
{
   int i,n;
   n=Hfm.longth;
   printf("\n\n******************Output the code of the chars****************\n\n");
   for(i=1;i<=n;i++)
   {
      printf("\n");
      printf("Char: %c\t",Hfm.c[i]);
      printf("Weight: %d\t",Hfm.HT[i].weight);
      printf("Code: ");
      puts(Hfm.HC[i]);
   }
}

void Encoding(Huffman Hfm)
{
   int i=0,j=0,n;
   char ch[MAX];
   FILE *fp,*ffp;
   n=Hfm.longth;
   printf("\n\n*******************Encoding**************************\n\n");
   if((ffp=fopen("ToBeTran","rt"))==NULL)
   {
     printf("\nPlease input the sentence: ");
     scanf("%s",&ch);
     printf("\n");
     fp=fopen("CodeFile","wt+");
   }
   else
   {
     fscanf(ffp,"%s",ch);
     fclose(ffp);
   }
   while(ch[j])
     {
       for(i=1;i<=n;i++)
     if(ch[j]==Hfm.c[i])
     {
       printf("%s",Hfm.HC[i]);
       fprintf(fp,"%s",Hfm.HC[i]);
       break;
     }
      j++;
    }
    rewind(fp);
    fclose(fp);
}

void Decoding(Huffman Hfm)
{
   HuffmanTree p;
   int i,n;
   int j=0;
   char d[50];
   FILE *fp;
   n=Hfm.longth;
   printf("\n\n******************Decoding************************\n\n");
   if((fp=fopen("CodeFile","rt"))==NULL)
   {
     printf("Please input the code:");
     scanf("%s",&d);
   }
   else
   {
     fscanf(fp,"%s",d);
     fclose(fp);
   }
   printf("\nThe file is : ");
   fp=fopen("TextFile","wt+");
   while(d[j])
   {
     p=&Hfm.HT[2*n-1];
     while(p->lchild||p->rchild)
     {
       if(d[j]=='0')
       { i=p->lchild;   p=&Hfm.HT[i]; }
       else
       { i=p->rchild;   p=&Hfm.HT[i]; }
       j++;
     }
     printf("%c",Hfm.c[i]);
     fprintf(fp,"%c",Hfm.c[i]);
   }
   fclose(fp);
}

Huffman RebuildHuffman(Huffman Hfm)
{
   int n,i;
   FILE *fp;
   fp=fopen("hfmTree","wt");
   Hfm=InputHuffman(Hfm);
   fprintf(fp,"%d\n",Hfm.longth);
   for(i=1;i<=Hfm.longth;i++)
   fprintf(fp,"%c %d",Hfm.c[i],Hfm.HT[i].weight);
   rewind(fp);
   fclose(fp);
   Hfm=HuffmanCoding(Hfm);
   return Hfm;
}

int main()
{
   Huffman Hfm;
   char choice='a';
   Hfm=InitHuffman(Hfm);
   while(choice!='q')
   {
     clrscr();
     printf("\n\n\n\t\t*************************************\n\n");
     printf("\t\t\ta. Encoding:\n\n");
     printf("\t\t\tb. Decoding:\n\n");
     printf("\t\t\tc. Print all codes:\n\n");
     printf("\t\t\td. Rebuild the huffmantree:\n\n");
     printf("\t\t\tq. Quit...\n\n");
     printf("\n\t\t************************************\n\n");
     printf("Please enter your choice: ");
     scanf("%s",&choice);
     switch(choice)
     {
       case 'a':
        clrscr();
        Encoding(Hfm);
        printf("\n\n*******Please enter anykey to continue*******\n");
        getch(); break;
       case 'b':
        clrscr();
        Decoding(Hfm);
        printf("\n\n*******Please enter anykey to continue********\n");
        getch(); break;
       case 'c':
        clrscr();
        Output(Hfm);
        printf("\n\n*******Please enter anykey to continue********\n");
        getch(); break;
       case 'd':
        clrscr();
        Hfm=RebuildHuffman(Hfm);
        printf("\n\n********************Initial*********************\n");

        getch(); break;
       case 'q':
        break;
       default:
        printf(" Your choice is wrong!\n Please enter anykey to choice again!\n");
        getch(); break;
       }
     }
   return 0;
}