Data Structures using C++

1. Write programs to implement the following using an array: a) Stack ADT b) Queue
ADT.
A) Write a program to implement stack using array ( Stack ADT)
#include <iostream.h>
class Stack
{
private:
int stack [50];
int MaxCapacity;
int top;
public:
Stack()
{
MaxCapacity = 50;
top = -1;
}
int getTop();
int pop();
void push(int Element);
int Empty();
int CurrSize();
int IsFull();
};
int Stack :: getTop()
{
if(!Empty())
return(stack [top]);
else
return 0;
}
int Stack :: pop()
{
if(!Empty())
return(stack [top - -]);
else
return 0;
}
int Stack :: Empty()
{
if(top == -1)
return 1;
else
return 0;
}
int Stack :: IsFull()
{
if(top == MaxCapacity - 1)
return 1;
else
return 0;
}
int Stack :: CurrSize()
{
return(top + 1);
}
void Stack :: push(int Element)
{
 if(!IsFull())
stack [++top] = Element;
}
void main()
{
Stack S;
[Link]();
[Link](1);
[Link](2);
cout << [Link]() << endl;
cout << [Link]() << endl;
cout << [Link]() << endl;
}
Output:

2
2
1
(B) Write a program to implement Queue using array (Queue ADT)
#include <iostream.h>
class Queue
{
private:
int Rear, Front;
int Q[50];
int max;
int Size;
public:
Queue()
{
Size = 0;
max = 50;
Rear = Front = -1 ;
}
int Empty();
int IsFull();
void Add(int Element);
int Delete();
int getFront();
};
int Queue :: Empty()
{
if(Front == Rear)
return 1;
else
return 0;
}
int Queue :: IsFull()
{
if(Rear == max - 1)
return 1;
else
return 0;
}
void Queue :: Add(int Element)
{
if(!IsFull())
Q[++Rear] = Element;
Size++;
}
int Queue :: Delete()
{
if(!Empty())
{
Size--;
return(Q[++Front]);
}
else
return -1;
}
int Queue :: getFront()
{
if(!Empty())
return(Q[Front + 1]);
else
return -1;
}
void main( )
{
Queue Q1;
[Link](11);
[Link](12);
[Link](13);
cout << [Link]() << endl;
[Link](14);
cout << [Link]() << endl;
cout << [Link]() << endl;
cout << [Link]() << endl;
cout << [Link]() << endl;
[Link](15);
[Link](16);
cout << [Link]() << endl;
}
Output:
11
12
13
14
-1
15
2. Write a program to convert the given infix expression to postfix expression using stack.

#include<iostream.h>
#include<conio.h>
#include<string.h>
#define Max 20

class Stack
{
char stack[Max]; // array of characters
int top;
public:
Stack() // constructor to initialize top
{
top = -1;
}
int isempty(); // function to check empty condition
int isfull(); // function to check full condition
void push(char ch); // to push a character into stack
char pop(); // function to pop a character from stack
char getTop(); // function to get the top element of stack

};

int Stack::isempty()

if(top == -1)

return 1;

else

return 0;

int Stack::isfull()

if(top == Max - 1)

return 1;

else
return 0;

void Stack::push(char ch)

if(isfull())

cout << "\nStack full";

else

top++;

stack[top] = ch;

char Stack::pop()

char ch;

if(isempty())

cout << "\n stack empty \n";

else

ch = stack[top];

top--;

return(ch);

}
char Stack::getTop()

char ch;

if(isempty())

cout << "\n stack empty \n";

else

ch = stack[top];

return(ch);

// Function to get in-stack priority

char isp(char ch)

switch(ch)

case '+':

case '-':return 1;

case '*':

case '/':return 2;

case '^':return 3;

case '(':return 0;

case '#':return -2;

}
return 0;
}

// Function to get incoming priority

char icp(char ch)

switch(ch)

case '+':

case '-':return 1;
case '*':
case '/':return 2;
case '^':return 3;
case '(':return 4;
}
return 0;

void intopost(char infix[20])

{
int i = 0;
char ch, x;
Stack s;
[Link]('#');
while(infix[i]!= '\0')
//extract character till end of expression
{
ch = infix[i];
i++;
if(ch >= 'a' && ch <= 'z') // operand
{
cout << ch;
}
else // operator
{
if(ch == '(')
{
while([Link]()!= '(')
{
x = [Link]();
cout << x;
}
x = [Link]();
}
else
{
while(isp([Link]()) >= icp(ch))
{
x = [Link]();
cout << x;
}
[Link](ch);
}
}
}
while(![Link]())
{
x = [Link]();
if(x != '#')
cout<<x;
}
}
void main()
{

char infix[20], postfix[20];

cout << "\nEnter the infix expression:";

cin >> infix;

intopost(infix);

Output:

Enter the Infix expression : a+b

ab+
3 Write a program to evaluate a postfix expression using stack.
#include <iostream.h>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
const int MAX = 50;
class postfix
{
private :
int stack[MAX] ;
int top, nn ;
char s;
public :
postfix( ) ;
void push(int item);
int pop( ) ;
void calculate(char ch[]) ;
void show( ) ;
};
postfix :: postfix( )
{
top = -1 ;
}
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 0 ;
}
int data = stack[top] ;
top-- ;
return data ;
}
void postfix :: calculate(char ch[MAX])
{
int n1, n2, n3,i=0;
while (ch[i]!='\0')
{
s=ch[i];
i++;
if ( s == ' ' || s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( s ) )
{
 nn = s - '0' ;
push ( nn ) ;
}
else
{
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 ;
default :
cout << "Unknown operator" ;
exit ( 1 ) ;
}
push ( n3 ) ;
 }
s++ ;
}
}
void postfix :: show( )
{
nn = pop ( ) ;
cout << "Result is: " << nn ;
}
int main( )
{
char expr[MAX] ;
cout << "\nEnter postfix expression to be evaluated : " ;
[Link] ( expr, MAX ) ;
postfix q ;
[Link](expr) ;
[Link]( ) ;
}

