#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);
}
}