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. }

ALGORITHM FOR SEARCHING

1. Algorithm search (x)
2. {
3. found:= false;
4. t:= tree;
5. while ( ( t != 0) and not found) do
6. {
7. if (x =(t-> data)) then found:= true;
8. else if(x < ( t-> data)) then t::= ( t-> l. child);
9. else t::= ( t-> r. child);
10. }
11. if ( not found) then return 0;
12. else return t;
13. }

Binary search tree output:

Tree - Insert and Delete and search operations :
1.insert 2.delete 3.search 4.exit
enter choice:1
Key to insert ? 5
Tree display :
5
1.insert 2.delete 3.search 4.exit
enter choice:1
Key to insert ? 6
Tree display :
6
5


1.insert 2.delete 3.search 4.exit
enter choice:1
Key to insert ? 4
Tree display :
6
5
4
1.insert 2.delete 3.search 4.exit
enter choice:1
Key to insert ? 8
Tree display :
8
6
5
4
1.insert 2.delete 3.search 4.exit
enter choice: 2
Key to delete ?5
tree Display :
8
6
4

1.insert 2.delete 3.search 4.exit
enter choice:2
Key to delete ?6
tree Display :
8
4
1.insert 2.delete 3.search 4.exit
enter choice:2
Key to delete ?4
tree Display :
8
1.insert 2.delete 3.search 4.exit
enter choice:2
Key to delete ?8
tree Display :
1.insert 2.delete 3.search 4.exit
enter choice:4

CODE