Output:
Enter postfix expression to be evaluated: 5 4 +
Result is: 9
4 Write a program to ensure the parentheses are nested correctly in arithmetic
expression.
#include <iostream.h>
#include <conio.h>
#include <string.h>
#define Max 20
//class Stack
class Stack
{
char stack[Max]; // array of characters
int top;
public:
Stack() // constructor to initialize top
{
top = -1;
}
int isempty(); // function to check empty condition
int isfull(); // function to check full condition
void push(char ch); // to push a character into stack
char pop(); // function to pop a character from stack
char getTop(); // function to get the top element of stack
};

int Stack::isempty()
{
if(top == -1)
return 1;
else
return 0;
}

int Stack::isfull()
{
if(top == Max - 1)
return 1;
else
return 0;
}

void Stack::push(char ch)

{
if(isfull())
cout << "\nStack full";
else
{
top++;
stack[top] = ch;
}
}
char Stack::pop()
{
char ch;
if(isempty())
cout << "\n stack empty \n";
else
{
ch = stack[top];
top--;
}
return(ch);
}
char Stack::getTop()
{
char ch;
if(isempty())
cout << "\n stack empty \n";
else
{
ch = stack[top];
}
return(ch);
}
void main()
{
int i,top;
Stack s;
char c[30], a, y, z,ch;
cout<<"Enter the expression:\n";
cin>>c;
for (i = 0; i < strlen(c); i++)
{
if ((c[i] == '(') || (c[i] == '{') || (c[i] == '['))
{ ch=c[i];
[Link](ch);
}
else
{
switch(c[i])
{
case ')':
a =[Link]();
if ((a == '{') || (a == '['))
{
cout<<"invalid expr!!";
getch();
 }
break;
case '}':
y =[Link]();
if ((y == '[') || (y == '('))
{
cout<<"invalid expr!!";
getch();
}
break;
case ']':
z =[Link]();
if ((z == '{') || (z == '('))
{
cout<<"invalid expr!!";
getch();
}
break;
}
}
}
if ([Link]())
{
cout<<"balanced expr!!";
}
else
{
cout<<"string is not valid.!!";
}
getch();

Output:
Enter the expression:
{s}
balanced expr!!
 5 Write a program to find following using Recursion

a) Factorial of +ve Integer

b) nth term of the Fibonacci Sequence
c) GCD of two +ve integers
(a)
#include<iostream.h>
int Factorial(int n);
int main()
{
int n;
cout << "Enter a positive integer: ";
cin >> n;
cout << "Factorial of " << n << " = " << Factorial(n);
return 0;
}
int Factorial(int n)
{
if(n == 1) // end condition
return 1;
else
return Factorial(n - 1) * n;
}

Output:

Enter a positive integer: 6

Factorial of 6 = 720
(b)
#include<iostream.h>
int Fib(int n);
int main()
{
int n,i=0;
cout<<"Input the number of terms for Fibonacci Series:";
cin>>n;
cout<<"\nFibonacci Series is as follows\n";
while(i<n)
{
cout<<" "<<Fib(i);
i++;
}
return 0;
}
int Fib(int n)
{
if(n == 1 ||n == 0)
return (n);
else
return(Fib(n - 1) + Fib(n - 2));
}
Output:
Input the number of terms for Fibonacci Series: 5
Fibonacci Series is as follows
01123
(c)
#include<iostream.h>
int gcd(int n,int m);
int gcd(int n,int m)
{
if((n>=m)&&((n%m)==0))
return(m);
else
return gcd(m,(n%m));
}
int main()
{
int n,m,result;
cout<<"Input the first integer number:";
cin>>n;
cout<<"Input the second integer number:";
cin>>m;
result=gcd(n,m);
cout<<"GCD of "<<n<<" and "<<m<<" is :"<<result;
return 0;
}
Output:
Input the first integer number : 4
Input the second integer number: 6
GCD of 4 and 6 is 2
6 Write a program to create a single linked list and write functions to implement
the following operations.
a) Insert an element at a specified position
b) Delete a specified element in the list
c) Search for an element and find its position in the list
d) Sort the elements in the list ascending order

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

