huffman编码压缩

#include"stdio.h"
#include"stdlib.h"
typedef struct tree1   //结构体定义结点
{
        float data;        //存放字符出现的概率
        char ch;          //存放字符
        struct tree1 *next,*left,*right;
}*tree,tree1;
/////////////////////生成文件
void createfile(char *filename)
{
    char c,choose;
        FILE *fp;
        printf("\n是要对已存在的文件进行压缩(y)还是要新建一个文件(n)?\n");
        fflush(stdin);
        scanf("%c",&choose);
        if(choose=='n')
        {
            printf("请输入要创建的文件名:\n");
            scanf("%s",filename);
            printf("输入文件内容，'*'做为结束标志\n");
            fflush(stdin);
            if((fp=fopen(filename,"w"))!=NULL)
                {
                   scanf("%c",&c);
                   while(c!='*')
                   {
                           fputc(c,fp);
                          scanf("%c",&c);
                   }
                   fclose(fp);
                } else printf("\n创建文件失败%s\n",filename);
        }
          else
          {
                  printf("\n请输入文件名：\n");
                  scanf("%s",filename);
          }
}
//////////////////////////以下对文件进行编码
void stat(tree head,char *filename)  //统计各个字符出现的概率
{
        FILE *fp;
        char c;
        tree p,q;
        p=head;
        if((fp=fopen(filename,"rb"))!=NULL)
        {
                while((c=getc(fp))!=EOF)
                {
          while(p->next&&p->next->ch!=c)
                           p=p->next;
                  if(p->next)
                          p->next->data+=1;
                     else
                         {
                                 q=(tree)malloc(sizeof(tree1));
                 q->left=NULL;
                                 q->right=NULL;
                                 q->ch=c;
                                 q->data=1;
                                 q->next=p->next;
                                 p->next=q;
                         }
          p=head;
                }
                fclose(fp);
        }
        else printf("\n打开文件%s失败\n",filename);
}
tree insert_order(tree head,tree q)    //插入排序
{
        tree p;
        p=head;
        while(p->next&&p->next->data<q->data)
                p=p->next;
        q->next=p->next;
        p->next=q;
        return(head);
}
tree huffman_tree(tree head)         //构造huffman树
{
   tree q,p;
   p=head->next;
   q=p->next;
   p->next=NULL;
   while(q)                     //整体先进行插入排序
   {
      p=q->next;
      head=insert_order(head,q);
          q=p;
   }
   while(head->next->next)     //当链表剩下多于两个的数据就可以合成一棵树
   {
      p=(tree)malloc(sizeof(tree1));
      p->left=head->next;
      p->right=head->next->next;
      p->data=p->right->data+p->left->data;
          p->ch='\0';
      head->next=head->next->next->next;
          head=insert_order(head,p);
   }
   return(p);
}
char char_code(tree root,char ch,char *a,int i)    //根据产生的huffman树对单个字符进行编码
{
   tree p;
   char c;
   p=root;
   if(p->left->ch==ch)
  {
           a[i]='0';
           a[i+1]='\0';
           return(p->left->ch);
   }
   if(p->right->ch==ch)
   {
           a[i]='1';
           a[i+1]='\0';
           return(p->right->ch);
   }
   if(p->left->ch=='\0')
   {
           c=char_code(p->left,ch,a,i+1);
       if(c==ch)
           {
                   a[i]='0';
               return(c);
           }
   }
   if(p->right->ch=='\0')
   {
           c=char_code(p->right,ch,a,i+1);
       if(c==ch)
       {   
               a[i]='1';
               return(c);
           }
   }
   return('\0');
}

