Tower of Hanoi

#include<stdio.h>
#include<string.h>

int tower(int n, char s, char t, char d)
{
   int x,y;
   if(n<=0) return 0;
   x= tower(n-1,s,d,t);
   printf("move %d from %c to %c\n",n,s,d);
   y=tower(n-1,t,s,d);
   return(x+y+1);
 }

void main()
{
   int n;
   printf("Enter the number of discs\n");
   scanf("%d",&n);
   n= tower(n,'S', 'T','D');
   printf("There are %d moves\n",n);
   getch();
}


This is the code from the text Tanenbaum..a slight modification has been done.


#include<stdio.h>

int tower(int n,char s,char d,char a)
{
 if(n==1)
 {
  printf("Move the disk %d from %c to %c\n",n,s,d);
  return;
 }
 tower(n-1,s,a,d);
 printf("Move the disk %d from %c to %c\n",n,s,d);
 tower(n-1,a,d,s);
}

main()
{
 int n;
 printf("Enter the number of discs:\n");
 scanf("%d",&n);
 printf("The moves are:\n");
 tower(n,'S','D','A');
}

Circular Queue using Arrays

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define SIZE 5

void insert(int q[], int *f, int *r)
{
   if(*f == (*r+1)%SIZE)
      return;
   *r=(*r+1)%SIZE;
     printf("Enter the data\n");
     scanf("%d",&q[*r]);
     if(*f == -1)
        *f= 0;
}

void del(int *f, int *r)
{
   if(*f== -1)
      return;
   if(*f == *r)
     *f = *r = -1;
   else
     *f= (*f+1)% SIZE;
}

void display(int q[], int *f, int *r)
{
   int i;
   if(*f== -1)
       printf("circular queue is empty\n");
   else
   {
      for(i= *f; i!= *r; i=(i+1)%SIZE)
        printf("%d", q[i]);
      if(*f == (*r+1)%SIZE)
        printf("circular queue is full\n");
    }
}

void main()
{
  int ch, q[SIZE],f = -1,r= -1;
  while(1)
  {
    display(q,&f,&r);
    printf(" 1. Insert\n 2. Delete\n 3.quit\n");
    printf("Enter your choice\n");
    scanf("%d",&ch);
    switch(ch)
    {
       case 1 : insert(q,&f,&r);break;
       case 2 : del(&f,&r);break;
       default : return;
     }
 }

This is my program which uses structures..a better way :)


#include<stdio.h>
#define size 3

struct queue
{
  int front,rear;
  int array[size];
}s;

int count=0,j;

int qfull()
{
  if(count == size)
    return 1;
  return 0;
}

int qempty()
{
 if(count == 0)
  return 1;
 return 0;
}

void insert_rear(int x)
{
 
   s.rear=(s.rear+1)%size;
   s.array[s.rear]=x;
   count++;
   return;
}


int del_front()
{
 int i;

 i=s.array[s.front];
 s.front=(s.front+1)%size;
 count--;
 printf("The element deleted is %d\n", i);

}

void display()
{
 int i,j=s.front;
 if(qempty())
  printf("QUEUE IS EMPTY\n");
 else
 {
   printf("The contents of the queue are:\n");
   for(i=0;i<count;i++)
    {
      printf("%d\n",s.array[j]);
      j=(j+1)%size;
    }
 }
}

main()
{
  s.rear= size-1;s.front=0;
  int ch,x,c;
  while(1)
  {
   printf("1.Insert\n2.Delete\n3.Display\n4.Exit\n");
   printf("Enter your choice\n");
   scanf("%d",&ch);
   switch(ch)
   {
    case 1 : if(qfull())
             {
              printf("OVERFLOW IN QUEUE\n");
             }
             else
             {
              printf("Enter the element to be inserted\n");
              scanf("%d",&x);
              insert_rear(x);
             }
             break;
    case 2 :  if(qempty())
              {
               printf("UNDERFLOW\n");
              }
               else
             del_front();
             break;
    case 3 : display();
             break;
    default : return;
   }
  }
}

Infix to Postfix

Write a C pogram to convert an infix expression to postfix expression using the concept of stacks.


#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>

#define SIZE 20

int pos;

struct stack
{
  int top;
  char items[SIZE];
};

void push(struct stack *s,char ch)
{
  if(s->top==(SIZE-1))
  return;
  s->items[++s->top]=ch;
}

char pop(struct stack *s)
{
  char y;
  if(s->top==-1)
  printf("Stack is empty\n");
  else
  {
     y=s->items[s->top];
     s->top--;
     return y;
    }
}

