#include
#include
#include
struct node
{
	char sym;
	float pro;
	int arr[40];
	int top;
}s[40];
typedef struct node node;
int main()
{
	char *p,tchar,str[60],symbol[30]={""};
        char find[]={'a','b','c','d','e','f','g','h','i','j','k','l','m','n'
,'o','p','q','r','s','t','u','v','w','x','y','z'};
	int flag,start,temp,*v,count[3],scount[30]={0},slen,i,len=0,numlen,j,fchar[30]={0},k,flen;
	float *vf;
	void shannon(int l,int h,node s[]);
	clrscr();
	numlen=strlen(find);
	printf("enter string :");
	scanf("%[^\n]",str);
	len=strlen(str);
	i=0;
	while(i{
	 for(j=0;j {
		if(str[i]==find[j])
		{
		 fchar[j]++;         //increment count for character
		}
	 }
	i++;
	}
	str[i]='\0';
	i=0;
	for(k=0;k{
	 if(fchar[k]!=0)
	 {
	   symbol[i]=find[k];
	   scount[i]=fchar[k];
	   i++;
	 }
	}
	slen=i;
	for(i=0;i{
	  for(j=0;j  {
		  if(scount[i]>scount[j])
		  {
		   //swap value
		   temp=scount[i];
		   scount[i]=scount[j];
		   scount[j]=temp;
		   //swap char
		   tchar=symbol[i];
		   symbol[i]=symbol[j];
		   symbol[j]=tchar;
		  }
	  }
	}
	printf("\nsymbol count\n");
	for(j=0,i=slen-1;j{
	  printf("%c      %d\n",symbol[j],scount[j]);
	  *(vf+j)=(float)scount[j]/100;
	  s[i].sym=symbol[j];
	  s[i].pro=*(vf+j);
	}
	for(i=0;is[i].top=-1;
	shannon(0,slen-1,s);
	//code bit logic
	printf("---------------------------------------------------------------");
	printf("\n\n\n\tSymbol\tProbability\tCode");
	printf("---------------------------------------------------------------");
	printf("\n\n\n\tSymbol\tProbability\tCode");
	for(i=slen-1;i>=0;i--)
	{
		printf("\n\t%c\t%f\t",s[i].sym,s[i].pro);
		for(j=0;j<=s[i].top;j++)
		printf("%d",s[i].arr[j]);
	}
	printf("\n---------------------------------------------------------------");
	getch();
	return 0;
}
void shannon(int l,int h,node s[])
{
	float pack1=0,pack2=0,diff1=0,diff2=0;
	int i,d,k,j;
	if((l+1)==h || l==h || l>h)
	{
		if(l==h || l>h)
		return;
		s[h].arr[++(s[h].top)]=0;
		s[l].arr[++(s[l].top)]=1;
		return;
	}
	else
	{
		for(i=l;i<=h-1;i++)
		pack1=pack1+s[i].pro;
		pack2=pack2+s[h].pro;
		diff1=pack1-pack2;
		if(diff1< 0)
		diff1=diff1*-1;
		j=2;
		while(j!=h-l+1)
		{
			k=h-j;
			pack1=pack2=0;
			for(i=l;i<=k;i++)
			pack1=pack1+s[i].pro;
			for(i=h;i>k;i--)
			pack2=pack2+s[i].pro;
			diff2=pack1-pack2;
			if(diff2< 0)
			diff2=diff2*-1;
			if(diff2>=diff1)
			break;
			diff1=diff2;
			j++;
		}
		k++;
		for(i=l;i<=k;i++)
		s[i].arr[++(s[i].top)]=1;
		for(i=k+1;i<=h;i++)
		s[i].arr[++(s[i].top)]=0;
		shannon(l,k,s);
		shannon(k+1,h,s);
	}
}