huffman.c

哈夫曼程序设计课程

#include <stdio.h>    /*定义以流为基础的I/O函数*/
#include <stdlib.h>   /*几种公用的例行程序，转换子程序，查找排序子程序及其它*/
#include <ctype.h>    /*字符分类和字符转换宏*/
#include <string.h>   /*字符串操作和存储操作的一些库函数*/
#define M 50

int n,m;              /*哈夫曼树和哈夫曼编码的存储表示*/
   struct node 
   {
   int weight;
   int parent;
   int lchild,rchild;
   char c;
   int num;
   };

  struct node *ht; 
  typedef char * *hfmcode;    /*动态分配数组存储哈夫曼编码表*/
  hfmcode HC;       /*动态分配数组存储哈夫曼树*/
  char wd[M];

FILE *fp1,*fp2,*fp3,*h,*fp4,*fp5;

sort(k,i)      /*建立排序函数在建哈夫曼树时被调用*/
{     int p,w,r,l,tmp,ch;

      p=ht[k].parent;
      w=ht[k].weight;
      r=ht[k].rchild;
      l=ht[k].lchild;
      tmp=ht[k].num;
      ch=ht[k].c;
      
      ht[k].parent=ht[i].parent;
      ht[k].weight=ht[i].weight;
      ht[k].rchild=ht[i].rchild;
      ht[k].lchild=ht[i].lchild;
      ht[k].num=ht[i].num;
      ht[k].c=ht[i].c;
      
      ht[i].parent=p;
      ht[i].weight=w;
      ht[i].rchild=r;
      ht[i].lchild=l;
      ht[i].num=tmp;
      ht[i].c=ch;
     }



