5/30/2025

Data Structure
Lab Manual

Name: Mohit Kumar

ADMISSION NO: 24SCSE2030379
SEC - 5
 Data Structure Lab Mannual
Program 1: Write a program to find the largest and second largest element from an array.
Program:
//Finding largest and SecLargest value In a Given Array
#include <stdio.h>
void main()
{
int size;

printf("Enter the size of Array :");

scanf("%d", &size);
int arr1[size];

printf("Enter Array Elements \n");

for (int i = 0; i < size; i++)
{
scanf("%d", &arr1[i]);
}

// Output
int large = arr1[0];
int seclarge = arr1[0];
for (int i = 1; i < size; i++)
{

if (arr1[i] > large)

{s
seclarge = large;
large = arr1[i];
}
else if (arr1[i] > seclarge)
seclarge = arr1[i];

}
printf("Largest Number is : %d\n",large);
printf("Second Largest Number is : %d",seclarge);

}
Output:
Enter the size of Array :5
Enter Array Elements
8
9
0
1

1
87
Largest Number is :87
Second Largest Number is :9
Program 2: Write a program to reverse the contents of an array.

Program:
// WAP to Reverse a given array
#include <stdio.h>
int main()
{
int size;
int i, j;
int temp;

printf("Enter the size of Array :");

scanf("%d", &size);
int arr1[size];

printf("Enter Array Elements \n");

for (i = 0; i < size; i++)
{
scanf("%d", &arr1[i]);
}
printf("Original Array :");
for (i = 0; i < size; i++)
{
printf("%d\t", arr1[i]);
}
printf("\n");
i = 0;
j = size - 1;

// Reverse Operation
while (i < j)
{
temp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = temp;
i++;
j--;
}

printf("Reversed Array :");

for (int i = 0; i < size; i++)
{
printf("%d\t", arr1[i]);
}

2
 return 0;

Output:
Enter the size of Array :5
Enter Array Elements
8
4
0
90
7
Original Array: 8 4 0 90 7
Reversed Array: 7 90 0 4 8

Program 3: Write a program to rotate an array

Program:
// WAP to Rotate a given array
#include <stdio.h>
int main()
{
int size, k, n;

printf("Enter the size of Array :");

scanf("%d", &size);
int arr1[size];
int i;

printf("Enter Array Elements \n");

for (int i = 0; i < size; i++)
{
scanf("%d", &arr1[i]);
}

printf("Enter the Value of n : ");

scanf("%d", &n);
for (k = 0; k < n; k++)
{

3
 int temp = arr1[0];
for (i = 1; i <= size; i++)
{

arr1[i - 1] = arr1[i];
}
arr1[size - 1] = temp;
}

printf("After Rotaing an Array(%d times Rotation ) :",n);

for (int i = 0; i < size; i++)
{
printf("%d ", arr1[i]);
}
return 0;
}

Output:
Enter the size of Array :5
Enter Array Elements
7
8
0
1
2
Enter the value of n :1
After Rotating an Array(1 times Rotation) :8 0 1 2 7

Program 4: Write a program to merge two sorted arrays

Program
//WAP in to merge two given sorted array in ascending order and stored in third array with
ascending order
#include <stdio.h>
int main()
{
int size1, size2;
int i, j, k;
printf("Enter the size of array1 :");
scanf("%d", &size1);
printf("Enter the size of array2 :");
scanf("%d", &size2);

4
int arr1[size1];
int arr2[size2];
int arr3[size1 + size2];
printf("Enter the %d elements of 1st array in Ascending Order \n",size1);
for (i = 0; i < size1; i++)
{
scanf("%d", &arr1[i]);
}

printf("Enter the %d elements of 2nd array in Ascending Order \n",size2);

for (j = 0; j < size2; j++)
{
scanf("%d", &arr2[j]);
}
i = 0;
j = 0;
k = 0;
while (i < size1 && j < size2){
if (arr1[i] < arr2[j])
{
arr3[k] = arr1[i];
i++;
}
else
{
arr3[k] = arr2[j];
j++;
}

k++;
}
// Copy remaining elements of arr1 if any
while (i < size1){
arr3[k] = arr1[i];
i++;
k++;
}
// Copy remaining elements of arr2 if any
while (j < size2){
arr3[k] = arr2[j];
j++;
k++;
}

printf("\nThe first array elements are \n");

for (i = 0; i < size1; i++)
{

5
 printf("%d ", arr1[i]);
}
printf("\nThe Second array elements are \n");
for (j = 0; j < size2; j++)
{
printf("%d ", arr2[j]);
}
// Display the merged array
printf("\nMerged sorted array:\n");
for (k = 0; k < size1 + size2; k++)
{
printf("%d ", arr3[k]);
}
return 0;
}
Output:

Program 5: Implement the representation of sparse matrix

Program:
//WAP print the sparse matrix representation
#include <stdio.h>
int main()
{
int i, j, r = 1, count = 0;
int row,col;

6
int arr1[50][50];
int sp[100][3];
printf("Enter the no of Row :");
scanf("%d",&row);
printf("Enter the o of Col :");
scanf("%d",&col);
printf("Enter the elements of sparse matrix\n");
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
{
scanf("%d", &arr1[i][j]);
if (arr1[i][j] != 0)
{
count++;
}
}
}
sp[0][0] = row;
sp[0][1] = col;
sp[0][2] = count;
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
{
if (arr1[i][j] != 0)
{
sp[r][0] = i;
sp[r][1] = j;
sp[r][2] = arr1[i][j];
r++;
}
}
}

