(Institute under SNDT women’s university, Mumbai)

Lab Manual
Data Structures and Analysis of Algorithm

By:
Mr. Shaikh Shahid S.
Department head
Computer science & technology
Indian institute of food science & technology
Aurangabad 431-001

Department of computer Science & Technology

2024-25
 LIST OF EXPERIMENTS

Date of Page Faculty

Sr. No. Name of the Experiment
Experiment No Signature

Implementation of Stacks, Queues (using

1 both arrays and linked lists). 3

Implementation of Singly Linked List,

2 Doubly Linked List and Circular List. 14

Implementation of Infix to postfix

conversion and evaluation of postfix
3 expression. 40

Implementation of Polynomial arithmetic

4 using linked list 44

Implementation of Linear search and

5 Binary Search 47

Implementation of Hashing Technique

6 50

Implementation of Binary Tree and Binary

tree traversal techniques (in order,
7 preorder, post order, level-order) 54

Implementation of Binary search tree and

its operations
8 59

Implementation of Insertion Sort,

Selection Sort, Bubble Sort, Merge Sort,
9 Quick Sort, Heap Sort 75

Implementation of Graph Search Methods

10 Depth first search, Breath first search 85
IIFST Data Structures and Analysis of Algorithm-Lab

Program 1: Implementation of Stacks, Queues (using both arrays and linked lists).

Aim: C++ Programs to implement Implementation of Stacks, Queues (using both arrays
and linked lists).
Description :
2.A) Stack ADT
Stacks: A stack is a linear data structure in which elements are added to or deleted from a
single end called as Top of the stack. The elements last inserted is the first to be removed,
therefore stack is said to follow the Last In First Out principle, LIFO. In this context, the
insert operation is more commonly known as Push and deletes operation as Pop. Other
operations on a stack are: to find size of stack, return top most element, search for an element
in the stack etc.
Stacks are used in: Function calls, Recursion, Evaluation of expressions by
compilers, undo mechanism in an editor, etc
The stack data structures can be represented using Arrays or Linked Lists. When
represented using an array, the initial value of Top, the index for top most element,
when stack is empty, is -1, a nonexistent index.
The ADT for an array based stack is :

ADT Stack
{
Private:
An array;
Top index;
Public:
Stack();
boolean isEmpty()
boolean isFull();
void push( item e);
int pop();
int peek();
}
When elements are pushed into stack, the Top gradually increases towards right. Each pop
operation causes the Top index to decrease by one.
Figure illustrates the array representation.

Stacks can also be represented using linked representation, wherein the elements of the

Page 3
IIFST Data Structures and Analysis of Algorithm-Lab

stack are not stored contiguously using an array, rather the elements are stored using a
node structure that can be stored in the memory non-contiguously. Each node contains
information about the data element and the address of where the next element is stored
in the memory.

Figure for linked stack

The ADT for a

linked stack is: ADT
Struct Node
{
Private:
T data; //template type data
Node<T> *link;
};
ADT LinkedStack
{
Private:
Node<T> *Top;
Int size;
Public:

Push(T item);
Pop();
boolisEmpty();
}

Page 4
IIFST Data Structures and Analysis of Algorithm-Lab

Aim: A program that implements a stack operations using array.

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

#define MAX 1000

class Stack {
int top;
int a[MAX]; // Maximum size of Stack
public:
Stack() { top = -1; }
void push(int x);
int pop();
int peek();
bool isEmpty();
bool isFull();
void display();
};

void Stack::push(int x)
{
if (isFull()) {
cout << "Stack Overflow";
}
else {
a[++top] = x;
cout << x << " pushed into stack\n";
}
}
int Stack::pop()
{
if (isEmpty()) {
cout << "Stack Underflow";
return 0;

else {

int x = a[top--];
return x;
}
}
int Stack::peek()
{
if (isEmpty()) {
cout << "Stack is Empty";
return 0;

Page 5
IIFST Data Structures and Analysis of Algorithm-Lab

}
else {
int x = a[top];
return x;
}
}
bool Stack::isEmpty()
{
return (top < 0);
}
bool Stack::isFull()
{
return(top>=MAX-1);
}
void Stack::display()
{
cout<<"Stack elements are\n";
for(int i=top;i>=0;i--)
cout<<a[i]<<" ";
}
// Driver program to test above functions
int main()
{
class Stack s;
s.push(10);
s.push(20);
s.push(30);
cout << s.pop() << " Popped from stack\n";
s.display();
return 0;
}

Expected Output:
10 pushed into stack
20 pushed into stack
30 pushed into stack

30 Popped from stack

Stack elements are
20 10

Page 6
IIFST Data Structures and Analysis of Algorithm-Lab

Aim :Program to implement Linked Stack

#include<iostream>
using namespace std;
struct Node
{
int data;
Node *next;
}*top=NULL,*p;

Node* newnode(int x)
{
p=new Node;
p->data=x;
p- >next=NULL;
return(p);
}

void push(Node *q)

{
if(top==NULL)
top=q;
else
{
q- >next=top;
top=q;
}
}
void pop(){
if(top==NULL){
cout<<"Stack is empty!!";
}
else{
cout<<"Deleted element is "<<top->data;
p=top;
top=top->next;
delete(p);
}
}
void showstack()
{
Node *q;
q=top;

if(top==NULL){
cout<<"Stack is empty!!";
}
else{
while(q!=NULL)
{
cout<<q->data<<" ";
q=q->next;
}

Page 7
IIFST Data Structures and Analysis of Algorithm-Lab

}
}
int main()
{
int ch,x;
Node *nptr;

while(1)
{
cout<<"\n\n1.Push\n2.Pop\n3.Display\n4.Exit";
cout<<"\nEnter your choice(1-4):";
cin>>ch;

switch(ch){
case 1: cout<<"\nEnter data:";
cin>>x;
nptr=newnode(x);
push(nptr);
break;

case 2: pop();
break;

case 3: showstack();
break;

case 4: exit(0);

default: cout<<"\nWrong choice!!";

}
}

return 0;
}

Expected Output:

1.Push
2.Pop
3.Display
4.Exit
Enter your choice(1-4):1
Enter data:10
1.Push
2.Pop
3.Display
4.Exit
Enter your choice(1-4):1
Enter data:20
1.Push
2.Pop
3.Display

Page 8
IIFST Data Structures and Analysis of Algorithm-Lab

4.Exit
Enter your choice(1-4):1
Enter data:30
1. Push
2.Pop
3.Display
4.Exit
Enter your choice(1-4):2
Deleted element is 30
1.Push
2. Pop
3.Display
4.Exit
Enter your choice(1-4):3
20 10
1. Push
2.Pop
3.Display
4.Exit
Enter your choice(1-4):4

2.B) Queue ADT

A queue is a linear data structure in which elements can be inserted and deleted from
two different ends. The end at which elements are inserted into queue is referred to as
Rear and the end from which elements are deleted is known as Front. The element first
inserted will be the first to delete, therefore queue is said to follow, First In First Out,
FIFO principle. Queues are used: in processor scheduling, request processing systems,
etc. A queue can be implemented using arrays or linked representation.
The ADT for array based Queue is
ADT Queue
{
public:
Queue();
void enqueue(const T& newItem);
int dequeue();
void display();
private:
int front;
int rear;
int q[50];
}

Aim:Program to implement Queue operations using arrays

#include<iostream>
using namespace std;
#define SIZE 10
class Queue

Page 9
IIFST Data Structures and Analysis of Algorithm-Lab

{
int a[SIZE];
int rear; //same as tail
int front; //same as head

public:
Queue()
{
rear = front = -1;
}
//declaring enqueue, dequeue and display functions
void enqueue(int x);
int dequeue();
void display();
};

// function enqueue - to add data to queue

void Queue :: enqueue(int x)
{
if(front == -1) {
front++;
}
if( rear == SIZE-1)
{
cout << "Queue is full";
}
else
{
a[++rear] = x;
}
}

// function dequeue - to remove data from queue

int Queue :: dequeue()
{
return a[++front]; // following approach [B], explained above
}

// function to display the queue elements

void Queue :: display()
{
int i;
for( i = front; i <= rear; i++)
{
cout << a[i] << endl;
}
}
// the main function
int main()
{
Queue q;
q.enqueue(10);

Page 10
IIFST Data Structures and Analysis of Algorithm-Lab

q.enqueue(100);
q.enqueue(1000);
q.enqueue(1001);
q.enqueue(1002);
cout<<"Queue elements Are \n";
q.display();
q.dequeue();
q.enqueue(1003);
q.dequeue();
q.dequeue();
q.enqueue(1004);
cout<<"Queue elements are \n";
q.display();
return 0;
}

Expected Output:
Queue elements Are
10
100
1000
1001
1002
Queue elements are
1001
1002
1003
1004

The ADT for linked Queue is:

struct Node{
int data;
Node *next;
};
class Queue{
Node *front,*rear;
Public:
Queue(){front=rear=NULL;}

void insert(int n);

void deleteitem();
void display();
~Queue();
};

Page 11
IIFST Data Structures and Analysis of Algorithm-Lab

2.C) Aim: C++ program to Implement a QUEUE using singly linked list

#include<iostream>
using namespace std;
struct Node{
int data;
Node *next;
};
class Queue{
public:
Node *front,*rear;
Queue(){front=rear=NULL;}
void insert(int n);
void deleteitem();
void display();
~Queue();
};
void Queue::insert(int n){
Node *temp=new Node;
if(temp==NULL){
cout<<"Overflow"<<endl;
return;
}
temp->data=n;
temp->next=NULL;
//for first node
if(front==NULL){
front=rear=temp;
}
else{
rear->next=temp;
rear=temp;
}
cout<<n<<" has been inserted successfully."<<endl;
}
void Queue::display(){
if(front==NULL){
cout<<"Underflow."<<endl;
return;
}
Node *temp=front;
//will check until NULL is not found
while(temp){
cout<<temp->data<<" ";
temp=temp->next;
}
cout<<endl;
}
void Queue :: deleteitem()
{
if (front==NULL){
cout<<"underflow"<<endl;

Page 12
IIFST Data Structures and Analysis of Algorithm-Lab

return;
}
cout<<front->data<<" is being deleted "<<endl;
if(front==rear)//if only one node is there
front=rear=NULL;
else
front=front->next;
}
Queue ::~Queue()
{
while(front!=NULL)
{
Node *temp=front;
front=front->next;
delete temp;
}
rear=NULL;
}
int main(){
Queue Q;
Q.display();
Q.insert(10);
Q.insert(24);
Q.insert(28);
Q.insert(32);
Q.insert(30);
Q.display();
Q.deleteitem();
Q.deleteitem();
Q.deleteitem();
Q.deleteitem();
Q.deleteitem();
return 0;
}

