DATA STRUCTURE

PROBLEM SHEET

Mahale Tanisha
SYBCA-B

SEM -3
2312117

1.Write a program to perform the operations on the STACK.

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

#define MAX 5
void push();
void pop();
void display();
int
stack[5]; int
top=-1;

void main()
{
int ch;

do
{
printf("\n 1. PUSH");
printf("\n 2. POP"); printf("\n 3.
Display");
printf("\n 4. Exit");

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

scanf("%d", &ch);

switch(ch)
{
case 1:
push();
 break;

case 2:
pop(); break;

case 3:
display();
break;

case 4:
exit(0);
break;

deafult:
printf("invalid chocice");
break;
}
getch();
}while(ch!=4);
} void
push()
{
int value;
if(top==MAX-1)
{
printf("\n Overflow");
}
else
{
printf("\n enter a value you want to push:");
scanf("%d",&value);

top=top+1;
stack[top]=value;
}
} void
pop()
{
int value;

if(top==-1)
{
printf("\n Underflow");
}
else
{
value=stack[top];
top=top-1;
printf("\n %d value deleted from stack",value);
}
}
void display()
{
int i;
 if(top==-1)
{
printf("\n Underflow");
}
else
{
printf("\n stack elements are......");
for(i=top; i>=0; i--)
{
printf("\n %d",stack[i]);
}
}
}
OUTPUT:
2. Write a program to perform the operations on the Simple QUEUE.
#include<stdio.h>
#define MAX 5
void insert();
void delete();
void display();
int
queue_array[MAX]; int
rear = - 1; int front
= - 1;
main()
{ int
choice;
while (1) {
printf("1.Insert element to queue \n");
printf("2.Delete element from queue \n");
printf("3.Display all elements of queue \n");
printf("4.Quit \n");
printf("Enter your choice : ");
scanf("%d", &choice);
switch (choice)
{
case 1:
insert();
break; case
2: delete();
break;
case 3:
display();
break; case
4: exit(1);
default:
 printf("Wrong choice \n");
} /* End of switch */
} /* End of while */
} /* End of main() */
void insert() { int
add_item; if (rear == MAX -
1) printf("Queue Overflow \
n"); else
{
if (front == - 1) /*If queue
is initially empty */ front = 0;
printf("Inset the element in queue : ");
scanf("%d", &add_item); rear = rear + 1;
queue_array[rear] = add_item;
}
} /* End of insert() */
void
delete() {
if (front == - 1 || front > rear)
{
printf("Queue Underflow \n");
return ;
} else { printf("Element deleted
from queue is :
%d\n",queue_array[front]);

front = front + 1;
}
} /* End of delete() */
void display() { int i; if
(front == - 1) printf("Queue
is empty \n");

else
{
printf("Queue is : \n");
for (i = front; i <= rear; i++)
printf("%d ", queue_array[i]);
printf("\n");
}
/* End of display() */
}
OUTPUT:
3. Write a program to perform the operations on the CIRCULAR QUEUE.
#include<stdio.h>
#define MAX 5 int
cqueue_arr[MAX]; int
front = -1; int rear
= -1; void
insert(int item)
{
if((front == 0 && rear == MAX-1) || (front == rear+1))
{
printf("\nQueue Overflow \n");
return; }
if(front == -1)
{ front = 0; rear
= 0; } else
{ if(rear == MAX-
1) rear = 0; else
rear = rear+1;
}
cqueue_arr[rear] = item ;
}
void deletion()
{
if(front == -1)
{
printf("\nQueue Underflow \n");
return ; }
printf("Element deleted from queue is : %d \n",cqueue_arr[front]); if(front
== rear)
{ front = -1;
rear=-1; } else
{ if(front == MAX-
1) front = 0; else
front = front+1;
} }
void display()
{
int front_pos = front,rear_pos = rear; if(front
== -1)
{
printf("Queue is empty \n");
return; } printf("\nQueue
elements :\n"); if( front_pos
<= rear_pos ) while(front_pos
<= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]); front_pos++;
} else
{
while(front_pos <= MAX-1)
{
printf("%d ",cqueue_arr[front_pos]);
front_pos++; } front_pos = 0;
while(front_pos <= rear_pos)
{
printf("%d ",cqueue_arr[front_pos]); front_pos++;
} } printf("\n"); } int main()
{ int choice,item; do
{ printf("1.Insert \n");
printf("2.Deleten \n");
printf("3.Display \n");
printf("4.Quit \n"); printf("\
nEnter your choice : ");
scanf("%d",&choice);
switch(choice) { case 1 :
printf("Input the element for insertion in queue : ");
scanf("%d", &item); insert(item); break; case 2 :
deletion(); break; case 3: display(); break; case 4:
break; default:
printf("Wrong choice\n");
}
}while(choice!=4);
return 0; }
OUTPUT:
4. Write a program to implement Sequential search.
#include <stdio.h>
void main() { int
num;
int array[10], i, search, found = 0;
printf("Enter the number of elements ");
scanf("%d", &num);
printf("Enter the elements one by one \n");
for (i = 0; i < num; i++)
{
scanf("%d", &array[i]);
}
printf("Enter the element to be searched ");
scanf("%d", &search);

/* Linear search begins */

for (i = 0; i < num ; i++)
{
if (search == array[i] )
{
found = 1;
break;
}
} if (found == 1) printf("Element is present in the array
at position %d",i); else
printf("Element is not present in the array\n");
getch();
}
OUTPUT:

5. Write a program to implement Binary search.

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#define size 10 // Added to make changing size of array easier
int smallest(int arr[], int k, int n); // Added to sort array
void selection_sort(int arr[], int n); // Added to sort array
int main(int argc, char *argv[]) { int arr[size], num, i, n,
beg, end, mid, found=0; printf("\n Enter the number of
elements in the array: "); scanf("%d", &n);
printf("\n Enter the elements: "); for(i=0;i<n;i+
+)
{
scanf("%d", &arr[i]);
} selection_sort(arr, n); // Added to sort the
array printf("\n The sorted array is: \n");
for(i=0;i<n;i++)
printf(" %d\t", arr[i]);
printf("\n\n Enter the number that has to be searched: ");
scanf("%d", &num); beg = 0, end = n-1; while(beg<=end)
{ mid = (beg +
end)/2; if (arr[mid]
== num)
{
printf("\n %d is present in the array at position %d", num, mid+1);
found =1; break; }
else if (arr[mid]>num)
end = mid-1; else beg
= mid+1; }
if (beg > end && found == 0)
printf("\n %d does not exist in the array", num);
return 0; }
int smallest(int arr[], int k, int n)
{
int pos = k, small=arr[k], i; for(i=k+1;i<n;i++)
{
if(arr[i]< small)
{ small =
arr[i]; pos =
i;
} } return
pos;
getch(); }
void selection_sort(int arr[],int n)
{ int k, pos,
temp;
for(k=0;k<n;k++)
{ pos = smallest(arr, k,
n); temp = arr[k]; arr[k]
= arr[pos]; arr[pos] =
temp;
}
}

OUTPUT:

7. Write a program to implement Bubble sort.

#include <stdio.h>
int
main() {
 int array[100], n, i, j, swap;
clrscr();
printf("Enter number of elements\n");
scanf("%d", &n);

printf("Enter %d integers values\n", n);

for (i = 0; i < n; i++)
scanf("%d", &array[i]);

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

{
for (j = 0 ; j < n - i - 1; j++)
{
if (array[j] > array[j+1]) /* For decreasing order use '<' instead
of '>' */
{
swap = array[j];
array[j] = array[j+1];
array[j+1] = swap;
}
}
}
printf("Sorted list in ascending order:\n");
for (i = 0; i < n; i++)
printf("%d\n", array[i]);
getch(); return 0; }
OUTPUT:

8. Write a program to implement Merge sort.

#include <stdio.h>
#include <conio.h> #define
size 100
void merge(int a[], int, int, int);
void merge_sort(int a[],int, int);
void main() {
int arr[size], i, n;
printf("\n Enter the number of elements in the array : ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
merge_sort(arr, 0, n-1); printf("\n
The sorted array is: \n");
for(i=0;i<n;i++) printf(" %d\t",
arr[i]); getch(); }
void merge(int arr[], int beg, int mid, int end)
{
int i=beg, j=mid+1, index=beg, temp[size], k; while((i<=mid)
&& (j<=end))
{
if(arr[i] < arr[j])
{
temp[index] = arr[i];
i++; } else {
temp[index] = arr[j];
j++; } index++; }
if(i>mid) {
while(j<=end)
{temp[index] = arr[j];
j++; index++;
}
}
else {
while(i<=mid)
{
temp[index] = arr[i];
i++; index++;
} }
for(k=beg;k<index;k++)
arr[k] = temp[k];
}
void merge_sort(int arr[], int beg, int end)
{ int mid; if(beg<end) { mid
= (beg+end)/2;
merge_sort(arr, beg, mid);
merge_sort(arr, mid+1, end);
merge(arr, beg, mid, end);
}
}

OUTPUT:

9. Write a program to implement Quick sort.

#include <stdio.h>
#include <conio.h> #define
size 100
int partition(int a[], int beg, int end);
void quick_sort(int a[], int beg, int end);
void main() {
int arr[size], i, n;
printf("\n Enter the number of elements in the array: ");
scanf("%d", &n);
printf("\n Enter the elements of the array: ");
for(i=0;i<n;i++)
{
scanf("%d", &arr[i]);
}
quick_sort(arr, 0, n-1); printf("\n The
sorted array is: \n"); for(i=0;i<n;i++)
printf(" %d\t", arr[i]); getch(); } int
partition(int a[], int beg, int end)
{
int left, right, temp, loc, flag;
loc = left = beg; right = end;
flag = 0; while(flag != 1)
{
while((a[loc] <= a[right]) && (loc!=right))
right--; if(loc==right) flag =1;
else if(a[loc]>a[right])
{ temp = a[loc];
a[loc] = a[right];
a[right] = temp;
loc = right; }
if(flag!=1) {
while((a[loc] >= a[left]) && (loc!=left))
left++; if(loc==left) flag =1;
else if(a[loc] <a[left])
{ temp =
a[loc]; a[loc] =
a[left]; a[left]
= temp; loc =
left;
}
} } return
loc; }
void quick_sort(int a[], int beg, int end)
{ int loc; if(beg<end) { loc
= partition(a, beg, end);
quick_sort(a, beg, loc-1);
quick_sort(a, loc+1, end);
}
}

OUTPUT: