## Thursday, April 23, 2009

### DATA STRUCTURE PROGRAMS IN C++

Aim: Write a C++ program to find the sparse of a matrix

PROGRAM

#include<iostream.h>
#include<conio.h>

void main()
{
int a[50][50],sp[50][50],i,j,k=0,m,n;
clrscr();
cout<<"\n Enter the order of matrix: ";
cin>>m>>n;
cout<<"\n Enter the elements: ";
for(i=0;i< m;i++)
{
for(j=0;j< n;j++)
{
cin>>a[i][j];
if(a[i][j]!=0)
{
k++;
sp[k][0]=i;
sp[k][1]=j;
sp[k][2]=a[i][j];
}
}
}
sp[0][0]=m;
sp[0][1]=n;
sp[0][2]=k;
cout<<"\n The sparse matrix is:\n";
for(i=0;i<=k;i++)
{
for(j=0;j<3;j++)
cout<< sp[i][j]<<" ";
cout<<"\n";
}
getch();
}

OUTPUT

Enter the order of matrix: 3 3

Enter the elements:
0 1 0
2 0 0
0 0 3

The sparse matrix is:
3 3 3
0 1 1
1 0 2
2 2 3

Aim: Write a C++ program to find the transpose of a matrix using the given sparse matrix

PROGRAM

#include<iostream.h>
#include<conio.h>

void main()
{
int a[50][50],sp[50][50],i,j,k=0,m,n,tsp[50][50],p=0;
clrscr();
cout<<"\n Enter the order of matrix: ";
cin>>m>>n;
cout<<"\n Enter the elements: ";
for(i=0;i< m;i++)
{
for(j=0;j< n;j++)
{
cin>>a[i][j];
if(a[i][j]!=0)
{
k++;
sp[k][0]=i;
sp[k][1]=j;
sp[k][2]=a[i][j];
}
}
}
sp[0][0]=m;
sp[0][1]=n;
sp[0][2]=k;
cout<<"\n The sparse matrix is:\n";
for(i=0;i<=k;i++)
{
for(j=0;j<3;j++)
cout<< sp[i][j]<<" ";
cout<<"\n";
}
p=0;
for(j=0;j< n;j++)
{
for(i=1;i<=k;i++)
{
if(sp[i][1]==j)
{
p++;
tsp[p][0]=sp[i][1];
tsp[p][1]=sp[i][0];
tsp[p][2]=sp[i][2];
}
}
}
tsp[0][0]=sp[0][1];
tsp[0][1]=sp[0][0];
tsp[0][2]=p;
cout<<"\n Transpose of sparse \n";
for(i=0;i<=p;i++)
{
for(j=0;j<3;j++)
cout<< tsp[i][j]<<" ";
cout<<"\n";
}

getch();
}

OUTPUT

Enter the order of matrix: 3 3

Enter the elements:
1 0 0
0 0 2
0 3 0

The sparse matrix is:
3 3 3
0 0 1
1 2 2
2 1 3

Transpose of sparse
3 3 3
0 0 1
1 2 3
2 1 2

Aim: Write a C++ program to find transpose of a matrix using fast transpose method

PROGRAM

#include<iostream.h>
#include<conio.h>

void main()
{
int a[50][50],sp[50][50],i,j,k=0,m,n,t,tsp[50][50];
int start[50],size[50];
clrscr();
cout<<"\n Enter the order of matrix: ";
cin>>m>>n;
cout<<"\n Enter the elements: ";
for(i=0;i< m;i++)
{
for(j=0;j< n;j++)
{
cin>>a[i][j];
if(a[i][j]!=0)
{
k++;
sp[k][0]=i;
sp[k][1]=j;
sp[k][2]=a[i][j];
}
}
}
sp[0][0]=m;
sp[0][1]=n;
sp[0][2]=k;
cout<<"\n The sparse matrix is:\n";
for(i=0;i<=k;i++)
{
for(j=0;j<3;j++)
cout<< sp[i][j]<<" ";
cout<<"\n";
}
for(i=0;i< n;i++)
size[i]=0;

for(i=1;i<=k;i++)
{
t=sp[i][1];
size[t]++;
}
start[0]=1;
for(i=1;i< n;i++)
start[i]=start[i-1]+size[i-1];

for(i=1;i<=k;i++)
{
j=sp[i][1];
t=start[j];
tsp[t][0]=sp[i][1];
tsp[t][1]=sp[i][0];
tsp[t][2]=sp[i][2];
start[j]++;
}

tsp[0][0]=sp[0][1];
tsp[0][1]=sp[0][0];
tsp[0][2]=sp[0][2];
cout<<"\n Transpose \n";
for(i=0;i<=k;i++)
{
for(j=0;j<3;j++)
cout<< tsp[i][j]<<" ";
cout<<"\n";
}
getch();
}

OUTPUT

Enter the order of matrix: 3 3

Enter the elements:
0 1 0
2 0 0
0 0 5

The sparse matrix is:
3 3 3
0 1 1
1 0 2
2 2 5

Transpose
3 3 3
0 1 2
1 0 1
2 2 5

Aim: Write a C++ program to convert the given sparse to original matrix

PROGRAM

#include<iostream.h>
#include<conio.h>
#include<process.h>

void main()
{
int sp[50][50],a[40][40],k,i,j,m,n,r,c;
clrscr();
cout<<"\n Enter the order of sparse matrix: ";
cin>>n;
cout<<"\n Enter the sparse matrix: ";
for(i=0;i< n;i++)
for(j=0;j<3;j++)
cin>>sp[i][j];

if(sp[0][2]!=(n-1))
{
cout<<"\n Error ";
getch();
exit(0);
}

for(i=0;i<40;i++)
for(j=0;j<40;j++)
a[i][j]=0;

m=sp[0][0];
n=sp[0][1];
k=sp[0][2];

for(i=1;i<=k;i++)
{
r=sp[i][0];
c=sp[i][1];
a[r][c]=sp[i][2];
}

cout<<"\n The original matrix is: \n";
for(i=0;i< m;i++)
{
for(j=0;j< n;j++)
cout<< a[i][j]<<" ";
cout<<"\n";
}
getch();
}

OUTPUT

Enter the order of sparse matrix: 4

Enter the sparse matrix:
3 3 3
0 1 2
1 0 1
2 1 3

The original matrix is:
0 2 0
1 0 0
0 3 0

Aim: Write a C++ program to perform sparse matrix addition

PROGRAM

#include”iostream.h”
#include”conio.h”
void main()
{
int num,sp1[50][50],i,j,k1=0,k2=0,k=0,m1,n1,m2,n2,sp2[50][50],sp[50][50];
int m,n;
clrscr();
cout<<"\n Enter the order of matrix1: ";
cin>>m1>>n1;
cout<<"\n Enter the elements: ";
for(i=0;i< m1;i++)
{
for(j=0;j< n1;j++)
{
cin>>num;
if(num!=0)
{
k1++;
sp1[k1][0]=i;
sp1[k1][1]=j;
sp1[k1][2]=num;
}
}
}
sp1[0][0]=m1;
sp1[0][1]=n1;
sp1[0][2]=k1;

cout<<"\n Enter the order of matrix2: ";
cin>>m2>>n2;
cout<<"\n Enter the elements: ";
for(i=0;i< m2;i++)
{
for(j=0;j< n2;j++)
{
cin>>num;
if(num!=0)
{
k2++;
sp2[k2][0]=i;
sp2[k2][1]=j;
sp2[k2][2]=num;
}
}
}
sp2[0][0]=m2;
sp2[0][1]=n2;
sp2[0][2]=k2;
i=1;
j=1;
k=0;
while(i<=k1&&j<=k2)
{
if(sp1[i][0]==sp2[j][0])
{
if(sp1[i][1]< sp2[j][1])
{
k++;
sp[k][0]=sp1[i][0];
sp[k][1]=sp1[i][1];
sp[k][2]=sp1[i][2];
i++;
}
else if(sp1[i][1]>sp2[j][1])
{
k++;
sp[k][0]=sp2[j][0];
sp[k][1]=sp2[j][1];
sp[k][2]=sp2[j][2];
j++;
}
else
{
k++;
sp[k][0]=sp2[j][0];
sp[k][1]=sp2[j][1];
sp[k][2]=sp2[j][2]+sp1[i][2];
j++;i++;
}
}
else if(sp1[i][0]< sp2[j][0])
{
k++;
sp[k][0]=sp1[i][0];
sp[k][1]=sp1[i][1];
sp[k][2]=sp1[i][2];
i++;
}
else if(sp1[i][0]>sp2[j][0])
{
k++;
sp[k][0]=sp2[j][0];
sp[k][1]=sp2[j][1];
sp[k][2]=sp2[j][2];
j++;
}
}
while(i<=k1)
{
k++;
sp[k][0]=sp1[i][0];
sp[k][1]=sp1[i][1];
sp[k][2]=sp1[i][2];
i++;
}
while(j<=k2)
{
k++;
sp[k][0]=sp2[j][0];
sp[k][1]=sp2[j][1];
sp[k][2]=sp2[j][2];
j++;
}
m=((m1>m2)?m1:m2);
n=((n1>n2)?n1:n2);
sp[0][0]=m;
sp[0][1]=n;
sp[0][2]=k;

cout<<"\n The sparse of sum matrix is:\n";
for(i=0;i<=k;i++)
{
for(j=0;j<3;j++)
cout<< sp[i][j]<<" ";
cout<<"\n";
}
getch();
}