printf("Originsl Matrix\n");
for (i = 0; i < row; i++)
{
for (j = 0; j < col; j++)
{
printf("%d\t", arr1[i][j]);
}
printf("\n");
}
printf("\n");
printf("Sparse Matrix\n");

7
 for (i = 0; i < r; i++)
{

printf("%d\t%d\t%d\n", sp[i][0], sp[i][1], sp[i][2]);

}
return 0;
}
Output:

Program 6: Write a program to add two polynomials represented using two-dimensional

Array.
Program:
// //WAP of polynomial representation using 2d array where a polynomial containing n
terms the size of polynomial is 2xn
#include <stdio.h>

int main()
{
int size1, size2, size3;
printf("Enter the size of 1st polynomial :");
scanf("%d", &size1);
printf("Enter the size of 2nd polynomiAal :");
scanf("%d", &size2);
size3 = size1 + size2;
int arr1[2][size1], arr2[2][size2], sum[2][size3];

// int p1[2][5], p2[2][8], s[2][13];

int i, j, k;

printf("Enter the values of first Polynomial \n");

for (i = 0; i < size1; i++)
{
scanf("%d %d", &arr1[0][i], &arr1[1][i]);
}

8
printf("Enter the values of second Polynomial \n");
for (i = 0; i < size2; i++)
{
scanf("%d %d", &arr2[0][i], &arr2[1][i]);
}

i = 0;
j = 0;
k = 0;

while (i < size1 && j < size2)

{
if (arr1[1][i] == arr2[1][j])
{
sum[0][k] = arr1[0][i] + arr2[0][j];
sum[1][k] = arr1[1][i];
i++;
j++;
k++;
}
else if (arr1[1][i] > arr2[1][j])
{
sum[0][k] = arr1[0][i];
sum[1][k] = arr1[1][i];
i++;
k++;
}
else
{
sum[0][k] = arr2[0][j];
sum[1][k] = arr2[1][j];
j++;
k++;
}
}

// Add remaining terms from p1

while (i < size1)
{
sum[0][k] = arr1[0][i];
sum[1][k] = arr1[1][i];
i++;
k++;
}

// Add remaining terms from p2

9
 while (j < size2)
{
sum[0][k] = arr2[0][j];
sum[1][k] = arr2[1][j];
j++;
k++;
}

printf("Resultant Polynomial after addition..\n");

for (i = 0; i < k; i++)
{
printf("%dx^%d", sum[0][i], sum[1][i]);
if (i < k - 1)
printf("+");
}
printf("\n");
return 0;
}

Output:

10
Program 7: WAP to find the Transpose of a square matrix without using any additional
array. Transpose to be created in a given matrix itself.
Program:
#include<stdio.h>
int main()
{

int row_size,col_size;
printf("Enter the size of Row :");
scanf("%d",&row_size);
printf("Enter the size of Column :");
scanf("%d",&col_size);

int arr1[row_size][col_size],arr2[row_size][col_size];
int i,j;
printf("Enter the elements of Matrix \n");
for(i=0;i<row_size;i++){
for(j=0;j<col_size;j++)
{

11
 scanf("%d",&arr1[i][j]);
}
}
printf("\nOriginal Matrix \n");
for(i=0;i<row_size;i++)
{
for(j=0;j<col_size;j++)
{
printf("%d ",arr1[i][j]);
}
printf("\n");
}
printf("Transpose Matrix \n");
for(i=0;i<row_size;i++)
{
for(j=0;j<col_size;j++)
{
arr2[j][i]=arr1[i][j];
printf("%d ",arr1[j][i]);
}
printf("\n");
}
}

Program:

12
Program 8: WAP to implement Towers of Hanoi Problem.
Program:
//WAP to implement Towers of Hanoi Problem
#include <stdio.h>
#include<conio.h>
static int count=0;
int main()
{
int a=1,b=2,c=3,k;
void tower(int,int,int,int);
printf("Enter the numbers of disks in the Tower\n");
scanf("%d",&k);
printf("\n");
tower(k,a,b,c);
printf("\nTotal value :%d",count);
return 0;
}

void tower(int n,int x,int y,int z)

{
if(n==1)
{
printf("%d ->%d\n",x,y);
count++;
}
else{
tower(n-1,x,z,y);
printf("%d ->%d\n",x,z);
count++;

tower(n-1,y,x,z);
}
}
Output:

13
Program 9: WAP to implement Ackermann’s function.

Ackermann Function Definition:

markdown
Copy code
A(m, n) =
n + 1 if m == 0
A(m - 1, 1) if m > 0 and n == 0
A(m - 1, A(m, n - 1)) if m > 0 and n > 0

Program:
#include <stdio.h>
// Function to implement Ackermann's function
int ackermann(int m, int n) {
if (m == 0)
return n + 1;
else if (n == 0)
return ackermann(m - 1, 1);
else
return ackermann(m - 1, ackermann(m, n - 1));
}

int main() {
int m, n;

printf("Enter two non-negative integers (m and n): ");

scanf("%d %d", &m, &n);

if (m < 0 || n < 0) {
printf("Only non-negative integers are allowed.\n");
return 1;
}

14
 int result = ackermann(m, n);
printf("Ackermann(%d, %d) = %d\n", m, n, result);

return 0;
}

Output:

Program 10: WAP to

create a singly LinkedList and print the contents of it.

Program:
//Linked list representation in C
// This program creates a linked list and prints its contents.
#include <stdio.h>
#include<stdlib.h>

struct linklist
{
int info;
struct linklist *next;
};

typedef struct linklist node;

int main()
{
node *head;

void create(node *);

void print(node *);

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

create(head);
print(head);
return 0;
}

15
void create(node *list)
{
printf("Enter the Data :");
scanf("%d", &list->info);
if (list->info == -1)
list->next = NULL;
else{
list->next = (node *)malloc(sizeof(node));
create(list->next);
}
}
void print(node *list)
{
printf("\nLinkedList Contenets : ");
while (list != NULL)
{
printf("%d ", list->info);
list = list->next;
}
}
Output:

Program 11: Wap to delete the first and last node of Singly LinkedList.
Program:
//Linked list Representation and print its contents
#include <stdio.h>
#include<stdlib.h>

struct linklist
{
int info;
struct linklist *next;
};

typedef struct linklist node;

16
int main()
{
node *head;

void create(node *);

void print(node *);

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

create(head);
print(head);

void deletelast(node *x);

deletelast(head);

print(head);
printf("\n\nAfter Deleting First Node\n");
head = head->next;
print(head);
return 0;
}
void create(node *list)
{
printf("Enter the Data :");
scanf("%d", &list->info);
if (list->info == -1)
list->next = NULL;
else{
list->next = (node *)malloc(sizeof(node));
create(list->next);
}
}
void print(node *list)

printf("LinkedList Contenets : ");

while (list != NULL)
{
printf("%d ", list->info);
list = list->next;
}
}
void deletelast (node *x)
{
printf("\n\nAfter Deleting Last Node\n");

17
 node *y;
while(x->next!=NULL)
{
y=x;
x=x->next;
}
y->next=NULL;
}

Output:

Program 12: Write a program to add a new node in the beginning/ as the last node in a
singly linked list.
Program:
#include <stdio.h>
#include <stdlib.h>

