#include<stdio.h> //带缓冲的标准输入输出
#include<stdlib.h> //包含了的C语言标准库函数
#include<malloc.h>  // 动态存储分配函数头文件
#include<string.h>  //  C语言里面关于字 符数组的函数 定义的头文件
#define MAX 5000   //预处理指令 #define 和符号常量
typedef struct   
{   
    int weight;   
    int parent,lchild,rchild;   
    char code;   
}hufftree;   
typedef char * huffcode;


void tongji(char zimu[],int w1[],int*n1)
{FILE*fp;
char ch;
int i,n=*n1;
for(i=0;i<100;i++)                        //初始化
w1[i]=0;
if ((fp=fopen("source.txt","r+"))==NULL)//打开source.txt文件  
//fopen("source.txt","r+")指以只读方式打开source.txt文件。fp是一个返回值，为指针。fp==NULL 是说操作失败
{
    printf("Can not open\n");
    exit(0);
}
ch=fgetc(fp);                            //读取一个字符
while(ch!=-1)
{for(i=0;zimu[i]!=ch;i++)
    if(i==n){zimu[i]=ch;n++;w1[i]++;break;}//读取了新字符
if(zimu[i]==ch)w1[i]++;                        //读取了已有字符
ch=fgetc(fp);
}
*n1=n;
for(i=0;i<n;i++)
printf("%c   %d\n",zimu[i],w1[i]);            //输出字母 频率
fclose(fp);
}


void select(hufftree *p,int j,int *s)
{   int i,m,n,mid,t;                       
    hufftree *q;   
    m=n=MAX;   
    for(i=0,q=p;i<j;i++,q++)   
       if(q->parent==0)   
       {  if(q->weight<m)   
       {     mid=m;  m=q->weight;  n=mid;   
             t=*s; *s=i; *(s+1)=t;   
       }
          else if(q->weight<n)   
          {      n=q->weight;  *(s+1)=i;}   
       }   
}

  
 void hcode(hufftree *ht,int *w,int n)  
{   
    int i,m,s[2];   
    hufftree *p;   
    m=2*n-1;   
    for(i=0,p=ht;i<n;i++,p++,w++)   //n个前结点初始化
    {  p->weight=*w;   
       p->parent=p->lchild=p->rchild=0;   
    }   
    for(;i<m;i++,p++)                //n个后结点初始化
       p->weight=p->parent=p->lchild=p->rchild=0;   
    for(i=n;i<m;i++)   
    {  select(ht,i,s);               //寻找较小两个数
       (ht+s[0])->parent=i;  (ht+s[1])->parent=i;   
       (ht+i)->code='*',(ht+i)->lchild=s[0];  (ht+i)->rchild=s[1];   
       (ht+i)->weight=(ht+s[0])->weight+(ht+s[1])->weight;   
    }   
}
 
void huffc(hufftree *ht,huffcode *hc,int n)   
{   char *cd;   
    int i,start,c,f;   
    cd=(char*)malloc(n*sizeof(char));   
    *(cd+n-1)='\0';   
    for(i=0;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*sizeof(char));   
       strcpy(*(hc+i),cd+start);   
    }   
    free(cd);   
}   


void zhuanzhi(char  zimu[],huffcode *hc,int n)
{
    FILE*in,*out;int i;char ch,jie='|';huffcode *r;
   if ((in=fopen("source.txt","r+"))==NULL)
{
    printf("Can not open\n");
    exit(0);
}
   if ((out=fopen("code.dat","wb+"))==NULL)
{
    printf("Can not open\n");
    exit(0);
}
ch=fgetc(in);
while(ch!=-1)
{
for(i=0,r=hc;i<n;i++,r++)
if(zimu[i]==ch){
fputs(*r,out);fputc(jie,out);break;}
ch=fgetc(in);
}
fclose(in);fclose(out);
}


void jiema(char  zimu[],huffcode *hc,int n)//解码
{
    char li[15],ch;int i=0,j=0,k=0;FILE*p,*q;huffcode *r;
if ((p=fopen("code.dat","r+"))==NULL)
{
    printf("Can not open\n");
    exit(0);
}
if ((q=fopen("target.txt","w+"))==NULL)
{
    printf("Can not open\n");
    exit(0);
}
ch=fgetc(p);
while(ch!=-1)
{
    if(ch!='|')li[k++]=ch;
    else{li[k]='\0';
        for(i=0,r=hc;i<n;i++,r++)
            if(strcmp(li,*r)==0)
            {fputc(zimu[i],q);
            k=0;
            }
        }   
ch=fgetc(p);
}
fclose(p);fclose(q);
}


void cmp()
{
    int i=0;FILE*p,*q;char ch,ci;
if ((p=fopen("source.txt","r+"))==NULL)
{
    printf("Can not open\n");
    exit(0);
}
if ((q=fopen("target.txt","r+"))==NULL)
{
    printf("Can not open\n");
    exit(0);
}
ch=fgetc(p);ci=fgetc(q);
while(ch!=-1&&ci!=-1)
{i++;
if(ch!=ci)
printf("第%d个不同分别是%c %c\n",i,ch,ci);
ch=fgetc(p);ci=fgetc(q);
}
fclose(p);fclose(q);
}


void main()
{    int n=0,m,i,*w,*p,nn;   
    hufftree *ht,*q;   
    huffcode *hc,*r;
    char zimu[100];int w1[100];
    tongji(zimu,w1,&n);nn=n;//统计每个字符出现的频率
printf("共计有%d个字符\n",n);
 m=2*n-1;
w=(int*)malloc(m*sizeof(int));   
ht=(hufftree*)malloc(m*sizeof(hufftree));
 for(i=0,p=w,q=ht;i<n;i++,p++,q++)//将统计信息传递   
    {   
        q->code=zimu[i];   
        *p=w1[i];      
    }   
hcode(ht,w,n);   
    hc=(huffcode*)malloc(m*sizeof(huffcode));   
    huffc(ht,hc,n);   
    printf("哈夫曼编码是:\n");   
    for(i=0,q=ht,r=hc;i<n;i++,q++,r++)   
       printf("%c  %s\n",q->code,*r);   
     zhuanzhi(zimu,hc,nn);
     jiema(zimu,hc,nn);
     cmp();
}