void filehead(char *filename,tree root,char *a,char i)    //创建文件头信息
{
        FILE *fp;
        tree p;
        char j;
        p=root;
        if(p->ch)
        {
                if((fp=fopen(filename,"a"))!=NULL)
                {       
            fputc(i,fp);
                        for(j=0;j<i;j++)
                                fputc(a[j],fp);
                        fputc(p->ch,fp);
                        fclose(fp);
                }else printf("\n创建文件%s失败\n",filename);
                return;
        }
        a[i]='0';
        filehead(filename,p->left,a,i+1);
        a[i]='1';
        filehead(filename,p->right,a,i+1);
}
void code_file(tree root,char *filename,char *codefilename,char *headfilename)   //通过调用char_code对整个文件进行压缩编码
{
   FILE *fp1,*fp2;
   char ch,a[50],b[50];
   int blength=0;
   if((fp1=fopen(filename,"rb"))!=NULL)
   {
          if((fp2=fopen(codefilename,"a"))!=NULL)
          {
          while((ch=getc(fp1))!=EOF)
                  {
             if(ch==char_code(root,ch,a,0))
                         {
                                 int i=0,k;
                                 while(a[i])
                                         b[blength++]=a[i++];
                                 b[blength]='\0';
                             k=blength/8;
                                 for(i=0;i<k;i++)    //每8位放入文件中
                                 {
                                         int code=0;
                                         int temp=128,j;
                                         for(j=0;j<8;j++)
                                         {
                        code+=(b[i*8+j]-48)*temp;
                                                temp=temp/2;
                                         }
                                         fputc(code,fp2);
                                 }
                                 blength=blength%8;
                                 for(i=0;i<blength;i++)
                                         b[i]=b[i+k*8];
                         }
                  }
                  if(blength>0)
                  {
                                char code=0;
                                int temp=128,j;
                            for(j=0;j<blength;j++)
                                {
                     code+=b[j]*temp;
                                            temp=temp/2;
                                }
                                fputc(code,fp2);
                  }
                  fclose(fp2);
                  if((fp2=fopen(headfilename,"a"))!=NULL)
                  {
                          ch=0;
                          fputc(ch,fp2);
                          fputc(blength,fp2);      //将最后一段编码的位数放入头文件中
                          fclose(fp2);
                  }else printf("\n创建文件%s失败\n",headfilename);
          }
          else printf("\n创建文件%s失败\n",codefilename);
          fclose(fp1);
   }
   else printf("\n打开文件%s失败\n",filename);
}
void createcodefile(tree root,char *filename)        //生成密文
{
         char codefilename[50],headfilename[50],a[50];
         FILE *fp;
     printf("\n请输入要创建的压缩文件名：\n");
     scanf("%s",codefilename);
         printf("\n请输入要创建的密钥文件名：\n");
     scanf("%s",headfilename);
     if((fp=fopen(codefilename,"w"))!=NULL)
                fclose(fp);
          else printf("\n创建文件%s失败\n",codefilename);
         if((fp=fopen(headfilename,"w"))!=NULL)
                fclose(fp);
          else printf("\n创建文件%s失败\n",headfilename);
         filehead(headfilename,root,a,0);
     code_file(root,filename,codefilename,headfilename);
}
////////////////以下对文件进行译码
int create_huffman(char *headfilename,tree root)    //根据密钥文件创建huffman树
{
        FILE *fp;
        char ch;
        tree p=root,q;
        if((fp=fopen(headfilename,"r"))!=NULL)
        {
       while((ch=getc(fp))!=EOF)
           {
            if(ch==0)
                                break;
                    int i,length=ch;
                        for(i=0;i<length;i++)
                        {
                                ch=getc(fp);
                                if(ch=='0')
                                {
                                        if(p->left==NULL)
                                        {
                       q=(tree)malloc(sizeof(tree1));
                                           q->ch='\0';
                                           q->left=NULL;
                                           q->right=NULL;
                                           p->left=q;
                                        }
                                        p=p->left;
                                }
                                else
                                {
                     if(p->right==NULL)
                                        {
                       q=(tree)malloc(sizeof(tree1));
                                           q->ch='\0';
                                           q->left=NULL;
                                           q->right=NULL;
                                           p->right=q;
                                         }
                                         p=p->right;
                                }
                        }
            ch=getc(fp);
                        p->ch=ch;
                        p=root;
           }
       ch=getc(fp);
           fclose(fp);
           return(ch);
        }else printf("\n打开文件%s失败\n",headfilename);
         return(8);
}
void create_decode_file(tree root,char *codefilename,char *decodefilename,int length)
{
   tree p=root;                  //经过译码生成源文件
   FILE *fp1,*fp2;
   int temp,i,code,ch1,ch2;
   if((fp1=fopen(codefilename,"rb"))!=NULL)
   {
           if((fp2=fopen(decodefilename,"wb"))!=NULL)
           {   
                   ch1=getc(fp1);
               while((ch2=getc(fp1))!=EOF)
                   {
               temp=128;
                       for(i=0;i<8;i++)
                           {
                  code=ch1/temp;
                              ch1=ch1%temp;
                              temp=temp/2;
                                  if(code)
                     p=p->right;
                                    else p=p->left;
                  if(p->ch)
                                  {
                                          fputc(p->ch,fp2);
                                          p=root;
                                  }
                           }
                           ch1=ch2;
                   }
                   temp=128;
                   if(length==0)
                           length=8;
                   for(i=0;i<length;i++)
                   {
                           code=ch1/temp;
                           ch1=ch1%temp;
                           temp=temp/2;
                           if(code)
                                   p=p->right;
                             else p=p->left;
                                 if(p->ch)
                                 {
                                         fputc(p->ch,fp2);
                                         p=root;
                                 }
                   }
                   fclose(fp2);
           }else printf("\n创建文件%s失败\n",decodefilename);
           fclose(fp1);
   }else printf("\n打开文件%s失败\n",codefilename);
}
void decode()      //对文件解压
{
        char codefilename[50],headfilename[50],decodefilename[50];
        int length;
        tree root;
        printf("\n请输入压缩文件名\n");
        scanf("%s",codefilename);
        printf("\n请输入密钥文件名\n");
        scanf("%s",headfilename);
        printf("\n请输入要生成的文件名\n");
        scanf("%s",decodefilename);
    root=(tree)malloc(sizeof(tree1));
        root->left=NULL;
        root->right=NULL;
        root->ch='\0';
        length=create_huffman(headfilename,root);
        create_decode_file(root,codefilename,decodefilename,length);
}
void main()
{
    char filename[50],choose,exit='n';
        tree head,root;
        head=(tree)malloc(sizeof(tree1));
        head->next=NULL;
        head->right=NULL;
        head->left=NULL;
        while(exit=='n')
        {
                printf("\n请选择编码(c)或者解码(d):\n");
                fflush(stdin);
                scanf("%c",&choose);
                if(choose=='c')
                {
               createfile(filename);
               stat(head,filename);
               root=huffman_tree(head);
               createcodefile(root,filename);
                }
                else decode();
                printf("\n要退出吗?(y/n):\n");
                fflush(stdin);
                scanf("%c",&exit);
        }
}