hafuman.c

哈夫曼编码译码程序

   #include "stdio.h"
   #include "stdlib.h"
   #include <string.h>
   /*huffmancode storage struct*/
   typedef struct
   {
        char ch;
         char code[20];
         int len;
   }CodeNode;
   typedef CodeNode huffmancode[n+1];      /*empty No.0*/

   /*Btree storage struct*/
   typedef struct BTNode
   {
        int weight;
        char val;
       struct BTNode * lchild,* rchild, * parent;   /*left,right and parents node*/
   }HTNode;     /*Btree node struct*/
   int num;

/**从文件filename中读取要处理的字符存入数组shuru[].**/

  void read_char(char *filename,char *shuru)
  {
      FILE *fp;
      int i;
      char temp;
      if((fp=fopen(filename,"r"))==NULL)
      {
          printf("can not open %s",filename);
          exit(0);
      }//end of if
      for(i=0;i<n;i++)
      {
          shuru[i]='\0';
      }
      i=0;
      temp=fgetc(fp);
      while(i<n && temp!=EOF)
      {
          shuru[i]=temp;
          temp=fgetc(fp);
          i++;
      }//end of while
      printf("\n成功从文件%s读入字符串!\n\n",filename);
      fclose (fp);
  }

/**统计字符串中各种字符的个数以及字符种类**/

int jsq(char *s,int cnt[],char str[])
{
    char *p;
    int i,j,k;
    int temp[27];
    for(i=1;i<=26;i++)
        temp[i]=0;
    for(p=s;*p!='\0';p++)
    {
        if(*p>='A' && *p<='Z')
    	{
            k=*p-64;
            temp[k]++;
        }//end of if 
    }//end of for
    for(i=1,j=0;i<=26;i++)
        if(temp[i]!=0)
    	{
        	j++;
            str[j]=i+64;
            cnt[j]=temp[i];
        }//end of if
        //printf("%d\n",j);
    return j;
}

/**从根结点root开始递归遍历赫夫曼树**/

void bltree(HTNode *root,huffmancode HC,int &x)
{   HTNode *a,*temp;
    a=root;
    if(a->val){temp=a;x++;hs(temp,temp->val,HC,x);}
    if(a->rchild)bltree(a->rchild,HC,x);
    if(a->rchild)bltree(a->lchild,HC,x);
}

/**以回溯的方法从赫夫曼树中得到编码**/

void hs(HTNode *temp,char c,huffmancode HC,int &x)
{   char cd[n];
    
    HTNode *p;
    int i=0,j;
    while(p=temp->parent)
    {
        cd[i]=(p->lchild==temp) ? '0':'1';
        temp=p;
        i++;
    }
    HC[x].ch=c;
    HC[x].len=i;
    for(int numb=0;numb<20;numb++)
        HC[x].code[numb]='\0';
    
    for(--i,j=0;i>=0;--i,j++)
    {
        HC[x].code[j]=cd[i];
    }
}

/**************************将编码写入指定文件*************************/

void W_code_file(huffmancode HC,char *W_code_filename,char s[])
{
    FILE *fp;
    int temp;
    if((fp=fopen(W_code_filename,"w"))==NULL)
    {
        printf("Open file error!\n");
        exit(0);
    }
    printf("读入字符的编码为：");
    for(int numb=0;numb<n && s[numb]!='\0';numb++)
    {
    for(int i=1;i<=num;i++)
    {
        if(s[numb]==HC[i].ch)
    	{
            temp=HC[i].len;
            for(int j=0;j<temp;j++)
    		{
                fputc(HC[i].code[j],fp);
                printf("%c",HC[i].code[j]);
    		}
    	}
    }
    }
    printf("\n");
    printf("已成功将编码写入文件%s\n",W_code_filename);
    fclose (fp);
}

/**从文件中读取哈夫曼编码并存入指定文件中**/
void read_coding(huffmancode HC)
{
     FILE *fp;
     char str[n],*p,filename1[15],filename2[15];
     int i,j,k=0,cs;
     static char cd[n+1];
     Printf("请输入编码文件：");
     scanf("%s",filename1);
     if((fp=fopen(filename1,"r"))==NULL)
     {
         printf("canot open %s!\n",filename1);
        exit(0);
     }
     while(!feof(fp))
     {
         cs=0;
         for(i=0;i<num && cs==0 && !feof(fp);i++)
         {
             cd[i]=' ';cd[i+1]='\0';
             cd[i]=fgetc(fp);
             for(j=1;j<=num;j++)
                 if(strcmp(HC[j].code,cd)==0)
                 {
                     str[k]=HC[j].ch;
            		 k++;
                     cs=1;break;
                 }//end of if
         }//end of for
     }//end of while
     fclose (fp);
     str[k]='\0';
     p=str;
/***********************将译文写入文件代码段********************************/
     FILE *fp1;
    i=0;
    printf("\n\n请输入将翻译过来的字符存入文件的文件名：");
        scanf("%s",filename2);
    if((fp1=fopen(filename2,"w"))==NULL)
    {
        printf("canot open %s!",filename2);
        exit(0);
    }//end of if
    printf("\n翻译过来的字符串为：");
    while(*p!='\0')
    {
        fputc(*p,fp1);
        putchar(*p);
        p++;
    }//end of while
    printf("\n\n             成功将译文写入文件：%s\n\n",filename2);
    fclose(fp1);
}

/***************主函数************/
void main()
{
    int si=0;
    while(1)
    {
    char shuru[n],str[27],filename[15];
    int cnt[27],ch;
    huffmancode HC;
    HTNode *root;
    if((root=(HTNode *)malloc(sizeof(HTNode)))==NULL)
    {
        printf("memory error!\n");
        exit(0);
    }
    root->weight=0;
    root->val=NULL;
    root->parent=NULL;
    root->lchild=NULL;
    root->rchild=NULL;
    show();
    if(si==1)printf("\n\n       您的输入有误，请从新在1 和0 中选择！\n\n");
    printf("    请输入您的选择：");
    scanf("%d",&ch);
    if(ch==1)
    {
        printf("请输入读入文件的文件名：");
       scanf("%s",filename);
       read_char(filename,shuru);
       num=jsq(shuru,cnt,str);
       printf("       ***********************读入的字符及频率如下*******************\n");
       for(int i=1;i<=num;i++)
            printf("       *      字符:%c  的频率为:%3d              *\n",str[i],cnt[i]);             printf("**************************************************************\n");
    creatH_Tree(root,cnt, str,HC);
    char W_code_filename[20];
    printf("\n\n请输入要写入编码文件的文件名：");
    scanf("%s",W_code_filename);
    W_code_file(HC,W_code_filename,shuru);
    for(int j=1;j<=num;j++)
     {
          printf("   字符：%c 的编码为：%s\n",HC[j].ch,HC[j].code);
     }
    read_coding(HC);
    }
    else if(ch==0)
    {
        printf("\n\n                     谢谢使用，欢迎下次使用！^_^\n\n");
        exit(0);
    }
    else 
    {
    	
        system("cls");
        si=1;
        continue;
    }
    system("pause");
        system("cls");
    }
}