DSA Lab Record

Go to Index Page 2 of 89
INDEX
Sr. No Program Page No
1 Write a Program to implement a stack using array 3
2 Write a Program to implement a stack using linked list 6
3 Write a Program to implement a queue using array 9
4 Write a Program to implement a queue using linked list 13
5 Write a Program to implement a circular queue using array 17
6 Write a Program to implement a simple linked list 21
7 Write a Program to implement a circular linked list 28
8 Write a Program to implement a doubly linked list 38
9 Write a Program to count a node in linked list 46
10 Write a Program to implement a reversed a linked list 51
11 Write a Program to implement the following Searching Algorithms:

53
A. Sequential search, B. Index Sequential Search, C. Binary Search
12 Write a Program to implement the following Sorting Algorithms:

A. Insertion Sort B. Selection Sort, C. Bubble Sort, 60
D. Quick Sort E. Merge Sort F. Heap Sort
13 Write a program to implement the Minimum Spanning Tree using

75
Kruskal’s Algorithm and Prim’s Algorithm.
14 Write a program to implement the TSP problem. 82
15 Write a Program to implement DFS & BFS 85
16 Write a Program to implement Dijkstra's Algorithm 91

Q.1 Write a Program to implement a stack using arrays.

#include<iostream.h>
int stack[6];
int top=-1;
int push()
{
int temp;
if(top==5)
cout<<"\n Stack is Overflow";
else
{
cout<<"\n Enter element in stack = ";
cin>>temp;
top++;
stack[top]=temp;
return top;
}
}
int pop()
{
int temp;
if(top==-1)
cout<<"\n Stack is Underflow ";
else
{
temp=stack[top];
top--;
cout<<"\n deleted element = "<<temp;
}
return top;
}
void display(int n)
{
int i;
if(top==-1)
cout<<"\n Stack is empty";
else
{
for(i=n;i>=0;i--)
{
cout<<"\n "<<stack[i];
n--;
}
}
}
int main()
{
int choice,status;
cout<<"\n 1 - Push element is stack";
cout<<"\n 2 - Pop element from stack";
cout<<"\n 3 - Display elements of stack";
cout<<"\n 4 - Quit";
do
{
cout<<"\n*******************************\n";
cout<<"\n\n Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
status=push();
break;
case 2:
status=pop();
break;
case 3:
display(status);
break;
case 4:
exit(0);
}
}while(choice!=4);
cout<<"\n\n Thank you for visiting";
return 0;
}
Q.2 Write a Program to implement a stack using a linked list.

#include<iostream>
#include<cstdlib>
class Stack_Node
{
public:
int data;
Stack_Node *link;
};
class Stack{
private:
Stack_Node *Top;
int size;
public:
Stack(){
Top=NULL;
size=0;
}
int GetTop();
int IsEmpty();
int Pop();
void Push(int Element);
int CurrSize();
};
int Stack::IsEmpty(){
if(Top==NULL){
cout<<"Stack is Empty";
return 1;
}
else
return 0;
}
void Stack::Push(int Element){

Stack_Node* newnode;
newnode= new Stack_Node;
newnode->data=Element;
newnode->link=NULL;
newnode->link=Top;
Top=newnode;
}
int Stack::Pop(){
Stack_Node* tmp=Top;
int data=Top->data;
if(!IsEmpty()){
Top=Top->link;
delete tmp;
return(data);
}
}
int Stack::GetTop(){
if(!IsEmpty())
return(Top->data);
}
int main() {
int choice, data;
Stack S;
cout<<"\n 1 - Insert element in queue";
cout<<"\n 2 - Delete element from queue";
cout<<"\n 3 - Display top of queue";
cout<<"\n 4 - Exit";
do
{
cout<<"\n*****************************";
cout<<"\n Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\n Enter value of element : ";
cin>>data;
S.Push(data);
break;
case 2:
cout<<"Pop : "<<S.Pop()<<"\n";
break;
case 3:
cout<<"Top of Stack : "<<S.GetTop()<<"\n";
break;
}
}while(choice<4);
return 0;
}
Q.3 Write a Program to implement a queue using array.
int queue[5];
int rear=0;
int front=0;
void insert()
{
int elem;
if(rear>4)
cout<<"\n No space in queue";
else
{
cout<<"\n Enter element in queue = ";
cin>>elem;
queue[rear]=elem;
rear++;
cout<<"\n Element added in queue";
}
}
void deQueue()
{
int temp;
if(front>4 || rear==0)
cout<<"\n Queue is empty";
else
{
temp=queue[front];
front++;
cout<<"\n Deleted element is "<<temp;
}
}
void display()
{
int i;
if(rear==0 || front>4)
cout<<"\n Queue is empty";
else
{
for(i=front;i<rear;i++)
{
cout<<"\n "<<queue[i];
}
}
}
int main()
{
int choice;
cout<<"\n 1 - Insert element in queue";
cout<<"\n 2 - Delete element from queue";
cout<<"\n 3 - Display element of queue";
do
{
cout<<"\n*****************************";
cout<<"\n Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
insert();
break;
case 2:
deQueue();
break;
case 3:
display();
break;
}
}while(choice<4);
return 0;
}
Q. 4. Write a Program to implement a queue using linked list.
#include<stdlib.h>
template <class T>
class node
{
public:
T data;
node<T>*next;
};
template <class T>

