C program for BFS traversal

#include<stdio.h>
#include<stdlib.h>
#define SIZE 100
int FRONT=-1,REAR=-1;
int A[SIZE];
void enq(int);
int deq();
main()
{
 int VISIT[20],adjmat[20][20];
 int n,i,j,v=0;
 printf("Enter the no of vertices\n");
 scanf("%d",&n);
 printf("Enter adjacency matrix\n");
 for(i=0;i<n;i++)
 {
  for(j=0;j<n;j++)
   scanf("%d",&adjmat[i][j]);
 }
 if (n<=0)
  printf("The graph is empty\n");
 else
 {
  printf("The BFS traversal is\n");
  for(i=0;i<n;i++)
  {
   VISIT[i]=0;
  }
  enq(v);
  while(FRONT!=-1 && REAR!=-1)
  {
   v=deq();
   if(VISIT[v]==0)
   {
    printf("\tv%d",v);
    VISIT[v]=1;
    for(i=0;i<n;i++)
    {
     if((adjmat[v][i]==1)&&(VISIT[i]==0))
      enq(i);
    }
   }
  }
 }
}
void enq(int n)
{
 if(REAR>=99)
  printf("Queue is full\n");
 else
 {
  if((REAR==-1)&&(FRONT==-1))
  {
   FRONT=0;REAR=0;
   A[REAR]=n;
  }
  else
  {
   REAR=REAR+1;
   A[REAR]=n;
  }
 }
}

int deq()
{
 int i;
 if((FRONT==-1)&&(REAR==-1))
 {
  printf("QUEUE IS EMPTY \n");
  return(-999);
 }
 else
 {
  i=A[FRONT];
  if(FRONT==REAR)
  {
   FRONT=-1;REAR=-1;
  }
  else
  {
   FRONT=FRONT+1;
  }
  return(i);
 }
}

Output

Quick sort

Quick sort

#include<stdio.h>
void quicksort(int,int);
int partition(int,int);
int a[100],n;
main()
{
 int i;
 printf("Enter limit \n");
 scanf("%d",&n);
 printf("Enter %d elements \n",n);
 for(i=0;i<n;i++)
  scanf("%d",&a[i]);
 printf("Before sorting \n");
 for (i=0;i<n;i++)
  printf("%d\t",a[i]);
 quicksort(0,n-1);
 printf("Afer sorting\n");
 for(i=0;i<n;i++)
  printf("%d\t",a[i]);
}
void quicksort(int lb,int ub)
{
 int newub;
 if (lb<ub)
 {
  newub=partition(lb,ub);
  quicksort(lb,newub-1);
  quicksort(newub+1,ub);
 }
}
int partition(int lb,int ub)
{
 int temp,down=lb,up=ub,pivot=a[lb];
 while (down<up)
 {
  while (pivot>=a[down] && down<=up)
   down=down+1;
  while (pivot<a[up])
   up=up-1;
  if (down<up)
  {
   temp=a[down];
   a[down]=a[up];
   a[up]=temp;
  }
 }
temp=a[lb];
a[lb]=a[up];
a[up]=temp;
return up;
}
 

Output

Dijkstra's Algorithm

Dijkstra's Algorithm

#include<stdio.h>
void dijkstra(int);
int search_min(int [100],int [100]);
int adjmat[100][100],n;
int  main()
{
int s,i,j;
printf("Enter number of vertices?\n");
scanf("%d",&n);
printf("enter adjacensy  matrix?\n");
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
scanf("%d",&adjmat[i][j]);
}
}
printf("Enter source vertex?\n");
scanf("%d",&s);
dijkstra(s);

}
void dijkstra(int s)
{
int set[100],length[100],path[100];
int i=0,j,complete;
while(i<n)
{
set[i]=0;
i++;
}
i=0;
while(i<n)
{
if(adjmat[s][i]==0)
{
length[i]=999;
path[i]=999;
}
else
{
length[i]=adjmat[s][i];
path[i]=s;
}
i++;
}
set[s]=1;
length[s]=0;
complete=0;
while(complete==0)
{
i=search_min(length,set);
set[i]=1;
j=0;
while(j<n)
{
if(set[j]==1)
j++;
else
{
if(adjmat[i][j]!=0)
{
if((length[i]+adjmat[i][j])<length[j])
{
length[j]=length[i]+adjmat[i][j];
path[j]=i;
}
}
j++;
}
}
complete=1;
i=0;
while(i<n)
{
if(set[i]==0)
{
complete=0;
break;
}
else
{
i++;
}
}
}
printf("source->dest\tpath\tlength\n");
for(i=1;i<n;i++)
{
printf("v%d->v%d\t\t",s,i);
j=i;
while(j!=s)
{
printf("v%d-",j);
j=path[j];
}
       printf("v%d\t\t%d\n",s,length[i]);

}
}

