#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]; /*用于存儲記錄過的字符數(shù)*/
typedef struct node
{
    char c;
    int tag;          /*是否有雙親的標(biāo)志*/
    int weight;
    char code[100];         /*該字符的huffman編碼*/
    struct node *parents,*lc,*rc;
}NODE;
NODE *head;
char filename1[40]={0};                 /*源文件名*/
char filename2[40]={0};                 /*統(tǒng)計結(jié)果文件名稱*/
char filename3[40]={0};                 /*壓縮文件名稱*/
char filename4[40]={0};                 /*解壓后源文件名稱*/
int n;
/*保存統(tǒng)計結(jié)果保存函數(shù)*/
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中后不便于后面的讀取，所以用英文中幾乎不出現(xiàn)的字符 ^ 來代替會回車*/
    s[32].c='~'; /*空格在讀取字符時會出錯，用～代替*/
    s[9].c=127;
    for(i=1;i<=128;i++)
    {
        if(s[i].weight==0)
            continue;          /*過濾權(quán)值非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號空間空留不用，構(gòu)成一個結(jié)構(gòu)體數(shù)組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)                              /*一種字符構(gòu)不成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';                     /*用棧來存儲編碼實現(xiàn)對其順序的調(diào)整*/
                p1=p2;
            }
            strcpy(head[i].code,&cd[j]);
        }
    }
    fclose(fp);
    return head;             /*申請了2n個空間，0號不用最后一個是2n－1*/
}
/*文件校驗函數(shù)*/
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();
}
/*統(tǒng)計主函數(shù)*/
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時文件未結(jié)束*/
    {
        t=fgetc(fp);
        s[t].weight++;       /*按照ASCII碼表的對應(yīng)位置統(tǒng)計權(quán)值*/
     }
    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;                 /*統(tǒng)計0 1 個數(shù)*/
    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);           /*統(tǒng)計出了 0 1 個數(shù)*/
    }                            /*遍歷文件得到字符的個數(shù)，保存在filename3文件中*/
    num--;
    rewind (fp);                 /*將文件指針移回文件的頭*/
    fprintf(fp1,"%ld",num);
    ch1='\\';
    fprintf(fp1,"%c",ch1);      /*注意輸出的格式*/
    while(feof(fp)==0)
    {
        ch1=fgetc(fp);           /*將數(shù)字0和1轉(zhuǎn)換為字符0和1*/
        if(ch1==255)             /*因為ch1只可能是結(jié)束標(biāo)志或0 、1*/
        {
            fputc(ch,fp1);
            break;
        }   
        ch1-=48;
        ch1<<=i--;               /*從文件中讀取字符*/
        ch=ch|ch1;               /*與0取或?qū)?個數(shù)字合并未一個*/
        n++;
        if(n%7==0)
        {
            if(ch==7)           /*屏對文件有影響的字符*/
                ch=128;         /*7號顯示不出，8號后退一個吃掉前一個字符*/
            else if (ch==8)     /*13號顯示不出，10號是換行，26號文件結(jié)束字符*/
                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);        /*只有一個節(jié)點是構(gòu)不成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環(huán)境下默認(rèn)有符號，但在vc環(huán)境下默認(rèn)有符號*/
    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號文件結(jié)束字符*/
            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;           /*將從文件中讀出的字符中的有效數(shù)字還原成數(shù)字*/
            if(num!=0)      /*輸出的總的有效的位數(shù)夠后就不進(jìn)行輸出*/
            {
                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--;  /*減去末尾結(jié)束標(biāo)志*/
    weight=num/1024;
    while(feof(fp1)==0)
    {
        ch=fgetc(fp1);
        num1++;
    }
    num1--;/*減去末尾結(jié)束標(biāo)志*/
    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();
}
/*編碼壓縮主函數(shù)*/
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();
}
/*解碼壓縮主函數(shù)*/
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();
}
/*主函數(shù)*/
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;   /*計數(shù)模塊*/
            case 2:  EncodeSymbol();    break;   /*編碼模塊*/
            case 3:  DecodeSymbol();    break;   /*解碼模塊*/
            case 4:  CheckSymbol();     break;   /*校驗?zāi)K*/
            case 0:  exit(0);            /*正常退出*/
         }
    }while(1);
}