Laboratory Man

FACULTY OF ENGINEERING AND TECHNOLOGY

BACHELOR OF TECHNOLOGY

Data Structures and Algorithms

(203105206)

III SEMESTER
Computer Science & Engineering
Department

Laboratory Manual

WIRELESS COMMUNICATIONPRACTICAL BOOK

 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

COMPUTER SCIENCE &ENGINEERING DEPARTMENT

PREFACE
It gives us immense pleasure to present the first edition of the Data Structure and
Algorithms Practical Book for the B.Tech . 3rd semester students for PARUL UNIVERSITY.
The DSA theory and laboratory courses at PARUL UNIVERSITY, WAGHODIA,
VADODARA are designed in such a way that students develop the basic understanding of the
subject in the theory classes and then try their hands on the experiments to realize the various
implementations of problems learnt during the theoretical sessions. The main objective of the
DSA laboratory course is: Learning DSA through Experimentations. All the experiments are
designed to illustrate various problems in different areas of DSA and also to expose the students
to various uses.
The objective of this DSA Practical Book is to provide a comprehensive source for all the
experiments included in the DSA laboratory course. It explains all the aspects related to every
experiment such as: basic underlying concept and how to analyze a problem. It also gives
sufficient information on how to interpret and discuss the obtained results.
We acknowledge the authors and publishers of all the books which we have consulted
while developing this Practical book. Hopefully this DSA Practical Book will serve the purpose
for which it has been developed.

2| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

INSTRUCTIONS TO STUDENTS

1. The main objective of the DSA laboratory is: Learning through the Experimentation. All
the experiments are designed to illustrate various problems in different areas of DSA and
also to expose the students to various problems and their uses.
2. Be prompt in arriving to the laboratory and always come well prepared for the practical.
3. Every student should have his/her individual copy of the DSA Practical Book.
4. Every student have to prepare the notebooks specifically reserved for the DSA practical
work: ”DSA Practical Book”
5. Every student has to necessarily bring his/her DSA Practical Book, DSA Practical Class
Notebook and DSA Practical Final Notebook.
6. Finally find the output of the experiments along with the problem and note results in the
DSA Practical Notebook.
7. The grades for the DSA practical course work will be awarded based on our performance
in the laboratory, regularity, recording of experiments in the DSA Practical Final
Notebook, lab quiz, regular viva-voce and end-term examination.

3| Page
 CERTIFICATE

This is to certify that

Mr./Ms AYUSH KUMAR SARRAF with enrolment no. 210303105563

has successfully completed his/her laboratory experiments in the DSA

(203105306) from the department of COMPUTER SCIENCE &

ENGINEERING during the academic year 2022 – 2023.

Date of Submission:......................... Staff In charge:...........................

Head Of Department:...........................................
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

TABLE OF CONTENT
Page No
Sr. Date of Date of Marks
Experiment Title Sign
No Start Completion (out of 10)
From To
1. Write a program to implement
1 (a) linear Search (b) Binary
Search
Write a program to implement
(a) Bubble Sort
2.
(b) Insertion Sort
(c) Selection Sort

Implement a program to
3. convert infix notation to postfix
notation using stack.
Write a program to
implement QUEUE using
arrays that performs
4. following operations
(a)INSERT
(b) DELETE
(c) DISPLAY
Write a menu driven program to
implement following operations
on the singly linked list and
5. doubly linked list.
(a) Insert a node at the specified
position
(b) Delete a first node of the
linked list.

Write a menu driven program to

implement following operations
on the singly linked list and
6. doubly linked list
(a) Delete a node before
specified position.
(b) Delete a node after
specified position.
7.
Write a program to
implement following
operations on the circular
linked list.
(a) Insert anode at the end of

2| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

the linked list.

(b) Insert a node before
specified position.

8. Write a program to implement

stack using linked list.
9. Write a program to create
binary Tree Traversal.
10. Write a program to implement
Prim’s and Kruskal’s algorithm.

3| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

PRACTICAL NO: 1
Aim: - Write a program to implement (a) linear Search (b) Binary Search

a) What is Linear Search?

Linear Search is basically a sequential search algorithm. In this algorithm, the key element is
searched in the given input array in sequential order. If the key element is found in the input array, it
returns the element.

Linear Search Algorithm:

procedure LINEAR_SEARCH (array, key)

for each item in the array

if match element == key
return element's index
end if
end for

end procedure

Liner Search Program

Program Code:

#include <stdio.h>