class queue {
private:
T item;
friend class node<T>;
node<T> *front,*rear;
public: queue();
void insert_q();
void delete_q();
void display_q();
};
template <class T>
queue<T>::queue() {
front=rear=NULL;
}
//code to push an item into queue;
template <class T>
void queue<T>::insert_q() {
node<T>*p;
cout<<"Enter an element to be inserted:";
cin>>item;
p=new node<T>;
p
->data=item;
p
->next=NULL;
if(front==NULL)
rear=front=p;
else
{
rear
->next=p;
rear=p;
}
cout<<"\nInserted into Queue Sucesfully....\n";
}
//code to delete an element
template <class T>
void queue<T>::delete_q() {
node<T>*t;
if(front==NULL)
cout<<"\nqueue is Underflow";
else
{
item=front
->data;
t=front;
front=front
->next;
cout<<"\n"<<item<<" is deleted Sucesfully from
queue....\n";
}
delete(t);
}
//code to display elements in queue
template <class T>
void queue<T>::display_q()
{
node<T>*t;
if(front==NULL)
cout<<"\nqueue Under Flow";
else
{
cout<<"\nElements in the queue are....\n";
t=front;
while(t!=NULL)
{
cout<<"|"<<t->data<<"|<-";
t=t->next;
}
}
}
int main()
{
int choice;
queue<int>q1;
cout<<"\n\n***Menu for Queue operations***\n\n";
cout<<"1.Insert\n2.Delete\n3.DISPLAY\n4.EXIT\n";
while(1)
{
cout<<"\nEnter Choice:";
cin>>choice;
switch(choice)
{
case 1: q1.insert_q();
break;
case 2: q1.delete_q();
break;
case 3: q1.display_q();
break;
case 4: exit(0);
default:cout<<"Invalid choice...Try again...\n";
}
}
return 0;
}
Q. 5. Write a Program to implement a circular queue using array.
#include <iostream.h>
int Queue[7];
int front=-1, rear=-1, n=7;
void AddinQueue(int val) {

if ((front == 0 && rear == n-1) || (front == rear+1)) {
cout<<"Queue Overflow \n";
return;
}
if (front == -1) {
front = 0;
rear = 0;
} else {
if (rear == n - 1)
rear = 0;
else
rear = rear + 1;
}
Queue[rear] = val ;
}
void deleteCQ() {
if (front == -1) {
cout<<"Queue Underflow\n";
return ;
}
cout<<"Element deleted from queue is : "<<Queue[front]<<endl;
if (front == rear) {
front = -1;
rear = -1;
} else {
if (front == n - 1)
front = 0;
else
front = front + 1;
}
}
void displayCQ() {
int f = front, r = rear;
if (front == -1) {
cout<<"Queue is empty"<<endl;
return;
}
cout<<"Queue elements are :\n";
if (f <= r) {
while (f <= r){
cout<<Queue[f]<<" ";
f++;
}
} else {
while (f <= n - 1) {
f++;
}
f = 0;
while (f <= r) {
f++;
}
}
cout<<endl;
}
int main() {
int choice, data;

cout<<"1. Insert element in Queue\n";
cout<<"2. Delete element from Queue\n";
cout<<"3. Display Queue\n";
cout<<"0. Quit\n";
do {
cout<<"\nEnter choice : "<<endl;
cin>>choice;
switch(choice) {
case 1:
cout<<"Input for insertion: "<<endl;
cin>>data;
AddinQueue(data);
break;
case 2:
deleteCQ();
break;
case 3:
displayCQ();
break;
case 0:
cout<<"Exit\n";
break;
default: cout<<"Incorrect!\n";
}
} while(choice != 0);
return 0;
}
Q. 6 Write a Program to implement a simple linked list.
class node{
public:
int data;
node *link;
};
class create
{
private:
node *head,*curr;
public:
create()
{
head=curr=NULL;
}
node * createNode(int n);

void addAtFirst(int n);
void addAtLast(int n);
void addAtPosition(int pos,int value);
void deleteAtFirst();
void deleteAtLast();
void deleteAtPosition(int pos);
void disp();
};
//create standalone node in memory

node * create::createNode(int n)
{
node *newNode;
newNode= new node;
newNode->data=n;
newNode->link=NULL;
return newNode;
}
//Delete element from specifeid position
void create::deleteAtPosition(int pos)
{
int counter=1;
node *temp;
curr=head;
if(head==NULL)
cout<<"\n List is Empty";
else if(pos==1)
head=head->link;
else
{
while(counter<pos)
{
if(curr->link==NULL)
break;
temp=curr;
curr=curr->link;
counter++;
}
if(counter==pos)
temp->link=curr->link;
else
cout<<"Position not found";
}
}
//Delete element from first position
void create::deleteAtFirst()
{
if(head==NULL)
cout<<"\n List is Empty";
else
head=head->link;
}
//Delete element from last position
void create::deleteAtLast()
{
node *temp;
curr=head;
if(head==NULL)
cout<<"\n List is empty";
else
{
while(1)
{
break;
temp=curr;
curr=curr->link;
}
temp->link=NULL;
}
}
//Add element at specified position
void create::addAtPosition(int pos,int value)
{
int flag=1,counter=2;
node *temp;
curr=head;
if(head==NULL)
{
temp=createNode(value);
head=temp;
}
else if(pos==1)
{
temp->link=head;
head=temp;
}
else
{
while(counter<pos)
{
break;
curr=curr->link;
counter++;
}
if(counter==pos)
{
curr->link=temp;
}
else
}
}
//Add element at first position

