fano.cpp

编码程序

#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>
#include<string.h>
#include<math.h>
#define N 30
int n;//实际数据量
typedef struct
{
  float p;
  char  code[10];
  int length;
}SCandP;
SCandP scp[N];  //定义结构体数组存储字符相关信息。

void init();//声明部分
void quickSort(SCandP *,int,int); 
int  endidx(SCandP [], int, int);
void encode( int, int, char* );
void output();

int index = 0;

int arrmark = 0;

void main()
{
	init();//读入数据，初始化存储空间
	int i;
   for(i=0; i<n; ++i)
   {
      scp[i].code[0] = '\0';
   }
   int begin = 0;
   int over = n-1;
 quickSort(scp, begin, over);//排序后的结构放入 scp[size]

  encode(begin, over, "");

  printf("===================================\n");
  printf("Fano Encode:          chy\n");
  printf("probability - FanoCode\n");
  output();
}

void init()
{
	int i;
	printf("n=");
	scanf("%d",&n);
	printf("input the possibility value of n symbols:\n");
	for( i=0;i<n;i++)
	{
		scanf("%f",&scp[i].p);
	}
}
void quickSort(SCandP a[], int l, int r)//定义部分
{
  SCandP temp, pivot;
  if(l >= r)    return;
  int i = l, j = r + 1;
  pivot= a[l];
  while(1)
  {
   do
   {
     i = i + 1;
   }while(a[i].p > pivot.p);

   do
   {
     j =j - 1;
   }while(a[j].p < pivot.p);

   if(i >= j)  break;
   temp = a[i];
   a[i] = a[j];
   a[j] = temp;
  }//while(1)
  a[l] = a[j];
  a[j] = pivot;
  quickSort(a, l, j-1); // 对左段排序
  quickSort(a, j+1, r); // 对右段排序
}

int endidx( SCandP arTP[],int index, int endex)
{
  int i;
  double accp=0;
  double divd,d;
  for(i=index;i<=endex;i++) accp+=arTP[i].p;
  divd=accp/2.0;
  i=index;
  accp=arTP[i].p;
  while((d=accp-divd)<0)
  {
   i++;
   accp+=arTP[i].p;
  }
  if(arTP[index].p>divd)  return index;
  else
  {
    if(d<=arTP[i].p/2.0) ;
    else i--;
    return i;
  }
}

void encode(int head, int end,  char* string)
{
   int i;
//    printf(" %d %d \n",head,end);
   if(head>end)  return;
   for(i=head;i<=end;i++)
     strcat(scp[i].code,string);
  //     printf("haha");
   if(head>=end)  return;
  //    printf(" 3.1");
   encode( head, endidx(scp,head,end),"0" );
   encode( endidx(scp,head,end)+1,end,"1" );
}

void output()
{
  for(int i=0;i<n;i++)
  {
    printf("%-15.2f",scp[i].p);
    printf("%s \n",scp[i].code);
	scp[i].length=strlen(scp[i].code);
//	printf("%d \n",scp[i].length);
  }
  printf("===================================\n");
  float H;      //信源符号的信息熵
	H=0;
	for(i=0;i<n;i++)
	{
		H=H+scp[i].p*log(scp[i].p)/log(2);
	}
	H=-H;
	float K;          //平均信息率
	K=0;
	for(i=0;i<n;i++)
	{
		K=K+scp[i].p*scp[i].length;
	}
	float yita;
	yita=H/K;
	printf("Calculate the efficiency of fano:\n");
	printf("yita=%f\n",yita);
}