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

Go to Index Page 3 of 89

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
Go to Index Page 4 of 89

{
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;
}
Go to Index Page 5 of 89
Go to Index Page 6 of 89

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;
Go to Index Page 7 of 89

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";
Go to Index Page 8 of 89

break;
case 3:
cout<<"Top of Stack : "<<S.GetTop()<<"\n";
break;
}
}while(choice<4);
return 0;
}
Go to Index Page 9 of 89

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

#include<iostream.h>
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
Go to Index Page 10 of 89

{
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";
cout<<"\n 4 - Exit";
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;
}
Go to Index Page 11 of 89
Go to Index Page 12 of 89

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

#include<stdlib.h>
#include<iostream.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
Go to Index Page 13 of 89

{
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;
}
Go to Index Page 14 of 89

}
}
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;
}
Go to Index Page 15 of 89
Go to Index Page 16 of 89

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;
Go to Index Page 17 of 89

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) {
cout<<Queue[f]<<" ";
f++;
}
f = 0;
while (f <= r) {
cout<<Queue[f]<<" ";
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:
Go to Index Page 18 of 89

deleteCQ();
break;

case 3:
displayCQ();
break;

case 0:
cout<<"Exit\n";
break;
default: cout<<"Incorrect!\n";
}
} while(choice != 0);
return 0;
}
Go to Index Page 19 of 89
Go to Index Page 20 of 89

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

#include<iostream.h>
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)
{
Go to Index Page 21 of 89

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)
Go to Index Page 22 of 89

{
if(curr->link==NULL)
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=createNode(value);
temp->link=head;
head=temp;
}
else
{
temp=createNode(value);
while(counter<pos)
{
if(curr->link==NULL)
break;

curr=curr->link;
counter++;
}
if(counter==pos)

{
temp->link=curr->link;
Go to Index Page 23 of 89

curr->link=temp;
}
else
cout<<"Position not found";
}
}

//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)
{
if(curr->link==NULL)
break;
curr=curr->link;
}
curr->link=temp;
}
}

//Display full list

void create::disp()
{
node *d=head;
cout<<"\n";
Go to Index Page 24 of 89

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";
cout<<"\n 0 - Exit";
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;
cout<<"\n Enter value of element : ";
cin>>element;
L1.addAtPosition(pos,element);
break;
case 3:
Go to Index Page 25 of 89

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

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;
}
Go to Index Page 26 of 89
Go to Index Page 27 of 89

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

#include <stdio.h>
#include<iostream.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;
Go to Index Page 28 of 89

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:
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:
cout<<"Enter the element for deletion: ";
cin>>element;
Go to Index Page 29 of 89

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;
}
Go to Index Page 30 of 89

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)
Go to Index Page 31 of 89

{
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;
}
Go to Index Page 32 of 89

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;
Go to Index Page 33 of 89

if (last == NULL)
{
cout<<"List Empty!! Can't search"<<endl;
return;
}
else
{
s = last->next;
while (s != last)
{
counter++;
if (s->info == value)
{
cout<<"Element "<<value;
cout<<" found at position "<<counter<<endl;
return;
}
s = s->next;
}
}
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()
{
node *s;
if (last == NULL)
{
cout<<"List is empty, nothing to display"<<endl;
return;
}
Go to Index Page 34 of 89

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;
}
Go to Index Page 35 of 89