int LINEAR_SEARCH(int inp_arr[], int size, int val)

{

for (int i = 0; i < size; i++)

if (inp_arr[i] == val)
return i;
return -1;
}

int main(void)
{
int arr[] = { 10, 20, 30, 40, 50, 100, 0 };
int key = 100;
int size = 10;
int res = LINEAR_SEARCH(arr, size, key);
if (res == -1)

4| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

printf("ELEMENT NOT FOUND!!");

else
printf("Item is present at index %d", res);

return 0;
}

Output Obtained:

5| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

b) What is Binary Search?

Binary Search is a searching algorithm used in a sorted array by repeatedly dividing the
search interval in half. The idea of binary search is to use the information that the array is
sorted and reduce the time complexity to O(Log n).

Binary Algorithm :

Step 1: Start
Step 2: Input Sorted array in "a[]" and element to be searched in "x" and size of array in "size"
Step 3: Initialize low=0, high=size-1
Step 4: Repeat until low>=high
Step 4.1: mid=(low+high)/2
Step 4.2: If a[mid] is equal to x,
then, print index value of mid and Goto step 6
Else
If a[mid]<x
low=mid+1
else
high=mid-1
Step 5: Print x not found in the list
Stop 6: Stop

Binary Search program:

Source Code:

// C program to implement recursive Binary Search

#include <stdio.h>

// A recursive binary search function. It returns

// location of x in given array arr[l..r] is present,
// otherwise -1
int binarySearch(int arr[], int l, int r, int x)
{
if (r >= l) {
int mid = l + (r - l) / 2;

6| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

// If the element is present at the middle

// itself
if (arr[mid] == x)
return mid;

// If element is smaller than mid, then

// it can only be present in left subarray
if (arr[mid] > x)
return binarySearch(arr, l, mid - 1, x);

// Else the element can only be present

// in right subarray
return binarySearch(arr, mid + 1, r, x);
}

// We reach here when element is not

// present in array
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;
}

Binary Search Output:

7| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

PRACTICAL NO: 2
Aim:- Write a program to implement (a) Bubble Sort (b) Insertion Sort (c) Selection Sort

a) What is Bubble Sort?

Bubble sort is a basic algorithm for arranging a string of numbers or other elements in the correct
order. The method works by examining each set of adjacent elements in the string, from left to
right, switching their positions if they are out of order.

Bubble Sort algorithm :

procedure bubbleSort( list : array of items )

loop = list.count;

for i = 0 to loop-1 do:

swapped = false

for j = 0 to loop-1 do:

/* compare the adjacent elements */

if list[j] > list[j+1] then
/* swap them */
swap( list[j], list[j+1] )
swapped = true
end if

end for

/*if no number was swapped that means

array is sorted now, break the loop.*/

if(not swapped) then

break
end if

end for

end procedure return list

8| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

Bubble Sort Program:

Source code:

// C program for implementation of Bubble sort

#include <stdio.h>

void swap(int* xp, int* yp)

{
int temp = *xp;
*xp = *yp;
*yp = 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], &arr[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 program to test above functions

int main()
{
int arr[] = { 14,26,32,92,10,99 };
int n = sizeof(arr) / sizeof(arr[0]);
bubbleSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

9| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

Bubble Sort Output:

10| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

b) What is insertion sort?

Insertion sort in c is the simple sorting algorithm that virtually splits the given array into sorted
and unsorted parts, then the values from the unsorted parts are picked and placed at the correct
position in the sorted part.

Insertion Sort algorithm:

i?1
while i < length(A)
j?i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j?j-1
end while
i?i+1
end while

Insertion Code Program:

Source Code:

// 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;
}
}

11| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

// 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 program to test insertion sort */

int main()
{
int arr[] = { 21, 22, 89, 10, 3 };
int n = sizeof(arr) / sizeof(arr[0]);

insertionSort(arr, n);
printArray(arr, n);

return 0;
}

Insertion Sort Output:

12| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

c) What is Selection Sort?

Selection sort is another algorithm that is used for sorting. This sorting algorithm, iterates
through the array and finds the smallest number in the array and swaps it with the first element if
it is smaller than the first element.

Selection Sort algorithm:

procedure selection sort

list : array of items
n : size of list

for i = 1 to n - 1
/* set current element as minimum*/
min = i

/* check the element to be minimum */

for j = i+1 to n
if list[j] < list[min] then
min = j;
end if
end for

/* swap the minimum element with the current element*/

