//Write a c program to
perform Huffman coding.
#include<stdio.h>
#include<conio.h>
void
main()
{
intn,i,j,t,total,min,oc[10],sym[10],c[20];
floatflotot,foc[10],pr[10];
clrscr();
printf("enter the num of
symboles you want to enter:");
scanf("%d",&n);
printf("\nenter the
symabols:");
for(i=0;i<n;i++)
{
scanf("\n%d",&sym[i]);
}
printf("\nenter the occurences
for symboles:");
for(i=0;i<n;i++)
{
scanf("\n%d",&oc[i]);
}
//sorting
for(i=0;i<n-1;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(oc[j]<oc[min])
{
min=j;
}
}
t=oc[i];
oc[i]=oc[min];
oc[min]=t;
}
//probablity
total=0;
for(i=0;i<n;i++)
{
total=total+oc[i];
}
flotot=(float)total;
for(i=0;i<n;i++)
{
foc[i]=(float)oc[i];
}
for(i=0;i<n;i++)
{
pr[i]=(foc[i]/flotot);
}
//huffman tree
printf("\nSymbol\tprobability\tCode");
switch(n)
{
case 1:
c[0]=0;
break;
case 2:
i=0;
c[i]=1;
c[i+1]=0;
break;
case 3:
c[0]=1;
for(i=1;i<=(n+1);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n]);
i=i--;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n-1],c[n-2]);
i--;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n-1],c[n-3]);
break;
case 4:
c[0]=1;
for(i=1;i<=(n+2);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n+1]);
i=i--;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n],c[n-1]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n],c[n-2],c[n-3]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n],c[n-2],c[n-4]);
break;
case 5:
c[0]=1;
//printf("code:%d",c[0]);
for(i=1;i<=(n+3);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n+2]);
i=i--;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n+1],c[n]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n+1],c[n-1],c[n-2]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d",sym[i],pr[i],c[n+1],c[n-1],c[n-3],c[n-4]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d",sym[i],pr[i],c[n+1],c[n-1],c[n-3],c[n-5]);
break;
case 6:
c[0]=1;
//printf("code:%d",c[0]);
for(i=1;i<=(n+4);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n+3]);
i=i--;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n+2],c[n+1]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n+2],c[n],c[n-1]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d",sym[i],pr[i],c[n+2],c[n],c[n-2],c[n-3]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d",sym[i],pr[i],c[n+2],c[n],c[n-2],c[n-4],c[n-5]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d",sym[i],pr[i],c[n+2],c[n],c[n-2],c[n-4],c[n-n]);
break;
case 7:
c[0]=1;
for(i=1;i<=(n+5);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n+4]);
i=i--;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n+3],c[n+2]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n+3],c[n+1],c[n]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d",sym[i],pr[i],c[n+3],c[n+1],c[n-1],c[n-2]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d",sym[i],pr[i],c[n+3],c[n+1],c[n-1],c[n-3],c[n-4]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d",sym[i],pr[i],c[n+3],c[n+1],c[n-1],c[n-3],c[n-5],c[n-6]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d",sym[i],pr[i],c[n+3],c[n+1],c[n-1],c[n-3],c[n-5],c[n-n]);
break;
case 8:
c[0]=1;
for(i=1;i<=(n+6);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n+5]);
i=i-1;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n+4],c[n+3]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n+4],c[n+2],c[n+1]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d",sym[i],pr[i],c[n+4],c[n+2],c[n],c[n-1]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d",sym[i],pr[i],c[n+4],c[n+2],c[n],c[n-2],c[n-3]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d",sym[i],pr[i],c[n+4],c[n+2],c[n],c[n-2],c[n-4],c[n-5]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d",sym[i],pr[i],c[n+4],c[n+2],c[n],c[n-2],c[n-4],c[n-6],c[n-7]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d",sym[i],pr[i],c[n+4],c[n+2],c[n],c[n-2],c[n-4],c[n-6],c[n-n]);
break;
case 9:
c[0]=1;
for(i=1;i<=(n+7);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n+6]);
i=i-1;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n+5],c[n+4]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n+5],c[n+3],c[n+2]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d",sym[i],pr[i],c[n+5],c[n+3],c[n+1],c[n]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d",sym[i],pr[i],c[n+5],c[n+3],c[n+1],c[n-1],c[n-2]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d",sym[i],pr[i],c[n+5],c[n+3],c[n+1],c[n-1],c[n-3],c[n-4]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d",sym[i],pr[i],c[n+5],c[n+3],c[n+1],c[n-1],c[n-3],c[n-5],c[n-6]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d%d",sym[i],pr[i],c[n+5],c[n+3],c[n+1],c[n-1],c[n-3],c[n-5],c[n-7],c[n-8]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d%d",sym[i],pr[i],c[n+5],c[n+3],c[n+1],c[n-1],c[n-3],c[n-5],c[n-7],c[n-n]);
break;
case 10:
c[0]=1;
for(i=1;i<=(n+8);i++)
{
if(c[i-1]==0)
{
c[i]=1;
}
else
{
c[i]=0;
}
}
i=n-1;
printf("\n%d\t%.2f\t\t%d",sym[i],pr[i],c[n+7]);
i=i-1;
printf("\n%d\t%.2f\t\t%d%d",sym[i],pr[i],c[n+6],c[n+5]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+3]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+2],c[n+1]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+2],c[n],c[n-1]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+2],c[n],c[n-2],c[n-3]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+2],c[n],c[n-2],c[n-4],c[n-5]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+2],c[n],c[n-2],c[n-4],c[n-6],c[n-7]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+2],c[n],c[n-2],c[n-4],c[n-6],c[n-8],c[n-9]);
i--;
printf("\n%d\t%.2f\t\t%d%d%d%d%d%d%d%d%d",sym[i],pr[i],c[n+6],c[n+4],c[n+2],c[n],c[n-2],c[n-4],c[n-6],c[n-8],c[n-n]);
break;
}
getch();
}