Expected Output:
Underflow.
10 has been inserted successfully.
24 has been inserted successfully.
28 has been inserted successfully.
32 has been inserted successfully.
30 has been inserted successfully.
10 24 28 32 30
10 is being deleted
24 is being deleted
28 is being deleted
32 is being deleted
30 is being deleted

Page 13
IIFST Data Structures and Analysis of Algorithm-Lab

Program 2:Implementation of Singly Linked List, Double Linked List, Circular List.
Aim : C++ Programs to Implementation of Singly Linked List, Double Linked List,
Circular List.
Description :

3.A)Linked Lists:
A linked list is a linear data structure, in which the elements are not stored at contiguous
memory locations. The elements in a linked list are linked using pointers as shown below:

The elements of a linked list are called the nodes. A node has two fields i.e. data and next. The
data field contains the data being stored in that specific node. It cannot just be a single variable.
There may be many variables presenting the data section of a node. The next field contains the
address of the next node. So this is the place where the link between nodes is established.

Operations on Linked Lists:

Insert: Insert at first position, insert at last position, insert into
ordered list

Delete: Delete an element from first, last or any intermediate

position

Traverse List: print the list

Copy the linked List, Reverse the linked list, search for an element in the list, etc
Types of Linked Lists:
Singly Linked List:
 It is a basic type of linked list.
 Each node contains data and pointer to next node and last node’s pointer is NULL.
 Limitation of SLL is that we can traverse the list in only one direction, forward direction.

Page 14
IIFST Data Structures and Analysis of Algorithm-Lab

Figure : Single Linked List

Circular Linked List:
 CLL is a SLL where last node points to first node in the list
 It does not contain null pointers like SLL
 We can traverse the list in only one direction
 Its advantage is that when we want to go from last node to first node, it directly
points to first node

Figure: CLL
Doubly Linked List:
 Each node of doubly linked list contains data and two pointer fields, pointer to
previous and next node.

 Advantage of DLL is that we can traverse the list any direction, forward orreverse.
 Other advantages of DLL are that we can delete a node with little trouble, since we
have pointers to the previous and next nodes. A node on a SLL cannot be removed
unless we have pointer to its predecessor.

Page 15
IIFST Data Structures and Analysis of Algorithm-Lab

Inserting into a SLL:

3.A) Aim :Program to Create a singly linked list , Insert an element , delete an
element,searchan element and display linked list

#include<iostream>
#include<conio.h>
#include<stdlib.h>
using namespace std;
class Node
{
public:
int info;
Node* next;
};
class List:public Node
{

Node *first,*last;
public:
List()
{
first=NULL;
last=NULL;
}
void create();
void insert();
void delet();
void display();
void search();
};
void List::create()
{
Node *temp;
temp=new Node;
int n;
cout<<"\nEnter an Element:";
cin>>n;
temp->info=n;
temp->next=NULL;
if(first==NULL)
{
first=temp;
last=first;
}

Page 16
IIFST Data Structures and Analysis of Algorithm-Lab

else
{
last->next=temp;
last=temp;
}
}
void List::insert()
{
Node *prev,*cur;
prev=NULL;
cur=first;
int count=1,pos,ch,n;
Node *temp=new Node;
cout<<"\nEnter an Element:";
cin>>n;
temp->info=n;
temp->next=NULL;
cout<<"\nINSERT AS\n1:FIRSTNODE\n2:LASTNODE\n3:IN BETWEEN FIRST&LAST
NODES";
cout<<"\nEnter Your Choice:";
cin>>ch;
switch(ch)
{
case 1:
temp->next=first;
first=temp;
break;
case 2:
last->next=temp;
last=temp;
break;
case 3:
cout<<"\nEnter the Position to Insert:";
cin>>pos;
while(count!=pos)
{
prev=cur;
cur=cur->next;
count++;
}
if(count==pos)
{
prev->next=temp;
temp->next=cur;
}
else
cout<<"\nNot Able to Insert";
break;
}
}
void List::delet()
{

Page 17
IIFST Data Structures and Analysis of Algorithm-Lab

Node *prev=NULL,*cur=first;
int count=1,pos,ch;
cout<<"\nDELETE\n1:FIRSTNODE\n2:LASTNODE\n3:IN BETWEEN FIRST&LAST
NODES";
cout<<"\nEnter Your Choice:";
cin>>ch;
switch(ch)
{
case 1:
if(first!=NULL)
{
cout<<"\nDeleted Element is "<<first->info;
first=first->next;
}
else
cout<<"\nNot Able to Delete";
break;
case 2:
while(cur!=last)
{
prev=cur;
cur=cur->next;
}
if(cur==last)
{
cout<<"\nDeleted Element is: "<<cur->info;
prev->next=NULL;
last=prev;
}
else
cout<<"\nNot Able to Delete";
break;
case 3:
cout<<"\nEnter the Position of Deletion:";
cin>>pos;
while(count!=pos)
{
prev=cur;
cur=cur->next;
count++;
}
if(count==pos)
{
cout<<"\nDeleted Element is: "<<cur->info;
prev->next=cur->next;
}
else
cout<<"\nNot Able to Delete";
break;
}
}
void List::display()

Page 18
IIFST Data Structures and Analysis of Algorithm-Lab

{
Node *temp=first;
if(temp==NULL)
{
cout<<"\nList is Empty";
}
while(temp!=NULL)
{
cout<<temp->info;
cout<<"-->";
temp=temp->next;
}
cout<<"NULL";
}
void List::search()
{
int value,pos=0;
bool flag=false;
if(first==NULL)
{
cout<<"List is Empty";
return;
}
cout<<"Enter the Value to be Searched:";
cin>>value;
Node *temp;
temp=first;
while(temp!=NULL)
{
pos++;
if(temp->info==value)
{
flag=true;
cout<<"Element"<<value<<"is Found at "<<pos<<" Position";
return;
}
temp=temp->next;
}
if(!flag)
{
cout<<"Element "<<value<<" not Found in the List";
}
}
int main()
{
List l;
int ch;
while(1)
{
cout<<"\n**** MENU ****";
cout<<"\n1:CREATE\n2:INSERT\n3:DELETE\n4:SEARCH\n5:DISPLAY\n6:EXIT\n";
cout<<"\nEnter Your Choice:";

Page 19
IIFST Data Structures and Analysis of Algorithm-Lab

cin>>ch;
switch(ch)
{
case 1:
l.create();
break;
case 2:
l.insert();
break;
case 3:
l.delet();
break;
case 4:
l.search();
break;
case 5:
l.display();
break;
case 6:
return 0;
}
}
return 0;
}

EXPECTED OUTPUT:
**** MENU ****
1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:1

Enter an Element:10

**** MENU ****

1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:2

Enter an Element:20

INSERT AS
1:FIRSTNODE

Page 20
IIFST Data Structures and Analysis of Algorithm-Lab

2:LASTNODE
3:IN BETWEEN FIRST&LAST NODES
Enter Your Choice:2

**** MENU ****

1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:2

Enter an Element:30

INSERT AS
1:FIRSTNODE
2:LASTNODE
3:IN BETWEEN FIRST&LAST NODES
Enter Your Choice:1

**** MENU ****

1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:5

30-->10-->20-->NULL
**** MENU ****
1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:4

Enter the Value to be Searched:20
Element20is Found at 3 Position
**** MENU ****
1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:4

Page 21
IIFST Data Structures and Analysis of Algorithm-Lab

Enter the Value to be Searched:50

Element 50 not Found in the List
**** MENU ****
1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:3

DELETE
1:FIRSTNODE
2:LASTNODE
3:IN BETWEEN FIRST&LAST NODES
Enter Your Choice:3

Enter the Position of Deletion:2

Deleted Element is: 10

**** MENU ****
1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:5

30-->20-->NULL
**** MENU ****
1:CREATE
2:INSERT
3:DELETE
4:SEARCH
5:DISPLAY
6:EXIT

Enter Your Choice:6

3.B) AIM :C++ Program to Implement Doubly Linked List

#include<iostream>
#include<cstdio>
#include<cstdlib>

* Node Declaration

using namespace std;

struct node
{

Page 22
IIFST Data Structures and Analysis of Algorithm-Lab

int info;
struct node *next;
struct node *prev;
}*start;

/*
Class Declaration
*/
class double_llist
{
public:
void create_list(int value);
void add_begin(int value);
void add_after(int value, int position);
void delete_element(int value);
void search_element(int value);
void display_dlist();
void count();
void reverse();
double_llist()
{
start = NULL;
}
};

