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();
}