#include<string.h>
#include<stdlib.h>
#include<stdio.h>
int m,s1,s2;
FILE *fp1;
FILE *fp2;
FILE *fp3;
FILE *fp4;
FILE *fp5;
int j=0; long int s=0;int left;
int num[128]={0};char ch=48;
char filename[50];


typedef struct {
	char name;
    int weight;
    int parent,lchild,rchild;
}HTNode,*HuffmanTree;  HuffmanTree HT;
typedef struct {
	int weight;
	char name;
}codeweight;   codeweight cw[128];
typedef char **HuffmanCode;  HuffmanCode HC;

void Select(HuffmanTree HT,int g,int &s1,int &s2)
{
  int j,k,m,n;
    for(k=1;k<=g;k++)
     {
		if(HT[k].parent==0)
		{  s1=k;  break;}
     }
   for(j=1;j<=g;j++)
   {
    if((HT[j].weight<HT[k].weight)&&(HT[j].parent==0))
       s1=j;
   }
     for(m=1;m<=g;m++)
      {
        if((HT[m].parent==0)&&(m!=s1))
		{s2=m;break;}
      }
      for(n=1;n<=g;n++)
       if((HT[n].weight<HT[m].weight)&&(HT[n].parent==0)&&(n!=s1)) s2=n;
}
//編碼
void HuffmanCoding(HuffmanTree &HT, HuffmanCode &HC, codeweight *cw, int n)
{
	 int i,m,s1=0,s2=0;
     int c,f,start;
     char *cd;
   if (n<=1) return;
   m = 2 * n - 1;
   HT = (HuffmanTree)malloc((m+1) * sizeof(HTNode));
    for (i=1; i<=n; i++)
    {
      HT[i].weight=cw[i-1].weight;
	  HT[i].name=cw[i-1].name;
      HT[i].parent=0;
      HT[i].lchild=0;
      HT[i].rchild=0;
    }
    for (i=n+1; i<=m; i++)
    {
      HT[i].weight=0;
      HT[i].parent=0;
      HT[i].lchild=0;
      HT[i].rchild=0;
    }
   for (i=n+1; i<=m; i++)
   {
     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 *));
   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));
     strcpy(HC[i],&cd[start]);
   }
free(cd);
}
//******************譯碼*****************************//
void HuffmanTran(HuffmanTree &HT,FILE *fp4,FILE *fp5,int n)
{
HuffmanTree p=HT+2*n-1;
char ch=48;
 while(1)
 {
   ch=fgetc(fp4);
   if(ch==EOF)break;
   if(ch=='0') p=HT+p->lchild;
       else if(ch=='1') p=HT+p->rchild;
    if(p->lchild==0&&p->rchild==0)
	   {
             //共n個(gè)權(quán)值中查找weigt的對(duì)應(yīng)碼
          	 fprintf(fp5,"%c",p->name);
			 p=HT+2*n-1;
       }
 }
 fclose(fp4);
 fclose(fp5);
}
 //-----函數(shù)---------