/*
* 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;
}
}
Go to Index Page 36 of 89
Go to Index Page 37 of 89

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

#include<iostream.h>

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)
Go to Index Page 38 of 89

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

}
Go to Index Page 39 of 89

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;
Go to Index Page 40 of 89

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;
Go to Index Page 41 of 89

}
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->pre)->next=temp->next;
(temp->next)->pre=temp->pre;
}
//release memory
Go to Index Page 42 of 89

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)
{
(temp->pre)->next=temp->next;
}
Go to Index Page 43 of 89

else
{
(temp->pre)->next=temp->next;
(temp->next)->pre=temp->pre;
}
//release memory
delete temp;
}
else
cout<<"\n Oops! Node not found";
}
}
Go to Index Page 44 of 89
Go to Index Page 45 of 89

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

#include<iostream.h>
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;
Go to Index Page 46 of 89

node *temp;
curr=head;
if(head==NULL)
{
temp=createNode(value);
head=temp;
}
else if(pos==1)
{
temp=createNode(value);
temp->link=head;
head=temp;
}
else
{
temp=createNode(value);
while(counter<pos)
{
if(curr->link==NULL)
break;

curr=curr->link;
counter++;

}
if(counter==pos)

{
temp->link=curr->link;
curr->link=temp;
}
else
cout<<"Position not found";
}
}

//Add element at first position

void create::addAtFirst(int n)
{
node * temp;
temp=createNode(n);
Go to Index Page 47 of 89

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)
{
if(curr->link==NULL)
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;
Go to Index Page 48 of 89

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";
cout<<"\n 0 - Exit";
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;
cout<<"\n Enter value of element : ";
cin>>element;
L1.addAtPosition(pos,element);
break;
case 3:
cout<<"\n Enter value of element : ";
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;
}
Go to Index Page 49 of 89
Go to Index Page 50 of 89

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

#include<iostream.h>

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;
}
Go to Index Page 51 of 89

/* 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;
}
Go to Index Page 52 of 89

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;
}
Go to Index Page 53 of 89
Go to Index Page 54 of 89

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)
Go to Index Page 55 of 89

// 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;
}
Go to Index Page 56 of 89
Go to Index Page 57 of 89

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;
}
Go to Index Page 58 of 89
Go to Index Page 59 of 89

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];
cout<<"Enter no of elements: \n";
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;
Go to Index Page 60 of 89

return 0;
}
Go to Index Page 61 of 89

B. Selection Sort

#include<iostream>
void selection_sort (int list[],int n);
int main()
{
int n,i;
int list[30];
cout<<"Enter no of elements: \n";
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++)
cout<<list[i]<<endl;
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;
}
}
Go to Index Page 62 of 89
Go to Index Page 63 of 89

C. Bubble Sort

#include<iostream>
using namespace std;
void bubble_sort(int list[30],int n);
int main()
{
int n,i;
int list[30];
cout<<"Enter no of elements: \n";
cin>>n;
cout<<"Enter "<<n<<" numbers: \n";
for(i=0;i<n;i++)
cin>>list[i];
bubble_sort (list,n);
cout<<" After sorting\n";
for(i=0;i<n;i++)
cout<<list[i]<<endl;
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;
}
}
Go to Index Page 64 of 89
Go to Index Page 65 of 89

D. Quick Sort

#include<iostream>
using namespace std;
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];
cout<<"Enter no of elements: \n";
cin>>n;
cout<<"Enter "<<n<<" numbers: \n";
for(i=0;i<n;i++)
Go to Index Page 66 of 89

cin>>list[i];
quicksort(list,0,n-1);
cout<<" After sorting\n";
for(i=0;i<n;i++)
cout<<list[i]<<endl;
return 0;
}
Go to Index Page 67 of 89
Go to Index Page 68 of 89

E. Merge Sort
#include<iostream>
using namespace std;
#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];
Go to Index Page 69 of 89

++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];
cout<<"Enter no of elements: \n";
cin>>n;
cout<<"Enter "<<n<<" numbers: \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++)
cout<<list[i]<<endl;
return 0;
}
Go to Index Page 70 of 89
Go to Index Page 71 of 89

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];
cout<<"Enter no of elements: \n";
Go to Index Page 72 of 89

cin>>n;
cout<<"Enter "<<n<<" numbers: \n";
for(i=0;i<n;i++)
cin>>list[i];
heapSort(list, n);
cout << "Sorted array is: \n";
printArray(list, n);
return 0;
}
Go to Index Page 73 of 89
Go to Index Page 74 of 89

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>
using namespace std;

#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) {
Go to Index Page 75 of 89

// 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.AddWeightedEdge(0, 2, 4);
g.AddWeightedEdge(1, 2, 2);
g.AddWeightedEdge(1, 0, 4);
Go to Index Page 76 of 89

g.AddWeightedEdge(2, 0, 4);
g.AddWeightedEdge(2, 1, 2);
g.AddWeightedEdge(2, 3, 3);
g.AddWeightedEdge(2, 5, 2);
g.AddWeightedEdge(2, 4, 4);
g.AddWeightedEdge(3, 2, 3);
g.AddWeightedEdge(3, 4, 3);
g.AddWeightedEdge(4, 2, 4);
g.AddWeightedEdge(4, 3, 3);
g.AddWeightedEdge(5, 2, 2);
g.AddWeightedEdge(5, 4, 3);
g.kruskal();
g.print();
return 0;
}
Go to Index Page 77 of 89

B. Prim’s Algorithm

#include <cstring>
#include <iostream>
using namespace std;

#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;
Go to Index Page 78 of 89

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;
}
Go to Index Page 79 of 89

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++)

Go to Index Page 80 of 89

{
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;
}
Go to Index Page 81 of 89
Go to Index Page 82 of 89

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>
using namespace std;

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];
Go to Index Page 83 of 89

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;
}
Go to Index Page 84 of 89

B. BFS

// BFS algorithm in C++

#include <iostream>
#include <list>

using namespace std;

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;
Go to Index Page 85 of 89

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;
}
Go to Index Page 86 of 89
Go to Index Page 87 of 89

Q.16 Write a Program to implement Dijasktra's Algorithm.

#include<iostream>
#include<stdio.h>
using namespace std;
#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];
Go to Index Page 88 of 89

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);
}
}
Go to Index Page 89 of 89