C program for Binary search operations

C program for Binary search operations

#define MAX_LEN 10

/* Non-Recursive function*/
void b_search_nonrecursive(int l[],int num,int ele)
{
int l1,i,j, flag = 0;
l1 = 0;
i = num-1;
while(l1 <= i)
{
j = (l1+i)/2;
if( l[j] == ele)
{
printf("\nThe element %d is present at position %d in list\n",ele,j);
flag =1;
break;
}
else
if(l[j] < ele)
l1 = j+1;
else
i = j-1;
}
if( flag == 0)
printf("\nThe element %d is not present in the list\n",ele);
}

/* Recursive function*/
int b_search_recursive(int l[],int arrayStart,int arrayEnd,int a)
{
int m,pos;
if (arrayStart<=arrayEnd)
{
m=(arrayStart+arrayEnd)/2;
if (l[m]==a)
return m;
else if (a return b_search_recursive(l,arrayStart,m-1,a);
else
return b_search_recursive(l,m+1,arrayEnd,a);
}
return -1;
}

void read_list(int l[],int n)
{
int i;
printf("\nEnter the elements:\n");
for(i=0;i scanf("%d",&l[i]);
}

void print_list(int l[],int n)
{
int i;
for(i=0;i printf("%d\t",l[i]);
}

/*main function*/
void main()
{
int l[MAX_LEN], num, ele,f,l1,a;
int ch,pos;

clrscr();
printf("\n\t\t\tMENU");
printf("\n=====================================================");
printf("\n[1] Binary Search using Recursion method");
printf("\n[2] Binary Search using Non-Recursion method");
printf("\n\nEnter your Choice:");
scanf("%d",&ch);

if(ch<=2 & ch>0)
{
printf("\nEnter the number of elements : ");
scanf("%d",&num);
read_list(l,num);
printf("\nElements present in the list are:\n\n");
print_list(l,num);
printf("\n\nEnter the element you want to search:\n\n");
scanf("%d",&ele);


switch(ch)
{
case 1:printf("\nRecursive method:\n");
pos=b_search_recursive(l,0,num,ele);
if(pos==-1)
{
printf("Element is not found");
}
else
{
printf("Element is found at %d position",pos);
}
getch();
break;

case 2:printf("\nNon-Recursive method:\n");
b_search_nonrecursive(l,num,ele);
getch();
break;
}
}
getch();
}

Related Links :

Queue as an array - Data Structure

Queue as an array - Data Structure 

Queue, being a linear data structure can be represented in various ways such as arrays and linked lists. Representing a queue as an array would have the same problem that we discussed in case of stacks. An array is a data structure that can store a fixed number of elements. The size of an array should be fixed before using it Queue, on the other hand keeps on changing as we remove elements from the front end or add new elements at the rear end. Declaring an array with a maximum size would solve this problem. The maximum size should be large enough for a queue to expand or shrink.

Related Links :

Stack as an array Data Structure

Stack as an array Data Structure

Stack contains an ordered collection of elements. An array is used to store ordered list of elements. Hence, it would be very easy to manage a stack if we represent it using an array. However, the problem with an array is that we are required to declare the size of the array before using it in a program. This means the size of an array should be fixed. Stack on the other hand does not have any fixed size. It keeps on changing, as the elements in stack are popped or pushed.

Though an array and a stack are totally different data structures, an array can be used to store the elements of a stack. We can declare the array with a maximum size large enough to manage a stack. As a result, the stack can grow or shrink within the space reserved for it.

Related Links :

Quick Sort Program in C | Data Structure Quick Sort using C Program | Quick Sort Algorithm in C

To Sort Elements Of The Array Using Quick Sort Algorithm | Quick Sort Program in C | Data Structure Quick Sort using C Program | Quick Sort Algorithm in C

#include< stdio.h>
#include< conio.h>
#define max 15
int beg,end,top,i,n,loc,left,right;
int array[max+1];    //contains the various elements.
int upper[max-1],lower[max-1];
//two stacks to store two ends of the list.

void main()
    {

      void enter(void);
      void quick(void);
      void prnt(void);
      clrscr();
      enter();     //entering elements in the array
      top=i-1;     //set top to stack
        if (top==0)
           {
     printf("
UNDERFLOW CONDITION ");
     getch();
     exit();
    }
       top=0;
       if(n>1)
           {
     top++;
     lower[top]=1;upper[top]=n;
     while ( top!=NULL )
     {
       beg=lower[top];
       end=upper[top];
       top--;
       left=beg;   right=end;    loc=beg;
       quick();
       if ( beg
          {
    top++;
    lower[top]=beg;
    upper[top]=loc-1;
           }
        if(loc+1
           {
    top++;
    lower[top]=loc+1;
    upper[top]=end;
    }
       }        //end of while
      }        //end of if statement
        printf("
Sorted elements of the array are :");
        prnt();   //to print the sorted array
      getch();
    }               //end of main


  void  enter(void)
   {
    printf("
Enter the no of elements in the array:");
    scanf("%d",&n);
    printf("
Enter the elements of the array :");
    for(i=1;i<=n;i++)
       {
     printf("
 Enter the %d element :",i);
     scanf("%d",&array[i]);
       }
   }


   void  prnt(void)
   {
    for(i=1;i<=n;i++)
       {
     printf("
 The %d element  is : %d",i,array[i]);
       }
   }

   void quick()
   {
     int temp;
     void tr_fr_right(void);
     while( array[loc]<=array[right] && loc!=right)
     {
       right--;
     }

      if(loc==right)
     return ;

      if(array[loc]>array[right])
     {
         temp=array[loc];
         array[loc]=array[right];
         array[right]=temp;
      loc=right;
      tr_fr_right();
     }
     return ;
    }

   void  tr_fr_right()
    {
       int temp;
       while( array[loc] > array[left] && loc!=left)
     {
       left++;
     }

      if(loc==left)
     return ;

      if(array[loc] < array[left])
     {
         temp=array[loc];
         array[loc]=array[left];
         array[left]=temp;
      loc=left;
      quick();
     }
     return ;
   }

Related Links :

Data Structures Program on XOR | XOR in Data Structure | C Program on XOR Data Structure

Data Structures XOR list example | XOR List Example in DS | Data Structures Program on XOR | XOR in Data Structure | C Program on XOR Data Structure

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

struct xnode {
 int data;
 unsigned long direction;
};

struct xnode *add_data(int data, struct xnode* list);
void walk_list(struct xnode *list);

int main(void) {

 struct xnode *l2 = add_data(2, NULL);
 struct xnode *l1 = add_data(1, l2);
 struct xnode *l3 = add_data(3, l2);
 struct xnode *l4 = add_data(4, l3);

 printf("front -> back....\n");
 walk_list(l1);
 printf("back -> front....\n");
 walk_list(l4);

 return 0;
}

struct xnode *add_data(int data, struct xnode *list) {
 struct xnode *newxnode = malloc(sizeof(struct xnode));

 assert(newxnode);
 newxnode->direction = (unsigned long)list;
 newxnode->data = data;

 if(list != NULL)
  list->direction ^= (unsigned long)newxnode;

 return newxnode;
}

void walk_list(struct xnode *list) {
 unsigned long prev = 0;

 while(list != NULL) {
  unsigned long next = prev ^ list->direction;
  printf("%d ", list->data);
  prev = (unsigned long)list;
  list = (struct xnode *)next;
 }

 printf("\n");
}

Related Links :

concatenate files using CAT function in C

#include 

main(argc, argv)        /* cat: concatenate files */
int argc;
char *argv[];
{
    FILE *fp, *fopen();

    if (argc == 1) /* no args; copy standard input */
         filecopy(stdin);
    else
         while (--argc > 0)
            if ((fp = fopen(*++argv, "r")) == NULL) {
                fprintf(stderr,
                        "cat: can't open %s\n", *argv);
                exit(1);
            } else {
                filecopy(fp);
                fclose(fp);
            }
    exit(0);
}

filecopy(fp)    /* copy file fp to standard output */
FILE *fp;
{
    int c;

    while ((c = getc(fp)) != EOF)
        putc(c, stdout);
}

Related Links :

Relation between Pointers and Structures in C Language

Relation between Pointers and Structures in C :-

• struct inventory { char name[30];
• int number;
• float price; }
• product[2],*p;
• p = product; // assign zeroth element
• p -> name is same as (*p).name
• ++ptr->count increments count
• (++ptr)->count increments ptr and then return count
• ptr++->count is legal and increments ptr after accessing count
• *ptr->p fetches whatever p points to
• *ptr->p++ increments p after accessing whatever it points to
• (*ptr->p)++ increments whatever p points to
• *ptr++->p increments ptr after accessing whatever it points to

Related Links :

Program on Array implementation of stack in C

 

# include< stdio.h>
# include< string.h>
# define size 3
int tos= -1;
/*this variable will keep track of the top of the stack */
int flag = 0;
/* this variable will determine whether push or pop will be granted. */
int stack[size];
/* array , within this array stack will grow and shrink. */
void push(int s[], int d)
{
if(tos==size-1)
{
/* this condition becomes true when the stack can not grow further */
flag=0;
}
else
{
flag = 1;
++tos;
s[tos] = d;
}
}
int pop(int s[])
{
int p;
if(tos == -1)
{
p = 0;
flag = 0;
}
else
{
flag = 1;
p = s[tos];
--tos;
}
return p;
}
void display(int s[])
{
int i;
if(tos == -1)
{
printf("\n Stack is empty");
}
else
{
for(i = tos; i >= 0; --i)
printf("\n %d", s[i] );
}
}
void main()
{
int data;
char choice;
int q = 0;
clrscr();
do
{
printf(" \nPush->i Pop->p Quit->q:");
printf("\nInput the choice : ");
do
{
choice = getchar();
choice =tolower(choice);
}while(strchr("ipq",choice)==NULL);
printf("Your choice is: %c",choice);
switch(choice)
{
case 'i' :
printf("\n Input the element to push:");
scanf("%d", &data);
push(stack, data);
if(flag)
{
printf("\n After inserting ");
display(stack);
if(tos == (size-1))
printf("\n Stack is full");
}
else
printf("\n capacity is exhausted");
break;
case 'p' :
data = pop(stack);
if(flag)
{
printf("\n Data is popped: %d", data);
printf("\n Rest data in stack is as follows:\n");
display(stack);
}
else
printf("\n No popping took place" );
break;
case 'q':
q = 1;
}
} while(!q);
getch();
} 

Related Links :

C Program to show Linked list implementation of stack

 

# include< stdio.h>
# include< stdlib.h>
struct link
{
int info;
struct link *next;
};
void display(struct link *rec)
{
while(rec != NULL)
{
printf(" %d ",rec->info);
rec = rec->next;
}
}
struct link * push(struct link *rec)
{
struct link *new1;
printf("\n Enter value for stack:-");
new1 = (struct link *)malloc(sizeof(struct link));
scanf("%d", &new1->info);
new1->next = rec;
/* next pointer of new1 is holding the address of the first node of the list. so new1 is the first node now.*/
rec = new1;
/* from this point the pointer rec is pointing the first node of the list. */
return rec;
}
struct link * pop(struct link *rec)
{
struct link *temp;
if(rec == NULL)
{
printf("\n Stack is empty");
}
else
{
/*rec is pointing the first node of the list.*/
temp = rec->next;
/*temp is pointing the second node of the list. */
free(rec);
rec = temp;
printf("\n After pop operation the stack is as follows:\n");
display(rec);
if(rec == NULL)
printf("\n Stack is empty");
}
return rec;
}
int selection()
{
int choice;
do
{
printf("\n 1<-Push ");
printf("\n 2<-Pop");
printf("\n 3<-Quit");
printf("\n Input your choice :");
scanf("%d", &choice);
if(choice <1 || choice >3)
printf("\n Incorrect choice-> Try once again");
} while(choice <1 || choice >3);
return choice;
}
void main()
{
struct link *start ;
int choice;
clrscr();
start = NULL;
do
{
choice = selection();
switch(choice)
{
case 1:
start = push(start);
printf("\n After push operation stack is as follows:\n");
display(start);
break;
case 2:
start = pop(start);
break;
default :
printf("\n End of session");
}
} while(choice != 3);
getch();
}

Related Links :