/*
* Node Declaration
*/
struct node
{
int info;
struct node *next;
}*start;

/*
* Class Declaration
*/
class single_llist
{
public:
node* create_node(int);
void insert_begin();
void insert_pos();
void insert_last();
void delete_pos();
void sort();
void search();
void display();
single_llist()
{
start = NULL;
}
};

/*
* Main :contains menu
*/
main()
{
int choice, nodes, element, position, i;
single_llist sl;
start = NULL;
while (1)
{
cout<<endl<<"---------------------------------"<<endl;
cout<<endl<<"Operations on singly linked list"<<endl;
cout<<endl<<"---------------------------------"<<endl;
cout<<"[Link] Node at beginning"<<endl;
cout<<"[Link] node at last"<<endl;
cout<<"[Link] node at position"<<endl;
cout<<"[Link] Link List"<<endl;
cout<<"[Link] a Particular Node"<<endl;
cout<<"[Link] Element"<<endl;
cout<<"[Link] Linked List"<<endl;
cout<<"[Link] "<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
cout<<"Inserting Node at Beginning: "<<endl;
sl.insert_begin();
cout<<endl;
break;
case 2:
cout<<"Inserting Node at Last: "<<endl;
sl.insert_last();
cout<<endl;
break;
case 3:
cout<<"Inserting Node at a given position:"<<endl;
sl.insert_pos();
cout<<endl;
break;
case 4:
cout<<"Sort Link List: "<<endl;
[Link]();
cout<<endl;
break;
case 5:
cout<<"Delete a particular node: "<<endl;
sl.delete_pos();
break;
case 6:
cout<<"Search element in Link List: "<<endl;
[Link]();
cout<<endl;
 break;
case 7:
cout<<"Display elements of link list"<<endl;
[Link]();
cout<<endl;
break;
case 8:
cout<<"Exiting..."<<endl;
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}
}

/*
* Creating Node
*/
node *single_llist::create_node(int value)
{
struct node *temp, *s;
temp = new(struct node);
if (temp == NULL)
{
cout<<"Memory not allocated "<<endl;
return 0;
}
else
{
temp->info = value;
temp->next = NULL;
return temp;
}
}

/*
* Inserting element in beginning
*/
void single_llist::insert_begin()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *p;
temp = create_node(value);
if (start == NULL)
{
start = temp;
start->next = NULL;
 }
else
{
p = start;
start = temp;
start->next = p;
}
cout<<"Element Inserted at beginning"<<endl;
}

/*
* Inserting Node at last
*/
void single_llist::insert_last()
{
int value;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s;
temp = create_node(value);
s = start;
while (s->next != NULL)
{
s = s->next;
}
temp->next = NULL;
s->next = temp;
cout<<"Element Inserted at last"<<endl;
}

/*
* Insertion of node at a given position
*/
void single_llist::insert_pos()
{
int value, pos, counter = 0;
cout<<"Enter the value to be inserted: ";
cin>>value;
struct node *temp, *s, *ptr;
temp = create_node(value);
cout<<"Enter the postion at which node to be inserted: ";
cin>>pos;
int i;
s = start;
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos == 1)
 {
if (start == NULL)
{
start = temp;
start->next = NULL;
}
else
{
ptr = start;
start = temp;
start->next = ptr;
}
}
else if (pos > 1 && pos <= counter)
{
s = start;
for (i = 1; i < pos; i++)
{
ptr = s;
s = s->next;
}
ptr->next = temp;
temp->next = s;
}
else
{
cout<<"Positon out of range"<<endl;
}
}

/*
* Sorting Link List
*/
void single_llist::sort()
{
struct node *ptr, *s;
int value;
if (start == NULL)
{
cout<<"The List is empty"<<endl;
return;
}
ptr = start;
while (ptr != NULL)
{
for (s = ptr->next;s !=NULL;s = s->next)
{
if (ptr->info > s->info)
{
value = ptr->info;
 ptr->info = s->info;
s->info = value;
}
}
ptr = ptr->next;
}
}

/*
* Delete element at a given position
*/
void single_llist::delete_pos()
{
int pos, i, counter = 0;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the position of value to be deleted: ";
cin>>pos;
struct node *s, *ptr;
s = start;
if (pos == 1)
{
start = s->next;
}
else
{
while (s != NULL)
{
s = s->next;
counter++;
}
if (pos > 0 && pos <= counter)
{
s = start;
for (i = 1;i < pos;i++)
{
ptr = s;
s = s->next;
}
ptr->next = s->next;
}
else
{
cout<<"Position out of range"<<endl;
}
free(s);
cout<<"Element Deleted"<<endl;
 }
}

/*
* Searching an element
*/
void single_llist::search()
{
int value, pos = 0;
//bool flag = false;
if (start == NULL)
{
cout<<"List is empty"<<endl;
return;
}
cout<<"Enter the value to be searched: ";
cin>>value;
struct node *s;
s = start;
while (s != NULL)
{
pos++;
if (s->info == value)
{
//flag = true;
cout<<"Element "<<value<<" is found at position "<<pos<<endl;
}
s = s->next;
}
//if (!flag)
// cout<<"Element "<<value<<" not found in the list"<<endl;
}

