/**
*
* Fano Code
*
* 黄益星
*
* 2011.4.13
*
*说明 从D盘文件Fano.text读入字符，然后进行编码，输出
*/
#include<stdio.h>
#include<math.h>
#include<stdlib.h>
#define N 300
struct event {
int n;//第几个数
float x;//权值
int code[N];//编码
int low; //几位编码
};
char a[100000]={0};
int qq=0,coun=0;//qq是统计文本中有多少个不同的字符，coun是统计文本中有多少个字符
FILE *fp2;
struct event A[N+1];
//建立文本函数
void creat_save()
{
int i=0;
char ch;
FILE *fp1;
fp1=fopen("D:\\Fanotext.txt","r");
printf("please input text\n");
ch=fgetc(fp1);
while(ch!=EOF)
{
a[i]=ch;
i++;
coun++;
ch=fgetc(fp1);
}
fprintf(fp2,"总字符数coun=%d",coun);
printf("get here 1\n");
}
int s[256]={0};//s[0]到s[255]分别对应字母的ASCII码由0到255的统计个数
void count()
{
int j;
int i=0,f=0;
char m;
while(i<coun)//
{
m=0;
for(j=0;a[i]!=m;j++)
m++;
s[m]++;
i++;
}
fprintf(fp2," \n");
while(f!=255)
{
if(s[f]!=0)
{
A[qq].n=f; //记录ASCII码
A[qq].x=s[f];
qq++;
}
f++;
}
for(i=0;i<qq;i++)
{
// A[qq].x=A[qq].x/coun;
A[qq].low=0;
}
fprintf(fp2,"不同字符总数qq=%d\n",qq);
printf("get here 2\n");
}
/************************************************************************************************************************/
void inputcode(struct event *a,int b)/*input code*/
{
a->code[a->low]=b;
(a->low)++;
}
void outcode(struct event a)/*output code*/
{
int i;
for(i=0;i<a.low;i++)
fprintf(fp2,"%d",a.code[i]);
}
double getsum(int h,int t,struct event a[])/*get sum*/
{
int i=h;
double sum=0.0;
for(i=h;i<=t;i++)
{
sum=sum+a[i].x;
}
return sum;
}
int getbreakpoint(struct event a[],int h,int t)/*all right*/
{
int n,t1;
double f[N+1],temp=0.0;
for(n=h;n<t;n++)
{
f[n]=fabs(getsum(h,n,a)-getsum(n+1,t,a));
}
temp=f[h];
t1=h;
for(n=h;n<t;n++)
{
if(f[n]<temp)
{
temp=f[n];
t1=n;
}
}
return t1;
}
void group(int h,int t,struct event a[])
{
int i,breakpoint,zero=0,one=1;
if(t==h+1)
{
inputcode(&a[h],zero);
inputcode(&a[t],one);
}
else
if(t==h)
;
else
{
breakpoint=getbreakpoint(a,h,t);
for(i=h;i<=breakpoint;i++)
{
inputcode(&a[i],zero);
}
for(i=breakpoint+1;i<=t;i++)
{
inputcode(&a[i],one);
}
group(h,breakpoint,a);
group(breakpoint+1,t,a);
}
}
void sort(struct event a[])
{
int i,j;
struct event t;
for(i=1;i<qq;i++)
for(j=1;j<qq-i+1;j++)
if(a[j].x<a[j+1].x)
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
void main()
{
int i;
int h=1,t=N;
float avlen=0; //平均码长
fp2=fopen("D:\\Fano黄益星.txt","w+"); //运行结果的记录文本
/*input data*/
creat_save();
printf("get here 0");
/*initialize*/
count();
sort(A);
printf("get here 3");
group(h,t,A);
printf("get here 4");
/*Out put result*/
for(i=1;i<=qq;i++)
{
fprintf(fp2,"字符%c:ASCII码%d:频率%.4f:编码",A[i].n,A[i].n,A[i].x);
outcode(A[i]);
fprintf(fp2,"\n");
avlen+=A[i].x*A[i].low;
}
avlen=avlen/coun;
fprintf(fp2,"****\n平均码长=%f\n费诺编码成功！\n****\n",avlen);
fclose(fp2);
}