OUTPUT

Enter the order of matrix1: 3 3

Enter the elements:
1 0 0
0 5 0
0 0 6

Enter the order of matrix2: 3 3

Enter the elements:
0 5 0
0 6 0
0 0 3

The sparse of sum matrix is:
3 3 4
0 0 1
0 1 5
1 1 11
2 2 9

Aim: Write a C++ program to perform sparse multiplication

PROGRAM

#include”iostream.h”
#include”conio.h”
#include"process.h"

void main()
{
int num,sp1[50][50],mul[50][50],i,j,k1=0,k2=0,k=0,m1,n1,m2,n2,sp2[50][50],sp[50][50];
int m,n,t;
clrscr();
cout<<"\n Enter the order of matrix1: ";
cin>>m1>>n1;
cout<<"\n Enter the elements: ";
for(i=0;i< m1;i++)
{
for(j=0;j< n1;j++)
{
cin>>num;
if(num!=0)
{
k1++;
sp1[k1][0]=i;
sp1[k1][1]=j;
sp1[k1][2]=num;
}
}
}
sp1[0][0]=m1;
sp1[0][1]=n1;
sp1[0][2]=k1;

cout<<"\n Enter the order of matrix2: ";
cin>>m2>>n2;
cout<<"\n Enter the elements: ";
for(i=0;i< m2;i++)
{
for(j=0;j< n2;j++)
{
cin>>num;
if(num!=0)
{
k2++;
sp2[k2][0]=i;
sp2[k2][1]=j;
sp2[k2][2]=num;
}
}
}
sp2[0][0]=m2;
sp2[0][1]=n2;
sp2[0][2]=k2;

if(n1!=m2)
{
cout<<"\n Error ";
getch();
exit(0);
}

k=0;
for(i=1;i<=k1;i++)
{
for(j=1;j<=k2;j++)
{
if(sp1[i][1]==sp2[j][0])
{
k++;
sp[k][0]=sp1[i][0];
sp[k][1]=sp2[j][1];
sp[k][2]=sp1[i][2]*sp2[j][2];
}
}
}

sp[0][2]=k;
sp[0][0]=m1;
sp[0][1]=n2;

t=0;
for(i=0;i< sp[0][0];i++)
{
for(j=0;j< sp[0][1];j++)
{
for(k1=1;k1<=sp[0][2];k1++)
{
if(sp[k1][0]==i&&sp[k1][1]==j)
{
t++;
mul[t][0]=sp[k1][0];
mul[t][1]=sp[k1][1];
mul[t][2]=sp[k1][2];
}
}
}
}

mul[0][2]=k;
mul[0][0]=m1;
mul[0][1]=n2;

cout<<"\n The sparse of product matrix is:\n";
for(i=0;i<=t;i++)
{
for(j=0;j<3;j++)
cout<< mul[i][j]<<" ";
cout<<"\n";
}

getch();
}

OUTPUT

Enter the order of matrix1: 3 3

Enter the elements:
2 0 9
0 1 0
0 0 2

Enter the order of matrix2: 3 3

Enter the elements:
0 0 3
1 0 1
2 1 0

The sparse of product matrix is:
3 3 7
0 0 18
0 1 9
0 2 6
1 0 1
1 2 1
2 0 4
2 1 2

Aim: Write a C++ program to convert an infix expression to postfix and evaluate

PROGRAM

#include"iostream.h"
#include"conio.h"
#include"stdio.h"
#include"ctype.h"
#include"string.h"
#include"process.h"
#include"math.h"

int top=-1;
int stack[50];
int p;
void evaluate(char [],int);

void display(char a[],int n)
{
int i;
for(i=0;i<=n;i++)
{
cout<< a[i];
}
cout<<"\n";
}