/*
* Display Elements of a link list
*/
void single_llist::display()
{
struct node *temp;
if (start == NULL)
{
cout<<"The List is Empty"<<endl;
return;
}
temp = start;
cout<<"Elements of list are: "<<endl;
while (temp != NULL)
{
cout<<temp->info<<"->";
temp = temp->next;
 }
cout<<"NULL"<<endl;
}
Output:
7 Write a program to create a double linked list and write functions to
implement the following operations.
a) Insert an element at a specified position
b) Delete a specified element in the list
c) Search for an element and find its position in the list
d) Sort the elements in the list ascending order
#include<iostream.h>
#include<stdlib.h> //for exit(1)
#include<conio.h>
#define MAX 10

struct node{
int data;
struct node *lptr;
struct node *rptr;
};

class dbllist{
node *head;
public:
dbllist(){
head=NULL;
}
void create(); //initial data assignment
void display(int); //process is display (assumed)
int count(int);
void insert();
void del();
void search();
void sort();
};

void dbllist :: create(){

node *start=NULL,*newl=NULL,*end=NULL;
int takedata;
clrscr();
cout<<"\n\t\t*****Create List*****\n";
while(1){
cout<<"\t\t-999 to Quit\n";
cout<<"\t\tEnter data : ";
cin>>takedata;
if(takedata == -999)
break;
else{
//create memory for new node
 newl = new node;
if(newl == NULL){
cout<<"\n\t\tNot Enough Memory";
getch();
exit(1);
}
newl->data = takedata;
newl->lptr = NULL;
newl->rptr = NULL;

//check for first node

if(start == NULL){
start->rptr = newl;
newl->lptr = start;
start = newl;
}
else{
end->rptr = newl;
newl->lptr = end;
}
end = newl;
}//end else
}//end while

head->rptr = start;
start->lptr = head;
head = start;
}

void dbllist :: display(int check){

node *tmp=NULL;

cout<<"\n\t\t*****Display*****\n";
cout<<"\t\t";
if(check==1){ //forward display
for(tmp=head; tmp!=NULL; tmp=tmp->rptr){
cout<<tmp->data;
if(tmp->rptr != NULL)
cout<<"-->";
}//end for
}
else{ //Reverse display
for( tmp=head; tmp->rptr!=NULL; tmp=tmp->rptr);//points to last node
while(tmp!=NULL)
{
cout<<tmp->data;
if(tmp->lptr != NULL)
cout<<"-->";
tmp = tmp->lptr;
}//end whiile
 }//end if
getch();
}

int dbllist :: count(int check){

node *tmp=NULL;
int cnt;

for(tmp=head,cnt=0 ; tmp!=NULL; tmp=tmp->rptr,cnt++);//do nothing

if(check==1){
cout<<"\n\t\t*****Status of List*****\n";
cout<<"\t\tTotal Items : "<<cnt;
getch();
return(cnt);
}
else
return(cnt); //To use count value in other functions
}

void dbllist :: insert(){

node *newl=NULL,*tmp=NULL,*prev=NULL,*next=NULL;
int choice,takedata,pos,i;
while(1){
clrscr();
cout<<"\n\t\t*****Insertion*****\n";
cout<<"\t\t1) Begining\n";
cout<<"\t\t2) In Between\n";
cout<<"\t\t3) End\n";
cout<<"\t\t4) Return to Main Menu\n";
cout<<"\t\tEnter your choice : ";
cin>>choice;
if(choice==1 || choice==2 || choice==3){
//create memory for new node
newl = new node;
if(newl == NULL){
cout<<"\n\t\tNot Enough Memory";
getch();
exit(1);
}
cout<<"\n\t\tEnter data : ";
cin>>takedata;
newl->data = takedata;
newl->lptr = NULL;
newl->rptr = NULL;
}
else return;

switch(choice){
case 1 : newl->rptr = head;
 head->lptr = newl;
head = newl;
break;

case 2 : cout<<"\n\t\tEnter Position : ";

cin>>pos;
if(pos <=1 || pos >= count(2)){
cout<<"\n\t\tInvalid Position";
getch();
break;
}
else{
//to points to previous node from where//to insert
for(i=1,prev=head; i < (pos-1); prev=prev->rptr,i++);

next = prev->rptr;
newl->rptr = next;
next->lptr = newl;
newl->lptr = prev;
prev->rptr = newl;
break;
}
case 3 : //For pointing to last node
for(tmp=head; tmp->rptr != NULL; tmp=tmp->rptr);

tmp->rptr = newl;
newl->lptr = tmp;
}//end switch
}//end while
}

