Table of the contents

1. Aims and Objectives 4
2.JNTU syllabus 5
3.Evaluation Procedure for Internal Laboratory Examinations 7
4.Evaluation Procedure for External Laboratory Examinations 7
5.LAB Schedule 8
6.Sample programs 11
6.1 Stack using Arrays 11
6.2 Queue Using Arrays 16
6.3 STACK USING SINGLE LINKED LIST 23
6.5 Queue Using Arrays 30
6.6 Dequeue 35
6.7 Binary search Tree 46
6.8 Circular queue using arrays 56
6.9 BFS & DFS 62
6.10 Sorting Technique Methods 69
6.10.A Quick sort ALGORITHM: 69
6.10.B IMPLEMENT MERGESORT PROGRAM 74
6.10.C HEAP SORT 79
6.11 PRIMS ALGORITHM 82
6.12 Kruskal Algorithm 88
7. Additional Programs 95
7.1 PROGRAM TO IMPLEMENT PARAMETERIZED CONSTRUCTORS 95
7.2 PROGRAM TO IMPLEMENT COPY CONSTRUCTORS 97
7.3 PROGRAM TO IMPLEMENT SINGLE INHERITENCE 99
7.4 PROGRAM TO IMPLEMENT MULTILEVEL INHERITANCE 100
7.5 PROGRAM TO IMPLEMENT MULTIPLE INHERITENCE 102
7.6 PROGRAM TO STUDENTS DATABASE 103
7.7 PROGRAM TO MAINTAIN HOSPITAL DATABASE USING SINGLE INHERITENCE 105
7.8 PROGRAM TO IMPLEMENT OPERATOR OVERLOADING 107
7.9 PROGRAM TO IMPLEMENT FUNCTION OVELOADIN 109
7.10 PROGRAM TO CONVERT A LOWER CASE CHARACTER TO AN UPPERCASE CHARACTER OF A TEXT FILE 110
7.11 PROGRAM TO IMPLEMENT EXCEPTION HANDLING 112
7.12 PROGRAM TO FIND SUM OF TWO NUMBERS USING CLASS TEMPLATES 114
7.13 PROGRAM TO IMPLEMENT BINARY SEARCH 117
7.14 PROGRAM TO IMPLEMENT JOB SEQUENCING USING GREEDY METHOD 119















2. JNTU syllabus
Advanced Data Structures and Algorithms(C++)

1.Write a C++ programs to implement the following using an array
a). Stack ADT b). Queue ADT
2.Write a C++ programs to implement the following using linked list
a). Stack ADT b). Queue ADT
3. write a C++ program to implement the deueue(double ended queue) ADT using a doubly linked list
4. Write a C++ program to perform the following operations:
a) Insert an element into a binary search tree
b) Delete an element from a binary search tree
c) Search for a key element in a binary search tree
5. Write a C++ program to implement circular queue ADT using an array
6. Write C++ programs that use non-recursive functions to traverse the given binary tree in
a) Preorder b) in order and c)post order
7. Write a C++ programs for the implementation of bfs and dfs for a given graph
8. Write a C++ program for implementing the following sorting methods
a) Quick sort b) Merge sort c) Heap sort
9. Write a C++ program to perform the following operations
a) Insertion into a b-tree b) deletion from B- tree
10. Write a C++ program to perform the following operations
a)Insertion into an AVL-tree b) deletion from AVL- tree
11. Write a C++ program to implement Kruskal’s algorithm to generate a minimum spanning tree.
12. Write a C++ program to implement Prim’s algorithm to generate a minimum spanning tree.
13. Write a C++ program to implement all the functions of a dictionary (ADT) using hashing.

6.1 Stack using Arrays