#include
#include
#define true 1
#define false 0
#include
class tree
{
public:
int data;
tree *left,*right;
};
tree *inserttree(int data,tree *p)
{
if(p==NULL)
{
p=new tree();
p->data=data;
p->left=NULL;
p->right=NULL;
return p;
}
if(datadata)
p->left=inserttree(data,p->left);
else
if(data>p->data)
p->right=inserttree(data,p->right);
return p;
}
void printtree(tree *t,int level)
{
int i;
if(t)
{
printtree(t->right,level+1);
cout< for(i=0;i cout<<" ";
cout<data;
printtree(t->left,level+1);
}
}
tree *del(tree *r,tree *q)
{
tree *dnode;
if(r->right!=NULL)
r->right=del(r->right,q);
else
{
dnode=r;
q->data=r->data;
r=r->left;
delete dnode;
}
return r;
}
tree *deleteelement(tree *p,int data)
{
tree *q;
if(p==NULL)
{
cout< return p;
}
else
{
if(datadata)
p->left=deleteelement(p->left,data);
else
if(data>p->data)
p->right=deleteelement(p->right,data);
else
{
q=p;
if(q->right==NULL)
{
p=q->left;
delete q;
}
else
if(q->left==NULL)
{
p=q->right;
delete q;
}
else
q->left=del(q->left,q);
}
}
return p;
}
tree *searchelement(tree *p,int data)
{
tree *q;
if(p==NULL)
{
cout< return p;
}
else
{
if(datadata)
p->left=searchelement(p->left,data);
else
if(data>p->data)
p->right=searchelement(p->right,data);
else
cout<<"element is found\n";
return p;
}

}

void main()
{
int data,depth,ch;
tree *t=NULL;
clrscr();
cout< while(1)
{
cout<<"\n1.insert 2.delete 3.search 4.exit"< cout<<"\n enter choice:";
cin>>ch;
switch(ch)
{
case 1:
cout< cin>>data;
if(data==0)
break;
t=inserttree(data,t);
cout<<"\n Tree display : \n";
printtree(t,1);
break;
case 2:
cout<<"\n Key to delete ?";
cin>>data;
t=deleteelement(t,data);
cout< printtree(t,1);
break;
case 3:
cout<<"\n Key to search ?";
cin>>data;
t=searchelement(t,data);
cout< printtree(t,1);
break;
case 4: exit(0);
}
}
}

6.8 Circular queue using arrays

Program Definition
Insert a set of integers into the Circular QUEUE , ,and delete these integers from circular QUEUE using arrays
Algorithm:
Algorithm for addition of an element
1. Algorithm add q(item)
2. // Insert item in the circular queue
3. // sorted in q[0;n-1] rear points to the
4. // last item and front is one position
5. // counter wise from the first item in q
6. {
7. rear := (rear+1)mod n; // advance rear clockwise
8. if (front =rear) then
9. {
10. write (“queue is full”);
11. if (front=0) then rear:=n-1;
12.else rear:=rear-1;
13.// move rear one position counter clockwise
14.return false;
15.}
16. elae
17.{
18. q[rear]:= item; || insert new item
19. return true;
ALGORITHM FOR DELETION OF AN ELEMENT

1.algorithm delete q(item)
2.// removes and returns the front element of the queue q[0;n-1]
3.{
4.if (front=rear) then
5.{
6.write(“queue is empty”);
7.return false;
8.}
9.else
10.{
11.front := (front+1)mod n;
12. item := q[front];
// set item to front of queue

13.return true;
14.}
15.}
Circular queue using arrays output:

enter choice1
enter element:6
1.insert 2.delete 3.display 4.exit
enter choice1
cq is over flow
1.insert 2.delete 3.display 4.exit
enter choice2
deleted element is:2
1.insert 2.delete 3.display 4.exit
enter choice1
enter element:10
1.insert 2.delete 3.display 4.exit
enter choice3
the elements in the array are:
10 3 5 6
1.insert 2.delete 3.display 4.exit
enter choice2
deleted element is:3
1.insert 2.delete 3.display 4.exit
enter choice2
deleted element is:5
1.insert 2.delete 3.display 4.exit
enter choice2

deleted element is:6
1.insert 2.delete 3.display 4.exit
enter choice2
deleted element is:10
1.insert 2.delete 3.display 4.exit
enter choice2
cq is empty
1.insert 2.delete 3.display 4.exit
enter choice4

CODE

#include
#include
#include
class cq
{
private:
int cq[10],i,rear,front,element,max;
public:
void get()
{
cout<<"enter size of cq:";
cin>>max;
}
void insertion();
void deletion();
void display();
cq()
{
front=0;
rear=-1;
}
};
void cq::insertion()
{
if((rear==max-1 && front==0)||((front==rear+1)&&(front!=0 && rear!=-1)))
{
cout<<"cq is over flow";
}
else
{
rear=(rear+1) % max;
cout<<"enter element:";
cin>>element;
cq[rear]=element;
}
}
void cq::deletion()
{
if(front==0 && rear==-1)
{
cout<<"cq is empty";
}
else
{
element=cq[front];
if(front!=rear)
front=(front+1) % max;
else
{
front=0;
rear=-1;
}
cout< }
}
void cq::display()
{
if(front==0 && rear==-1)
cout<<"cq is empty";
else if(rear {
cout<<"the elements in the array are:"< for(i=0;i<=rear;i++)
cout<<" "< for(i=front;i cout<<" "< }
else
{
cout<<"the elements in the array are:"< for(i=front;i<=rear;i++)
cout<<" "< }}
void main()

6.9 BFS & DFS

Program Definition:
A Program for implementation of BFS and DFS for a given graph
Algorithm
#include
#include
#include
#include
#define max 10
class graph
{
public:
int array[max][max],stack[max],queue[max],order[max],visited[max];
int top,rear,front,ord,vertices;
void init();
void input();
void addq(int);
int delq();
void bfs(int);
void push(int);
int pop();
void dfs(int);
void display();
};
void graph::init()
{
int i;
for(i=0;i {
visited[i]=0;
order[i]=0;
}
front=rear=-1;
top=-1;
ord=0;
}
void graph::input()
{
int i,j;
cout<<"\n enter no of vertices:";
cin>>vertices;
for(i=0;i {
for(j=0;j {
cout<<"\n enter path from"< cin>>array[i][j];
}
}
}
void graph::addq(int item)
{
if(rear==max-1)
cout<<"overflow";
else
{
queue[++rear]=item;
if(front==-1)
front=0;
}
}
int graph::delq()
{
int item;
if(front==-1)
cout<<"underflow";
else
{
item=queue[front];
if(front==rear)
front=rear=-1;
else
front=front+1;
}
return item;
}
void graph::bfs(int start)
{
visited[start]=1;
addq(start);
while(front!=-1)
{
start=delq();
for(int i=0;i<=vertices;i++)
{
if(visited[i]==0)
{
addq(i);
visited[i]=1;
order[ord++]=i;
}
}
}
}
void graph::push(int item)
{
if(top==max)
cout<<"overflow";
else
stack[++top]=item;
}
int graph::pop()
{
int item;
if(top==-1)
cout<<"underflow";
else
item=stack[top--];
return item;
}
void graph::dfs(int start)
{
visited[start]=1;
push(start);
order[ord++]=start+1;
while(top!=-1)
{
start=pop();
for(int i=0;i {
if(array[start][i] && !visited[i])
{
push(i);
dfs(i);
}
}
}
}
void graph::display()
{
cout<<"\nvisited vertices";
for(int i=0;i {
if(i)
cout<<"->";
cout< }
}
void main()
{
graph g;
int ch,ver;
clrscr();
while(1)
{
cout< cout<<"enter choice:";
cin>>ch;
switch(ch)
{
case 1:
g.init();
g.input();
break;
7 case 2:cout<<"bfs start value:";
cin>>ver;
g.init();
g.bfs(ver-1);
break;
case 3:cout<<"dfs start value:";
cin>>ver;
g.init();
g.dfs(ver-1);
break;

case 4:g.display();
break;
case 5:exit(0); } }}
Output of BFS & DFS
enter path from1to11/0 :0
enter path from1to21/0 :1
enter path from1to31/0 :1
enter path from1to41/0 :0
enter path from2to11/0 :1
enter path from2to21/0 :0
enter path from2to31/0 :0
enter path from2to41/0 :1
enter path from3to11/0 :1
enter path from3to21/0 :0
enter path from3to31/0 :0
enter path from3to41/0 :1
enter path from4to11/0 :0
enter path from4to21/0 :1
enter path from4to31/0 :1
enter path from4to41/0 :0
1.initialise 2.bfs 3.dfs 4.display 5.exit
enter choice:2
bfs start value:1
1.initialise 2.bfs 3.dfs 4.display 5.exit
enter choice:4
visited vertices1->2->3->4
1.initialise 2.bfs 3.dfs 4.display 5.exit
enter choice:3

6.10 Sorting Technique Methods

Program Definition
A Program for implementing the following sorting methods:
1. Quick sort 2. Merge sort 3. Heap sort
6.10.A Quick sort ALGORITHM:
,Quicksort splits the array into two pieces. However, Quicksort takes the additional step of placing all the low values in the left piece and all the high values in the right piece. Consequently, no merge step is needed after the two halves have been sorted. The partition() function (below) is responsible for dividing the array into two pieces.

1. Algorithm QUICK sort(p, q)
2. //sorts the elements a[p],……a[q] which
3. Reside in the global array a[1:n] into
4. ascending order; a[n+1] is considered to
5. be defined and must be greater than or equal to all the
6. elements in a[1:n]
7. {
8. if (p9. {
10. //divide p into two sub problems
11. j:= partition (a,p,q+1);
12. //j is the position of the partitioning element
13. //solve the sub problems
14. QUICK sort (p,j-1);
15. QUICK sort (j+1,q);
16. //There is no need for combining solutions
17. }
18. }


ALGORITHM FOR PARTITION
1. Algorithm partition (a, m, p);
2. //within a[m], a[m+1],…. A[p-1] the elements
3. //are rearranged in such a manner that
4. //if initially t=a[m], then after completion
5. //a[q]=t for some q between m and
6. //p-1, a[k]<=t for m<=k<=q and a[k]>=t
7. //for q8. {
9. v:= a[m]; I := m; j:= p;
10. repeat
11. {
12. repeat
13. I : =i+1;
14. until (a[j]<=v);
15. repeat
16. j: =j-1;
17. until (a[j]<=v);
18. if (i19. } until(i>=j);
20. a[m]:= a[j]; a[j]:v; return j;
21. }

ALGORITHM FOR INTERCHANGE
1. Algorithm interchange(a, I, j);
2. //exchange a[i] with a[j]
3. {
4. p:=a[j];
5. a[i]: = a[j];a[j]:=p;
6. }


Sample input and output
Output for quick sort
enter n values:5
array elements
6
7
5
8
4
the sorted array
4 5 6 7 8

Quick sort CODE

#include
#include
#include
int a[20];
class quick
{
int i,j;
public:
void quicksort(int lb,int ub);
};
void quick::quicksort(int lb,int ub)
{
int pivot,temp;
if(lb{
i=lb;
j=ub;
pivot=a[lb];
while(i{
while(a[i]<=pivot)
i++;
while(a[j]>pivot)
j--;
if(i{
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
else
break;
}
a[lb]=a[j];
a[j]=pivot;
quicksort(lb,j-1);
quicksort(j+1,ub);
}
}
void main()
{
quick q;
int i,n;
clrscr();
cout<<"enter n values:";
cin>>n;
cout<<"array elements"<for(i=0;icin>>a[i];
q.quicksort(0,n-1);
cout<<"the sorted array\n";
for(i=0;icout<<" "<getch();
}

6.10.B IMPLEMENT MERGESORT PROGRAM

1. Algorithm Merge sort(low, high)
2. //a[low: high] is a global array to be sorted
3. //small (p) is true if there if there is only one element
4. //to sort in this case the list is already sorted
5. {
6. if(low7. {
8. //divide p into sub problems
9. //find where to split the set
10. mid:=[(low+ high)/2];
11. //solve the sub problems
12. Merge sort (low, mid);
13. Merge sort (mid+1, high);
14. //combines the solutions
15. Merge (low, mid, high);
16. }
17. }

ALGORITHM FOR MERGINGTWO SORTED SUB ARRAYS

1. Algorithm Merge (low, mid, high)
2. //a[low: high] is a global array containing
3. //two sorted subsets in a
4. //[low: mid] and in a[mid+1, high]. The global
5. //is to merge these two sets into a single
6. //set residing in a[low: high] b[] is a
7. // Auxiliary global array
8. {
9. h:=low; i:=low; j:=mid+1;
10. while((h<=mid) and (j<=high)) do
11. {
12. if(a[h]<=a[j]) then
13. {
14. b[i]: = a[h]; h:=h+1;
15. }
16. else

Merge Sort relies on the merge function to merge together two sorted arrays. Merge Sort gets its efficiency from the fact that at most one comparison is needed for each item being merged. Think about merging two decks of cards, A and B, into a third deck C. Decks A and B are assumed to each be already in sorted order. Deck C stars out empty. You compare the top cards from each deck and place the smaller of the two, face down, on the merged deck. When either deck A or deck B becomes empty, you place the entire remaining deck, face down, onto deck C. The key here is that the two decks, A and B are sorted to begin with. At most one comparison is made for each card merged. When one of the decks becomes empty, no further comparisons are done and the entire remining deck is merged in at once. This is the basis for the following merge algorithm. In this algorithm, the "cards" are stored in an array. Deck A is stored in indices low1..high1, inclusive. Deck B is stored in indices low2..high2. We further stipulate that the two "decks" are contiguous in the array (the last card of deck A comes just before the first card of deck B). The mergesort algorithm uses the merge algorithm (below) to sort the entire array. To sort the whole array A, low would be zero and high would be the maximum index in the array.
Sample input and output
Output for merge sort
enter size of list:6
enter the unsorted elements:3
2
1
5
4
6
elements in list are 3 2 1 5 4 6
merge sorted list is 1 2 3 4 5 6

Merge Sort

#include
#include
#include
class mergesort
{
public:
void sort(int *,int,int,int);
void pass(int *,int,int);
};
void mergesort::sort(int l[],int top,int size,int bottom)
{
int temp[10];
int f=top;
int s=size+1;
int t=top;
while((f<=size)&&(s<=bottom))
{
if(l[f]<=l[s])
{
temp[t]=l[f];
f++;
}
else
{
temp[t]=l[s];
s++;
}
t++;
}
if(f<=size)
{
for(f=f;f<=size;f++)
{
temp[t]=l[f];
t++;
}
}
else
{
for(s=s;s<=bottom;s++)
{
temp[t]=l[s];
t++;
}
}
for(int upper=top;upper<=bottom;upper++)
{
l[upper]=temp[upper];
}
}
void mergesort::pass(int append[],int m,int n)
{
if(m!=n)
{
int mid=(m+n)/2;
pass(append,m,mid);
pass(append,mid+1,n);
sort(append,m,mid,n);
}
}
void main()
{
int n,i;
mergesort s;
int list[100];
clrscr();
cout<<"enter size of list:";
cin>>n;
cout<<"enter the unsorted elements:";
for(i=0;i {
cin>>list[i];
}
cout<<"\n elements in list are";
for(i=0;i {
cout<<" "< }
i=0;
s.pass(list,i,n-1);
cout<<"\n merge sorted list is";
for(i=0;i {
cout<<" "< }
}

6.10.C HEAP SORT

#include
#include
#include
#include
int a[20];
class heap
{
public:
void cheap(int *a,int n);
};
void heap::cheap(int a[],int n)
{
int i,parent,child,next;
for(i=2;i<=n;i++)
{
next=a[i];
child=i;
parent=child/2;
while(child>1&&next>a[parent])
{
a[child]=a[parent];
child=parent;
parent=child/2;
if(parent<1)
parent=1;
}
a[child]=next;
}
}
void main()
{
heap h;
int n,i,last,temp;
clrscr();
cout<<"enter n value:";
cin>>n;
cout<<"enter array elements"<for(i=1;i<=n;i++)
cin>>a[i];
h.cheap(a,n);
for(last=n;last>=2;last--)
{temp=a[1];
a[1]=a[last];
a[last]=temp;
h.cheap(a,last-1);
}
cout<<"enter stored elements"<for(i=1;i<=n;i++)
cout<<" "<getch();
}
Heap sort sample input and out put
enter n value:5
enter array elements
2
1
4
3
0
enter stored elements
0 1 2 3 4

6.11 PRIMS ALGORITHM

#include
#include
#include
#include
class ll_node
{
public:
int scr,dest,weight;
ll_node *next;
};
int *parent;
char err[]="some nodes are isolated";
void error(char *msg)
{
puts(msg);
exit(1);
}
void put_sorted(ll_node *phead,ll_node *node)
{
ll_node *prev,*cur;
prev=phead;
cur=phead->next;
while(cur && cur->weight < node->weight)
{
prev=cur;
cur=cur->next;
}
node->next=cur;
prev->next=node;
}
int input(ll_node *phead)
{
int p=0,i,j,n=0,w;
ll_node *node;
char inps[80];
puts("\n input adjacency matrix on node list\n");
do
{
p=1;
cout<<"enter no of nodes:";
cin>>n;
cout<<"input adjacency matrix"< for(i=0;i {
cout<<"row"< for(j=0;j {
cin>>w;
if(w)
{
node=new ll_node;
node->scr=i;
node->dest=j;
node->weight=w;
put_sorted(phead,node);
}
}
}
}while(!p);
return n;
}
int root(int *parent,int node)
{
while(parent[node]!=node)
node=parent[node];
return node;
}
int min_span(ll_node *phead,int n)
{
ll_node *first,*cur,*temp;
int *parent;
int i,root_scr,root_dest,nedges;
parent=new int;
for(i=0;i parent[i]=i;
cur=phead->next;
while(cur && cur->scr==cur->dest)
cur=cur->next;
if(!cur)
error(err);
first=cur;
parent[first->dest]=first->scr;
nedges=1;
cur=first->next;
first->next=NULL;
while(cur||nedges<1)
{
temp=cur->next;
root_scr=root(parent,cur->scr);
root_dest=root(parent,cur->dest);
if(root_dest!=root_scr)
{
cur->next=first;
first=cur;
parent[root_dest]=root_scr;
nedges++;
}
else
delete cur;
cur=temp;
}
phead->next=first;
return nedges;
}
void main()
{
int n;
ll_node head;
ll_node *cur;
clrscr();
head.next=NULL;
n=input(&head);
if(min_span(&head,n)!=n-1)
error(err);
cur=head.next;
cout<<"\nthe minimum spanning tree by prims \n";
while(cur)
{
cout<scr+1<<"-"<dest+1<<"-"<weight;
cur=cur->next;
}
getch();
}

Sample input and output
Output of PRIMS

input adjacency matrix on node list

enter no of nodes:4
input adjacency matrix
row1 0 3 0 6
row2 3 0 4 7
row3 0 4 0 5
row4 6 7 5 0

the minimum spanning tree by prims

4-3-5
3-2-4
2-1-3

6.12 Kruskal Algorithm

#include
#include
#include
#include
#define max(a,b)(a>b?a:b)
class ll_node
{
public:
int src,dest,weight;
ll_node *next;
};
int *parent;
char err[]="Some nodes in the tree are isolated";
void error(char *msg)
{
puts(msg);
exit(1);
}
void put_sorted(ll_node *phead,ll_node *node)
{
ll_node *cur,*prev;
prev=phead;
cur=phead->next;
while(cur && cur->weightweight)
{
prev=cur;
cur=cur->next;
}
node->next=cur;
prev->next=node;
}
int input(ll_node *phead)
{
char c;
int p=0;
int i,j,n=0,w;
ll_node *node;
char inps[80];

do
{
p=1;
cout<<"Input the edges as : ";
cout< gets(inps);
while(sscanf(inps,"%d %d %d",&i,&j,&w)==3)
{
cout< node=new ll_node;
node->src=i-1;
node->dest=j-1;
node->weight=w;
n=max(n,i);
n=max(n,j);
put_sorted(phead,node);
gets(inps);
}
puts(inps);
}while(!p);
return(n);
}
int root(int *parent,int node)
{
while(parent[node]!=node)
node=parent[node];
return node;
}
int min_span(ll_node *phead,int n)
{
ll_node *first,*cur,*temp;
int *parent;
int i,root_src,root_dest,nedges;
parent=new int;
for(i=0;i parent[i]=i;
cur=phead->next;
while(cur && cur->src==cur->dest)
cur=cur->next;
if (!cur)
error(err);
first=cur;
parent[first->dest]=first->src;
nedges=1;
cur=first->next;
first->next=NULL;
while(cur||nedges {
temp=cur->next;
root_src=root(parent,cur->src);
root_dest=root(parent,cur->dest);
if(root_dest!=root_src)
{
cur->next=first;
first=cur;
parent[root_dest]=root_src;
nedges++;
}else
delete cur;
cur=temp;
}
phead->next=first;
return nedges;
}
void main()
{
int n;
ll_node head;
ll_node *cur;
clrscr();
head.next=NULL;
n=input(&head);
if(min_span(&head,n)!=n-1)
error(err);
cur=head.next;
cout<<"The minimum spanning tree has the following edges\n";
while(cur)
{
cout<src+1<<"-"<dest+1<<"-"<weight;
cur=cur->next;
}
}
Output for KRUSHKAL
Input the edges as :
Input non-numerals to terminate 1 2 3
123 2 3 4
234 3 4 5
345 4 1 6
416 4 2 7
427

The minimum spanning tree has the following edges

3-4-5
2-3-4
1-2-3

7.1 PROGRAM TO IMPLEMENT PARAMETERIZED CONSTRUCTORS

#include
#include

class sub
{
int a,b,c,d,e;
public:
sub()
{
a=5;
b=6;
c=40;
d=50;
e=a+b+c+d;
}
sub(int x,int y)
{
a=x;
b=y;
e=a+b;
}
sub(int x,int y,int z)
{
a=x;
b=y;
c=z;
e=a+c+b;
}
void display()
{
cout<<"the sum of numbers is :"< }
};
void main()
{
sub s1,s2(30,40),s3(10,20,30);
s1.display();
s2.display();
s3.display();
getch();
}




OUTPUT :

the sum of numbers is :101
the sum of numbers is :70
the sum of numbers is :60

7.2 PROGRAM TO IMPLEMENT COPY CONSTRUCTORS

#include
#include

class abc
{
int x,y,z;
public:
abc()
{
x=10;
y=20;
}
abc(int a,int b)
{
x=a;
y=b;
}
abc(abc &o)
{
x=o.x;
y=o.y;
}
void display()
{
cout<<"the result of is "< }
};

void main()
{
clrscr();
abc o1,o2(5,10),o3(o2);
o1.display();
o2.display();
cout<<"using copy constructors\n";
o3.display();
getch();
}






OUTPUT :

the result of is 30
the result of is 15
using copy constructors
the result of is 15

7.3 PROGRAM TO IMPLEMENT SINGLE INHERITENCE

#include
#include
class sum
{
int a,b;
public:
void read(int x,int y)
{
a=x;
b=y;
}
void display()
{
cout<<"sum"< }
};
class ABC:public sum
{
int x,y,z;
public:
void read(int a,int b,int c)
{
x=a;y=b; z=c;
}
void display()
{
cout<<"sum="< }
};
void main()
{
sum *p,o1;
ABC o2,*p1;
clrscr();
p=&o1;
p->read(20,30);
p->display();
p1=&o2;
p1->read(20,30,40);
p1->display();
getch();
}

Output: sum50sum=90

7.4 PROGRAM TO IMPLEMENT MULTILEVEL INHERITANCE

#include
#include
#include

class wholesalers
{
public:
char p_name[20];
float cost;
int quantity;
void read()
{
cout<<"ENTER PRODUCT_NAME,PRODUCT_COST,PRODUCT_QUANTITY\n"<cin>>p_name>>cost>>quantity;
}
void write()
{
cout<<"PRODUCT NAME :"<cout<<"PRODUCT COST :"<cout<<"PRODUCT QUANTITY :"<}
};
class retailsalers: public wholesalers
{
int icost;
int t_pieces;
public:
void accept()
{
cout<<"ENTER INCREASE IN COST & NUMBER OF PRODUCTS IN SHOP "<cin>>icost>>t_pieces;
}
void display()
{
cost+=icost;
cout<<"THE COST OF A PRODUCT IN RETAIL SHOP:"<cout<<"REMAINING PRODUCTS :"<}
};
class consumer :public retailsalers
{
int p_consumed,tcost;
public:
void rd()
{
cout<<"ENTER NUMBER OF PRODUCTS CONSUMED"<cin>>p_consumed;
}
void wr()
{
cout<<"PRODUCTS BOUGHT BY CONSUMER :"<tcost=p_consumed*cost;
cout<<"TOTAL COST OF PRODUCTS IS :"<}
};

void main()
{
clrscr();
consumer x;
x.read();
x.accept();
x.rd();
x.write();
x.display();
x.wr();
getch();
}

OUTPUT:

ENTER PRODUCT_NAME,PRODUCT_COST,PRODUCT_QUANTITY

NOTEBOOKS
15
200
ENTER INCREASE IN COST & NUMBER OF PRODUCTS IN SHOP
5
10
ENTER NUMBER OF PRODUCTS CONSUMED
5
PRODUCT NAME :NOTEBOOKS
PRODUCT COST :15
PRODUCT QUANTITY :200
THE COST OF A PRODUCT IN RETAIL SHOP:20
REMAINING PRODUCTS :10
PRODUCTS BOUGHT BY CONSUMER :5
TOTAL COST OF PRODUCTS IS :100

7.5 PROGRAM TO IMPLEMENT MULTIPLE INHERITENCE

#include
#include
#include

class base1
{
protected:
int x;
public:
void showx()
{
cout< }
};

class base2
{
protected:
int y;
public:
void showy()
{
cout< }
};

//INHERIT MULTIPLE BASE CLASSES

class derived:public base1, public base2
{
public:
void set(int i,int j)
{
x=i;
y=j;
}
};

int main()
{
clrscr();
derived ob;
ob.set(10,20); //PROVIDED BY DERIVED
ob.showx(); //FROM BASE1
ob.showy(); //FROM BASE2
getch();
return 0;
}


OUTPUT:
10
20

7.6 PROGRAM TO STUDENTS DATABASE

#include
#include
#include

class student
{
private:
char name[20];
int rno,m1,m2,m3,sum,avg;
public:
void accept()
{
cout<<"\n";
cout<<"Enter student Name,number,marks in three subjects"<<"\n";
cin>>name>>rno>>m1>>m2>>m3;
}
void compute()
{
sum=m1+m2+m3;
avg=sum/3;
}
void display()
{
cout< }
};

void main()
{
clrscr();
student s1,s2;
s1.accept();
s2.accept();
cout<<"\n"<<"STUDENTS DATA"<<"\n";
s1.compute();
s2.compute();
cout<<"\nNAME REG_NO M1 M2 M3 TOTAL AVG\n";
s1.display();
cout< s2.display();
getch();
}


OUTPUT:


Enter student Name,number,marks in three subjects
ravi
567
90
89
90

Enter student Name,number,marks in three subjects
raju
543
78
90
78

STUDENTS DATA

NAME REG_NO M1 M2 M3 TOTAL AVG
ravi 567 90 89 90 269 89
raju 543 78 90 78 246 82

7.7 PROGRAM TO MAINTAIN HOSPITAL DATABASE USING SINGLE INHERITENCE

#include
#include
#include

class hospital
{
char name[20];
char address[40];
int age;
char join[20];
char toi[50];
public:
void read()
{
cout<<"ENTER THE DETAILS\n";
cout<<"ENTER NAME,ADDRESS,AGE,ILLNESS,JOINING_DATE\n";
cin>>name>>address>>age>>toi>>join;
}

void write()
{
cout<<" NAME :"<cout<<"ADDRESS :"<cout<<"AGE :"<cout<<"ILLNESS :"<cout<<"JOINING DATE :"<}
};

class p_details: public hospital
{
int wardno,bedno;
char dod[20];
public:
void accept()
{
cout<<"ENTER WARDNUMBER,BEDNO,DATE OF DISCHARGE\n";
cin>>wardno>>bedno>>dod;
}

void display()
{
cout<<"WARDNUMBER :"<cout<<"BED NUMBER :"<cout<<"DATE OF DISCHARGE :"<}
};

void main()
{
clrscr();
p_details x;
x.read();
x.accept();
cout<x.write();
x.display();
getch();
}

OUTPUT:


ENTER THE DETAILS
ENTER NAME,ADDRESS,AGE,ILLNESS,JOINING_DATE
sanjay
hno389,stno5,hyd
30
tuberculosis
4thjan2004
ENTER WARDNUMBER,BEDNO,DATE OF DISCHARGE
30
10
5thfeb2004


NAME :sanjay
ADDRESS :hno389,stno5,hyd
AGE :30
ILLNESS :tuberculosis
JOINING DATE :4thjan2004
WARDNUMBER :30
BED NUMBER :10
DATE OF DISCHARGE :5thfeb2004

7.8 PROGRAM TO IMPLEMENT OPERATOR OVERLOADING

#include
#include
#include

class ABC
{
int big;
float a,b,c;
public:

ABC(int x,int y)
{
a=x;b=y;
}
ABC()
{
a=20;b=30;
}
ABC operator + (ABC o1)
{
ABC x; x.a=a+o1.a;
x.b=b+o1.b;
return(x);
}
ABC operator - (ABC o1)
{
ABC x;
x.a=a-o1.a;
x.b=b-o1.b;
return(x);
}
ABC operator * (ABC o1)
{
ABC x;
x.a=a*o1.a;
x.b=b*o1.b;
return(x);
}
int operator < (ABC o1)
{
if(a big=o1.a;
else
big=a;
return big;
}
void operator = (ABC o1)
{
a=o1.a;
b=o1.b;
}
ABC operator / (ABC o1)
{
ABC x;
a=a/o1.a;
b=b/o1.b;
return(x);
}
void display()
{
cout< }
};

void main()
{
ABC o1,o2(5,10),o3,o4,o5,o6;
clrscr();
o3=o1+o2;
o4=o1-o2;
o5=o1*o2;
o6=o1/o2;
o1=o3;
o1.display();
o3.display();
o4.display();
o5.display();
o6.display();

getch();
}

Output:
25 40
25 40
15 20
100 300
20 30

7.9 PROGRAM TO IMPLEMENT FUNCTION OVELOADING

#include
#include

class sum{
int x,y,z;
public:
sum()
{
x=10;
y=20;
cout<<"sum="< }
sum(int p,int q)
{
x=p;
y=q;
cout<<"sum="< }
sum(int r,int s,int t)
{
x=r;
y=s;
z=t;
cout<<"sum="< }
};
void main()
{
clrscr();
sum o1;
sum o2(1,2);
sum o3(4,5,6);
getch();
}



OUTPUT:

Sum=30
Sum=3
Sum=15

7.10 PROGRAM TO CONVERT A LOWER CASE CHARACTER TO AN UPPERCASE CHARACTER OF A TEXT FILE

#include
#include
#include
#include
#include
#include

void main()
{
ofstream outfile;
ifstream infile;
char fname1[10],fname2[10];
char ch,uch;
clrscr();
cout<<"enter a file name to be copied?\n";
cin>>fname1;
cout<<"new file name ? \n";
cin>>fname2;
infile.open(fname1);
if (infile.fail())
{
cerr << "No such a file exists \n";
exit(1);
}
outfile.open(fname2);
if(outfile.fail())
{
cerr<< "unable to create a file \n";
exit(1);
}
while(!infile.eof())
{
ch=(char)infile.get();
uch=toupper(ch);
outfile.put(uch);
}
infile.close();
outfile.close();
}//end of main








OUTPUT:

enter a file name to be copied?
xxx.dat
new file name ?
yyy.dat

contents in xxx.dat
abcdefgh

contents in yyy.dat
ABCDEFGH

7.11 PROGRAM TO IMPLEMENT EXCEPTION HANDLING

#include

int main()
{
int x;
cout<<”Enter value of x : ”;
cin>>x;

try
{
if(x==1)
throw(20);
if(x==2)
throw(‘A’);
if(x==3)
throw(2.5f);
}
catch(int p)
{
cout<<”int value x=”< }
catch(char c)
{
cout<<”char value x= “< }
catch(float f)
{
cout<<”float value x= “< }
return 0;
}
OUTPUT:
[itlab@localhost itlab]$ g++ -o mulexc mulexc.cpp
in file included from
/usr/include/c++/3.2.2/backward/iostream.h:31;
from mulexc.cpp:1:
/usr/include/c++/3.2.2/backward/backward_warning,h:32:2:
warning:# warning this
file includes atleast one deprecated or antiquated header.
Please consider using one of the 32 headers found in section 17.4.1.2 of the c++ standard examples
Include substituting the header for the header for c++ includes, or instead of the deprecated header
. To disable this warning use-wno-deprecated.
[itlab@localhost itlab]$ ./mulexc
Enter value of x : 1
int value x=20
[itlab@localhost itlab]$ ./mulexc
Enter value of x : 2
char value x=A
[itlab@localhost itlab]$ ./mulexc
Enter value of x : 3
float value x=2.5

[itlab@localhost itlab]$

7.12 PROGRAM TO FIND SUM OF TWO NUMBERS USING CLASS TEMPLATES

#include

template
class sum
{
T a,b,c;
public:
sum(T x,T y)
{
a=x;
b=y;
}
void read(T p,T q)
{
a=p;
b=q;
}
void read(T p,T q)
{
a=p;
b=q;
}
void display()
{
c=a+b;
cout<<"sum ="< }
};

void main()
{
sum o1(10,20);
sum o2(2.5,3.0);
sum o3(2.0,5.0);
o1.display();
o2.display();
o3.display();
}

OUTPUT :
sum =30
sum =5.5
sum =7

PROGRAM TO IMPLEMENT FUNCTION TEMPLATES

#include
#include
#include

template
void swap1(t a,t b)
{
t temp;
temp=a;
a=b;
b=temp;
cout<}

void main()
{
int c,d;
float e,f;
char g,h;
clrscr();

cout<<"enter values :";
cin>>c>>d>>e>>f>>g>>h;
swap1(c,d);
swap1(e,f);
swap1(g,h);
getch();
}


Output :

enter values :2 3 4.5 6.7 a b
3 2 6.7 4.5 b a

7.13 PROGRAM TO IMPLEMENT BINARY SEARCH

#include
#include

int mid,i,arr[20],l=0,p,max,se;
int binsrch(int,int);

void main()
{
cout<<"ENTER SIZE OF THE ARRAY"<cin>>max;
cout<<"ENTER ELEMENTS IN ASCENDING ORDER"<for(i=l;icin>>arr[i];
cout<<"enter element to be searched"<cin>>se;
p=binsrch(l,max);
if(p==1)
{
cout<<"search is succesful\n";
cout<<"element is found at:" <}
else
cout<<"NOT SUCCESFUL\N";
getch();
}
int binsrch(int low,int high)
{
if(low==high)
{
if(arr[low]==se)
return 1;
else
return 0;
}
else
{
mid=(low+high)/2;
if(arr[mid]==se)
return 1;
else
{
if(se binsrch(low,mid-1);
else
binsrch(mid+1,high);
}
}
}




OUTPUT:

ENTER SIZE OF THE ARRAY
8
ENTER ELEMENTS IN ASCENDING ORDER
-2
0
7
8
23
45
56
78
enter element to be searched
56
search is succesful
element is found at:6

7.14 PROGRAM TO IMPLEMENT JOB SEQUENCING USING GREEDY METHOD

#include
#include
#include
class jobs
{
private:
int *p;
int *d;
int n;
int k;
public:
int retsize(){return k;}
int jobseq(int []);
void readdata(int);
};
void jobs:: readdata(int x)
{
n=x;
p=new int [n+1];
d= new int [n+1];
cout<<"enter the deadlines:\n";
for(int i=1;i<=n;i++)
cin>>d[i];
cout<<"enter the profits:[in descending order]\n";
for(i=1;i<=n;i++)
cin>>p[i];
}
int jobs::jobseq(int j[])
{
int r,t;
int profit=0;
d[0]=0;j[0]=0;
k=1;
j[1]=1;
profit+=p[1];
for(int i=2;i<=n;i++)
{
r=k;
while(d[j[r]]>d[i] && d[j[r]]!=r)
r--;
if((d[j[r]] <=d[i]) && (d[i]>r))
{
for(t=k;t>=r+1;t--)
j[t+1]=j[t];
profit+=p[i];
j[r+1]=i;
k++;
}
}
return profit;
}
void main()
{
jobs obj;
int optsoln;
int n;
int *j;
int s;
clrscr();
cout<<"enter the no of objects:";
cin>>n;
obj.readdata(n);
j=new int [n+1];
optsoln=obj.jobseq(j);
s=obj.retsize();
cout<<"the solution vector:\n";
for(int i=1;i<=s;i++)
cout< cout<< endl;
cout<<"the optimal solution =" << optsoln< }

OUTPUT:

enter the no of objects:4
enter the deadlines:
2 1 2 1
enter the profits:[in descending order]
100 27 15 10
the solution vector:
2 1
the optimal solution =127

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