INDEX PAGE

S.NO PROGRAM DATE SIGNATURE

1. WAP TO COUNT NUMBER

18/09/2024
OF FREQUENCY

WAP TO FIND MINIMUM OR 25/09/2024

2.
MAXIMUM NUMBER

3. WAP TO IMPLEMENT LINEAR 02/10/2024

SEARCH
4. WAP TO IMPLEMENT BINARY 08/10/2024
SEARCH

5. WAP TO IMPLEMENT BUBBLE 09/10/2024

SORT

6. WAP TO IMPLEMENT 23/10/2024

SELECTION SORT

7. WAP TO IMPLEMENT 06/11/2024

INSERTION SORT

8. WAP TO IMPLEMENT MERGE 13/11/2024

SORT
9. WAP TO IMPLEMENT QUICK 20/11/2024
SORT
10. MENU DRIVEN PROGRAM FOR
04/12/2024
ALL OPERATIONS ON SINGLY
11. LINKLIST
WAP TO IMPLEMENT STACK 11/12/2024
USING ARRAY
12. WAP TO IMPLEMENT QUEUE 18/12/2024
USING ARRAY
13. WAP TO IMPLEMENT STACK 08/01/2025
USING LINKLIST
Q1. Write a program to Count number of occurrences (or frequency) in a
sorted array

include <stdio.h>
// Returns number of times x occurs in arr[0..n-1]
int countOccurrences(int arr[], int n, int x)
{

int res = 0;
for (int i = 0; i < n; i++)
if (x == arr[i])
res++;
return res;
}
// Driver code
int main()
{

int arr[] = {1, 2, 2, 2, 2, 3, 4, 7, 8, 8};

int n = sizeof(arr) / sizeof(arr[0]);
int x = 2;
printf("%d", countOccurrences(arr, n, x));
return 0;
}

Q2. WAP to find the minimum (or maximum) element of an array.

#include <stdio.h>
// Find maximum between two

numbers.
intreturn (num1
max(int > num2)
num1, ? num1 : num2;
int num2)
{}

// Find minimum between two