int search_min(int length[100],int set[100])
{
int min=999;
int i=-1,ind=-1;
for(i=0;i<n;i++)
{
if(set[i]==0)
{
if(min>length[i])
{
min=length[i];
ind=i;
}
}
}
return ind;
}


Output

C program for infix expression to postfix expression and postfix expression evaluation

C program for infix expression to postfix expression and postfix expression evaluation

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
void push1(char);
char pop1(void);
int operand(char);
int priority(char);
void push2(float);
float pop2(void);
float findval(char);
char expr[100];
char variable[100];
float value[100];
char stack1[100],c;
int top1=-1;
int top2=-1;
char postfix[100];
int nv;
float stack2[100];
float val,val1,val2;
main()
{
 int i,j,l,p1,p2,flag;
 printf("Enter the no. of variables\n");
 scanf("%d",&nv);
 printf("Enter the variable names\n");
 getchar();
 for(i=0;i<nv;i++)
 {
  scanf("%c",&variable[i]);
  getchar();
 }
 printf("enter the values of variables\n");
 for(i=0;i<nv;i++)
 {
  printf("%c=?",variable[i]);
  scanf("%f",&value[i]);
 }
 printf("enter the infix expression\n");
 scanf("%s",expr);
 l=strlen(expr);
 expr[l]=')';
 expr[l+1]='\0';
 push1('(');
 i=0;
 j=0;
 while(top1>=0)
 {
  if(operand(expr[i]))
  {
   postfix[j++]=expr[i];
  }
  else if(expr[i]=='(')
  {
   push1('(');
  }
  else if(expr[i]==')')
  {
   c=pop1();
   while(c!='(')
   {
    postfix[j++]=c;
    c=pop1();
   }
  }
  else
  {
   p2=priority(expr[i]);
   p1=priority(stack1[top1]);
   while(p1>=p2)
   {
    postfix[j++]=pop1();
    p1=priority(stack1[top1]);
   }
   push1(expr[i]);
  }
  i++;
 }
 postfix[j]='\0';
 printf("Postfix expression=%s",postfix);
 printf("\n");
 i=0;
 for(i=0;postfix[i]!='\0';i++)
 {

  if(operand(postfix[i]))
  {
   val=findval(postfix[i]);
   push2(val);
  }
  else
  {
   val1=pop2();
   val2=pop2();
   switch(postfix[i])
   {
    case '+':
     val=val2+val1;
     break;
    case '-':
     val=val2-val1;
     break;
    case '*':
     val=val2*val1;
     break;
    case '/':
     val=val2/val1;
     break;
    case '^':
     val=pow(val2,val1);
     break;
    default:
     {
      printf("Error!\n");
      exit(0);
     }
   }  
   push2(val);
  }
 }
 val=pop2();
 printf("The value of expression=%f",val);
 printf("\n");
}
void push1(char c)
{

 stack1[++top1]=c;
}

char pop1(void)
{
 char c;
 c=stack1[top1];
 top1--;
 return c;
}
void push2(float c)
{
 stack2[++top2]=c;
}
                           
