C Program for Huffman code Generation

C Program for Huffman code Generation

#include<stdio.h>
#include<stdlib.h>
void createhufman(void)  ;
void initialize();
int arrange(void);
void setpriority();
void taketwoleast();
void sort_character(void);
void sort_freq(int);
void post_order(struct node *);
void push(char);
void pop();
struct node
{
char c;
char code[100];
int freq;
int selected;
struct node *lchild;
struct node *rchild;
};
char str[100];

char stack[100]={'\0'};
int top=-1;
struct node *tree[100]={NULL};

void main()
{

printf("Enter a string?\n");
gets(str);
createhufman( );
if(tree[0]->lchild==NULL && tree[0]->rchild==NULL)
printf("huffman code for %c =0",tree[0]->c);
else
post_order(tree[0]);

}
void createhufman()
{
int n;
initialize();

setpriority();

n=arrange();
sort_freq(n);
while(n!=1)
{

taketwoleast();
sort_freq(n);
n=arrange();

}


}

void initialize()
{
int i;
struct node *temp;

for(i=0;i
{

if(str[i]!=' '|| str[i]!='\t')
{
temp=(struct node *)malloc(sizeof(struct node));
temp->c=str[i];
temp->freq=0;
temp->lchild=NULL;
temp->rchild=NULL;
tree[i]=temp;
}
}


}




void setpriority()
{
int count=1,i=0;
sort_character();
while(tree[i]!=NULL)
{
if(tree[i]->c==tree[i+1]->c)
count++;
else
{
tree[i]->selected=1;
tree[i]->freq=count;
count=1;
}
i++;
}
}


void sort_character()
{
struct node *temp;
int i=0,j;
for(i=0;i
{

       for(j=0;j
       {
if(tree[j]->c > tree[j+1]->c)
{
temp=tree[j];
tree[j]=tree[j+1];
tree[j+1]=temp;
}


       }

}
}

int arrange()
{
int i=0,j,k ;
while(tree[i]!=NULL)
{
if(tree[i]->selected!=1)
{
j=i;

while(tree[j]!=NULL)
{
tree[j]=tree[j+1];

j++;
}
tree[j]=NULL;
i--;
}
i++;


}

return(i);
}



void taketwoleast()
{

struct node *temp;
temp=(struct node *)malloc(sizeof(struct node));
temp->c='\0';
temp->freq=tree[0]->freq+tree[1]->freq;

tree[0]->selected=0;
tree[1]->selected=0;
temp->lchild=tree[0];

temp->rchild=tree[1];
temp->selected=1;
tree[0]=temp;
}


void sort_freq(int n)
{
struct node *temp;
int i=0,j;
for(i=0;i
{

       for(j=0;j
       {
if(tree[j]->freq > tree[j+1]->freq)
{
temp=tree[j];
tree[j]=tree[j+1];
tree[j+1]=temp;
}


       }

}
}
void post_order(struct node *temp)
{
if(temp!=NULL)
{
push('0');
post_order(temp->lchild);
pop();
push('1');
post_order(temp->rchild);
pop();
if(temp->lchild==NULL && temp->rchild==NULL )
{
printf("hufman code for %c =",temp->c);
printf("%s\n" ,stack);
}
}
}

void push(char s)
{
stack[++top]=s;
}
void pop()
{
stack[top--]='\0';
}
Sample Output

C program for Converting NFA to DFA

C program for Converting  NFA to DFA

#include<stdio.h>
#include<stdlib.h>
struct node
{
int st;
struct node *link;
};
struct node1
{

int nst[20];
};

void insert(int ,char, int);
int findalpha(char);
void findfinalstate(void);
int insertdfastate(struct node1);
int compare(struct node1,struct node1);
void printnewstate(struct node1);
static int set[20],nostate,noalpha,s,notransition,nofinal,start,finalstate[20],c,r,buffer[20];
int complete=-1;
char alphabet[20];
static int eclosure[20][20]={0};
struct node1 hash[20];
struct node * transition[20][20]={NULL};
void main()
{
int i,j,k,m,t,n,l;
struct node *temp;
struct node1 newstate={0},tmpstate={0};

printf("Enter the number of alphabets?\n");
printf("NOTE:- [ use letter e as epsilon]\n");
printf("NOTE:- [e must be last character ,if it is present]\n");
printf("\nEnter No of alphabets and alphabets?\n");
scanf("%d",&noalpha);
getchar();
for(i=0;i<noalpha;i++)
{

alphabet[i]=getchar();
getchar();
}
printf("Enter the number of states?\n");
scanf("%d",&nostate);
printf("Enter the start state?\n");
scanf("%d",&start);
printf("Enter the number of final states?\n");
scanf("%d",&nofinal);
printf("Enter the final states?\n");
for(i=0;i<nofinal;i++)
scanf("%d",&finalstate[i]);
printf("Enter no of transition?\n");

scanf("%d",&notransition);
printf("NOTE:- [Transition is in the form–> qno alphabet qno]\n",notransition);
printf("NOTE:- [States number must be greater than zero]\n");
printf("\nEnter transition?\n");


for(i=0;i<notransition;i++)
{


scanf("%d %c%d",&r,&c,&s);
insert(r,c,s);

}
for(i=0;i<20;i++)
{
for(j=0;j<20;j++)
hash[i].nst[j]=0;
}
complete=-1;
i=-1;
printf("\nEquivalent DFA.....\n");
printf(".......................\n");

printf("Trnsitions of DFA\n");

newstate.nst[start]=start;
insertdfastate(newstate);
while(i!=complete)
{
i++;
newstate=hash[i];
for(k=0;k<noalpha;k++)
{
c=0;
for(j=1;j<=nostate;j++)
set[j]=0;
for(j=1;j<=nostate;j++)
{
l=newstate.nst[j];
if(l!=0)
{
temp=transition[l][k];
while(temp!=NULL)
{
if(set[temp->st]==0)
{
c++;
set[temp->st]=temp->st;
}
temp=temp->link;


}
}
}
printf("\n");
if(c!=0)
{
for(m=1;m<=nostate;m++)
tmpstate.nst[m]=set[m];

insertdfastate(tmpstate);

printnewstate(newstate);
printf("%c\t",alphabet[k]);
printnewstate(tmpstate);
printf("\n");
}
else
{
printnewstate(newstate);
printf("%c\t", alphabet[k]);
printf("NULL\n");
}

}
  }
printf("\nStates of DFA:\n");
for(i=0;i<=complete;i++)
printnewstate(hash[i]);
printf("\n Alphabets:\n");
for(i=0;i<noalpha;i++)
printf("%c\t",alphabet[i]);
 printf("\n Start State:\n");
  printf("q%d",start);
printf("\nFinal states:\n");
findfinalstate();

}
int insertdfastate(struct node1 newstate)
{
int i;
for(i=0;i<=complete;i++)
{
if(compare(hash[i],newstate))
return 0;
}
complete++;
hash[complete]=newstate;
return 1;
}
int compare(struct node1 a,struct node1 b)
{
int i;


for(i=1;i<=nostate;i++)
{
if(a.nst[i]!=b.nst[i])
return 0;
}
return 1;


}

void insert(int r,char c,int s)
{
       int j;
       struct node *temp;
       j=findalpha(c);
       if(j==999)
       {
printf("error\n");
exit(0);
       }
       temp=(struct node *) malloc(sizeof(struct node));
       temp->st=s;
       temp->link=transition[r][j];
       transition[r][j]=temp;
}

int findalpha(char c)
{
int i;
for(i=0;i<noalpha;i++)
if(alphabet[i]==c)
return i;

return(999);


}


void findfinalstate()
{
int i,j,k,t;

for(i=0;i<=complete;i++)
{
for(j=1;j<=nostate;j++)
{
for(k=0;k<nofinal;k++)
{
if(hash[i].nst[j]==finalstate[k])
{
printnewstate(hash[i]);
printf("\t");
j=nostate;
break;
}
}
}
}
}


void printnewstate(struct node1 state)
{
int j;
printf("{");
for(j=1;j<=nostate;j++)
{
if(state.nst[j]!=0)
printf("q%d,",state.nst[j]);
}
printf("}\t");

}

Sample Output

C Program for Converting ε(epsilon) NFA to NFA[ updated due to some missing code while pasting to blog]

C Program for Converting  ε NFA to NFA

#include<stdio.h>
#include<stdlib.h>
struct node
{
        int st;
        struct node *link;
};

void findclosure(int,int);
void insert_trantbl(int ,char, int);
int findalpha(char);
void findfinalstate(void);
void unionclosure(int);
void print_e_closure(int);
static int set[20],nostate,noalpha,s,notransition,nofinal,start,finalstate[20],c,r,buffer[20];
char alphabet[20];
static int e_closure[20][20]={0};
struct node * transition[20][20]={NULL};
void main()
{
           int i,j,k,m,t,n;

           struct node *temp;
           printf("enter the number of alphabets?\n");
           scanf("%d",&noalpha);
           getchar();
           printf("NOTE:- [ use letter e as epsilon]\n");

          printf("NOTE:- [e must be last character ,if it is present]\n");

          printf("\nEnter alphabets?\n");
          for(i=0;i<noalpha;i++)
         {

                  alphabet[i]=getchar();
                  getchar();
        }
        printf("Enter the number of states?\n");
        scanf("%d",&nostate);
        printf("Enter the start state?\n");
        scanf("%d",&start);
        printf("Enter the number of final states?\n");
        scanf("%d",&nofinal);
        printf("Enter the final states?\n");
        for(i=0;i<nofinal;i++)
                scanf("%d",&finalstate[i]);

         printf("Enter no of transition?\n");

        scanf("%d",&notransition);

        printf("NOTE:- [Transition is in the form--> qno   alphabet   qno]\n",notransition);

        printf("NOTE:- [States number must be greater than zero]\n");

        printf("\nEnter transition?\n");

        for(i=0;i<notransition;i++)

        {

                scanf("%d %c%d",&r,&c,&s);

                insert_trantbl(r,c,s);

        }

        printf("\n");

        for(i=1;i<=nostate;i++)

        {

                c=0;

                for(j=0;j<20;j++)

                {

                              buffer[j]=0;

                               e_closure[i][j]=0;

                }

                findclosure(i,i);

        }

        printf("Equivalent NFA without epsilon\n");

        printf("-----------------------------------\n");

        printf("start state:");

        print_e_closure(start);

        printf("\nAlphabets:");

        for(i=0;i<noalpha;i++)

                  printf("%c ",alphabet[i]);

        printf("\n States :" );

        for(i=1;i<=nostate;i++)

                  print_e_closure(i);

        printf("\nTnransitions are...:\n");

        for(i=1;i<=nostate;i++)

        {

                  for(j=0;j<noalpha-1;j++)

                 {

                          for(m=1;m<=nostate;m++)

                                        set[m]=0;

                          for(k=0;e_closure[i][k]!=0;k++)

                          {

                                    t=e_closure[i][k];

                                   temp=transition[t][j];

                                   while(temp!=NULL)

                                  {

                                             unionclosure(temp->st);

                                            temp=temp->link;

                                   }

                         }

                        printf("\n");

                        print_e_closure(i);

                        printf("%c\t",alphabet[j]   );

                        printf("{");

                        for(n=1;n<=nostate;n++)

                        {

                                     if(set[n]!=0)

                                             printf("q%d,",n);

                        }

                         printf("}");

                }

        }

        printf("\n Final states:");

        findfinalstate();

}

void findclosure(int x,int sta)

{

            struct node *temp;

            int i;

           if(buffer[x])

                     return;

             e_closure[sta][c++]=x;

            buffer[x]=1;

             if(alphabet[noalpha-1]=='e' && transition[x][noalpha-1]!=NULL)

                {

                             temp=transition[x][noalpha-1];

                             while(temp!=NULL)

                            {

                                         findclosure(temp->st,sta);

                                         temp=temp->link;

                             }

                }

  }

void insert_trantbl(int r,char c,int s)

{

           int j;

           struct node *temp;

            j=findalpha(c);

          if(j==999)

          {

                     printf("error\n");

                    exit(0);

          }

         temp=(struct node *) malloc(sizeof(struct node));

         temp->st=s;

         temp->link=transition[r][j];

         transition[r][j]=temp;

}

int findalpha(char c)

{

            int i;

            for(i=0;i<noalpha;i++)

                   if(alphabet[i]==c)

                          return i;

                return(999);

}

void unionclosure(int i)

{

              int j=0,k;

             while(e_closure[i][j]!=0)

             {

                      k=e_closure[i][j];

                      set[k]=1;

                      j++;

             }

}

void findfinalstate()

{

            int i,j,k,t;

            for(i=0;i<nofinal;i++)

           {

                      for(j=1;j<=nostate;j++)

                      {

                              for(k=0;e_closure[j][k]!=0;k++)

                                {

                                         if(e_closure[j][k]==finalstate[i])

                                        {

                                                 print_e_closure(j);

                                        }

                               }

                      }

             }

  }

void print_e_closure(int i)

{

        int j;

        printf("{");

        for(j=0;e_closure[i][j]!=0;j++)

                        printf("q%d,",e_closure[i][j]);

         printf("}\t");

}

Sample Output