/*
* Main: Conatins Menu
*/
int main()
{
int choice, element, position;
double_llist dl;
while (1)
{
cout<<endl<<" --------------------------- "<<endl;
cout<<endl<<"Operations on Doubly linked list"<<endl;
cout<<endl<<" --------------------------- "<<endl;
cout<<"1.Create Node"<<endl;
cout<<"2.Add at begining"<<endl;
cout<<"3.Add after position"<<endl;
cout<<"4.Delete"<<endl;
cout<<"5.Display"<<endl;
cout<<"6.Count"<<endl;
cout<<"7.Reverse"<<endl;
cout<<"8.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch ( choice )
{
case 1:
cout<<"Enter the element: ";
cin>>element;

Page 23
IIFST Data Structures and Analysis of Algorithm-Lab

dl.create_list(element);
cout<<endl;
break;
case 2:
cout<<"Enter the element: ";
cin>>element;
dl.add_begin(element);
cout<<endl;
break;
case 3:
cout<<"Enter the element: ";
cin>>element;
cout<<"Insert Element after postion: ";
cin>>position;
dl.add_after(element, position);
cout<<endl;
break;
case 4:
if (start == NULL)
{
cout<<"List empty,nothing to delete"<<endl;
break;
}
cout<<"Enter the element for deletion: ";
cin>>element;
dl.delete_element(element);
cout<<endl;
break;
case 5:
dl.display_dlist();
cout<<endl;
break;
case 6:
dl.count();
break;
case 7:
if (start == NULL)
{
cout<<"List empty,nothing to reverse"<<endl;
break;
}
dl.reverse();
cout<<endl;
break;
case 8:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}

Page 24
IIFST Data Structures and Analysis of Algorithm-Lab

/*
* Create Double Link List
*/
void double_llist::create_list(int value)
{
struct node *s, *temp;
temp = new(struct node);
temp->info = value;
temp->next = NULL;
if (start == NULL)
{
temp->prev = NULL;
start = temp;
}
else
{
s = start;
while (s->next != NULL)
s = s->next;
s->next = temp;
temp->prev = s;
}
}

/*
* Insertion at the beginning
*/
void double_llist::add_begin(int value)
{
if (start == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct node);
temp->prev = NULL;
temp->info = value;
temp->next = start;
start->prev = temp;
start = temp;
cout<<"Element Inserted"<<endl;
}

/*
* Insertion of element at a particular position
*/
void double_llist::add_after(int value, int pos)
{
if (start == NULL)
{

Page 25
IIFST Data Structures and Analysis of Algorithm-Lab

cout<<"First Create the list."<<endl;

return;
}
struct node *tmp, *q;
int i;
q = start;
for (i = 0;i<pos - 1;i++)
{
q = q->next;
if (q == NULL)
{
cout<<"There are less than ";
cout<<pos<<" elements."<<endl;
return;
}
}
tmp = new(struct node);
tmp->info = value;
if (q->next == NULL)
{
q->next = tmp;
tmp->next = NULL;
tmp->prev = q;
}
else
{
tmp->next = q->next;
tmp->next->prev = tmp;
q->next = tmp;
tmp->prev = q;
}
cout<<"Element Inserted"<<endl;
}

/*
* Deletion of element from the list
*/
void double_llist::delete_element(int value)
{
struct node *tmp, *q;
/*first element deletion*/
if (start->info == value)
{
tmp = start;
start = start->next;
start->prev = NULL;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = start;
while (q->next->next != NULL)

Page 26
IIFST Data Structures and Analysis of Algorithm-Lab

{
/*Element deleted in between*/
if (q->next->info == value)
{
tmp = q->next;
q->next = tmp->next;
tmp->next->prev = q;
cout<<"Element Deleted"<<endl;
free(tmp);
return;
}
q = q->next;
}
/*last element deleted*/
if (q->next->info == value)
{
tmp = q->next;
free(tmp);
q->next = NULL;
cout<<"Element Deleted"<<endl;
return;
}
cout<<"Element "<<value<<" not found"<<endl;
}

/*
* Display elements of Doubly Link List
*/
void double_llist::display_dlist()
{
struct node *q;
if (start == NULL)
{
cout<<"List empty,nothing to display"<<endl;
return;
}
q = start;
cout<<"The Doubly Link List is :"<<endl;
while (q != NULL)
{
cout<<q->info<<" <-> ";
q = q->next;
}
cout<<"NULL"<<endl;
}

/*
* Number of elements in Doubly Link List
*/
void double_llist::count()
{
struct node *q = start;

Page 27
IIFST Data Structures and Analysis of Algorithm-Lab

int cnt = 0;
while (q != NULL)
{
q = q->next;
cnt++;
}
cout<<"Number of elements are: "<<cnt<<endl;
}

/*
* Reverse Doubly Link List
*/
void double_llist::reverse()
{
struct node *p1, *p2;
p1 = start;
p2 = p1->next;
p1->next = NULL;
p1->prev = p2;
while (p2 != NULL)
{
p2->prev = p2->next;
p2->next = p1;
p1 = p2;
p2 = p2->prev;
}
start = p1;
cout<<"List Reversed"<<endl;
}
EXPECTED OUTPUT:
$ g++ doubly_llist.cpp
$ a.out

Operations on Doubly linked list

1.Create Node
2. Add at begining
3.Add after
4.Delete
5.Display
6.Count
7.Reverse
8.Quit
Enter your choice : 2
Enter the element: 100
First Create the list.

Operations on Doubly linked list

Enter your choice : 3
Enter the element: 200
Insert Element after postion: 1
First Create the list.

Page 28
IIFST Data Structures and Analysis of Algorithm-Lab

Operations on Doubly linked list

Enter your choice : 4
List empty,nothing to delete

Operations on Doubly linked list

Enter your choice : 5
List empty,nothing to display

Operations on Doubly linked list

Enter your choice : 6

Number of elements are: 0

Operations on Doubly linked list

Enter your choice : 7
List empty,nothing to reverse

Operations on Doubly linked list

Enter your choice : 1

Enter the element: 100

Operations on Doubly linked list

Enter your choice : 5
The Doubly Link List is :
100 <->NULL

Operations on Doubly linked list

Enter your choice : 2
Enter the element: 200
Element Inserted

Operations on Doubly linked list

Enter your choice : 5

The Doubly Link List is :
200 <-> 100 <->NULL

Operations on Doubly linked list

Enter your choice : 3
Enter the element: 50
Insert Element after postion: 2
Element Inserted

Operations on Doubly linked list

Enter your choice : 5
The Doubly Link List is :
200 <-> 100 <-> 50 <->NULL

Operations on Doubly linked list

Enter your choice : 3
Enter the element: 150

Page 29
IIFST Data Structures and Analysis of Algorithm-Lab

Insert Element after postion: 3

Element Inserted

Operations on Doubly linked list

Enter your choice : 5
The Doubly Link List is :
200 <-> 100 <-> 50 <-> 150 <->NULL

Operations on Doubly linked list

Enter your choice : 6
Number of elements are: 4

Operations on Doubly linked list

Enter your choice : 4
Enter the element for deletion: 50
Element Deleted

Operations on Doubly linked list

Enter your choice : 5
The Doubly Link List is :
200 <-> 100 <-> 150 <->NULL

Operations on Doubly linked list

Enter your choice : 6
Number of elements are: 3

Operations on Doubly linked list

Enter your choice : 7
List Reversed

Operations on Doubly linked list

Enter your choice : 5
The Doubly Link List is :
150 <-> 100 <-> 200 <->NULL

Operations on Doubly linked list

Enter your choice : 3
Enter the element: 200
Insert Element after postion: 100
There are less than 100 elements.

Operations on Doubly linked list

Enter your choice : 4
Enter the element for deletion: 150
Element Deleted

Operations on Doubly linked list

Enter your choice : 5
The Doubly Link List is :
100 <-> 200 <->NULL

Operations on Doubly linked list

Page 30
IIFST Data Structures and Analysis of Algorithm-Lab

Enter your choice : 8

3.C) Aim:C++ Program to Implement Circular Linked List

#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *next;
}*last;

/*
* Class Declaration
*/
class circular_llist
{
public:
void create_node(int value);
void add_begin(int value);
void add_after(int value, int position);
void delete_element(int value);
void search_element(int value);
void display_list();
void update();
void sort();
circular_llist()
{
last = NULL;
}
};

/*
* Main :contains menu
*/
int main()
{
int choice, element, position;
circular_llist cl;
while (1)
{
cout<<endl<<" -------------------------- "<<endl;
cout<<endl<<"Circular singly linked list"<<endl;
cout<<endl<<" -------------------------- "<<endl;
cout<<"1.Create Node"<<endl;
cout<<"2.Add at beginning"<<endl;
cout<<"3.Add after"<<endl;

Page 31
IIFST Data Structures and Analysis of Algorithm-Lab

cout<<"4.Delete"<<endl;
cout<<"5.Search"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Update"<<endl;
cout<<"8.Sort"<<endl;
cout<<"9.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Enter the element: ";
cin>>element;
cl.create_node(element);
cout<<endl;
break;
case 2:
cout<<"Enter the element: ";
cin>>element;
cl.add_begin(element);
cout<<endl;
break;
case 3:
cout<<"Enter the element: ";
cin>>element;
cout<<"Insert element after position: ";
cin>>position;
cl.add_after(element, position);
cout<<endl;
break;
case 4:
if (last == NULL)
{
cout<<"List is empty, nothing to delete"<<endl;
break;
}
cout<<"Enter the element for deletion: ";
cin>>element;
cl.delete_element(element);
cout<<endl;
break;
case 5:
if (last == NULL)
{
cout<<"List Empty!! Can't search"<<endl;
break;
}
cout<<"Enter the element to be searched: ";
cin>>element;
cl.search_element(element);
cout<<endl;
break;

Page 32
IIFST Data Structures and Analysis of Algorithm-Lab

case 6:
cl.display_list();
break;
case 7:
cl.update();
break;
case 8:
cl.sort();
break;
case 9:
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}
return 0;
}

/*
* Create Circular Link List
*/
void circular_llist::create_node(int value)
{
struct node *temp;
temp = new(struct node);
temp->info = value;
if (last == NULL)
{
last = temp;
temp->next = last;
}
else
{
temp->next = last->next;
last->next = temp;
last = temp;
}
}

/*
* Insertion of element at beginning
*/
void circular_llist::add_begin(int value)
{
if (last == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp;
temp = new(struct node);

Page 33
IIFST Data Structures and Analysis of Algorithm-Lab

temp->info = value;
temp->next = last->next;
last->next = temp;
}

/*
* Insertion of element at a particular place
*/
void circular_llist::add_after(int value, int pos)
{
if (last == NULL)
{
cout<<"First Create the list."<<endl;
return;
}
struct node *temp, *s;
s = last->next;
for (int i = 0;i< pos-1;i++)
{
s = s->next;
if (s == last->next)
{
cout<<"There are less than ";
cout<<pos<<" in the list"<<endl;
return;
}
}
temp = new(struct node);
temp->next = s->next;
temp->info = value;
s->next = temp;
/*Element inserted at the end*/
if (s == last)
{
last=temp;
}
}

/*
* Deletion of element from the list
*/
void circular_llist::delete_element(int value)
{
struct node *temp, *s;
s = last->next;
/* If List has only one element*/
if (last->next == last && last->info == value)
{
temp = last;
last = NULL;
free(temp);
return;

Page 34
IIFST Data Structures and Analysis of Algorithm-Lab

}
if (s->info == value) /*First Element Deletion*/
{
temp = s;
last->next = s->next;
free(temp);
return;
}
while (s->next != last)
{
/*Deletion of Element in between*/
if (s->next->info == value)
{
temp = s->next;
s->next = temp->next;
free(temp);
cout<<"Element "<<value;
cout<<" deleted from the list"<<endl;
return;
}
s = s->next;
}
/*Deletion of last element*/
if (s->next->info == value)
{
temp = s->next;
s->next = last->next;
free(temp);
last = s;
return;
}
cout<<"Element "<<value<<" not found in the list"<<endl;
}

/*
* Search element in the list
*/
void circular_llist::search_element(int value)
{
struct node *s;
int counter = 0;
s = last->next;
while (s != last)
{
counter++;
if (s->info == value)
{
cout<<"Element "<<value;
cout<<" found at position "<<counter<<endl;
return;
}
s = s->next;

Page 35
IIFST Data Structures and Analysis of Algorithm-Lab

}
if (s->info == value)
{
counter++;
cout<<"Element "<<value;
cout<<" found at position "<<counter<<endl;
return;
}
cout<<"Element "<<value<<" not found in the list"<<endl;
}

/*
* Display Circular Link List
*/
void circular_llist::display_list()
{
struct node *s;
if (last == NULL)
{
cout<<"List is empty, nothing to display"<<endl;
return;
}
s = last->next;
cout<<"Circular Link List: "<<endl;
while (s != last)
{
cout<<s->info<<"->";
s = s->next;
}
cout<<s->info<<endl;
}

/*
* Update Circular Link List
*/
void circular_llist::update()
{
int value, pos, i;
if (last == NULL)
{
cout<<"List is empty, nothing to update"<<endl;
return;
}
cout<<"Enter the node position to be updated: ";
cin>>pos;
cout<<"Enter the new value: ";
cin>>value;
struct node *s;
s = last->next;
for (i = 0;i<pos - 1;i++)
{
if (s == last)

Page 36
IIFST Data Structures and Analysis of Algorithm-Lab

{
cout<<"There are less than "<<pos<<" elements.";
cout<<endl;
return;
}
s = s->next;
}
s->info = value;
cout<<"Node Updated"<<endl;
}

/*
* Sort Circular Link List
*/
void circular_llist::sort()
{
struct node *s, *ptr;
int temp;
if (last == NULL)
{
cout<<"List is empty, nothing to sort"<<endl;
return;
}
s = last->next;
while (s != last)
{
ptr = s->next;
while (ptr != last->next)
{
if (ptr != last->next)
{
if (s->info >ptr->info)
{
temp = s->info;
s->info = ptr->info;
ptr->info = temp;
}
}
else
{
break;
}
ptr = ptr->next;
}
s = s->next;
}
}

EXPECTED OUTPUT:
Operations on Circular singly linked list
1.Create Node
2. Add at beginning

Page 37
IIFST Data Structures and Analysis of Algorithm-Lab

3. Add after
4.Delete
5.Search
6.Display
7.Update
8.Sort
9.Quit
Enter your choice : 4
List is empty, nothing to delete

Operations on Circular singly linked list

Enter your choice : 5
List is empty, nothing to search

Operations on Circular singly linked list

Enter your choice : 6
List is empty, nothing to display

Operations on Circular singly linked list

Enter your choice : 7
List is empty, nothing to update

Operations on Circular singly linked list

Enter your choice : 8
List is empty, nothing to sort

Operations on Circular singly linked list

Enter your choice : 1
Enter the element: 100

Operations on Circular singly linked list

Enter your choice : 2

Enter the element: 200

Operations on Circular singly linked list

Enter your choice : 6
Circular Link List:
200->100

Operations on Circular singly linked list

Enter your choice : 3
Enter the element: 50
Insert element after position: 2

Operations on Circular singly linked list

Enter your choice : 6
Circular Link List:
200->100->50

Operations on Circular singly linked list

Enter your choice : 3

Page 38
IIFST Data Structures and Analysis of Algorithm-Lab

Enter the element: 150

Insert element after position: 3

Operations on Circular singly linked list

Enter your choice : 6
Circular Link List:
200->100->50->150

Operations on Circular singly linked list

Enter your choice : 3
Enter the element: 1000
Insert element after position: 50
There are less than 50 in the list

Operations on Circular singly linked list

Enter your choice : 4
Enter the element for deletion: 150
Operations on Circular singly linked list
Enter your choice : 6
Circular Link List:
200->100->50
Operations on Circular singly linked list
Enter your choice : 5
Enter the element to be searched: 100
Element 100 found at position 2

Operations on Circular singly linked list

Enter your choice : 7
Enter the node position to be updated: 1
Enter the new value: 1010
Node Updated

Operations on Circular singly linked list

Enter your choice : 6
Circular Link List:
1010->100->50
Operations on Circular singly linked list
Enter your choice : 8
Operations on Circular singly linked list
Enter your choice : 6
Circular Link List:
50->100->1010
Operations on Circular singly linked list
Enter your choice : 9

Page 39
IIFST Data Structures and Analysis of Algorithm-Lab

Program 3:Implementation of Infix to Postfix conversion and evaluation of postfix

expression:

Aim : C++ Programs to Implementation of Infix to Postfix conversion and evaluation of

postfix expression
Description :

Conventional notation is called infix notation. The arithmetic operators appears between two
operands. Parentheses are required to specify the order of the operations. For example: a + (b
* c).

Post fix notation (also, known as reverse Polish notation) eliminates the need for parentheses.
There are no precedence rules to learn, and parentheses are never needed. Because of this
simplicity, some popular hand-held calculators use postfix notation to avoid the complications
of multiple sets of parentheses. The operator is placed directly after the two operands it needs
to apply. For example: a b c * +

4.A) Aim :Program to convert an Infix expression to Postfix expression

#include<iostream.h>
#include<string.h>
#include<stdlib.h>
#include<ctype.h>
class expression
{
private:
char infix[100]; char stack[200]; int top;
int r;
char postfix[100]; public:
void convert(); int input_p(char); int stack_p(char); int rank(char);
};
int expression::input_p(char c)
{
if(c==’+’ || c==’-') return 1;
else if(c==’*’ || c==’/') return 3;
else if(c==’^') return 6;
else if(isalpha(c)!=0) return 7;
else if(c==’(‘) return 9;
else if(c==’)') return 0;
else
{
cout<<”Invalid expression ::input error\n”; exit(0);
}
}
int expression::stack_p(char c)
{
if(c==’+’ || c==’-') return 2;
else if(c==’*’ || c==’/')

<<”\n*************************************************\n”;
cout<<”Enter an infix expression ::\n”; cin>>infix;
int l=strlen(infix); infix[l]=’)'; infix[l+1]=”;

Page 40
IIFST Data Structures and Analysis of Algorithm-Lab

//Convertion starts top=1; stack[top]=’(‘;r=0;

int x=-1; int i=0;
char next=infix[i]; while(next!=”)
{
//Pop all the elements to outputin stack which have higher precedence while( input_p(next)
<stack_p(stack[top]) )
{
if(top<1)
{
cout<<”invalid expression ::stack error\n”; exit(0);
}
postfix[++x]=stack[top]; top–; r=r+rank(postfix[x]);

if(r<1)
{
cout<<”Invalid expression ::r<1\n”; exit(0);
}
}
if(input_p( next ) != stack_p( stack[top])) stack[++top]=next;
else top–; i++;
next=infix[i];
}
postfix[++x]=”; if(r!=1 || top!=0)
{
cout<<”Invalid expression ::error in rank or stack\n”; exit(0);
}
cout<<”\n\nThe corresponding postfix expression is ::\n”; cout<<postfix<<endl;
}
int main()
{
expression obj; obj.convert(); return 0;
}
EXPECTED OUTPUT::
************************************************* This program converts the given
infix expression
in to postfix form
************************************************* Enter an infix expression ::
(a+b^c^d)*(c+d)
The corresponding postfix expression is :: abcd^^+cd+*
Press any key tocontinue

4.B) Aim:Program to evaluatea Postfix expression.

#include <iostream.h>
#include <math.h>
#include <stdlib.h>
#include <ctype.h>
const int MAX = 50;
class postfix
{
private :

Page 41
IIFST Data Structures and Analysis of Algorithm-Lab

int stack[MAX] ;
int top, nn ;
char *s ; public :
postfix( ) ;
void setexpr( char *str ) ;
void push ( int item ) ;
int pop( ) ;
void calculate( ) ;
void show( ) ;
};
postfix :: postfix( )
{
top = -1 ;
}
void postfix :: setexpr ( char *str )
{
s = str ;
}
void postfix :: push ( int item )
{
if ( top == MAX - 1 )
cout<< endl << "Stack is full" ;
else
{
top++ ;
stack[top] = item ;
}
int postfix :: pop( )
{
if ( top == -1 )
{
cout<< endl << "Stack is empty" ; return NULL ;
}
int data = stack[top] ; top-- ;
return data ;
}
void postfix :: calculate( )
{
int n1, n2, n3 ; while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) )
{
}
else
{
nn = *s - '0' ;
push ( nn ) ;

Page 42
IIFST Data Structures and Analysis of Algorithm-Lab

n1 = pop( ) ;
n2 = pop( ) ;
switch ( *s )
{
case '+' :
n3 = n2 + n1 ; break ;
case '-' :
n3 = n2 - n1 ; break ;
case '/' :
n3 = n2 / n1 ; break ;
case '*' :
n3 = n2 * n1 ; break ;
case '%' :
n3 = n2 % n1 ; break ;
case '$' :
n3 = pow ( n2 , n1 ) ;
break ;
default :
cout<<”Unknown operator”;
exit(1);
} s++ ;
}
}
}
push ( n3 ) ;
cout<< "Unknown operator" ; exit ( 1 ) ;
void postfix :: show( )
{
nn = pop ( ) ;
cout<< "Result is: " <<nn ;
}
void main( )
{
char expr[MAX] ;
cout<< "\nEnter postfix expression to be evaluated : " ; cin.getline ( expr, MAX ) ;
postfix q ;q.setexpr ( expr ) ; q.calculate( ) ; q.show( ) ;
}

Expected Output:
Enter postfix expression to be evaluated : 123*4- Result is:2

Page 43
IIFST Data Structures and Analysis of Algorithm-Lab

Program 4:Implementation of Polynomial arithmetic using linked list

Aim : C++ Programs to Implementation of Polynomial arithmetic using linked list

#include<iostream.h>
#include<conio.h>
#include<process.h>

// Creating a NODE Structure struct node

{
int coe,exp; // data
struct node *next; // link to next node and previous node
};

// Creating a class Polynomial class polynomial

{
struct node *start,*ptrn,*ptrp; public:
void get_poly(); // to get a polynomial void show(); // show
void add(polynomial p1,polynomial p2); // Add two polynomials void subtract(polynomial
p1,polynomial p2); //Subtract2 polynomials
};

void polynomial::get_poly() // Get Polynomial

{
char c='y'; ptrn=ptrp=start=NULL; while(c=='y' || c=='Y')
{
ptrn=new node; ptrp->next=ptrn; if(start==NULL) start=ptrn;
ptrp=ptrn;
cout<<"\nEnter the coefficient: "; cin>>ptrn->coe;
cout<<"\nEnter the exponent: "; cin>>ptrn->exp;
ptrn->next=NULL;
cout<<"\nEnter y to add more nodes: "; cin>>c;
}
return;
}

void polynomial::show() // Show Polynomial

{
struct node *ptr; ptr=start; while(ptr!=NULL)
{
cout<<ptr->coe<<"X^"<<ptr->exp<<" + "; ptr=ptr->next;
}
cout<<" ";
}

void polynomial::add(polynomial p1,polynomial p2) // Add Polynomials

{
struct node *p1ptr,*p2ptr; int coe,exp; ptrn=ptrp=start=NULL; p1ptr=p1.start; p2ptr=p2.start;
while(p1ptr!=NULL && p2ptr!=NULL)
{
if(p1ptr->exp==p2ptr->exp) // If coefficients are equal

Page 44
IIFST Data Structures and Analysis of Algorithm-Lab

{
coe=p1ptr->coe+p2ptr->coe; exp=p1ptr->exp; p1ptr=p1ptr->next; p2ptr=p2ptr->next;
}
else if(p1ptr->exp>p2ptr->exp)
{
coe=p1ptr->coe; exp=p1ptr->exp; p1ptr=p1ptr->next;
}
else if(p1ptr->exp<p2ptr->exp)
{
coe=p2ptr->coe; exp=p2ptr->exp; p2ptr=p2ptr->next;
}
ptrn=new node; if(start==NULL)
start=ptrn; ptrn->coe=coe; ptrn->exp=exp; ptrn->next=NULL; ptrp->next=ptrn; ptrp=ptrn;
} // End of While if(p1ptr==NULL)
{
while(p2ptr!=NULL)
{
coe=p2ptr->coe; exp=p2ptr->exp; p2ptr=p2ptr->next; ptrn=new node; if(start==NULL)
start=ptrn; ptrn->coe=coe; ptrn->exp=exp;
ptrn->next=NULL; ptrp->next=ptrn; ptrp=ptrn;
}
}
else if(p2ptr==NULL)
{
while(p1ptr!=NULL)
{
coe=p1ptr->coe; exp=p1ptr->exp; p1ptr=p1ptr->next; ptrn=new node; if(start==NULL)
start=ptrn; ptrn->coe=coe; ptrn->exp=exp;
ptrn->next=NULL; ptrp->next=ptrn; ptrp=ptrn;
}
}
} // End of addition

// Subtract two polynomials

void polynomial::subtract(polynomial p1,polynomial p2) // Subtract
{
struct node *p1ptr,*p2ptr; int coe,exp; ptrn=ptrp=start=NULL; p1ptr=p1.start; p2ptr=p2.start;
while(p1ptr!=NULL && p2ptr!=NULL)
{
if(p1ptr->exp==p2ptr->exp) // If coefficients are equal
{
coe=p1ptr->coe-p2ptr->coe; exp=p1ptr->exp; p1ptr=p1ptr->next; p2ptr=p2ptr->next;
}
else if(p1ptr->exp>p2ptr->exp)
{
coe=p1ptr->coe; exp=p1ptr->exp; p1ptr=p1ptr->next;
}
else if(p1ptr->exp<p2ptr->exp)
{
coe=0-p2ptr->coe; exp=p2ptr->exp; p2ptr=p2ptr->next;
}
ptrn=new node; if(start==NULL)

Page 45
IIFST Data Structures and Analysis of Algorithm-Lab

start=ptrn; ptrn->coe=coe; ptrn->exp=exp; ptrn->next=NULL; ptrp->next=ptrn; ptrp=ptrn;

} // End of While if(p1ptr==NULL)
{
while(p2ptr!=NULL)
{
coe=0-p2ptr->coe; exp=p2ptr->exp; p2ptr=p2ptr->next; ptrn=new node; if(start==NULL)
start=ptrn; ptrn->coe=coe; ptrn->exp=exp;
ptrn->next=NULL; ptrp->next=ptrn; ptrp=ptrn;
}
}
else if(p2ptr==NULL)
{
while(p1ptr!=NULL)
{
coe=p1ptr->coe; exp=p1ptr->exp; p1ptr=p1ptr->next; ptrn=new node; if(start==NULL)
start=ptrn; ptrn->coe=coe; ptrn->exp=exp;
ptrn->next=NULL; ptrp->next=ptrn; ptrp=ptrn;
}
}
} // End of subtraction

int main()
{
clrscr();
polynomial p1,p2,sum,diff; cout<<"\nFirst Polynomial"; p1.get_poly(); cout<<"\nSecond
polynomial."; p2.get_poly();
cout<<"\nThe First polynomial is: "; p1.show();
cout<<"\nThe second polynomial is: "; p2.show();
cout<<"\nThe sum of two polynomials is: "; sum.add(p1,p2);
sum.show();
cout<<"\nThe difference of two polynomials is: "; diff.subtract(p1,p2);
diff.show();
getch();
return 0;
}

Expected Output:

First Polynomial
Enter the coefficient: 2 Enter the exponent: 2
Enter y to add more nodes: 3

Second polynomial. Enter the coefficient: 3

Enter the exponent: 3

Enter y to add more nodes: 4 The First polynomial is: 2X^2 +

The second polynomial is: 3X^3 +
The sum of two polynomials is: 3X^3 + 2X^2 +
The difference of two polynomials is: -3X^3 + 2X^2 +

Page 46
IIFST Data Structures and Analysis of Algorithm-Lab

Program 5:Implementation of Linear search and Binary search

Aim: Given an array arr[] of n elements, write a function to search a given element x in
arr[] using linear search.

Description :
A simple approach is to do a linear search, i.e
 Start from the leftmost element of arr[] and one by one compare x with each element of
arr[]
 If x matches with an element, return the index.
 If x doesn’t match with any of elements, return -1.

6.A) Linear Search