float pop2(void)
{
 float c;
 c=stack2[top2];
 top2--;
 return c;
}
int operand(char c)
{
 int i,flag=0;
 for(i=0;i<nv;i++)
 {
  if(variable[i]==c)
  { 
   flag=1;
  }
 }
 return flag;
}
int priority(char c)
{
 if(c=='(')
 {
  return 0;
 }
 if(c=='+')
 {
  return 1;
 }
 if(c=='-')
 {
  return 1;

 }
 if(c=='*')
 {
  return 2;
 }
 if(c=='/')
 {
  return 2;
 }
 if(c=='^')
 {
  return 3;
 }
 else
 {
  printf("Invalid operation\n");
  exit(0);
 }
}
float findval(char c)
{
 int i;
 for(i=0;i<nv;i++)
 {
  if(c==variable[i])
  {
   return value[i];
  }
  
 }
  return 0;
}

Output

C Program for open hashing

C Program for open hashing

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node *link;
};
void insert_hash(struct node**,int);
void traverse_hash(struct node*);
void delete_hash(struct node**,int);
void search_hash(struct node*,int);
main()
{
 int i,ch,key,pos;
 struct node* hash[10]={NULL};
 while(1)
 {
  printf("1-INSERTION\n2-TRAVERSING\n3-DELETION\n4-SEARCHING\n5-EXIT\n");
  printf("Enter a choice\n");
  scanf("%d",&ch);
  switch (ch)
  {
   case 1:
    printf("Enter the key\n");
    scanf("%d",&key);
    pos=key%10;
    insert_hash(&hash[pos],key);
    break;
   case 2:
    for(i=0;i<10;i++)
    {
     printf("hash[%d]:",i);
     traverse_hash(hash[i]);
    }
    break;
   case 3:
    printf("Enter key\n");
    scanf("%d",&key);
    pos=key%10;
    delete_hash(&hash[pos],key);
    break;
   case 4:
    printf("Enter key\n");
    scanf("%d",&key);
    pos=key%10;
    search_hash(hash[pos],key);
    break;
   case 5:
    exit(0);
  }
 }
}
void insert_hash(struct node**start,int key)
{
 struct node *temp,*temp1,*prev;
 temp=(struct node*) malloc (sizeof(struct node));
 if (temp==NULL)
 {
  printf("Linked list is not created\n");
 }
 else
 {
  temp->data=key;
  temp->link=NULL;
  temp1=*start;
  prev=*start;
  while( temp1!=NULL && key>temp1->data )
  {
   prev=temp1;
   temp1=temp1->link;
  }
  if (temp1==prev)
  {
   temp->link=*start;
   *start=temp;
  }
  else
  {
   temp->link=temp1;
   prev->link=temp;
  }
 }
}
void traverse_hash(struct node*start)
{
 struct node*temp;
 if (temp==NULL)
  printf("linked list is empty\n");
 else
 {
  temp=start;
  while(temp!=NULL)
  {
   printf("%d->",temp->data);
   temp=temp->link;
  } 
  printf("NULL\n");
 }
}
void delete_hash(struct node **start,int key)
{
 struct node *temp,*prev;
 if (*start==NULL)
  printf("linked list is empty\n");
 else
 {
  temp=*start;
  prev=*start;
  while (temp!=NULL && key!=(temp->data))
  {
   prev=temp;
   temp=temp->link;
  }
  if (temp==NULL)
   printf("Key is not found  \n");
  else
  {
   if (temp==prev)
    *start=(*start)->link;
   else
   {
    prev->link=temp->link;
   }
   free(temp);
  }
 } 
}
void search_hash(struct node*start,int key)
{
 struct node *temp;
 int flag;
 if(temp==NULL)
  printf("Linked list is empty\n");
 else
 {
  temp=start;
  flag=0;
  while(temp!=NULL && flag==0)
  {
   if (key==temp->data)
    flag=1;
   temp=temp->link;
  }
 
  if (flag==0)
   printf("Key is not found\n");
  else
   printf("Key is found\n");
 }
}
 

Output

Polynomial Addition and Multiplication using Linked List

