ITM UNIVERSITY, GWALIOR (M.
P)
DSA PRACTICAL FILE
(CSL0204)
Submitted To: Submitted By:
H.N Verma Sir Yuvraj Singh
Dept. of CSE
BETN1AI25283
Program 1
Write a C program that uses functions to perform the following:
a) Create a singly linked list of integers.
b) Delete a given integer from the above linked list.
c) Display the contents of the above list after deletion.
Ans. Input
#include <stdio.h>
struct Node {
int data;
struct Node* next;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
return newNode;
struct Node* insertEnd(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL) {
return newNode;
struct Node* temp = head;
while (temp->next != NULL) {
temp = temp->next;
temp->next = newNode;
return head;
struct Node* deleteValue(struct Node* head, int value) {
struct Node *temp = head, *prev = NULL;
if (temp != NULL && temp->data == value) {
head = temp->next;
free(temp);
return head;
while (temp != NULL && temp->data != value) {
prev = temp;
temp = temp->next;
if (temp == NULL) {
printf("Value not found in list.\n");
return head;
prev->next = temp->next;
free(temp);
return head;
void display(struct Node* head) {
struct Node* temp = head;
if (temp == NULL) {
printf("List is empty.\n");
return;
}
printf("Linked List: ");
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
printf("NULL\n");
int main() {
struct Node* head = NULL;
int n, value, del;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &value);
head = insertEnd(head, value);
printf("\nOriginal ");
display(head);
printf("Enter value to delete: ");
scanf("%d", &del);
head = deleteValue(head, del);
printf("\nAfter deletion ");
display(head);
return 0;
Output
Program 2
Write a C program that uses functions to perform the following:
a) Create a doubly linked list of integers.
b) Delete a given integer from the above doubly linked list. c) Display the contents of the above list after deletion.
Ans. Input
#include <stdio.h>
struct Node {
int data;
struct Node *prev;
struct Node *next;
};
struct Node* createNode(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->prev = NULL;
newNode->next = NULL;
return newNode;
struct Node* insertEnd(struct Node* head, int value) {
struct Node* newNode = createNode(value);
if (head == NULL)
return newNode;
struct Node* temp = head;
while (temp->next != NULL)
temp = temp->next;
temp->next = newNode;
newNode->prev = temp;
return head;
struct Node* deleteValue(struct Node* head, int value) {
struct Node* temp = head;
while (temp != NULL && temp->data != value)
temp = temp->next;
if (temp == NULL) {
printf("Value not found in list.\n");
return head;
if (temp->prev == NULL)
head = temp->next;
else
temp->prev->next = temp->next;
if (temp->next != NULL)
temp->next->prev = temp->prev;
free(temp);
return head;
void display(struct Node* head) {
struct Node* temp = head;
if (temp == NULL) {
printf("List is empty.\n");
return;
printf("Doubly Linked List: ");
while (temp != NULL) {
printf("%d <-> ", temp->data);
temp = temp->next;
} printf("NULL\n");
int main() {
struct Node* head = NULL;
int n, value, del;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &value);
head = insertEnd(head, value);
printf("\nOriginal ");
display(head);
printf("Enter value to delete: ");
scanf("%d", &del);
head = deleteValue(head, del);
printf("\nAfter deletion ");
display(head);
return 0;
Output
Program 3
Write a C program that uses stack operations to convert a given infix expression into its postfix Equivalent,
Implement the stack using an array.
Input
#include <stdio.h>
char stack[MAX];
int top = -1;
void push(char x) {
stack[++top] = x;
char pop() {
if (top == -1)
return -1;
else
return stack[top--];
}int precedence(char x) {
if (x == '+' || x == '-')
return 1;
if (x == '*' || x == '/')
return 2;
if (x == '^')
return 3;
return 0;
int main() {
char infix[100], postfix[100];
int i = 0, j = 0;
printf("Enter infix expression: ");
scanf("%s", infix);
while (infix[i] != '\0') {
char ch = infix[i];
if (isalnum(ch)) {
postfix[j++] = ch;
else if (ch == '(') {
push(ch);
else if (ch == ')') {
while (stack[top] != '(')
postfix[j++] = pop();
pop(); }
else {
while (top != -1 && precedence(stack[top]) >= precedence(ch))
postfix[j++] = pop();
push(ch);
i++;
}while (top != -1)
postfix[j++] = pop();
postfix[j] = '\0';
printf("Postfix expression: %s\n", postfix);
return 0;
Output
Program 4
Write C programs to implement a double ended queue ADT using
i)array and
Input
#include <stdio.h>
int deque[MAX];
int front = -1, rear = -1;
void insertFront(int x){
if((front==0 && rear==MAX-1) || front==rear+1)
printf("Deque Overflow\n");
else{
if(front==-1){
front=rear=0;
else if(front==0){
front=MAX-1;
else{
front--;
deque[front]=x;
void insertRear(int x){
if((front==0 && rear==MAX-1) || front==rear+1)
printf("Deque Overflow\n");
else{
if(front==-1){
front=rear=0;
}
else if(rear==MAX-1){
rear=0;
else{
rear++;
deque[rear]=x;
void deleteFront(){
if(front==-1){
printf("Deque Underflow\n");
else{
printf("Deleted: %d\n", deque[front]);
if(front==rear){
front=rear=-1;
else if(front==MAX-1){
front=0;
else{
front++;
void deleteRear(){
if(front==-1){
printf("Deque Underflow\n");
else{
printf("Deleted: %d\n", deque[rear]);
if(front==rear){
front=rear=-1;
else if(rear==0){
rear=MAX-1;
else{
rear--;
}
}
void display(){
int i=front;
if(front==-1){
printf("Deque is empty\n");
return;
printf("Deque elements: ");
while(i!=rear){
printf("%d ", deque[i]);
i=(i+1)%MAX;
printf("%d\n", deque[rear]);
int main(){
insertRear(10);
insertRear(20);
insertFront(5);
insertRear(30);
display();
deleteFront();
deleteRear();
display();
Output
ii)doubly linked list respectively.
Input
#include <stdio.h>
struct node{
int data;
struct node *prev,*next;
};
struct node *front=NULL,*rear=NULL;
void insertFront(int x){
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->prev=NULL;
temp->next=front;
if(front==NULL)
rear=temp;
else
front->prev=temp;
front=temp;
void insertRear(int x){
struct node *temp=(struct node*)malloc(sizeof(struct node));
temp->data=x;
temp->next=NULL;
temp->prev=rear;
if(rear==NULL)
front=temp;
else
rear->next=temp;
rear=temp;
void deleteFront(){
if(front==NULL){
printf("Deque Underflow\n");
return;
struct node *temp=front;
printf("Deleted: %d\n", temp->data);
front=front->next;
if(front==NULL)
rear=NULL;
else
front->prev=NULL;
free(temp);
void deleteRear(){
if(rear==NULL){
printf("Deque Underflow\n");
return;
struct node *temp=rear;
printf("Deleted: %d\n", temp->data);
rear=rear->prev;
if(rear==NULL)
front=NULL;
else
rear->next=NULL;
free(temp);
void display(){
struct node *temp=front;
if(temp==NULL){
printf("Deque is empty\n");
return;
printf("Deque elements: ");
while(temp!=NULL){
printf("%d ", temp->data);
temp=temp->next;
printf("\n");
int main(){
insertFront(10);
insertRear(20);
insertFront(5);
insertRear(30);
display();
deleteFront();
deleteRear();
display();
Output
Program 5
Write a C program that uses functions to perform the following:
a) Create a binary search tree of characters
b) Traverse the above Binary search tree recursively in Postorder.
Input
#include <stdio.h>
#include <stdlib.h>
struct node {
char data;
struct node *left;
struct node *right;
};
struct node* createNode(char value) {
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = value;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
struct node* insert(struct node* root, char value) {
if (root == NULL)
return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
return root;
void postorder(struct node* root) {
if (root != NULL) {
postorder(root->left);
postorder(root->right);
printf("%c ", root->data);
int main() {
struct node* root = NULL;
int n, i;
char ch;
printf("Enter number of characters: ");
scanf("%d", &n);
printf("Enter %d characters:\n", n);
for (i = 0; i < n; i++) {
scanf(" %c", &ch);
root = insert(root, ch);
printf("Postorder Traversal: ");
postorder(root);
return 0;
OUTPUT
Program 6
Write a C program that uses functions to perform the following:
a) Create a binary search tree of integers.
b) Traverse the above Binary search tree non recursively in inorder.
Input
#include <stdio.h>
#include <stdlib.h>
struct node {
int data;
struct node *left, *right;
};
struct node* createNode(int value) {
struct node* newNode = (struct node*)malloc(sizeof(struct node));
newNode->data = value;
newNode->left = newNode->right = NULL;
return newNode;
struct node* insert(struct node* root, int value) {
if (root == NULL)
return createNode(value);
if (value < root->data)
root->left = insert(root->left, value);
else if (value > root->data)
root->right = insert(root->right, value);
return root;
void inorder(struct node* root) {
struct node* stack[100];
int top = -1;
struct node* current = root;
while (current != NULL || top != -1) {
while (current != NULL) {
stack[++top] = current;
current = current->left;
current = stack[top--];
printf("%d ", current->data);
current = current->right;
}
int main() {
struct node* root = NULL;
int n, value;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++) {
scanf("%d", &value);
root = insert(root, value);
printf("Inorder Traversal (Non-Recursive): ");
inorder(root);
return 0;
Output
Program 7
Write C programs for implementing the following sorting methods to arrange a list of integers in Ascending order :
a) Insertion sort
Input
#include <stdio.h>
void insertionSort(int a[], int n) {
int i, j, key;
for (i = 1; i < n; i++) {
key = a[i];
j = i - 1;
while (j >= 0 && a[j] > key) {
a[j + 1] = a[j];
j--;
a[j + 1] = key;
}
void display(int a[], int n) {
for (int i = 0; i < n; i++)
printf("%d ", a[i]);
int main() {
int a[100], n;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
insertionSort(a, n);
printf("Sorted list (Insertion Sort): ");
display(a, n);
return 0;
Output
b) Merge sort
input
#include <stdio.h>
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 mergeSort(int arr[], int l, int r) {
if(l < r) {
int m = (l + r) / 2;
mergeSort(arr, l, m);
mergeSort(arr, m + 1, r);
merge(arr, l, m, r);
int main() {
int arr[100], n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
mergeSort(arr, 0, n - 1);
printf("Sorted array in ascending order:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
}
return 0;
Output
Program 8
Write C programs for implementing the following sorting methods to arrange a list of integers in ascending order:
a) Quick sort
Input
#include <stdio.h>
void quickSort(int arr[], int low, int high);
int partition(int arr[], int low, int high);
int main() {
int arr[100], n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
quickSort(arr, 0, n - 1);
printf("Sorted array in ascending order:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
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);
int partition(int arr[], int low, int high) {
int pivot = arr[high];
int i = low - 1, j, temp;
for(j = low; j < high; j++) {
if(arr[j] < pivot) {
i++;
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
b) Selection sort
#include <stdio.h>
int main() {
int arr[100], n, i, j, min, temp;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter %d integers:\n", n);
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
for(i = 0; i < n - 1; i++) {
min = i;
for(j = i + 1; j < n; j++) {
if(arr[j] < arr[min]) {
min = j;
temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
printf("Sorted array in ascending order:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
Output
Program 9
i) Write a C program to perform the following operation: a)Insertion into a B-tree.
Input
#include <stdio.h>
struct BTreeNode {
int val[MAX + 1], count;
struct BTreeNode *link[MAX + 1];
};
struct BTreeNode *root;
struct BTreeNode* createNode(int val, struct BTreeNode *child) {
struct BTreeNode *newNode;
newNode = (struct BTreeNode*)malloc(sizeof(struct BTreeNode));
newNode->val[1] = val;
newNode->count = 1;
newNode->link[0] = root;
newNode->link[1] = child;
return newNode;
void insertNode(int val, int pos, struct BTreeNode *node, struct BTreeNode *child) {
int j = node->count;
while (j > pos) {
node->val[j + 1] = node->val[j];
node->link[j + 1] = node->link[j];
j--;
node->val[j + 1] = val;
node->link[j + 1] = child;
node->count++;
void display(struct BTreeNode *node) {
if (node) {
int i;
for (i = 0; i < node->count; i++) {
display(node->link[i]);
printf("%d ", node->val[i + 1]);
display(node->link[i]);
int main() {
root = NULL;
root = createNode(10, NULL);
insertNode(20, 1, root, NULL);
insertNode(5, 0, root, NULL);
printf("B-Tree elements:\n");
display(root);
return 0;
Output
ii) Write a C program for implementing Heap sort algorithm for sorting a given list of integers in ascending
order.
Input
#include <stdio.h>
void heapify(int arr[], int n, int i) {
int largest = i;
int left = 2*i + 1;
int right = 2*i + 2;
int temp;
if (left < n && arr[left] > arr[largest])
largest = left;
if (right < n && arr[right] > arr[largest])
largest = right;
if (largest != i) {
temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
void heapSort(int arr[], int n) {
int i, temp;
for (i = n/2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (i = n-1; i > 0; i--) {
temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
heapify(arr, i, 0);
int main() {
int arr[100], n, i;
printf("Enter number of elements: ");
scanf("%d", &n);
printf("Enter elements:\n");
for(i = 0; i < n; i++) {
scanf("%d", &arr[i]);
heapSort(arr, n);
printf("Sorted array in ascending order:\n");
for(i = 0; i < n; i++) {
printf("%d ", arr[i]);
return 0;
Output
Program 10
Write a C program to implement all the functions of a dictionary (ADT) using hashing.
Input
#include <stdio.h>
#define SIZE 10
struct node {
int key;
char value[50];
struct node *next;
};
struct node* hashTable[SIZE];
int hashFunction(int key) {
return key % SIZE;
void insert(int key, char value[]) {
int index = hashFunction(key);
struct node *newNode = (struct node*)malloc(sizeof(struct node));
newNode->key = key;
strcpy(newNode->value, value);
newNode->next = NULL;
if(hashTable[index] == NULL) {
hashTable[index] = newNode;
} else {
struct node *temp = hashTable[index];
while(temp->next != NULL)
temp = temp->next;
temp->next = newNode;
printf("Key inserted successfully.\n");
void search(int key) {
int index = hashFunction(key);
struct node *temp = hashTable[index];
while(temp != NULL) {
if(temp->key == key) {
printf("Key found! Value = %s\n", temp->value);
return;
temp = temp->next;
printf("Key not found.\n");
void deleteKey(int key) {
int index = hashFunction(key);
struct node *temp = hashTable[index];
struct node *prev = NULL;
while(temp != NULL) {
if(temp->key == key) {
if(prev == NULL)
hashTable[index] = temp->next;
else
prev->next = temp->next;
free(temp);
printf("Key deleted successfully.\n");
return;
prev = temp;
temp = temp->next;
printf("Key not found.\n");
void display() {
int i;
struct node *temp;
for(i = 0; i < SIZE; i++) {
temp = hashTable[i];
printf("Index %d: ", i);
while(temp != NULL) {
printf("(%d, %s) -> ", temp->key, temp->value);
temp = temp->next;
printf("NULL\n");
int main() {
int choice, key;
char value[50];
while(1) {
printf("\n--- Dictionary using Hashing ---\n");
printf("1. Insert\n2. Search\n3. Delete\n4. Display\n5. Exit\n");
printf("Enter your choice: ");
scanf("%d", &choice);
switch(choice) {
case 1:
printf("Enter key: ");
scanf("%d", &key);
printf("Enter value: ");
scanf("%s", value);
insert(key, value);
break;
case 2:
printf("Enter key to search: ");
scanf("%d", &key);
search(key);
break;
case 3:
printf("Enter key to delete: ");
scanf("%d", &key);
deleteKey(key);
break;
case 4:
display();
break;
case 5:
exit(0);
default:
printf("Invalid choice.\n");
return 0;
Output
Program 11
Write a C program for implementing Knuth-Morris- Pratt pattern matching algorithm.
#include <stdio.h>
void computeLPS(char pattern[], int m, int lps[]) {
int len = 0;
int i = 1;
lps[0] = 0;
while (i < m) {
if (pattern[i] == pattern[len]) {
len++;
lps[i] = len;
i++;
} else {
if (len != 0) {
len = lps[len - 1];
} else {
lps[i] = 0;
i++;
}
void KMPSearch(char text[], char pattern[]) {
int m = strlen(pattern);
int n = strlen(text);
int lps[m];
computeLPS(pattern, m, lps);
int i = 0;
int j = 0;
while (i < n) {
if (pattern[j] == text[i]) {
i++;
j++;
if (j == m) {
printf("Pattern found at index %d\n", i - j);
j = lps[j - 1];
else if (i < n && pattern[j] != text[i]) {
if (j != 0)
j = lps[j - 1];
else
i++;
int main() {
char text[100], pattern[100];
printf("Enter the text: ");
scanf("%s", text);
printf("Enter the pattern: ");
scanf("%s", pattern);
KMPSearch(text, pattern);
return 0;
}
Output
Program 12
Write C programs for implementing the following graph traversal algorithms:
a)Depth first traversal
input
#include <stdio.h>
int visited[10], graph[10][10], n;
void DFS(int v) {
int i;
printf("%d ", v);
visited[v] = 1;
for(i = 1; i <= n; i++) {
if(graph[v][i] == 1 && visited[i] == 0) {
DFS(i);
int main() {
int i, j, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
scanf("%d", &graph[i][j]);
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("DFS Traversal: ");
DFS(start);
return 0;
}
Output
b)Breadth first traversal
input
#include <stdio.h>
int graph[10][10], visited[10], queue[10];
int front = -1, rear = -1, n;
void enqueue(int v) {
if(rear == n-1)
return;
else {
if(front == -1)
front = 0;
rear++;
queue[rear] = v;
int dequeue() {
int item;
if(front == -1)
return -1;
else {
item = queue[front];
front++;
return item;
void BFS(int v) {
int i;
printf("%d ", v);
visited[v] = 1;
enqueue(v);
while(front <= rear) {
v = dequeue();
for(i = 1; i <= n; i++) {
if(graph[v][i] == 1 && visited[i] == 0) {
printf("%d ", i);
visited[i] = 1;
enqueue(i);
int main() {
int i, j, start;
printf("Enter number of vertices: ");
scanf("%d", &n);
printf("Enter adjacency matrix:\n");
for(i = 1; i <= n; i++) {
for(j = 1; j <= n; j++) {
scanf("%d", &graph[i][j]);
printf("Enter starting vertex: ");
scanf("%d", &start);
printf("BFS Traversal: ");
BFS(start);
return 0;
Output