//DOUBLY LINKED LIST
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
struct Doubly
{
int info;
struct Doubly*next;
struct Doubly*previous;
};
class linked
{
public:
int no,dnode,search;
Doubly first,*new1;
public:
void create(Doubly*);
void insert(Doubly*);
void delet(Doubly*);
void display(Doubly*);
};
void linked::create(Doubly*node)
{
first.next=NULL;
first.previous=NULL;
node=&first;
no=0;
cout<<"\n input choice b for break: ";
char ch=getche();
while(ch!='b')
{
node->next=(Doubly*)malloc(sizeof(Doubly));
node->next->previous=node;
node=node->next;
cout<<"\n Input the values of the node: "<<(no+1)<<":";
cin>>node->info;
node->next=NULL;
cout<<"\n Input choice b for break;";
ch=getche();
no++;
}
cout<<"\n total node="<<no;
}
void linked::delet(Doubly*node)
{
search=0;
cout<<"Enter the node to be delete: ";
cin>>dnode;
node=first.next;
if(node==NULL)
{
cout<<"\n underflow\nList is empty\n";
}
else
{
while(node)
{
if((search+1)==dnode)
{
node->previous->next=node->next;
node->next->previous=node->previous;
free(node);
}
else
{
node=node->next;
}
search++;
}
}
node=node->next;
}
void linked::insert(Doubly*node)
{
new1=(Doubly*)malloc(sizeof(Doubly));
cout<<"\n insert the node value";
cin>>new1->info;
node=first.next;
if(node==NULL)
{
cout<<"\n list is empty";
}
else
{
new1->next=node;
new1->previous=node->previous;
node->previous->next=new1;
node->previous=new1;
}
}
void linked::display(Doubly*node)
{
node=first.next;
do
{
cout<<"\n";
cout<<""<<node->info;
node=node->next;
}
while(node->next);
do
{
cout<<"\n";
cout<<""<<node->info;
node=node->previous;
}
while(node->previous);
getch();
}
void main()
{
linked l;
int zy,t;
clrscr();
cout<<"\n\t\t Creating a simple Doubly linked list";
cout<<"\n\t\t *****************************\n";
Doubly*node=(Doubly*)malloc(sizeof(Doubly));
do
{
cout<<"\1. Create\n2. Insert New Node\n3. Display
\n5. Exit\nEnter ur choice: ";
cin>>zy;
switch(zy)
{
case 1:
l.create(node);
cout<<"\n Create doubly linked list is as follows\n";
l.display(node);
break;
case 2:
cout<<"\t\t inserting some nodes\n\n";
l.insert(node);
case 3:
cout<<"\n Insert node doubly linked list is as follows\n";
l.display(node);
break;
case 4:
cout<<"\t\tDelete nodes\n\n";
l.delet(node);
break;
case 5:
break;
}
}
while(zy!=5);
getch();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// STACK USING ARRAY
#include<iostream.h>
#include<conio.h>
#include<ctype.h>
int max=5;
class stack
{
int stack[10],top;
public:
int i;
stack()
{
top=-1;
}
void push();
void pop();
void disp();
};
void stack::push()
{
int p;
if(top==max-1)
cout<<"\nstack is full";
else
{
cout<<"Enter the value\n";
cin>>p;
top=top+1;
stack[top]=p;
}
}
void stack::pop()
{
if(top==-1)
cout<<"stack is empty";
else
{
cout<<"The deleted element is"<<stack[top]<<"\n";
top--;
}
}
void stack::disp()
{
if(top==-1)
cout<<"stack is empty";
else
{
cout<<"Element in stack\n";
for(i=0;i<=top;i++)
cout<<stack[i]<<"\n";
}
cout<<"\n";
}
void main()
{
int ch;
clrscr();
stack s;
cout<<"\nSTACK IN ARRAY";
cout<<"1.push\n";
cout<<"2.pop\n";
cout<<"3.disp\n";
cout<<"4.exit\n";
do
{
cout<<"Enter your choice";
cin>>ch;
do
{
cout<<"Enter your choice";
cin>>ch;
switch(ch)
{
case 1:
s.push();
break;
case 2:
s.pop();
break;
case 3:
s.disp();
break;
}
}
while(ch!=4);
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
SINGLE LINKED LIST
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
struct link
{
int info;
struct link *next;
};
class insert
{
private:
int i,number;
link start,*previous,*new1;
public:
void insertion(link *);
void create(link *);
void display(link *);
void dele(link *);
};
void insert::create(link *node)
{
start.next=NULL;
node=&start;
i=0;
cout<<"\ninput choice n for break;";
char ch=getche();
while(ch!='n')
{
node->next=(struct link *)malloc(sizeof(struct link));
node=node->next;
cout<<"\n input node:"<<(i+1)<<":";
cin>>node->info;
node->next=NULL;
cout<<"\ninput choice n for break:";
ch=getche();
i++;
}
}
void insert::insertion(link *node)
{
node=start.next;
previous=&start;
new1=(struct link *)malloc(sizeof(struct link));
new1->next=node;
previous->next=new1;
cout<<"\ninput the first node value:";
cin>>new1->info;
}
void insert::display(link *node)
{node=start.next;
cout<<"\nafter inserting a node list is a follows:\n";
while(node)
{
cout<<"\n"<<node;
cout<<" "<<node->info;
cout<<"\t"<<node->info;
node=node->next;
}
}
void insert::dele(link *node)
{
node=start.next;
previous=&start;
if(node==NULL)
cout<<"\nunder flow\n";
else
{
previous->next=node->next;
free(node);
}
}
void main()
{
int t;
clrscr();
insert in;
link *node=(link *)malloc(sizeof(link));
do
{
cout<<"\n1.creat\n2.insertion\n3.display\n4.delete\n5.exit\n";
cout<<"\n enter ur choice:";
cin>>t;
switch(t)
{
case 1:
in.create(node);
case 2:
in.insertion(node);
break;
case 3:
in.display(node);
break;
case 4:
in.dele(node);
break;
case 5:
cout<<"\nur choice is wrong"<<endl;
break;
}
}
while(t<5);
getch();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
QUEUE USING POINTER
#include<iostream.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int data;
node *link;
};
struct q1
{
node *front;
node *rear;
node *link;
};
struct queue
{
q1 q;
node *t;
public:
void intialise()
{
q.front=NULL;
q.rear=NULL;
}
void addq();
void delq();
void displayq();
};
void queue::addq()
{
t=new(node);
cout<<"enter item to add";
cin>>t->data;
cout<<"item added is:"<<t->data;
t->link=NULL;
if((q.rear)==NULL)
q.front=t;
else
q.rear->link=t;
q.rear=t;
}
void queue::delq()
{
if(q.front==NULL)
{
cout<<"Queue is empty";
q.rear=NULL;
}
else
{
t=q.front;
cout<<"item deleted is"<<q.front->data;
q.front=q.front->link;
free(t);
}
}
void queue::displayq()
{
if(q.front==NULL)
cout<<"queue is empty";
else
{
cout<<"\n front";
for(t=q.front;t!=NULL;t=t->link)
cout<<"==>"<<t->data;
cout<<"<==REAR\n";
}
}
void main()
{
int choice;
queue qu;
clrscr();
qu.intialise();
cout<<"\n\t1-add\n\t2-delete\n\t3-display\n\t4-exit";
do
{
cout<<"\n Enter your choice:\t";
cin>>choice;
switch(choice)
{
case 1:
qu.addq();
break;
case 2:
qu.delq();
break;
case 3:
qu.displayq();
break;
case 4:
break;
default:
cout<<"invalid choice";
}
}
while(choice!=4);
getch();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
// POLYNOMIAL
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
void line(int lines);
class subpoly
{
private:
int degree;
int *coeff;
public:
subpoly()
{
degree=0;
coeff=new int[1];
}
subpoly(int deg)
{
degree=deg;
coeff=new int[deg+1];
}
subpoly(const subpoly &A);
void get(istream &in);
int Coeff(int deg);
void display(ostream &out);
friend subpoly operator -(subpoly &A, subpoly &B);
};
void main()
{
subpoly A(3);
subpoly B(3);
clrscr();
cout<<"Enter he value for first polynomial:\n";
A.get(cin);
cout<<"Enter the value for second polynomial:\n";
B.get(cin);
cout<<"\n First polynomial=";
A.display(cout);
line(2);
cout<<"\n Second polynomial=";
B.display(cout);
line(2);
subpoly C(3);
C=A-B;
cout<<"\nSubtraction polynomial=";
C.display(cout);
getch();
}
subpoly operator-(subpoly &A, subpoly &B)
{
subpoly C;
if(A.degree==B.degree)
{
C=A;
for(int i=B.degree;i>=0;i--)
{
C.coeff[i]=A.coeff[i]-B.coeff[i];
}
return C;
}
else if(A.degree<B.degree)
{
C=B;
for(int i=A.degree;i>0;i--)
{
C.coeff[i]=B.coeff[i];
}
return C;
}
else if(A.degree>B.degree)
{
C=A;
for(int i=A.degree;i>=0;i--)
{
C.coeff[i]=A.coeff[i];
}
return C;
}
return 0;
}
int subpoly::Coeff(int deg)
{
return coeff[deg];
}
void line(int lines)
{
for(int i=0;i<lines;i++)
cout<<endl;
}
void subpoly::get(istream &in)
{
for(int i=degree; i>=0;i--)
{
cin>>coeff[i];
}
in.ignore();
}
void subpoly::display(ostream &out)
{
for(int i=degree; i>=0;i--)
{
if(coeff[i]>=0)
{
if(i!=degree)
out<<" + ";
out<< coeff[i];
}
else
{
if(coeff[i]<0)
out<<" - ";
out<< 0-coeff[i];
}
if(i>1)
out<<"X^"<<i;
else if(i==1)
out<<"X";
}
}
subpoly::subpoly(const subpoly &A)
{
coeff=new int[A.degree+1];
degree=A.degree;
for(int i=A.degree;i>=0;i--)
{
coeff[i]=A.coeff[i];
}
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
//MATRIX
#include<iostream.h>
#include<conio.h>
class matmul
{
public:
int r1,r2,c1,c2,i,j,k;
int a[10][10],b[10][10],c[10][10];
public:
void get();
void mul();
void put();
};
void matmul::get()
{
cout<<"Enter row of 1stmatrix";
cin>>r1;
cout<<"Enter col of 1st matrix";
cin>>c1;
cout<<"Enter row of 2nd matrix";
cin>>r2;
cout<<"Enter col of 2nd matrix";
cin>>c2;
}
void matmul::put()
{
cout<<"First matrix\n";
for(i=0;i<r1;i++)
{
for(j=0;j<c1;j++)
{
cout<<a[i][j]<<"\t";
}
cout<<"\n";
}
cout<<"Second matrix\n";
for(i=0;i<r2;i++)
{
for(j=0;j<c2;j++)
{
cout<<b[i][j]<<"\t";
}
cout<<"\n";
}
cout<<"RESULT\n";
for(i=0;i<r1;i++)
{
for(j=0;j<c1;j++)
{
cout<<c[i][j]<<"\t";
}
cout<<"\n";
}
}
void matmul::mul()
{
if(r1==c2)
{
cout<<"Enter first matrix";
cout<<"Second matrix\n";
for(i=0;i<r1;i++)
{
for(j=0;j<c1;j++)
{
cin>>a[i][j];
}}
cout<<"Second matrix\n";
for(i=0;i<r2;i++)
{
for(j=0;j<c2;j++)
{
cin>>b[i][j];
}}
for(i=0;i<r1;i++)
{
for(j=0;j<c2;j++)
{
c[i][j]=0;
for(k=0;k<r1;k++)
{
//c[i][j]=c[i][j]+a[k][j]*b[i][k];
c[i][j]=c[i][j]+a[i][k]*b[k][j];
}}}
put();
}
else
cout<<"not possible";
}
void main()
{
clrscr();
matmul m;
m.get();
m.mul();
getch();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
INFIX POSTFIX
#include <iostream.h>
#include <string.h>
#include <ctype.h>
#include<conio.h>
const int MAX = 50 ;
class infix
{
private :
char target[MAX], stack[MAX] ;
char *s, *t ;
int top, l ;
public :
infix( ) ;
void setexpr ( char *str ) ;
void push ( char c ) ;
char pop( ) ;
void convert( ) ;
int priority ( char c ) ;
void show( ) ;
} ;
infix :: infix( )
{
top = -1 ;
strcpy ( target, "" ) ;
strcpy ( stack, "" ) ;
l = 0 ;
}
void infix :: setexpr ( char *str )
{
s = str ;
strrev ( s ) ;
l = strlen ( s ) ;
* ( target + l ) = '\0' ;
t = target + ( l - 1 ) ;
}
void infix :: push ( char c )
{
if ( top == MAX - 1 )
cout << "\nStack is full\n" ;
else
{
top++ ;
stack[top] = c ;
}
}
char infix :: pop( )
{
if ( top == -1 )
{
cout << "Stack is empty\n" ;
return -1 ;
}
else
{
char item = stack[top] ;
top-- ;
return item ;
}
}
void infix :: convert( )
{
char opr ;
while ( *s )
{
if ( *s == ' ' || *s == '\t' )
{
s++ ;
continue ;
}
if ( isdigit ( *s ) || isalpha ( *s ) )
{
while ( isdigit ( *s ) || isalpha ( *s ) )
{
*t = *s ;
s++ ;
t-- ;
}
}
if ( *s == ')' )
{
push ( *s ) ;
s++ ;
}
if ( *s == '*' || *s == '+' || *s == '/' ||
*s == '%' || *s == '-' || *s == '$' )
{
if ( top != -1 )
{
opr = pop( ) ;
while ( priority ( opr ) > priority ( *s ) )
{
*t = opr ;
t-- ;
opr = pop( ) ;
}
push ( opr ) ;
push ( *s ) ;
}
else
push ( *s ) ;
s++ ;
}
if ( *s == '(' )
{
opr = pop( ) ;
while ( ( opr ) != ')' )
{
*t = opr ;
t-- ;
opr = pop ( ) ;
}
s++ ;
}
}
while ( top != -1 )
{
opr = pop( ) ;
*t = opr ;
t-- ;
}
t++ ;
}
int infix :: priority ( char c )
{
if ( c == '$' )
return 3 ;
if ( c == '*' || c == '/' || c == '%' )
return 2 ;
else
{
if ( c == '+' || c == '-' )
return 1 ;
else
return 0 ;
}
}
void infix :: show( )
{
while ( *t )
{
cout << " " << *t ;
t++ ;
}
}
void main( )
{
char expr[MAX] ;
infix q ;
clrscr();
cout << "\nEnter an expression in infix form: " ;
cin.getline ( expr, MAX ) ;
q.setexpr( expr ) ;
q.convert( ) ;
cout << "The Prefix expression is: " ;
q.show( ) ;
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
DOUBLY LINKED LIST
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
struct Doubly
{
int info;
struct Doubly*next;
struct Doubly*previous;
};
class linked
{
public:
int no,dnode,search;
Doubly first,*new1;
public:
void create(Doubly*);
void insert(Doubly*);
void delet(Doubly*);
void display(Doubly*);
};
void linked::create(Doubly*node)
{
first.next=NULL;
first.previous=NULL;
node=&first;
no=0;
cout<<"\n input choice b for break: ";
char ch=getche();
while(ch!='b')
{
node->next=(Doubly*)malloc(sizeof(Doubly));
node->next->previous=node;
node=node->next;
cout<<"\n Input the values of the node: "<<(no+1)<<":";
cin>>node->info;
node->next=NULL;
cout<<"\n Input choice b for break;";
ch=getche();
no++;
}
cout<<"\n total node="<<no;
}
void linked::delet(Doubly*node)
{
search=0;
cout<<"Enter the node to be delete: ";
cin>>dnode;
node=first.next;
if(node==NULL)
{
cout<<"\n underflow\nList is empty\n";
}
else
{
while(node)
{
if((search+1)==dnode)
{
node->previous->next=node->next;
node->next->previous=node->previous;
free(node);
}
else
{
node=node->next;
}
search++;
}
}
node=node->next;
}
void linked::insert(Doubly*node)
{
new1=(Doubly*)malloc(sizeof(Doubly));
cout<<"\n insert the node value";
cin>>new1->info;
node=first.next;
if(node==NULL)
{
cout<<"\n list is empty";
}
else
{
new1->next=node;
new1->previous=node->previous;
node->previous->next=new1;
node->previous=new1;
}
}
void linked::display(Doubly*node)
{
node=first.next;
do
{
cout<<"\n";
cout<<""<<node->info;
node=node->next;
}
while(node->next);
do
{
cout<<"\n";
cout<<""<<node->info;
node=node->previous;
}
while(node->previous);
getch();
}
void main()
{
linked l;
int zy,t;
clrscr();
cout<<"\n\t\t Creating a simple Doubly linked list";
cout<<"\n\t\t *****************************\n";
Doubly*node=(Doubly*)malloc(sizeof(Doubly));
do
{
cout<<"\1. Create\n2. Insert New Node\n3. Display
\n5. Exit\nEnter ur choice: ";
cin>>zy;
switch(zy)
{
case 1:
l.create(node);
cout<<"\n Create doubly linked list is as follows\n";
l.display(node);
break;
case 2:
cout<<"\t\t inserting some nodes\n\n";
l.insert(node);
case 3:
cout<<"\n Insert node doubly linked list is as follows\n";
l.display(node);
break;
case 4:
cout<<"\t\tDelete nodes\n\n";
l.delet(node);
break;
case 5:
break;
}
}
while(zy!=5);
getch();
}
Dijkstra's
#include <iostream.h>
#include <conio.h>
#define MAX_NODE 50
struct node
{
int vertex;
int weight;
node *next;
};
struct fringe_node
{
int vertex;
fringe_node *next;
};
node *adj[MAX_NODE];
int totNodes;
const int UNSEEN=1,FRINGE=2,INTREE=3;
int status[MAX_NODE];
fringe_node *fringe_list;
void createGraph()
{
node *newl,*last;
int neighbours;
cout<<"\n\n---Graph Creation---\n\n";
cout<<"Enter total nodes in graph : ";
cin>>totNodes;
for(int i=1;i<=totNodes;i++){
last=NULL;
cout<<"Total Neighbours of "<<i<<" : ";
cin>>neighbours;
for(int j=1;j<=neighbours;j++){
newl=new node;
cout<<"Neighbour #"<<j<<" : ";
cin>>newl->vertex;
cout<<"Weight #"<<j<<" : ";
cin>>newl->weight;
newl->next=NULL;
if(adj[i]==NULL)
adj[i]=last=newl;
else
{
last->next = newl;
last = newl;
}
} } }
//Insert node in a fring_list at Begining.
void Insert_Beg(int item)
{
fringe_node *newl;
newl = new fringe_node;
newl->vertex = item;
newl->next = NULL;
newl->next = fringe_list;
fringe_list = newl;
}
//Delete element at pos position from fringe_list.
void del(int pos)
{
//to points to previous node from where
//to insert
int i;
fringe_node *tmp,*delnode;
for(i=1,tmp=fringe_list; i < (pos-1); tmp=tmp->next,i++);
delnode = tmp->next;
tmp->next = tmp->next->next;
delete(delnode);
}
void print_path(int s,int d,int parent[])
{
if(d==s)
cout<<" "<<s;
else{
print_path(s,parent[d],parent);
cout<<"-->"<<d;
}}
void shortestPath()
{
int i,x,parent[MAX_NODE],edge_count,w,wt,v;
int min_dist,y,dist[MAX_NODE],stuck;
int source,destination;
node *ptr1;
fringe_node *ptr2;
cout<<"Enter Source Node : ";
cin>>source;
cout<<"Enter Destination Node : ";
cin>>destination;
fringe_list=NULL;
for(i=1;i<=totNodes;i++)
{
status[i]=UNSEEN;
parent[i]=0;
}
status[source]=INTREE;
dist[source]=0;
x=source;
stuck=0;
while( (x != destination) && (!stuck))
{
ptr1=adj[x];
while(ptr1!=NULL)
{
y=ptr1->vertex;
wt=ptr1->weight;
if((status[y]==FRINGE) && (dist[x]+wt < dist[y]))
{
parent[y]=x;
dist[y] = dist[y] + wt;
}
else if(status[y]==UNSEEN)
{
status[y]=FRINGE;
parent[y]=x;
dist[y] = dist[y] + wt;
Insert_Beg(y);}
ptr1=ptr1->next;}
if(fringe_list==NULL)
stuck=1;
else{
x=fringe_list->vertex;
min_dist=dist[x];
ptr2=fringe_list->next;
while(ptr2!=NULL){
w=ptr2->vertex;
if(dist[w] < min_dist)
{
x=w;
min_dist=dist[w];
}
ptr2=ptr2->next;
}
del(x);
status[x]=INTREE;
} }
if(parent[destination]==0)
cout<<"No path from "<<source<<" to "<<destination;
else
{
cout<<"\n\nShortest Path\n";
print_path(source,destination,parent);
}
}
void main(){
clrscr();
cout<<"*****Minimum Spaning Tree (MST)*****\n";
createGraph();
cout<<"\n===Minimum Spaning Tree===\n";
shortestPath();
getch();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
DFS BFS
#include<iostream.h>
#include<conio.h>
#include<stdio.h>
#define max 50
int adj[max][max];
class graph
{
private:
int vertex[max];
int visited[max];
public:
graph()
{}
~graph()
{}
void creategraph(int);
void depthfirst(int);
void breathfirst(int);
void DFS(int,int);
};
void graph::DFS(int ad,int v)
{
int k;
for(k=ad;k<v;k++)
for(int j=0;j<v;j++)
if(adj[k][j]==1)
{
if(visited[j]==0)
{
visited[j]=1;
cout<<vertex[j]<<"==>>";
DFS(j,v);
}}}
void graph::creategraph(int v)
{
int i,j;
for(i=0;i<v;i++)
{
cout<<"Enter the node value:";
cin>>vertex[i];
visited[i]=0;
}
for(i=0;i<v;i++)
for(j=0;j<v;j++)
adj[i][j]=0;
cout<<"enter the adjacency vertices list for each vertex of the graph:";
cout<<"\n";
int n,m,k;
for(i=0;i<v;i++)
{
cout<<"Enter the no of adjacency vertices for the vertex";
cout<<vertex[i]<<";";
cin>>n;
for(j=1;j<=n;j++)
{cout<<"Enter the adjacency vertex";
cin>>m;
for(k=0;k<v;k++)
{if(vertex[k]==m)
adj[j][k]=1;
}}}
clrscr();
cout<<"\n graph created with no of vertices=="<<v<<endl<<endl;
cout<<"\n\n the adjacency matrix of the graph is:\n\n";
for(i=0;i<v;i++)
cout<<adj[i][j]<<" ";
cout<<endl;
}
void graph::depthfirst(int v)
{
int i=0;
for(i=0;i<v;i++)
visited[i]=0;
adj[0][0]=1;
visited[0]=1;
cout<<"\t\t depth first traversal \n\n";
cout<<vertex[0]<<"==>>";
DFS(0,v);
}
void graph::breathfirst(int v)
{
int i,j;
for(i=0;i<v;i++)
visited[i]=0;
cout<<"\t\t breath first traversal\n\n";
cout<<vertex[0]<<"==>>";
visited[0]=1;
for(i=0;i<v;i++)
{
for(j=0;j<v;j++)
{
if(adj[i][j]==1)
{
if(visited[j]==0)
{
cout<<vertex[j]<<"==>>";
visited[j]=1;
}}}}
cout<<"x\n\n";
}
void main()
{
graph g;
int ch,v;
do
{
clrscr();
cout<<"\t\t Graph creation and traversal\n\n";
cout<<"\t\t 1.Creat Graph\n\n";
cout<<"\t\t 2.Breadth First Traversal\n\n";
cout<<"\t\t 3.Depth First Traversal\n\n";
cout<<"\t\t 4.Exit\n\n";
cout<<"\t\t Enter your choice\n\n";
cin>>ch;
switch(ch)
{
case 1:
clrscr();
cout<<"\n\t\t Graph Creation \n\n";
cout<<"Enter the no of vertices to be created";
cin>>v;
g.creategraph(v);
cout<<"Press any key to continue";
getch();
break;
case 2:
clrscr();
g.breathfirst(v);
cout<<"press any key to continue";
getch();
break;
case 3:
clrscr();
g.depthfirst(v);
cout<<"X\n\n";
cout<<"press any key to continue";
getch();
break;
default:
break;
}
}
while(ch!=4);
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
CIRCULAR LINKED LIST
#include<iostream.h>
#include<conio.h>
#include<malloc.h>
struct node
{
int a;
struct node*next;
};
class list
{
struct node*root,*end;
public:
void create();
void insert();
void delet();
void show();
};
void list::create()
{
struct node*p,*n;
int t,s;
root=p=NULL;
s=sizeof(struct node);
cout<<"\n Enter -99 to stop";
cin>>t;
while(t!=-99)
{
n=(struct node*)malloc(s);
n->a=t;
n->next=NULL;
if(root==NULL)
root=n;
else
p->next=n;
p=n;
cout<<"\n Enter -99 to stop";
cin>>t;
}
end=n;
end->next=root;
}
void list::show()
{
struct node*x=root;
cout<<"/n root->";
do
{
cout<<x->a<<"->";
x=x->next;
}while(x!=root);
cout<<"root";
}
void list::insert()
{
struct node*temp,*ex=root;
int t,p,i=2;
cout<<"\n enter the value & position to insert:";
cin>>t>>p;
temp=(struct node*)malloc(sizeof(struct node));
temp->a=t;
temp->next=NULL;
if(p==1)
{
temp->next=root;
end->next=temp;
root=temp;
}
else
{
while(ex->next!=root && i<p)
{
ex=ex->next;
i++;
}
temp->next=ex->next;
ex->next=temp;
if(ex==end)
end=temp;
}}
void list::delet()
{
struct node*ex=root;
int p,i=2;
cout<<"\n Enter the position to delete:";
cin>>p;
if(p==i)
{
root=root->next;
end->next=root;
}
else
{
while(ex->next!=NULL && i<p)
{
ex=ex->next;
i++;
}
if(ex->next==end)
{
ex->next=root;
end=ex;
}
else
{
ex->next=ex->next->next;
}}
}
void main()
{
clrscr();
cout<<"\n\t\t OUT PUT \n";
list o;
o.create();
o.show();
o.insert();
o.show();
o.delet();
o.show();
getch();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
//CIRCULAR QUEUE
#include<iostream.h>
#include<conio.h>
#include<string.h>
#include<ctype.h>
#include<process.h>
#define size 6
class cirque
{
public:
int rear,front;
int ch;
int q[size];
public:
cirque()
{
rear=front=-1;
}
void insert();
void deleteq();
void display();
clrscr();
};
void cirque :: insert()
{
if((front==0)&&(rear==size-1))
{
cout<<"\n overflow";
rear=1;
return;
}
else
if(front<0)
{
front=0;
rear=0;
cout<<"\n Give the input element";
cin>>ch;
q[rear]=ch;
}
else
if(rear==size-1)
{
rear=0;
cout<<"\n Give the input element:";
cin>>ch;
q[rear]=ch;
}
else
{
rear++;
cout<<"Give the input element:";
cin>>ch;
q[rear]=ch;
}
}
void cirque :: deleteq()
{
if(front<0)
{
cout<<"\n underflow";
return;
}
ch=q[front];
q[front]=NULL;
cout<<"Elementis Deleted:"<<ch;
if(front==rear)
{
front=-1;
rear=-1;
}
else
if(front==size-1)
{
front=0;
}
else
{
front++;
}
}
void cirque :: display()
{
if(front<0)
return;
if(rear>=front)
{
for(int i=front;i<=rear;i++)
{
cout<<"\n i="<<i;
cout<<" "<<q[i];
}
}
else
{
for(int i=front;i<=size;i++)
{
cout<<"\n i="<<i;
cout<<" "<<q[i];
}
for(i-0;i<=rear;i++)
{
cout<<"\n i="<<i;
cout<<" "<<q[i];
}
}
}
void main()
{
cirque Q;
int k=0;
char choice;
clrscr();
do
{
cout<<"\n INSERT->i DELETE->d QUIT->q:\n";
cout<<"\n Input choice:\n";
do
{
cin>>choice;
choice=tolower(choice);
}
while(strchr("idq",choice)==NULL);
cout<<"\nenter your choice is->"<<choice;
switch(choice)
{
case 'i':
Q.insert();
cout<<"\n queue after inserting:";
Q.display();
break;
case 'd':
Q.deleteq();
cout<<"\n queue content after deleteion is as follow:\n";
Q.display();
break;
case 'q':
k=1;
}
}
while(!k);
getch();
}
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
BINARY TREE TRAVERSAL
BINARY TREE TRAVERSAL
#include<iostream.h>
#include<stdio.h>
#include<alloc.h>
#include<stdlib.h>
#include<conio.h>
typedef struct tree *node;
node create(int,node temp);
void inorder(node temp);
void preorder(node temp);
void postorder(node temp);
struct tree
{
int data;
struct tree *right,*left;
}*root;
void main()
{
node temp= NULL;
int data,ch,i=0,n;
clrscr();
cout<<"\nEnter the number of elements in the Tree:";
cin>>n;
cout<<"\n The elements are :\n";
for(i=0;i<n;i++)
{
cin>>data;
temp=create(data,temp);
}
cout<<"1.INORDER\n2.PREORDER\n3.POSTOTRDER\n4.EXIT\n";
do
{
cout<<"Enter your choice:";
cin>>ch;
switch (ch)
{
case 1:
cout<<"Inorder traversal of the given Tree\n";
inorder(temp);
break;
case 2:
cout<<"Preoroder traversal of the given Tree\n";
preorder(temp);
break;
case 3:
cout<<"Postorder traversal of the given Tree\n";
postorder(temp);
break;
default:
cout<<"Exit";
exit(0);}
}
while(ch!=4);
getch();
}
node create(int X, node temp)
{
struct tree *new1;
new1=(tree*)malloc(sizeof(struct tree));
if(new1==NULL)
cout<<"No Nodes are here\n";
else
{
if(temp==NULL)
{
new1->data=X;
new1->left=NULL;
new1->right=NULL;
temp=new1;}
else
{
if(X<temp->data)
temp->left=create(X,temp->left);
else
temp->right=create(X,temp->right);
}
}
return temp;
}
void inorder(node temp)
{
if(temp!=NULL)
{
inorder(temp->left);
cout<<"\t"<<temp->data;
inorder(temp->right);
}
}
void preorder(node temp)
{
if(temp!=NULL)
{
cout<<"\t"<<temp->data;
preorder(temp->left);
preorder(temp->right);
}
}
void postorder(node temp)
{
if(temp!=NULL)
{
postorder(temp->left);
postorder(temp->right);
cout<<"\t"<<temp->data;
}
}
BINARY SEARCH TREE
#include<iostream.h>
#include<conio.h>
enum boolean
{
false=0,true=1
};
struct node
{
int element;
node *left,*right;
}*root=NULL;
class BST
{
node *par,*temp,*temp1;
node* newnode(int);
public:
void insert(int,node*,int);
boolean search(int,node*);
node* deletemin(node**);
void del(int,node**);
void display(node*);
};
node* BST::newnode(int x)
{
node *nod=new node;
nod->element=x;
nod->left=nod->right=NULL;
return(nod);
}
void BST::insert(int x,node *cur,int pos)
{
if(cur == NULL)
{
cur=newnode(x);
if (pos==1)
par->left=cur;
else if (pos==2)
par->right=cur;
if(root==NULL)
root=cur;
}
else
{
par=cur;
if(x < cur->element)
insert(x,cur->left,1);
else if(x > cur->element)
insert(x,cur->right,2);
}}
boolean BST::search(int x,node *cur)
{
if(root ==NULL)
return false;
else if(x == cur->element)
return true;
else if(x < cur->element && cur->left !=NULL)
return (search(x,cur->left));
else if(x <cur->element && cur->right !=NULL)
return (search(x,cur->right));
return false;
}
node* BST::deletemin(node **cur)
{
if((*cur)->left==NULL)
{
temp=(*cur);
(*cur)=(*cur)->right;
}
else
temp=deletemin((&(*cur)->left));
return(temp);
}
void BST::del(int x,node **cur)
{
if((*cur) !=NULL)
{
if(x<(*cur)->element)
del(x,(&(*cur)->left));
else if(x>(*cur)->element)
del(x,(&(*cur)->right));
else
{
if(((*cur)->left==NULL) && ((*cur)->right==NULL))
{
delete((*cur));
(*cur)=NULL;
}
else if((*cur)->left==NULL)
(*cur)=(*cur)->right;
else if((*cur)->right==NULL)
(*cur)=(*cur)->left;
else
{
temp1=(*cur)->left;
(*cur)=deletemin((&(*cur)->right));
(*cur)->left=temp1;
}
}
}
}
void BST::display(node *cur)
{
if(cur !=NULL)
{
display(cur->left);
cout<<"\t"<<cur->element;
display(cur->right);
}
}
void main()
{
int no,x,p;
BST bst;
clrscr();
do
{
cout<<"\n1Insert\n2:Delete\n3:Search\n4:Display\n5:Exit
\nSelect your option :";
cin>>no;
switch(no)
{
case 1:
cout<<"\nEnter the no. to be inserted\n";
cin>>x;
bst.insert(x,root,0);
break;
case 2:
cout<<"\nEnter the element to be deleted: ";
cin>>x;
bst.del(x,&root);
break;
case 3:
cout<<"\nEnter the element to be searched :";
cin>>x;
p=bst.search(x,root);
if(p==true)
cout<<"The element is in the Tree\n";
else
cout<<"The element is not in the Tree\n";
break;
case 4:
cout<<"\nThe elements in the list are\n";
bst.display(root);
}
}
while(no<5);
}
THE END TO C++ ;-)
No comments:
Post a Comment