Polynomial Addition and Multiplication using Linked List

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int coef;
 int exp;
 struct node *link;
};
void insert_term(struct node **,int,int);
void traverse(struct node *);
void poly_add(struct node **,struct node **,struct node **);
void poly_pdt(struct node **,struct node **,struct node **);
void main()
{
 struct node *start_p=NULL,*start_q=NULL,*start_r=NULL;
 int i,n,c,e;
 printf("Enter first polynomial?\n");
 printf("Enter no of terms?\n");
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  printf("Enter %d term\n",i+1);
  printf("Enter coefficient\n");
  scanf("%d",&c);
  printf("Enter exponent\n");
  scanf("%d",&e);
  insert_term(&start_p,c,e);
 }
 printf("Enter second polynomial\n");
 printf("Enter no of terms?\n");
 scanf("%d",&n);
 for(i=0;i<n;i++)
 {
  printf("Enter %d term",i+1);
  printf("Enter coefficient\n");
  scanf("%d",&c);
  printf("Enter exponent\n");
  scanf("%d",&e);
  insert_term(&start_q,c,e);
 }
 printf("First polynomial:\n");
 traverse(start_p);
 printf("second polynomial:\n");
 traverse(start_q);
 poly_add(&start_p,&start_q,&start_r);
 printf("sum of two polynomial:\n");
 traverse(start_r);
 start_r=NULL;
 poly_pdt(&start_p,&start_q,&start_r);
 printf("Product of the two polynomial:\n");
 traverse(start_r);
 
}
void insert_term(struct node **start,int c,int e)
{ 
 struct node *temp,*temp1,*prev;
 if (*start==NULL)
 {
  temp=(struct node*)malloc(sizeof(struct node));
  if (temp==NULL)
   printf("Node is not created.Term cannot be inserted\n");
  else
  {
   temp->coef=c;
   temp->exp=e;
   temp->link=NULL;
   *start=temp;
  }
 }
 else
 {
  temp1=*start;
  while (temp1!=NULL && temp1->exp>e)
  {
   prev=temp1;
   temp1=temp1->link;
  }
  if(temp1==NULL)
  {
   temp=(struct node *)malloc(sizeof(struct node));
   if (temp==NULL)
    printf("Node is not created\n");
    
   else
   {
    temp->coef=c;
    temp->exp=e;
    temp->link=NULL;
    prev->link=temp; 
   }
  }
  else
  {
   if(temp1->exp==e)
    temp1->coef=temp1->coef+c;
   else
   {
    if(temp1==*start)
    {
     temp=(struct node *)malloc (sizeof (struct node));
     if(temp==NULL)
      printf("Node is not created\n");
     else
     {
      temp->coef=c;
      temp->exp=e;
      temp->link=*start;
      *start=temp;
     }
    }
    else
    {
     temp=(struct node *)malloc(sizeof(struct node));
     if (temp==NULL)
      printf("node is not created\n");
     else
     {
      temp->coef=c;
      temp->exp=e;
      temp->link=temp1;
      prev->link=temp;
     }
    }
   } 
  }
 }

}
void traverse(struct node *start)
{
 struct node *temp;
 temp=start;
 if (temp==NULL)
  printf("Empty polynomial\n");
 else
 {
  while(temp!=NULL)
  {
   printf("+  %d X ^%d ",temp->coef,temp->exp);
   temp=temp->link;
  }
  printf("\n");
 }
 

}
void poly_add(struct node** start_p,struct node **start_q,struct node** start_r)
{
 int c,e;
 struct node *pptr,*qptr;
 *start_r=NULL;
 pptr=*start_p;
 qptr=*start_q;
 while(pptr!=NULL && qptr!=NULL)
 {
  if (pptr->exp==qptr->exp)
  {
   c=pptr->coef+qptr->coef;
   e=pptr->exp;
   insert_term(start_r,c,e);
   pptr=pptr->link;
   qptr=qptr->link;
  }
  else
  {
   if (pptr->exp>qptr->exp)
   {
    c=pptr->coef;
    e=pptr->exp;
    insert_term(start_r,c,e);
    pptr=pptr->link;
   }
   else
   {
    c=qptr->coef;
    e=qptr->exp;
    insert_term(start_r,c,e);
    qptr=qptr->link;
   }
  }
 }
 while(pptr!=NULL)
 {
  c=pptr->coef;
  e=pptr->exp;
  insert_term(start_r,c,e);
  pptr=pptr->link;
 }
 while (qptr!=NULL)
 {
  c=qptr->coef;
  e=qptr->exp;
  insert_term(start_r,c,e);
  qptr=qptr->link;
 }
 
}
void poly_pdt(struct node ** start_p,struct node **start_q,struct node** start_r)
{
 int c,e;
 struct node *pptr,*qptr;
 *start_r=NULL;
 pptr=*start_p;
 qptr=*start_q;
 if (*start_p==NULL && *start_q==NULL)
  printf("\n Multiplication of polynomial is not possible\n");
 else
 {
  while(pptr!=NULL)
  {
   qptr=*start_q;
   while(qptr!=NULL)
   {
    c=pptr->coef*qptr->coef;
    e=pptr->exp+qptr->exp;
    insert_term(start_r,c,e);
    qptr=qptr->link;
   }
   pptr=pptr->link;
  }
 }
}