void Initialization()    /*建哈夫曼树函数*/
     {
     int i=0,j=0,k=0,x=0,y=0,b=0,tm=0;
     int p=0,r=0,l=0,w=0;
     int tmp;
     char ch;
     ht=(struct node *)malloc((m+1)*sizeof(struct node));  /*0号单元未用分配树的空间*/
     
	     for(i=1;i<=n;i++)   /*利用循环输入每个字符及其权值*/
     {   printf("\n");
         printf("INPUT CHAR %d:",i);     
         scanf("%c",&ht[i].c);         
         if(ht[i].c==' ') ht[i].c='|';     
         wd[i]=ht[i].c;
         while(getchar()!='\n')
         continue;
         printf("INPUT THE WEIGHT :");
         scanf("%d",&ht[i].weight);
         printf("\n");
         while(getchar()!='\n')
         continue;

         ht[i].parent=0;    /*开始时将其左右孩子置空*/
         ht[i].rchild=0;
         ht[i].lchild=0;
         ht[i].num=i;
       }

     for(i=n+1;i<=m;i++)    
      {
        ht[i].parent=0;
        ht[i].num=i;
        ht[i].weight=0;
        ht[i].lchild=0;
        ht[i].rchild=0;
        ht[i].c='$';
       }


     for(i=1;i<n;i++)   /*第一次对输入的结点按其权值由小到大排序调用排序函数sort*/    
     {
      k=i;
      for(j=i+1;j<n+1;j++)
      if(ht[j].weight<ht[k].weight) k=j;
      sort(k,i);

       }

       y=n+1;
       x=1; b=2;
     
       for(i=n+1;i<=m;i++,x+=2,b+=2,y++)  /*从排序中取出权值最小的权值相加放到n+1个位置上*/
      
	   {
       ht[x].parent=i; 
       ht[b].parent=i;
       if( ht[x].num>ht[b].num) 
       {ht[i].rchild=ht[x].num; 
        ht[i].lchild=ht[b].num; }           
       else 
       {ht[i].lchild=ht[x].num; 
        ht[i].rchild=ht[b].num;}
        ht[i].weight=ht[x].weight+ht[b].weight;

       
       for(tm=1;tm<y;tm++)  /*每次生成新的结点后再一次排序取出权值最小的两个权值相加作为新结点*/
       {
       k=tm;
       for(j=tm+1;j<y+1;j++)
       if(ht[j].weight<ht[k].weight) k=j;
       sort(k,tm);
        }
        }
       
      for(i=1;i<m;i++)  /*最后一次排序是重新按序号排序*/
       {
       k=i;
       for(j=i+1;j<m+1;j++)
       if(ht[j].num<ht[k].num)  
	   k=j;
       sort(k,i);

     }
      printf("THE HUFFMAN TREE IS:\n");
      printf("\n");
      printf("   NUMBER        CHAR      WEIGHT        PARENT         LCHILD        RCHILD\n");
      for(i=1;i<=m;i++)
      printf("%4d %13c %13d %13d %13d %13d\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);


    if((h=fopen("hfmTree","wb"))==NULL)   /*将生成的哈夫曼树保存到文件hfmtree中*/
    { printf("CANT OPEN THE FILE!\n");
      exit(0);
    }
    for(i=1;i<=m;i++)
    fprintf(h,"%4d %13c %13d %13d %13d %13d\r\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild);
    fclose(h);
    }



void Encode()  /*编码函数*/
   { int i,mm,c,f,start,j;
     char g,*cd,*str,ch,k;
     printf("HFMTREE IN DISK PRESS 'D' , HFMTREE IN FILE PRESS 'F' :"); /*如果哈夫曼树在磁盘就按D如果调用文件里面的就按F*/
     scanf("%c",&k);
     
     if(k=='F')   
   { printf("PLEASE INPUT THE NUMBER OF LAST HUFFMANTREE CODE n : ");  /*如果调用文件哈夫曼树的话就要重新分配一个空间来保存哈夫曼树*/
     scanf("%d",&n); 
     m=2*n-1;
     ht=(struct node*)malloc((m+1)*sizeof(struct node));}
   
   if((h=fopen("hfmTree","rb"))==NULL)
   {printf("CANNOT OPEN FILE!\n");
   exit(0);}

   
     for(i=1;i<=m;i++)
     fscanf(h,"%4d %13c %13d %13d %13d %13d\n",&ht[i].num,&ht[i].c,&ht[i].weight,&ht[i].parent,&ht[i].lchild,&ht[i].rchild);  
     fclose(h);

    HC=(hfmcode)malloc((n+1)*sizeof(char *)); /*分配n个字符编码的头指针向量*/
    cd=(char *)malloc(n*sizeof(char));  /*分配求编码的工作空间*/      
    cd[n-1]='\0';  /*编码结束符*/
    
	for(i=1;i<=n;i++) /*逐个字符求哈夫曼编码*/
    { start=n-1;
      for(c=i,f=ht[i].parent;f!=0;c=f,f=ht[f].parent) /*从叶子到根逆向求编码*/
      if(ht[f].lchild==c) cd[--start]='0';
    else 
      cd[--start]='1';
    HC[i]=(char *)malloc((n-start)*sizeof(char));  /*为第i个安符编码分配空间*/
      strcpy(HC[i],&cd[start]);  /*从cd复制编码到HC*/
    }
  
    free(cd);  /*释放空间*/
    for(i=1;i<=n;i++)   
    printf("%c----%s\n",ht[i].c,HC[i]);
    printf("\n");
  
  
    printf("INPUT TOBETRAN NOW SELECT 1,READ FROM FILE SELECT 2\n");  /*输入需要编码的字符或者从文件中读取要编码的字符*/
  
    printf("INPUT:");
    scanf("%d",&g);getchar(); 
    if(g==1)
    {  if((fp1=fopen("ToBeTran","w"))==NULL)    /*把刚输入的字符输到文件TOBETRAN中*/
       { printf("CANNOT OPEN THE TOBETRAN FILE!\n");
         exit(0);
        }
      printf("INPUT YOUR TOBETRAN:\n");
      
      ch=getchar();
      
       while(ch!='\n')
       { if(ch==' ')fputc('|',fp1);  /*当输入的为空格的话用|代替*/
          else fputc(ch,fp1);
         ch=getchar();
        }
      fclose(fp1);
       }
    printf("\n");
    getchar();
    
    if((fp1=fopen("ToBeTran","r"))==NULL)
    { printf("CANNOT OPEN FILE TOBETRAN!\n");
      exit(0);
    }
  if((fp2=fopen("CodeFile","w"))==NULL)
    { printf("CANNOT OPEN CODEFILE!\n");
      exit(0);
    }
    if(g==2)
    printf("THE TOBETRAN FILE CONTENT IS:\n");
    while(!feof(fp1))
    { ch=fgetc(fp1);
      if(g==2)
      printf("%c",ch);
      
	  for(i=1;i<=n;i++) /*对输入的字符进行编码并写入文件CODEFILE中*/
      if(ht[i].c==ch) 
      for(j=0;HC[i][j]!='\0';j++) 
      fputc(HC[i][j],fp2);
    }
  fclose(fp1);
  fclose(fp2);
  printf("\n"); 
  printf("THE CODE HAVE BEEN INPUTTED INTO THE FILE!\n");
  printf("\n");  

}



void Decode()   /*译码函数*/
{ int i,c,f=m;
  char ch,k;
  printf("IF YOU USE HFMTREE IN DISK SELECT D, IF YOU USE THE ONE IN FILE SELECT F :");  /*如果哈夫曼树在磁盘的话按D在文件的话按F*/
  scanf("%c",&k);
     
     if(k=='F')   
   { printf("PLEASE INPUT THE NUMBER OF LAST HUFFMANTREE CODE n : ");  /*分配空间来保存哈夫曼编码*/
     scanf("%d",&n);
     m=2*n-1;
     ht=(struct node*)malloc((m+1)*sizeof(struct node));  }
     f=m;
    if((h=fopen("hfmTree","rb"))==NULL)
    { printf("CANNOT OPEN FILE!\n");
      exit(0);
    }
   for(i=1;i<=m;i++)
    fscanf(h,"%4d %13c %13d %13d %13d %13d\n",&ht[i].num,&ht[i].c,&ht[i].weight,&ht[i].parent,&ht[i].lchild,&ht[i].rchild); 
    fclose(h);
    if((fp2=fopen("CodeFile","r"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  if((fp3=fopen("TextFile","w"))==NULL)
    { printf("cannot open file\n");
      exit(0);
    }
  
  while(!feof(fp2))  /*译码过程*/
    { ch=fgetc(fp2);   
      printf("%c",ch); /*利用递归由根结点开始求字编码的字符*/
      if(ch=='0')  f=ht[f].lchild;  
      if(ch=='1')  f=ht[f].rchild;
      if(!ht[f].lchild&&!ht[f].rchild) 
      { 
      printf("%c",ht[f].c);
      fputc(ht[f].c,fp3); f=m; }
      }
  
  fclose(fp2);
  fclose(fp3);
  printf("\n");
}



void Printcode()  /*打印代码函数*/
{ int i=0;
  char ch;
  if((fp2=fopen("CodeFile","r"))==NULL) /*从文件CODEFILE中读取编码并打印出来*/
    { printf("CANNOT OPEN FILE!\n");
      exit(0);
    }
  if((fp4=fopen("CodePrin","w"))==NULL)
    { printf("CANNOT OPEN FILE!\n");
      exit(0);
    }
  while(!feof(fp2)) { if(i==50) { printf("\n");  i=0; }  ch=fgetc(fp2); fputc(ch,fp4); printf("%c",ch); i++; }  /*每行50个代码打印出来*/
  printf("\n");
  fclose(fp2);
  fclose(fp4);
}




void Printtree()  /*用凹入法找印哈夫曼树*/
{ int i,k,top,b,p;

  int *level,*stack;  
  printf("THE HUFFMANTREE IS :\n");
  level=(int *)malloc(n*sizeof(int));
  stack=(int *)malloc(n*sizeof(int));
  if((h=fopen("hfmTree","rb"))==NULL)
  { printf("CANNOT OPEN FILE!\n");
    exit(0); }
  
    for(i=1;i<=m;i++)
    fscanf(h,"%4d %13c %13d %13d %13d %13d\n",&ht[i].num,&ht[i].c,&ht[i].weight,&ht[i].parent,&ht[i].lchild,&ht[i].rchild);
    fclose(h);
    b=m;
    if(b!=0)
  { top=1; stack[top]=b;  level[top]=3; /*由根结点开始打印,跟着找印其右子树,再到左子树*/
    while(top>0)
  { p=stack[top];   k=level[top];    for(i=1;i<=k;i++) printf(" ");
    printf("%d\n",ht[p].weight);
    top--;
    if(ht[p].rchild!=0)
  { top++;    stack[top]=ht[p].rchild;  level[top]=k+3; }
    if(ht[p].lchild!=0)
  { top++;    stack[top]=ht[p].lchild;  level[top]=k+3; }
    }
    }
  if((fp5=fopen("TreePrint","w"))==NULL)
  { printf("CANNOT OPEN FILE!\n");
    exit(0); }
    for(i=1;i<=m;i++)
    fprintf(fp5,"%4d %13c %13d %13d %13d %13d\r\n",ht[i].num,ht[i].c,ht[i].weight,ht[i].parent,ht[i].lchild,ht[i].rchild); 
    fclose(fp5);
   }





 void main()

{ char cho;
  
printf("\t***************WELCOME TO USE THE HUFFMAN SYSTEM****************");
printf("\n");
printf("\n");
printf("\t***************CAIXUECONG NETWORK(1) 200208024103***************");

printf("\n");
printf("\n");
printf("\n");
printf("         ----------------THE SYSTEM HAS FIVE FUNCTION---------------\n");
printf("\n");
printf("         I:INSTAL THE HUFFMAN TREE\n");
printf("\n");
printf("         E:ENCODE THE CODE\n"); 
printf("\n");
printf("         D:DECODE TEH CODE\n");
printf("\n");
printf("         T:PRINT THE HUFFTREE\n");
printf("\n");
printf("         P:PRINT THE FILE CODE\n");
printf("\n");
printf("         Q:QUIT \n");
printf("\n");
printf("         --------------PLEASE CHOOSE ONE FUNCTION ABOVE ---------------\n");
printf("\n");
printf("\n");
printf("INPUT YOUR FUNCTIONT CHOICE ");
scanf("%c",&cho);
getchar();
  for(;!(cho=='Q');)
  {
   if(cho=='I'){printf("INPUT THE NUMBER OF THE CHAR : "); 
   scanf("%d",&n);
   m=2*n-1;
   while(getchar()!='\n')  continue; Initialization();}
   if(cho=='E')  Encode();
   if(cho=='D')  Decode();
   if(cho=='P')  Printcode();
   if(cho=='T')  Printtree();
   
printf("\n");
printf("\n");
printf("         ----------------THE SYSTEM HAS FIVE FUNCTION---------------\n");
printf("\n");
printf("         I:INSTAL THE HUFFMAN TREE\n");
printf("\n");
printf("         E:ENCODE THE CODE\n"); 
printf("\n");
printf("         D:DECODE TEH CODE\n");
printf("\n");
printf("         T:PRINT THE HUFFTREE\n");
printf("\n");
printf("         P:PRINT THE FILE CODE\n");
printf("\n");
printf("         Q:QUIT \n");
printf("\n");
printf("         --------------PLEASE CHOOSE ONE FUNCTION ABOVE --------------\n");
printf("\n");
printf("\n");
printf("INPUT YOUR FUNCTIONT CHOICE ");
scanf("%c",&cho);
while(getchar()!='\n')  continue;
   }
}