void dbllist :: del(){

node *delnode=NULL,*tmp=NULL,*prev=NULL,*next=NULL;
int choice,deldata,pos,i;
while(1){
clrscr();
cout<<"\n\t\t*****Deletion*****\n";
cout<<"\t\t1) Begining\n";
cout<<"\t\t2) In Between\n";
cout<<"\t\t3) End\n";
cout<<"\t\t4) Return to Main Menu\n";
cout<<"\t\tEnter your choice : ";
cin>>choice;
switch(choice){
case 1 : delnode = head;
head = head->rptr;
head->lptr = NULL;
break;
 case 2 : cout<<"\n\t\tEnter Position : ";
cin>>pos;
if(pos <=1 || pos >= count(2)){
cout<<"\n\t\tInvalid Position";
getch();
break;
}
else{
//to points to previous node from where//to insert
for(i=1,prev=head; i < (pos-1); prev=prev->rptr,i++);

next=prev->rptr->rptr;
delnode = prev->rptr;
prev->rptr = prev->rptr->rptr;
next->lptr = prev;
break;
}
case 3 : //For pointing to last node
for(tmp=head; tmp->rptr->rptr != NULL; tmp=tmp->rptr);
delnode = tmp->rptr;
tmp->rptr = NULL;
break;
case 4 : return;
default : cout<<"\n\t\tInvalid Position";
getch();
}//end switch
delete(delnode);
}//end while
}

void dbllist :: search(){

node *tmp=NULL;
int item,n;
cout<<"\n\t\t*****Search*****\n";
cout<<"\t\tEnter data to be searched : ";
cin>>item;
for(tmp=head,n=1; tmp!=NULL; tmp=tmp->rptr,n++){
if(tmp->data == item){
cout<<"\n\t\tSearch is located at "<<n<<" location";
getch();
return;
}
}
cout<<"\n\t\tSearch Not Found";
getch();
}
void dbllist :: sort(){
node *i,*j;
int tmp;
cout<<"\n\t\t*****Sort*****\n";
for(i=head;i!=NULL;i=i->rptr){
for(j=i;j!=NULL;j=j->rptr){
if(i->data > j->data){
tmp = i->data;
i->data = j->data;
j->data = tmp;
}
}
}
cout<<"\n\t\tAfter Sort...";
cout<<"\n\n\t\t==List==";
display(1);
}

void main()
{
int choice;
dbllist obj;
while(1){
clrscr();
cout<<"\n\t\tDOUBLY LINK-LIST OPERATIONS\n\n";
cout<<"\t\t1) Create List\n";
cout<<"\t\t2) Display List\n";
cout<<"\t\t3) List Status\n";
cout<<"\t\t4) List Insertion\n";
cout<<"\t\t5) List Deletion\n";
cout<<"\t\t6) Search List\n";
cout<<"\t\t7) Display Reverse List\n";
cout<<"\t\t8) Sort List\n";
cout<<"\t\t9) Exit\n";
cout<<"\t\tEnter your Choice : ";
cin>>choice;
switch(choice){
case 1 : [Link](); // 1 for A list
break;
case 2 : [Link](1);// 1 for A list
break;
case 3 : choice = [Link](1);
//choice value is not used anywhere//it is just a placeholder
break;
case 4 : [Link]();
break;
case 5 : [Link]();
break;
case 6 : [Link]();
 break;
case 7 : [Link](2);
break;
case 8 : [Link]();
break;
case 9 : goto out;
default: cout<<"\n\n\t\tInvalid Choice\n\n";
getch();
break;
}
}
out:
}

Output:
8 Write a program to create singular circular linked lists and function to
implement the following operations.
a) Insert an element at a specified position
b) Delete a specified element in the list
c) Search for an element and find its position in the list
#include<iostream.h>
#include<stdio.h>
#include<stdlib.h>

/*
* Node Declaration
*/
struct node
{
int info;
struct node *next;
}*last;

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

/*
* Main :contains menu
*/
void main()
{
int choice, element, position;
circular_llist cl;
while (1)
{
cout<<endl<<"---------------------------"<<endl;
cout<<endl<<"Circular singly linked list"<<endl;
cout<<endl<<"---------------------------"<<endl;
cout<<"[Link] Node"<<endl;
cout<<"[Link] after"<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link]"<<endl;
cout<<"[Link]"<<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;
cout<<"Insert element after position: ";
cin>>position;
cl.add_after(element, position);
cout<<endl;
break;
case 3:
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 4:
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;
case 5:
if (last == NULL)
{
cout<<"List Empty!! Can't Display"<<endl;
 break;
}
[Link]();
cout<<endl;
break;
case 6:
exit(1);
break;
default:
cout<<"Wrong choice"<<endl;
}
}

/*
* 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 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;
}
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;
}
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 Elements of a link list
*/
void circular_llist::display()
{
struct node *s;
if(last==NULL)
{
cout<<"List is Empty";
}
s = last->next;
while (s != last)
{
cout<<s->info<<"->";
s = s->next;
}

Output:
9 Write programs to implement the following using a single linked list:
a) Stack ADT b) Queue ADT.
a)
#include<iostream.h>
class Stack_Node
{
public:
int data;
Stack_Node *link;
};
class Stack
{
private:
Stack_Node *Top;
int Size;
int IsEmpty();
public:
Stack()
{
Top = NULL;
Size = 0;
}
int GetTop();
int Pop();
void Push(int Element);
int CurrSize();
};
int Stack :: IsEmpty()
{
if(Top == NULL)
return 1;
else
return 0;
}
int Stack :: GetTop()
{
if(!IsEmpty())
return (Top->data);
else
return 0;
}
void Stack :: Push(int value)
{
Stack_Node* NewNode;
NewNode = new Stack_Node;
NewNode->data = value;
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);
}
else
return 0;
}
int main()
{
Stack S;
[Link](5);
[Link](6);
cout << [Link]()<<endl;
cout << [Link]()<<endl;
[Link](7);
cout << [Link]()<<endl;
cout << [Link]()<<endl;
}

