SE 203: Data Structures Lab

Practical File

Submitted towards the partial fulfilment of the requirements of the award of the
degree of

Bachelor of Technology In Software Engineering

Submitted by
Mandeep
23/SE/93
3rd SEM, II YEAR

Submitted to
Dr. Divyashika Sethia
Assistant Professor
Department of Software Engineering

Delhi Technological University

(FORMERLY Delhi College of Engineering) Bawana Road, New Delhi-110042
November, 2024

Mandeep 23/SE/93
 INDEX

S. no. List of Experiments Date Page Sign Remarks

No

Mandeep 23/SE/93
 Experiment 1
Objective:
Write a small program in C to reverse an array, compile using c and generate a valid output
file.

Code:
// Mandeep 23/SE/93

#include <stdio.h>
void reverseArray(int arr[], int size)
{ int start = 0, end = size - 1,
temp; while (start < end) {
temp = arr[start];
arr[start] =
arr[end]; arr[end] =
temp; start++;
end--;
}
}

int main()
{ int n,
i;
printf("Enter the number of elements in the array: ");
scanf("%d", &n);

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

Mandeep 23/SE/93
 scanf("%d", &arr[i]);
}

reverseArray(arr, n);

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

return 0;
}

Output:

Mandeep 23/SE/93
 Experiment 2
Objective:
Creating a menu driver program that will take input from the user to (1). enter elements in a
one dimensional array (2). delete element in a one dimensional array (have all conditions,
beginning, last, middle index) (3,) Find the largest element (4.) Find the smallest element.

Code:
// Mandeep 23/SE/93