//統(tǒng)計(jì)源文件字符
void statistics_file () {                                                         
printf("請(qǐng)輸入要譯碼的文件名(例如e:\\source.txt)");
scanf("%s",filename);
if( (fp1=fopen(filename,"r"))==NULL )
{
printf("open source.txt fail!");
exit(0);
}
if( (fp2=fopen("e:\\statistics.txt","w+"))==NULL )
{
printf("create statistics.txt fail!");
fclose(fp1);
exit(0);
}
//---建樹并輸出赫夫曼編碼
   while(1)
  {
	 ch=fgetc(fp1);
	 if(ch==EOF){fseek(fp1,0,0);break;}
	 ++num[ch];
  }

  for(int i=0;i<128;i++)
  {
    if(num[i])
    {
	  fprintf(fp2,"%c %d\n",i,num[i]);
	  cw[j].name=i;cw[j].weight=num[i];
      ++j;
	}
  }
fclose(fp2); 
}                                                              
void  create_code() {                                                  
HuffmanCoding(HT,HC,cw,j);
        if((fp3=fopen("e:\\code.txt","w+"))==NULL )
             {
                printf("create code.txt fail!");
                exit(0);
             }
		for(int i=1;i <= j;i++)
            fprintf(fp3,"%c %s\n",cw[i-1].name,HC[i]);
        fclose(fp3);                                                       
}//二進(jìn)制壓縮編碼輸出
void   bin_code (){
fp4=fopen("e:\\source_code.txt","w+");
 ch=48;
 while(1)
 {
	 ch=fgetc(fp1);
	 if(ch==EOF)break;
	 for(int i=0;i<j;i++)
	    if(ch==cw[i].name)fputs(HC[i+1],fp4);
 }
fclose(fp1);
fclose(fp4);
fp1=fopen("e:\\bin_code","wb+");
fp4=fopen("e:\\source_code.txt","rb");
char bin=0; char c;
int t,x;
	 for(t=0;t<8;t++)
	 {
	    ch=fgetc(fp4);
		if(ch==EOF)
		{
                     for(left=0;left<t;left++)
                     if((bin&(1<<(7-left)))==0){c='0';fputc(c,fp1);}
                     else {c='1';fputc(c,fp1);}
		}
	    if(ch==EOF)break;
		if(ch==48)x=0;else x=1;
	     bin=bin|x<<(7-t);
	     ++s;
		 if(t==7){t=-1;fwrite(&bin,sizeof(char),1,fp1);bin=0; }
    }
fclose(fp1);
fclose(fp4);                                                              
}//二進(jìn)制編碼的譯碼輸出
void tran_code(){                                                 
 unsigned char a;
fp1=fopen("e:\\bin_code","rb");
fp4=fopen("e:\\pre2_code.txt","wb+");
for(int i=0;i<s/8;i++)
{
    fread(&a,sizeof(char),1,fp1);
    for(int t=0;t<8;t++)
    if((a&(1<<(7-t)))==0){ch='0';fputc(ch,fp4);}
    else {ch='1';fputc(ch,fp4);}
}
for(int t=0;t<left;t++)
fputc(fgetc(fp1),fp4);
fclose(fp1);
fclose(fp4);
fp4=fopen("e:\\pre2_code.txt","rb");
fp5=fopen("e:\\tran_code.txt","wb+");
HuffmanTran(HT,fp4,fp5,j);                                               
}


void main()
{
       unsigned char choice;
	   printf("***********哈夫曼編譯碼系統(tǒng)**********\n\n");
       printf("操作提示：\n");
       printf("           統(tǒng)計(jì)字符權(quán)值：<S>\n");
	   printf("           字符編碼輸出：<C>\n");
	   printf("           文件編碼輸出：<E>\n");
	   printf("           文件譯碼輸出：<D>\n");
	   printf("           退出應(yīng)用系統(tǒng)：<Q>\n");
	   while(choice!='Q')
	   {   
		   printf("\n請(qǐng)選擇相應(yīng)的操作：(生成文件默認(rèn)保存在E:\)");
		   scanf("%c",&choice);
		   if (choice==10)scanf("%c",&choice);
		   switch (choice)
		   {
		    case 'S':
				{ statistics_file ();printf("\n生成字符統(tǒng)計(jì)文件statistics.txt\n");}break;
            case 'C':
				{ create_code(); printf("\n生成字符編碼文件code.txt\n");}break;
            case 'E':
				{ bin_code();printf("\n生成文件編碼文件source_code.txt二進(jìn)制壓縮編碼文件bin_code\n"); }break;
			case 'D':
				{ tran_code();printf("\n生成文件譯碼文件tran_code.txt\n");}break;
			case 'Q':
			      break;
			default :
                printf("輸入有誤，請(qǐng)重新選擇！\n");
		   }
	   }
}