PRACTICAL FILE
DATA STRUCTURE
KCS-351
SUBMITTED BY-
ADEEBA FATIMA
22GCEBCSD064
CSD
PROGRAM-1
Array addition using Two-Dimensional Array
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#define ROWS 3
#define COLUMNS 3
void add_2d_arrays(int array1[][COLUMNS], int array2[][COLUMNS], int result[][COLUMNS])
{
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLUMNS; j++) {
result[i][j] = array1[i][j] + array2[i][j];
int main() {
int array1[ROWS][COLUMNS] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int array2[ROWS][COLUMNS] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}};
int result[ROWS][COLUMNS];
add_2d_arrays(array1, array2, result);
printf("Result of adding two arrays: \n");
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLUMNS; j++) {
printf("%d ", result[i][j]);
printf("\n");
}
return 0;
OUTPUT:
Result of adding two arrays:
10 10 10
10 10 10
10 10 10
Program For multiplication of 2 2D array
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#define ROWS 3
#define COLUMNS 3
void multiply_2d_arrays(int array1[][COLUMNS], int array2[][COLUMNS], int result[]
[COLUMNS]) {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLUMNS; j++) {
result[i][j] = 0;
for (int k = 0; k < COLUMNS; k++) {
result[i][j] += array1[i][k] * array2[k][j];
}
int main() {
int array1[ROWS][COLUMNS] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int array2[ROWS][COLUMNS] = {{9, 8, 7}, {6, 5, 4}, {3, 2, 1}};
int result[ROWS][COLUMNS];
multiply_2d_arrays(array1, array2, result);
printf("Result of multiplying two arrays: \n");
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLUMNS; j++) {
printf("%d ", result[i][j]);
printf("\n");
return 0;
OUTPUT:
Result of multiplying two arrays:
30 24 18
84 69 54
138 114 90
Program-2
Program to Find the Transpose of a Matrix
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#define ROWS 3
#define COLUMNS 3
void transpose_matrix(int array[][COLUMNS], int transposed_array[][ROWS]) {
for (int i = 0; i < ROWS; i++) {
for (int j = 0; j < COLUMNS; j++) {
transposed_array[j][i] = array[i][j];
int main() {
int array[ROWS][COLUMNS] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}};
int transposed_array[COLUMNS][ROWS];
transpose_matrix(array, transposed_array);
printf("Transposed matrix: \n");
for (int i = 0; i < COLUMNS; i++) {
for (int j = 0; j < ROWS; j++) {
printf("%d ", transposed_array[i][j]);
printf("\n");
return 0;
}
OUTPUT:
Transposed matrix:
147
258
369
PROGRAM-3
C Program for STACK Using Arrays
#include<stdio.h>
//Program by: Saurabh Kumar Singh
#include<stdlib.h>
int n, top = -1, *stack;
void push(int x){
if(top==n) return;
stack[++top]=x;
int pop(){
if(top==-1) return -1;
return stack[top--];
int peek(){
if(top==-1) return -1;
return stack[top];
}
void display(){
for(inti=top ; i>-1 ; i--) printf("%d ",stack[i]);
printf("\n\n");
int main(){
n = 10;
printf("Initializing the stack with size 10\n\n");
stack = (int*)malloc(n*sizeof(int));
printf("Pushing elements into the stack\n1\n2\n3\n\n");
push(1);
push(2);
push(3);
printf("Displaying elements of the stack -\n");
display();
printf("The top of the stack = %d\n\n",peek());
printf("Pop the top of the stack = %d\n\n",pop());
printf("Pop the top of the stack = %d\n\n",pop());
printf("Displaying elements of the stack -\n");
display();
return 0;
OUTPUT:
Initializing the stack with size 10
Pushing elements into the stack 1 2 3
Displaying elements of the stack -
321
The top of the stack = 3
Pop the top of the stack = 3
Pop the top of the stack = 2
Displaying elements of the stack -
PROGRAM-4
Implementation of Queue using Array in C
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#include <stdlib.h>
#define MAX_SIZE 100
struct Queue {
int front;
int rear;
int data[MAX_SIZE];
};
void enqueue(struct Queue *queue, int item) {
if (queue->rear == MAX_SIZE - 1) {
printf("Error: Queue overflow\n");
return;
queue->rear++;
queue->data[queue->rear] = item;
}
int dequeue(struct Queue *queue) {
if (queue->front == queue->rear) {
printf("Error: Queue underflow\n");
return -1;
queue->front++;
int item = queue->data[queue->front];
return item;
int main() {
struct Queue queue;
[Link] = 0;
[Link] = -1
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
printf("%d dequeued from queue\n", dequeue(&queue));
printf("%d dequeued from queue\n", dequeue(&queue));
printf("%d dequeued from queue\n", dequeue(&queue));
return 0;
OUTPUT:
20 dequeued from queue
30 dequeued from queue
Error: Queue underflow
-1 dequeued from queue
PROGRAM-5
C program to implement circular queue using array
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#include <stdlib.h>
#define MAX_SIZE 100
struct CircularQueue {
int front;
int rear;
int data[MAX_SIZE];
};
void enqueue(struct CircularQueue *queue, int item) {
int next_rear = (queue->rear + 1) % MAX_SIZE;
if (next_rear == queue->front) {
printf("Error: Queue overflow\n");
return;
queue->rear = next_rear;
queue->data[queue->rear] = item;
int dequeue(struct CircularQueue *queue) {
if (queue->front == queue->rear) {
printf("Error: Queue underflow\n");
return -1;
}
queue->front = (queue->front + 1) % MAX_SIZE;
int item = queue->data[queue->front];
return item;
int main() {
struct CircularQueue queue;
[Link] = 0;
[Link] = -1;
enqueue(&queue, 10);
enqueue(&queue, 20);
enqueue(&queue, 30);
printf("%d dequeued from queue\n", dequeue(&queue));
printf("%d dequeued from queue\n", dequeue(&queue));
printf("%d dequeued from queue\n", dequeue(&queue));
return 0;
Output:
Error: Queue overflow
Error: Queue overflow
Error: Queue overflow
8257536 dequeued from queue
0 dequeued from queue
48 dequeued from queue
PROGRAM-6
Program to implement Stack using Linked List in C language
#include <stdio.h>
#include <stdlib.h>
// Structure to create a node with data and the next pointer
struct Node {
int data;
struct Node *next;
};
Node* top = NULL;
// Push() operation on a stack
void push(int value) {
struct Node *newNode;
newNode = (struct Node *)malloc(sizeof(struct Node));
newNode->data = value; // assign value to the node
if (top == NULL) {
newNode->next = NULL;
} else {
newNode->next = top; // Make the node as top
top = newNode; // top always points to the newly created node
printf("Node is Inserted\n\n");
}
int pop() {
if (top == NULL) {
printf("\nStack Underflow\n");
} else {
struct Node *temp = top;
inttemp_data = top->data;
top = top->next;
free(temp);
returntemp_data;
void display() {
// Display the elements of the stack
if (top == NULL) {
printf("\nStack Underflow\n");
} else {
printf("The stack is \n");
struct Node *temp = top;
while (temp->next != NULL) {
printf("%d--->", temp->data);
temp = temp->next;
printf("%d--->NULL\n\n", temp->data);
}
int main() {
int choice, value;
printf("\nImplementation of Stack using Linked List\n");
while (1) {
printf("1. Push\n2. Pop\n3. Display\n4. Exit\n");
printf("\nEnter your choice : ");
scanf("%d", &choice);
switch (choice) {
case 1:
printf("\nEnter the value to insert: ");
scanf("%d", &value);
push(value);
break;
case 2:
printf("Popped element is :%d\n", pop());
break;
case 3:
display();
break;
case 4:
exit(0);
break;
default:
printf("\nWrong Choice\n");
OUTPUT-
Implementation of Stack using Linked List
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 1
Enter the value to insert: 12
Node is Inserted
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 1
Enter the value to insert: 45
Node is Inserted
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 1
Enter the value to insert: 56
Node is Inserted
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 3
The stack is
56--->45--->12--->NULL
POP
Implementation of Stack using Linked List
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 1
Enter the value to insert: 12
Node is Inserted
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 1
Enter the value to insert: 45
Node is Inserted
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 1
Enter the value to insert: 56
Node is Inserted
1. Push
2. Pop
3. Display
4. Exit
Enter your choice : 3
The stack is
56--->45--->12--->NULL
PROGRAM-7
Linked list based implementation of queue
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Queue {
struct Node *front;
struct Node *rear;
};
struct Node *newNode(int k) {
struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = k;
temp->next = NULL;
return temp;
}
struct Queue *createQueue() {
struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
q->front = q->rear = NULL;
return q;
}
void enQueue(struct Queue *q, int k) {
struct Node *temp = newNode(k);
if (q->rear == NULL) {
q->front = q->rear = temp;
return;
}
q->rear->next = temp;
q->rear = temp;
}
struct Node *deQueue(struct Queue *q) {
if (q->front == NULL) {
printf("Queue is Empty\n");
return NULL;
}
struct Node *temp = q->front;
q->front = q->front->next;
if (q->front == NULL) {
q->rear = NULL;
}
return temp;
}
int main() {
struct Queue *q = createQueue();
int choice, item;
while (1) {
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Quit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter the item to be enqueued: ");
scanf("%d", &item);
enQueue(q, item);
break;
case 2:
item = deQueue(q)->data;
printf("Dequeued item is %d\n", item);
break;
case 3:
exit(0);
default:
printf("Invalid choice\n");
}
}
return 0;
}
OUTPUT:
1. Enqueue
2. Dequeue
3. Quit
PROGRAM-8
C Program to Implement Circular Queue using Linked list
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#include <stdlib.h>
struct Node {
int data;
struct Node *next;
};
struct Queue {
struct Node *rear;
};
struct Node *newNode(int k) {
struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp->data = k;
temp->next = NULL;
return temp;
struct Queue *createQueue() {
struct Queue *q = (struct Queue*)malloc(sizeof(struct Queue));
q->rear = NULL;
return q;
void enQueue(struct Queue *q, int k) {
struct Node *temp = newNode(k);
if (q->rear == NULL) {
q->rear = temp;
temp->next = q->rear;
} else {
temp->next = q->rear->next;
q->rear->next = temp;
q->rear = temp;
struct Node *deQueue(struct Queue *q) {
if (q->rear == NULL) {
printf("Queue is Empty\n");
return NULL;
struct Node *temp = q->rear->next;
if (q->rear == q->rear->next) {
q->rear = NULL;
} else {
q->rear->next = temp->next;
return temp;
int main() {
struct Queue *q = createQueue();
enQueue(q, 10);
enQueue(q, 20);
deQueue(q);
deQueue(q);
enQueue(q, 30);
enQueue(q, 40);
enQueue(q, 50);
struct Node *n = deQueue(q);
if (n != NULL) {
printf("Dequeued item is %d\n", n->data);
return 0;
}
OUTPUT:
Dequeued item is 30
PROGRAM-9
C Program to Implement Binary Tree using Linked List
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *new_node(int item) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = item;
node->left = NULL;
node->right = NULL;
return node;
void inorder_traversal(struct Node *root) {
if (root != NULL) {
inorder_traversal(root->left);
printf("%d ", root->data);
inorder_traversal(root->right);
int main() {
struct Node *root = new_node(1);
root->left = new_node(2);
root->right = new_node(3);
root->left->left = new_node(4);
root->left->right = new_node(5);
printf("Inorder traversal of binary tree is: ");
inorder_traversal(root);
return 0;
OUTPUT:
Inorder traversal of binary tree is: 4 2 5 1 3
PROGRAM-10
Binary Search Tree operations in C
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *new_node(int item) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = item;
node->left = NULL;
node->right = NULL;
return node;
struct Node *insert(struct Node *node, int item) {
if (node == NULL) {
return new_node(item);
if (item < node->data) {
node->left = insert(node->left, item);
} else if (item > node->data) {
node->right = insert(node->right, item);
return node;
}
struct Node *search(struct Node *node, int item) {
if (node == NULL || node->data == item) {
return node;
if (node->data < item) {
return search(node->right, item);
return search(node->left, item);
void inorder_traversal(struct Node *node) {
if (node != NULL) {
inorder_traversal(node->left);
printf("%d ", node->data);
inorder_traversal(node->right);
int main() {
struct Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal of the binary search tree: ");
inorder_traversal(root);
struct Node *result = search(root, 60);
if (result == NULL) {
printf("\nElement not found in the binary search tree");
} else {
printf("\nElement found in the binary search tree");
return 0;
OUTPUT:
Inorder traversal of the binary search tree: 20 30 40 50 60 70 80
Element found in the binary search tree
PROGRAM-12
To Implement BFS using Linked List
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#include <stdlib.h>
struct Node {
int data;
struct Node *left;
struct Node *right;
};
struct Node *new_node(int item) {
struct Node *node = (struct Node *)malloc(sizeof(struct Node));
node->data = item;
node->left = NULL;
node->right = NULL;
return node;
struct Node *insert(struct Node *node, int item) {
if (node == NULL) {
return new_node(item);
if (item < node->data) {
node->left = insert(node->left, item);
} else if (item > node->data) {
node->right = insert(node->right, item);
return node;
struct Node *search(struct Node *node, int item) {
if (node == NULL || node->data == item) {
return node;
}
if (node->data < item) {
return search(node->right, item);
return search(node->left, item);
void inorder_traversal(struct Node *node) {
if (node != NULL) {
inorder_traversal(node->left);
printf("%d ", node->data);
inorder_traversal(node->right);
int main() {
struct Node *root = NULL;
root = insert(root, 50);
insert(root, 30);
insert(root, 20);
insert(root, 40);
insert(root, 70);
insert(root, 60);
insert(root, 80);
printf("Inorder traversal of the binary search tree: ");
inorder_traversal(root);
struct Node *result = search(root, 60);
if (result == NULL) {
printf("\nElement not found in the binary search tree");
} else {
printf("\nElement found in the binary search tree");
return 0;
OUTPUT:
Inorder traversal of the binary search tree: 20 30 40 50 60 70 80
Element found in the binary search tree
PROGRAM-13
Depth First Search (DFS) Program in C [Adjacency Matrix]
#include <stdio.h>
//Program by: Saurabh Kumar Singh
#include <stdlib.h>
#define MAX 100
int adj[MAX][MAX];
int visited[MAX];
int n;
void dfs(int u) {
int v;
visited[u] = 1;
for (v = 0; v < n; v++) {
if (adj[u][v] == 1 && visited[v] == 0) {
dfs(v);
int main() {
int i, j;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter the adjacency matrix:\n");
for (i = 0; i < n; i++) {
for (j = 0; j < n; j++) {
scanf("%d", &adj[i][j]);
for (i = 0; i < n; i++) {
visited[i] = 0;
dfs(0);
return 0;
Output:
Enter number of vertices: 2
Enter the adjacency matrix:
12 23 45 56
PROGRAM-14
Implementing Linear Search in C
#include <stdio.h>
int linear_search(int arr[], int n, int x) {
int i;
for (i = 0; i < n; i++) {
if (arr[i] == x) {
return i;
return -1;
int main() {
int arr[] = {10, 20, 80, 30, 60, 50, 110, 100, 130, 170};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 110;
int result = linear_search(arr, n, x);
if (result == -1) {
printf("Element is not present in the array\n");
} else {
printf("Element is present at index %d\n", result);
}
return 0;
OUTPUT:
Element is present at index 6
PROGRAM-15
To implement Binary Search
#include <stdio.h>
int binary_search(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l) / 2;
if (arr[mid] == x) {
return mid;
}
if (arr[mid] > x) {
return binary_search(arr, l, mid - 1, x);
}
return binary_search(arr, mid + 1, r, x);
}
return -1;
}
int main() {
int arr[] = {2, 3, 4, 10, 40};
int n = sizeof(arr) / sizeof(arr[0]);
int x = 10;
int result = binary_search(arr, 0, n - 1, x);
if (result == -1) {
printf("Element is not present in the array\n");
} else {
printf("Element is present at index %d\n", result);
}
return 0;
}
OUTPUT:
Element is present at index 3
PROGRAM-16
To Implement Bubble sort
#include <stdio.h>
//Program by: Saurabh Kumar Singh
int main(){
intarr[50], num, x, y, temp;
printf("Please Enter the Number of Elements you want in the array: ");
scanf("%d", &num);
printf("Please Enter the Value of Elements: ");
for(x = 0; x <num; x++)
scanf("%d", &arr[x]);
for(x = 0; x <num - 1; x++){
for(y = 0; y <num - x - 1; y++){
if(arr[y] >arr[y + 1]){
temp = arr[y];
arr[y] = arr[y + 1];
arr[y + 1] = temp;
}
}
printf("Array after implementing bubble sort: ");
for(x = 0; x <num; x++){
printf("%d ", arr[x]);
return 0;
OUTPUT:
Please Enter the Number of Elements you want in the array: 10
Please Enter the Value of Elements: 15 24 15 75 36 48 25 33 14 20
Array after implementing bubble sort: 14 15 15 20 24 25 33 36 48 75
PROGRAM-17
To implement selection sort
#include <stdio.h>
//program by: Saurabh Kumar Singh
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
void selection_sort(int arr[], int n) {
int i, j, min_idx;
for (i = 0; i < n-1; i++) {
min_idx = i;
for (j = i+1; j < n; j++) {
if (arr[j] < arr[min_idx]) {
min_idx = j;
swap(&arr[min_idx], &arr[i]);
void print_array(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
selection_sort(arr, n);
printf("Sorted array: \n");
print_array(arr, n);
return 0;
OUTPUT:
Sorted array:
11 12 22 25 64
PROGRAM-18
To implement Insertion sort
#include <stdio.h>
//Program by: Saurabh Kumar Singh
void insertion_sort(int arr[], int n) {
int i, key, j;
for (i = 1; i < n; i++) {
key = arr[i];
j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j = j - 1;
arr[j + 1] = key;
void print_array(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {25, 47, 52, 10, 32, 33};
int n = sizeof(arr) / sizeof(arr[0]);
insertion_sort(arr, n);
printf("Sorted array: \n");
print_array(arr, n);
return 0;
OUTPUT:
Sorted array: 10 25 32 33 47 52
PROGRAM-19
To implement merge sort
#include <stdio.h>
//Program by: Saurabh Kumar Singh
void merge(int arr[], int l, int m, int r) {
int i, j, k;
int n1 = m - l + 1;
int n2 = r - m;
int L[n1], R[n2];
for (i = 0; i < n1; i++) {
L[i] = arr[l + i];
for (j = 0; j < n2; j++) {
R[j] = arr[m + 1 + j];
i = 0;
j = 0;
k = l;
while (i < n1 && j < n2) {
if (L[i] <= R[j]) {
arr[k] = L[i];
i++;
} else {
arr[k] = R[j];
j++;
k++;
while (i < n1) {
arr[k] = L[i];
i++;
k++;
while (j < n2) {
arr[k] = R[j];
j++;
k++;
void merge_sort(int arr[], int l, int r) {
if (l < r) {
int m = l + (r - l) / 2;
merge_sort(arr, l, m);
merge_sort(arr, m + 1, r);
merge(arr, l, m, r);
void print_array(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
merge_sort(arr, 0, n - 1);
printf("Sorted array: \n");
print_array(arr, n);
return 0;
OUTPUT:
Sorted array: 12 23 45 56 67 89
PROGRAM-20
To implement Heap sort
#include <stdio.h>
//Program by: Saurabh Kumar Singh
void swap(int *a, int *b) {
int temp = *a;
*a = *b;
*b = temp;
void heapify(int arr[], int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest != i) {
swap(&arr[i], &arr[largest]);
heapify(arr, n, largest);
void heap_sort(int arr[], int n) {
int i;
for (i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
for (i = n - 1; i >= 0; i--) {
swap(&arr[0], &arr[i]);
heapify(arr, i, 0);
void print_array(int arr[], int size) {
int i;
for (i = 0; i < size; i++) {
printf("%d ", arr[i]);
printf("\n");
int main() {
int arr[] = {64, 25, 12, 22, 11};
int n = sizeof(arr) / sizeof(arr[0]);
heap_sort(arr, n);
printf("Sorted array: \n");
print_array(arr, n);
return 0;
OUTPUT:
Sorted array: 11 12 22 25 64