Generate n of random integers in a given range and sort them using quick sort. Apply both binary search and Interpolation search to locate a given integer and compare the search algorithms based on the number of comparisons/probes required for a successful as well as unsuccessful search..

Generate n of random integers in a given range and sort them using quick sort. Apply both binary search and Interpolation search to locate a given integer and compare the search algorithms based on the number of comparisons/probes required for a successful as well as unsuccessful search..

#include<stdlib.h>

#include<conio.h>

#include<stdio.h>

void quicksort(int [10],int,int);

void interpolation(int [10],int,int,int);

main()

{

     int x[10],i,n,e;

     clrscr();

     printf("Enter the Size : ");

     scanf("%d",&n);

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

     {

x[i]=rand()%100;

     }

     printf("Before Sorting        : ");

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

printf("%d\t",x[i]);

     quicksort(x,0,n-1);

     printf("\nAfter Quick Sorting : ");

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

       printf("%d\t",x[i]);

     printf("\nEnter the Search Key  : ");

     scanf("%d",&e);

     interpolation(x,0,n-1,e);

     b_search(x,0,n-1,e);

     getch();

}

void quicksort(int x[10],int first, int last)

{

    int pivot,j,temp,i;

    if(first<last)

    {

pivot=first;

i=first;

j=last;

while(i<j)

{

    while(x[i]<=x[pivot]&&i<last)

i++;

    while(x[j]>x[pivot])

j--;

    if(i<j)

    {

temp=x[i];

x[i]=x[j];

x[j]=temp;

    }

}

temp=x[pivot];

x[pivot]=x[j];

x[j]=temp;

quicksort(x,first,j-1);

quicksort(x,j+1,last);

    }

}

void interpolation(int a[10],int low,int high,int item)

{

     int mid,f=0,i,c=0;

     printf("\nInterpolation Search :\n");

     while(low<=high)

     {

     c++;

     mid=low+(high-low)*((item-a[low])/(a[high]-a[low]));

     if(a[mid]==item)

     {

 printf("\nElements found at POS %d ",mid+1);

 f=1;

 break;

     }

     else if(item<a[mid])

 high=mid-1;

     else

 low=mid+1;

     }

     if(f==0)

 printf("\nThe Element is not found");

     printf("\nSuccess Comparsions : %d",c);

}

b_search(int a[10],int top,int bot,int item)

{

     int mid,flag=0,loc,count=0,i;

     printf("\n\nBianary Search Result :\n");

     while(top<=bot)

     {

 count++;

 mid=(top+bot)/2;

 if(item==a[mid])

 {

      loc=mid;

      flag=1;

      break;

 }

 else if(item<a[mid])

      bot=mid-1;

 else

      top=mid+1;

     }

 if(flag==1)

      printf("\nElement found at POS : %d",loc+1);

 else

      printf("\nThe Element is not found ");

 printf("\nSuccess Comparisions : %d",count);

}

Evaluation of Post-fix Expression

ADT Stack implementation and use  it for evaluation of Post-fix Expression

/*Progam for Postfix Evalution */
#define SIZE 50            /* Size of Stack */
#include <ctype.h>
#include<stdio.h>
int s[SIZE];
int top=-1;       /* Global declarations */

push(int elem)
{                       /* Function for PUSH operation */
 s[++top]=elem;
}

int pop()
{                      /* Function for POP operation */
 return(s[top--]);
}

main()
{                         /* Main Program */
 char pofx[50],ch;
 int i=0,op1,op2;
 printf("\n\nRead the Postfix Expression ? ");
 scanf("%s",pofx);
 while( (ch=pofx[i++]) != '\0')
 {
  if(isdigit(ch))
push(ch-'0'); /* Push the operand */
  else
  {        /* Operator,pop two  operands */
op2=pop();
op1=pop();
switch(ch)
   {
case '+':push(op1+op2);break;
case '-':push(op1-op2);break;
   case '*':push(op1*op2);break;
   case '/':push(op1/op2);break;
   }
  }
 }
 printf("\n Given Postfix Expn: %s\n",pofx);
 printf("\n Result after Evaluation: %d\n",s[top]);
}