Output

C Program for Binary Search Tree

C Program for Binary Search Tree

#include<stdio.h>
#include<stdlib.h>
struct node
{
 int data;
 struct node  *lchild;
 struct node *rchild;
 
};
void ins_bst(struct node**,int);
void del_bst(struct node **,int);
void pre_bst(struct node *);
 void in_bst(struct  node*);
void post_bst(struct node*);
struct node *inos(struct node *);
main()
{
 int i,ch;
 struct node *root=NULL;
 while(1)
 {
  printf("*********\n\tMENU\n********");
  printf("\n1.Insertion\n2.Deletion\nTRAVERSAL\n3.Inorder\n4.Preorder\n5.Postorder\n6.Exit\nEnter ur choice\n");
 scanf("%d",&ch);
 switch(ch)
 {
  case 1:
   printf("Enter the data\n");
   scanf("%d",&i);
   ins_bst(&root,i);
   break;
  case 2:
   printf("Enter the item to be deleted\n");
   scanf("%d",&i);
   del_bst(&root,i);
   break;
  case 3:
   printf("THE INORDER TRAVERSAL\t");
   in_bst(root);
   printf("\n");
   break;
  case 4:
   printf("THE PREORDER TRAVERSAL\t");
   pre_bst(root);
   printf("\n");
   break;
  case 5:
   printf("THE POSTORDER TRAVERSAL\t");
   post_bst(root);
   break;
  case 6:
   exit(0);
   break;
  default:
   printf("SORRY WRONG CHOICE\n");

 }
}
}
void in_bst(struct node *root)
{
 struct node *ptr;
 ptr=root;
 if(ptr!=NULL)
 {
  in_bst(ptr->lchild);
  printf("%d\t",ptr->data);
  in_bst(ptr->rchild);
 }
}
void ins_bst(struct node **root,int item)
{
 int f=0;
 struct node *ptr,*temp,*parent;
 ptr=*root;
 parent=*root;
 while(ptr!=NULL&&f==0)
 {
  if(item==ptr->data)
  {
   printf("ITEM ALREADY EXISTS\n");
   f=1;
  }
  else if(item>ptr->data)
  {
   parent=ptr;
   ptr=ptr->rchild;
  }
  else if(item<ptr->data)
  { parent=ptr;
   ptr=ptr->lchild;
  }
 }
 if (f==0)
 {
  temp=(struct node*)malloc(sizeof(struct node));
  if(temp==NULL)
  {
   printf("The node is not created\n");
  }
  else
  {
   temp->data=item;
   temp->rchild=NULL;
   temp->lchild=NULL;
   if(*root==NULL)  
   {
    *root=temp;
   }
   else
   {
    if(item>parent->data)
     parent->rchild=temp;
    else
    {
     parent->lchild=temp;
    }
   }
  }
 }
}
void del_bst(struct node **root,int item)
{
 int f=0,c,i1;
 struct node *ptr1,*ptr,*parent;
 ptr=*root;
 parent=*root;
 while(ptr!=NULL&&f==0)
 {
  if(ptr->data==item)
   f=1;
  else if (item>ptr->data)
  {
   parent=ptr; 
   ptr=ptr->rchild;
  }
  else /* if(item<ptr->data)*/
  {
   parent=ptr;
   ptr=ptr->lchild;
  }
 }
 if(f==0)
 {
  printf("Item is not present\n");
  /* return(0);*/
 }
 else
 {
  if(ptr->lchild==NULL&&ptr->rchild==NULL)
  {
   c=0;
  }
  else if (ptr->lchild!=NULL && ptr->rchild!=NULL)
  {
   c=2;
  }
  else
  {
   c=1;
  }

  if(c==0)
  {
   if(parent==ptr) 
    *root=NULL;
   else
   {

    if(parent->lchild==ptr)
    { 
     parent->lchild=NULL;
    }
    else
    {
     parent->rchild=NULL;
    }
    free(ptr);
   }
  }
  if(c==1)
  {
   if(parent==ptr)
   {
    if(parent->rchild==NULL)
    {
     *root=parent->lchild;
    }
    else
    {
     *root=parent->rchild;
    }
   }
   else if(parent->lchild==ptr)
   {
    if(ptr->lchild==NULL)
    {
     parent->lchild=ptr->rchild;
    }
    else
    {
     parent->lchild=ptr->lchild;
    }
   }  
   else
   {
    if(ptr->lchild==NULL)
    {
     parent->rchild=ptr->rchild;
    }
    else
    {

     parent->rchild=ptr->lchild;
    }
   }
   free(ptr);
  }
  if(c==2)
  {
   ptr1=inos(ptr);
   i1=ptr1->data;
   del_bst(root,i1);
   ptr->data=i1;
  }
 
 }
}
struct node*inos(struct node *ptr)