// Define the node structure

struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}

18
// Function to print the linked list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}

// Add node at the beginning

void addAtBeginning(struct Node** head, int value) {
struct Node* newNode = createNode(value);
newNode->next = *head;
*head = newNode;
}

// Add node at the end

void addAtEnd(struct Node** head, int value) {
struct Node* newNode = createNode(value);
if (*head == NULL) {
*head = newNode;
return;
}

struct Node* temp = *head;

while (temp->next != NULL) {
temp = temp->next;
}
temp->next = newNode;
}

// Main function
int main() {
struct Node* head = NULL;

// Adding nodes
addAtEnd(&head, 10); // List: 10
addAtEnd(&head, 20); // List: 10 -> 20
addAtBeginning(&head, 5); // List: 5 -> 10 -> 20
addAtEnd(&head, 30); // List: 5 -> 10 -> 20 -> 30

printf("Linked List:\n");
printList(head);

return 0;
}

19
Output:

Program 13: Write a program to reverse a singly linked list.

Program:
#include <stdio.h>
#include <stdlib.h>

// Define the structure for a node

struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*) malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
}
// Function to print the linked list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
// Function to reverse the linked list
struct Node* reverseList(struct Node* head) {
struct Node* prev = NULL;
struct Node* current = head;
struct Node* next = NULL;

while (current != NULL) {

next = current->next; // Save next

20
 current->next = prev; // Reverse current node's pointer
prev = current; // Move prev to current
current = next; // Move to next node
}
return prev; // New head
}
// Main function
int main() {
// Creating a simple linked list: 10 -> 20 -> 30 -> 40 -> NULL
struct Node* head = createNode(10);
head->next = createNode(20);
head->next->next = createNode(30);
head->next->next->next = createNode(40);

printf("Original List:\n");
printList(head);

head = reverseList(head);

printf("Reversed List:\n");
printList(head);
return 0;
}

Output:

Program 14: Write a program to implement Quick Sort.

Program:
#include <stdio.h>

void quicksort(int array[], int low, int high);

int partition(int array[], int low, int high);

int main() {
int myArray[] = {64, 34, 25, 12, 22, 11, 90, 5};
int n = sizeof(myArray) / sizeof(myArray[0]);

21
 quicksort(myArray, 0, n - 1);

printf("Sorted array: ");

for (int i = 0; i < n; i++) {
printf("%d ", myArray[i]);
}
return 0;
}
void quicksort(int array[], int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quicksort(array, low, pivotIndex - 1);
quicksort(array, pivotIndex + 1, high);
}
}