void create::addAtFirst(int n)
{
node * temp;
temp=createNode(n);
temp->link=head;
head=temp;
}
//Add element at last position

void create::addAtLast(int n)
{
node *temp;
temp=createNode(n);
if(head==NULL)
head=curr=temp;
else
{
curr=head;
while(1)
{
break;
curr=curr->link;
}
curr->link=temp;
}
}
//Display full list

void create::disp()
{
node *d=head;
cout<<"\n";
while(d!=NULL)
{
cout<<d->data<<"\t";
d=d->link;
}
}
//main() method
int main()
{
char ans;
int choice,element,pos;
create L1;
cout<<"\n 1 - Insert node at first position";
cout<<"\n 2 - Insert node at specified position";
cout<<"\n 3 - Insert node at last position";
cout<<"\n 4 - Delete node from first position";
cout<<"\n 5 - Delete node from specified position";
cout<<"\n 6 - Delete node from last position";

cout<<"\n 7 - Display List";
while(1)
{
cout<<"\n--->Enter your choice from menu : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\n Enter element to insert : ";
cin>>element;
L1.addAtFirst(element);
break;
case 2:
cout<<"\n Enter position to insert : ";
cin>>pos;
cin>>element;
L1.addAtPosition(pos,element);
break;
case 3:

cin>>element;
L1.addAtLast(element);
break;
case 4:
L1.deleteAtFirst();
break;
case 5:
cout<<"\n Enter positin of node to be deleted : ";
cin>>pos;
L1.deleteAtPosition(pos);
break;
case 6:
L1.deleteAtLast();
break;
case 7:
L1.disp();
break;
case 0:
exit(0);
default:
cout<<"\nInvalid Choice";
}
}
return 0;
}
Q. 7 Write a Program to implement a circular linked list.
#include <stdio.h>
class node
{
public:
int info;
node *next, *last;
node(){
next=last=NULL;
}
};
/*Class Declaration */
class circular_llist
{
private:
node *last, *next;
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<<"---------------------------"<<;
cout<<endl<<"Circular singly linked list"<<;
cout<<endl<<"---------------------------"<<endl;
cout<<"1.Create Node"<<endl;
cout<<"2.Add at beginning"<<endl;
cout<<"3.Add after"<<endl;
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:
cin>>element;
cl.add_begin(element);
cout<<endl;
break;
case 3:
cin>>element;
cout<<"Insert element after position: ";
cin>>position;
cl.add_after(element, position);
cout<<endl;
break;
case 4:
cout<<"Enter the element for deletion: ";
cin>>element;
cl.delete_element(element);
cout<<endl;
break;
case 5:
cout<<"Enter the element to be searched: ";
cin>>element;
cl.search_element(element);
cout<<endl;
break;
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)
{
node *temp;
temp = new 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;
}
node *temp;
temp = new node;
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;
}
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 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)
{
node *temp, *s;
if (last == NULL)
{
cout<<"List is empty, nothing to delete"<<endl;
return;
}
else
{
s = last->next;
/* If List has only one element*/
if (last->next == last && last->info == value)
{
temp = last;
last = NULL;
free(temp);
return;
}
if (s->info == value) /*First Element Deletion*/

{
temp = s;
last->next = s->next;
delete 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;
delete 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)
{
node *s;
int counter = 0;
if (last == NULL)
{
cout<<"List Empty!! Can't search"<<endl;
return;
}
else
{
s = last->next;
while (s != last)
{
counter++;
if (s->info == value)
{
cout<<" found at position "<<counter<<endl;
return;
}
s = s->next;
}
}
if (s->info == value)
{
counter++;
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()
{
node *s;
if (last == NULL)
{
cout<<"List is empty, nothing to display"<<endl;
return;
}
s = last->next;
cout<<"\nCircular 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)
{
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()
{
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;
}
}
Q. 8 Write a Program to implement a doubly linked list.
class DLL_Node{
public:
int data;
DLL_Node *pre,*next;
DLL_Node()
{
pre=NULL;
next=NULL;
}
};
class DList{
private:
DLL_Node *head ,*tail;
public:
DList()
{
head=tail=NULL;
}
void create();
DLL_Node* GetNode();
void Append(DLL_Node* newNode);
void Traverse();
void DeleteNode(int val);
void Delete_Pos(int pos);
void Insert_Pos(DLL_Node* newNode, int pos);
};
DLL_Node* DList::GetNode()
{
DLL_Node* newNode;
newNode= new DLL_Node;
cout<<"Enter the data to insert in node: \t";
cin>>newNode->data;
return (newNode);
}
void DList::Append(DLL_Node * newNode)
{
if(head==NULL)
{
head=newNode;
tail=newNode;
}
else{
tail->next=newNode;
newNode->pre=tail;
tail=newNode;
}
}
void DList::create()
{
char ans;
DLL_Node *newNode;
while(1)
{
cout<<"\nAny more node want to ceate (y/n) : ";
cin>>ans;
if(ans=='n'||ans=='N')break;
newNode=GetNode();
Append(newNode);
}
}
void DList::Traverse()
{
DLL_Node *curr;
curr=head;
if(curr==NULL)
cout<<"\nList Is Empty";
else
{
cout<<"\n\n Final list:\n\n";
while(curr!=NULL){
cout<<curr->data<<"\t";
curr=curr->next;
}
}
int main()
{
int choice, pos;
DList D1;
DLL_Node* newNode;
newNode= new DLL_Node;
D1.create();
D1.Traverse();
//DLL_Node NewNode;
//NewNode=D1.GetNode();
cout<<"\n\n 1 is for insert at position";

cout<<"\n 2 is for delete";
cout<<"\n 3 is for delete at position";
cout<<"\n\n -->> Enter Choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\nEnter position at whcih is to be
inserted : ";
cin>>pos;
D1.Insert_Pos(newNode, pos);
D1.Traverse();
break;
case 2:
cout<<"\nEnter value of node whcih is to
be deleted : ";
cin>>pos;
D1.DeleteNode(pos);
D1.Traverse();
break;
case 3:
cout<<"\nEnter position whcih is to be
deleted : ";
cin>>pos;
D1.Delete_Pos(pos);
D1.Traverse();
break;
default:
cout<<"Invalid choice";
}
return 0;
}
void DList :: Insert_Pos(DLL_Node* NewNode, int pos)

{
// int data;
cout<<"\nEnter the new node that u want to insert : ";
cin>>NewNode->data;
DLL_Node *temp=head;
int count=1;
if(head==NULL)
head=tail=NewNode;
else if (pos==1)
{
NewNode->next=head;
head->pre=NewNode;
head=NewNode;
}
else{
while(count!=pos){
temp=temp->next;
if(temp!=NULL)
count++;
else
break;
}
if (count== pos)
{
(temp->pre)->next=NewNode;
NewNode->pre=temp->pre;
temp->pre=NewNode;
NewNode->next=temp;
}
else
cout<<"\n Postion not found";
}
}
void DList::Delete_Pos(int pos)
{
int count=1;
DLL_Node *temp=head, *curr;
if(head==NULL)
cout<<"\nList is empty";
else if(pos==1)
{
temp=head;
head=head->next;
//release memory
delete temp;
}
else
{
while(count!=pos)
{
temp=temp->next;
//curr=temp->pre;
if(temp!=NULL)
count++;
else
break;
}
if(count==pos)
{
if(temp->next==NULL)
{
(temp->pre)->next=temp->next;
}
else
{
(temp->next)->pre=temp->pre;
}
//release memory
delete temp;
}
else
cout<<"\n Position not found\n List is \n";
}
}
void DList::DeleteNode(int val)
{
int flag=0;
DLL_Node *temp=head, *curr;
if(head==NULL)
cout<<"\nList is empty";
else if(head->data==val)
{
temp=head;
head=head->next;
delete temp;
}
else
{
while(1)
{
if(temp!=NULL)
{
if(temp->data==val)
{
flag=1;
break;
}
}
temp=temp->next;
//curr=temp->pre;
if(temp==NULL)
break;
}
if(flag==1)
{
if(temp->next==NULL)
{
}
else
{
(temp->next)->pre=temp->pre;
}
//release memory
delete temp;
}
else
cout<<"\n Oops! Node not found";
}
}
Q. 9 Write a Program to count a node in the linked list.
class node{
public:
int data;
node *link;
};
class create
{
private:
node *head,*curr;
public:
create()
{
head=curr=NULL;
}
node * createNode(int n);

void addAtFirst(int n);
void addAtLast(int n);
void addAtPosition(int pos,int value);
int node_count();
};
//create standalone node in memory

node * create::createNode(int n)
{
node *newNode;
newNode= new node;
newNode->data=n;
newNode->link=NULL;
return newNode;
}
//Add element at specified position

void create::addAtPosition(int pos,int value)
{
int flag=1,counter=2;
node *temp;
curr=head;
if(head==NULL)
{
head=temp;
}
else if(pos==1)
{
temp->link=head;
head=temp;
}
else
{
while(counter<pos)
{
break;
curr=curr->link;
counter++;
}
if(counter==pos)
{
curr->link=temp;
}
else
}
}
//Add element at first position

void create::addAtFirst(int n)
{
node * temp;
temp=createNode(n);
temp->link=head;
head=temp;
}
//Add element at last position

void create::addAtLast(int n)
{
node *temp;
temp=createNode(n);
if(head==NULL)
head=curr=temp;
else
{
curr=head;
while(1)
{
break;
curr=curr->link;
}
curr->link=temp;
}
}
int create::node_count( ) {
int nc=0; node*t; if(head==NULL){
cout<<"\nList Under Flow"<<endl;
cout<<"No Nodes in the Linked List are: "<<nc<<endl; }
else {
t=head;
while(t!=NULL) {
nc++; t=t->link; }
cout<<"No Nodes in the Linked List are: "<<nc<<endl;
}
return nc;
}
//main() method
int main()
{
char ans;
int choice,element,pos;
create L1;
cout<<"\n 1 - Insert node at first position";

cout<<"\n 2 - Insert node at specified position";
cout<<"\n 3 - Insert node at last position";
cout<<"\n 4 - Count nodes in List";
while(1)
{
cout<<"\n--->Enter your choice from menu : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"\n Enter element to insert : ";
cin>>element;
L1.addAtFirst(element);
break;
case 2:
cout<<"\n Enter position to insert : ";
cin>>pos;
cin>>element;
L1.addAtPosition(pos,element);
break;
case 3:
cin>>element;
L1.addAtLast(element);
break;
case 4:
cout<<"No of Nodes = "<<L1.node_count();
break;
case 0:
exit(0);
default:
cout<<"\nInvalid Choice";
}
}
return 0;
}
Q. 10 Write a Program to implement a reversed a linked list.
struct node {
int data;
struct node *next;
}*head = NULL;
/* Function to insert nodes in a linked list. */

void insert(int data) {
struct node *Node,*temp;
Node = (struct node*)malloc(sizeof(struct node));
Node->data = data;
Node->next = NULL;
if(head==NULL)
{
head=Node;
temp=Node;
}
else
{
temp->next = Node;
temp=Node;
}
}
/* Function to reverse the nodes in a linked list. */

void reverse() {
struct node *temp = NULL;
struct node *prev = NULL;
struct node *current = (head);
while(current != NULL) {
temp = current->next;
current->next = prev;
prev = current;
current = temp;
}
(head) = prev;
}
/* Function to print the nodes in a linked list. */

void printList() {
struct node *disp=head;
while(disp != NULL) {
cout<<disp->data<<" ";
disp = disp->next;
}
}
/* Driver function to check the above algorithm. */

int main() {
insert(100);
insert(200);
insert(300);
insert(400);
insert(500);
cout << "\nList before reversing" << endl;
printList();
reverse();
cout << endl;
cout << "\nList after reversing"<<endl;
printList();
return 0;
}
Q.11. Write a Program to implement the following Searching

Algorithms:
A. Sequential Search
B. Index Sequential Search
C. Binary Search.
A. Sequential Search
#include<iostream>
using namespace std;
int Lsearch(int list[ ],int n,int key);
int main()
{
int n,i,key,list[25],pos;
cout<<"Enter no of elements: \n";
cin>>n;
cout<<"Enter "<<n<<" elements:\n";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"Enter key to search: \n";
cin>>key;
pos= Lsearch (list,n,key);
if(pos==-1)
cout<<"\n Element not found.";
else
cout<<"\n Element found at index. "<<pos;
}
/*function for linear search*/

int Lsearch(int list[],int n,int key)
{
int i,pos=-1;
for(i=0;i<n;i++)
if(key==list[i])
{
pos=i;
break;
}
return pos;
}
B. Index Sequential Search

#include <iostream.h>
#define max 24
void createIndex(int index[],int isize,int A[],int asize)
{
int i, j;
for(i = 0, j = 0; i < asize; i+=8, j++)
{
index[j] = A[i];
}
index[j] = A[asize - 1];
}
int indexSeqSearch(int val, int index[], int isize, int A[],
int asize)
{
int i = 0, j = 0, pos = 0;
int high = 0,low = 0;
if(val > index[isize - 1] && val < index[0])
return -1;
while(i < isize)
{
if(val == index[i])
{
pos = 8 * i; // here 8 is the step size
return pos;
}
if(val < index[i])
{
low = 8 * (i - 1);
high = 8 * i;
break;
}
else
{
low = 8 * i;
high = 8 * (i + 1);
}
i++;
}
cout<<"\n low = "<< low <<"high = "<<high;
while(low < high)
// search in array from index low to high

{
if(val == A[low])
return low;
else
low++;
}
return -1;
}
int main()
{
int A[max];
int index[(max/8) + 1] = {0};
int position;
int key, i, choice;
int opt = 0, pos = 0;
cout<<"\nEnter 7 elements in array:\n";
for(i=0;i<7;i++)
cin>>A[i];
cout << "Enter number to be searched : \n";
cin >> key;
createIndex(&index[0],(max/8) + 1,&A[0], max);
pos = indexSeqSearch(key, index, (max/8) + 1, A, max);
if(pos != -1)
{
cout << "Found at position: " << pos+1;
}
else
cout << "Not found. ";
return 0;
}
C. Binary Search
#include<iostream>
int binary_search(int list[],int key,int low,int high);
int main()
{
int n,i,key,list[25],pos;
cout<<"Enter no of elements: \n" ;
cin>>n;
cout<<"Enter "<<n<<" elements in ascending order: \n";
for(i=0;i<n;i++)
cin>>list[i];
cout<<"Enter key to search: " ;
cin>>key;
pos=binary_search(list,key,0,n-1);
if(pos==-1)
cout<<"Element not found.";
else
cout<<"Element found at index."<<pos;
}
/* function for binary search*/
int binary_search(int list[],int key,int low,int high)
{
int mid,pos=-1;
while(low<=high)
{
mid=(low+high)/2;
if(key==list[mid])
{
pos=mid;
break;
}
else if(key<list[mid])
high=mid-1;
else
low=mid+1;
}
return pos;
}
Q.12 Write a Program to implement the following Sorting

Algorithms:
A. Insertion Sort
B. Selection Sort
C. Bubble Sort
D. Quick Sort
E. Merge Sort
F. Heap Sort
A. Insertion Sort
#include<iostream>
void insertion_sort(int a[],int n)
{
int i,t,pos;
for(i=0;i<n;i++)
{
t=a[i];
pos=i;
while(pos>0&&a[pos-1]>t)
{
a[pos]=a[pos-1];
pos--;
}
a[pos]=t;
}
}
int main()
{
int n,i;
int list[30];
cin>>n;
cout<<"Enter "<<n<<" numbers:\n";
for(i=0;i<n;i++)
cin>>list[i];
insertion_sort(list,n);
cout<<" After sorting :\n";
for(i=0;i<n;i++)
cout<<list[i]<<endl;
return 0;
}
B. Selection Sort
#include<iostream>
void selection_sort (int list[],int n);
int main()
{
int n,i;
int list[30];
cin>>n;
cout<<"Enter "<<n<<" numbers: \n";
for(i=0;i<n;i++)
cin>>list[i];
selection_sort (list,n);
cout<<" After sorting\n";
for(i=0;i<n;i++)
return 0;
}
void selection_sort (int list[],int n)
{
int min,temp,i,j;
for(i=0;i<n;i++)
{
min=i;
for(j=i+1;j<n;j++)
{
if(list[j]<list[min])
min=j;
}
temp=list[i];
list[i]=list[min];
list[min]=temp;
}
}
C. Bubble Sort
#include<iostream>
void bubble_sort(int list[30],int n);
int main()
{
int n,i;
int list[30];
cin>>n;
for(i=0;i<n;i++)
cin>>list[i];
bubble_sort (list,n);
for(i=0;i<n;i++)
return 0;
}
void bubble_sort (int list[30],int n)
{
int temp ;
int i,j;
for(i=0;i<n;i++)
for(j=0;j<n-1;j++)
if(list[j]>list[j+1])
{
temp=list[j];
list[j]=list[j+1];
list[j+1]=temp;
}
}
D. Quick Sort
#include<iostream>
void quicksort(int x[],int Lb,int Ub)
{
int down,up,pivot,t;
if(Lb<Ub)
{
down=Lb;
up=Ub;
pivot=down;
while(down<up)
{
while((x[down]<=x[pivot])&&(down<Ub))down++;
while(x[up]>x[pivot])up--;
if(down<up)
{
t=x[down];
x[down]=x[up];
x[up]=t;
}
}
t=x[pivot];
x[pivot]=x[up];
x[up]=t;
quicksort( x,Lb,up-1);
quicksort( x,up+1,Ub);
}
}
int main()
{
int n,i;
int list[30];
cin>>n;
for(i=0;i<n;i++)
cin>>list[i];
quicksort(list,0,n-1);
for(i=0;i<n;i++)
return 0;
}
E. Merge Sort
#include<iostream>
#define max 15
template<class T>
void merge(T a[],int l,int m,int u)
{
T b[max];
int i,j,k;
i=l; j=m+1;
k=l;
while((i<=m)&&(j<=u))
{
if(a[i]<=a[j])
{
b[k]=a[i];
++i;
}
else
{
b[k]=a[j];
++j;
}
++k;
}
if(i>m)
{
while(j<=u)
{
b[k]=a[j];
++j;
++k;
}
}
else
{
while(i<=m)
{
b[k]=a[i];
++i;
++k;
}
}
for(int r=l;r<=u;r++)
a[r]=b[r];
}
template <class T>
void mergesort(T a[],int p,int q)
{
int mid;
if(p<q)
{
mid=(p+q)/2;
mergesort(a,p,mid);
mergesort(a,mid+1,q);
merge(a,p,mid,q);
}
}
int main()
{
int n,i;
int list[30];
cin>>n;
for(i=0;i<n;i++)
cin>>list[i];
mergesort (list,0,n-1);
cout<<" After Sorting\n";
for(i=0;i<n;i++)
return 0;
}
F. Heap Sort
#include <iostream>
void heapify(int arr[], int n, int i)
{
int largest = i;
int l = 2*i + 1;
int r = 2*i + 2;
if (l < n && arr[l] > arr[largest])
largest = l;
if (r < n && arr[r] > arr[largest])
largest = r;
if (largest != i)
{
swap(arr[i], arr[largest]);
heapify(arr, n, largest);
}
}
// main function to do heap sort
void heapSort(int arr[], int n)
{
for (int i = n / 2 - 1; i >= 0; i--)
heapify(arr, n, i);
for (int i=n-1; i>=0; i--)
{
swap(arr[0], arr[i]);
heapify(arr, i, 0);
}
}
/* A utility function to print array of size n */
void printArray(int arr[], int n)
{
for (int i=0; i<n; ++i)
cout << arr[i] << " ";
cout << "\n";
}
int main()
{
int n,i;
int list[30];
cin>>n;
for(i=0;i<n;i++)
cin>>list[i];
heapSort(list, n);
cout << "Sorted array is: \n";
printArray(list, n);
return 0;
}
Q.13 Write a program to implement the Minimum Spanning Tree

using Kruskal’s and Prim’s Algorithm.
A. Kruskal’s Algorithm
#include <algorithm>
#include <iostream>
#include <vector>
#define edge pair<int, int>
class Graph {
private:
vector<pair<int, edge> > G; // graph
vector<pair<int, edge> > T; // mst
int *parent;
int V; // number of vertices/nodes in graph
public:
Graph(int V);
void AddWeightedEdge(int u, int v, int w);
int find_set(int i);
void union_set(int u, int v);
void kruskal();
void print();
};
Graph::Graph(int V) {
parent = new int[V];
//i 0 1 2 3 4 5
//parent[i] 0 1 2 3 4 5
for (int i = 0; i < V; i++)
parent[i] = i;
G.clear();
T.clear();
}
void Graph::AddWeightedEdge(int u, int v, int w) {
G.push_back(make_pair(w, edge(u, v)));
}
int Graph::find_set(int i) {
// If i is the parent of itself

if (i == parent[i])
return i;
else
// Else if i is not the parent of itself
// Then i is not the representative of his set,
// so we recursively call Find on its parent
return find_set(parent[i]);
}
void Graph::union_set(int u, int v) {

parent[u] = parent[v];
}
void Graph::kruskal() {
int i, uRep, vRep;
sort(G.begin(), G.end()); // increasing weight
for (i = 0; i < G.size(); i++) {
uRep = find_set(G[i].second.first);
vRep = find_set(G[i].second.second);
if (uRep != vRep) {
T.push_back(G[i]); // add to tree
union_set(uRep, vRep);
}
}
}
void Graph::print() {
cout << "Edge :"
<< " Weight" << endl;
for (int i = 0; i < T.size(); i++) {
cout << T[i].second.first << " - " << T[i].second.second <<
" : "
<< T[i].first;
cout << endl;
}
}
int main() {
Graph g(6);
g.AddWeightedEdge(0, 1, 4);
g.kruskal();
g.print();
return 0;
}
B. Prim’s Algorithm
#include <cstring>
#include <iostream>
#define INF 9999999
// number of vertices in graph

#define V 5
// create a 2d array of size 5x5

//for adjacency matrix to represent graph
int G[V][V] = {
{0, 9, 75, 0, 0},
{9, 0, 95, 19, 42},
{75, 95, 0, 51, 66},
{0, 19, 51, 0, 31},
{0, 42, 66, 31, 0}};
int main() {
int no_edge; // number of edge
int selected[V];
memset(selected, false, sizeof(selected));
no_edge = 0;
selected[0] = true;
int x; // row number

int y; // col number
cout << "Edge"
<< " : "
<< "Weight";
cout << endl;
while (no_edge < V - 1) {
int min = INF;
x = 0;
y = 0;
for (int i = 0; i < V; i++) {

if (selected[i]) {
for (int j = 0; j < V; j++) {
if (!selected[j] && G[i][j]) {
if (min > G[i][j]) {
min = G[i][j];
x = i;
y = j;
}
}
}
}
}
cout << x << " - " << y << " : " << G[x][y];
cout << endl;
selected[y] = true;
no_edge++;
}
return 0;
}
Q.14 Write a program to implement the TSP problem.
#include<iostream>
int ary[10][10],completed[10],n,cost=0;
void takeInput()
{
int i,j;
cout<<"Enter the number of villages: ";
cin>>n;
cout<<"\nEnter the Cost Matrix\n";
for(i=0;i < n;i++)

{
cout<<"\nEnter Elements of Row: "<<i+1<<"\n";
for( j=0;j < n;j++)

cin>>ary[i][j];
completed[i]=0;
}
cout<<"\n\nThe cost list is:";
for( i=0;i < n;i++)

{
cout<<"\n";
for(j=0;j < n;j++)

cout<<"\t"<<ary[i][j];
}
}
int least(int c)
{
int i,nc=999;
int min=999,kmin;
for(i=0;i < n;i++)

{
if((ary[c][i]!=0)&&(completed[i]==0))
if(ary[c][i]+ary[i][c] < min)
{
min=ary[i][0]+ary[c][i];
kmin=ary[c][i];
nc=i;
}
}
if(min!=999)
cost+=kmin;
return nc;
}
void mincost(int city)
{
int i,ncity;
completed[city]=1;
cout<<city+1<<"--->";
ncity=least(city);
if(ncity==999)
{
ncity=0;
cout<<ncity+1;
cost+=ary[city][ncity];
return;
}
mincost(ncity);
}
int main()
{
takeInput();
cout<<"\n\nThe Path is:\n";

mincost(0); //passing 0 because starting vertex
cout<<"\n\nMinimum cost is "<<cost;
return 0;
}
Q.15. Write a program to demonstrate:
A. DFS (Depth First Search)

B. BFS (Breadth First Search)
A. DFS
// DFS algorithm in C++

#include <iostream>
#include <list>
class Graph {
int numVertices;
list<int> *adjLists;
bool *visited;
public:
Graph(int V);
void addEdge(int src, int dest);
void DFS(int vertex);
};
// Initialize graph
Graph::Graph(int vertices) {
numVertices = vertices;
adjLists = new list<int>[vertices];
visited = new bool[vertices];
}
// Add edges
void Graph::addEdge(int src, int dest) {
adjLists[src].push_front(dest);
}
// DFS algorithm
void Graph::DFS(int vertex) {
visited[vertex] = true;
list<int> adjList = adjLists[vertex];
cout << vertex << " ";
list<int>::iterator i;
for (i = adjList.begin(); i != adjList.end(); ++i)
if (!visited[*i])
DFS(*i);
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 3);
g.DFS(2);
return 0;
}
B. BFS
// BFS algorithm in C++
#include <iostream>
#include <list>
class Graph {
int numVertices;
list<int>* adjLists;
bool* visited;
public:
Graph(int vertices);
void addEdge(int src, int dest);
void BFS(int startVertex);
};
// Create a graph with given vertices,

// and maintain an adjacency list
Graph::Graph(int vertices) {
numVertices = vertices;
adjLists = new list<int>[vertices];
}
// Add edges to the graph

void Graph::addEdge(int src, int dest) {
adjLists[src].push_back(dest);
adjLists[dest].push_back(src);
}
// BFS algorithm
void Graph::BFS(int startVertex) {
visited = new bool[numVertices];
for (int i = 0; i < numVertices; i++)
visited[i] = false;
list<int> queue;
visited[startVertex] = true;
queue.push_back(startVertex);+
list<int>::iterator i;
while (!queue.empty()) {
int currVertex = queue.front();
cout << "Visited " << currVertex << " ";
queue.pop_front();
for (i = adjLists[currVertex].begin(); i !=
adjLists[currVertex].end(); ++i) {
int adjVertex = *i;
if (!visited[adjVertex]) {
visited[adjVertex] = true;
queue.push_back(adjVertex);
}
}
}
}
int main() {
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(1, 2);
g.addEdge(2, 0);
g.addEdge(2, 3);
g.addEdge(3, 3);
g.BFS(2);
return 0;
}
Q.16 Write a Program to implement Dijasktra's Algorithm.
#include<iostream>
#include<stdio.h>
#define INFINITY 9999
#define max 5
void dijkstra(int G[max][max],int n,int startnode);
int main() {
int
G[max][max]={{0,1,0,3,10},{1,0,5,0,0},{0,5,0,2,1},{3,0,2,0,6},{1
0,0,1,6,0}};
int n=5;
int u=0;
dijkstra(G,n,u);
return 0;
}
void dijkstra(int G[max][max],int n,int startnode) {
int cost[max][max],distance[max],pred[max];
int visited[max],count,mindistance,nextnode,i,j;
for(i=0;i<n;i++)
for(j=0;j<n;j++)
if(G[i][j]==0)
cost[i][j]=INFINITY;
else
cost[i][j]=G[i][j];
for(i=0;i<n;i++) {
distance[i]=cost[startnode][i];
pred[i]=startnode;
visited[i]=0;
}
distance[startnode]=0;
visited[startnode]=1;
count=1;
while(count<n-1) {
mindistance=INFINITY;
for(i=0;i<n;i++)
if(distance[i]<mindistance&&!visited[i]) {
mindistance=distance[i];
nextnode=i;
}
visited[nextnode]=1;
for(i=0;i<n;i++)
if(!visited[i])
if(mindistance+cost[nextnode][i]<distance[i]) {
distance[i]=mindistance+cost[nextnode][i];
pred[i]=nextnode;
}
count++;
}
for(i=0;i<n;i++)
if(i!=startnode) {
cout<<"\nDistance of node"<<i<<"="<<distance[i];
cout<<"\nPath="<<i;
j=i;
do {
j=pred[j];
cout<<"<-"<<j;
}while(j!=startnode);
}
}

DSA Lab Record

Uploaded by

Copyright:

Available Formats

DSA Lab Record

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DSA Lab Record

Uploaded by

Copyright:

Available Formats

Go to Index Page 2 of 89

1 Write a Program to implement a stack using array 3

2 Write a Program to implement a stack using linked list 6

3 Write a Program to implement a queue using array 9

4 Write a Program to implement a queue using linked list 13

5 Write a Program to implement a circular queue using array 17

6 Write a Program to implement a simple linked list 21

7 Write a Program to implement a circular linked list 28

8 Write a Program to implement a doubly linked list 38

9 Write a Program to count a node in linked list 46

10 Write a Program to implement a reversed a linked list 51

11 Write a Program to implement the following Searching Algorithms:

12 Write a Program to implement the following Sorting Algorithms:

13 Write a program to implement the Minimum Spanning Tree using

14 Write a program to implement the TSP problem. 82

15 Write a Program to implement DFS & BFS 85

16 Write a Program to implement Dijkstra's Algorithm 91

Q.1 Write a Program to implement a stack using arrays.

Q.2 Write a Program to implement a stack using a linked list.

void Stack::Push(int Element){

Q.3 Write a Program to implement a queue using array.

Q. 4. Write a Program to implement a queue using linked list.

template <class T>

Q. 5. Write a Program to implement a circular queue using array.

void AddinQueue(int val) {

int choice, data;

Q. 6 Write a Program to implement a simple linked list.

node * createNode(int n);

//create standalone node in memory

//Add element at first position

//Add element at last position

//Display full list

cout<<"\n 6 - Delete node from last position";

cout<<"\n Enter value of element : ";

Q. 7 Write a Program to implement a circular linked list.

if (s->info == value) /*First Element Deletion*/

Q. 8 Write a Program to implement a doubly linked list.

cout<<"\n\n 1 is for insert at position";

void DList :: Insert_Pos(DLL_Node* NewNode, int pos)

Q. 9 Write a Program to count a node in the linked list.

node * createNode(int n);

//create standalone node in memory

//Add element at specified position

//Add element at first position

//Add element at last position

cout<<"\n 1 - Insert node at first position";

Q. 10 Write a Program to implement a reversed a linked list.

/* Function to insert nodes in a linked list. */

/* Function to reverse the nodes in a linked list. */

/* Function to print the nodes in a linked list. */

/* Driver function to check the above algorithm. */

Q.11. Write a Program to implement the following Searching

/*function for linear search*/

B. Index Sequential Search

// search in array from index low to high

Q.12 Write a Program to implement the following Sorting

Q.13 Write a program to implement the Minimum Spanning Tree

#define edge pair<int, int>

// If i is the parent of itself

if (s->info == value) /First Element Deletion/

/function for linear search/