#include <iostream>
using namespace std;

// linear search template function

// arr: array
// n: size of array
// x: value to search
// the function returns the index of x if it is present in arr
// otherwise it returns -1
template <class T>
int LinearSearch(T arr[], int n, T x) {

for (int i = 0; i < n; ++i) {

if (arr[i] == x)
return i;

return -1;

int main() {

int arr[] = { 6 , 43 ,23 ,6, 12 ,43, 3, 4, 2, 6 };

int n, index, x;
n = sizeof(arr) / sizeof(int); // size of arr

cout << "Integer Array: ";

for (int i = 0; i < n; ++i) cout << arr[i] << ' ';
cout << endl;

cout << "Enter Value you want to search: ";

cin >> x;

index = LinearSearch(arr, n, x);

Page 47
IIFST Data Structures and Analysis of Algorithm-Lab

if (index != -1)
cout << x << " is present in the array at position " << index << endl;
else
cout << x << " is not present in the array \n" << endl;

/* */

char charArr[] = { 'A', 'v', 'D', 'R', 'T','u', 'j', 'o' };

char c;
n = sizeof(charArr) / sizeof(char);

cout << "Char Array: ";

for (int i = 0; i < n; ++i) cout << charArr[i] << ' ';
cout << endl;

cout << "Enter character you want to search: ";

cin >> c;

index = LinearSearch(charArr, n, c);

if (index != -1)
cout << c << " is present in the array at position " << index << endl;
else
cout << c << " is not present in the array " << endl;

}
Expected Output:

Integer Array: 6 43 23 6 12 43 3 4 2 6
Enter Value you want to search: 43
43 is present in the array at position 1
Char Array: A v D R T u j o
Enter character you want to search: t
t is not present in the array

6.B) Aim :Program to search for an element in an array using Binary search.
The elements in the array has to be considered in sorted order.

#include<iostream>
using namespace std;
// binary search function using template
// n: size of arr
// x: value to search
// the fucntion returns -1 if x is not found in arr
// otherwise it returns index of x
template<typename T>
int binary_search(T arr[],int n,T x)
{
int start = 0;

Page 48
IIFST Data Structures and Analysis of Algorithm-Lab

int end = n-1;

while(start<=end)
{
int mid = (start+end)/2;
if(arr[mid]==x)
return mid;
else if(arr[mid]<x)
start = mid + 1;
else
end = mid - 1;
}
return -1;
}

// Template function to print array

// n: size of arr
template<typename T>
void PrintArray(T arr[], int n)
{
for (int i = 0; i < n; ++i)
cout << arr[i] << " ";
cout << "\n\n";
}
int main()
{
int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11 ,12 };
int n = sizeof(arr) / sizeof(int);
cout << "Array : " << endl;
PrintArray(arr, n);
int x, index;
cout<<"Enter value you want to Search: ";
cin>>x;

index = binary_search(arr, n, x);

if(index==-1)
cout<<x<<" is not present in the array"<<endl;
else
cout<<x<<" is present in the array at position "<<index<<endl;
}
Expected Output:

Array :
1 2 3 4 5 6 7 8 9 10 11 12
Enter value you want to Search: 2
2 is present in the array at position 1

Array :
1 2 3 4 5 6 7 8 9 10 11 12

Enter value you want to Search: 20

20 is not present in the array

Page 49
IIFST Data Structures and Analysis of Algorithm-Lab

Program 6:Implementation of Hashing Technique

Aim: Implementation of Hashing Technique

Description :
Hashing: Hashing is an important concept in Computer Science. A Hash Table is a
data structure that allows you to store and retrieve data very quickly. There are three
components that are involved with performing storage and retrieval with Hash Tables:

A hash table. This is a fixed size table that stores data of a given type.
A hash function: This is a function that converts a piece of data into an integer.
Sometimes we call this integer a hash value. The integer should be at least as big as the
hash table. When we store a value in a hash table, we compute its hash value with the
hash function, take that value modulo the hash table size, and that's where we
store/retrieve the data.
A collision resolution strategy: There are times when two pieces of data have hash
values that, when taken modulo the hash table size, yield the same value. That is called
a collision. You need to handle collisions. We will detail four collision resolution
strategies: Separate chaining, linear probing, quadratic probing, and double hashing.

Example

We have numbers from 1 to 100 and hash table of size 10. Hash function is mod 10. That
means number 23 will be mapped to (23 mod 10 = 3) 3rd index of hash table.