{
 ptr=ptr->rchild;
 if(ptr!=NULL)
 {
  while(ptr->lchild!=NULL)
  {
   ptr=ptr->lchild;
  }
 }
 return(ptr);
}
void pre_bst(struct node *root)
{
 struct node *ptr;
 ptr=root;
 if(ptr!=NULL)
 {
  printf("%d\t",ptr->data);
  pre_bst(ptr->lchild);
  pre_bst(ptr->rchild);
 }
 
 
}
void post_bst(struct node*root)
{
 struct node *ptr;
 ptr=root;
 if(ptr!=NULL)

 {
  post_bst(ptr->lchild);
  post_bst(ptr->rchild);
  printf("%d\t",ptr->data);
 }

}

Output

C Program for Linked List Implementation

C Program for Linked List Implementation

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

};
void insert_begin_sll(struct node**,int);
void traverse_sll(struct node*);
void insert_end_sll(struct node **,int);
void insert_position_sll(struct node**,int,int);
void delete_begin_sll(struct node **);
void delete_end_sll(struct node **);
void delete_position_sll(struct node **,int);
void search_sll(struct node**,int);
int main()

{
 int ch,position,key;
 struct node *start=NULL;
 while(1)
 {
  printf("Select from the menu\n");
  printf("1.Insert node at beginning\n2.Traversing\n3.Insert node at end\n4.Insert node at specific position\n5.Delete node from beginning\n6.Delete node from end\n7.Delete node from specified position\n8.searching\n9.exit\n");
 printf("Enter a choice\n");
 scanf("%d",&ch);

 switch (ch)
 {
  case 1:
   printf("Enter key\n");
   scanf("%d",&key);
   insert_begin_sll(&start,key);
   break;
  case 2:
   traverse_sll(start);
   break;
  case 3:
   printf("Enter key\n");
   scanf("%d",&key);
   insert_end_sll(&start,key);
   break;
  case 4:
   printf("Enter key\n");
   scanf("%d",&key);
   printf("Enter position\n");
   scanf("%d",&position);
   insert_position_sll(&start,key,position);
   break;
  case 5:
   delete_begin_sll(&start);
   break;
  case 6:
   delete_end_sll(&start);
   break;
  case 7:
   printf("Enter position\n");
   scanf("%d",&position);
   delete_position_sll(&start,position);
   break;
  case 8:
   printf("Enter the key to be searched\n");
   scanf("%d",&key);
   search_sll(&start,key);
   break;
  case 9:
   exit(0);
 }
 }
}
void insert_begin_sll(struct node **start,int key)
{
 struct node *temp;
 temp=(struct node*)malloc(sizeof(struct node));
 if (temp==NULL)
  printf("Node is not created \n Insertion is not possible\n");
 else
 { 
  temp->data=key;
  temp->link=NULL;
  temp->link=*start;
  *start=temp;
 }
} 
void traverse_sll(struct node *start)
{
 struct node *temp;
 if (start==NULL)
  printf("Linked list is empty\n");
 else
 {
  temp=start;
  while(temp!=NULL)
  {
   printf("%d->",temp->data);
   temp=temp->link;
  }
  printf("NULL\n");
 }
}
void insert_end_sll(struct node**start,int key)
{
 struct node *temp,*temp1;
 temp=(struct node *)malloc(sizeof(struct node));
 if (temp==NULL)
  printf("node is not created\nInsertion is not possible\n");
 else
 {
  temp->data=key;
  temp->link=NULL;
  if(*start==NULL)
   *start=temp;
  else
  {
   temp1=*start;
   while(temp1->link!=NULL)
    temp1=temp1->link;
   temp1->link=temp;
  }
 }
}
void insert_position_sll(struct node **start,int key,int position)
{
 struct node *temp1,*temp;
 int count;
 if (position<=0)
  printf("position is invalid\n");
 else
 {
  temp=(struct node*)malloc(sizeof(struct node));
  if (temp==NULL)
   printf("Node is not created\nInsertion is not possible\n");
  else
  {
   temp->data=key;
   temp->link=NULL;
   if (position==1)
   {
    temp->link=*start;
    *start=temp;
   }
   else
   {
    temp1=*start;
    count=1;
    while (count<position-1 && temp1!=NULL)
    {
     temp1=temp1->link;
     count++;
    }
    if(temp1==NULL)
     printf("Linked list is out of range\n");
    else
    {
     temp->link=temp1->link;
     temp1->link=temp;
    }
   }
  }
 }
}
void delete_begin_sll(struct node **start)
{
 struct node *temp;
 if(*start==NULL)
  printf("Linked list is empty\n Deletion is not possible\n");
 else
 {
  temp=*start;
  *start=(*start)->link;
  free(temp);
 }
}  
void delete_end_sll(struct node **start)
{
 struct node *prev,*temp;
 if(*start==NULL)
  printf("Linked list is empty \nDeletion is not possible\n");
 else
 {
  temp=*start;
  prev=*start;
  while(temp->link!=NULL)
  {
   prev=temp;
   temp=temp->link;
  }
  if(temp==prev)
   *start=NULL;
  else
   prev->link=NULL;
  free(temp);
 }
}
void delete_position_sll(struct node **start,int position)
{
 struct node *temp,*prev;
 int count;
 if (position<=0)
  printf("position is invalid\n");
 else
 {
  if (position==1)
  {
   temp=*start;
   *start=(*start)->link;
  }
  else
  {
   temp=*start;
   prev=*start;
   count=1;
  }
  while (count<position && temp!=NULL)
  {
   prev=temp;
   temp=temp->link;
   count++;
  }
  if(temp==NULL)
   printf("Linked list is out of range\n");
  else
   prev->link=temp->link;
  free(temp);
 }
}
void search_sll(struct node **start,int key)
{
 struct node *temp;
 int flag=0;
 if(start==NULL)
  printf("Linked list is empty.\nSearching is not possible\n");
 else
 {
  temp=*start;
  while (temp!=NULL && flag==0)
  {
   if (key==temp->data)
    flag=1;
   temp=temp->link;
  }
  if (flag==0)
   printf("key is not found\n");
  else
   printf("Key is found\n");
 }
}

Output

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