if indexMin != i then
swap list[min] and list[i]
end if
end for

end procedure

Selection Sort Program:

Source Code:

// C program for implementation of selection sort

#include <stdio.h>

void swap(int *xp, int *yp)

{

13| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

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

if(min_idx != i)
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[] = { 66, 87, 25, 15, 37};
int n = sizeof(arr)/sizeof(arr[0]);
selectionSort(arr, n);
printf("Sorted array: \n");
printArray(arr, n);
return 0;
}

14| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

Selection Code Output:

PRACTICAL NO – 3

Aim :~ Implement a program to convert infix notation to postfix notation using stack.

• Infix Notation:
We write expression in infix notation, e.g. a - b + c, where operators are used in-between
operands. It is easy for us humans to read, write, and speak in infix notation but the same does
not go well with computing devices. An algorithm to process infix notation could be difficult and
costly in terms of time and space consumption.

• Postfix Notation:
This notation style is known as Reversed Polish Notation. In this notation style, the operator is
postfixed to the operands i.e., the operator is written after the operands. For example, ab+. This is
equivalent to its infix notation a + b.

Algorithm to convert infix notation to postfix notation using stack.

 Step 1 : Scan the Infix Expression from left to right.

 Step 2 : If the scanned character is an operand, append it with final Infix to Postfix string.
 Step 3 : Else,
 Step 3.1 : If the precedence order of the scanned(incoming) operator is greater than