But problem is if elements (for example) 2, 12, 22, 32, elements need to be inserted then they
try to insert at index 2 only. This problem is called Collision. To solve this collision problem
we use different types of hash function techniques. Those are given below.

Chaining

Page 50
IIFST Data Structures and Analysis of Algorithm-Lab

Open addressing
Linear probing
a.Quadratic probing
b.Double hashing

These also called collision resolution techniques.

Chaining
In hash table instead of putting one element in index we maintain a linked list. When collision
happened we place that element in corresponding linked list. Here some space is wasted
because of pointers.

Aim:Program to implement hashing with chaining

#include<bits/stdc++.h>
using namespace std;

class Hash
{
int BUCKET; // No. of buckets

// Pointer to an array containing buckets

list<int> *table;
public:
Hash(int V); // Constructor

// inserts a key into hash table

void insertItem(int x);

// deletes a key from hash table

void deleteItem(int key);

// hash function to map values to key

int hashFunction(int x) {
return (x % BUCKET);
}

void displayHash();
};

Page 51
IIFST Data Structures and Analysis of Algorithm-Lab

Hash::Hash(int b)
{
this->BUCKET = b;
table = new list<int>[BUCKET];
}

void Hash::insertItem(int key)

{
int index = hashFunction(key);
table[index].push_back(key);
}

void Hash::deleteItem(int key)

{
// get the hash index of key
int index = hashFunction(key);

// find the key in (inex)th list

list <int> :: iterator i;
for (i = table[index].begin();
i != table[index].end(); i++) {
if (*i == key)
break;
}

// if key is found in hash table, remove it

if (i != table[index].end())
table[index].erase(i);
}

// function to display hash table

void Hash::displayHash() {
for (int i = 0; i< BUCKET; i++) {
cout<<i;
for (auto x : table[i])
cout<< " --> " << x;
cout<< endl;
}
}

// Driver program
int main()
{
// array that contains keys to be mapped
int a[] = {15, 11, 27, 8, 12};
int n = sizeof(a)/sizeof(a[0]);

// insert the keys into the hash table

Hash h(7); // 7 is count of buckets in
// hash table
for (int i = 0; i< n; i++)
h.insertItem(a[i]);

Page 52
IIFST Data Structures and Analysis of Algorithm-Lab

// delete 12 from hash table

h.deleteItem(12);
// display the Hash table
h.displayHash();
return 0;
}

Expected Output:
0
1 --> 15 --> 8
2
3
4 --> 11
5
6 --> 27

Page 53
IIFST Data Structures and Analysis of Algorithm-Lab

Program 7:Implementation of Binary Tree and Binary Tree Traversal techniques (in
order, pre order, post order, level-order)

Aim: Implementation of Binary Tree and Binary Tree Traversal techniques (in order, pre
order, post order, level-order)

Description :

Trees: A tree is a nonlinear hierarchical data structure that consists of nodes connected by
edges.

Node : A node is an entity that contains a key or value and pointers to its child nodes.

The last nodes of each path are called leaf nodes or external nodes that do not contain a
link/pointer to child nodes. The node having at least a child node is called an internal node.
Edge :It is the link between any two nodes.

Nodes and edges of a tree

Root: It is the topmost node of a tree.

Height of a Node :The height of a node is the number of edges from the node to the deepest
leaf (ie. the longest path from the node to a leaf node).

Depth of a Node :The depth of a node is the number of edges from the root to the node.

Height of a Tree: The height of a Tree is the height of the root node or the depth of the
deepest node.

Page 54
IIFST Data Structures and Analysis of Algorithm-Lab

Height and depth of each node in a tree

Degree of a Node: The degree of a node is the total number of branches of that node.

An example of a Tree with 15 nodes

Page 55
IIFST Data Structures and Analysis of Algorithm-Lab

This is not a Tree, as it has multiple paths between a pair of nodes.

Binary Trees: A binary tree is a tree data structure in which each parent node can have
at most two children. A binary tree is a special kind of tree in which each node can
haveat most two children: they are distinguished as a left child and a right child. The
subtreerooted at the left child of a node is called its left subtree and the subtree rooted
at the right child of a node is called its right subtree.

Level of a node refers to the distance of a node from the root. The level of the root is 1.
Children of the root are at level 2, grandchildren or children of the children of the root
are at level 3, etc.

Maximum number of nodes on a level i of a binary tree is 2i-1. Also the maximum
number of nodes in a binary tree of depth k is 2k – 1, k>0.

Page 56
IIFST Data Structures and Analysis of Algorithm-Lab

A) Binary Tree
Aim :Program to create a Binary tree and perform inorder,preorder,postorder
traversal on the tree.

#include<stdio.h>
#include<stdlib.h>
typedef char EleType;
typedef struct BiTNode{
EleType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;

//Create a binary tree recursively according to the pre-order traversal method

bool createBitTree(BiTree *T){
EleType data;
scanf("%c",&data);
if('#' == data)
*T = nullptr;
else{
(*T) = (BiTree)malloc(sizeof(BiTNode));
if(!(*T)){
exit(-1);
}
(*T)->data = data;
createBitTree(&(*T)->lchild);//Create the left subtree
createBitTree(&(*T)->rchild);//Create the right subtree
}
return true;
}

void visite(EleType data){

printf("%c",data);
}

//Recursively realize the first order traversal of the binary tree

bool proOrderTraverse(BiTree &T){
if(T == nullptr)
return false;
visite(T->data);
proOrderTraverse(T->lchild);
proOrderTraverse(T->rchild);

return true;
}
//Recursively implement in-order traversal of the binary tree
bool inOrderTraverse(BiTree &T){
if(T == nullptr)
return false;

inOrderTraverse(T->lchild);
visite(T->data);

Page 57
IIFST Data Structures and Analysis of Algorithm-Lab

inOrderTraverse(T->rchild);

return true;
}
//Recursively implement post-order traversal of the binary tree
bool postOrderTraverse(BiTree &T){
if(T == nullptr)
return false;

postOrderTraverse(T->lchild);
postOrderTraverse(T->rchild );
visite(T->data);

return true;
}
int main(){
BiTree T;
createBitTree(&T);
proOrderTraverse(T);
printf("\n");
inOrderTraverse(T);
printf("\n");
postOrderTraverse(T);
getchar();
return 0;
}

Expected Output:
ABC##DE#G##F###
ABCDEGF
CBEGDFA
CGEFDBA

Page 58
IIFST Data Structures and Analysis of Algorithm-Lab

Program 8: Implementation of Binary Search Tree and its operations.

Aim: Implementation of Binary Search Tree and its operations.

Description

Binary Search Tree: A binary search tree is a binary tree which may be empty. If not
empty, it satisfies the following properties:

1. Every element has a key and no two elements have the same key.
2. The keys (if any) in the left subtree are smaller than the key in the root
3. The keys (if any) in the right subtree are greater than the key in the root
4. The left and right subtrees are binary search trees.

Binary Search Treeon Number Binary Search Tree onStrings

Searching a Binary Search Tree: Suppose we wish to search for an element with key
x. We being at root. If the root is 0, then the search tree contains no elements and the
search terminates unsuccessfully. Otherwise, we compare x with key in root. If x equals
key in root, then search terminates successfully. If x is less than key in root, then no
element in right sub tree can have key value x, and only left subtree is to be searched. If
x is larger than key in root, the no element in left subtree can have the key x, and only
right subtree is to be searched. The subtrees can be searched recursively.

Insertion into a Binary Search Tree: To insert an element x, we must first verify that
its key is different from those of existing elements. To do this, a search is carried out. If
search is unsuccessful, then element is inserted at point where the search terminated.

Page 59
IIFST Data Structures and Analysis of Algorithm-Lab

Deleting from a Binary Search Tree: Deletion from a leaf element is achieved by
simply removing the leaf node and making its parent’s child field to be null. Other cases
are deleting a node with one subtree and two subtrees.

Deleting aleaf node Deleting a non leaf node.

Aim :Program in C++ to create a Binary search tree, insert a node a binary tree, delete a
node , perform traversal on BST.

#include<iostream>

#include<stdlib.h>

using namespace std;

struct treeNode

int data;

treeNode *left;

treeNode *right;

};

treeNode* FindMin(treeNode *node)

if(node==NULL)

/* There is no element in the tree */

Page 60
IIFST Data Structures and Analysis of Algorithm-Lab

return NULL;

if(node->left) /* Go to the left sub tree to find the min element */

return FindMin(node->left);

else

return node;

treeNode* FindMax(treeNode *node)

if(node==NULL)

/* There is no element in the tree */

return NULL;

if(node->right) /* Go to the left sub tree to find the min element */

return(FindMax(node->right));

else

return node;

treeNode *Insert(treeNode *node,int data)

if(node==NULL)

treeNode *temp;

temp=new treeNode;

//temp = (treeNode *)malloc(sizeof(treeNode));

temp -> data = data;

temp -> left = temp -> right = NULL;