Program Definition
Insert a set of integers into the stack and delete these integers by stack using arrays
Algorithm:
Algorithm for Push operation
1. Algorithm add (item)
2. //push an element on to the stack .return
3. //True if successful; else return false
4. // item is used as an input
5. {
6. If (top>=n-1) then
7. {
8. Write (“stack is full!”); return false;
9. }
10. Else
11. {
12. Top: =top+1;
13. Stack [top]:=item;
14. Return true;
15. }

Algorithm for Pop operation
1. Algorithm delete (item)
2. //pop the top element from the stack .return
3. //true if successful else returns false .item
4. //is used as an output
5. {
6. If (top<0) then
7. {
8. Write (“stack is empty”); return false;
9. }
10. Else
11. {
12. Item: = stack [top]; top=top-1; return true;
13. }
14. }

Stacks using arrays out put:
enter the size of stack: 4
1.insert 2.delete 3.display 4.quit
enter choice: 1
enter element to be inserted 2
1.insert 2.delete 3.display 4.quit
enter choice: 1
enter element to be inserted 3
1.insert 2.delete 3.display 4.quit
enter choice: 1
enter element to be inserted 5
1.insert 2.delete 3.display 4.quit
enter choice: 3
element in stack are 2 3 5
1.insert 2.delete 3.display 4.quit
enter choice: 2
the element popped is5
1.insert 2.delete 3.display 4.quit
enter choice: 2
the element popped is3
1.insert 2.delete 3.display 4.quit
enter choice: 2
the element popped is2
1.insert 2.delete 3.display 4.quit
enter choice: 2
stack is under flow
1.insert 2.delete 3.display 4.quit
enter choice: 4


CODE
#include
#include
#include
class stack
{
private:
int stack[10],max,top,i,element;
public:
void read();
void insert();
void del();
void display();
stack()
{
top=-1;
}
}s;
void stack::read()
{
cout<<"enter the size of stack: ";
cin>>max;
}
void stack::insert()
{
if(top==max-1)
cout<<"stack is over flow";
else
{
top=top+1;
cout<<"enter element to be inserted";
cin>>element;
stack[top]=element;
}
}
void stack::del()
{
if(top==-1)
cout<<"stack is under flow";
else
{
element=stack[top];
cout<<"the element popped is"< top=top-1;
}
}
void stack::display()
{
if(top==-1)
cout<<"stack is empty";
else
{
cout<<"element in stack are";
for(i=0;i<=top;i++)
cout<<" "< }
}
void main()
{
int choice;
clrscr();
s.read();
while(1)
{
cout<<"\n1.insert 2.delete 3.display 4.quit";
cout<<"\nenter choice:";
cin>>choice;
switch(choice)
{
case 1:s.insert();
break;
case 2:s.del();
break;
case 3:s.display();
break;
case 4:exit(0);
}
}
}
RESULT:A set of integers has been inserted and the list of integers also displayed, If delete an integer from the stack that is also be done.
Remarks
This program is only for set of integer when assigned at compile time or this is work only size of the stack by the user.
6.2 Queue Using Arrays
Program Definition
Insert a set of integers into the QUEUE and delete these integers by QUEUE using arrays
Algorithm:
Algorithm for Insert operation
1. Algorithm addq(item)
2. Check overflow condition
If rear>=size-1
Output “Overflow” and return.
3. Increment rear pointer
Rear=rear+1
4. Insert an element
A[rear]=value
5. Set the front pointer
If front ==-1
Front=0
6. Return
Algorithm for Delete operation

1. Algorithm delete(item)
2. Check underflow condition
If front ==-1
Output “Underflow” and return
3. Remove an element
Value=q[front]
4. Check for empty queue
If front==rear
Front=-1
Rear=-1
Else
Front =front+1
5. Return value
Queue using arrays output:

enter n value:5
1.insert 2.delete 3.display 4.quit
enter your choice:1
insert value into queue:2

1.insert 2.delete 3.display 4.quit
enter your choice:1
insert value into queue:3

1.insert 2.delete 3.display 4.quit
enter your choice:1
insert value into queue:5

1.insert 2.delete 3.display 4.quit
enter your choice:1
insert value into queue:6

1.insert 2.delete 3.display 4.quit
enter your choice:3
elements in queue are 2 3 5 6
1.insert 2.delete 3.display 4.quit
enter your choice:2
element deleted is 2
1.insert 2.delete 3.display 4.quit
enter your choice :2
element deleted is 3
1.insert 2.delete 3.display 4.quit
enter your choice :2
element deleted is 5
1.insert 2.delete 3.display 4.quit
enter your choice :2
element deleted is 6
1.insert 2.delete 3.display 4.quit
enter your choice :2
queue is empty
1.insert 2.delete 3.display 4.quit
enter your choice :4





Code
#include
#include
#include
class queue
{
private:
int front,rear,max,a[10],element;
public:
void getn();
void insert();
void del();
void display();
queue()
{
front=0;
rear=-1;
}
}q;
void queue::getn()
{
cout<<"\n enter max value:";
cin>>max;
}
void queue::insert()
{
if(rear==max-1)
cout<<"queue is overflow";
else
{
cout<<"insert value into queue:";
cin>>element;
rear=rear+1;
a[rear]=element;
}
}
void queue::del()
{
int temp;
if(rear {
cout<<"queue is empty";
front=0;
rear=-1;
}
else
{
temp=a[front];
front=front+1;
cout<<"element deleted is "< }
}
void queue::display()
{
int i;
if(rear cout<<"queue is empty";
else
{
cout<<"elements in queue are";
for(i=front;i<=rear;i++)
cout<<" "< }
}
void main()
{
int choice;
clrscr();
q.getn();
while(1)
{
cout<<"\n 1.insert 2.delete 3.display 4.quit";
cout<<"\n enter your choice:";
cin>>choice;
switch(choice)
{
case 1:q.insert();
break;
case 2:q.del();
break;
case 3:q.display();
break;
case 4:exit(0);
}
}
}

6.3 STACK USING SINGLE LINKED LIST

Program Definition
Insert a set of integers into the stack and delete these integers by stack using linked lists
Algorithm:
Algorithm for push operation
//type is the type of data
Node = record
{
Type=data; node *link;
}
1. Algorithm add(item)
2. {
3. //get a newnode
4. temp:=newnode;
5. if(temp!=0)then
6. {
7. (temp->data):=item;(temp->link):=top;
8. top:=temp;
9. return true;
10. }
11. else
12. {
13. write (“out of space!”);
14. return false;
15. }
16. }
Algorithm for pop operation
1. Algorithm delete(item)
2. {
3. if(top=0)then
4. {
5. write(“stack is empty”);
6. return false;
7. }
8. else
9. {
10. item:=(top->data);temp:=top;
11. top:=(top->link);
12. delete temp;
13. return true;
14. }
15. }

Stack using linked list output:

1.push 2.pop 3.display 4.exit
enter your chioce:1
enter element into the stack:9

1.push 2.pop 3.display 4.exit
enter your chioce:1
enter element into the stack:8

1.push 2.pop 3.display 4.exit
enter your chioce:1
enter element into the stack:7

1.push 2.pop 3.display 4.exit
enter your chioce:2
element deleted from stack is:7

1.push 2.pop 3.display 4.exit
enter your chioce:3
elements present in the stack are
8
9
1.push 2.pop 3.display 4.exit
enter your chioce:2
element deleted from stack is:8

1.push 2.pop 3.display 4.exit
enter your chioce:2
element deleted from stack is:9
1.push 2.pop 3.display 4.exit
enter your chioce:3
stack is empty
1.push 2.pop 3.display 4.exit
enter your choice: 4


CODE
#include
#include
#include
#include
class sll
{
private:
int element;
struct node
{
int value;
node *next;
};
typedef struct node nodeptr;
nodeptr *top;
public:
sll()
{
top=NULL;
}
void insert();
void delelement();
void display();
};
void sll::insert()
{
nodeptr *temp;
temp=new nodeptr;
cout<<"enter element into the stack:";
cin>>element;
temp->value=element;
temp->next=NULL;
if(top==NULL)
{
top=temp;
top->next=NULL;
}
else
{
temp->next=top;
top=temp;
}
}
void sll::delelement()
{
nodeptr *temp;
temp=top;
if(top==NULL)
cout<<"stack is empty\n";
else
{
top=top->next;
cout<<"element deleted from stack is:"<value< delete temp;
}
}
void sll::display()
{
nodeptr *temp;
if(top==NULL)
cout<<"stack is empty\n";
else
{
cout<<"elements present in the stack are\n";
for(temp=top;temp!=NULL;temp=temp->next)
{
cout<value<<"\n";
}
}
}
void main()
{
int chioce;
sll s;
clrscr();
while(1)
{
cout<<"\n1.push 2.pop 3.display 4.exit"<<"\n";
cout<<"enter your chioce:";
cin>>chioce;
switch(chioce)
{
case 1: s.insert();
break;
case 2: s.delelement();
break;
case 3: s.display();
break;
case 4:exit(0);
}
}
}

6.5 Queue Using Arrays

Program Definition
Insert a set of integers into the QUEUE and delete these integers by QUEUE using linked lists
Algorithm:
CODE
#include
#include
#include
#include
class queue
{
private:
int element;
struct node
{
int value;
node *next;
};
node *front,*rear;
public:
queue()
{
front=NULL;
rear=NULL;
}
void insert();
void delelement();
void display();
};
void queue::insert()
{
node *temp;
temp=new node;
cout<<"\nenter the element into the queue:";
cin>>element;
temp->value=element;
if(front==NULL)
{
front=temp;
rear=temp;
rear->next=NULL;
}
else
{
while(rear->next!=NULL)
rear=rear->next;
rear->next=temp;
rear=temp;
rear->next=NULL;
}
}
void queue:: delelement()
{
node *temp;
if(front==NULL)
cout<<"queue is empty\n";
else
{
temp=front;
front=front->next;
cout<<"\nelement deleted from queue is:";
cout<value;
delete temp;
}
}
void queue::display()
{
node *temp;
if(front==NULL)
cout<<"queue is empty";
else
{
cout<<"elements present in the queue are\n";
for(temp=front;temp!=NULL;temp=temp->next)
{
cout<value<<"\n";
}
}
}
void main()
{
queue q;
int chioce;
clrscr();
while(1)
{
cout<<"\n1.insert 2.delete 3.display 4.exit \n";
cout<<"enter your chioce:";
cin>>chioce;
switch(chioce)
{
case 1:
q.insert();
break;
case 2:
q.delelement();
break;
case 3:
q.display();
break;
case 4:
exit(0);
}
}
}

6.6 Dequeue

Program Definition
Insert a set of integers into the DEQUEUE ,insert an integer at beginning or at end ,and delete these integers from QUEUE at the beginning or at end .
Algorithm:
INSERTING AT FRONT
1. Declaring the new node.
2. Entering the element into new node.
3. Checking if front= =NULL.
4. Front<- new node.
Front->left <-NULL
Rear<- new node
Rear ->right ->NULL
5. else
new node-> right = front
front <-new node
front<-left <-NULL

ALGORITHM FOR INSERTING
1. Declaring the new node
2. Entering the element into new node.
3. Checking if front = =NULL.
4. front <-new node
front -> left <-NULL
Rear <- new node
Rear -> right<-NULL
5. else
rear = front
temp = front
while temp ->right != NULL
temp <-> temp -> right
rear <- temp
rear ->right <-new node
new node <-left <-rear
rear <-new node
rear ->right <-NULL
ALGORITHM FOR DELETION FROM FRONT
1. Declaring the temporary nodeptr.
2. Check if front = = NULL.
3. Write QUEUE is empty
else
{
if(front = = rear)
{
temp<-rear
temp<-rear
deleting temporary node ptr
front <- rear <-NULL
}
else
{
temp <- front;
current <-front;
temp <-temp <-right;
while(temp ->right !=NULL)
{
temp <-temp ->right
current <-current ->right
}
Rear=temp;
Rear=current;
Delete temporary nodeptr
Rear ->right =NULL
}
}
END


Sample input and output
Output for dequeue
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:1
enter the element:2
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:1
enter the element:3
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:2
enter the data:5
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:2
enter the data:6
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:5
3 2 5 6

1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:3
deleted item:3
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:4
deleted item:6
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:3
deleted item:2
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:4
deleted item:5
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit
enter u r choice:5
dq is empty
1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit

CODE

#include
#include
#include
class node
{
public:
int no;
node *left,*next;
};
class list
{
public:
node *front,*rear;
list()
{
front=NULL;
}
void ibeg();
void iend();
void dbeg();
void dend();
void display();
};
void list::ibeg()
{
node *temp=new node;
cout<<"enter the element:";
cin>>temp->no;
if(front==NULL)
{
front=temp;
front->left=NULL;
rear=temp;
rear->next=NULL;
}
else
{
temp->next=front;
front->left=temp;
front=temp;
front->left=NULL;
}
}
void list::iend()
{
node *temp=new node;
cout<<"enter the data:";
cin>>temp->no;
if(front==NULL)
{
front=temp;
front->left=NULL;
rear=temp;
rear->next=NULL;
}
else
{
rear=front;
while(rear->next!=NULL)
rear=rear->next;
rear->next=temp;
temp->left=rear;
rear=temp;
rear->next=NULL;
}
}
void list::dbeg()
{
node *temp;
if(front==NULL)
cout<<" dq is empty"<else if(front==rear)
{
temp=front;
cout<<"deleted item:"<no<<"\n";
delete temp;
front=rear=NULL;
}
else
{
temp=front;
front=front->next;
cout<<"deleted item:"<no<<"\n";
delete temp;
}
}
void list::dend()
{
node *temp,*cur;
if(front==NULL)
cout<<"\ndq is empty\n";
else if(front==rear)
{
temp=front;
cout<<"deleted item:"<no<<"\n";
delete temp;
front=rear=NULL;
}
else
{
temp=front;
cur=front;
temp=front->next;
while(temp->next!=NULL)
{
cur=temp;
temp=temp->next;
}
rear=temp;
rear=cur;
cout<<"deleted item:"<no< rear->next=NULL;
}
}
void list::display()
{
node *temp;
if(front==NULL)
cout<<"dq is empty\n";
else
{
for(temp=front;temp!=NULL;temp=temp->next)
{
cout<<" "<no;
}
cout< }
}
void main()
{
list l;
int ch;
clrscr();
while(1)
{
cout<<"\n 1.ibeg 2.iend 3.dbeg 4.dend 5.display 6.exit";
cout<<"\nenter u r choice:";
cin>>ch;
switch(ch)
{
case 1:l.ibeg();
break;
case 2:l.iend();
break;
case 3:l.dbeg();
break;
case 4:l.dend();
break;
case 5:l.display();
break;
case 6:exit(0);
}
}
}

6.7 Binary search Tree

Program Definition
A Program to perform the following operations:
1. Insert an element into a binary search tree.
2. Delete an element from a binary search tree
3. Search for a key element in a binary search tree.
Algorithm
BINARY SEARCH TREE OPERATIONS
Aim: Algorithm for insertion element
1. algorithm Insert (x)
2. // insert x into the binary search tree
3. {
4. found:= false;
5. p:= tree;
6. // search for x, q is parent of p
7. while ( (p != 0) and not found) do
8. {
9. q:= p; // save p
10. }
11. else
12. tree := p;
13. }
14. }