void inpst(char q[])
{
char stk[50],tp[50],op,ot;
int s=-1,p=-1,j,k,l,h,flg1,flg2;
char pcdn[6]={'-','+','/','*','^','\0'};
int pval[5]={1,1,2,2,3};

for(int i=0;q[i]!='\0';i++)
{
flg1=flg2=-1;
if(isalpha(q[i]))
{
p++;
tp[p]=q[i];

}

else if(q[i]=='(')
{
s++;
stk[s]=q[i];

}

else if(q[i]==')')
{
for(j=s;j>=0;j--)
{
if(stk[s]=='(')
break;

if(stk[j]!='(')
{
p++;
tp[p]=stk[j];

s--;

}
}

s--;

}

else
{
op=q[i];
flg1=-1;
/* to find precedence value */
for(h=0;pcdn[h]!='\0';h++)
{
if(op==pcdn[h])
{
flg1=pval[h];
break;
}
}

/* check for higher precedence operator */

for(k=s;k>=0;k--)
{
flg2=-1;
ot=stk[k];

for(h=0;pcdn[h]!='\0';h++)
{
if(ot==pcdn[h])
{
flg2=pval[h];
break;
}
}

if(flg2>flg1)
{
p++;
tp[p]=ot;
for(l=k;l {
stk[k]=stk[k+1];
}
s--;

}

}
s++;
stk[s]=op;
}
}

while(s>=0)
{
p++;
tp[p]=stk[s];
s--;
}

cout<<"\n The post fix expression is: ";
display(tp,p);

evaluate(tp,p);
}

int result(int a,int b,char op)
{
int c=0;

switch(op)
{
case '+': c=a+b; break;
case '-': c=a-b; break;
case '*': c=a*b; break;
case '/': if(b!=0)
c=a/b;
else
{
cout<<"\n Error: ";
getch();
exit(0);
}
break;
case '^':c=(int)pow(a,b); break;
case '%':c=a%b; break;
}
return c;
}

void push(int item)
{
stack[++top]=item;
}

int pop()
{
int s;
if(top>=0)
{
s=stack[top];
top--;
return s;
}
else
return 0;
}

void evaluate(char post[],int p)
{
int a,b,v=0,q;
top=-1;

for(int i=0;i<=p;i++)
{
if(isalpha(post[i]))
{
cout<<"\n Enter value for "<< post[i]<<": ";
cin>>q;
push(q);
continue;
}
else
{
a=pop();
b=pop();
v=result(a,b,post[i]);
push(v);
}
a=b=0;
}

}

void main()
{
char q[50];
clrscr();
cout<<"\n Enter the infix expression: ";
gets(q);
inpst(q);
cout<<"\n Value of expression "<< stack[top];
getch();
}

OUTPUT

Enter the infix expression: a*b+c*d

The post fix expression is: ab*cd*+

Enter value for a: 2

Enter value for b: 3

Enter value for c: 4

Enter value for d: 5

Value of expression 26

Aim: Write a C++ program to implement stack operations

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

int stk[50],top=-1,i,j,max,num,ch;

void push()
{
top++;
cout<<"\n Enter the item: ";
cin>>num;
stk[top]=num;
}

void pop()
{
cout<<"\n Popped "<< stk[top];
top--;
}

void display()
{
cout<<"\n ---------------------\n";
cout<<"TOP>> ";
for(i=top;i>=0;i--)
cout<< stk[i]<<" ";
cout<<"\n ---------------------";
}
void main()
{

clrscr();
cout<<"\n Enter the limit: ";
cin>>max;
do
{
cout<<"\n\n STACK\n";
cout<<"\n1.Push\n2.Pop\n3.Display\n4.Exit";
cout<<"\n Enter the choice: ";
cin>>ch;
switch(ch)
{
case 1:if(top>=max-1)
{
cout<<"\n Stack full: ";
continue;
}
push();
break;
case 2:if(top==-1)
{
cout<<"\n Stack empty: ";
continue;
}
pop();
break;
case 3:display();
break;
case 4:cout<<".......Thanking you.......";
getch();
exit(0);
default:cout<<"\n INVALID KEY-IN ";
}
}while(1);

}

OUTPUT

Enter the limit: 3

STACK

1.Push
2.Pop
3.Display
4.Exit
Enter the choice: 1

Enter the item: 23

STACK

1.Push
2.Pop
3.Display
4.Exit
Enter the choice: 1

Enter the item: 96

STACK

1.Push
2.Pop
3.Display
4.Exit
Enter the choice: 3

---------------------
TOP>> 96 56 23
---------------------

STACK

1.Push
2.Pop
3.Display
4.Exit
Enter the choice: 2

Popped 96

STACK

1.Push
2.Pop
3.Display
4.Exit
Enter the choice: 3

---------------------
TOP>> 56 23
---------------------

STACK

1.Push
2.Pop
3.Display
4.Exit
Enter the choice: 4
.......Thanking you.......

Aim: Write a C++ program to reverse a string using stack

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"
#include"string.h"

void revstk(char str[])
{
char stk[50];
int top,i;
for(i=0;str[i]!='\0';i++)
stk[i]=str[i];

top=--i;
cout<<"\n Reversed string: ";
for(i=top;i>=0;i--)
cout<< stk[i];

return;
}

void main()
{
char str[50];
clrscr();
cout<<"\n Enter a string:";
gets(str);
revstk(str);
getch();
}

OUTPUT

Enter a string:english

Reversed string: hsilgne

Aim: Write a C++ program to implement simple queue operations

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

int que[50],rear=-1,front=-1,i,j,max,num,ch;

void insert()
{
rear++;
cout<<"\n Enter the item: ";
cin>>num;
que[rear]=num;
if(front==-1)
front=0;
}

void delet()
{
cout<<"\n Deleted "<< que[front];
if(front==rear)
front=rear=-1;
else
front++;
}

void display()
{
if(front==-1)
{
cout<<"\n\t\t\t QUEUE EMPTY ";
return;
}
cout<<"\n -----------------------------\n";
cout<<"FRONT>> ";
for(i=front;i<=rear;i++)
cout<< que[i]<<" ";
cout<<" << REAR";
cout<<"\n -----------------------------";
}
void main()
{

clrscr();
cout<<"\n Enter the limit: ";
cin>>max;
do
{
cout<<"\n\n SIMPLE QUEUE\n";
cout<<"\n1.Insert\n2.Delete\n3.Display\n4.Exit";
cout<<"\n Enter the choice: ";
cin>>ch;
switch(ch)
{
case 1:if(rear+1>max-1)
{
cout<<"\n\t\t\t Queue full: ";
continue;
}
insert();
break;
case 2:if(front==-1||front>rear)
{
cout<<"\n\t\t\t Queue empty: ";
continue;
}
delet();
break;
case 3:display();
break;
case 4:cout<<".......Thanking you.......";
getch();
exit(0);
default:cout<<"\n\t\t\t INVALID KEY-IN ";
}
}while(1);

}

OUTPUT

Enter the limit: 2

SIMPLE QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 23

SIMPLE QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 96

SIMPLE QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 3

-----------------------------
FRONT>> 23 96 << REAR
-----------------------------

SIMPLE QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 2

Deleted 23

SIMPLE QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 3

-----------------------------
FRONT>> 96 << REAR
-----------------------------

SIMPLE QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 4
.......Thanking you.......

Aim: Write a C++ program to implement circular queue operations

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

int que[50],rear=-1,front=-1,i,j,max,num,ch;

void insert()
{
rear=(rear+1)%max;
cout<<"\n Enter the item: ";
cin>>num;
que[rear]=num;
if(front==-1)
front=0;
}

void delet()
{
cout<<"\n Deleted "<< que[front];
if(front==rear)
front=rear=-1;
else
front=(front+1)%max;
}

void display()
{
if(front==-1)
{
cout<<"\n QUEUE EMPTY ";
return;
}
cout<<"\n -----------------------------\n";
cout<<"FRONT>> ";
if(rear< front)
{
for(i=front;i< max;i++)
cout<< que[i]<<" ";
for(i=0;i<=rear;i++)
cout<< que[i]<<" ";
}
else
for(i=front;i<=rear;i++)
cout<< que[i]<<" ";
cout<<" << REAR";
cout<<"\n -----------------------------";
}
void main()
{
clrscr();
cout<<"\n Enter the limit: ";
cin>>max;
do
{
cout<<"\n\n CIRCULAR QUEUE\n";
cout<<"\n1.Insert\n2.Delete\n3.Display\n4.Exit";
cout<<"\n Enter the choice: ";
cin>>ch;
switch(ch)
{
case 1:if((front==(rear+1)%max))
{
cout<<"\n Queue full: ";
continue;
}
insert();
break;
case 2:if(front==-1)
{
cout<<"\n Queue empty: ";
continue;
}
delet();
break;
case 3:display();
break;
case 4:cout<<".......Thanking you.......";
getch();
exit(0);
default:cout<<"\n INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

Enter the limit: 2

CIRCULAR QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 44

CIRCULAR QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 56

CIRCULAR QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 3

-----------------------------
FRONT>> 44 56 << REAR
-----------------------------

CIRCULAR QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 2

Deleted 44

CIRCULAR QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 99

CIRCULAR QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 3

-----------------------------
FRONT>> 56 99 << REAR
-----------------------------

CIRCULAR QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 4
.......Thanking you.......

Aim: Write a C++ program to implement double ended queue operations

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

int que[50],rear=-1,front=-1,i,j,max,num,ch;

void r_insert()
{
rear++;
cout<<"\n Enter the item: ";
cin>>num;
que[rear]=num;
if(front==-1)
front=0;
}

void f_insert()
{
if(front==-1)
front=rear=0;
else if(front>0)
front--;

cout<<"\n Enter the item: ";
cin>>num;
que[front]=num;

}

void r_delet()
{
cout<<"\n Deleted "<< que[rear];
if(front==rear)
front=rear=-1;
else
rear--;
}

void f_delet()
{
cout<<"\n Deleted "<< que[front];
if(front==rear)
front=rear=-1;
else
front++;
}

void display()
{
if(front==-1)
{
cout<<"\n\t\t\t QUEUE EMPTY ";
return;
}
cout<<"\n -----------------------------\n";
cout<<"FRONT>> ";
for(i=front;i<=rear;i++)
cout<< que[i]<<" ";
cout<<" << REAR";
cout<<"\n -----------------------------";
}
void main()
{

clrscr();
cout<<"\n Enter the limit: ";
cin>>max;
do
{
cout<<"\n\n DE-QUEUE\n";
cout<<"\n1.Insert at rear\n2.Insert at front\n3.Delete at front\n4.Delete at rear\n5.Display\n6.Exit";
cout<<"\n Enter the choice: ";
cin>>ch;
switch(ch)
{
case 1:if(rear+1>max-1)
{
cout<<"\n\t\t\t Queue full: ";
continue;
}
r_insert();
break;
case 2:if(front==0)
{
cout<<"\n\t\t\t Cannot insert: ";
continue;
}
f_insert();
break;
case 3:if(front==-1||front>rear)
{
cout<<"\n\t\t\t Queue empty: ";
continue;
}
f_delet();
break;
case 4:if(front==-1||front>rear)
{
cout<<"\n\t\t\t Queue empty: ";
continue;
}
r_delet();
break;
case 5:display();
break;
case 6:cout<<".......Thanking you.......";
getch();
exit(0);
default:cout<<"\n\t\t\t INVALID KEY-IN ";
}
}while(1);

}

OUTPUT

Enter the limit: 3

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit

Enter the choice: 2

Enter the item: 23

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit
Enter the choice: 1

Enter the item: 44

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit
Enter the choice: 1

Enter the item: 96

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit
Enter the choice: 5

-----------------------------
FRONT>> 23 44 96 << REAR
-----------------------------

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit
Enter the choice: 3

Deleted 23

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit
Enter the choice: 4

Deleted 96

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit
Enter the choice: 5

-----------------------------
FRONT>> 44 << REAR
-----------------------------

DE-QUEUE

1.Insert at rear
2.Insert at front
3.Delete at front
4.Delete at rear
5.Display
6.Exit
Enter the choice: 6
.......Thanking you.......

Aim: Write a C++ program to implement priority queue operations

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

int que[50],rear=-1,front=-1,i,j,max,item,ch;
struct p_que
{
int num;
int pr;
};
class pro
{
public:
void insert(p_que ob[]);
void delet(p_que ob[]);
void display(p_que ob[]);
};

void pro::insert(p_que ob[])
{
rear++;
cout<<"\n Enter the item: ";
cin>>item;
ob[rear].num=item;
cout<<"\n Enter the priority: ";
cin>>ob[rear].pr;
if(front==-1)
front=0;
}

void pro::delet(p_que ob[])
{
p_que temp;
int big=ob[front].pr;
int p=0;
for(int i=front+1;i<=rear;i++)
{
if(ob[i].pr>big)
{
big=ob[i].pr;
p=i;
}
}

for(i=p;i<=rear;i++)
{
ob[i].num=ob[i+1].num;
ob[i].pr=ob[i+1].pr;
}

if(front==rear)
front=rear=-1;
else
rear--;
}

void pro::display(p_que ob[])
{
if(front==-1)
{
cout<<"\n\t\t\t QUEUE EMPTY ";
return;
}
cout<<"\n -----------------------------\n\n";
cout<<"FRONT>> Pr ";
for(i=front;i<=rear;i++)
printf("%3d",ob[i].pr);
cout<<" << REAR";
cout<<"\n\n Data";
for(i=front;i<=rear;i++)
printf("%3d",ob[i].num);

cout<<"\n -----------------------------";
}

void main()
{
p_que o[50];
pro pp;
clrscr();
cout<<"\n Enter the limit: ";
cin>>max;
do
{
cout<<"\n\n PRIORITY QUEUE\n";
cout<<"\n1.Insert\n2.Delete\n3.Display\n4.Exit";
cout<<"\n Enter the choice: ";
cin>>ch;
switch(ch)
{
case 1:if(rear+1>max-1)
{
cout<<"\n\t\t\t Queue full: ";
continue;
}
pp.insert(o);
break;
case 2:if(front==-1||front>rear)
{
cout<<"\n\t\t\t Queue empty: ";
continue;
}
pp.delet(o);
break;
case 3:pp.display(o);
break;
case 4:cout<<".......Thanking you.......";
getch();
exit(0);
default:cout<<"\n\t\t\t INVALID KEY-IN ";
}
}while(1);

}

OUTPUT

Enter the limit: 3

PRIORITY QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 23

Enter the priority: 5

PRIORITY QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 44

Enter the priority: 6

PRIORITY QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 1

Enter the item: 96

Enter the priority: 7

PRIORITY QUEUE

1.Insert
2.Delete
3.Display
4.Exit

Enter the choice: 3

-----------------------------

FRONT>> Pr 5 6 7 << REAR

Data 23 44 96
-----------------------------

PRIORITY QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 2

PRIORITY QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 3

-----------------------------

FRONT>> Pr 5 6 << REAR

Data 23 44
-----------------------------

PRIORITY QUEUE

1.Insert
2.Delete
3.Display
4.Exit
Enter the choice: 4
.......Thanking you.......

Aim: Write a C++ program to represent a polynomial

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class poly
{
int i,n;
struct rep
{
int co;
int ex;
}r[10];

public:
void disp();
};

{
cout<<"\n Enter the number of terms in the polynomial: ";
cin>>n;
cout<<"\n Enter the coefficient and exponent: ";

for(i=0;i< n;i++)
{
cout<<"\n Term "<< i+1<<": ";
cin>>r[i].co>>r[i].ex;
}
}

void poly::disp()
{
cout<<"\nThe polynomial is:\n\n";
for(i=0;i< n-1;i++)
{
cout<< r[i].co<<"x^"<< r[i].ex<<"+";
}
cout<< r[i].co<<"x^"<< r[i].ex;
}

void main()
{
clrscr();
poly ob;
ob.disp();
getch();
}

OUTPUT

Enter the number of terms in the polynomial: 3

Enter the coefficient and exponent:
Term 1: 5 2

Term 2: 6 1

Term 3: 7 0

The polynomial is:

5x^2+6x^1+7x^0

Aim: Write a C++ program to perform polynomial addition

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class poly
{
int i,n;
struct rep
{
int co;
int ex;
}r[10];

public:
void sum(poly,poly);
void disp();
};

{
cout<<"\n Enter the number of terms in the polynomial: ";
cin>>n;
cout<<"\n Enter the coefficient and exponent: ";

for(i=0;i< n;i++)
{
cout<<"\n Term "<< i+1<<": ";
cin>>r[i].co>>r[i].ex;
}
}

void poly::disp()
{
cout<<"\n.........................\n";
for(i=0;i< n-1;i++)
{
cout<< r[i].co<<"x^"<< r[i].ex<<"+";
}
cout<< r[i].co<<"x^"<< r[i].ex;
cout<<"\n\n";
}

void poly::sum(poly c1,poly c2)
{
int i=0,j=0,k=0,t;

while(i< c1.n&&j< c2.n)
{//1
if(c1.r[i].ex==c2.r[j].ex)
{
r[k].co=c1.r[i].co+c2.r[j].co;
r[k].ex=c1.r[i].ex;
i++,j++,k++;
}

else if(c1.r[i].ex>c2.r[j].ex)
{
r[k].co=c1.r[i].co;
r[k].ex=c1.r[i].ex;
i++,k++;
}

else if(c1.r[i].ex< c2.r[j].ex)
{
r[k].co=c2.r[j].co;
r[k].ex=c2.r[j].ex;
j++,k++;
}
}//1

while(i< c1.n)
{
r[k].co=c1.r[i].co;
r[k].ex=c1.r[i].ex;
i++,k++;
}

while(j< c2.n)
{
r[k].co=c2.r[j].co;
r[k].ex=c2.r[j].ex;
j++,k++;
}
n=k--;

}

void main()
{
clrscr();
poly c1,c2,c3;
cout<<"\n Polynomial 1: ";
c1.disp();
cout<<"\n Polynomial 2: ";
c2.disp();
c3.sum(c1,c2);
cout<<"\n Sum polynomial : ";
c3.disp();
getch();
}

OUTPUT

Enter the number of terms in the polynomial: 3

Enter the coefficient and exponent:
Term 1: 4 2

Term 2: 5 1

Term 3: 3 0

Enter the number of terms in the polynomial: 2

Enter the coefficient and exponent:
Term 1: 8 3

Term 2: 5 1

Polynomial 1:
.........................
4x^2+5x^1+3x^0

Polynomial 2:
.........................
8x^3+5x^1

Sum polynomial :
.........................
8x^3+4x^2+10x^1+3x^0

Aim: Write a C++ program to implement a singly linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class node
{
int data;
node *next;
public:
void display();
void insertend();
void insertbeg();
void insertsp();
void delbeg();
void delend();
void delsp();
};

void node::display()
{
temp=start;
cout<<"\n Data list: ";
while(temp!=NULL)
{
cout<< temp->data<<" ";
temp=temp->next;
}
}

void node::insertbeg()
{
cout<<"\n Enter the data: ";

if(start==NULL)
{
}
else
{
}
}

void node::insertend()
{
cout<<"\n Enter the data: ";

if(start==NULL)
{
}
else
{
temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
}
}
}

void node::insertsp()
{
int pos,i;
cout<<"\n Enter the data: ";
cout<<"\n Enter the position: ";
cin>>pos;
if(pos==1)
insertbeg();
else
{
temp=start;
for(i=1;i< pos-1;i++)
{
temp=temp->next;
}

}
}

void node::delbeg()
{
if(start==NULL)
cout<<"\n LIST EMPTY ";
else
{
//temp=start;
cout<< start->data;
start=start->next;
delete temp;
}
}

void node::delend()
{
temp=start;
if(start==NULL)
cout<<"\n LIST EMPTY ";

else if(temp->next==NULL)
{
cout<< temp->data;
start=NULL;
delete temp;
}

else
{
while(temp->next!=NULL)
{
t=temp;
temp=temp->next;
}
cout<< temp->data;
t->next=NULL;
delete temp;
}
}

void node::delsp()
{

if(start==NULL)
{
cout<<"\n LIST EMPTY ";
return;
}

int num;
cout<<"\n Enter the item: ";
cin>>num;
temp=start;
while(temp!=NULL)
{
if(temp->data==num)
{
if(temp==start)
delbeg();
else
{
cout<< temp->data;
t->next=temp->next;
delete temp;
}
}
else
{
t=temp;
temp=temp->next;
}

}
}

void main()
{
int ch;
node ob;
start=NULL;
clrscr();
do
{
//clrscr();
cout<<"\n1.INSERT AT BEGINNING\n2.INSERT AT END\n3.INSERT AT A SPECIFIED POSITION";
cout<<"\n4.DELETION FROM BEGINNING\n5.DELETION FROM END\n6.DELETION FROM A SPECIFIED POSITION";
cout<<"\n7.DISPLAY\n8.EXIT\n\n";
cin>>ch;
switch(ch)
{
case 1:ob.insertbeg();break;
case 2:ob.insertend();break;
case 3:ob.insertsp();break;
case 4:ob.delbeg();break;
case 5:ob.delend();break;
case 6:ob.delsp();break;
case 7:ob.display();break;
case 8:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 23

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 44

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 56

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 99

Enter the position: 2

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 44 99 23 56

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

44

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

56

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the item: 23
23

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 99

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

....THANKS....

Aim: Write a C++ program to implement a circular linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"
#define MAX 25
class node
{
int data;
node *next;
public:
void display();
void insertend();
void insertbeg();
void insertsp();
void delbeg();
void delend();
void delsp();
};

void node::display()
{
temp=start;
cout<<"\n Data list: ";
while(temp!=last)
{
cout<< temp->data<<" ";
temp=temp->next;
}
cout<< last->data;
}

void node::insertbeg()
{
cout<<"\n Enter the data: ";

if(start==NULL)
{
last->next=NULL;
}
else
{
}
}

void node::insertend()
{
cout<<"\n Enter the data: ";

if(start==NULL)
{
}
else
{
}
}

void node::insertsp()
{
int pos,i;
cout<<"\n Enter the data: ";
cout<<"\n Enter the position: ";
cin>>pos;
if(pos==1)
{
insertbeg();
return;
}
else
{
temp=start;
for(i=1;i< pos-1;i++)
{
temp=temp->next;
}

}
}

void node::delbeg()
{

if(start==NULL)
cout<<"\n LIST EMPTY ";

else if(start->next==start)
{
temp=start;
cout<< temp->data;
start=last=NULL;
delete temp;
}
else
{
temp=start;
cout<< start->data;
start=start->next;
last->next=start;
delete temp;
}
}

void node::delend()
{
temp=start;
if(start==NULL)
cout<<"\n LIST EMPTY ";
else if(start->next==start)
{
temp=start;
cout<< temp->data;
start=last=NULL;
delete temp;
}
else
{
temp=start;
if(temp->next!=last)
{
temp=temp->next;
}
t=last;
cout<< t->data;
temp->next=start;
last=temp;
delete t;
}
}

void node::delsp()
{

if(start==NULL)
{
cout<<"\n LIST EMPTY ";
return;
}

int item;
cout<<"\n Enter the item: ";
cin>>item;
int i=0;
for(temp=start;i< MAX;i++,t=temp,temp=temp->next)
{
if(temp->data==item)
{
if(temp==start)
{
delbeg();
return;
}
else if(temp==last)
{
delend();
return;
}
else
{
t->next=temp->next;
delete temp;
return;
}
}

}
}

void main()
{
int ch;
node ob;
start=last=NULL;
clrscr();
do
{
cout<<"\n1.INSERT AT BEGINNING\n2.INSERT AT END\n3.INSERT AT A SPECIFIED POSITION";
cout<<"\n4.DELETION FROM BEGINNING\n5.DELETION FROM END\n6.DELETION FROM A SPECIFIED POSITION";
cout<<"\n7.DISPLAY\n8.EXIT\n\n";
cin>>ch;
switch(ch)
{
case 1:ob.insertbeg();break;
case 2:ob.insertend();break;
case 3:ob.insertsp();break;
case 4:ob.delbeg();break;
case 5:ob.delend();break;
case 6:ob.delsp();break;
case 7:ob.display();break;
case 8:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 25

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 47

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 58

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 101

Enter the position: 2

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 47 101 25 58

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

47

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

58

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the item: 25
25

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 101

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

....THANKS....

Aim: Write a C++ program to implement a doubly linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class node
{
int data;
node *next;
node *prev;
public:
void display();
void insertend();
void insertbeg();
void insertsp();
void delbeg();
void delend();
void delsp();
};

void node::display()
{
temp=start;
if(start==NULL)
{
cout<<"\n LIST EMPTY ";
return;
}
cout<<"\n Data list: ";
while(temp!=last)
{
cout<< temp->data<<" ";
temp=temp->next;
}
cout<< last->data;
}

void node::insertbeg()
{
cout<<"\n Enter the data: ";
if(start==NULL)
{
}
else
{
}
}

void node::insertend()
{
cout<<"\n Enter the data: ";
if(start==NULL)
{
}
else
{
}
}

void node::insertsp()
{
int pos,i;
cout<<"\n Enter the position: ";
cin>>pos;
if(pos==1)
insertbeg();
else
{
cout<<"\n Enter the data: ";
temp=start;
for(i=1;i< pos-1;i++)
{
temp=temp->next;
}
if(temp->next==NULL)

}
}

void node::delbeg()
{
if(start==NULL)
cout<<"\n LIST EMPTY ";
else if(start==last)
{
cout<< start->data;
temp=start;
start=last=NULL;
delete temp;
}
else
{
temp=start;
cout<< start->data;
start=start->next;
start->prev=NULL;
delete temp;
}
}

void node::delend()
{
temp=start;
if(start==NULL)
cout<<"\n LIST EMPTY ";
else if(start==last)
{
cout<< last->data;
temp=last;
start=last=NULL;
delete temp;
}

else
{
temp=last;
cout<< last->data;
last=last->prev;
last->next=NULL;
delete temp;
}
}

void node::delsp()
{

if(start==NULL)
{
cout<<"\n LIST EMPTY ";
return;
}

int num;
cout<<"\n Enter the item: ";
cin>>num;
temp=start;
while(temp!=NULL)
{
if(temp->data==num)
{
if(temp==start)
{
delbeg();
return;
}
else if(temp==last)
{
delend();
return;
}

else
{
cout<< temp->data;
t1=temp->prev;
t2=temp->next;
t1->next=t2;
t2->prev=t1;
delete temp;
}
}
else
{
temp=temp->next;
}
}
}

void main()
{
int ch;
node ob;
start=last=NULL;
clrscr();
do
{
cout<<"\n1.INSERT AT BEGINNING\n2.INSERT AT END\n3.INSERT AT A SPECIFIED
POSITION";
cout<<"\n4.DELETION FROM BEGINNING\n5.DELETION FROM END\n6.DELETION
FROM A SPECIFIED POSITION";
cout<<"\n7.DISPLAY\n8.EXIT\n";
cin>>ch;

switch(ch)
{
case 1:ob.insertbeg();break;
case 2:ob.insertend();break;
case 3:ob.insertsp();break;
case 4:ob.delbeg();break;
case 5:ob.delend();break;
case 6:ob.delsp();break;
case 7:ob.display();break;
case 8:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 45

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 25

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 96

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the position: 3

Enter the data: 56

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 25 45 56 96

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

25

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

96

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the item: 56

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 45

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

....THANKS....

Aim: Write a C++ program to implement a circular doubly linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class node
{
int data;
node *next;
node *prev;
public:
node(){}
void create();
void display();
void insertend();
void insertbeg();
void insertsp();
void delbeg();
void delend();
void delsp();
};

node *temp,*t,*curr,*t1,*t2;

void node::create()
{
}

void node::display()
{
cout<<"\n DATA LIST EMPTY ";
else
{
cout<<"\n Data list: ";
{
temp=temp->next;
cout<< temp->data<<" ";
}
}

}

void node::insertbeg()
{
curr=new node;
cout<<"\n Enter the data: ";
cin>>curr->data;
{
return;
}
curr->next=temp;
temp->prev=curr;

}

void node::insertend()
{
curr=new node;
cout<<"\n Enter the data: ";
cin>>curr->data;
curr->prev=temp;
temp->next=curr;
}

void node::insertsp()
{
int pos,k;
cout<<"\n Enter the position: ";
cin>>pos;
if(pos==1)
insertbeg();
else
{
for(k=1;k< pos;k++)
{
temp=temp->next;
}
curr=new node;
cout<<"\n Enter the data: ";
cin>>curr->data;
t=temp->next;
temp->next=curr;
curr->prev=temp;
curr->next=t;
t->prev=curr;
}

}

void node::delbeg()
{
cout<<"\n DELETION IMPOSSIBLE ";

else
{
cout<< temp->data;
delete temp;
}
}

void node::delend()
{
cout<<"\n DELETION IMPOSSIBLE ";

else
{
cout<< temp->data;
delete temp;
}
}

void node::delsp()
{
{
cout<<"\n DELETION IMPOSSIBLE ";
return;
}
else
{
int item;
cout<<"\n Enter the item: ";
cin>>item;
do
{
if(temp->data==item)
{
{
delbeg();
return;
}
{
delend();
return;
}
else
{
t1=temp->prev;
t2=temp->next;
t1->next=t2;
t2->prev=t1;
delete temp;
return;
}
}
else
{
temp=temp->next;
}
}

}

void main()
{
int ch;
node ob;
clrscr();
ob.create();
do
{
cout<<"\n1.INSERT AT BEGINNING\n2.INSERT AT END\n3.INSERT AT A SPECIFIED POSITION";
cout<<"\n4.DELETION FROM BEGINNING\n5.DELETION FROM END\n6.DELETION FROM A SPECIFIED POSITION";
cout<<"\n7.DISPLAY\n8.EXIT\n\n";
cin>>ch;
switch(ch)
{
case 1:ob.insertbeg();break;
case 2:ob.insertend();break;
case 3:ob.insertsp();break;
case 4:ob.delbeg();break;
case 5:ob.delend();break;
case 6:ob.delsp();break;
case 7:ob.display();break;
case 8:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);

}

OUTPUT

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 21

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 41

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the data: 51

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the position: 2

Enter the data: 91

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 41 91 21 51

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

41

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

51

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Enter the item: 21
21

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

Data list: 91

1.INSERT AT BEGINNING
2.INSERT AT END
3.INSERT AT A SPECIFIED POSITION
4.DELETION FROM BEGINNING
5.DELETION FROM END
6.DELETION FROM A SPECIFIED POSITION
7.DISPLAY
8.EXIT

....THANKS....

Aim: Write a C++ program to implement a stack using linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class node
{
int data;
node *next;
public:
void display();
void push();
void pop();
};

void node::display()
{
temp=start;
if(temp==NULL)
cout<<"\n STACK EMPTY ";
else
cout<<"\n STACK: ";
while(temp!=NULL)
{
cout<< temp->data<<" ";
temp=temp->next;
}
}

void node::push()
{
cout<<"\n Enter the data: ";

if(start==NULL)
{
}
else
{
temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
}
}
}

void node::pop()
{
temp=start;
if(start==NULL)
cout<<"\n STACK EMPTY ";

else if(temp->next==NULL)
{
cout<< temp->data;
start=NULL;
delete temp;
}

else
{
while(temp->next!=NULL)
{
t=temp;
temp=temp->next;
}
cout<< temp->data;
t->next=NULL;
delete temp;
}
}

void main()
{
int ch;
node ob;
start=NULL;
clrscr();
do
{

cout<<"\n1.PUSH\n2.POP\n3.DISPLAY\n4.EXIT\n\n";
cin>>ch;
switch(ch)
{
case 1:ob.push();break;
case 2:ob.pop();break;
case 3:ob.display();break;
case 4:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

1.PUSH
2.POP
3.DISPLAY
4.EXIT

Enter the data: 23

1.PUSH
2.POP
3.DISPLAY
4.EXIT

Enter the data: 45

1.PUSH
2.POP
3.DISPLAY
4.EXIT

STACK: 23 45

1.PUSH
2.POP
3.DISPLAY
4.EXIT

45

1.PUSH
2.POP
3.DISPLAY
4.EXIT

STACK: 23

1.PUSH
2.POP
3.DISPLAY
4.EXIT

....THANKS....

Aim: Write a C++ program to implement a simple queue using linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class node
{
int data;
node *next;
public:
void display();
void insert();
void del();
};

void node::display()
{
temp=start;
if(temp==NULL)
cout<<"\n QUEUE EMPTY ";
else
cout<<"\n QUEUE: ";
while(temp!=NULL)
{
cout<< temp->data<<" ";
temp=temp->next;
}
}

void node::insert()
{
cout<<"\n Enter the data: ";

if(start==NULL)
{
}
else
{
temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
}
}
}

void node::del()
{
if(start==NULL)
cout<<"\n QUEUE EMPTY ";
else
{
temp=start;
cout<< start->data;
start=start->next;
delete temp;
}
}

void main()
{
int ch;
node ob;
start=NULL;
clrscr();
do
{
cout<<"\n1.INSERTION\n2.DELETION\n3.DISPLAY\n4.EXIT\n";
cin>>ch;
switch(ch)
{
case 1:ob.insert();break;
case 2:ob.del();break;
case 3:ob.display();break;
case 4:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Enter the data: 25

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Enter the data: 50

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

QUEUE: 25 50

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

25

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

QUEUE: 50

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

....THANKS....

Aim: Write a C++ program to implement a circular queue using linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class node
{
int data;
node *next;
public:
node(){}
void display();
void insert();
void del();
};

void node::display()
{
temp=start;
cout<<"\n Data list: ";
while(temp!=last)
{
cout<< temp->data<<" ";
temp=temp->next;
}
cout<< last->data;
}

void node::insert()
{
cout<<"\n Enter the data: ";

if(start==NULL)
{
}
else
{
}

}

void node::del()
{

if(start==NULL)
cout<<"\n LIST EMPTY ";

else if(start->next==start)
{
temp=start;
cout<< temp->data;
start=last=NULL;
delete temp;

}
else
{
temp=start;
cout<< start->data;
start=start->next;
last->next=start;
delete temp;
}
}

void main()
{
int ch;
node ob;
start=last=NULL;

clrscr();
do
{
cout<<"\n\n\t...CIRCULAR QUEUE USING LL...\n";
cout<<"\n1.INSERTION\n2.DELETION\n3.DISPLAY\n4.EXIT\n\n";
cin>>ch;
switch(ch)
{
case 1:ob.insert();break;
case 2:ob.del();break;
case 3:ob.display();break;
case 4:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

...CIRCULAR QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Enter the data: 23

...CIRCULAR QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Enter the data: 44

...CIRCULAR QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Data list: 23 44

...CIRCULAR QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

23

...CIRCULAR QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Data list: 44

...CIRCULAR QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

....THANKS....

Aim: Write a C++ program to implement a priority queue using linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

class node
{
int data;
int prty;
node *next;
public:
void display();
void insert();
void del();
void delbeg();
};

void node::display()
{

temp=start;
cout<<"\n Data list: ";

while(temp!=NULL)
{
printf("%3d ",temp->data);
temp=temp->next;
}

temp=start;
cout<<"\n Priority: ";

while(temp!=NULL)
{
printf("%3d ",temp->prty);
temp=temp->next;
}

}

void node::insert()
{

cout<<"\n Enter the data: ";
cout<<"\n Enter the priority: ";

if(start==NULL)
{
}

else
{
temp=start;
while(temp->next!=NULL)
{
temp=temp->next;
}

}

}

void node::delbeg()
{
if(start==NULL)
cout<<"\n LIST EMPTY ";
else
{
cout<< start->data;
start=start->next;
delete temp;
}
}

void node::del()
{

if(start==NULL)
{
cout<<"\n LIST EMPTY ";
return;
}

int lp;
temp=start;
lp=temp->prty;

while(temp!=NULL)
{
if(temp->prty>lp)
{
lp=temp->prty;
}
temp=temp->next;
}

temp=start;
while(temp!=NULL)
{
if(temp->prty==lp)
{
if(temp==start)
{
delbeg();
return;
}
else
{
cout<< temp->data;
t->next=temp->next;
delete temp;
return;
}
}
else
{
t=temp;
temp=temp->next;
}

}
}

void main()
{
int ch;
node ob;
start=NULL;
clrscr();
do
{
cout<<"\n\n\t...PRIORITY QUEUE USING LL...\n";
cout<<"\n1.INSERTION\n2.DELETION\n3.DISPLAY\n4.EXIT\n\n";
cin>>ch;
switch(ch)
{
case 1:ob.insert();break;
case 2:ob.del();break;
case 3:ob.display();break;
case 4:cout<<"\n\t ....THANKS....";
getch();
exit(0);
default:cout<<"\n\t INVALID KEY-IN ";
}
}while(1);
}

OUTPUT

...PRIORITY QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Enter the data: 23

Enter the priority: 5

...PRIORITY QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Enter the data: 96

Enter the priority: 6

...PRIORITY QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Data list: 23 96
Priority: 5 6

...PRIORITY QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

96

...PRIORITY QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

Data list: 23
Priority: 5

...PRIORITY QUEUE USING LL...

1.INSERTION
2.DELETION
3.DISPLAY
4.EXIT

....THANKS....

Aim: Write a C++ program to perform polynomial addition using linked list

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”

struct node
{
int co,exp;
node *next;
};

class poly
{
public:
poly()
{
start=NULL;
}
void create();
void display();
};

void poly::create()
{
int n;
do
{
cout<<"\n Enter values for coefficient and exponent: ";
goto PROCEED;
else if(start==NULL)
else
{
}

PROCEED:
cout<<"\n Continue? ,then press \"1\":";
cin>>n;
}while(n==1);
}

void poly::display()
{
temp=start;
cout<<"\n\n........................................\n\n\n\t";
while(temp->next!=NULL)
{
cout<< temp->co<<"x^"<< temp->exp<<"+";
temp=temp->next;
}
cout<< temp->co<<"x^"<< temp->exp;
cout<<"\n\n........................................\n";
}

{
r1.temp=r1.start;
r2.temp=r2.start;
while(r1.temp!=NULL&&r2.temp!=NULL)
{
if(r1.temp->exp>r2.temp->exp)
{
if(start==NULL)
else
{
}
r1.temp=r1.temp->next;
}

else if(r1.temp->expexp)
{
if(start==NULL)
else
{
}
r2.temp=r2.temp->next;
}

else
{
if(start==NULL)
else
{
}
r1.temp=r1.temp->next;
r2.temp=r2.temp->next;
}
}

while(r1.temp!=NULL)
{
if(start==NULL)
else
{
}
r1.temp=r1.temp->next;
}

while(r2.temp!=NULL)
{
if(start==NULL)
else
{
}
r2.temp=r2.temp->next;
}

}

void main()
{
poly p1,p2,p3;
clrscr();
cout<<"\n First polynomial...";
p1.create();
cout<<"\n Second polynomial...";
p2.create();
p3.display();
getch();
}

OUTPUT

First polynomial...
Enter values for coefficient and exponent: 4 3

Continue? ,then press "1":1

Enter values for coefficient and exponent: 5 2

Continue? ,then press "1":1

Enter values for coefficient and exponent: 3 1

Continue? ,then press "1":1

Enter values for coefficient and exponent: 6 0

Continue? ,then press "1":0

Second polynomial...
Enter values for coefficient and exponent: 3 3

Continue? ,then press "1":1

Enter values for coefficient and exponent: 2 2

Continue? ,then press "1":1

Enter values for coefficient and exponent: 3 1

Continue? ,then press "1":1

Enter values for coefficient and exponent: 1 0

Continue? ,then press "1":0

. . . . . . . . . . . . . . . . .

7x^3+7x^2+6x^1+7x^0

. . . . . . . . . . . . . . . . .

Aim: Write a C++ program to implement a binary tree

PROGRAM

#include
#include
#include

struct node
{
char data;
node *lchild,*rchild;
};

class tree
{
node *root;
public:
tree()
{
root=NULL;
}
node * makenode(char);
void createtree(node *);
void inorder(node *);
void preorder(node *);
void postorder(node *);
};

{
char item;
cout<<"\n Enter data: ";
cin>>item;
root=makenode(item);
createtree(root);
return root;
}

node * tree::makenode(char x)
{
}

void tree::createtree(node *root)
{
int ch;
char item;
if(root!=NULL)
{
cout<<"\n Create left child for "<< root->data<<" (if so press \"1\")";
cin>>ch;
if(ch==1)
{
cout<<"\n Enter data: ";
cin>>item;
root->lchild=makenode(item);
createtree(root->lchild);
}

cout<<"\n Create right child for "<< root->data<<" (if so press \"1\")";
cin>>ch;
if(ch==1)
{
cout<<"\n Enter data: ";
cin>>item;
root->rchild=makenode(item);
createtree(root->rchild);
}
}
}

void tree::inorder(node *root)
{
if(root!=NULL)
{
inorder(root->lchild);
cout<< root->data<<" ";
inorder(root->rchild);
}
}

void tree::preorder(node *root)
{
if(root!=NULL)
{
cout<< root->data<<" ";
preorder(root->lchild);
preorder(root->rchild);
}
}

void tree::postorder(node *root)
{
if(root!=NULL)
{
postorder(root->lchild);
postorder(root->rchild);
cout<< root->data<<" ";
}
}

void main()
{
tree ob;
node *root;
int ch;
clrscr();
do
{
cout<<"\n\n.... BINARY TREE ....\n\n";
cout<<"\n1.Creation\n2.Inorder Traversal\n3.Preorder Traversal";
cout<<"\n4.Postorder Traversal\n5.Exit";
cin>>ch;
switch(ch)
{
break;
case 2:ob.inorder(root);
break;
case 3:ob.preorder(root);
break;
case 4:ob.postorder(root);
break;
case 5:cout<<"\n\n\t... Thanking You ...";
getch();
exit(0);
default:cout<<"\n Invalid key-in ";
}

}while(1);

}

OUTPUT

.... BINARY TREE ....

1.Creation
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Exit

Enter data: A

Create left child for A (if so press "1")1

Enter data: B

Create left child for B (if so press "1")1

Enter data: C

Create left child for C (if so press "1")0

Create right child for C (if so press "1")0

Create right child for B (if so press "1")1

Enter data: D

Create left child for D (if so press "1")0

Create right child for D (if so press "1")0

Create right child for A (if so press "1")1

Enter data: E

Create left child for E (if so press "1")0

Create right child for E (if so press "1")0

.... BINARY TREE ....

1.Creation
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Exit
C B D A E

.... BINARY TREE ....

1.Creation
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Exit
A B C D E

.... BINARY TREE ....

1.Creation
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Exit
C D B E A

.... BINARY TREE ....

1.Creation
2.Inorder Traversal
3.Preorder Traversal
4.Postorder Traversal
5.Exit

... Thanking You ...

Aim: Write a C++ program to implement Binary Search Tree

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"stdio.h"

struct node
{
int data;
node *left;
node *right;
};

node *root;

class bst
{
public:
bst()
{
root=NULL;
}
node *insert(node *,int);
void delet(node *,node*);
void search(node *,int);
node *find(node *,int);

};

node * bst::insert(node *root,int item)
{
if(root==NULL)
{
root=new node;
root->data=item;
root->left=root->right=NULL;
}
else if(itemdata)
root->left=insert(root->left,item);
else
root->right=insert(root->right,item);

return root;

}
void bst::search(node *root,int item)
{
if(root==NULL)
cout<<"\n Number doesnot exist ";
else if(root->data==item)
cout<<"\n Number is present ";
else if(itemdata)
search(root->left,item);
else
search(root->right,item);

}

node *bst::find(node *root,int item)
{
node *temp;
temp=root;
node *parent;
while(root!=NULL)
{
if(itemdata)
{
parent=root;
root=root->left;
}
else if(item>root->data)
{
parent=root;
root=root->right;
}
else
{
delet(root,parent);
break;
}
}
if(root==NULL)
{
cout<<"\n Item doesnot exist ";
}

return temp;

}

void bst::delet(node *root,node *parent)
{

if(root->left==NULL&&root->right==NULL)//terminal node
{
if(parent->left==root)
parent->left=NULL;
else
parent->right=NULL;

return;
}

else if(root->left!=NULL&&root->right!=NULL)//node with 2 childs
{
node *ptr,*temp;
parent=root;
temp=root->left;
ptr=root->right;
if(ptr->left==NULL)
{
root->data=ptr->data;
}
while(ptr->left!=NULL)
{
parent=ptr;
ptr=ptr->left;
root->data=ptr->data;
}
root->left=temp;
delete ptr;

return;

}

else//node with 1 child
{
if(parent->left==root)
{
if(root->left==NULL)
parent->left=root->right;
else
parent->left=root->left;
}
else if(parent->right==root)
{
if(root->left==NULL)
parent->right=root->right;
else
parent->right=root->left;
}
return;
}

}

void main()
{
clrscr();
bst ob;
int item,ch;
node *temp;
do
{
cout<<"\n\n ... BINARY SEARCH TREE ... ";
cout<<"\n\n1.Insertion\n2.Deletion\n3.Searching\n4.Exit";
cin>>ch;

switch(ch)
{
case 1: cout<<"\n Enter an item: "; cin>>item;
root=ob.insert(root,item);
break;
case 2: cout<<"\n Enter the item: "; cin>>item;
root=ob.find(root,item);
break;
case 3: cout<<"\n Enter the item: "; cin>>item;
ob.search(root,item);
break;
case 4: cout<<"\n ... Thanking You ...";
getch();
exit(0);
default:cout<<"\n Invalid key-in ";

}

}while(1);

}

OUTPUT

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter an item: 25

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter an item: 10

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter an item: 20

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter an item: 5

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter an item: 35

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter an item: 32

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter the item: 10

Number is present

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter the item: 10

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

Enter the item: 10

Number doesnot exist

... BINARY SEARCH TREE ...

1.Insertion
2.Deletion
3.Searching
4.Exit

... Thanking You ...

Aim: Write a C++ program to create and evaluate an Expression Tree

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”
#include"ctype.h"
#include"stdio.h"

struct node
{
char data;
node *lchild;
node *rchild;
};

char p[50];
node *stack[50];
int top=-1;
float c;
float v;
node *q;

class tree
{
node *root;
public:
tree(){ }
float evaluate(node *);
node *makenode(char);
void createtree();
void push(node *);
node *pop();
float result(float,float,char);
};

void tree::createtree()
{
int i=0;
while(p[i]!='\0')
{
root=makenode(p[i]);
if(!isalpha(p[i]))
{
root->rchild=pop();
root->lchild=pop();
}

push(root);
i++;
}

}

void tree::push(node *root)
{
top++;
stack[top]=root;
}

node *tree::pop()
{
q=stack[top];
top--;
return q;
}

node * tree::makenode(char x)
{
}

float tree::evaluate(node *root)
{
float a,b;
if(!isalpha(root->lchild->data))
a=evaluate(root->lchild);
else
{
cout<<"\n Enter the value for "<< root->lchild->data<<": ";
cin>>a;
}

if(!isalpha(root->rchild->data))
b=evaluate(root->rchild);
else
{
cout<<"\n Enter the value for "<< root->rchild->data<<": ";
cin>>b;
}

v=result(a,b,root->data);
return v;

}

float tree::result(float a,float b,char op)
{
float c=0;

switch(op)
{
case '+': c=a+b; break;
case '-': c=a-b; break;
case '*': c=a*b; break;
case '/': if(b!=0)
c=a/b;
else
{
cout<<"\n Error: ";
getch();
exit(0);
}
break;
}

return c;
}

void main()
{
clrscr();
float ans;
cout<<"\n Enter a postfix expression: ";
gets(p);
tree ob;
ob.createtree();
ans=ob.evaluate(stack[top]);
cout<<"\n Value of the expression is: "<< ans;
getch();

}

OUTPUT

Enter a postfix expression: ab/cd/*

Enter the value for a: 15

Enter the value for b: 5

Enter the value for c: 20

Enter the value for d: 4

Value of the expression is: 15

Aim: Write a C++ program to implement various Sorting techniques

PROGRAM

#include"iostream.h"
#include"conio.h"
#include"process.h"

int item;

void display(int a[],int n)
{
cout<<"\n Sorted elements are: \n";

for(int i=0;i< n;i++)
cout<< a[i]<<" ";
}

void bubblesort(int a[],int n)
{
int i,j,t;
for(i=0;i< n;i++)
{
for(j=0;j< n-1-i;j++)
{
if(a[j]>a[j+1])
{
t=a[j];
a[j]=a[j+1];
a[j+1]=t;
}
}
}

}

void seletionsort(int a[],int n)
{
int i,j,t;
for(i=0;i< n;i++)
{
for(j=i+1;j< n;j++)
{
if(a[i]>a[j])
{
t=a[i];
a[i]=a[j];
a[j]=t;
}
}
}

}

void insertionsort(int a[],int n)
{
int k,j,t;
for(k=1;k< n;k++)
{
t=a[k];
j=k-1;
while(t< a[j]&&j>=0)
{
a[j+1]=a[j];
j--;
}
a[j+1]=t;
}

}

void quicksort(int a[],int low,int high)
{
int l,h,key,t;
l=low;
h=high;
key=a[(low+high)/2];

do
{
while(key>a[low])
low++;
while(key< a[high])
high--;
if(low<=high)
{
t=a[low];
a[low++]=a[high];
a[high--]=t;
}

}while(low<=high);

if(l< high)
quicksort(a,l,high);

if(low< h)
quicksort(a,low,h);

}

void bucketsort(int a[],int n)
{
int i,j,pass,k,l,div=1,num=0,large=a[0];
int buck[10],q[15][15];

for(i=1;i< n;i++)
{
if(a[i]>large)
large=a[i];
}

while(large>0)
{
num++;
large=large/10;
}

for(pass=0;pass< num;pass++)
{
for(k=0;k<10;k++)
buck[k]=0;

for(i=0;i< n;i++)
{
l=(a[i]/div)%10;
q[l][buck[l]]=a[i];
buck[l]++;
}
i=0;

for(k=0;k<10;k++)
for(j=0;j< buck[k];j++)
{
a[i]=q[k][j];
i++;
}

div=div*10;
}

}

void merge(int a[],int low,int mid,int high)
{
int i,h,j,b[30],k;
i=low;
h=low;
j=mid+1;

while(h<=mid&&j<=high)
{
if(a[h]< a[j])
{
b[i]=a[h];
h++;
}
else
{
b[i]=a[j];
j++;
}
i++;
}

if(h>mid)
{
for(k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}

for(k=low;k<=high;k++)
{
a[k]=b[k];
}

}

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,mid,high);
}

}
/* for tree sort */
struct node
{
int data;
node *left;
node *right;
};

node *root;

class bst
{
public:
bst()
{
root=NULL;
}
node *insert(node *,int);

};

node * bst::insert(node *root,int item)
{
if(root==NULL)
{
root=new node;
root->data=item;
root->left=root->right=NULL;
}
else if(itemdata)
root->left=insert(root->left,item);
else
root->right=insert(root->right,item);

return root;

}

void inorder(node *root)
{
if(root!=NULL)
{
inorder(root->left);
cout<< root->data<<" ";
inorder(root->right);
}
}

void treesort(int a[],int n)
{
node *root;
bst ob;
for(int i=0;i< n;i++)
{
root=ob.insert(root,a[i]);
}
cout<<"\n Sorted elements are: \n";
inorder(root);
}

/* end of tree sort */

void heapsort(int a[],int n)
{
int i,s,f,item,value;
for(i=0;i< n;i++)
{
item=a[i];
s=i;
f=(s-1)/2;
while(s>0&&a[f]< item)
{
a[s]=a[f];
s=f;
f=(s-1)/2;
}
a[s]=item;
}

for(i=n-1;i>0;i--)
{
value=a[i];
a[i]=a[0];
f=0;
if(i==1)
s=-1;
else
s=1;
if(i>2&&a[2]>a[1])
s=2;

while(s>=0&&value< a[s])
{
a[f]=a[s];
f=s;
s=2*f+1;
if(s+1<=i-1&&a[s] s=s+1;
if(s>i-1)
s=-1;
}

a[f]=value;
}

}

void main()
{

int a[50],num[50],n,i,flag=1,ch,low,high;
clrscr();
do
{
cout<<"\n..... SORTING ....\n\n";
cout<<"\n1.BUBBLE SORT\n2.SELECTION SORT\n3.INSERTION SORT\n4.QUICK SORT";
cin>>ch;

if(ch>=1&&ch<=8&&flag==1)
{
cout<<"\n Enter the limit: ";
cin>>n;
cout<<"\n Enter the elements: ";
for(i=0;i< n;i++)
{
cin>>a[i];
}
flag=0;
}

for(i=0;i< n;i++)
num[i]=a[i];

switch(ch)
{
case 1:bubblesort(num,n);
break;
case 2:seletionsort(num,n);
break;
case 3:insertionsort(num,n);
break;
case 4:low=0;high=n-1;
quicksort(num,low,high);
break;
case 5:bucketsort(num,n);
break;
case 6:low=0;high=n-1;
mergesort(num,low,high);
break;
case 7:flag=0;
treesort(num,n);
break;
case 8:heapsort(num,n);
break;
case 9:cout<<"\n\t .....Thanking You .....";
getch();
exit(0);
default:cout<<"\n\t Invalid key-in ";
}

if(ch>=1&&ch<=8&&ch!=7)
{
display(num,n);
}

}while(1);

}

OUTPUT

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Enter the limit: 5

Enter the elements: 99 12 56 3 4

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

Sorted elements are:
3 4 12 56 99

..... SORTING ....

1.BUBBLE SORT
2.SELECTION SORT
3.INSERTION SORT
4.QUICK SORT
6.MERGE SORT
7.TREE SORT
8.HEAP SORT
9.EXIT

.....Thanking You .....

Aim: Write a C++ program to implement various Searching techniques

PROGRAM

#include”iostream.h”
#include”conio.h”
#include”process.h”

void sequential(int a[],int n,int item)
{
int flag=0,i;
for(i=0;i< n;i++)
{
if(a[i]==item)
{
cout<<"\n Item is found at position "<< i+1;
flag=1;
break;
}
}

}

void binary(int a[],int n,int item)
{
int loc=-1,b=0,e=n-1,mid=-1;
while((b<=e)&&(a[mid]!=item))
{
mid=(b+e)/2;
if(item==a[mid])
{
cout<<"\n Item is found at position "<< mid+1;
loc=mid;
}
else if(item< a[mid])
e=mid-1;
else
b=mid+1;
}

}

void main()
{
int num[50],n,item,ch,flag=1,i;
clrscr();
do
{
cout<<"\n\n\n .... SEARCHING .... \n\n\n";
cout<<"\n1.Sequential Search\n2.Binary Search\n3.Enter another list\n4.Exit";
cin>>ch;

if(ch==3) flag=1;

if(ch>=1&&ch<=3&&flag==1)
{
cout<<"\n Enter the limit: ";
cin>>n;
cout<<"\n Enter the elements: ";
for(i=0;i< n;i++)
cin>>num[i];
}
if(ch>=1&&ch<=2)
{
cout<<"\n Enter the element to be searched: ";
cin>>item;
}

switch(ch)
{
case 1:sequential(num,n,item);
break;
case 2:binary(num,n,item);
break;
case 3:break;
case 4:cout<<"\n\t.... Thanking You .... ";
getch();
exit(0);
default:cout<<"\n\t Invalid key-in";
}
flag=0;

}while(1);

}

OUTPUT

.... SEARCHING ....

1.Sequential Search
2.Binary Search
3.Enter another list
4.Exit

Enter the limit: 5

Enter the elements: 12 56 10 45 96

Enter the element to be searched: 10

Item is found at position 3

.... SEARCHING ....

1.Sequential Search
2.Binary Search
3.Enter another list
4.Exit

Enter the limit: 5

Enter the elements: 10 20 30 40 50

.... SEARCHING ....

1.Sequential Search
2.Binary Search
3.Enter another list
4.Exit

Enter the element to be searched: 40

Item is found at position 4

....SEARCHING ....

1.Sequential Search
2.Binary Search
3.Enter another list
4.Exit

.... Thanking You ....

## Contact Form

Name

Email *

Message *

### The Insane Techie - Android App

Launched an android app for the blog on 07th June 2016. Get it from google play store... Tips for using the app Use in landscape mo...