Page 61
IIFST Data Structures and Analysis of Algorithm-Lab

return temp;

if(data >(node->data))

node->right = Insert(node->right,data);

else if(data < (node->data))

node->left = Insert(node->left,data);

/* Else there is nothing to do as the data is already in the tree. */

return node;

treeNode * Delet(treeNode *node, int data)

treeNode *temp;

if(node==NULL)

cout<<"Element Not Found";

else if(data < node->data)

node->left = Delet(node->left, data);

else if(data > node->data)

node->right = Delet(node->right, data);

Page 62
IIFST Data Structures and Analysis of Algorithm-Lab

else

/* Now We can delete this node and replace with either minimum element

in the right sub tree or maximum element in the left subtree */

if(node->right && node->left)

/* Here we will replace with minimum element in the right sub tree */

temp = FindMin(node->right);

node -> data = temp->data;

/* As we replaced it with some other node, we have to delete that node */

node -> right = Delet(node->right,temp->data);

else

/* If there is only one or zero children then we can directly

remove it from the tree and connect its parent to its child */

temp = node;

if(node->left == NULL)

node = node->right;

else if(node->right == NULL)

node = node->left;

free(temp); /* temp is longer required */

return node;

treeNode * Find(treeNode *node, int data)

Page 63
IIFST Data Structures and Analysis of Algorithm-Lab

if(node==NULL)

/* Element is not found */

return NULL;

if(data > node->data)

/* Search in the right sub tree. */

return Find(node->right,data);

else if(data < node->data)

/* Search in the left sub tree. */

return Find(node->left,data);

else

/* Element Found */

return node;

void Inorder(treeNode *node)

if(node==NULL)

return;

Inorder(node->left);

Page 64
IIFST Data Structures and Analysis of Algorithm-Lab

cout<<node->data<<" ";

Inorder(node->right);

void Preorder(treeNode *node)

if(node==NULL)

return;

cout<<node->data<<" ";

Preorder(node->left);

Preorder(node->right);

void Postorder(treeNode *node)

if(node==NULL)

return;

Postorder(node->left);

Postorder(node->right);

cout<<node->data<<" ";

int main()

treeNode *root = NULL,*temp;

int ch;

//clrscr();

Page 65
IIFST Data Structures and Analysis of Algorithm-Lab

while(1)

cout<<"\n1.Insert\n2.Delete\n3.Inorder\n4.Preorder\n5.Postorder\n6.FindMin\n7.FindMax\n8.
Search\n9.Exit\n";

cout<<"Enter ur choice:";

cin>>ch;

switch(ch)

case 1:

cout<<"\nEnter element to be insert:";

cin>>ch;

root = Insert(root, ch);

cout<<"\nElements in BST are:";

Inorder(root);

break;

case 2:

cout<<"\nEnter element to be deleted:";

cin>>ch;

root = Delet(root,ch);

cout<<"\nAfter deletion elements in BST are:";

Inorder(root);

break;

case 3:

cout<<"\nInorder Travesals is:";

Inorder(root);

break;

case 4:

cout<<"\nPreorder Traversals is:";

Page 66
IIFST Data Structures and Analysis of Algorithm-Lab

Preorder(root);

break;

case 5:

cout<<"\nPostorder Traversals is:";

Postorder(root);

break;

case 6:

temp = FindMin(root);

cout<<"\nMinimum element is :"<<temp->data;

break;

case 7:

temp = FindMax(root);

cout<<"\nMaximum element is :"<<temp->data;

break;

case 8:

cout<<"\nEnter element to be searched:";

cin>>ch;

temp = Find(root,ch);

if(temp==NULL)

cout<<"Element is not foundn";

else

cout<<"Element "<<temp->data<<" is Found\n";

break;

case 9:

Page 67
IIFST Data Structures and Analysis of Algorithm-Lab

exit(0);

break;

default:

cout<<"\nEnter correct choice:";

break;

return 0;

Expected Output:

1. Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:1

Enter element to be insert:10

Elements in BST are:10

1.Insert

2. Delete

3.Inorder

4.Preorder

5.Postorder

Page 68
IIFST Data Structures and Analysis of Algorithm-Lab

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:1

Enter element to be insert:13

Elements in BST are:10 13

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:1

Enter element to be insert:12

Elements in BST are:10 12 13

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Page 69
IIFST Data Structures and Analysis of Algorithm-Lab

Enter ur choice:1

Enter element to be insert:14

Elements in BST are:10 12 13 14

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:1

Enter element to be insert:9

Elements in BST are:9 10 12 13 14

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:1

Enter element to be insert:7

Elements in BST are:7 9 10 12 13 14

1.Insert

Page 70
IIFST Data Structures and Analysis of Algorithm-Lab

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:3

Inorder Travesals is:7 9 10 12 13 14

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:4

Preorder Traversals is:10 9 7 13 12 14

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

Page 71
IIFST Data Structures and Analysis of Algorithm-Lab

8.Search

9.Exit

Enter ur choice:5

Postorder Traversals is:7 9 12 14 13 10

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:6

Minimum element is :7

1.Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:7

Maximum element is :14

1.Insert

2. Delete

Page 72
IIFST Data Structures and Analysis of Algorithm-Lab

3. Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:8

Enter element to be searched:12

Element 12 is Found

1. Insert

2.Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

7.FindMax

8.Search

9.Exit

Enter ur choice:2

Enter element to be deleted:12

After deletion elements in BST are:7 9 10 13 14

1.Insert

2. Delete

3.Inorder

4.Preorder

5.Postorder

6.FindMin

Page 73
IIFST Data Structures and Analysis of Algorithm-Lab

7.FindMax

8.Search

9.Exit

Enter ur choice:9

Page 74
IIFST Data Structures and Analysis of Algorithm-Lab

Program 9. Implementation of Insertion Sort, Selection Sort, Bubble Sort, Merge Sort,
Quick Sort, Heap Sort

Aim: Implementation of Insertion Sort, Selection Sort, Bubble Sort, Merge Sort, Quick
Sort, Heap Sort

Description

Sorting is nothing but arranging the data in ascending or descending order. Sorting
arrangesdata in a sequence which makes searching easier.

Different Sorting Algorithms

There are many different techniques available for sorting, differentiated by their efficiency
and space requirements. Following are some sorting techniques:

 Insertion Sort
 Selection Sort
 Bubble Sort
 Quick Sort
 Merge Sort
 Heap Sort

10.A)Aim: Program to sort elements of an array using Insertion sort.

#include<iostream>
using namespace std;

int main ()
{

int i,j, k,temp;

int a[10] = { 10, 9, 7, 101, 23, 44, 12, 78, 34, 23};

cout<<"\nprinting sorted elements...\n";

for(k=1; k<10; k++)

{
temp = a[k];

j= k-1;
while(j>=0 && temp <= a[j])

{
a[j+1] = a[j];

j = j-1;
}

a[j+1] = temp;
}

for(i=0;i<10;i++)

Page 75
IIFST Data Structures and Analysis of Algorithm-Lab

cout <<a[i]<<"\n";
}

}
Expected Output:

printing sorted elements...

10

12

23

23

34

44

78

101

10.B)Aim: Program to sort elements of an array using Selection Sort

#include<iostream>
using namespace std;
int smallest(int[],int,int);
int main ()
{
int a[10] = {10, 9, 7, 101, 23, 44, 12, 78, 34, 23};
int i,j,k,pos,temp;
for(i=0;i<10;i++)
{
pos = smallest(a,10,i);
temp = a[i];
a[i]=a[pos];
a[pos] = temp;
}
cout<<"\n printing sorted elements...\n";
for(i=0;i<10;i++)
{

Page 76
IIFST Data Structures and Analysis of Algorithm-Lab

cout<<a[i]<<"\n";
}
return 0;
}
int smallest(int a[], int n, int i)
{
int small,pos,j;
small = a[i];
pos = i;
for(j=i+1;j<10;j++)
{
if(a[j]<small)
{
small = a[j];
pos=j;
}
}
return pos;
}
Expected Output:
printing sorted elements...
7
9
10
12
23
23
34
44
78
101

10.C) Aim: Write a Program to sort the elements of an array using Bubble Sort

#include<iostream>
usingnamespacestd;
intmain()
{
inta[50],n,i,j,temp;
cout<<"Enter the size of array: ";
cin>>n;

Page 77
IIFST Data Structures and Analysis of Algorithm-Lab

cout<<"Enter the array elements: ";

for(i=0;i<n;++i)
cin>>a[i];
for(i=0;i<n;++i)
{
for(j=0;j<(n-i-1);++j)
if(a[j]>a[j+1])
{
temp=a[j];
a[j]=a[j+1];
a[j+1]=temp;
}
}
cout<<"Array after bubble sort:";
for(i=0;i<n;++i)
cout<<" "<<a[i];
return0;
}
Expected Output:
Enter the size of array: 10
Enter the array elements: 2
1
4
0
-1
3
5
7
6
10
Array after bubble sort: -1 0 1 2 3 4 5 6 7 10
10.D) Aim:Program to sort the elements of an array using Quick sort
#include<iostream>
#include<vector>
using namespace std;
// template function to find the position of pivot element
// last element is taken as pivot
template <typename T>
int Partition(T arr[], int start, int end){
int pivot = end;
int j = start;
for(int i=start;i<end;++i){

Page 78
IIFST Data Structures and Analysis of Algorithm-Lab

if(arr[i]<arr[pivot]){
swap(arr[i],arr[j]);
++j;
}
}
swap(arr[j],arr[pivot]);
return j;
}
// template function to perform quick sort on array arr
template <typename T>
void Quicksort(T arr[], int start, int end ){
if(start<end){
int p = Partition(arr,start,end);
Quicksort(arr,start,p-1);
Quicksort(arr,p+1,end);
}
}
// Template function to print array
// n: size of arr[]
template <typename T>
void PrintArray(T arr[], int n){
for(int i=0;i<n;++i)
cout<<arr[i]<<" ";
cout<<"\n\n";
}
int main() {
int arr[] = { 1 , 10 , 11 , 9 , 14 , 3 , 2 , 20 , 19, 43, 57, 3, 2 };
int n = sizeof(arr)/sizeof(int);
cout<<"Array Before Sorting: "<<endl;
PrintArray(arr, n);
Quicksort(arr,0,n-1);
cout<<"Array After Sorting: "<<endl;
PrintArray(arr, n);
}
Expected Output:
Array Before Sorting:
1 10 11 9 14 3 2 20 19 43 57 3 2
Array After Sorting:
1 2 2 3 3 9 10 11 14 19 20 43 57

