Source Code: Data Structure Questions

Q.1) WRITE A
PROGRAM IN C TO SORT AN ARRAY USING INSERTION SORT.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void insort(int a[], int size)

{

 int i, j, t;

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

  {

                                t
= a[i];

                                j
= i;

                                while
((j > 0) && (a[j-1] > t))

                                 {

                                  a[j] = a[j-1];

                                  j = j - 1;

                                 }

                                a[j]
= t;

  }

}







void main()

{

 int *a,i,n;

 printf("\nEnter the length of the array
:");

 scanf("%d",&n);

 a=(int*)malloc(n * sizeof(int));

 printf("\nEnter the elements of the array
:\n");

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

  {

                printf("Enter
%d element : ",i+1);

                scanf("%d",&a[i]);

  }

 insort(a,n);

 printf("\n\nSorted array : ");

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

 printf(" 
%d",a[i]);

 getch();

}










Q.2) WRITE A
PROGRAM IN C TO SORT AN ARRAY USING SELECTION SORT.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>







void selsort(int a[], int size)

{

 int i, j, min,
temp;

 for (i=0;
i<(size-1); i++)

  {

                min
= i;

                for
(j=i+1; j<size; j++)

                 {

                  if (a[j] < a[min])

                  min = j;

                 }

                temp
= a[i];

                a[i]
= a[min];

                a[min]
= temp;

  }

}




void main()

{

 int *a,i,n;

 printf("\nEnter the length of the array
:");

 scanf("%d",&n);

 a=(int*)malloc(n * sizeof(int));

 printf("\nEnter the elements of the array
:\n");

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

  {

                printf("Enter
%d element : ",i+1);

                scanf("%d",&a[i]);

  }

 selsort(a,n);

 printf("\n\nSorted array : ");

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

 printf(" 
%d",a[i]);

 getch();

}




Q.3) WRITE A
PROGRAM IN C TO SORT AN ARRAY USING QUICK  SORT.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void quicksort(int *,int,int);

int split(int *,int,int);




void main()

{

                int
*a,i,n;

                clrscr();

                printf("Enter
the no. of  elements in the array:
");

                scanf("%d",&n);

                a
= (int *)malloc(n*sizeof(int));

                printf("\nEnter
the elements of the array : \n");

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

                 scanf("%d",&a[i]);




                quicksort(a,0,n-1);

                printf("\n\nThe
array after sorting is :");

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

                   printf("  %d",a[i]);




                getch();

}




void quicksort(int a[],int lower,int upper)

{

                int
i;

                if(upper>lower)

                {

                                i=split(a,lower,upper);

                                quicksort(a,lower,i-1);

                                quicksort(a,i+1,upper);

                }

}




int split(int a[],int lower,int upper)

{

                int
i,p,q,t;

                p=lower+1;

                q=upper;

                i=a[lower];




                while(q>=p)

                {

                                while(a[p]<i)

                                p++;




                                while(a[q]>i)

                                q--;




                                if(q>p)

                                {

                                                t=a[p];

                                                a[p]=a[q];

                                                a[q]=t;

                                }

                }

                t=a[lower];

                a[lower]=a[q];

                a[q]=t;

                return
q;

}




Q.4) WRITE A
PROGRAM IN C TO IMPLEMENT BINARY SEARCH IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void main()

{

 int *a, i, n,
x, low, mid, high;

 clrscr();




 printf("Enter the length of the array :
");

 scanf("%d",&n);

 a = (int
*)malloc(n * sizeof(int));




 printf("\n\nEnter the Array elements in
ASCENDING ORDER : \n");

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

                scanf("%d",&a[i]);




 printf("\n\nEnter the element to be
searched\n");

 scanf("%d", &x);




 low=1;

 high=n;




 do

  {

                mid=
(low + high) / 2;

                if
( x < a[mid] )

                                high
= mid - 1;

                else
if ( x > a[mid])

                                low
= mid + 1;

  } while(
x!=a[mid] && low <= high);




 if( x == a[mid]
)

                printf("\n\n....SUCCESSFUL
SEARCH....\nIt is at position %d",(mid+1));




 else

                printf("\n\nSearch
is FAILED");

}




Q.5) WRITE A
PROGRAM IN C TO IMPLEMENT STACK IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void stackpush (int *a,int &n)

{

 int i,x;

 if(n>10)

  {

 
printf("Cannot be inserted");

  return;

  }

 n++;




  printf("\nEnter
the element to be inserted : ");

 
scanf("%d",&x);

  a[n-1]=x;

 
printf("The array now is : ");

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

 
printf("%d ",a[i]);

  getch();

}




int stackpop (int a[],int &n)

{

 int x;

 if(n==0)

 
printf("Stack Underflow ");




 else

  {

  x=a[n-1];

  n--;

  }

 return(x);

}










void main()

{

 int *a,n,c,i,x;

 a = (int
*)malloc(10 * sizeof(int));

 clrscr();

 printf("Enter no. of elements of array :
");

 scanf("%d",&n);




 printf("\nEnter the array
elements:\n");

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

  scanf("%d",&a[i]);




 st:




 clrscr();

 printf("\n\t1.Stack Push");

 printf("\n\t2.Stack Pop");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter your Choice : ");

 scanf("%d",&c);

 switch (c)

 {

  case 1 :
stackpush(a,n);

                   break;




  case 2 :
x=stackpop(a,n);

                   printf("\nThe element popped out is
%d",x);

                   getch();

                   break;




  case 3 :
printf("\n\nThe elements in the array : ");

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

                   printf("%d ",a[i]);

                   getch();

                   break;




   case 4 :
exit(0);




   default : printf("\n\n....Wrong
Choice ....");

                     getch();

                     break;

  }

  goto st;

}







Q.6)  WRITE A PROGRAM IN C TO IMPLEMENT STACK IN A
LINKED LIST.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




typedef struct linkedlist

{

 int data;

 struct linkedlist
*link;

}node;




node *top=NULL;




void stackpush()

{

 node *temp;

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

 printf("\nEnter the node data : ");

 scanf("%d",&temp->data);

 temp->link=top;

 top=temp;

}







int stackpop()

{

 node *p,*pre;

 int temp;

 p=top;

 if(p->link==NULL)

  {

                free(p);

                top=NULL;

                return
0;

  }

 else

  {

                pre=p;

                p=p->link;

                top=p;

                temp=pre->data;

                free(pre);

                return(temp);

  }




}




void display()

{

 node *ptr;

 int i=0;

 if(top==NULL)

                printf("\n....Empty
list....");

 else

  {

                ptr=top;

                while(ptr)

                 {

                  printf("\nNode %d data :
%d",i+1,ptr->data);

                  ptr=ptr->link;

                  i++;

                 }

  }

 getch();

}







void main()

{

 int c,x;

 clrscr();




 st:




 clrscr();

 printf("\n\t1.Stack Push");

 printf("\n\t2.Stack Pop");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter your Choice : ");

 scanf("%d",&c);




 switch (c)

 {

  case 1 :
stackpush();

                                                  break;




  case 2 :
x=stackpop();

                                                  printf("\nThe element popped out is
%d",x);

                                                  getch();

                                                  break;




  case 3 :
display();

                                                  break;




  case 4 :
exit(0);




  default :
printf("\n\n....Wrong Choice ....");

                                                                getch();

 }




 goto st;

}













Q.7) WRITE
PROGRAM IN C TO IMPLEMENT QUEUE IN AN ARRAY.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void queueins (int *a,int &n)

{

 int i,x;

 if(n>10)

  {

 
printf("Cannot be inserted");

  return;

  }

  n++;




 
printf("\nEnter the element to be inserted : ");

 
scanf("%d",&x);

  a[n-1]=x;

 
printf("The array now is : ");

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

 
printf("%d ",a[i]);

  getch();

}




int queuedel (int a[],int &n)

{

 int i,x;

 if(n==0)

 
printf("Queue Underflow ");




 else

  {

   x=a[0];

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

   a[i]=a[i+1];

   n--;

   }

  return(x);

}










void main()

{

 int *a,n,c,i,x;

 a = (int
*)malloc(10 * sizeof(int));

 clrscr();

 printf("Enter no. of elements of array :
");

 scanf("%d",&n);




 printf("\nEnter the array
elements:\n");

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

 
scanf("%d",&a[i]);




 st:




 clrscr();

 printf("\n\t1.Queue Insert");

 printf("\n\t2.Queue Delete");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter your Choice : ");

 scanf("%d",&c);




 switch (c)

 {

  case 1 :
queueins(a,n);

                   break;




  case 2 :
x=queuedel(a,n);

                   printf("\nThe element deleted is
%d",x);

                   getch();

                   break;




  case 3 :
printf("\n\nThe elements in the array : ");

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

                   printf("%d ",a[i]);

                   getch();

                   break;




   case 4 :
exit(0);




   default :
printf("\n\n....Wrong Choice ....");

                     getch();

                     break;

  }




  goto st;

}
















Q.8) WRITE
PROGRAM IN C TO IMPLEMENT QUEUE IN A LINKED LIST.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




typedef struct linkedlist

{

 int data;

 struct
linkedlist *link;

}node;




node *top=NULL;




void qins()

{

 node
*temp,*ptr;

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

 printf("Enter the node data : ");

 scanf("%d",&temp->data);

 if(top==NULL)

                {

                temp->link=NULL;

                top=temp;

                }

 else

                {

                 ptr=top;

                 while(ptr->link)

                                ptr=ptr->link;

                 temp->link=NULL;

                 ptr->link=temp;




                }

}







int qdel()

{

 node *p,*pre;

 int temp;

 p=top;

 if(p->link==NULL)

  {

                free(p);

                top=NULL;

                return
0;

  }

 else

  {

                pre=p;

                p=p->link;

                top=p;

                temp=pre->data;

                free(pre);

                return(temp);

  }




}




void display()

{

 node *ptr;

 int i=0;

 if(top==NULL)

                printf("\n....Empty
list....");

 else

  {

                ptr=top;

                while(ptr)

                 {

                  printf("\nNode %d data :
%d",i+1,ptr->data);

                  ptr=ptr->link;

                  i++;

                 }

  }

 getch();

}







void main()

{

 int c,x;

 clrscr();




 st:




 clrscr();

 printf("\n\t1.Queue Insert");

 printf("\n\t2.Queue Delete");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter
your Choice : ");

 scanf("%d",&c);

 switch (c)

 {

  case 1 :
qins();

                                                  break;




  case 2 :
x=qdel();

                                                  printf("\nThe element deleted is
%d",x);

                                                  getch();

                                                  break;




  case 3 :
display();

                                                  break;




  case 4 :
exit(0);




  default : printf("\n\n....Wrong
Choice ....");

                                                                getch();

 }

 goto st;

}







Q.9) WRITE
PROGRAM IN C TO IMPLEMENT DOUBLE-ENDED QUEUE IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define max 10







int count(int *arr)

{

 int c=0,i;




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

 {

  if(arr[i]!=0)

    c++;

 }




 return c;

}







void addatbeg(int *arr,int item,int *pfront,int
*prear)

{

 int i,k,c;

 if(*pfront==0
&& *prear==max-1)

 {

 
printf("\nDeque is Full...\n");

  return;

 }




 if(*pfront==-1)

 {

 
*pfront=*prear=0;

  arr[*pfront]=item;

  return;

 }




 if(*prear!=max-1)

 {

   
c=count(arr);

    k=*prear+1;




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

    {

    
arr[k]=arr[k-1];

     k--;

    }

    arr[k]=item;

    *pfront=k;

    (*prear)++;

 }




 else

  {

    (*pfront)--;

   
arr[*pfront]+item;

  }

}




void addatend (int *arr,int item,int *pfront,int
*prear)

{

 int i,k;




 if (*pfront==0
&& *prear==max-1)

 {

 
printf("\nDeque s full..");

  return;

 }




 if(*pfront ==
-1)

 {

  *prear =
*pfront=0;

  arr[*prear]=
item;

  return;

 }




 if(*prear==max-1)

 {

   k=*pfront-1;




  
for(i=*pfront-1;i<*prear;i++)

    {

     k=i;

    
if(k==max-1)

      arr[k]=0;

     else

     
arr[k]=arr[i+1];

     }




   (*prear)--;

   (*pfront)--;

 }




 (*prear)++;

 arr[*prear]=item;

}




int delatbeg (int *arr,int *pfront,int *prear)

{

 int item;

 if(*pfront==-1)

  {

  
printf("\nDeque is Empty...");

   return (0);

  }




 item =
arr[*pfront];

 arr[*pfront]=0;




 if(*pfront==*prear)

  
*pfront=*prear=-1;




 else

  ( *pfront)++;




 return item;

}







int delatend (int *arr,int *pfront,int *prear)

{

 int item;

 if(*pfront==-1)

  {

  
printf("\nDeque is Empty...");

   return (0);

  }




 item =
arr[*prear];

 arr[*prear]=0;

 (*prear)--;




 if(*prear==-1)

   *pfront=-1;




 return item;

}




void display(int *arr,int *pfront,int *prear)

{

 int i;




 printf("\nfront->  ");

 for(i=(*pfront);i<=(*prear);i++)

 
printf("  %d",arr[i]);

 printf(" 
<-rear");

}













void main()

{

 int a[max];

 int
front=-1,rear=-1,i,x,aa,bb;

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

    a[i]= 0;

 top:

 clrscr();

 printf("\n\t1.Add at Beg");

 printf("\n\t2.Add at End");

 printf("\n\t3.Delete from Beg");

 printf("\n\t4.Delete from End");

 printf("\n\t5.Display");

 printf("\n\t...Press other key for
exit...");

 printf("\n\nEnter your choice : ");

 scanf("%d",&x);

 switch (x)

 {

  case 1 : printf("\nEnter
element : ");

                   scanf("%d",&aa);

                   addatbeg(a,aa,&front,&rear) ;

                   printf("\n....Item Inserted at
Beg....");

                   getch();

                   break;




  case 2:  printf("\nEnter element : ");

                   scanf("%d",&bb);

                   addatend(a,bb,&front,&rear) ;

                   printf("\n....Item Inserted at
End....");

                   getch();

                   break;




  case 5:   printf("\nElements in a Deque :
");

                    display(a,&front,&rear);

                    getch();

                    break;




  case 3:   i=delatbeg(a,&front,&rear);

                    printf("\nItem Extracted :
%d",i);

                    getch();

                    break;




  case 4:   i=delatend(a,&front,&rear);

                    printf("\nItem Extracted :
%d",i);

                    getch();

                    break;




  default :
exit(0);

 }

goto top;

}







Q.10) WRITE
PROGRAM IN C TO IMPLEMENT PRIORITY QUEUE IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

void insert();

void del();

void display();




struct node

 {

  int priority;

  int info;

  struct node
*next;

 }*start,*q,*temp,*a;




void main()

{

 int ch;

 top :

 clrscr();

 printf("\n\n\t[1] INSERTION\n\t[2]
DELETION\n\t[3] DISPLAY\n\t[4] EXIT\n");

 printf("\nEnter your Choice : ");

 scanf("%d",&ch);

 switch(ch)

  {

   case 1 :
insert();

                    break;




   case 2 :
del();

                    break;




   case 3 :
display();

                    break;




   case 4 :
exit(0);




   default:
printf("\n\n....Wrong Choice....");

                    getch();

  }

  goto top;

}




void insert()

{

 int item,pr;

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

 printf("\n\nEnter the element to be
inserted : ");

 scanf("%d",&item);

 printf("\nEnter its Priority : ");

 scanf("%d",&pr);

 a->info=item;

 a->priority=pr;




 if(start==NULL
|| pr<(start->priority))

  {

  
a->next=start;

   start=a;

  }




 else

  {

   q=start;




  
while(q->next != NULL && (q->next->priority) <= pr)

   q=q->next;




  
a->next=q->next;

   q->next=a;

  }

}




void del()

{

 if(start==NULL)

   
printf("\n....UnderFlow\n");




 else

 {

  a=start;

 
printf("\nDeleted item is %d",a->info);

 
start=start->next;

  free(start);

 }

}




void display()

{

 temp=start;

 if(start==NULL)

  
printf("\n....Queue is Empty....");




 else

  {

  
printf("\n\n\nQueue is as follows :\n");

  
printf("\n\n\t\t  ITEM  || PRIORITY\n");

  
printf("\t\t---------------------");

  
while(temp!=NULL)

    {

    
printf("\n\t\t   %2d   ||  
%2d",temp->info,temp->priority);

    
temp=temp->next;

    }

  }

  getch();

}




Q.11)WRITE A
PROGRAM IN C TO CONVERT INFIX EXPRESSION TO POSTFIX EXPRESSION.










#include<stdio.h>

#include<conio.h>

#include<ctype.h>




char in[20],post[20],stack[20];

int top=-1,p=-1;




void push(char c)

                {

                stack[++top]=c;

                }







char pop()

                {

                return
stack[top--];

                }




int pred(char c)

                {

                int
p;

                switch(c)

                                {

                                case
'^':p=3;

                                break;

                                case
'%':

                                case
'/':

                                case
'*':p=2;

                                break;

                                case
'+':

                                case
'-':p=1;

                                break;

                                default
:p=0;

                                break;




                                }

                return
p;

                }







void main()

                {

                int
i;

                char
c;

                clrscr();




                printf("\n
Enter the Infix Expression : ");

                gets(in);

                for(i=0;in[i];i++)

                                {

                                if(isalpha(in[i]))

                                                post[++p]=in[i];

                                else

                                                {

                                                if(in[i]=='(')

                                                                push(in[i]);

                                                else
if(in[i]==')')

                                                                {

                                                                while(stack[top]!='(')

                                                                                post[++p]=pop();

                                                                top--;

                                                                }

                                                else

                                                                {

                                                                                while((pred(in[i])<=pred(stack[top]))&&(top>-1))

                                                                                {

                                                                                post[++p]=pop();

                                                                                }

                                                                                push(in[i]);




                                                                }

                                                }

                                }




                while(top>=0)

                                                post[++p]=pop();







                post[++p]=NULL;

                printf("\n\nThe
Postfix Expression is : ");

                for(i=0;post[i];i++)

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

                getch();

                }
















Q.12)WRITE A
PROGRAM IN C TO CONVERT INFIX EXPRESSION TO PREFIX EXPRESSION.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<string.h>

#define max 30

#define operand 10

#define OPERATOR 20

#define leftpara 30

#define rightpara 40

typedef struct prestk

{

int top;

char stack[max];

}stack;

void init(stack *st)

{

                st->top=-1;

}

void push(stack *st,char c)

{

st->top++;

st->stack[st->top]=c;

}

char pop(stack *st)

{

                char
c;

                c=st->stack[st->top];

                st->top--;

                return
c;

}

int getprec(char c)

{

                switch(c)

                {

                                case
')' : return 0;

                                case
'+' :

                                case
'-' : return 1;

                                case
'*' :

                                case
'/' :

                                case
'%' : return 2;

                                case
'^' : return 3;

                }

}

int gettype(char c)

{

                switch(c)

                {

                                case
'+':

                                case
'-':

                                case
'*':

                                case
'/':

                                case
'^':

                                case
'%': return OPERATOR;

                                case
'(': return leftpara;

                                case
')': return rightpara;

                                default
: return operand;

                }

}

void main()

{

stack stk;

char inf[max],ch,pre[max];

int l,i,k=0,pr;

clrscr();

init(&stk);

printf("\nEnter an infix expression : ");

gets(inf);

l=strlen(inf);

for(i=l-1;i>=0;i--)

{

                switch(gettype(inf[i]))

                {

                                case
operand : pre[k++]=inf[i];

                                break;

                                case
OPERATOR : pr=getprec(inf[i]);

                                while(pr<getprec(stk.stack[stk.top])
&& stk.top!=-1)

                                                pre[k++]=pop(&stk);

                                push(&stk,inf[i]);

                                break;

                                case
rightpara : push(&stk,inf[i]);

                                break;

                                case
leftpara : while((ch=pop(&stk))!=')')

                                                                                pre[k++]=ch;

                }

}

printf("\n\nThe corresponing Prefix Expression is
: ");

while(stk.top!=-1)

                pre[k++]=pop(&stk);

pre[k]='\0';

strrev(pre);

puts(pre);

getch();

}










Q.13)WRITE A
PROGRAM IN C TO EVALUATE A POSTFIX EXPRESSION.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#include<math.h>

#include<ctype.h>

#define MAX 50




struct postfix

{

 int stack[MAX];

 int top,nn;

 char *s;

};

void initpostfix(struct postfix*);

void setexpr(struct postfix*,char*);

void push(struct postfix*,int);

int pop(struct postfix*);

void calculate(struct postfix*);

void show(struct postfix);

void main()

{

 struct postfix
q;

 char expr[MAX];

 clrscr();

 initpostfix(&q);

 printf
("\nEnter the Postfix Expression to be evaluated : ");

 gets(expr);

 setexpr(&q,expr);

 calculate(&q);

 show(q);

 getch();

}

void initpostfix(struct postfix*p)

{

p->top=-1;

}




void setexpr(struct postfix*p,char *str)

{

p->s=str;

}




void push(struct postfix*p, int item)

{

 if(p->top==MAX-1)

 printf("stack is full\n");




 else

 {

 p->top++;

 p->stack[p->top]=item;

 }

}

 int pop(struct
postfix*p)

{

 int data;

 if(p->top==-1)

 {

 printf("stack
is empty");

 return NULL;

 }

 data=p->stack[p->top];

 p->top--;

 return data;

}

void calculate(struct postfix*p)

{

                int
n1,n2,n3;

                while(*(p->s))

                 {

                  if(*p->s==' '||*(p->s)=='\t')

                  { 
p->s++;

                  continue;

                  }

                 if(isdigit(*(p->s)))

                 {

                 p->nn=*(p->s)-'0';

                 push(p,p->nn);

                 }

                 else

                 {

                  n1=pop(p);

                  n2=pop(p);

                  switch(*(p->s))

                     {

                                case
'+':   n3=n2+n1;

                                                 break;

                                case
'-':   n3=n2-n1;

                                                break;

                                case
'/':  n3=n2/n1;

                                                break;

                                case '*':  n3=n2*n1;

                                                break;

                                case
'%':  n3=n2%n1;

                                                 break;

                                case
'^':   n3=pow(n2,n1);

                                                break;

                                default:                   printf(" unknown operator");

                                                 exit(1);

                     }

                  push(p,n3);

                  }

                  p->s++;

                  }

                  }




 void
show(struct postfix p)

  {

                                p.nn=pop(&p);

                                printf("\n\nResult
= %d",p.nn);

 }

























 Q.1) WRITE A
PROGRAM IN C TO SORT AN ARRAY USING INSERTION SORT.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void insort(int a[], int size)

{

 int i, j, t;

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

  {

                                t
= a[i];

                                j
= i;

                                while
((j > 0) && (a[j-1] > t))

                                 {

                                  a[j] = a[j-1];

                                  j = j - 1;

                                 }

                                a[j]
= t;

  }

}







void main()

{

 int *a,i,n;

 printf("\nEnter the length of the array
:");

 scanf("%d",&n);

 a=(int*)malloc(n * sizeof(int));

 printf("\nEnter the elements of the array
:\n");

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

  {

                printf("Enter
%d element : ",i+1);

                scanf("%d",&a[i]);

  }

 insort(a,n);

 printf("\n\nSorted array : ");

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

 printf(" 
%d",a[i]);

 getch();

}










Q.2) WRITE A
PROGRAM IN C TO SORT AN ARRAY USING SELECTION SORT.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>







void selsort(int a[], int size)

{

 int i, j, min,
temp;

 for (i=0;
i<(size-1); i++)

  {

                min
= i;

                for
(j=i+1; j<size; j++)

                 {

                  if (a[j] < a[min])

                  min = j;

                 }

                temp
= a[i];

                a[i]
= a[min];

                a[min]
= temp;

  }

}




void main()

{

 int *a,i,n;

 printf("\nEnter the length of the array
:");

 scanf("%d",&n);

 a=(int*)malloc(n * sizeof(int));

 printf("\nEnter the elements of the array
:\n");

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

  {

                printf("Enter
%d element : ",i+1);

                scanf("%d",&a[i]);

  }

 selsort(a,n);

 printf("\n\nSorted array : ");

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

 printf(" 
%d",a[i]);

 getch();

}




Q.3) WRITE A
PROGRAM IN C TO SORT AN ARRAY USING QUICK  SORT.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void quicksort(int *,int,int);

int split(int *,int,int);




void main()

{

                int
*a,i,n;

                clrscr();

                printf("Enter
the no. of  elements in the array:
");

                scanf("%d",&n);

                a
= (int *)malloc(n*sizeof(int));

                printf("\nEnter
the elements of the array : \n");

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

                 scanf("%d",&a[i]);




                quicksort(a,0,n-1);

                printf("\n\nThe
array after sorting is :");

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

                   printf("  %d",a[i]);




                getch();

}




void quicksort(int a[],int lower,int upper)

{

                int
i;

                if(upper>lower)

                {

                                i=split(a,lower,upper);

                                quicksort(a,lower,i-1);

                                quicksort(a,i+1,upper);

                }

}




int split(int a[],int lower,int upper)

{

                int
i,p,q,t;

                p=lower+1;

                q=upper;

                i=a[lower];




                while(q>=p)

                {

                                while(a[p]<i)

                                p++;




                                while(a[q]>i)

                                q--;




                                if(q>p)

                                {

                                                t=a[p];

                                                a[p]=a[q];

                                                a[q]=t;

                                }

                }

                t=a[lower];

                a[lower]=a[q];

                a[q]=t;

                return
q;

}




Q.4) WRITE A
PROGRAM IN C TO IMPLEMENT BINARY SEARCH IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void main()

{

 int *a, i, n,
x, low, mid, high;

 clrscr();




 printf("Enter the length of the array :
");

 scanf("%d",&n);

 a = (int
*)malloc(n * sizeof(int));




 printf("\n\nEnter the Array elements in
ASCENDING ORDER : \n");

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

                scanf("%d",&a[i]);




 printf("\n\nEnter the element to be
searched\n");

 scanf("%d", &x);




 low=1;

 high=n;




 do

  {

                mid=
(low + high) / 2;

                if
( x < a[mid] )

                                high
= mid - 1;

                else
if ( x > a[mid])

                                low
= mid + 1;

  } while(
x!=a[mid] && low <= high);




 if( x == a[mid]
)

                printf("\n\n....SUCCESSFUL
SEARCH....\nIt is at position %d",(mid+1));




 else

                printf("\n\nSearch
is FAILED");

}




Q.5) WRITE A
PROGRAM IN C TO IMPLEMENT STACK IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void stackpush (int *a,int &n)

{

 int i,x;

 if(n>10)

  {

 
printf("Cannot be inserted");

  return;

  }

 n++;




  printf("\nEnter
the element to be inserted : ");

 
scanf("%d",&x);

  a[n-1]=x;

 
printf("The array now is : ");

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

 
printf("%d ",a[i]);

  getch();

}




int stackpop (int a[],int &n)

{

 int x;

 if(n==0)

 
printf("Stack Underflow ");




 else

  {

  x=a[n-1];

  n--;

  }

 return(x);

}










void main()

{

 int *a,n,c,i,x;

 a = (int
*)malloc(10 * sizeof(int));

 clrscr();

 printf("Enter no. of elements of array :
");

 scanf("%d",&n);




 printf("\nEnter the array
elements:\n");

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

  scanf("%d",&a[i]);




 st:




 clrscr();

 printf("\n\t1.Stack Push");

 printf("\n\t2.Stack Pop");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter your Choice : ");

 scanf("%d",&c);

 switch (c)

 {

  case 1 :
stackpush(a,n);

                   break;




  case 2 :
x=stackpop(a,n);

                   printf("\nThe element popped out is
%d",x);

                   getch();

                   break;




  case 3 :
printf("\n\nThe elements in the array : ");

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

                   printf("%d ",a[i]);

                   getch();

                   break;




   case 4 :
exit(0);




   default : printf("\n\n....Wrong
Choice ....");

                     getch();

                     break;

  }

  goto st;

}







Q.6)  WRITE A PROGRAM IN C TO IMPLEMENT STACK IN A
LINKED LIST.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




typedef struct linkedlist

{

 int data;

 struct linkedlist
*link;

}node;




node *top=NULL;




void stackpush()

{

 node *temp;

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

 printf("\nEnter the node data : ");

 scanf("%d",&temp->data);

 temp->link=top;

 top=temp;

}







int stackpop()

{

 node *p,*pre;

 int temp;

 p=top;

 if(p->link==NULL)

  {

                free(p);

                top=NULL;

                return
0;

  }

 else

  {

                pre=p;

                p=p->link;

                top=p;

                temp=pre->data;

                free(pre);

                return(temp);

  }




}




void display()

{

 node *ptr;

 int i=0;

 if(top==NULL)

                printf("\n....Empty
list....");

 else

  {

                ptr=top;

                while(ptr)

                 {

                  printf("\nNode %d data :
%d",i+1,ptr->data);

                  ptr=ptr->link;

                  i++;

                 }

  }

 getch();

}







void main()

{

 int c,x;

 clrscr();




 st:




 clrscr();

 printf("\n\t1.Stack Push");

 printf("\n\t2.Stack Pop");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter your Choice : ");

 scanf("%d",&c);




 switch (c)

 {

  case 1 :
stackpush();

                                                  break;




  case 2 :
x=stackpop();

                                                  printf("\nThe element popped out is
%d",x);

                                                  getch();

                                                  break;




  case 3 :
display();

                                                  break;




  case 4 :
exit(0);




  default :
printf("\n\n....Wrong Choice ....");

                                                                getch();

 }




 goto st;

}













Q.7) WRITE
PROGRAM IN C TO IMPLEMENT QUEUE IN AN ARRAY.




#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




void queueins (int *a,int &n)

{

 int i,x;

 if(n>10)

  {

 
printf("Cannot be inserted");

  return;

  }

  n++;




 
printf("\nEnter the element to be inserted : ");

 
scanf("%d",&x);

  a[n-1]=x;

 
printf("The array now is : ");

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

 
printf("%d ",a[i]);

  getch();

}




int queuedel (int a[],int &n)

{

 int i,x;

 if(n==0)

 
printf("Queue Underflow ");




 else

  {

   x=a[0];

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

   a[i]=a[i+1];

   n--;

   }

  return(x);

}










void main()

{

 int *a,n,c,i,x;

 a = (int
*)malloc(10 * sizeof(int));

 clrscr();

 printf("Enter no. of elements of array :
");

 scanf("%d",&n);




 printf("\nEnter the array
elements:\n");

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

 
scanf("%d",&a[i]);




 st:




 clrscr();

 printf("\n\t1.Queue Insert");

 printf("\n\t2.Queue Delete");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter your Choice : ");

 scanf("%d",&c);




 switch (c)

 {

  case 1 :
queueins(a,n);

                   break;




  case 2 :
x=queuedel(a,n);

                   printf("\nThe element deleted is
%d",x);

                   getch();

                   break;




  case 3 :
printf("\n\nThe elements in the array : ");

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

                   printf("%d ",a[i]);

                   getch();

                   break;




   case 4 :
exit(0);




   default :
printf("\n\n....Wrong Choice ....");

                     getch();

                     break;

  }




  goto st;

}
















Q.8) WRITE
PROGRAM IN C TO IMPLEMENT QUEUE IN A LINKED LIST.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>




typedef struct linkedlist

{

 int data;

 struct
linkedlist *link;

}node;




node *top=NULL;




void qins()

{

 node
*temp,*ptr;

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

 printf("Enter the node data : ");

 scanf("%d",&temp->data);

 if(top==NULL)

                {

                temp->link=NULL;

                top=temp;

                }

 else

                {

                 ptr=top;

                 while(ptr->link)

                                ptr=ptr->link;

                 temp->link=NULL;

                 ptr->link=temp;




                }

}







int qdel()

{

 node *p,*pre;

 int temp;

 p=top;

 if(p->link==NULL)

  {

                free(p);

                top=NULL;

                return
0;

  }

 else

  {

                pre=p;

                p=p->link;

                top=p;

                temp=pre->data;

                free(pre);

                return(temp);

  }




}




void display()

{

 node *ptr;

 int i=0;

 if(top==NULL)

                printf("\n....Empty
list....");

 else

  {

                ptr=top;

                while(ptr)

                 {

                  printf("\nNode %d data :
%d",i+1,ptr->data);

                  ptr=ptr->link;

                  i++;

                 }

  }

 getch();

}







void main()

{

 int c,x;

 clrscr();




 st:




 clrscr();

 printf("\n\t1.Queue Insert");

 printf("\n\t2.Queue Delete");

 printf("\n\t3.Display");

 printf("\n\t4.Exit");

 printf("\n\nEnter
your Choice : ");

 scanf("%d",&c);

 switch (c)

 {

  case 1 :
qins();

                                                  break;




  case 2 :
x=qdel();

                                                  printf("\nThe element deleted is
%d",x);

                                                  getch();

                                                  break;




  case 3 :
display();

                                                  break;




  case 4 :
exit(0);




  default : printf("\n\n....Wrong
Choice ....");

                                                                getch();

 }

 goto st;

}







Q.9) WRITE
PROGRAM IN C TO IMPLEMENT DOUBLE-ENDED QUEUE IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

#define max 10







int count(int *arr)

{

 int c=0,i;




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

 {

  if(arr[i]!=0)

    c++;

 }




 return c;

}







void addatbeg(int *arr,int item,int *pfront,int
*prear)

{

 int i,k,c;

 if(*pfront==0
&& *prear==max-1)

 {

 
printf("\nDeque is Full...\n");

  return;

 }




 if(*pfront==-1)

 {

 
*pfront=*prear=0;

  arr[*pfront]=item;

  return;

 }




 if(*prear!=max-1)

 {

   
c=count(arr);

    k=*prear+1;




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

    {

    
arr[k]=arr[k-1];

     k--;

    }

    arr[k]=item;

    *pfront=k;

    (*prear)++;

 }




 else

  {

    (*pfront)--;

   
arr[*pfront]+item;

  }

}




void addatend (int *arr,int item,int *pfront,int
*prear)

{

 int i,k;




 if (*pfront==0
&& *prear==max-1)

 {

 
printf("\nDeque s full..");

  return;

 }




 if(*pfront ==
-1)

 {

  *prear =
*pfront=0;

  arr[*prear]=
item;

  return;

 }




 if(*prear==max-1)

 {

   k=*pfront-1;




  
for(i=*pfront-1;i<*prear;i++)

    {

     k=i;

    
if(k==max-1)

      arr[k]=0;

     else

     
arr[k]=arr[i+1];

     }




   (*prear)--;

   (*pfront)--;

 }




 (*prear)++;

 arr[*prear]=item;

}




int delatbeg (int *arr,int *pfront,int *prear)

{

 int item;

 if(*pfront==-1)

  {

  
printf("\nDeque is Empty...");

   return (0);

  }




 item =
arr[*pfront];

 arr[*pfront]=0;




 if(*pfront==*prear)

  
*pfront=*prear=-1;




 else

  ( *pfront)++;




 return item;

}







int delatend (int *arr,int *pfront,int *prear)

{

 int item;

 if(*pfront==-1)

  {

  
printf("\nDeque is Empty...");

   return (0);

  }




 item =
arr[*prear];

 arr[*prear]=0;

 (*prear)--;




 if(*prear==-1)

   *pfront=-1;




 return item;

}




void display(int *arr,int *pfront,int *prear)

{

 int i;




 printf("\nfront->  ");

 for(i=(*pfront);i<=(*prear);i++)

 
printf("  %d",arr[i]);

 printf(" 
<-rear");

}













void main()

{

 int a[max];

 int
front=-1,rear=-1,i,x,aa,bb;

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

    a[i]= 0;

 top:

 clrscr();

 printf("\n\t1.Add at Beg");

 printf("\n\t2.Add at End");

 printf("\n\t3.Delete from Beg");

 printf("\n\t4.Delete from End");

 printf("\n\t5.Display");

 printf("\n\t...Press other key for
exit...");

 printf("\n\nEnter your choice : ");

 scanf("%d",&x);

 switch (x)

 {

  case 1 : printf("\nEnter
element : ");

                   scanf("%d",&aa);

                   addatbeg(a,aa,&front,&rear) ;

                   printf("\n....Item Inserted at
Beg....");

                   getch();

                   break;




  case 2:  printf("\nEnter element : ");

                   scanf("%d",&bb);

                   addatend(a,bb,&front,&rear) ;

                   printf("\n....Item Inserted at
End....");

                   getch();

                   break;




  case 5:   printf("\nElements in a Deque :
");

                    display(a,&front,&rear);

                    getch();

                    break;




  case 3:   i=delatbeg(a,&front,&rear);

                    printf("\nItem Extracted :
%d",i);

                    getch();

                    break;




  case 4:   i=delatend(a,&front,&rear);

                    printf("\nItem Extracted :
%d",i);

                    getch();

                    break;




  default :
exit(0);

 }

goto top;

}







Q.10) WRITE
PROGRAM IN C TO IMPLEMENT PRIORITY QUEUE IN AN ARRAY.







#include<stdio.h>

#include<conio.h>

#include<stdlib.h>

void insert();

void del();

void display();




struct node

 {

  int priority;

  int info;

  struct node
*next;

 }*start,*q,*temp,*a;




void main()

{

 int ch;

 top :

 clrscr();

 printf("\n\n\t[1] INSERTION\n\t[2]
DELETION\n\t[3] DISPLAY\n\t[4] EXIT\n");

 printf("\nEnter your Choice : ");

 scanf("%d",&ch);

 switch(ch)

  {

   case 1 :
insert();

                    break;




   case 2 :
del();

                    break;




   case 3 :
display();

                    break;




   case 4 :
exit(0);




   default:
printf("\n\n....Wrong Choice....");

                    getch();

  }

  goto top;

}




void insert()

{

 int item,pr;

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

 printf("\n\nEnter the element to be
inserted : ");

 scanf("%d",&item);

 printf("\nEnter its Priority : ");

 scanf("%d",&pr);

 a->info=item;

 a->priority=pr;




 if(start==NULL
|| pr<(start->priority))

  {

  
a->next=start;

   start=a;

  }




 else

  {

   q=start;




  
while(q->next != NULL && (q->next->priority) <= pr)

   q=q->next;




  
a->next=q->next;

   q->next=a;

  }

}




void del()

{

 if(start==NULL)

   
printf("\n....UnderFlow\n");




 else

 {

  a=start;

 
printf("\nDeleted item is %d",a->info);

 
start=start->next;

  free(start);

 }

}




void display()

{

 temp=start;

 if(start==NULL)

  
printf("\n....Queue is Empty....");




 else

  {

  
printf("\n\n\nQueue is as follows :\n");

  
printf("\n\n\t\t  ITEM  || PRIORITY\n");

  
printf("\t\t---------------------");

  
while(temp!=NULL)

    {

    
printf("\n\t\t   %2d   ||  
%2d",temp->info,temp->priority);

    
temp=temp->next;

    }

  }

  getch();

}




Q.11)WRITE A
PROGRAM IN C TO CONVERT INFIX EXPRESSION TO POSTFIX EXPRESSION.










#include<stdio.h>

#include<conio.h>

#include<ctype.h>




char in[20],post[20],stack[20];

int top=-1,p=-1;




void push(char c)

                {

                stack[++top]=c;

                }







char pop()

                {

                return
stack[top--];

                }




int pred(char c)

                {

                int
p;

                switch(c)

                                {

                                case
'^':p=3;

                                break;

                                case
'%':

                                case
'/':

                                case
'*':p=2;

                                break;

                                case
'+':

                                case
'-':p=1;

                                break;

                                default
:p=0;

                                break;




                                }

                return
p;

                }







void main()

                {

                int
i;

                char
c;

                clrscr();




                printf("\n
Enter the Infix Expression : ");

                gets(in);

                for(i=0;in[i];i++)

                                {

                                if(isalpha(in[i]))

                                                post[++p]=in[i];

                                else

                                                {

                                                if(in[i]=='(')

                                                                push(in[i]);

                                                else
if(in[i]==')')

                                                                {

                                                                while(stack[top]!='(')

                                                                                post[++p]=pop();

                                                                top--;

                                                                }

                                                else

                                                                {

                                                                                while((pred(in[i])<=pred(stack[top]))&&(top>-1))

                                                                                {

                                                                                post[++p]=pop();

                                                                                }

                                                                                push(in[i]);




                                                                }

                                                }

                                }




                while(top>=0)

                                                post[++p]=pop();







                post[++p]=NULL;

                printf("\n\nThe
Postfix Expression is : ");

                for(i=0;post[i];i++)

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

                getch();

                }
















Q.12)WRITE A
PROGRAM IN C TO CONVERT INFIX EXPRESSION TO PREFIX EXPRESSION.







#include<stdio.h>

#include<stdlib.h>

#include<string.h>

#define max 30

#define operand 10

#define OPERATOR 20

#define leftpara 30

#define rightpara 40

typedef struct prestk

{

int top;

char stack[max];

}stack;

void init(stack *st)

{

                st->top=-1;

}

void push(stack *st,char c)

{

st->top++;

st->stack[st->top]=c;

}

char pop(stack *st)

{

                char
c;

                c=st->stack[st->top];

                st->top--;

                return
c;

}

int getprec(char c)

{

                switch(c)

                {

                                case
')' : return 0;

                                case
'+' :

                                case
'-' : return 1;

                                case
'*' :

                                case
'/' :

                                case
'%' : return 2;

                                case
'^' : return 3;

                }

}

int gettype(char c)

{

                switch(c)

                {

                                case
'+':

                                case
'-':

                                case
'*':

                                case
'/':

                                case
'^':

                                case
'%': return OPERATOR;

                                case
'(': return leftpara;

                                case
')': return rightpara;

                                default
: return operand;

                }

}

void main()

{

stack stk;

char inf[max],ch,pre[max];

int l,i,k=0,pr;

clrscr();

init(&stk);

printf("\nEnter an infix expression : ");

gets(inf);

l=strlen(inf);

for(i=l-1;i>=0;i--)

{

                switch(gettype(inf[i]))

                {

                                case
operand : pre[k++]=inf[i];

                                break;

                                case
OPERATOR : pr=getprec(inf[i]);

                                while(pr<getprec(stk.stack[stk.top])
&& stk.top!=-1)

                                                pre[k++]=pop(&stk);

                                push(&stk,inf[i]);

                                break;

                                case
rightpara : push(&stk,inf[i]);

                                break;

                                case
leftpara : while((ch=pop(&stk))!=')')

                                                                                pre[k++]=ch;

                }

}

printf("\n\nThe corresponing Prefix Expression is
: ");

while(stk.top!=-1)

                pre[k++]=pop(&stk);

pre[k]='\0';

strrev(pre);

puts(pre);

getch();

} 




Q.13) PROGRAM IN C TO EVALUATE A POSTFIX EXPRESSION.




#include<stdio.h>

#include<stdlib.h>

#include<math.h>

#include<ctype.h>

#define MAX 50




struct postfix

{

 int stack[MAX];

 int top,nn;

 char *s;

};

void initpostfix(struct postfix*);

void setexpr(struct postfix*,char*);

void push(struct postfix*,int);

int pop(struct postfix*);

void calculate(struct postfix*);

void show(struct postfix);

void main()

{

 struct postfix
q;

 char expr[MAX];

 clrscr();

 initpostfix(&q);

 printf
("\nEnter the Postfix Expression to be evaluated : ");

 gets(expr);

 setexpr(&q,expr);

 calculate(&q);

 show(q);

 getch();

}

void initpostfix(struct postfix*p)

{

p->top=-1;

}




void setexpr(struct postfix*p,char *str)

{

p->s=str;

}




void push(struct postfix*p, int item)

{

 if(p->top==MAX-1)

 printf("stack is full\n");




 else

 {

 p->top++;

 p->stack[p->top]=item;

 }

}

 int pop(struct
postfix*p)

{

 int data;

 if(p->top==-1)

 {

 printf("stack
is empty");

 return NULL;

 }

 data=p->stack[p->top];

 p->top--;

 return data;

}

void calculate(struct postfix*p)

{

                int
n1,n2,n3;

                while(*(p->s))

                 {

                  if(*p->s==' '||*(p->s)=='\t')

                  { 
p->s++;

                  continue;

                  }

                 if(isdigit(*(p->s)))

                 {

                 p->nn=*(p->s)-'0';

                 push(p,p->nn);

                 }

                 else

                 {

                  n1=pop(p);

                  n2=pop(p);

                  switch(*(p->s))

                     {

                                case
'+':   n3=n2+n1;

                                                 break;

                                case
'-':   n3=n2-n1;

                                                break;

                                case
'/':  n3=n2/n1;

                                                break;

                                case '*':  n3=n2*n1;

                                                break;

                                case
'%':  n3=n2%n1;

                                                 break;

                                case
'^':   n3=pow(n2,n1);

                                                break;

                                default:                   printf(" unknown operator");

                                                 exit(1);

                     }

                  push(p,n3);

                  }

                  p->s++;

                  }

                  }




 void
show(struct postfix p)

  {

                                p.nn=pop(&p);

                                printf("\n\nResult
= %d",p.nn);

 }