numbers.
intreturn (num1
min(int num1,> int
num2) ? num2 : num1;
num2)
{
}
int getMin(int arr[], int n)
{

int res = arr[0];

for (int i = 1; i < n; i++)
res = min(res, arr[i]);
return res;
}
int getMax(int arr[], int n)
{

int res = arr[0];

for (int i = 1; i < n; i++)
res = max(res, arr[i]);
return res;
}
int main()
{

int arr[] = { 12, 1234, 45, 67, 1 }; int n =

sizeof(arr) / sizeof(arr[0]);
printf("Minimum element of array: %d
\n", getMin(arr, n));
printf("Maximum element of array: %d \n",
getMax(arr, n));
return 0;
}

Q3.WAP to implement linear search in an array

// C program to implement linear search using loops

#include <stdio.h>
// linear search function that searches the key in arr
int linearSearch(int* arr, int size, int key)
{
// starting traversal
for (int i = 0; i < size; i++) {
// checking condition
if (arr[i] == key) {
return i;
}
}
 return -1;
}
// Driver code
int main()
{
int arr[10] = { 3, 4, 1, 7, 5, 8, 11, 42, 3, 13 };
int size = sizeof(arr) / sizeof(arr[0]);
int key = 4;
// calling linearSearch
int index = linearSearch(arr, size, key);
// printing result based on value returned by
// linearSearch()
if (index == -1) {

printf("The element is not present in the arr.");

}
else {
printf("The element is present at arr[%d].", index);
}
return 0;
}

Q4. WAP to implement Binary search in an Array ?

#Include <stdio.h>

int binarySearch(int arr[], int l, int r, int x)

{
while (l <= r) {
int m = l + (r - l) / 2;
// Check if x is present at mid
if (arr[m] == x)

return m;

// If x greater, ignore left half

if (arr[m] < x)
l = m + 1;

// If x is smaller, ignore right half

else
r = m - 1;
 }

// If we reach here, then element was not present

return -1;
}

int main(void)
{
int arr[] = { 2, 3, 4, 10, 40 };
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binarySearch(arr, 0, n - 1, x);
(result == -1) ? printf("Element is not present"
" in array")
: printf("Element is present at "
"index %d",
result);
return 0;
}

Q5. WAP in C to implement bubble sort

// C program for implementation of Bubble sort
#include <stdio.h>
// Swap function
void swap(int* arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}

// A function to implement bubble sort

void bubbleSort(int arr[], int n)
{
int i, j;
for (i = 0; i < n - 1; i++)

// Last i elements are already

// in place
for (j = 0; j < n - i - 1; j++)
if (arr[j] > arr[j + 1])
swap(arr, j, j + 1);
}
// Function to print an array
void printArray(int arr[], int size)
{
int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main()
{

int arr[] = { 5, 1, 4, 2, 8 };
int N = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, N);
printf("Sorted array: ");
printArray(arr, N);
return 0;
}

Q6. WAP to implement selection sort in C

// C program for implementation of selection sort

#include <stdio.h>
void swap(int* xp, int* yp)
{

int temp = *xp;

*xp = *yp;
*yp = temp;
}
void selectionSort(int arr[], int n)
{

int i, j, min_idx;
// One by one move boundary of unsorted subarray
for (i = 0; i < n - 1; i++) {

// Find the minimum element in unsorted array

min_idx = i;
for (j = i + 1; j < n; j++)
if (arr[j] < arr[min_idx])
min_idx = j;

// Swap the found minimum element with the first

 // element
swap(&arr[min_idx], &arr[i]);
}
}
/* Function to print an array */
void printArray(int arr[], int size)
{

int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver program to test above functions
int main()
{

int arr[] = { 64, 25, 12, 22, 11 };

int n = sizeof(arr) / sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

Q7.WAP to implement insertion sort in C

// C program for insertion sort

#include <math.h> #include
<stdio.h> /* Function to sort an
array using insertion sort*/ void
insertionSort(int arr[], int n) {

int i, key, j;
for (i = 1; i < n; i++)
{
key = arr[i];
j = i - 1;
/* Move elements of arr[0..i-1],
that are greater than key,
to one position ahead of
their current position */
 while (j >= 0 && arr[j] > key)
{
arr[j + 1] = arr[j];
j = j - 1;
}
arr[j + 1] = key;
}
}
// A utility function to print
// an array of size n
void printArray(int arr[], int n)
{

int i;
for (i = 0; i < n; i++)
printf("%d ", arr[i]);
printf("\n");
}
// Driver code
int main()
{

int arr[] = {12, 11, 13, 5, 6};

int n = sizeof(arr) / sizeof(arr[0]);
insertionSort(arr, n);
printArray(arr, n);
return 0;

Q8.WAP to implement merge sort in C

// C program for Merge Sort

#include <stdio.h>
#include <stdlib.h>
// Merges two subarrays of arr[].
// First subarray is arr[l..m]
// Second subarray is arr[m+1..r]
void merge(int arr[], int l, int m, int r)
{

int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
// Create temp arrays
int L[n1], R[n2];
// Copy data to temp arrays
// L[] and R[]
for (i = 0; i < n1; i++)

L[i] = arr[l + i];

for (j = 0; j < n2; j++)
R[j] = arr[m + 1 + j];

// Merge the temp arrays back

// into arr[l..r]
// Initial index of first subarray
i = 0;
// Initial index of second subarray
j = 0;
// Initial index of merged subarray
k = l;
while (i < n1 && j < n2) {

if (L[i] <= R[j]) {

arr[k] = L[i];
i++;
}
else {
arr[k] = R[j];
j++;
}
k++;
}
// Copy the remaining elements
// of L[], if there are any
while (i < n1) {

arr[k] = L[i];
i++;
k++;
}
// Copy the remaining elements of
// R[], if there are any
while (j < n2) {

arr[k] = R[j];
j++;
k++;
 }
}
// l is for left index and r is
// right index of the sub-array
// of arr to be sorted
void mergeSort(int arr[], int l, int r)
{

if (l < r) {
// Same as (l+r)/2, but avoids
// overflow for large l and r
int m = l + (r - l) / 2;
// Sort first and second halves
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);

}
}
// UTILITY FUNCTIONS
// Function to print an array
void printArray(int A[], int size)
{

int i;
for (i = 0; i < size; i++)
printf("%d ", A[i]);
printf("\n");
}
// Driver code
int main()
{

int arr[] = { 12, 11, 13, 5, 6, 7 };

int arr_size = sizeof(arr) / sizeof(arr[0]);
printf("Given array is \n");
printArray(arr, arr_size);
mergeSort(arr, 0, arr_size - 1);
printf("\nSorted array is \n");
printArray(arr, arr_size);
return 0;

}
Q9. WAP to implement Quick sort in C

#include <stdio.h>
// Function to swap two elements
void swap(int* a, int* b) {
int t = *a;
*a = *b;
*b = t;
}
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = (low - 1);
for (int j = low; j <= high - 1; j++) {

if (arr[j] < pivot) {

i++;
swap(&arr[i], &arr[j]);
}
}
swap(&arr[i + 1], &arr[high]);
return (i + 1);
}
void quickSort(int arr[], int low, int high) {
if (low < high) {
int pi = partition(arr, low, high);
quickSort(arr, low, pi - 1);
quickSort(arr, pi + 1, high);
}
}
// Function to print the array
void printArray(int arr[], int size) {

int i;
for (i = 0; i < size; i++)
printf("%d ", arr[i]);
printf("\n");
}
int main() {
int arr[] = { 12, 17, 6, 25, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
quickSort(arr, 0, n - 1);
printf("Sorted array: \n");
printArray(arr, n);
 return 0;
}
Q10. Menu driven program for all operations on singly linked list in C
// C program for the all operations in // the Singly Linked List #include <stdio.h>
#include <stdlib.h> // Linked List Node struct node {

int info;
struct node* link;
};
struct node* start = NULL;
// Function to create list with n nodes initially
void createList()
{

if (start == NULL) {
int n;
printf("\nEnter the number of nodes: ");
scanf("%d", &n);
if (n != 0) {
int data;
struct node* newnode;
struct node* temp;
newnode = malloc(sizeof(struct node));
start = newnode;
temp = start;
printf("\nEnter number to"
" be inserted : ");
scanf("%d", &data);
start->info = data;
for (int i = 2; i <= n; i++) {

newnode = malloc(sizeof(struct node));

temp->link = newnode;
printf("\nEnter number to"
" be inserted : ");
scanf("%d", &data);
newnode->info = data;
temp = temp->link;
}
}
 printf("\nThe list is created\n");
}
else
printf("\nThe list is already created\n");
}
// Function to traverse the linked list
void traverse()
{
struct node* temp;
// List is empty
if (start == NULL)
printf("\nList is empty\n");

// Else print the LL

else {
temp = start;
while (temp != NULL) {
printf("Data = %d\n", temp->info);
temp = temp->link;
}
}
}

// Function to insert at the front

// of the linked list
void insertAtFront()
{
int data;
struct node* temp;
temp = malloc(sizeof(struct node));
printf("\nEnter number to"
" be inserted : ");
scanf("%d", &data);
temp->info = data;

// Pointer of temp will be

// assigned to start
temp->link = start;
start = temp;
}

// Function to insert at the end of

// the linked list
void insertAtEnd()
{
 int data;
struct node *temp, *head;
temp = malloc(sizeof(struct node));
// Enter the number
printf("\nEnter number to"

" be inserted : ");

scanf("%d", &data);
// Changes links
temp->link = 0;
temp->info = data;
head = start;
while (head->link != NULL) {

head = head->link;
}
head->link = temp;
}
// Function to insert at any specified
// position in the linked list
void insertAtPosition()
{

struct node *temp, *newnode; int

pos, data, i = 1; newnode =
malloc(sizeof(struct node)); // Enter
the position and data printf("\nEnter
position and data :"); scanf("%d %d",
&pos, &data); // Change Links temp =
start; newnode->info = data;
newnode->link = 0; while (i < pos - 1)
{

temp = temp->link;
i++;
}
newnode->link = temp->link;
temp->link = newnode;
}
// Function to delete from the front
// of the linked list
void deleteFirst()
{
 struct node* temp;
if (start == NULL)
printf("\nList is empty\n");
else { temp = start;
start = start->link;
free(temp);

}
}
// Function to delete from the end
// of the linked list
void deleteEnd()
{

struct node *temp, *prevnode;

if (start == NULL)
printf("\nList is Empty\n");
else { temp = start;
while (temp->link != 0) {

prevnode = temp;
temp = temp->link;
}
free(temp);
prevnode->link = 0;
}
}
// Function to delete from any specified
// position from the linked list
void deletePosition()
{

struct node *temp, *position;

int i = 1, pos;
// If LL is empty
if (start == NULL)

printf("\nList is empty\n");

// Otherwise
else {
printf("\nEnter index : ");
// Position to be deleted
scanf("%d", &pos);
position = malloc(sizeof(struct node));
temp = start;
 // Traverse till position
while (i < pos - 1) {
temp = temp->link;
i++;
}
// Change Links
position = temp->link;
temp->link = position->link;

// Free memory
free(position);
}
}
// Function to find the maximum element
// in the linked list
void maximum()
{
int a[10];
int i;
struct node* temp;

// If LL is empty
if (start == NULL)
printf("\nList is empty\n");

// Otherwise
else {
temp = start;
int max = temp->info;
// Traverse LL and update the
// maximum element
while (temp != NULL) {

// Update the maximum

// element
if (max < temp->info)
max = temp->info;
temp = temp->link;
}
printf("\nMaximum number "
"is : %d ",
max);
}
}
// Function to find the mean of the
// elements in the linked list
void mean()
{

int a[10];
int i;
struct node* temp;
// If LL is empty
if (start == NULL)

printf("\nList is empty\n");

// Otherwise
else {
temp = start;
// Stores the sum and count of
// element in the LL
int sum = 0, count = 0;
float m;
// Traverse the LL
while (temp != NULL) {

// Update the sum

sum = sum + temp->info;
temp = temp->link;
count++;
}
// Find the mean
m = sum / count;
// Print the mean value
printf("\nMean is %f ", m);

}
}
// Function to sort the linked list
// in ascending order
void sort()
{

struct node* current = start;

struct node* index = NULL;
int temp;
 // If LL is empty
if (start == NULL) {
return;
}
// Else
else {

// Traverse the LL
while (current != NULL) {
index = current->link;
// Traverse the LL nestedly
// and find the minimum
// element
while (index != NULL) {

// Swap with it the value

// at current
if (current->info > index->info) {
temp = current->info;
current->info = index->info;
index->info = temp;
}
index = index->link;
}
// Update the current
current = current->link;

}
}
}
// Function to reverse the linked list
void reverseLL()
{

struct node *t1, *t2,

*temp; t1 = t2 = NULL; //
If LL is empty if (start ==
NULL)

printf("List is empty\n");

// Else
else {
 // Traverse the LL
while (start != NULL) {

// reversing of
points t2 = start-
>link; start->link =
t1; t1 = start; start =
t2;
}
start = t1;
// New head Node
temp = start;
printf("Reversed linked "

"list is : ");

// Print the LL
while (temp != NULL) {
printf("%d ", temp->info);
temp = temp->link;
}
}
}
// Function to search an element in linked list
void search()
{

int found = -1;

// creating node to traverse
struct node* tr = start;
// first checking if the list is empty or not
if (start == NULL) {

printf("Linked list is empty\n");

}
else {
printf("\nEnter the element you want to search: ");
int key;
scanf("%d", &key);
// checking by traversing
while (tr != NULL) {

// checking for key

if (tr->info == key) {
found = 1;
break;
 }
// moving forward if not at this position
else {
} tr = tr->link;

}
// printing found or not
if (found == 1) {

printf(
"Yes, %d is present in the linked list.\n",
key);
}
else {
printf("No, %d is not present in the linked "
"list.\n",
key);
}
}
}
// Driver Code
int main()
{

createList();
int choice;
while (1) {

printf("\n\t1 To see list\n");

printf("\t2 For insertion at"
" starting\n");
printf("\t3 For insertion at"
" end\n");
printf("\t4 For insertion at "
"any position\n");
printf("\t5 For deletion of "
"first element\n");
printf("\t6 For deletion of "
"last element\n");
printf("\t7 For deletion of "
"element at any position\n");
printf("\t8 To find maximum among"
" the elements\n");
printf("\t9 To find mean of "
"the elements\n");
printf("\t10 To sort element\n");
printf("\t11 To reverse the "
 "linked list\n");
printf("\t12 Search an element in linked list\n");
printf("\t13 To exit\n");
printf("\nEnter Choice :\n");
scanf("%d", &choice);
switch (choice) {
case 1:

traverse();
break;
case 2:
insertAtFront();
break;
case 3:
insertAtEnd();
break;
case 4:
insertAtPosition();
break;
case 5:
deleteFirst();
break;
case 6:
deleteEnd();
break;
case 7:
deletePosition();
break;
case 8:
maximum();
break;
case 9:
mean();
break;
case 10:
sort();
break;
case 11:
reverseLL();
break;
case 12:
search();
break;
case 13:
exit(1);
break;
default:
 printf("Incorrect Choice\n");
} }
return 0;

Q11. WAP to implement stack using array in C.

#include <stdio.h> int

MAXSIZE = 8; int stack[8]; int
top = -1; /* Check if the stack
is empty */ int isempty(){

if(top == -1)
return 1;
else
return 0;
}
/* Check if the stack is full */
int isfull(){

if(top == MAXSIZE)
return 1;
else
return 0;
}
/* Function to return the topmost element in the stack */
int peek(){

return stack[top];
}
/* Function to delete from the stack */
int pop(){

int data;
if(!isempty()) {
data = stack[top];
top = top - 1;
return data;
} else {
printf("Could not retrieve data, Stack is empty.\n");
}
}
/* Function to insert into the stack */
int push(int data){
if(!isfull()) {
top = top + 1;
stack[top] = data;
} else {
printf("Could not insert data, Stack is full.\n");
}
}
/* Main function */
int main(){
push(44);
push(10);
push(62);
push(123);
push(15);
printf("Element at top of the stack: %d\n" ,peek());
printf("Elements: \n");

// print stack data

while(!isempty()) {
int data = pop();
printf("%d\n",data);
}
printf("Stack full: %s\n" , isfull()?"true":"false");
printf("Stack empty: %s\n" , isempty()?"true":"false");
return 0;
}

Q12. WAP to implement Queue in C using Array

#define MAX_SIZE 100

int queue[MAX_SIZE];
int front = -1;
int rear = -1;

void enqueue(int element) {

if (rear == MAX_SIZE - 1) {
printf("Queue is full");
return;
}
if (front == -1) {
front = 0;
 }
rear++;
queue[rear] = element;
}
int dequeue() {
if (front == -1 || front > rear) {
printf("Queue is empty");
return -1;
}
int element = queue[front];
front++;
return element;
}

int main() {
enqueue(10);
enqueue(20);
enqueue(30);
printf("%d ", dequeue());
printf("%d ", dequeue());
printf("%d ", dequeue());
printf("%d ", dequeue());
return 0;
}

Q13. WAP to implement Stack using linked list.

#include <stdio.h>
#include <stdlib.h>
void push();
void pop();
void display();
struct node
{
int val;
struct node *next;
};
struct node *head;

void main ()
{
int choice=0;
printf("\n*********Stack operations using linked list*********\n");
printf("\n----------------------------------------------\n");
while(choice != 4)
 {
printf("\n\nChose one from the below options...\n");
printf("\n1.Push\n2.Pop\n3.Show\n4.Exit");
printf("\n Enter your choice \n");
scanf("%d",&choice);
switch(choice)
{
case 1:
{
push();
break;
}
case 2:
{
pop();
break;
}
case 3:
{
display();
break;
}
case 4:
{
printf("Exiting....");
break;
}
default:
{}
printf("Please Enter valid choice ");

};
} } void
push () {

int val; struct node *ptr = (struct

node*)malloc(sizeof(struct node)); if(ptr == NULL) { } else
{

printf("not able to push the element");

printf("Enter the value");

scanf("%d",&val);
if(head==NULL)
 {
ptr->val = val;
ptr -> next = NULL;
head=ptr;
}
else
{
ptr->val = val;
ptr->next = head;
head=ptr;

}
printf("Item pushed");

}
}
void pop()
{

int item; struct

node *ptr; if (head
== NULL) { } else {

printf("Underflow");

item = head->val;
ptr = head;
head = head->next;
free(ptr);
printf("Item popped");

}
}
void display()
{
int i; struct node
*ptr; ptr=head;
if(ptr == NULL) {
} else {

printf("Stack is empty\n");

printf("Printing Stack elements \n");

 while(ptr!=NULL)
{
printf("%d\n",ptr->val);
ptr = ptr->next;
}
}
}