Page 79
IIFST Data Structures and Analysis of Algorithm-Lab

10.E) Aim: Program to sort elements of array using merge sort

#include <iostream>
using namespace std;
// A function to merge the two half into a sorted data.
void Merge(int *a, int low, int high, int mid)
{
// We have low to mid and mid+1 to high already sorted.
int i, j, k, temp[high-low+1];
i = low;
k = 0;
j = mid + 1;
// Merge the two parts into temp[].
while (i <= mid && j <= high)
{
if (a[i] < a[j])
{
temp[k] = a[i];
k++;
i++;
}
else
{
temp[k] = a[j];
k++;
j++;
}
}
// Insert all the remaining values from i to mid into temp[].
while (i <= mid)
{
temp[k] = a[i];
k++;
i++;
}
// Insert all the remaining values from j to high into temp[].
while (j <= high)
{
temp[k] = a[j];
k++;
j++;

Page 80
IIFST Data Structures and Analysis of Algorithm-Lab

}
// Assign sorted data stored in temp[] to a[].
for (i = low; i <= high; i++)
{
a[i] = temp[i-low];
}
}
// A function to split array into two parts.
void MergeSort(int *a, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
// Split the data into two half.
MergeSort(a, low, mid);
MergeSort(a, mid+1, high);

// Merge them to get sorted output.

Merge(a, low, high, mid);
}
}
int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
int arr[n];
for(i = 0; i < n; i++)
{
cout<<"Enter element "<<i+1<<": ";
cin>>arr[i];
}
MergeSort(arr, 0, n-1);
// Printing the sorted data.
cout<<"\nSorted Data ";
for (i = 0; i < n; i++)
cout<<"->"<<arr[i];
return 0;

Page 81
IIFST Data Structures and Analysis of Algorithm-Lab

}
Expected Output:
Enter the number of data element to be sorted: 5
Enter element 1: 6
Enter element 2: 4
Enter element 3: 9
Enter element 4: 0
Enter element 5: 1
Sorted Data ->0->1->4->6->9
10.F) Aim:Program to sort elements of array using Heap sort

#include <iostream>
using namespace std;
// A function to heapify the array.
void MaxHeapify(int a[], int i, int n)
{
int j, temp;
temp = a[i];
j = 2*i;
while (j <= n)
{
if (j < n && a[j+1] > a[j])
j = j+1;
// Break if parent value is already greater than child value.
if (temp > a[j])
break;
// Switching value with the parent node if temp < a[j].
else if (temp <= a[j])
{
a[j/2] = a[j];
j = 2*j;
}
}
a[j/2] = temp;
return;
}
void HeapSort(int a[], int n)
{
int i, temp;
for (i = n; i >= 2; i--)

Page 82
IIFST Data Structures and Analysis of Algorithm-Lab

{
// Storing maximum value at the end.
temp = a[i];
a[i] = a[1];
a[1] = temp;
// Building max heap of remaining element.
MaxHeapify(a, 1, i - 1);
}
}
void Build_MaxHeap(int a[], int n)
{
int i;
for(i = n/2; i >= 1; i--)
MaxHeapify(a, i, n);
}
int main()
{
int n, i;
cout<<"\nEnter the number of data element to be sorted: ";
cin>>n;
n++;
int arr[n];
for(i = 1; i < n; i++)
{
cout<<"Enter element "<<i<<": ";
cin>>arr[i];
}
// Building max heap.
Build_MaxHeap(arr, n-1);
HeapSort(arr, n-1);

// Printing the sorted data.

cout<<"\nSorted Data ";
for (i = 1; i < n; i++)
cout<<"->"<<arr[i];
return 0;
}
Expected Output:

Page 83
IIFST Data Structures and Analysis of Algorithm-Lab

Enter the number of data element to be sorted: 5

Enter element 1: 4
Enter element 2: 2
Enter element 3: 1
Enter element 4: 5
Enter element 5: 0

Sorted Data ->0->1->2->4->5

Page 84
IIFST Data Structures and Analysis of Algorithm-Lab

Program 10. Implementation of Graph Search Methods.

Aim: Implementation of Graph Search Methods

Discription

Graph: Graph is a non-linear data structure. It contains a set of points known as nodes (or
vertices) and a set of links known as edges (or Arcs). Here edges are used to connect the
vertices. A graph is defined as follows...

Graph is a collection of vertices and arcs in which vertices are connected with arcs. Graph is a
collection of nodes and edges in which nodes are connected with edges.

Generally, a graph G is represented as G = ( V , E ), where V is set of vertices and E is set of

edges.
Example:
The following is a graph with 5 vertices and 6 edges.

This graph G can be defined as G = ( V , E )

Where V = {A,B,C,D,E} and E = {(A,B),(A,C)(A,D),(B,D),(C,D),(B,E),(E,D)}.

Graph Traversal :
Graph traversal is a technique used for a searching vertex in a graph. The graph traversal is
also used to decide the order of vertices is visited in the search process. A graph traversal
finds the edges to be used in the search process without creating loops. That means using
graph traversal we visit all the vertices of the graph without getting into looping path.
There are two graph traversal techniques and they are as follows...
1. DFS (Depth First Search)

2. BFS (Breadth First Search)

DFS (Depth First Search)

DFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph
without loops. We use Stack data structure with maximum size of total number of vertices
in the graph to implement DFS traversal.
We use the following steps to implement DFS traversal...

Step 1 - Define a Stack of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and push it on to
the Stack.

Page 85
IIFST Data Structures and Analysis of Algorithm-Lab

Step 3 - Visit any one of the non-visited adjacent vertices of a vertex which is at the top of
stack and push it on to the stack.

Step 4 - Repeat step 3 until there is no new vertex to be visited from the vertex which is at the
top of the stack.

Step 5 - When there is no new vertex to visit then use back tracking and pop one vertex from
the stack.

Step 6 - Repeat steps 3, 4 and 5 until stack becomes Empty.

Step 7 - When stack becomes Empty, then produce final spanning tree by removing unused
edges from the graph

Page 86
IIFST Data Structures and Analysis of Algorithm-Lab

Page 87
IIFST Data Structures and Analysis of Algorithm-Lab

12.A) Aim: Write a C++ Program to implement Depth first Search

#include<iostream>
using namespace std;
class graph
{
int a[10][10],n,start;
public:
void getdata();
void dfs_traverse();
};
void graph::getdata()
{
cout<<"Enter the number of vertices in the graph ";
cin>>n;
cout<<"Enter the adjacency matrix of graph "<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
cout<<"Enter the vertex from which you want to traverse ";
cin>>start;
}
void graph::dfs_traverse()
{
int *visited= new int[n];
int stack[10],top=-1,i;
for(int j=0;j<n;j++)
visited[j]=0;
cout<<"The Depth First Search Traversal : "<<endl;
i=stack[++top]=start;
visited[start]=1;
while(top>=0)
{
i=stack[top];
cout<<stack[top--]<<endl;
for(int j=n-1;j>=0;j--)
if(a[i][j]!=0&&visited[j]!=1)
{
stack[++top]=j;
visited[j]=1;
}
}
}
int main()
{
graph dfs;
dfs.getdata();
dfs.dfs_traverse();
return 0;
}

Expected Output:

Page 88
IIFST Data Structures and Analysis of Algorithm-Lab

Enter the number of vertices in the graph 5

Enter the adjacency matrix of graph

01101

10010

10011

01100

00110

Enter the vertex from which you want to traverse 1

The Depth First Search Traversal :

BFS (Breadth First Search)

BFS traversal of a graph produces a spanning tree as final result. Spanning Tree is a graph
without loops. We use Queue data structure with maximum size of total number of vertices in
the graph to implement BFS traversal.
We use the following steps to implement BFS traversal...

Step 1 - Define a Queue of size total number of vertices in the graph.

Step 2 - Select any vertex as starting point for traversal. Visit that vertex and insert it into the
Queue.

Step 3 - Visit all the non-visited adjacent vertices of the vertex which is at front of the Queue
and insert them into the Queue.

Step 4 - When there is no new vertex to be visited from the vertex which is at front of the
Queue then delete that vertex.

Step 5 - Repeat steps 3 and 4 until queue becomes empty.

Step 6 - When queue becomes empty, then produce final spanning tree by removing unused
edges from the graph

Page 89
IIFST Data Structures and Analysis of Algorithm-Lab

Page 90
IIFST Data Structures and Analysis of Algorithm-Lab

12.B) Aim: Write a C++ program to implement Breadth first search traversal

#include<iostream>
using namespace std;
class graph
{
int a[10][10],n,start;
public:
void getdata();
void bfs_traverse();
};
void graph::getdata()
{
cout<<"Enter the number of vertices in the graph ";
cin>>n;
cout<<"Enter the adjacency matrix of graph "<<endl;
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
cin>>a[i][j];
cout<<"Enter the vertex from which you want to traverse ";
cin>>start;
}
void graph::bfs_traverse()
{
int *visited= new int[n];
int queue[10],front=-1,rear=0,i;
for(int j=0;j<n;j++)
visited[j]=0;
cout<<"Traversing the graph using breadth first search algorithm : "<<endl;
queue[rear]=start;
visited[start]=1;
while(front!=rear)
{
cout<<queue[++front]<<endl;
i=queue[front];
for(int j=0;j<n;j++)
if(a[i][j]!=0&&visited[j]!=1)
{
queue[++rear]=j;

Page 91
IIFST Data Structures and Analysis of Algorithm-Lab

visited[j]=1;
}
}
}
int main()
{
graph bfs;
bfs.getdata();
bfs.bfs_traverse();
return 0;
}
Expected Output:
Enter the number of vertices in the graph 5
Enter the adjacency matrix of graph
01101
10010
10011
01100
00110
Enter the vertex from which you want to traverse 1
Traversing the graph using breadth first search algorithm :
1
0
3
2
4

Page 92