Output:
6
6
7
5
b) #include<iostream.h>

class QNode
{
public:
int data;
QNode *link;
};
class Queue
{
QNode *Front, *Rear;
int IsEmpty();
public:
Queue()
{
Front = Rear = NULL;
}
void Add( int Element);
int Delete();
int FrontElement();
};
int Queue :: IsEmpty()
{
if(Front == NULL)
return 1;
else
return 0;
}
void Queue :: Add(int x)
{
QNode *NewNode;
NewNode = new QNode;
NewNode->data = x;
NewNode->link = NULL;
//if the new is a node getting added in empty queue //then front should be set so as to
point to new
if(Rear == NULL)
{
Front = NewNode;
Rear = NewNode;
}
else
{
Rear->link = NewNode;
Rear = NewNode;
}
}
int Queue :: Delete()
{
int temp;
QNode *current = NULL;
if(!IsEmpty())
{
temp = Front->data;
current = Front;
Front = Front->link;
delete current;
if(Front == NULL)
Rear = NULL;
return(temp);
}
else
return 0;
}
int Queue :: FrontElement()
{
if(!IsEmpty())
return(Front->data);
else
return 0;
}
int main()
{
Queue Q;
[Link](11);
[Link](12);
[Link](13);
cout << [Link]() << endl;
[Link](14);
cout << [Link]() << endl;
cout << [Link]() << endl;
cout << [Link]() << endl;
[Link](15);
[Link](16);
cout << [Link]() << endl;
cout << [Link]() << endl;
}
Output:

11

12

13

14

15

16
10 Write a program to implement Binary search technique using Iterative method
and Recursive methods.
Using Iteration:

#include<iostream.h>

#define max 20

int Binary_Search_non_recursive(int A[], int n, int key)

int low = 0,high = n - 1,mid;

while(low <= high)

{
mid = (low + high)/2;

if(A[mid] == key) //found

return mid; // return position (mid)

else if(key<A[mid])

high = mid - 1;

else

low = mid + 1; //look in lower half

return -1; //return "not found"

int main()

int A[max] = {8,20,26,38,90,105,206,221,229,287,309,312,340,367,483,492,502,551,618,641};

int pos = 0,key;

cout << "Enter number to be searched : ";

cin >> key;

pos = Binary_Search_non_recursive(A,max,key);

if(pos != -1)

cout << "found at position" << pos;

}
else

cout << "not found";

return 0;

Output:
Enter number to be searched : 20
Found at position1
Using Recursion:

#include<iostream.h>

#define max 20

int Binary_Search(int A[],int low,int high,int key)

int mid;

if(low <= high)

mid = (low + high)/2;

if(A[mid] == key)

return mid;

else if(key < A[mid])

return Binary_Search(A, low, mid - 1, key);

else

return Binary_Search(A,mid + 1,high, key);

return -1;

int main()

int A[max] = {8,20,26,38,90,105,206,221,229,287,309,312,340,367,483,492,502,551,618,641};

int low = 0,high = max - 1,key;

int pos = 0;
cout << "Enter number to be searched : ";
cin >> key;
pos = Binary_Search(A,low,high,key);

if(pos != -1)
{
 cout << "found at position" << pos;
}
else
cout << "not found";
return 0;
}

Output:
Enter number to be searched:67
not found
11 Write a program for sorting the given list numbers in ascending order using the
following technique: Bubble sort and Selection sort.
Bubble Sort:
#include<iostream.h>

void bubblesort(int A[], int n)

int i, j,temp;

for(i = 1; i < n; i++) // number of passes

for(j = 0; j < n - i; j++)

{
if( A[j] > A[j + 1] ) // compare two successive

temp = A[j];

A[j] = A[j + 1]; // swap A[j] with A[j + 1]

A[j + 1] = temp;

int main()

int a[10], n, i;

cout << "Enter N";

cin >> n;

cout << "Enter the elements";

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

cin >> a[i];

bubblesort(a, n);

cout << "The sorted elements are";

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

cout <<" "<<a[i];

Output:
Selection Sort:
#include<iostream.h>

void SelectionSort(int A[], int n)

int i, j;

int minpos, temp;

for(i = 0; i < n - 1; i++)

minpos = i;

for(j = i + 1; j < n; j++)

//find the position of min element as minpos from

//i + 1 to n - 1

if(A[j] < A[minpos])

minpos = j;

if(minpos != i)

temp = A[i];

//swap the ith element and minpos element

A[i] = A[minpos];

A[minpos] = temp;

}
int main()