Merge Sort Program

Merge Sort Program

#include<stdio.h>
#define MAX 50

void mergeSort(int arr[],int low,int mid,int high);
void partition(int arr[],int low,int high);

int main(){

int merge[MAX],i,n;

printf("Enter the total number of elements: ");
scanf("%d",&n);

printf("Enter the elements which to be sort: ");
for(i=0;i<n;i++){
scanf("%d",&merge[i]);
}

partition(merge,0,n-1);

printf("After merge sorting elements are: ");
for(i=0;i<n;i++){
printf("%d ",merge[i]);
}

return 0;
}

void partition(int arr[],int low,int high){

int mid;

if(low<high){
mid=(low+high)/2;
partition(arr,low,mid);
partition(arr,mid+1,high);
mergeSort(arr,low,mid,high);
}
}

void mergeSort(int arr[],int low,int mid,int high){

int i,m,k,l,temp[MAX];

l=low;
i=low;
m=mid+1;

while((l<=mid)&&(m<=high)){

if(arr[l]<=arr[m]){
temp[i]=arr[l];
l++;
}
else{
temp[i]=arr[m];
m++;
}
         i++;
}

if(l>mid){
         for(k=m;k<=high;k++){
temp[i]=arr[k];
             i++;
}
    }
else{
         for(k=l;k<=mid;k++){
temp[i]=arr[k];
             i++;
}
    }

    for(k=low;k<=high;k++){
arr[k]=temp[k];
    }
}

Quick Sort Program

Quick Sort Program 

 #include<stdio.h>

void quicksort(int [10],int,int);

int main(){
  int x[20],size,i;

  printf("Enter size of the array: ");
  scanf("%d",&size);

  printf("Enter %d elements: ",size);
  for(i=0;i<size;i++)
scanf("%d",&x[i]);

  quicksort(x,0,size-1);

  printf("Sorted elements: ");
  for(i=0;i<size;i++)
printf(" %d",x[i]);

  return 0;
}

void quicksort(int x[10],int first,int last){
int pivot,j,temp,i;

 if(first<last){
pivot=first;
i=first;
j=last;

while(i<j){
while(x[i]<=x[pivot]&&i<last)
 i++;
while(x[j]>x[pivot])
 j--;
if(i<j){
 temp=x[i];
x[i]=x[j];
x[j]=temp;
}
}

temp=x[pivot];
x[pivot]=x[j];
x[j]=temp;
quicksort(x,first,j-1);
quicksort(x,j+1,last);

}
}

Circular Queue Using Double linked list

Circular Queue Using Double linked list

#include<stdio.h>
#include<conio.h>
#include<stdlib.h>

struct node
{
int data;
struct node *next;
struct node *prev;
};

struct node *head=NULL,*temp;

void insert(int ele)
{
struct node *tempe;
temp=(struct node *)malloc(sizeof(struct node));
temp->data=ele;
temp->next=NULL;
if(head==NULL)
{
head=temp;
temp->next=head;
}
else
{
tempe=head;
while(tempe->next!=head)
{
tempe=tempe->next;
}
tempe->next=temp;
temp->next=head;
      temp->prev=tempe;
}
}

void display()
{
struct node *temp1;
temp1=head;
while(temp1->next!=head)
{
printf("%d\t",temp1->data);
temp1=temp1->next;
}
printf("%d",temp1->data);
}


void del(int pos)
{
struct node *temp1,*temp2;

if(head==NULL)
{
printf("Circular Queue is Emplty");
}
else if(pos==1)
{
temp1=head;
temp2=head;
while(temp1->next!=head)
{
temp1=temp1->next;
}
head=head->next;
temp1->next=head;
free(temp2);
}
else
{
temp2=head;
while(--pos!=0)
{
temp1=temp2;
temp2=temp2->next;

}
temp1->next=temp2->next;
free(temp2);
}
}
  void main()
{
int n,e,ch;
head=NULL;
while(1)
{
printf("\n1.Insert\n2.Delete\n3.Display\n4.Exit");
printf("\nEnter your Choice : ");
scanf("%d",&ch);
switch(ch)
{
case 1: printf("\nEnter the Number : ");
scanf("%d",&n);
insert(n);break;
case 2: printf("\nEnter the Position for Deleting : ");
scanf("%d",&e);
del(e);  break;
case 3:
display();  break;
case 4: exit(0);   break;
default: printf("\nYour Choice is Wrong");
}
}

}