int prec(char stopn, char inopn)
{
  int ip=0, sp=0;
  switch(stopn)
  {
    case '+' :
    case '-'  :   sp=2 ; break;
    case '*' :
    case '/'  :   sp=4; break;
    case '$' :   sp=5; break;
    case '(' :    sp= -1; break;
  }

 switch (inopn)
 {
   case '+' :
   case '-' : ip=1;break;
   case '*' :
   case '/' : ip =3;break;
   case '$' : ip=6;break;
   case '(' : ip=9;break;
  case ')' : ip=0;break;
  default : ip=8; break;
 }

if(sp>ip) return 1;
else return 0;
} //end of int prec()

int empty(struct stack *s)
{
   if(s->top== -1)return 1;
   else return 0;
}

char stacktop(struct stack *s)
{
   if(empty(s))
   {
      printf("underflow in stack\n");
      return;
    }
   else
   return (s->items[s->top]);
}

void main()
{
  struct stack s;
  char infix[50], postfix[50],symb;
  int i,rank=0;
  s.top= -1;
  printf("Enter infix string\n");
  scanf("%s",infix);
  if(infix[strlen(infix)-1] == '*' || infix[strlen(infix)-1] == '+' || infix[strlen  (infix)-1]== '-' || infix[strlen(infix)-1] == '/')
  {
    printf("Invalid expression\n");
    return;
   }
  for(i=0,pos=0; ((symb=infix[i])!= '\0'); i++)
  {
     if(isalpha(symb))
     {
        postfix[pos++] = symb;
        rank++;
      }
     else
     {
        while(! empty(&s) && prec(stacktop(&s),symb))
        {
           postfix[pos++] = pop(&s);
           rank--;
           if(rank<1)
          {
           printf("Invalid expression\n");
           return ;
           }
        }//end of while
      if(symb != ')' || empty(&s))
      push(&s,symb);
      else
      pop(&s);
     }//end of else
   }//end of for loop
 
   while(!empty(&s))
    {
       postfix[pos++] = pop(&s);
       rank--;
       if(rank<1)
       printf("Invalid expression\n");
    }

    if(rank== 1)
    {
       postfix[pos] = '\0';
       printf("%s",postfix);
    }
     else
         printf("Invalid expression\n");
   
}//end of main

Matrix multiplication using two-dimensional arrays

To write a simple C program to read two matrices A(MxN) and B(PxQ) and compute the product A and B after checking compatibility for multiplication.Output the input matrices and the resultant matrix with suitable headings and format.

#include<stdio.h>
main()
{
  int a[100][100],b[100][100],c[100][100],m,n,p,q,i,j,k;
  printf("Enter the order of the matrix A and B\n");
  scanf("%d%d%d%d",&m,&n,&p,&q);
  if(n==p)
  {
    printf("Enter the elements of matrix A\n");
    for(i=0;i<m;i++)
    {
      for(j=0;j<n;j++)
      {
        scanf("%d",&a[i][j]);
      }
     }
     printf("Enter the elements of matrix B\n");
     for(i=0;i<p;i++)
     {
       for(j=0;j<q;j++)
       {
          scanf("%d",&b[i][j]);
       }
      }
     for(i=0;i<m;i++)
     {
       for(j=0;j<q;j++)
       {
          for(k=0;k<n;k++)
          {
             c[i][j] += a[i][k]+b[k][j];
           }
       }
      }
      printf("The original matrices are\n");
      for(i=0;i<m;i++)
      {
         for(j=0;j<n;j++)
         {
           printf("%d\t",a[i][j]);
          }
           printf("\n");
        }
        for(i=0;i<p;i++)
        {
           for(j=0;j<q;j++)
           {
             printf("%d\t",b[i][j]);
           }
            printf("\n");
         }
         printf("Resultant matrix is \n");
         for(i=0;i<m;i++)
         {
            for(j=0;j<q;j++)
            {
              printf("%d\t"c[i][j]);
             }
            printf("\n");
         }
     } //end of if statement
else
 printf("multiplication not possible since n is not equal to p\n");
}//end of program

Bubble sort in single dimension array

To write a C program to input N integers into a single dimension array and sort them in ascending order suing bubble sort technique.

Here's a diagramatic explanation :





C code :

#include<stdio.h>
main()
{
  int i,j,n,a[100],t;
  printf("Enter the size of the array\n");
  scanf("%d",&n);
  printf("Enter the elements of the array\n");
  for(i=0;i<n;i++)
   scanf("%d",&a[i]);
 printf("The unsorted array is :\n");
 for(i=0;i<n;i++)
  printf("%d\n",a[i]);

 for(i=0;i<n-1;i++) //Actual bubble sort begins
 {
   for(j=0;j<n-1-i;j++)
   {
      if(a[j]>a[j+1])
      {
         t=a[j];
         a[j]=a[j+1];
         a[j+1]=t;
       }
    }
 }
 printf("The sorted array is :\n");
 for(i=0;i<n;i++)
  printf("%d\n",a[i]);
}  