int a[10], n, i;

cout << "Enter N";

cin >> n;

cout << "Enter the elements";

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

cin >> a[i];

SelectionSort(a, n);

cout << "The sorted elements are";

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

cout <<" "<<a[i];

Output:
12 Write a program for sorting the given list numbers in ascending order using the
following technique: Insertion sort and Quick sort.
Insertion Sort:
#include<iostream.h>

void InsertionSort(int A[], int n)

int i, j, element;

for(i = 1; i < n; i++)

element = A[i];

// insert ith element in 0 to i - 1 array

j = i;

while((j > 0) && (A[j - 1] > element))

A[j] = A[j - 1]; // shift elements

j = j - 1;

A[j] = element; // place element at jth position

int main()

int a[10], n, i;

cout << "Enter N";

cin >> n;

cout << "Enter the elements";

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

cin >> a[i];

InsertionSort(a, n);

cout << "The sorted elements are";

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

cout <<" "<<a[i];

Output:
Quick Sort:

#include<iostream.h>

#define max 20

void quickSort(int a[],int low,int high)

{
int pivot,temp,i,j;
if(low<high)
{
pivot=a[low];
i=low;
j=high+1;
while(i<j)
{
while(a[i] <= pivot && i<j )
i++;
while(a[j]>pivot && i<=j )
j--;
if(i<=j)
{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}
temp=a[j];
a[j]=a[low];
a[low]=temp;
quickSort(a,low,j-1);
quickSort(a,j+1,high);
}
}
int main()
{
int A[max], n;
int i;
cout << "Enter number of numbers:";
cin >> n;
cout << "Enter numbers:";
for(i=0;i<n;i++)
cin>>A[i];
quickSort(A, 0, n - 1);
cout << "Sorted array is:";
for(i=0;i<n;i++)
cout<<" "<<A[i];
}
Output:
13 Write a program for sorting the given list numbers in ascending order using the
following technique: Merge sort and Heap sort
Merge Sort:
#include<iostream.h>

#define max 20
void merge (int A[],int low, int high, int mid)

int i, j, k, C[max];

i = low; // index for first part

j = mid + 1; // index for second part

k = 0; // index for array C

while((i <= mid) && (j <= high))

// merge arrays A & B in array C

if(A[i] < A[j]) C[k] = A[i++];

else

C[k] = A[j++]; k++;

while(i <= mid) C[k++] = A[i++];

while(j <= high) C[k++]=A[j++];

for(i = low, j = 0; i<=high; i++, j++)

{
A[i] = C[j];

void MergeSort(int A[], int low, int high)

int mid;
if(low < high)

mid = (low + high)/2;

MergeSort(A, low, mid);

MergeSort(A, mid + 1, high);

merge(A, low, high, mid);

int main()

int a[10], n, i;

cout << "Enter N";

cin >> n;

cout << "Enter the elements";

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

cin >> a[i];

MergeSort(a, 0,n-1);

cout << "The sorted elements are";

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

cout <<" "<<a[i];

}
Output:
Heap Sort:

#include<iostream.h>

//reheapup operation is required when a new value is

//inserted at the ith location

void reheapdown(int a[], int n, int i)
{
int temp, j;
while(2 * i + 1 < n)
{

j = 2 * i + 1; // j index shows the left child of the node

if(j + 1 < n && a[j + 1] > a[j])

//finding max from left and right child

j = j + 1;

if(a[i] > a[j]) break;

// if root > children then break

else
{
//swap a[i] with a[j]
temp = a[i];
a[i] = a[j];
a[j] = temp;
i = j;
}
} // end of while
}

void Heap_Sort (int a[], int n)

{
//create heap
int i, temp;
for(i = (n - 1)/2; i >= 0; i--)
reheapdown(a, n, i);
//delete first value and swap it with last
while(n > 0)
{
//swap first and last element
temp = a[0];
a[0] = a[n - 1];
a[n - 1] = temp;
n--; // decrement count
reheapdown(a, n, 0);
}
}
int main()
{
int a[10], n, i;
cout << "Enter N";
cin >> n;
cout << "Enter the elements";
for(i = 0; i < n; i++)
cin >> a[i];
Heap_Sort(a, n);
cout << "The sorted elements are";
for(i = 0; i < n; i++)
cout <<" "<<a[i];
}

Output:
14 Write a program to traverse a binary tree in following way.
a) Pre-order b) In-order c) Post-order
#include<iostream.h>

struct Node {
char data;
struct Node *left;
struct Node *right;
};

//Function to visit nodes in Preorder

void Preorder(struct Node *root) {
// base condition for recursion
// if tree/sub-tree is empty, return and exit
if(root == NULL) return;

cout << root->data << " ";// Print data

Preorder(root->left); // Visit left subtree
Preorder(root->right); // Visit right subtree
}

//Function to visit nodes in Inorder

void Inorder(Node *root) {
if(root == NULL) return;

Inorder(root->left); //Visit left subtree

cout << root->data << " ";// Print data
Inorder(root->right); // Visit right subtree
}

