huffman.cpp

实现huffman编码的功能

#include "stdio.h"
#include "conio.h"
#include "string.h"
#include "stdlib.h"
#include "malloc.h"
typedef struct code
{
    char c;
    int weight;
}CODE;
CODE s[128]; /*用于存储记录过的字符数*/
typedef struct node
{
    char c;
    int tag;          /*是否有双亲的标志*/
    int weight;
    char code[100];         /*该字符的huffman编码*/
    struct node *parents,*lc,*rc;
}NODE;
NODE *head;
char filename1[40]={0};                 /*源文件名*/
char filename2[40]={0};                 /*统计结果文件名称*/
char filename3[40]={0};                 /*压缩文件名称*/
char filename4[40]={0};                 /*解压后源文件名称*/
int n;
/*保存统计结果保存函数*/
void save(void)
{
    int i;
    FILE *fp;
    printf("\nPlease input the huffcode file path:");
    gets(filename2);
    if((fp=fopen(filename2,"wt"))==NULL)
    {
        printf("Can't open creat the huffcode file!\nPlease cheak the flie!");
        getch();
        return ;
    }
    n=0;
    for(i=1;i<=128;i++)
    {
        if(s[i].weight==0)
            continue;
        n++;                    /*不存在的元素不输出*/
    }
    fprintf(fp,"%d",n);
    s[10].c='^'; /*因为回车在输出到huffcode中后不便于后面的读取，所以用英文中几乎不出现的字符 ^ 来代替会回车*/
    s[32].c='~'; /*空格在读取字符时会出错，用～代替*/
    s[9].c=127;
    for(i=1;i<=128;i++)
    {
        if(s[i].weight==0)
            continue;          /*过滤权值非0字符*/
        fprintf(fp," %c %d",s[i].c,s[i].weight);
     }
    fclose(fp);
}
/*建树模块*/
NODE *BuildTree(void)
{
    int min1=32767,min2=32767,i,j;
    NODE *p1,*p2;
    char cd[20];
    FILE *fp;
    
    if((fp=fopen(filename2,"rt"))==NULL)
    {
        printf("Sorry!the code file can't be opened!\nPlease check it!");
        exit(0) ;
    }
    fscanf(fp,"%d",&n);
    head=(NODE *)malloc(2*n*sizeof(NODE));/*多申请一个空间，0号空间空留不用，构成一个结构体数组head[2*n]*/                   /*n为字符的种类*/
    for(i=1;i<=n;i++)
    {
        fscanf(fp," %c %d",&head[i].c,&head[i].weight);    /* %c和%d之前的空格不能少，因为是格式化输出的*/
        head[i].tag=0; /*无双亲*/
        head[i].parents=NULL;
        head[i].lc=NULL;
        head[i].rc=NULL;
        head[i].code[0]='\0';
    }
    for(i=1;i<=3;i++)
    {                     /*还原被代替的字符*/
        if(head[i].c==127)
            head[i].c=9;
        else if (head[i].c=='^')
            head[i].c='\n';
        else if(head[i].c=='~')
            head[i].c=' ';
        else   ;
    }
    for(i=1;i<n;i++)     /*n个字符操作n－1次*/
    {
        min1=min2=32767;
        p1=NULL;p2=NULL;
        for(j=1;j<n+i;j++)
            if((head[j].weight<min1)&&(head[j].tag==0))
            {
                min2=min1;
                p2=p1;
                min1=head[j].weight;
                p1=&head[j];
            }
            else if((head[j].weight<min2)&&(head[j].tag==0))
            {
                min2=head[j].weight;
                p2=&head[j];
            }                      /*找出了最小p1的次小的p2*/
        p1->tag=1;
        p2->tag=1;
        head[n+i].weight=p1->weight+p2->weight;
        p1->parents=&head[n+i];
        p2->parents=&head[n+i];
        head[n+i].parents=NULL;
        head[n+i].lc=p1;
        head[n+i].rc=p2;
        head[n+i].tag=0;
    }
    if(n==1)                              /*一种字符构不成huffman树，定义其代码*/
    {
        head[1].code[0]='0';
        head[1].code[1]='\0';
    }
    else
    {
        for(i=1;i<=n;i++)
        {
            j=19;
            cd[j]='\0';
            p1=&head[i];
            for(p2=p1->parents;p2!=NULL;p2=p1->parents)
            {
                if(p1==p2->lc)
                    cd[--j]='0';
                else
                    cd[--j]='1';                     /*用栈来存储编码实现对其顺序的调整*/
                p1=p2;
            }
            strcpy(head[i].code,&cd[j]);
        }
    }
    fclose(fp);
    return head;             /*申请了2n个空间，0号不用最后一个是2n－1*/
}
/*文件校验函数*/
void CheckSymbol(void)
{
    FILE *fp,*fp1;
    char ch1,ch2;
    int  num=0;
    if((fp=fopen(filename1,"rt"))==NULL)
    {
        printf("Can't open the source file!");
        getch();    
        return ;
    }
    if((fp1=fopen(filename4,"rt"))==NULL)
    {
        printf("Can't open the restore file!");
        getch();
        return ;
    }
    while(feof(fp)==0||feof(fp1)==0)
    {
        ch1=fgetc(fp);
        ch2=fgetc(fp1);
        if(ch1==ch2)
         {   num++; continue; }
        else
        {
            printf("\nThe %d character is difficult!",num);
            printf("\nPlease check it!");
            getch();
            return ;
        }
    }
    printf("\nSucceeful!The file decoded is right!");
    getch();
}
/*统计主函数*/
void CountSymbol(void)
{
    FILE *fp;
    char t;
    int i;
    for(i=0;i<=128;i++)
    {
        s[i].c=i;
        s[i].weight=0;
    }
    printf("\nPlease input the file's path and file name:");
    getchar();
    gets(filename1);
    if((fp=fopen(filename1,"rt"))==NULL)
    {
        printf("Can't open the source file!\nPlease cheak the flie!");
        getch();
        return ;
    }
    t=0;
    while(feof(fp)==0) /*0时文件未结束*/
    {
        t=fgetc(fp);
        s[t].weight++;       /*按照ASCII码表的对应位置统计权值*/
     }
    save();
    fclose(fp);
    printf("\nThe code has been saved succeful!");
    getch();
}
/*编码模块*/
void Encode(NODE *head)
{
    FILE *fp,*fpc;
    char t,cd[20];
    int i;
    fp=fopen(filename1,"rt");                        /*遍历比较得到huffman编码*/
    fpc=fopen("encode.txt","wt");        /*生成中间0 1 代码文件*/
    while(feof(fp)==0)
    {
        t=fgetc(fp);
        for(i=1;i<=n;i++)
            if(t==head[i].c)
            {
                strcpy(cd,head[i].code);
                fprintf(fpc,"%s",cd);
            }
    }
    fclose(fp);
    fclose(fpc);
}
/*7位压缩模块*/
void Compress(void)
{
    int n=0,i=6;
    long  num=0;                 /*统计0 1 个数*/
    unsigned char ch=0,ch1;
    FILE *fp,*fp1;
    if((fp=fopen("encode.txt","rt"))==NULL)
    {
        printf("Can't open the code file!\nPlease cheak the flie!");
        getch();
        return ;
    }
    printf("\nplease input the compressed file path and name:");
    getchar();
    gets(filename3);
    if((fp1=fopen(filename3,"wt"))==NULL)
    {
        printf("Can't open the compressed file!\nPlease cheak the file!");
        getch();
        return ;
    }
    while(feof(fp)==0)
    {
        num++;
        ch1=fgetc(fp);           /*统计出了 0 1 个数*/
    }                            /*遍历文件得到字符的个数，保存在filename3文件中*/
    num--;
    rewind (fp);                 /*将文件指针移回文件的头*/
    fprintf(fp1,"%ld",num);
    ch1='\\';
    fprintf(fp1,"%c",ch1);      /*注意输出的格式*/
    while(feof(fp)==0)
    {
        ch1=fgetc(fp);           /*将数字0和1转换为字符0和1*/
        if(ch1==255)             /*因为ch1只可能是结束标志或0 、1*/
        {
            fputc(ch,fp1);
            break;
        }   
        ch1-=48;
        ch1<<=i--;               /*从文件中读取字符*/
        ch=ch|ch1;               /*与0取或将7个数字合并未一个*/
        n++;
        if(n%7==0)
        {
            if(ch==7)           /*屏对文件有影响的字符*/
                ch=128;         /*7号显示不出，8号后退一个吃掉前一个字符*/
            else if (ch==8)     /*13号显示不出，10号是换行，26号文件结束字符*/
                ch=129;
            else if (ch==9)
                ch=130;
            else if (ch==10)
                ch=131;
            else if (ch==13)
                ch=132;
            else if (ch==26)
                ch=133;
            else  ;                 
            fputc(ch,fp1);
            n=0;i=6;ch=0;   /*初始化*/
        }
    }
    fclose(fp1);
    fclose(fp);
}
/*解码模块*/
void Decode(NODE *head,int n)
{
    FILE *fp,*fp1;
    char t='0';          /*随便赋初值*/
    NODE *p1,*p0;
    p1=p0=&head[2*n-1];
    if((fp=fopen("d:\\encode.txt","rt"))==NULL)
    {
        printf("Can't open the compress file!");
        getch();
        return ;
    }
    if((fp1=fopen(filename4,"wt"))==NULL)
    {
        printf("Can't open the decode file!");
        getch();
        return ;
    }
    while(feof(fp)==0)
    {
        t=fgetc(fp);        /*只有一个节点是构不成huffman树*/
        if(t=='0')
        {
            if(p1->lc==NULL)
                fprintf(fp1,"%c",p1->c);
            else
            {               
                p1=p1->lc;                  
                if(p1->lc==NULL&&p1->rc==NULL)
                {
                    fprintf(fp1,"%c",p1->c);
                    p1=p0;
                }
            }
        }
        else if(t=='1')
        {
            p1=p1->rc;
            if(p1->rc==NULL&&p1->lc==NULL)
            {
                fprintf(fp1,"%c",p1->c);
                p1=p0;
            }
        }
    }
    fclose(fp);
    fclose(fp1);
}
/*解7位压缩模块*/
void Uncompress(void)
{
    FILE *fp,*fp1;
    long num;
    int i;
    unsigned char ch,exp;      /*在tc环境下默认有符号，但在vc环境下默认有符号*/
    if((fp=fopen(filename3,"rt"))==NULL)
    {
        printf("Can't open file!\nPlease cheak the flie!");
        getch();
        exit(1);
    }
    if((fp1=fopen("d:\\encode.txt","wt"))==NULL)
    {
        printf("Can't open file!\nPlease cheak the flie!");
        getch();
        exit(1);
    }
    fscanf(fp,"%ld",&num);  /*注意格式*/
    fscanf(fp,"%c",&ch);    /*取出'\'*/
    while(feof(fp)==0) /*只读出有用字符,而且解决了中断问题！！*/
    {
        ch=fgetc(fp);
        if(ch==255)   /*这块有问题，最后11111111时会出错！*/
            break;
        if(ch==128)           /*屏蔽对文件有影响的ASCII码*/
            ch=7;         /*7号显示不出，8号后退一个吃掉前一个字符，9号tab多时出错*/
        else if (ch==129)     /*13号显示不出，10号是换行，26号文件结束字符*/
            ch=8;
        else if (ch==130)
            ch=9;
        else if (ch==131)
            ch=10;
        else if (ch==132)
            ch=13;
        else if (ch==133)
            ch=26;
        else  ;
        for(i=1;i<8;i++)
        {
            exp=ch;  /*寄存*/
            exp<<=i;
            exp>>=7;         
            exp+=48;           /*将从文件中读出的字符中的有效数字还原成数字*/
            if(num!=0)      /*输出的总的有效的位数够后就不进行输出*/
            {
                num--;     /*只将有效的字符输出*/
                fputc(exp,fp1);
            }
        }
    }
    fclose(fp1);
    fclose(fp);
}
/*压缩率计算模块*/
void Rate(void)
{
    FILE *fp,*fp1;
    char ch=1;
    float num=0.0,num1=0.0;
    float weight,weight1,rate;
    fp=fopen(filename1,"rt");
    fp1=fopen(filename3,"rt");
    while(feof(fp)==0)
    {
        ch=fgetc(fp);          /*比较源文件和压缩后的文件*/
        num++;
    }
    num--;  /*减去末尾结束标志*/
    weight=num/1024;
    while(feof(fp1)==0)
    {
        ch=fgetc(fp1);
        num1++;
    }
    num1--;/*减去末尾结束标志*/
    weight1=num1/1024;
    rate=weight1/weight;
    printf("\nThe source file weight is %.4f Kb!",weight);
    printf("\nThe compressed file weight is %.4fKb!",weight1);
    printf("\nThe compresse rete is %.2f %!",rate*100);
    getch();
}
/*编码压缩主函数*/
void EncodeSymbol(void)
{
    NODE *head=NULL;
    head=BuildTree();       /*得到了huffman树的首地址*/
    Encode(head);
    Compress();
/*    remove("d:\\encode.txt"); */    /*将中间文件删除*/
    printf("\nThe file has been compressed!");
    printf("\nIt was saved in %s",filename2);
    Rate();
}
/*解码压缩主函数*/
void DecodeSymbol(void)
{
    NODE *head=NULL;
    printf("\nPlease input the code file path:");
    getchar();
    gets(filename2);
    printf("\nPlease input the compressed file path:");
    gets(filename3);
    printf("\nPlease input the restored file path:");
    gets(filename4);
    head=BuildTree();
    Uncompress();
    Decode(head,n);
/*    remove("d:\\encode.txt");  *//*删除中间文件*/
    printf("\nThe file has been restored!");
    printf("\nIt is saved in the %s!",filename4);
    getch();
}
/*主函数*/
void main(void)
{
    int choice;
    do
    {
        printf("\n\n\n\n\n\n\n");
        printf("                           This is a huffman code  \n             ");
        printf("\n                          1: Count character frequency");
        printf("\n                          2: Encode the file");
        printf("\n                          3: Decode the file");
        printf("\n                          4: Check the result");
        printf("\n                          0: exit\n\n");
        printf("\n          Please input your chose:");
        scanf("%d",&choice);
        while(choice<0||choice>4)
        {
            printf("          Sorry !The choice is wrong!\n          Please input it again:");
            scanf("%d",&choice);
        }
        switch(choice)
        {
            case 1:  CountSymbol();     break;   /*计数模块*/
            case 2:  EncodeSymbol();    break;   /*编码模块*/
            case 3:  DecodeSymbol();    break;   /*解码模块*/
            case 4:  CheckSymbol();     break;   /*校验模块*/
            case 0:  exit(0);            /*正常退出*/
         }
    }while(1);
}