Queue Operations using Single Linked List

Queue Operations using Single Linked List

#include<stdio.h>
#include<conio.h>
#include <stdlib.h>    

struct node
{
int data;
struct node *next;
};
struct node *front=NULL,*rear=NULL;

void insert()
{
int item;
struct node *temp,*tempe;

printf("\nEnter the Number : ");
scanf("%d",&item);
temp=(struct node *) malloc(sizeof(struct node));

temp->data=item;
temp->next=NULL;

if(rear==NULL)
{
front=temp;
rear=temp;
}
else
{
rear->next=temp;
rear=temp;
}
}



void del()
{


if(front==NULL)
printf("\Queue is Empty ");
else if(rear==front)
front=rear=NULL;
else
{
printf("%d is Deleted ",front->data);
front=front->next;
}
}

void display()
{
struct node *temp;

if(front==NULL && rear==NULL)
printf("\nQueue is Empty");
else
{
temp=front;
printf("\n Elements are : ");
while(temp->next!=NULL)
{
printf("%d\t",temp->data);
temp=temp->next;
}
printf("%d",temp->data);
}
}

void main()
{
int ch;
while(1)
{
printf("\n1.Insert\n2.Delete\n3.Display\n4.Exit");
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);break;
            default: printf("\nYour Choice is Woring");
}
}

}

Infix to Postfix Conversion using stack in C

Infix to Postfix Conversion using stack in C

#define SIZE 50 /* Size of Stack */
#include<string.h>
#include <ctype.h>
#include<stdio.h>
char s[SIZE]; int top=-1; /* Global declarations */
push(char elem)
{ /* Function for PUSH operation */
s[++top]=elem;
}
char pop()
{ /* Function for POP operation */
return(s[top--]);
}
int pr(char elem)
{ /* Function for precedence */
switch(elem)
{
case '#': return 0;
case ')': return 1;
case '+':
case '-': return 2;
case '*':
case '/':return 3;
}
}
main()
{ /* Main Program */
char infx[50],prfx[50],ch,elem;
int i=0,k=0;
printf("\n\nRead the Infix Expression ? ");
scanf("%s",infx);
push('#');

while( (ch=infx[i++]) != '\0')
{
if( ch == ')')
push(ch);
else if(isalnum(ch))
prfx[k++]=ch;
else if( ch == '(')
{
while( s[top] != ')')
prfx[k++]=pop();
elem=pop(); /* Remove ) */
}
else
{ /* Operator */
while( pr(s[top]) >= pr(ch) )
prfx[k++]=pop(); push(ch);
}
}
while( s[top] != '#') /* Pop from stack till empty */
prfx[k++]=pop();
prfx[k]='\0'; /* Make prfx as valid string */

printf("\n\nGiven Infix Expn: %s \nPrefix Expn: %s\n",infx,prfx);
}

Infix to Prefix Conversion using Stacks in C

Infix to Prefix Conversion  using Stacks in C

Algorithm to Convert Infix to Prefix Form

Suppose A is an arithmetic expression written in infix form. The algorithm finds equivalent prefix expression B. Step 1. Push “)” onto STACK, and add “(“ to end of the A
Step 2. Scan A from right to left and repeat step 3 to 6 for each element of A until the STACK is empty
Step 3. If an operand is encountered add it to B
Step 4. If a right parenthesis is encountered push it onto STACK
Step 5. If an operator is encountered then:

a. Repeatedly pop from STACK and add to B each operator (on the top of STACK) which has same or higher precedence than the operator.

b. Add operator to STACK

Step 6. If left parenthesis is encontered then

a. Repeatedly pop from the STACK and add to B (each operator on top of stack until a left parenthesis is encounterd)

b. Remove the left parenthesis

Step 7. Exit

Program 

#define SIZE 50 /* Size of Stack */
#include<string.h>
#include <ctype.h>
#include<stdio.h>
char s[SIZE]; int top=-1; /* Global declarations */
push(char elem)
{ /* Function for PUSH operation */
s[++top]=elem;
}
char pop()
{ /* Function for POP operation */
return(s[top--]);
}
int pr(char elem)
{ /* Function for precedence */
switch(elem)
{
case '#': return 0;
case ')': return 1;
case '+':
case '-': return 2;
case '*':
case '/':return 3;
}
}
main()
{ /* Main Program */
char infx[50],prfx[50],ch,elem;
int i=0,k=0;
printf("\n\nRead the Infix Expression ? ");
scanf("%s",infx);
push('#');
strrev(infx);
while( (ch=infx[i++]) != '\0')
{
if( ch == ')')
push(ch);
else if(isalnum(ch))
prfx[k++]=ch;
else if( ch == '(')
{
while( s[top] != ')')
prfx[k++]=pop();
elem=pop(); /* Remove ) */
}
else
{ /* Operator */
while( pr(s[top]) >= pr(ch) )
prfx[k++]=pop(); push(ch);
}
}
while( s[top] != '#') /* Pop from stack till empty */
prfx[k++]=pop();
prfx[k]='\0'; /* Make prfx as valid string */
strrev(prfx);
strrev(infx);
printf("\n\nGiven Infix Expn: %s \nPrefix Expn: %s\n",infx,prfx);
}

Out Put:

C Program for Linear search

C Program for Linear search

#include<conio.h>
#include<stdio.h>
main()
{
int a[20], n,i,k, flag=0,loc;
printf("Enter the size of Array: ");
scanf("%d",&n);

printf("Enter the Numbers: ");
for(i=0;i<n;i++)
scanf("%d",&a[i]);

printf("Enter Searching Element: ");
scanf("%d",&k);

for(i=0;i<n;i++)
{
if(a[i]==k)
{
loc=i+1;
flag=1;
break;
}
}

if(flag==1)
printf("The element is found at location %d",loc);
else
printf("Element is not found");
}

Matrix Multiplication in c

    #include<conio.h>
    #include<stdio.h>
    main()
    {
    int a[5][5],b[5][5],c[5][5],m,n,o,p,i,j,sum,k;

    clrscr();
    printf("Enter the A Matrix size:\n");
    scanf("%d%d",&m,&n);

    printf("Enter the A Matrix Elements\n");
    for(i=0;i<m;i++)
    for(j=0;j<n;j++)
    scanf("%d",&a[i][j]);

    printf("Enter the B Matrix size:\n");
    scanf("%d%d",&o,&p);

    printf("Enter the B Matrix Elements\n");
    for(i=0;i<o;i++)
    for(j=0;j<p;j++)
    scanf("%d",&b[i][j]);

    if(n!=o)
    printf("The 1st Matrix Column are shoul equal to 2nd Matrix Rows");
    else
    {
        for(i=0;i<m;i++)
        {
            for(j=0;j<p;j++)
            {
                sum=0;
                for(k=0;k<n;k++)
                {
                    sum=sum+a[i][k]*b[k][j];
                }
                c[i][j]=sum;
            }
        }


    printf("Enter the AxB Matrix Elements\n");
    for(i=0;i<o;i++)
    {
        printf("\n");
        for(j=0;j<p;j++)
        printf("%d\t",c[i][j]);
    }

    }
    getch();
    }


Out Put:

Relational Operators in C Programing

#include<conio.h>
    #include<stdio.h>
    main()
    {
    int a,b,c;
    clrscr();
    printf("Enter 2 No's: ");
    scanf("%d%d",&a,&b);
    printf("\na = %d",a);
    printf("\nb = %d",b);
    printf("\na>b = %d",a>b);
    printf("\na<b = %d",a<b);
    printf("\na>=b = %d",a>=b);
    printf("\na<=b = %d",a<=b);
    printf("\na==b = %d",a==b);
    printf("\na!=b = %d",a!=b);
    getch();
    }