#include
<stdio.h> #define
MAX 100
void enterElements(int arr[], int *size)
{ int n, i;
printf("Enter number of elements:
"); scanf("%d", &n);
if (n > MAX) {
printf("Cannot insert more than %d elements.\n", MAX);
return;
}
*size = n;
printf("Enter the elements:\
n"); for (i = 0; i < n; i++) {
scanf("%d", &arr[i]);
}
printf("Elements added successfully.\n");
}

void deleteElement(int arr[], int *size)

{ int choice, index, i;

Mandeep 23/SE/93
 if (*size == 0) {
printf("Array is empty. Nothing to delete.\
n"); return;
}

printf("Delete Options:\n");
printf("1. Delete from the beginning\n");
printf("2. Delete from the last\n");
printf("3. Delete from a specific index\n");
printf("Enter your choice: ");
scanf("%d", &choice);

switch (choice)
{ case 1:
for (i = 0; i < *size - 1; i++)
{ arr[i] = arr[i + 1];
}
(*size)--;
printf("Deleted element from the beginning.\
n"); break;
case 2:
(*size)--;
printf("Deleted element from the last.\
n"); break;
case 3:
printf("Enter the index to delete (0 to %d): ", *size - 1);
scanf("%d", &index);

if (index < 0 || index >= *size) {

Mandeep 23/SE/93
 printf("Invalid index.\n");
} else {
for (i = index; i < *size - 1; i++)
{ arr[i] = arr[i + 1];
}
(*size)--;
printf("Deleted element at index %d.\n", index);
}
break
;
default:
printf("Invalid choice.\
n"); break;
}
}

void findLargest(int arr[], int size)

{ if (size == 0) {
printf("Array is empty.\
n"); return;
}

int max = arr[0], i;

for (i = 1; i < size; i++)
{ if (arr[i] > max) {
max = arr[i];
}
}
printf("The largest element is %d.\n", max);
}

Mandeep 23/SE/93
void findSmallest(int arr[], int size)
{ if (size == 0) {
printf("Array is empty.\
n"); return;
}

int min = arr[0], i;

for (i = 1; i < size; i++)
{ if (arr[i] < min) {
min = arr[i];
}
}
printf("The smallest element is %d.\n", min);
}

int main() {
int arr[MAX], size = 0, choice;

while (1) { printf("\

nMenu:\n");
printf("1. Enter elements into the array\n");
printf("2. Delete element in the array\n");
printf("3. Find the largest element\n");
printf("4. Find the smallest element\n");
printf("5. Exit\n");
printf("Enter your choice:
"); scanf("%d", &choice);
switch (choice) {
case 1:
enterElements(arr, &size);

Mandeep 23/SE/93
 break
; case 2:
deleteElement(arr,
&size); break;
case 3:
findLargest(arr,
size); break;
case 4:
findSmallest(arr,
size); break;
case 5:
printf("Exiting...\
n"); return 0;
default:
printf("Invalid choice. Please try again.\n");
}
}

return 0;
}

Output:

Mandeep 23/SE/93
Mandeep 23/SE/93
 Experiment 3
Objective:
Write a menu driven program to
1. Merge two strings
2. reverse strings
3. Find a substring and replace it with another string.

Code:
// Mandeep 23/SE/93

#include <stdio.h>
#include <string.h>

void mergeStrings() {
char str1[100], str2[100];
printf("Enter the first string:
"); scanf("%s", str1);
printf("Enter the second string:
"); scanf("%s", str2);

strcat(str1, str2); // Concatenate str2 to str1

printf("Merged string: %s\n", str1);
}

void swap(char *s1, char *s2)

{ char temp = *s1;
*s1 = *s2;
*s2 = temp;
}

void reverseString()
{ char str[1000];

Mandeep 23/SE/93
 printf("Enter a string:
"); scanf("%s", str);

int len = strlen(str) -

1; int first = 0;

while (first <= len) {

swap(&str[first],
&str[len]); first++;
len--;
}

printf("Reversed string: %s\n", str);

}

void findAndReplace() {
char str[1000], oldWord[100], newWord[100],
result[1000]; int i, j, k;
int lenStr, lenOldWord, lenNewWord;

// Input main string, old word, and new

word printf("Enter the main string: ");
scanf("%s", str);
printf("Enter the word to find: ");
scanf("%s", oldWord);
printf("Enter the new word to replace with: ");
scanf("%s", newWord);

lenStr = strlen(str); // Length of main string

lenOldWord = strlen(oldWord); // Length of old
word

Mandeep 23/SE/93
 lenNewWord = strlen(newWord); // Length of new word

i = 0; // Index for main string

k = 0; // Index for result
string

// Outer loop to go through each character of the main string

while (i < lenStr) {
// Inner loop to check if the substring
matches for (j = 0; j < lenOldWord; j++) {
if (str[i + j] != oldWord[j]) {
break; // Exit if characters don't match
}
}

// If oldWord is found
if (j == lenOldWord)
{
// Copy newWord into result
for (j = 0; j < lenNewWord; j++)
{ result[k++] = newWord[j];
}
i += lenOldWord; // Move past the oldWord in the original string
} else {
// If no match, copy the current character from main string
result[k++] = str[i++];
}
}

result[k] = '\0'; // Null-terminate the result string

Mandeep 23/SE/93
 // Output the modified string

Mandeep 23/SE/93
 printf("Modified string: %s\n", result);
}
int main()
{ int
choice;
while (1) {
printf("\nMenu:\n");
printf("1. Merge two strings\
n"); printf("2. Reverse a string\
n");
printf("3. Find a substring and replace it\n");
printf("4. Exit\n");
printf("Enter your choice:
"); scanf("%d", &choice);
switch (choice) {
case 1:
mergeStrings()
; break;
case 2:
reverseString()
; break;
case 3:
findAndReplace()
; break;
case 4:
printf("Exiting program...\
n"); return 0;
default:
printf("Invalid choice. Please try again.\n");
}
}

Mandeep 23/SE/93
 return 0;}

Mandeep 23/SE/93
Output:

Mandeep 23/SE/93
 Experiment 4
Objective:
Write a program to implement character stack using an array. Implement:
- push
- pop functions keeping the boundary conditions.
- use the functions to check parenthesis correctness in a string array

Code:
// Mandeep 23/SE/93

#include <stdio.h>
#include <stdlib.h>
#include
<stdbool.h>

#define MAX 100

typedef struct {
char
items[MAX]; int
top;
} Stack;

void initialize(Stack *s)

{ s->top = -1;
}

bool isFull(Stack *s) {

return s->top == MAX - 1;
}

bool isEmpty(Stack *s)

{ return s->top == -1;

Mandeep 23/SE/93
}

Mandeep 23/SE/93
void push(Stack *s, char value)
{ if (isFull(s)) {
printf("Stack overflow\n");
} else {
s->items[++(s->top)] = value;
}
}

char pop(Stack *s)

{ if (isEmpty(s))
{
printf("Stack underflow\
n"); return '\0';
} else {
return s->items[(s->top)--];
}
}

// Function to check if the parentheses are balanced

bool checkParentheses(char *expression) {
Stack s;
initialize(&s)
;
for (int i = 0; expression[i] != '\0'; i++) {
if (expression[i] == '(' || expression[i] == '{' || expression[i] == '[')
{ push(&s, expression[i]);
} else if (expression[i] == ')' || expression[i] == '}' || expression[i] == ']')
{ if (isEmpty(&s)) {
return false;
}
char top = pop(&s);

Mandeep 23/SE/93
 if ((expression[i] == ')' && top != '(') ||

Mandeep 23/SE/93
 (expression[i] == '}' && top != '{') ||
(expression[i] == ']' && top != '['))
{ return false;
}} }
return isEmpty(&s);
}
int main() {
char expression[MAX];
printf("Enter an expression:
"); scanf("%s", expression);
if (checkParentheses(expression))
{ printf("Parentheses are balanced\
n");
} else {
printf("Parentheses are not balanced\n");
}
return 0;
}

Output:

Mandeep 23/SE/93
 Experiment 5
Objective:
Write a program to
1. display,
2. insert,
3. delete elements
4. .remove duplicates
to a circular queue using a menu driven program. Check for overflow and underflow
conditions.

Code:
// Mandeep 23/SE/93

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

#define SIZE 5 // defining size of queue here

// structure of queue
typedef struct
Queue
{
int front, rear,
size; int
array[SIZE];
} Queue;

// to create a queue
Queue
*createQueue()
{
Queue *queue = (Queue
Mandeep 23/SE/93
 *)malloc(sizeof(queue)); queue->front = queue-
>rear = -1;
queue->size =
0; return queue;
}

Mandeep 23/SE/93
// check if queue is full
int isFull(Queue
*queue)
{
return (queue->size == SIZE);
}
// check if queue is empty
int isEmpty(Queue
*queue)
{
return (queue->size == 0);
}

// enqueue function
void enqueue(Queue *queue, int x)
{
if (isFull(queue))
{
printf("queue overflow \
n"); return;
}
if (queue->front == -
1) queue->front =
0;

queue->rear = (queue->rear + 1) %
SIZE; queue->array[queue->rear] = x;
queue->size++;
printf("%d enqueued to queue,x");
}

Mandeep 23/SE/93
// dequeue function
int dequeue(Queue *queue)

Mandeep 23/SE/93
{
if (isEmpty(queue))
{
printf("queue underflow \
n"); return -1;
}
int x = queue->array[queue->front];
queue->front = (queue->front + 1) %
SIZE; queue->size--;
return x;
}

// display function
void display(Queue *queue)
{
if (isEmpty(queue))
{
printf("queue is empty \
n"); return;
}
int i;
// this i=i+1 % size is done to put the rear pointer again to start after it reaches the size of
the array as it is a circular array
for (i = queue->front; i != queue->rear; i = (i + 1) % SIZE)
printf("%d ", queue->array[i]);
printf("%d", queue->array[i]);
}

// function to remove duplicates

void removeDuplicates(Queue *queue)
{

Mandeep 23/SE/93
 if (isEmpty(queue))
{
printf("empty\
n"); return;
}
// traversing the array and finding the
duplicates int temp[SIZE], tempSize = 0;
int i, j;
for (i = queue->front; i != queue->rear; i = (i + 1) % SIZE)
{
int bool = 0;
for (j = 0; j < tempSize; j++)
{
if (queue->array[i] == temp[j])
{
bool =
1;
break;
}
}
if (!bool)
{
temp[tempSize++] = queue->array[i];
}
}
int bool = 0;
for (j = 0; j < tempSize; j++)
{
if (queue->array[i] == temp[j])
{
bool = 1;

Mandeep 23/SE/93
 break;
}
}
if (!bool)
{
temp[tempSize++] = queue->array[i];
}
queue->front = 0;
queue->rear = tempSize -
1; queue->size = tempSize;
for (i = 0; i < tempSize; i++)
{
queue->array[i] = temp[i];
}
printf("Duplicates removed \n");
}

// menu driven interface

void menu()
{
Queue *queue =
createQueue(); int choice,
item;
while (1)
{
printf("\n1. Display Queue\n");
printf("2. Insert Element\n");
printf("3. Delete Element\n");
printf("4. Remove Duplicates\
n");

Mandeep 23/SE/93
 printf("5. Input Elements for Queue\n");

Mandeep 23/SE/93
 printf("6. Exit\n");
printf("Enter your choice:
"); scanf("%d", &choice);
switch (choice)
{
case 1:
display(queue)
; break;
case 2:
printf("Enter the element to insert: ");
scanf("%d", &item);
enqueue(queue,
item); break;
case 3:
item =
dequeue(queue); if
(item != -1)
printf("%d dequeued from queue\n",
item); break;
case 4:
removeDuplicates(queue)
; break;
case 5:
printf("Enter %d elements for the queue: \n", SIZE);
for (int i = 0; i < SIZE; i++)
{
scanf("%d", &item);
enqueue(queue,
item);
}
break

Mandeep 23/SE/93
 ; case 6:

Mandeep 23/SE/93
 exit(0)
; default:
printf("Invalid choice\n");
}
}
}

int main()
{
menu();
return
0;
}

Output:

Mandeep 23/SE/93
Mandeep 23/SE/93
 Experiment 6
Objective:
Write a program for displaying, inserting and deleting elements to doubly linked list.

Code:
// Mandeep 23/SE/93

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

struct
node{ int
data;
struct
node*next;
struct
node*prev;
};
struct node
*head,*newnode,*tail; void
createDLL(){
head=0;
int choice=1;
while (choice)
{
newnode=(struct node*) malloc(sizeof(struct
node)); printf("enter data:");
scanf("%d",&newnode-
>data); newnode->prev=0;
newnode-
>next=0;

Mandeep 23/SE/93
 if(head==0){
tail= head=newnode;
}
else{
tail->next=newnode;
newnode-
>prev=tail;
tail=newnode;

Mandeep 23/SE/93
 }
printf("do you want to continue?(1 for yes , 0 for no):");
scanf("%d",&choice);

}
}
void display()
{ struct node
*temp;
temp=head;
while(temp!=0){
printf("%d",temp-
>data); temp=temp-
>next;
}
}
void insertatbeg(){
struct
node*newnode;
newnode=(struct node*)malloc(sizeof(struct
node)); printf("enter element to be entered");
scanf("%d",&newnode->data);
newnode->prev=0;
newnode->next=0;
head-
>prev=newnode;
newnode->next=head;
head=newnode;
}
void insertatend(){
struct

Mandeep 23/SE/93
 node*newnode;
newnode=(struct node*)malloc(sizeof(struct
node)); printf("enter element to be entered");
scanf("%d",&newnode->data);

Mandeep 23/SE/93
 newnode->prev=0;
newnode->next=0;
tail->next=newnode;
newnode-
>prev=tail;
tail=newnode;
}
void insertatpos()
{ int pos,i=1;
printf("enter
position:");
scanf("%d",&pos);
if(pos<1)
printf("invalid");
else
if(pos==1)
insertatbeg();
else{
struct node
*newnode,*temp;
temp=head;
newnode=(struct node*)malloc(sizeof(struct
node)); printf("enter data:");
scanf("%d",&newnode-
>data); while(i<pos-1){
temp=temp-
>next; i++;
}
newnode->prev=temp;
newnode->next=temp-
>next; temp-

Mandeep 23/SE/93
 >next=newnode;
newnode->next->prev=newnode;
}

Mandeep 23/SE/93
}

void insertafterpos()
{ int pos,i=1;
printf("enter
position:");
scanf("%d",&pos);
if(pos<1)
printf("invalid");

else{
struct node
*newnode,*temp;
temp=head;
newnode=(struct node*)malloc(sizeof(struct
node)); printf("enter data:");
scanf("%d",&newnode-
>data); while(i<pos){
temp=temp-
>next; i++;
}
newnode->prev=temp;
newnode->next=temp-
>next; temp-
>next=newnode;
newnode->next->prev=newnode;
}
}

void delfrombeg(){
struct

Mandeep 23/SE/93
 node*temp;
if(head==0)
printf("empty");

Mandeep 23/SE/93
 else{
temp=head;
head=head-
>next; head-
>prev=0;
free(temp);
}
}
void delfromend(){
struct
node*temp;
if(tail==0)
printf("empty");
else{
temp=tail;
tail->prev-
>next=0; tail=tail-
>prev; free(temp);
}
}

void delfrompos()
{ int pos ,i=1;
struct
node*temp;temp=head;
printf("enter position");
scanf("%d",&pos);
while(i<pos){
temp=temp-
>next; i++;
}

Mandeep 23/SE/93
 temp->prev->next=temp-
>next; temp->next-
>prev=temp->prev;

Mandeep 23/SE/93
 free(temp);
}
int main()
{ int
choice;
while (1) {
printf("\nMenu:\n");
printf("1. Create Doubly Linked List\
n"); printf("2. Display List\n");
printf("3. Insert at Beginning\n");
printf("4. Insert at End\n");
printf("5. Insert at Position\n");
printf("6. Insert after Position\n");
printf("7. Delete from Beginning\
n"); printf("8. Delete from End\n");
printf("9. Delete from Position\n");
printf("10. Exit\n");
printf("Enter your choice:
"); scanf("%d", &choice);

switch (choice)
{ case 1:
createDLL()
; break;
case 2:
display()
; break;
case 3:
insertatbeg()
; break;
case 4:

Mandeep 23/SE/93
 insertatend()
; break;
case 5:
insertatpos()
; break;
case 6:
insertafterpos()
; break;
case 7:
delfrombeg()
; break;
case 8:
delfromend()
; break;
case 9:
delfrompos()
; break;
case 10:
exit(0)
;
break;
default:
printf("Invalid choice\n");
}
}
return 0;
}

Output:

Mandeep 23/SE/93
Mandeep 23/SE/93
Mandeep 23/SE/93
 Experiment 7
Objective:

Choose a unique expression and store it in a binary tree. Use appropriate tree traversals to
generate and display the post and pre fix expressions.

Code:
// Mandeep 23/SE/93

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

//structure for a node in Binary tree

typedef struct Node {
char value;
struct Node *left, *right;
} Node;

//creating new node

Node* createNode(char value) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->value = value;
newNode->left = newNode->right =
NULL; return newNode;
}
//preorder traversal
void preOrder(Node* root)
{ if (root != NULL) {
printf("%c ", root-
>value); preOrder(root-
Mandeep 23/SE/93
 >left); preOrder(root-
>right);

Mandeep 23/SE/93
 }
}
//postorder traversal
void postOrder(Node* root)
{ if (root != NULL) {
postOrder(root->left);
postOrder(root->right);
printf("%c ", root-
>value);
}
}

int main() {
Node* root = createNode('x');//root node
root->left = createNode('y');//left node of root node
root->right = createNode('z');//right node of root
node root->right->left = createNode('w');//left node
of 'z'

//display preorder
printf("Prefix expression:
"); preOrder(root);
printf("\n");

//display postorder
printf("Postfix expression:
"); postOrder(root);
printf("\n");

return 0;
}

Mandeep 23/SE/93
Output:

Mandeep 23/SE/93
 Experiment 8
Objective:
Write an interactive menu-based program that provides the following options
1. Add an element to the BST
2. Delete element in the BST
3. Search element in the BST and provide its parent and children information.

Code:
// Mandeep 23/SE/93

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

struct Node
{ int key;
struct Node* left;
struct Node* right;
};

struct Node* createNode(int key) {

struct Node* newNode = (struct Node*)malloc(sizeof(struct
Node)); newNode->key = key;
newNode->left = NULL;
newNode->right =
NULL; return newNode;
}

struct Node* insert(struct Node* node, int key)

{ if (node == NULL) return createNode(key);

if (key < node->key)

Mandeep 23/SE/93
 node->left = insert(node->left, key);

Mandeep 23/SE/93
 else if (key > node->key)
node->right = insert(node->right, key);

return node;
}

struct Node* minValueNode(struct Node* node)

{ struct Node* current = node;
while (current && current->left != NULL)
current = current->left;
return current;
}

struct Node* deleteNode(struct Node* root, int key) {

if (root == NULL) return root;

if (key < root->key)

root->left = deleteNode(root->left,
key); else if (key > root->key)
root->right = deleteNode(root->right,
key); else {
if (root->left == NULL) {
struct Node* temp = root-
>right; free(root);
return temp;
} else if (root->right == NULL) {
struct Node* temp = root->left;
free(root);
return temp;
}

Mandeep 23/SE/93
 struct Node* temp = minValueNode(root-
>right); root->key = temp->key;
root->right = deleteNode(root->right, temp->key);
}
return root;
}

struct Node* search(struct Node* root, int key, struct Node** parent) {
*parent = NULL;
struct Node* current = root;

while (current != NULL && current->key != key) {

*parent = current;
if (key < current->key)
current = current-
>left;
else
current = current->right;
}

return current;
}

void getNodeDetails(struct Node* root, int key) {

struct Node* parent = NULL;
struct Node* node = search(root, key, &parent);

if (node == NULL) {
printf("Node with key %d not found.\n", key);
return;

Mandeep 23/SE/93
 }

printf("Node %d: ",

key); if (parent !=
NULL)
printf("Parent: %d, ", parent-
>key); else
printf("Parent: None, ");

if (node->left != NULL)
printf("Left Child: %d, ", node->left-
>key); else
printf("Left Child: None, ");

if (node->right != NULL)
printf("Right Child: %d\n", node->right-
>key); else
printf("Right Child: None\n");
}

void menu() {
struct Node* root =
NULL; int choice, key;

while (1) {
printf("\nBST Operations Menu:\n");
printf("1. Add an element to the BST\n");
printf("2. Delete element in the BST\n");
printf("3. Search element in the BST and provide its parent and children information\n");
printf("4. Exit\n");
printf("Enter your choice: ");

Mandeep 23/SE/93
 scanf("%d", &choice);

switch (choice)
{ case 1:
printf("Enter the element to insert: ");
scanf("%d", &key);
root = insert(root, key);
printf("Inserted %d into the BST.\n",
key); break;
case 2:
printf("Enter the element to delete: ");
scanf("%d", &key);
root = deleteNode(root, key);
printf("Deleted %d from the BST.\n",
key); break;
case 3:
printf("Enter the element to search:
"); scanf("%d", &key);
getNodeDetails(root, key);
break
; case 4:
printf("Exiting...\
n"); exit(0);
default:
printf("Invalid choice! Please choose a valid option.\n");
}
}
}

Mandeep 23/SE/93
int main()
{ menu(
);

return 0;

Output:

Mandeep 23/SE/93