Binary Search in Single dimension array

This is for my juniors who are finding it difficult to code in labs because of horrible lab teachers+theory teachers :P I hope my juniors wont suffer like me!

 To write a C program to input N real integers in ascending order into single dimension array and to conduct a Binary Search for a given integer.

Here's how this algorithm works :

#include<stdio.h>
main(0
{
   int i,n,a[100],begin,end,mid,flag=-1,k;//Comparing with the above  pic, here min=begin,max=end
   printf("Enter the size of the array\n");
   scanf("%d",&n);
   printf("Enter the array in the increasing order\n");
   for(i=0;i<n;i++)
    scanf("%d",&a[i]);
  printf("Enter the key number to be searched\n");
  scanf("%d",&k);
  begin=0;
  end=n-1;
  while(begin<=end)
  {
    mid=(begin+end)/2;
    if(k==a[mid])
    {
      flag=mid;
      break;
     }
   else if(k>a[mid])
     begin=mid+1;
   else
     end=mid-1;
  }
if(flag==-1)
 printf("FAILURE.Element not found in the array\n");
else
 printf("SUCCESS.The element is found in the array at location %d",flag);
}

Remember to enter the elements in ascending order! :)

TWO STACKS IN A SINGLE ARRAY IN C

Another important program which has been asked in many technical interviews is : WAP to implement two stacks in a single array so that either of the stacks become full only when the entire array is full.



Here's the C program :


#include<stdio.h>
#define SIZE 10
struct stack
{
 int top1,top2;
 int array[SIZE];
}s;

void push1(int x)
{
 if((s.top1)<(s.top2-1))
  s.array[++(s.top1)]=x;
 else
  printf("OVERFLOW IN STACK 1\n");
}

void push2(int x)
{
 if((s.top2)>(s.top1+1))
  s.array[--(s.top2)]=x;
 else
  printf("OVERFLOW IN STACK 2\n");
}

int pop1()
{
 if((s.top1)>=0 && (s.top1)<(s.top2))
  printf("The element popped out from stack1 is %d\n",s.array[(s.top1)--]);
 else
  printf("UNDERFLOW IN STACK 1\n");
}

int pop2()
{
 if((s.top2)<SIZE && (s.top2)>(s.top1))
  printf("The element popped out from stack 2 is %d\n",s.array[(s.top2)++]);
 else
  printf("UNDERFLOW IN STACK 2\n");
}

main()
{
 s.top1 = -1,s.top2 = 5;
 int ch,x;
 while(1)
 {
  printf("IMPLENTATION OF TWO STACKS IN SINGLE ARRAY\n");
  printf("Enter your choice of operation\n");
  printf("1.PUSH TO STACK 1\n2.PUSH TO STACK 2\n3.POP FROM STACK 1\n4.POP FROM STACK 2\n 5.EXIT\n");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1: printf("Enter element to be pushed to stack 1\n");
          scanf("%d",&x);
          push1(x);
          break;
   case 2: printf("Enter element to be pushed to stack 2\n");
          scanf("%d",&x);
          push2(x);
          break;
   case 3: pop1();
          break;
   case 4: pop2();
          break;
   default: return;
  }
 }
}

IMPLEMENTATION OF STACKS USING ARRAYS IN C

Datastructures is an important subject in CS engineering.Implementation of stacks using arrays is a common concept.If you google "implementation of stack using arrays", you will find hundreds of programs explaining this. Most of the programs would have declared array globally, but finding the program which uses structures is difficult :P .So I thought of uploading my program.

Here's the program in C:


#include<stdio.h>
#define SIZE 100

struct stack
{
 int top;
 int array[SIZE];
}s;



void push(int x)
{
 if((s.top)==(SIZE-1))
 printf("STACK OVERFLOW\n");
 (s.array[++(s.top)])=x;
}

int pop(int x)
{
 if((s.top)==-1)
 printf("STACK UNDERFLOW\n");
 else
 printf("The element popped out of the stack is %d\n",s.array[(s.top)--]);
}

void display()
{
 int i;
 if((s.top)==-1)
  printf("STACK IS EMPTY\n");
 else
 {
  printf("The contents of the stack are:\n");
  for(i=s.top;i>=0;i--)
   printf("%d\n",s.array[i]);
 }
}

int main()
{
 int ch,x;
 s.top = -1;
 while(1)
 {
  printf("Enter your choice of operation\n");
  printf("1.PUSH\n2.POP\n3.DISPLAY THE STACK\n4.EXIT\n");
  scanf("%d",&ch);
  switch(ch)
  {
   case 1: printf("Enter the element to be pushed\n");
             scanf("%d",&x);
             push(x);
             break;
   case 2: pop(x);
              break;
   case 3: display();
              break;
   default:return;
         
  }
 }
}