int partition(int array[], int low, int high) {

int pivot = array[high];
int i = low - 1;

for (int j = low; j < high; j++) {

if (array[j] <= pivot) {
i++;
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
int temp = array[i + 1];
array[i + 1] = array[high];
array[high] = temp;
return i + 1;
}
Output:
Sorted array : 5 11 12 22 25 34 64 90

Program 15: Write a program to find the Kth largest element from an array using the
technique used in Quick Sort.
Program:
#include <stdio.h>

// Function to swap two elements

void swap(int *a, int *b) {

22
 int temp = *a;
*a = *b;
*b = temp;
}

// Partition function similar to Quick Sort

int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low;

for (int j = low; j < high; j++) {

if (arr[j] > pivot) { // > for Kth largest
swap(&arr[i], &arr[j]);
i++;
}
}
swap(&arr[i], &arr[high]);
return i;
}

// Function to find Kth largest element

int findKthLargest(int arr[], int low, int high, int k) {
if (low <= high) {
int index = partition(arr, low, high);

if (index == k - 1)
return arr[index];
else if (index > k - 1)
return findKthLargest(arr, low, index - 1, k);
else
return findKthLargest(arr, index + 1, high, k);
}
return -1; // not found
}

// Main function
int main() {
int arr[] = {12, 3, 5, 7, 19, 0, 4};
int n = sizeof(arr) / sizeof(arr[0]);
int k;
printf("Enter the Largest no element:");
scanf("%d",&k);

int result = findKthLargest(arr, 0, n - 1, k);

if (result != -1)
printf("The %dth largest element is %d\n", k, result);
else

23
 printf("Invalid input.\n");

return 0;
}

Output:
Enter the largest no Element: 4
The 4th largest element is 5

Program 16: Write a program to implement Bubble Sort.

Program:
#include <stdio.h>

void bubbleSort(int arr[], int n) {

int i, j, temp;

// Outer loop for passes

for (i = 0; i < n - 1; i++) {
// Inner loop for comparisons
for (j = 0; j < n - i - 1; j++) {
// Swap if the element is greater than the next
if (arr[j] > arr[j + 1]) {
// Swapping elements
temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}

int main() {
int arr[100], n, i;

// Input number of elements

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

// Input array elements

printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);

24
 }

// Calling bubble sort function

bubbleSort(arr, n);

// Display sorted array

printf("Sorted array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

Output:

25
Program 17: Write a program to implement insertion sort.
Program:
#include <stdio.h>

void insertionSort(int arr[], int n) {

int i, key, j;

// Loop through the array

for (i = 1; i < n; i++) {
key = arr[i]; // Store the current element
j = i - 1;

// Move elements that are greater than key to one position ahead
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
}

// Place the key at the correct position

arr[j + 1] = key;
}
}

int main() {
int arr[100], n, i;

// Input number of elements

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

// Input array elements

printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Call the insertion sort function

insertionSort(arr, n);

// Output the sorted array

printf("Sorted array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;

26
}

Output:

Program 18: Write a program to implement Selection Sort.

Program:
#include <stdio.h>

void selectionSort(int arr[], int n) {

int i, j, minIndex, temp;

// Loop for each element

for (i = 0; i < n - 1; i++) {
minIndex = i; // Assume the minimum is at position i

// Find the index of the minimum element in the remaining array

for (j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) {
minIndex = j;
}
}

// Swap the found minimum with the first unsorted element

temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}

int main() {

27
 int arr[100], n, i;

// Input number of elements

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

// Input array elements

printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Call selection sort function

selectionSort(arr, n);

// Output sorted array

printf("Sorted array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}

return 0;
}

Output:

28
Program 19: Implement Linear Search. Write a module to add the element at the Kth
position if the searching is a failure.
Program:
#include <stdio.h>

// Linear search function

int linearSearch(int arr[], int n, int key) {
for (int i = 0; i < n; i++) {
if (arr[i] == key) {
return i; // Element found, return index
}
}
return -1; // Element not found
}

// Insert element at kth position

void insertAtK(int arr[], int *n, int key, int k) {
if (k < 0 || k > *n) {
printf("Invalid position. Cannot insert.\n");
return;
}

// Shift elements to the right

for (int i = *n; i > k; i--) {
arr[i] = arr[i - 1];
}

// Insert the element

arr[k] = key;
(*n)++; // Increase size of array
}

int main() {
int arr[100], n, i, key, k, pos;

29
 // Input number of elements
printf("Enter number of elements: ");
scanf("%d", &n);

// Input array elements

printf("Enter %d elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input the key to search

printf("Enter the element to search: ");
scanf("%d", &key);

// Perform linear search

pos = linearSearch(arr, n, key);

if (pos != -1) {
printf("Element found at position %d\n", pos);
} else {
printf("Element not found.\n");

// Ask for Kth position

printf("Enter position (0 to %d) to insert the element: ", n);
scanf("%d", &k);

// Insert the key at Kth position

insertAtK(arr, &n, key, k);

// Print the updated array

printf("Updated array:\n");
for (i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
}

return 0;
}

Output:

30
Program 20: Write a program to implement Binary search.
Program:
#include <stdio.h>

// Binary Search Function

int binarySearch(int arr[], int n, int key) {
int low = 0, high = n - 1, mid;

while (low <= high) {

mid = (low + high) / 2;

if (arr[mid] == key)
return mid; // Element found
else if (arr[mid] < key)
low = mid + 1;
else
high = mid - 1;
}

return -1; // Element not found

}

int main() {

31
 int arr[100], n, i, key, result;

// Input number of elements

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

// Input sorted array elements

printf("Enter %d sorted elements:\n", n);
for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}

// Input the key to search

printf("Enter the element to search: ");
scanf("%d", &key);

// Call binary search

result = binarySearch(arr, n, key);

// Output result
if (result != -1)
printf("Element found at position %d\n", result);
else
printf("Element not found.\n");

return 0;
}

Output:

32
--------------------*-------------------*-----------------------
End.

33