#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
#include <windows.h>
#include <ctype.h>
#include <malloc.h>

typedef struct{
    unsigned int weight;
    unsigned int parent,lchild,rchild;
}HTNode, *huffmantree;// 动态分配数组存储赫夫曼树

typedef char **huffmancode;// 动态分配数组存储赫夫曼编码表

int power(int i)
{
    int j,result=1;
    for(j=0;j<i;j++)
    {
        result*=2;
    }
    return result;
}

void write_file(char temp[],FILE *fp2)
{
    int i;
    unsigned char result=0;
    for(i=8;i>0;i--)
    {
        if(temp[8-i]!='0')
        {
            result+=power(i-1);
        }
    }
    strcpy(temp,temp+8);
}

void select(huffmantree HT, unsigned int i, unsigned int *s1, unsigned int *s2)
{// s1为最小的两个值中序号小的那个

    unsigned int j,temp;
    for(j=1;j<=i;j++)
    {
        if(HT[j].parent==0)
        {
            *s2=j;
            break;
        }
    }
    for(;j<=i;j++)
    {
        if(HT[j].parent==0 && j!=*s2)
        {
            *s1=j;
            break;
        }
    }
    for(j=1;j<=i;j++)
    {
        if(HT[j].parent==0 && HT[j].weight < HT[*s1].weight && *s2!=j)
        {
            *s1=j;
        }
    }
    for(j=1;j<=i;j++)
    {
        if(HT[j].parent==0 && HT[j].weight < HT[*s2].weight && *s1!=j)
        {
            *s2=j;
        }
    }
    if(*s1>*s2)
    {
        temp=*s1;
        *s1=*s2;
        *s2=temp;
    }
}


void huffmancoding(huffmantree &HT, huffmancode &HC,unsigned long int *w, unsigned int n)
{
    // w存放n个字符的权值(均>0),构造赫夫曼树HT,并求出n个字符的赫夫曼编码HC

    unsigned int s1,s2,start,c,f,i,m;// 0号单元未用
    huffmantree p;
    char *cd;
    if (n<=1)
    {
        return;
    }
    m=2*n-1;
    HT=(huffmantree)malloc((m+1)*sizeof(HTNode));//malloc 向系统申请分配指定size个字节的内存空间。
    for(p=HT+1,i=1; i<=n; ++i,++p,++w)
    {
        p->weight=*w;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }

    for(; i<=m; ++i,++p)
    {
        p->weight=0;
        p->parent=0;
        p->lchild=0;
        p->rchild=0;
    }

    for(i=n+1; i<=m; ++i)// 建赫夫曼树

    { // 在HT[1~i-1]中选择parent为0且weight最小的两个结点,其序号分别为s1和s2
        select(HT,i-1,&s1,&s2);
        HT[s1].parent=i;  HT[s2].parent=i;
        HT[i].lchild=s1;  HT[i].rchild=s2;
        HT[i].weight=HT[s1].weight+HT[s2].weight;
    }
      // 从叶子到根逆向求每个字符的赫夫曼编码
    HC=(huffmancode)malloc((n+1)*sizeof(char *));// 分配n个字符编码的头指针向量([0]不用
    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);// 释放工作空间
}


void main()
{
    char w[256]="\0";
    char temp[40]="\0";
    unsigned char len;
    unsigned long int count[256]={0},weight[256]={0},n=0,i=0;
    unsigned int q=0;
    unsigned long int *p;
    char filename[260]="\0",filename2[260]="\0",houzui[8]="\0";
    char *point;
    char colorplat[1024];
    FILE *fp,*fp2;
    huffmantree HT;
    huffmancode HC;

    BITMAPFILEHEADER bf;    //BMP文件头结构体   
    BITMAPINFOHEADER bi;    //BMP信息头结构体   
    //    打开文件   
    printf("input the file name ：");
    gets(filename);//从stdin流中读取字符串，直至接受到换行符或EOF时停止，并将读取的结果存放在str指针所指向的字符数组中。
    strcpy(filename2,filename);

    for(point=filename2+strlen(filename2); *point!='.'; point--);//文件名修改

    strcpy(houzui,point);
    strcpy(point,".shq");
    if((fp=fopen(filename,"rb"))==NULL)//fopen函数用来打开一个文件
    {
        printf("error\n");
        exit(1);
    }
    //读取信息头、文件头
    fread( &bf,sizeof(BITMAPFILEHEADER), 1, fp ); //把指针fp所指向的文件的头信息写入bf（地址）   
    fread( &bi,sizeof(BITMAPINFOHEADER), 1, fp );   
    if(bf.bfType != 0x4d42)           //校验图片类型
    {
        printf("文件非bmp格式 \n");
        exit(1);
    }
    if(bi.biBitCount<24)
    {   
        int tm;
        (int)tm=pow(2.,bi.biBitCount);
        fread(colorplat,4*tm,1,fp);
    }
    while(fread(&q,1,1,fp))
    {
        count[q]++;
    }
    fclose(fp);
    for(p=count;i<256;p++,i++)
    {
        weight[n++]=*p;
    }

    huffmancoding(HT,HC,weight,n);

    for(i=0,n=1;i<256;i++)
    {
        if(count[i]!=0)
        {
            printf("%d:  ",i);
            printf("%s\n",HC[n++]);
        }
    }
    if((fp=fopen(filename,"rb"))==NULL)
    { //只读打开或建立一个二进制文件，只允许读数据
        printf("error\n");
        exit(1);
    }
    if((fp2=fopen(filename2,"wb"))==NULL)
    { //只写打开或建立一个二进制文件，只允许写数据
        printf("error\n");
        exit(1);
    }
    fwrite( &bf,sizeof(BITMAPFILEHEADER), 1 ,fp2 );
    fwrite( &bi,sizeof(BITMAPINFOHEADER), 1, fp2 );
    if(bi.biBitCount<24)//调用套色板
    {   
        fwrite(colorplat,4*(int)pow(2.,bi.biBitCount),1,fp2);
    }
    fwrite(houzui,8,1,fp2);

    for(i=1;i<=256;i++)
    {
        len=strlen(HC[i]);
        fwrite(&len,1,1,fp2);
        fwrite(HC[i],len,1,fp2);
    }   
    fseek(fp,54L,0);//跳过文件头
    while(fread(&q,1,1,fp))
    {
        strcat(temp,HC[q+1]);
        while(strlen(temp)>=8)
        {
            write_file(temp,fp2);
        }
    }
    for(i=strlen(temp);i<8;i++)//编码长度<8的编码后面补'1'
    {
        temp[i]='1';
    }
    temp[i]='\0';
    write_file(temp,fp2);
    fclose(fp);
    fclose(fp2);

    system("pause");
}