the precedence order of the operator in the stack (or the stack is empty or the stack

15| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

contains a ‘(‘ or ‘[‘ or ‘{‘), push it on stack.

 Step 3.2 : Else, Pop all the operators from the stack which are greater than or equal to in
precedence than that of the scanned operator. After doing that Push the scanned operator to
the stack. (If you encounter parenthesis while popping then stop there and push the scanned
operator in the stack.)
 Step 4 : If the scanned character is an ‘(‘ or ‘[‘ or ‘{‘, push it to the stack.
 Step 5 : If the scanned character is an ‘)’or ‘]’ or ‘}’, pop the stack and and output it until a
‘(‘ or ‘[‘ or ‘{‘ respectively is encountered, and discard both the parenthesis.
 Step 6 : Repeat steps 2-6 until infix expression is scanned.
 Step 7 : Print the output
 Step 8 : Pop and output from the stack until it is not empty.

Program to convert :~

// C program to convert infix expression to postfix

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

// Stack type
struct Stack
{
int top;
unsigned capacity;
int* array;
};

// Stack Operations
struct Stack* createStack( unsigned capacity )
{
struct Stack* stack = (struct Stack*)
malloc(sizeof(struct Stack));

if (!stack)
return NULL;

stack->top = -1;
stack->capacity = capacity;

stack->array = (int*) malloc(stack->capacity *

sizeof(int));

return stack;
}
int isEmpty(struct Stack* stack)
{
return stack->top == -1 ;

16| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

}
char peek(struct Stack* stack)
{
return stack->array[stack->top];
}
char pop(struct Stack* stack)
{
if (!isEmpty(stack))
return stack->array[stack->top--] ;
return '$';
}
void push(struct Stack* stack, char op)
{
stack->array[++stack->top] = op;
}

// A utility function to check if

// the given character is operand
int isOperand(char ch)
{
return (ch >= 'a' && ch <= 'z') ||
(ch >= 'A' && ch <= 'Z');
}

// A utility function to return

// precedence of a given operator
// Higher returned value means
// higher precedence
int Prec(char ch)
{
switch (ch)
{
case '+':
case '-':
return 1;

case '*':
case '/':
return 2;

case '^':
return 3;
}
return -1;
}

// The main function that

17| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

// converts given infix expression

// to postfix expression.
int infixToPostfix(char* exp)
{
int i, k;

// Create a stack of capacity

// equal to expression size
struct Stack* stack = createStack(strlen(exp));
if(!stack) // See if stack was created successfully
return -1 ;

for (i = 0, k = -1; exp[i]; ++i)

{

// If the scanned character is

// an operand, add it to output.
if (isOperand(exp[i]))
exp[++k] = exp[i];

// If the scanned character is an

// ‘(‘, push it to the stack.
else if (exp[i] == '(')
push(stack, exp[i]);

// If the scanned character is an ‘)’,

// pop and output from the stack
// until an ‘(‘ is encountered.
else if (exp[i] == ')')
{
while (!isEmpty(stack) && peek(stack) != '(')
exp[++k] = pop(stack);
if (!isEmpty(stack) && peek(stack) != '(')
return -1; // invalid expression
else
pop(stack);
}
else // an operator is encountered
{
while (!isEmpty(stack) &&
Prec(exp[i]) <= Prec(peek(stack)))
exp[++k] = pop(stack);
push(stack, exp[i]);
}

// pop all the operators from the stack

while (!isEmpty(stack))

18| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

exp[++k] = pop(stack );

exp[++k] = '\0';
printf( "%s", exp );
}

// Driver program to test above functions

int main()
{
char exp[] = "a+b-c*(a^b)-d*f";
infixToPostfix(exp);
return 0;
}

Output:

PRACTICAL NO – 4

Aim :~ Write a program to implement QUEUE using arrays that performs following operations
(a)INSERT (b) DELETE (c) DISPLAY

What are queues?

A Queue is a linear structure which follows a particular order in which the operations are performed.
The order is First In First Out (FIFO). A good example of a queue is any queue of consumers for a
resource where the consumer that came first is served first. The difference between stacks and
queues is in removing. In a stack we remove the item the most recently added; in a queue, we
remove the item the least recently added.

Algorithm to implement Queue using arrays:

o Step 1: IF REAR = MAX - 1

Write OVERFLOW
Go to step
[END OF IF]
o Step 2: IF FRONT = -1 and REAR = -1
19| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

SET FRONT = REAR = 0

ELSE
SET REAR = REAR + 1
[END OF IF]
o Step 3: Set QUEUE[REAR] = NUM
o Step 4: EXIT

Program to implement QUEUE:

Source Code:

#include<stdlib.h>
#include<stdio.h>
#define max 5
int front=-1,rear=-1; // global variable
int CQueue[max];
void insert();
int remove();
void display();
int main()
{
int w,no;
for(;;)
{
printf("\n1. Insert");
printf("\n2. Delete");
printf("\n3. Display");
printf("\n4. EXIT");
printf("\nEnter what you want :");
scanf("%d",&w);
switch(w)
{
case 1:
insert();
break;
case 2:
no=remove();
break;
case 3:
display();
break;
case 4:
exit(1);
default:
printf("\nInvalid Choice !!\n");
}
}

20| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

}
void insert()
{
int no;
if((front ==0 && rear == max-1) || front == rear+1)
{
printf("\nCircular Queue Is Full !\n");
return;
}
printf("\nEnter a number to Insert :");
scanf("%d",&no);
if(front==-1)
front=front+1;
if(rear==max-1)
rear=0;
else rear=rear+1;
CQueue[rear]=no;
}
int remove()
{
int e;
if(front==-1)
{
printf("\nThe Circular Queue is Empty !!\n");

}
e=CQueue[front];
if(front==max-1)
front=0;
else if(front==rear)
{
front=-1;
rear=-1;
}
else front=front+1;
printf("\n%d was deleted !\n",e);
return e;
}
void display()
{
int i;
if(front==-1)
{
printf("\nThe Circular Queue is Empty ! Nothing To Display !!\n");
return;
}
i=front;
if(front<=rear)
{

21| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

printf("\n\n");
while(i<=rear)
printf("%d ",CQueue[i++]);
printf("\n");
}
else
{
printf("\n\n");
while(i<=max-1)
printf("%d ",CQueue[i++]) ;
i=0;
while(i<=rear)
printf("%d ",CQueue[i++]);
printf("\n");
}
}

22| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

23| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

EXPERIMENT NO.: 5

Aim: Write a program to implement STACK using arrays that performs following operations

A) PUSH
B) POP
C) SHOW

What is STACK?
Stack is a linear data structure which follows a particular order in
which the operations are performed. The order may be LIFO (Last In
First Out) or FILO(First In Last Out).
Queue Operations Pseudo Code:

1.[Check for stack overflow]

If TOP ≥ N
Then write (‘STACK OVERFLOW’)
Return
2. [Increment TOP]
TOP ←TOP + 1
3. [Insert Element]
S[TOP] ←X
4. [Finished]
Return

STACK Operations Program:

Input Used:

Pushed:[45,58,25]

Program Code:

#include<stdio.h>

#include<stdlib.h>

#define Size 4

int Top=-1, inp_array[Size];

void Push();
void Pop();
void show();

int main()
{
int choice;

24| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

while(1)
{
printf("\nOperations performed by Stack");
printf("\n1.Push the element\n2.Pop the element\n3.Show\n4.End");
printf("\n\nEnter the choice:");
scanf("%d",&choice);

switch(choice)
{
case 1: Push();
break;
case 2: Pop();
break;
case 3: show();
break;
case 4: exit(0);

default: printf("\nInvalid choice!!");

}
}
}

void Push()
{
int x;

if(Top==Size-1)
{
printf("\nOverflow!!");
}
else
{
printf("\nEnter element to be inserted to the stack:");
scanf("%d",&x);
Top=Top+1;
inp_array[Top]=x;
}
}

void Pop()
{
if(Top==-1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nPopped element: %d",inp_array[Top]);
Top=Top-1;

25| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

}
}

void show()
{

if(Top==-1)
{
printf("\nUnderflow!!");
}
else
{
printf("\nElements present in the stack: \n");
for(int i=Top;i>=0;--i)
printf("%d\n",inp_array[i]);
}
}

Output Obtained:

26| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

EXPERIMENT NO : 6

AIM: Write a menu driven program to implement following operations on the singly linked list
and doubly linked list.

(a) Insert a node at the specified position

(b) Delete the first node of the linked list

CODE:

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

<conio.h> void insert_beg(); void

traversal();

void insert_end(); void

delete_beg(); void delete_end();

void insert_AGN(int); struct node

int data;

struct node *next;

* H, *T;

int main()

int ch = 0, info; while (ch <

7)

{
printf("\n1.insert a node at starting position"); printf("\

n2.insert at last position"); printf("\n3.delet from front");

printf("\n4.delete from last");

27| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

printf("\n5. insert after any node"); printf("\n6. display");

printf("\n enter choice");

scanf("%d", &ch);

switch (ch)

case 1: insert_beg();

break;

case 2:

insert_end(); break;

case 3: delete_beg();

break;

case 4: delete_end();

break;

case 5:

printf("enter node value");

scanf("%d", &info); insert_AGN(info);

break;

case 6:

traversal();

break;

case 7:

break;

default:
printf("invalid");
}

28| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

getch();

void insert_beg()

{
struct node *newnode;
int x;
newnode = (struct node *)malloc(sizeof(struct node)); if (newnode ==

NULL)

printf("\nNode not created"); return;

}
printf("\ninsert data for new node"); scanf("%d",

&x);

newnode->data = x;

newnode->next = H; if (H ==

NULL)

{
T = newnode;
}
H = newnode;

void traversal()

struct node *temp; temp = H;

while (temp != NULL)

printf("\t%d", temp->data); temp = temp->next;

}
}

29| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

void insert_end()

{
struct node *newnode;
int x;
newnode = (struct node *)malloc(sizeof(struct node)); if (newnode ==

NULL)

{
printf("\nNode not created"); return;

}
printf("\ninsert data for new node"); scanf("%d",

&x);

newnode->data = x;

newnode->next = NULL;

if (H == NULL)

{
H = newnode;
T = newnode;
} else

{
T->next = newnode;
T = newnode;
}
}
void insert_AGN(int info)
{
struct node *newnode, *temp;
int x;
newnode = (struct node *)malloc(sizeof(struct node)); if (newnode ==

NULL)

{
printf("\nNode not created"); return;

}
temp = H;
while (temp->data != info && temp != NULL)
{
temp = temp->next;
}
if (temp == NULL)
{

30| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

printf("\nNode not found"); return;

}
printf("\ninsert data for new node"); scanf("%d",

&x);

newnode->data = x;

if (temp == T)

{
newnode->next = NULL;
T->next = newnode;
T = newnode;
} else

{
newnode->next = temp->next;

temp->next = newnode;

}
}

void delete_beg()

struct node *temp; temp =

H;

if (H == NULL)

{
printf("\nBlank LIST"); return;

}
if (H->next == NULL)
{
T = NULL;

}
H = H->next;

free(temp);

void delete_end()

31| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

struct node *temp, *curr; temp = T;

if (H == NULL)

{
printf("BLANK LIST");
return;
}
if (H->next == NULL)
{
H = NULL;
T = NULL;

else

curr = H;

while (curr->next != T)

curr = curr->next;

}
curr->next = NULL;
} free(temp);

OUTPUT:

32| Page
 COMPUTER SCIENCE AND ENGINEERING
FACULTY OF ENGINEERING & TECHNOLOGY
DSA (203105306) B. Tech. 3rd SEM
ENROLLMENT NO:210303105563

33| Page