//Function to visit nodes in Postorder

void Postorder(Node *root) {
if(root == NULL) return;

Postorder(root->left); // Visit left subtree

Postorder(root->right); // Visit right subtree
cout << root->data << " ";// Print data
}

// Function to Insert Node in a Binary Search Tree

Node* Insert(Node *root,char data) {
if(root == NULL) {
root = new Node();
root->data = data;
root->left = root->right = NULL;
}
else if(data <= root->data)
root->left = Insert(root->left,data);
 else
root->right = Insert(root->right,data);
return root;
}

int main() {
Node* root = NULL;
root = Insert(root,'M'); root = Insert(root,'B');
root = Insert(root,'Q'); root = Insert(root,'Z');
root = Insert(root,'A'); root = Insert(root,'C');
//Print Nodes in Preorder.
cout<<"Preorder: ";
Preorder(root);
cout<<"\n";
//Print Nodes in Inorder
cout<<"Inorder: ";
Inorder(root);
cout<<"\n";
//Print Nodes in Postorder
cout<<"Postorder: ";
Postorder(root);
cout<<"\n";
return 0;
}

Output:
15 Write a program to the implementation graph traversals – BFS and DFS.
BFS:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
int cost[10][10],i,j,k,n,qu[10],front,rare,v,visit[10],visited[10];
void main()
{
int m;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES \n";
for(k=1;k<=m;k++)
{
cin >>i>>j;
cost[i][j]=1;
}

cout <<"enter initial vertex";

cin >>v;
cout <<"Visitied vertices\n";
cout << v;
visited[v]=1;
k=1;
while(k<n)
{
for(j=1;j<=n;j++)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
qu[rare++]=j;
}
v=qu[front++];
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}
Output:
DFS:
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10];

void main()
{
int m;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES \n";
for(k=1;k<=m;k++)
{
cin >>i>>j;
cost[i][j]=1;
}

cout <<"enter initial vertex";

cin >>v;
cout <<"ORDER OF VISITED VERTICES";
cout << v <<" ";
visited[v]=1;
k=1;
while(k<n)
{
for(j=n;j>=1;j--)
if(cost[v][j]!=0 && visited[j]!=1 && visit[j]!=1)
{
visit[j]=1;
stk[top]=j;
top++;
}
v=stk[--top];
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}
Output:
16 Write a program to find the minimum spanning tree for a weighted graph using
a) Prim’s Algorithm b) Kruskal’s Algorithm.
Prim’s :
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

int cost[10][10],i,j,k,n,stk[10],top,v,visit[10],visited[10],u;

void main()
{
int m,c;
cout <<"enterno of vertices";
cin >> n;
cout <<"ente no of edges";
cin >> m;
cout <<"\nEDGES Cost\n";
for(k=1;k<=m;k++)
{
cin >>i>>j>>c;
cost[i][j]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;

cout <<"ORDER OF VISITED VERTICES";

k=1;
while(k<n)
{
m=31999;
if(k==1)
{
for(i=1;i<=n;i++)
for(j=1;j<=m;j++)
if(cost[i][j]<m)
{
m=cost[i][j];
u=i;
}
}
else
{
for(j=n;j>=1;j--)
if(cost[v][j]<m && visited[j]!=1 && visit[j]!=1)
{
 visit[j]=1;
stk[top]=j;
top++;
m=cost[v][j];
u=j;
}
}
cost[v][u]=31999;
v=u;
cout<<v << " ";
k++;
visit[v]=0; visited[v]=1;
}
}

Output:
Kruskal’s
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>

int cost[10][10],i,j,k,n,m,c,visit,visited[10],l,v,count,count1,vst,p;

void main()
{
int dup1,dup2;
cout<<"enter no of vertices";
cin >> n;
cout <<"enter no of edges";
cin >>m;
cout <<"EDGE Cost";
for(k=1;k<=m;k++)
{
cin >>i >>j >>c;
cost[i][j]=c;
cost[j][i]=c;
}
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]==0)
cost[i][j]=31999;
visit=1;
while(visit<n)
{
v=31999;
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if(cost[i][j]!=31999 && cost[i][j]<v && cost[i][j]!=-1 )
{
int count =0;
for(p=1;p<=n;p++)
{
if(visited[p]==i || visited[p]==j)
count++;
}
if(count >= 2)
{
for(p=1;p<=n;p++)
if(cost[i][p]!=31999 && p!=j)
dup1=p;
for(p=1;p<=n;p++)
if(cost[j][p]!=31999 && p!=i)
dup2=p;

if(cost[dup1][dup2]==-1)
continue;
}
l=i;
k=j;
v=cost[i][j];
}
cout <<"edge from " <<l <<"-->"<<k;
cost[l][k]=-1;
cost[k][l]=-1;
visit++;
int count=0;
count1=0;
for(i=1;i<=n;i++)
{
if(visited[i]==l)
count++;
if(visited[i]==k)
count1++;
}
if(count==0)
visited[++vst]=l;
if(count1==0)
visited[++vst]=k;
}
}

Output: