bellman

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

void main()
{
	clrscr();
	int **adj,i,j,k,size,count,*distance,start,weight;
	cout<<"Enter no. of nodes ";
	cin>>size;
	adj=new int *[size];
	distance=new int [size];
	for(i=0;i<size;i++)
	{
		adj[i]=new int [size];
		//initialize distance from root to maximum
		distance[i]=1000;
	}
	for(i=0;i<size;i++)
		for(j=0;j<size;j++)
			adj[i][j]=1000;
	char more ='y';
	//entry into adjacency matrix

	while(more=='y')
	{
		cout<<"Enter nodes that are connected through an edge ";
		cin>>i>>j;
		i--;j--;
		cout<<"Enter the weight of the edge: ";
		cin>>weight;
		adj[i][j]=weight;
		cout<<"Are there more connected edges ";
		cin>>more;
	}
	//display entered matrix

	cout<<"Matrix you entered is "<<endl;
	for(i=0;i<size;i++)
	{
		cout<<endl;
		adj[i][i]=0;
		for(j=0;j<size;j++)
			cout<<adj[i][j]<<"\t";
	}

	cout<<"Enter the starting node ";
	cin>>start;

	//count keeps track of the number of edges
	//permanent
	//when count=n-1
	//exit while
	count=1;

	//iterations of bellman algorithm
	int loop;

	while(count < size)
	{
		//loop=no. of edges that can be traversed for
		//this iteration
		loop=0;
		int temp=0;
		for(i=0;i<size;i++)
		{
			for(j=0;j<size;j++)
			{
				if(start==i || start==j )
					continue;
				else if(distance[j] < adj [start][j])
				{
					temp=adj[start][j];
					loop++;
					int x=j;
					while(loop <	count)
					{
						for(k=0;k<size;k++)
						{
							if(distance[x] > temp +adj[x][k])
						 {}
						}
					}
					}
					}
                                        }
getch();
}
}


bfs

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define  WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 20

typedef struct node_type
{
int vertex;
struct node_type *link;
}node;

typedef struct queue_type
{
int info;
struct queue_type *next;
}queue;

void create_empty_queue(queue **front,queue **rear)
{

*front =*rear = (queue *)NULL;

}

void enqueue(queue **front,queue **rear,int element)
{
queue *ptr;
ptr = (queue *)malloc(sizeof(queue));
ptr->info=element;
ptr->next = (queue*)NULL;
	if(*front == (queue *)NULL)
	*front = *rear =ptr;
	else
	{
		(*rear)->next = ptr;
		*rear = ptr;
	}

}

int dequeue (queue **front,queue **rear)
{
int temp;
queue *ptr;
temp = (*front)->info;
ptr=*front;
 if(*front == *rear)
 *front=*rear = (queue *)NULL;
 else
 *front = (*front)->next;
free(ptr);
return temp;

}

int head (queue *front)
{
	return front->info;
}

int empty (queue * front)
{
	if(front == (node  *)NULL)
	return 1;
	else
	return 0;

}

void create_graph (node *adj[],int num)
{
int i;
for (i=1;i<=num;i++)
adj[i] = (node *)NULL;
}


void input_graph(node *adj[],int num)
{
   node *ptr,*last;
   char *ss[] = { "","First","Second","Third","Forth","Fifth","Sixth","Seventh",
		   "Eigth","Ninth"};
   int i,j,m,val;
   clrscr();
   printf("\n How many nodes are there in the adjacency list of node %d:",i);
   for (i = 1; i<=num;i++)
   {
    last = (node *)NULL;
    clrscr();
   printf("\n How many nodes are there in the adjacency list of node %d:",i);
   scanf("%d",&m);
   for(j=1;j<=m;j++)
   {
     printf("Enter %s node :",ss[j]);
     scanf("%d",&val);
     ptr=(node *)malloc(sizeof(node));
     ptr->vertex = val;
     ptr->link =(node *)NULL;

     if(adj[i] == (node *)NULL)
     adj[i] = last =ptr;
     else
     {
      last->link =ptr;
      last =ptr;
      }
    }
  }
}

void delete_graph(node *adj[],int n)
{
 int i;
 node *temp,*ptr;
 for(i=1;i<=n;i++)
 {
    ptr = adj[i];
    while(ptr!=(node *)NULL)
    {
     temp = ptr;
     ptr = ptr->link;
     free(temp);

    }
   adj[i] = (node *)NULL;
   }
}

void bfs(node *adj[],int n,int s)
{
node *ptr;
queue *front,*rear;
int i,color[MAX],u,v;
create_empty_queue(&front,&rear);
	for(i=1;i<=n;i++)
	color[i]=WHITE;
color[s]=GRAY;
enqueue(&front,&rear,s);
	while(!empty(front))
	{
	u =head(front);
	ptr =adj[u];
		while(ptr!=(node *)NULL)
		{
		v=ptr->vertex;
			if(color[v] == WHITE)
			{
			color[v] == GRAY;
			enqueue(&front,&rear,v);
			}
		ptr =ptr->link;
		}
	u =dequeue(&front,&rear);
	printf("%d ",u);
	color[u] =BLACK;
	}
}

void main(void)
{
node *adj[MAX];
int n,s;
clrscr();
printf("\nEnter The  no. of nodes in graph; ");
scanf("%d",&n);
create_graph(adj,n);
input_graph(adj,n);
clrscr();
printf("Enter source vertex");
scanf("%d",&s);
printf("\n\nBFS from vertex %d is \n\n",s);
bfs(adj,n,s);
printf("\n\n Press any key to continue");
getch();
delete_graph(adj,n);
}

binary search

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

int binarysearch( int * a, int lb, int ub, int item)
{
	int mid;
	if(lb>ub)
		return -1;
	else
	{
		mid=(lb+ub)/2;
		if(item==a[mid])
			return mid;
		else if(item<a[mid])
			return binarysearch(a,lb,mid-1,item);
		else
			return binarysearch(a,mid+1,ub,item);
	}
}

void main()
{
	clrscr();
	int array[20],n,i,num,result;

	cout<<"\nEnter the elements of the array:";
	cin>>n;

	for(i=0;i<n;i++)
	{
		cin>>array[i];
	}

	cout<<"\nEnter the no you want to search:";
	cin>>num;

	result = binarysearch(array,0,n-1,num);
	if(result == -1)
		cout<<"No. not found";
	else
		cout<<"The number has been found at position:"<<result;
	getch();
}


bubble

#include"iostream.h"
#include"conio.h"
void bubble(int a[],int n)
{
	int temp,i,j;
	int flag=1;
	for(i=0;i<n&&flag;i++)
	{
		flag=0;
		for(j=0;j<n-i-1;j++)
		{
			if(a[j]>a[j+1])
			{
				flag=1;

				temp=a[j];
				a[j]=a[j+1];
				a[j+1]=temp;
			}
		}
	}
for(i=0;i<n;i++)
cout<<"\n      "<<a[i];
}
void main()
{
	clrscr();
	int a[100];
	int num;
	cout<<endl<<"How many elements are there in array:";
	cin>>num;
	cout<<endl<<"Enter array elements:";
	for(int h=0;h<num;h++)
	cin>>a[h];
	bubble(a,num);
	cout<<"The sorted array is:"<<endl;
	for(h=0;h<num;h++)
	cout<<a[h];
	getch();
}

count

#include<iostream.h>
#include<conio.h>
 void main()
 {
 clrscr();
 int a[500];
 int b[500];
 int c[500];
 int n;
 cout<<"Enter the number of elements "<<endl;
 cin>>n;
 cout<<"Enter the elements "<<endl;
 for(int i=1;i<=n;i++)
 cin>>a[i];
 int x=a[1];
 for(i=1;i<=n;i++)
 {
  if(x<a[i])
  x=a[i];
 }

 cout<<endl<<"The maximum element is"<<x;

 for(i=1;i<=x;i++)
 c[i]=0;
 for(i=1;i<=x;i++)
 b[i]=0;

 for(i=1;i<=n;i++)
 c[a[i]]=c[a[i]]+1;

 for(i=2;i<=x;i++)
 c[i]=c[i]+c[i-1];

 int j;
 for(j=n;j>=1;j--)
 {
 b[c[a[j]]]=a[j];
 c[a[j]]=c[a[j]]-1;
 }
 cout<<endl<<"The sorted array is-->"<<endl;

 for(i=1;i<=n;i++)
 cout<<b[i]<<endl;
 cout<<endl;
 cout<<"The auxillary array is-->"<<endl;
 for(i=1;i<=x;i++)
 cout<<"  "<<c[i];
 getch();
 }

dfs

#include <stdio.h>
#include <conio.h>
#include <alloc.h>
#define  WHITE 0
#define GRAY 1
#define BLACK 2
#define MAX 20

typedef struct node_type
{
	int vertex;
	struct node_type *link;
}node;

int color[MAX];

void create_graph (node *adj[],int num)
{
	int i;
	for (i=1;i<=num;i++)
	adj[i] = (node *)NULL;
}

void input_graph(node *adj[],int num)
{
	node *ptr,*last;
	char *ss[] = { "","First","Second","Third","Forth","Fifth","Sixth","Seventh",
	"Eigth","Ninth"};
	int i,j,m,val;
	for (i = 1; i<=num;i++)
	{
		last = (node *)NULL;
		clrscr();
		printf("\n How many nodes are there in the adjacency list of node %d:",i);
		scanf("%d",&m);
		for(j=1;j<=m;j++)
		{
		     printf("Enter %s node :",ss[j]);
		     scanf("%d",&val);
		     ptr=(node *)malloc(sizeof(node));
		     ptr->vertex = val;
		     ptr->link =(node *)NULL;
		     if(adj[i] == (node *)NULL)
			adj[i] = last =ptr;
		     else
		     {										   last->link =ptr;
			 last =ptr;
		     }
		}
	}
}

void delete_graph(node *adj[],int n)
{
	int i;
	node *temp,*ptr;
	for(i=1;i<=n;i++)
	{
		ptr = adj[i];
		while(ptr!=(node *)NULL)
		{
		  temp = ptr;
		  ptr = ptr->link;
		  free(temp);
		}
	       adj[i] = (node *)NULL;
	}
}
void dfs_visit(node *adj[],int u)
{
	int v;
	node *ptr;
	color[u]=GRAY;
	ptr=adj[u];
	while(ptr!=(node *)NULL)
	{
	 v= ptr->vertex;
	 if(color[v] == WHITE)
	 dfs_visit(adj,v);
	 ptr=ptr->link;
	}
	printf("%d ",u);
	color[u]=BLACK;
}
void main()
{
	node *adj[MAX];
	int n,i,tree=0;
	clrscr();
	printf("\nEnter number of nodes in graph :");
	scanf("%d",&n);
	create_graph(adj,n);
	input_graph(adj,n);
	for(i=1;i<=n;i++)
	color[i] = WHITE;
	for(i=1;i<=n;i++)
	{
		if(color[i]==WHITE)
		{
			tree++;
			printf("\n\nDFS tree %d : ",tree);
			dfs_visit(adj,i);
		}
	}
	printf("\n\npress any key to continue....");
	getch();
	delete_graph(adj,n);
}

djkastra

// Dijkstra's Algorithn //
// Swapandeep Mann  BE 132/99 //
#include<iostream.h>
#include<conio.h>
#include<stdlib.h>
#include<stdio.h>

int n;

int min(int value1, int value2)
{
 if(value1>value2)
   return value2;
 else
   return(value1);
}

int findmin(int *d,int *ts,int c)
{
 int *d1=new int[n];
  for(int i=0;i<n;i++)
   d1[i]=d[i];
  for( i=0;i<c+1;i++)
   {
    d1[ts[i]]=12000;
   }
 int min=d1[0];
 int p=0;
 for(i=1;i<n;i++)
  {
   if(min>d1[i])
    {
     min=d1[i];
     p=i;
    }
  }
  cout<<"**";
  cout<<p;
  return p;
}

class node
{
 public:
	int nno;
	int adjn;
	int **cost;
	void nodes(int n)
	{
	 nno=n;
	}
	void adjacency(int p)
	{
	 adjn=p;
	 int wt,no;
	 cost=new int*[n];
	  for(int i=0;i<n;i++)
	   cost[i]=new int[2];
	    for(i=0;i<n;i++)
	     {
	      cost[i][0]=-1;
	      cost[i][1]=-1;
	     }
	    for(i=0;i<adjn;i++)
	     {
	      cout<<"Enter the node no. : \n";
	      cin>>no;
	      cout<<"Enter the weight : \n";
	      cin>>wt;
	      cost[no][0]=no;
	      cost[no][1]=wt;
	     }

	     for(i=0;i<n;i++)
	      {
	       if(i==nno)
		{
		 cost[i][0]=0;
		 cost[i][1]=0;
		  continue;
		}
		if(cost[i][0]==-1)
		 {
		  cost[i][0]=i;
		  cost[i][1]=10000;
		 }
	       }
	}
};

void main()
{
 clrscr();
 cout<<"Please enter the no. of node in the Graph "<<endl;
 cin>>n;
 node*p=new node[n];
  for(int i=0;i<n;i++)
   {
    p[i].nodes(i);
   }
  clrscr();
  cout<<endl;
  cout<<"Please enter the source node "<<endl;
  int sno;
  cin>>sno;

  clrscr();
   for(i=0;i<n;i++)
    {
     int a;
     cout<<"Enter the no. of node adjacent to node "<<i<<endl;
     cin>>a;
     p[i].adjacency(a);
    }
    int *ts=new int[n];
    int w,c=0;
    ts[c]=sno;
    int *d=new int[n];
    d[sno]=0;
     for(int j=0;j<n;j++)
      {
       if(j==sno)
	continue;
       d[j]=p[sno].cost[j][1];
       cout<<d[j]<<" ";
      }
     while(c<n)
      {
       w=findmin(d,ts,c);
	for(int y=0;y<n;y++)
	 {
	  if(y==sno)
	   continue;
	  d[y]=min(d[y],d[w]+p[w].cost[y][1]);
	   cout<<d[y]<<" ";
	 }
	  c++;
	  ts[c]=w;
       }
      clrscr();
      cout<<endl<<endl<<endl;
      cout<<"The Single Source Shortest distance "<<endl;
      cout<<endl;
      for(i=0;i<n;i++)
       {
	if(d[i]==0)
	continue;
	cout<<"Node "<<i<<" is a distance \t "<<d[i]<<" \t from Source node "<<sno<<"  "<<endl;
       }
 getch();
}


djkastra2

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#define true 1
#define false 0
struct node
{
int info;
int next;
int wt;
};
node n[10][10];
int drec(int rec,int i,int num)
{
int k;
for(k=0;k<num;k++)
{
if(k+1==rec)
break;
}
int j=0;
while(n[k][j].info!=-1 && n[k][j].info!=i+1)
j=n[k][j].next;
if(n[k][j].info==i+1)
{
//cout<<endl<<n[k][j].wt<<endl;
return n[k][j].wt;
}
else
return 50;
}

void main()
{
clrscr();
int i,j,k;
int num,tot;
cout<<endl<<"Enter the total no of nodes"<<endl;
cin>>num;
for(i=0;i<num;i++)
{
j=0;
n[i][j].info=i+1;
n[i][j].next=j+1;
cout<<endl<<"Enter no of nodes adjacent to node "<<i+1<<endl;
cin>>tot;
cout<<endl<<"Enter the adjacent nodes and their weights"<<endl;
for(j=1;j<=tot;j++)
{
cin>>n[i][j].info>>n[i][j].wt;
n[i][j].next=j+1;
}
n[i][j].info=-1;
n[i][j].next=-1;
}
clrscr();
cout<<endl<<endl<<"The graph is"<<endl;
for(i=0;i<num;i++)
{
for(j=0;n[i][j].info!=-1;)
{
cout<<n[i][j].info<<n[i][j].wt<<"\t";
j=n[i][j].next;
}
cout<<endl;
}
getch();
int D[15];
int final[20];
int path;
int pred[15];
int x,d,s,y,z;
int recent,newlabel,temp;
/*cout<<endl<<"Enter the total no. of nodes"<<endl;
cin>>n;*/
cout<<endl<<"\t Enter the source node"<<endl;
cin>>s;
cout<<endl<<"Enter the destination node"<<endl;
cin>>d;
for(i=0;i<num;i++)
{
D[i]=50;
final[i]=false;
pred[i]=1;
}
D[s-1]=0;
final[s-1]=true;
recent=s;
path=true;
while(final[d-1]==false)
{
for(i=0;i<num;i++)
{
if(drec(recent,i,num)<50 && !final[i])
{
newlabel=D[recent-1]+drec(recent,i,num);
cout<<endl<<"\t"<<newlabel<<endl;
if(newlabel<D[i])
{
D[i]=newlabel;
pred[i]=recent;
}
}
}
/*for(z=0;z<num;z++)
{
cout<<endl<<pred[z]<<endl;
} */
getch();
temp=50;
for(x=0;x<num;x++)
if(!final[x] && (D[x]<temp))
{
y=x;
temp=D[x];
}
if(temp<50)
{
final[y]=true;
recent=y+1;
//cout<<"\n Recent node is"<<recent;
}
else
{
path=false;
final[d-1]=true;
}
}
cout<<endl<<"The path length is \t"<<D[d-1];
getch();
clrscr();
int arr[6];
int t;
arr[0]=d;
for(i=1;d!=s;i++)
{
if(final[d-1]==true)
{
arr[i]=pred[d-1];
d=arr[i];
}
}
t=i-1;
for(;t>=0;t--)
cout<<endl<<arr[t]<<endl;
getch();
}

evalpost

#include<iostream.h>
#include<string.h>
#include<stdio.h>
#include<conio.h>
#include<math.h>
struct stack1
{
int top;
int val[10];
};
void push(stack1 *s,int val)
{
if(s->top<9)
s->val[++s->top]=val;
else
cout<<"\n overflow";
}
int pop(stack1 *s)
{
if(s->top>-1)
{ int temp=s->val[s->top--]; return temp;}
else
cout<<"\nstack1 underflow";return -1;
}
void display(stack1 *s)
{
while(s->top>-1)
cout<<s->val[s->top--];
}
int isdigit(char ch)
{
if((int(ch-'0')>-1)&&(int (ch-'0')<10))
return 1;
else
return 0;
}
void eval(char ch,stack1*s)
{
int opd1,opd2;
opd1=pop(s);
opd2=pop(s);  int ans;
switch(ch)
{
case '+': ans=opd2+opd1;break;
case '-':ans=opd2-opd1;break;
case '*':ans=opd2*opd1;break;
case '/':ans=opd2/opd1;break;
case '$':ans=pow(opd2,opd1);break;
default:cout<<"unknown operation";
}
push(s,ans);
}

void main()
{
clrscr();
stack1 *s; s->top=-1;
char str[15];
cout<<"enter the postfix expression ";gets(str);
for(int i=0;i<strlen(str);i++)
if(isdigit(str[i]))
push(s,str[i]-'0');
else
eval(str[i],s);
cout<<"\n the result is ";
cout<<pop(s);
getch();
}

generic

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<process.h>
struct tree
{  int item;
   struct tree *son;
   struct tree *link;
};
 struct tree *t;
 void g_dfs(struct tree *t1,int x)
 {
  if(t1!=NULL)
 {
  if(t1->item!=x)
  {
  cout<<t1->item<<"-->";

  g_dfs(t1->son,x);
  g_dfs(t1->link,x);
  }
  else
  {

  cout<<t1->item;
  getch();
  exit(1);
  }
 }

 }
 void g_bfs(struct tree *t1,int x)
 {
  // struct tree *q;
   struct tree *p;
   struct tree *r;
  p=NULL;
  while(t1!=NULL)
  {
   if(p==NULL)
   {
     if(t1->item==x)
      {
      cout<<t1->item;
      getch();
      break;
      }
      else
      cout<<t1->item<<"--";
   }

   while(p!=NULL)
   {
     r=t1;
     while(x!=r->item && r!=NULL)
      {
      cout<<r->item<<" --";
      r=r->link;
      }
     if(x==r->item)
      {
	    cout<<r->item;
	    getch();
	    exit(1);
      }
      p=p->link;

   }
   p=t1;
   t1=t1->son;
  }
 }
 void maketree(int x)
 {
 t=(struct tree *)malloc(sizeof(struct tree));
 t->item=x;
 t->son=NULL;
 t->link=NULL;
 }
 void setson(struct tree *t1,int x)
 {
 struct tree *ts;
 ts=(struct tree *)malloc(sizeof(struct tree));
 ts->item=x;
 t1->son=ts;
 ts->son=NULL;
 ts->link=NULL;
 }
 void setbrother(struct tree *t1,int x)
 {
 struct tree *tb;
 tb=(struct tree *)malloc(sizeof(struct tree));
 tb->item=x;
 t1->link=tb;
 tb->son=NULL;
 tb->link=NULL;
 }
 void main()
 {
 clrscr();
 char ch='a';
 struct tree *q;
 int x;
 cout<<"\n\t Enter the root node"<<endl;
 cin>>x;
 maketree(x);
 //enter all sons at one level
// cout<<t->item;
 struct tree *p;
 cout<<"\n\t Do u want to enter nodes at next level?(y/n)"<<endl;
 cin>>ch;
 q=t;

 char opt;
 while(ch=='y')
 {
  p=q;
  if(q!=NULL)
  {
  cout<<"\n\tEnter the node at next level for"<<p->item<<endl;
  cin>>x;
  setson(p,x);
  cout<<"\n\tDo u want to enter its brothers?(y/n)"<<endl;
  cin>>opt;
  p=p->son;
  while (opt=='y' && p!=NULL){
       cout<<"\n\tEnter its other brothers"<<endl;
       cin>>x;
       setbrother(p,x);
       p=p->link;
       cout<<"\n\t Enter the brothers' further??"<<endl;
       cin>>opt;
		}
  cout<<"Enter the son for the next node at the same level??"<<endl;
  cin>>opt;
   if(opt=='y')
   q=q->link;
   else
       {
       cout<<"Enter any node at next level??"<<endl;
       cin>>ch;
	  if(ch=='y')
	  q=q->son;

       }
  }
  else
   {
   cout<<"No brother or son found"<<endl;
   getch();
   break;

  }

 }
 getch();
 clrscr();
 q=t;
  cout<<"The tree is"<<endl;
  cout<<q->item<<";";
  cout<<q->son->item<<",";
  q=q->son;
   while(q!=NULL)
   {
   q=q->link;
   cout<<q->item<<",";

   }

  getch();

  clrscr();
  cout<<"1. Start dfs"<<endl;
  cout<<"2. Start bfs"<<endl;
  cin>>ch;
  switch(ch)
  {
    case '1': cout<<"Enter the node to be searched-->  ";
	      cin>>x;
	      g_dfs(t,x);
	      break;
    case '2': cout<<"Enter the node to be searched-->  ";
	      cin>>x;
	      g_bfs(t,x);
	      break;
  }


 getch();
 }

hanoi

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

void towers(int n,char frompeg,char topeg, char auxpeg)
{
	if(n==1)
	{
		cout<<"\nmove disk 1 from peg "<<frompeg<<" to peg "<<topeg;
		return;
	}
	towers(n-1,frompeg,auxpeg,topeg);
	cout<<"\nmove disk "<<n<<" from peg "<<frompeg<<" to peg "<<topeg;
	towers(n-1,auxpeg,topeg,frompeg);
}

void main()
{       clrscr();
       //	int gd=DETECT,gm;
       //	initgraph(&gd,&gm,"y:\\borlandc\\bgi");
       //	setbkcolor(BLUE);
       //	setcolor(RED);
	int n;
	//clrscr();
       //	settextstyle(4,0,5);
       //	outtextxy(30,20,"\nEnter the number of disks");
	cout<<"Enter the number of disks";
	cout<<"\n\n\n\n\n";
	cin>>n;

	towers(n,'A','C','B');
	getch();
}

infxpost

#include<iostream.h>
#include<stdio.h>
#include<conio.h>
#include<stdlib.h>
#include<string.h>

struct stack
{
 char val;
 stack * link;
};

void push(char val,stack **top)
{
stack * node = new stack;
node->val=val;
node->link=*top;
*top=node;
}

char pop(stack **top)
{
if(top!=NULL)
  {
    stack * temp= *top;
    char n=temp->val;
    (*top)=(*top)->link;
    delete temp;
    return n;
  }
  return NULL;
}

int empty(stack * top)
{
if (top == NULL)
  return 1;
else
  return 0;
}

int precedence(char a,stack *top)
{
char *op="+-*/^",*result1,*result2,op1[2],op2[2];
op1[0]=a;op1[1]=0;
op2[0]=top->val;op2[1]=0;
result1=strstr(op,op1);
result2=strstr(op,op2);
if(strlen(result1) >= strlen(result2)) //exp[i] prec is less than top of stack
 return 1;
else
 return 0;
}



void main()
{
clrscr();
stack * top =NULL;
char exp[1000],result[1000]="",temp;
int a,b,c,k=0;
cout<<"enter the expression:";
gets(exp);
strcat(exp,")");
for(int i=0;exp[i]!=0;i++)
 switch(exp[i])
 {
  case '+' :while(precedence(exp[i],top) && !empty(top))
	    { temp=pop(&top);
	      result[k++]=temp;
	    }
	    push(exp[i],&top);
	    break;
  case '-' :while(precedence(exp[i],top) && !empty(top))
	    { temp=pop(&top);
	      result[k++]=temp;
	    }
	    push(exp[i],&top);
	    break;
  case '*' :while(precedence(exp[i],top) && !empty(top))
	    { temp=pop(&top);
	      result[k++]=temp;
	    }
	    push(exp[i],&top);
	    break;
  case '/' :while(precedence(exp[i],top) && !empty(top))
	    { temp=pop(&top);
	      result[k++]=temp;
	    }
	    push(exp[i],&top);
	    break;
  case '^' :while(precedence(exp[i],top) && !empty(top))
	    { temp=pop(&top);
	      result[k++]=temp;
	    }
	    push(exp[i],&top);
	    break;
  case ')' :do{
	       temp=pop(&top);
	       if(temp==')')
		break;
	       result[k++]=temp;
	       }while(!empty(top));
	     break;
  case '0' :
  case '1' :
  case '2' :
  case '3' :
  case '4' :
  case '5' :
  case '6' :
  case '7' :
  case '8' :
  case '9' :
  case 'a' :
  case 'b' :
  case 'c' :
  case 'd' :
  case 'e' :
  case 'f' :
  case 'g' :
  case 'h' :
  case 'i' :
  case 'j' :
  case 'k' :
  case 'l' :
  case 'm' :
  case 'n' :
  case 'o' :
  case 'p' :
  case 'q' :
  case 'r' :
  case 's' :
  case 't' :
  case 'u' :
  case 'v' :
  case 'w' :
  case 'x' :
  case 'y' :
  case 'z' :
  case 'A' :
  case 'B' :
  case 'C' :
  case 'D' :
  case 'E' :
  case 'F' :
  case 'G' :
  case 'H' :
  case 'I' :
  case 'J' :
  case 'K' :
  case 'L' :
  case 'M' :
  case 'N' :
  case 'O' :
  case 'P' :
  case 'Q' :
  case 'R' :
  case 'S' :
  case 'T' :
  case 'U' :
  case 'V' :
  case 'W' :
  case 'X' :
  case 'Y' :
  case 'Z' :result[k++]=exp[i];break;
  case '(':break;
  default  :cout<<"invalid Input";
 }
 result[k]=0;

 if(!empty(top))
   cout<<"invalid expession";
 else
  cout<<"result:"<<result;

getch();
}

inorder

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<string.h>
#include<process.h>
#include<stdio.h>
#define max 100
#define TRUE 1
#define FALSE 0

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

struct node * maketree(int x)
{
 struct node *p;
 p=(struct node *) malloc(sizeof(struct node));
 p->info=x;
 p->left=NULL;
 p->right=NULL;
 return(p);
}

void setleft(struct node *p, int x)
{
 if(p==NULL)
 cout<<"Void insertion"<<endl;
 else if (p->left != NULL)
 cout<<"Invalid Insertion"<<endl;
 else
 p->left=maketree(x);
}

void setright(struct node *p, int x)
{
 if(p==NULL)
 cout<<"Void insertion"<<endl;
 else if (p->right != NULL)
 cout<<"Invalid Insertion"<<endl;
 else
 p->right=maketree(x);
}

struct stack
 {
  int top;
  struct node* item[max];
 };
 int empty(struct stack *ps)
 {
  if(ps->top==-1)
  return(TRUE);
  else
  return(FALSE);
 }

 void push(struct stack *ps, struct node *x)
 {
  if(ps->top== max-1)
  {
   cout<<"Stack Overflow";
   exit(1);
  }
  else
  ps->item[++(ps->top)]=x;
  return;
}

 struct node* pop(struct stack *ps)
 {
  if(empty(ps))
  {
   cout<<"Stack Underflow";
   exit(1);
  }
  return(ps->item[ps->top--]);
 }

void intrav2( struct node * tree)
{
 struct stack *s;
 struct node *p;
 s->top=-1;
 p=tree;
 do
 {
 while(p!=NULL)
  {
   push(s,p);
   p=p->left;
  }
  if(!empty(s))
  {
   p=pop(s);
   cout<<endl<<p->info;
   p=p->right;
  }
 } while(!empty(s)|| p!=NULL);
}

void main()
{
clrscr();
struct node * ptree;
struct node *p,*q;
int number;
cout<<"Enter the nodes";
scanf("%d",&number);
ptree=maketree(number);
scanf("%d",&number);
while(number!=-1)
{
 p=q=ptree;
 while(number!=p->info && q!=NULL)
 {
  p=q;
  if(number<p->info)
  q=p->left;
  else
  q=p->right;
 }
 if (number<=p->info)
 setleft(p,number);
 else
 setright(p,number);
 scanf("%d",&number);
}
intrav2(ptree);
getch();
}

insert

#include<stdio.h>
#include<conio.h>
#include<iostream.h>
void insertionsort(int x[] , int n)
{
 int i,k,y;
 for(k=1;k<n;k++)
 {
   y=x[k];
   for(i=k-1;i>=0 && y<x[i];i--)
   x[i+1]=x[i];
   x[i+1]=y;
 }

}
void main()
{
int n,i,d[40];
clrscr();
cout<<"Enter the no of elements to sort";
cin>>n;
cout<<"\nEnter the elements";
for(i=0;i<n;i++)
cin>>d[i];
insertionsort(d,n);
cout<<"\nThe sorted list";
for(i=0;i<n;i++)
cout<<d[i]<<endl;

getch();

}

merge

#include<alloc.h>
#include<stdio.h>
#include<conio.h>
void Merge(int * Array1,int lb1,int ub1,int * Array2, int lb2, int ub2, int * Array3,int lb3)
{
int a=lb1,b=lb2;
int *temp=(int *)malloc((ub2-lb2+ub1-lb1)*sizeof(int));
int tempi=0;
while(a<(ub1)&&b<(ub2))
{
if(Array1[a]<Array2[b])
{
temp[tempi]=Array1[a];
a++;
}
else
{
temp[tempi]=Array2[b];
b++;
}
tempi++;
}
while(a<(ub1))
{
temp[tempi]=Array1[a];a++;tempi++;
}
while(b<(ub2))
{
temp[tempi]=Array2[b];b++;tempi++;
}
tempi--;
while(tempi>=0)
{
Array3[lb3+tempi]=temp[tempi];
tempi--;
}
}
void MergeSort(int * Array,int lb,int ub)
{
if(ub<=lb) return ;
else
{
int middle = (ub+lb)/2 ;
MergeSort(Array,lb,middle);

MergeSort(Array,middle+1,ub);

Merge(Array,lb,middle+1,Array,middle+1,ub+1,Array,lb);
}
}


void main()
{
int * Array;
clrscr();
printf("\n  Enter -1 to stop entering item to array");

int temp;
int i=0;
int j;
do
{
scanf("%d",&temp);
if(temp>=0)
Array[i++] = temp;
}while(temp>=0);
MergeSort(Array,0,i-1);
printf("\nArray after merging is \n");
for(j=0;j<i;j++)
printf("\t%d",Array[j]);
getch();
}

postorder

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<string.h>
#include<process.h>
#include<stdio.h>
#define max 100
#define TRUE 1
#define FALSE 0

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

struct node * maketree(int x)
{
 struct node *p;
 p=(struct node *) malloc(sizeof(struct node));
 p->info=x;
 p->left=NULL;
 p->right=NULL;
 return(p);
}

void setleft(struct node *p, int x)
{
 if(p==NULL)
 cout<<"Void insertion"<<endl;
 else if (p->left != NULL)
 cout<<"Invalid Insertion"<<endl;
 else
 p->left=maketree(x);
}

void setright(struct node *p, int x)
{
 if(p==NULL)
 cout<<"Void insertion"<<endl;
 else if (p->right != NULL)
 cout<<"Invalid Insertion"<<endl;
 else
 p->right=maketree(x);
}

struct stack
 {
  int top;
  struct node* item[max];
 };

int empty(struct stack *ps)
 {
  if(ps->top==-1)
  return(TRUE);
  else
  return(FALSE);
 }

void push(struct stack *ps, struct node* x)
 {
  if(ps->top== max-1)
  {
   cout<<"Stack Overflow";
   exit(1);
  }
  else
  ps->item[++(ps->top)]=x;
  return;
}

struct node* pop(struct stack *ps)
 {
  if(empty(ps))
  {
   cout<<"Stack Underflow";
   exit(1);
  }
  return(ps->item[ps->top--]);
}


void postrav2( struct node *tree)
{

 struct stack *s;
 struct node *p,*q;
 s->top=-1;
 p=tree;
 cout<<endl;
 push(s,tree);

 while(!empty(s))
 {
 while(tree!=NULL)
 {
   if(tree->right!=NULL)
     {
     tree->right->info=-tree->right->info;
     push(s,tree->right);
     }
     if(tree->left!=NULL)
     push(s,tree->left);

     tree=tree->left;
  }
     q=pop(s);
     if(q->info>0)
     cout<<q->info;
     else
     {
     tree=q;
     q->info=-q->info;
     push(s,q);
     }
}
}

void main()
{
clrscr();
struct node * ptree;
struct node *p,*q;
int number;
cout<<"ENTER THE NODES OF THE TREE";

scanf("%d",&number);
ptree=maketree(number);
scanf("%d",&number);
while(number!=-1)
{
 p=q=ptree;
 while(number!=p->info && q!=NULL)
 {
  p=q;
  if(number<p->info)
  q=p->left;
  else
  q=p->right;
 }
 if (number<=p->info)
 setleft(p,number);
 else
 setright(p,number);
 scanf("%d",&number);
}
//cout<<"In main";
postrav2(ptree);
getch();
}

preorder

#include<iostream.h>
#include<conio.h>
#include<alloc.h>
#include<string.h>
#include<process.h>
#include<stdio.h>
#define max 100
#define TRUE 1
#define FALSE 0

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

struct node * maketree(int x)
{
 struct node *p;
 p=(struct node *) malloc(sizeof(struct node));
 p->info=x;
 p->left=NULL;
 p->right=NULL;
 return(p);
}

void setleft(struct node *p, int x)
{
 if(p==NULL)
 cout<<"Void insertion"<<endl;
 else if (p->left != NULL)
 cout<<"Invalid Insertion"<<endl;
 else
 p->left=maketree(x);

}


void setright(struct node *p, int x)
{
 if(p==NULL)
 cout<<"Void insertion"<<endl;
 else if (p->right != NULL)
 cout<<"Invalid Insertion"<<endl;
 else
 p->right=maketree(x);

}


struct stack
 {
  int top;
  struct node* item[max];
 };

 int empty(struct stack *ps)
 {
  if(ps->top==-1)
  return(TRUE);
  else
  return(FALSE);
 }

 void push(struct stack *ps, struct node* x)
 {
  if(ps->top== max-1)
  {
   cout<<"Stack Overflow";
   exit(1);
  }
  else
  ps->item[++(ps->top)]=x;
  return;
 }

 struct node* pop(struct stack *ps)
 {
  if(empty(ps))
  {
   cout<<"Stack Underflow";
   exit(1);
  }
  return(ps->item[ps->top--]);
 }


void pretrav2( struct node *tree)
{

 struct stack *s;
 struct node *p;
 s->top=-1;
 p=tree;
 cout<<endl;
 //cout<<tree->info<<endl;
 //push(s,tree);
 while(tree!=NULL)
 {
  cout<<tree->info<<endl;
 if(tree->right!=NULL)
 push(s,tree->right);
 if(tree->left!=NULL)
 tree=tree->left;
 else{
 if(!empty(s))
  tree=pop(s);
 else if(empty(s))
 tree=NULL;
  }
 //cout<<tree->info<<endl;

 }

}

void main()
{
clrscr();
struct node * ptree;
struct node *p,*q;
int number;
cout<<"ENTER THE NODES OF THE TREE";

scanf("%d",&number);
ptree=maketree(number);
scanf("%d",&number);
while(number!=-1)
{

 p=q=ptree;
 while(number!=p->info && q!=NULL)
 {
  p=q;
  if(number<p->info)
  q=p->left;
  else
  q=p->right;
 }
 if (number<=p->info)
 setleft(p,number);
 else
 setright(p,number);
 scanf("%d",&number);
}
//cout<<"In main";
pretrav2(ptree);
getch();
}

prims

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

int n;
class node
{
	public:

	int nno,known,dist,pno;
	int adjn;
	int **cost;

	void nodes(int d)
	{
		known=0;dist=10000;pno=-1;
		nno=d;
	}

	void adjacency(int p)
	{
		adjn=p;
		int wt,no;
		cost=new int*[n];

		for(int i=0;i<n;i++)
		cost[i]=new int[2];

		for(i=0;i<n;i++)
		{
			cost[i][0]=-1;
			cost[i][1]=-1;

		}

		cout<<"Enter the adjacent nodes and their weights "<<endl;

		for(i=0;i<adjn;i++)
		{
			cin>>no;cin>>wt;
			cost[no][0]=no;
			cost[no][1]=wt;

		}

		for(i=0;i<n;i++)
		{
			if(i==nno)
			{
				cost[i][0]=0;
				cost[i][1]=0;
				continue;

			}

			if(cost[i][0]==-1)
			{
				cost[i][0]=i;
				cost[i][1]=10000;

			}

		}



	}

};

int findmin(int**x,int sn,node*p)
{
	int min;
	for(int i=1;i<n;i++)
	{
		if(x[i][1]!=10000)
		{p[i].dist=x[i][1];
		 p[i].pno=sn;
		}
	}
	i=0;
	min=i;
	while(p[i].known==1)
	i++;
	min=i;

	for(int j=i+1;j<n;j++)
	{
		if(x[min][1]>x[j][1])
		min=j;

	}

	return min;

}


int findmin1(int**x,int sn,node*p)
{
	int min;
	for(int i=0;i<n;i++)
	{
		if(x[i][1]!=10000&&p[i].known!=1)
		{
		       if(p[i].dist>x[i][1])
		       {
				p[i].dist=x[i][1];
				p[i].pno=sn;
		       }


		}

	}
	i=0;
	min=i;

	while(p[i].known==1)
	i++;
	min=i;

	for(int j=i+1;j<n;j++)
	{
		if(p[j].known==1)
		continue;

		if(p[min].dist>p[j].dist)
		min=j;

	}
	return min;

}

void main()
{
	clrscr();
	cout<<"Please enter the no-of nodes in the Graph "<<endl;
	cin>>n;
	node*p=new node[n];
	for(int i=0;i<n;i++)
	{
		p[i].nodes(i);

	}
	clrscr();
	for(i=0;i<n;i++)
	{
		int a;
		cout<<"Enter the no-of nodes adjacent to node "<<i<<endl;
		cin>>a;
		p[i].adjacency(a);

	}

	p[0].known=1;
	p[0].dist=0;
	p[0].pno=-1;
	int sn=0,sno;

	for(i=0;i<n;i++)
	{
		if(i==0)
		{
			sno=sn;
			sn=findmin(p[sn].cost,sn,p);
			p[sn].known=1;
			p[sn].pno=sno;
			p[sn].dist=p[sno].cost[sn][1];

		}
		else
		{	sno=sn;
			sn=findmin1(p[sn].cost,sn,p);
			p[sn].known=1;
		}

	}

		clrscr();
			cout<<endl<<endl;
			cout<<"Node"<<"   "<<"Known"<<"   "<<"Dist"<<"   "<<"Parent"<<endl;
			for(int ii=0;ii<n;ii++)
			{cout<<ii<<"      "<<p[ii].known<<"       "<<p[ii].dist<<"       "<<p[ii].pno<<endl<<endl;}
			cout<<endl<<endl;
			cout<<"The weight is :- "<<endl;
			int sum=0;
			for(i=0;i<n;i++)
			sum+=p[i].dist;
			cout<<sum<<endl;


			getch();



}

queen

#include<iostream.h>
#include<stdlib.h>
#include<conio.h>
#define FALSE 0
#define TRUE 1

int trying(int);
void drawboard(void);
int good(int,int);

static short int board[8][8];

void main()
{
 clrscr();
 int i,j;
 for(i=0;i<8;i++)
  for(j=0;j<8;j++)
   board[i][j]=FALSE;
    if(trying(0)==TRUE)
	drawboard();
  getch();
}

int trying(int n)
{
 int i;
 randomize();
 for(i=0;i<8;i++)
 {
  if(n==0)
  i=random(8);
  board[n][i]=TRUE;
  if(n==7 && good(n,i)==TRUE)
   return TRUE;
  if(n<7 && good(n,i)==TRUE && trying(n+1)==TRUE)
   return TRUE;
  board[n][i]=FALSE;
 }
 return FALSE;
}

void drawboard(void)
{
 int i,j;
 for(i=0;i<8;i++)
 {
  for(j=0;j<8;j++)
  cout<<board[i][j]<<" ";
  cout<<"\n";
 }
}

int good(int row,int col)
{
 int temp=row-1,m=col-1,n=col+1;
  while(temp>=0)
   {
    if(n<=7)
    {
     if(board[temp][n]==TRUE)
      return FALSE;
     else
     n++;
    }

    if(m>=0)
    {
     if(board[temp][m]==TRUE)
      return FALSE;
     else
     m--;
    }

    if(board[temp][col]==TRUE)
     return FALSE;
    temp--;
   }
   return TRUE;
}

quick

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

partition(int x[],int lb,int ub)
{
	int up,down,a;
	a=x[lb];
	up=ub;
	down=lb;
	while(down<up)
	{
		while(x[down]<=a && down<=up)
		down++;
		while(x[up]>a)
		up--;
		if(down<up)
		{
			int t=x[down];
			x[down]=x[up];
			x[up]=t;
		}
	}
	x[lb]=x[up];
	x[up]=a;
	return(up);
}

int quick(int * x,int lb,int ub)
{
	if(lb>ub)
		return 0;
	int j=partition(x,lb,ub);
	quick(x,lb,j-1);
	quick(x,j+1,ub);
	return 0;
}

void main()
{
	clrscr();
	int a[10],i,j,k,n,lb,ub;
	cout<<"enter the no of elements:";
	cin>>n;
	for(i=0;i<n;i++)
	{
		cout<<"enter a["<<i+1<<"]";
		cin>>a[i];
	}
	lb=0;
	ub=n-1;
	quick(a,lb,ub);
	cout<<"Sorted List\n";
	for(i=0;i<n;i++)
		cout<<"  "<<a[i]<<"\n";
	getch();
}

salesman

/*Best First Search*/
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>


typedef struct dtype
			{
				int dist;
				int status;
			}node;
			
int fun1(node *p,int n);
main()
{
	node **a;
	int i,j,n,tot=0,temp,pos=0;
	char **name;
	clrscr();
	printf("\n How many cities to visit : ");
	scanf("%d",&n);

	//allocating memory to names of cities
	name=(char **)malloc(2*n);
	for(i=0;i<n;i++)
		name[i]=(char *)malloc(12);

	// allocating mem to array which stores distance b/w diff cities
	a=(node **)malloc(2*n);
	for(i=0;i<n;i++)
		a[i]=(node *)malloc(sizeof(node)*n);

	printf("\nEnter the name of these cities \n");
	for(i=0;i<n;i++)
		scanf("%s",name[i]);

	for(i=0;i<n;i++)
		for(j=i;j<n;j++)
		{
			a[i][j].status=a[j][i].status=0;// Initially status of each is 0
			if(i==j)
			{
				a[i][j].dist=0; //distance b/w same city is 0
				continue;
			}
			printf("Enter the distance between   %s   and   %s : ",name[i],name[j]);
			scanf("%d",&a[i][j].dist);
			a[j][i].dist=a[i][j].dist;// copying the upper triangle elements
										//	to lower triangle elements
		 }

	printf("\n\n          ");
	for(i=0;i<n;i++)
			printf("%10s",name[i]);
	printf("\n");
	for(i=0;i<n;i++)
	{
		printf("\n");
		printf("%10s",name[i]);
		for(j=0;j<n;j++)
		  printf("%10d",a[i][j].dist);
	}

	printf("\n");
	printf("\nCity Travelled at no.  %d  is   %s ",1,name[pos]);
	for(i=1;i<n;i++)
	{
		for(j=0;j<n;j++)
			a[j][pos].status=1;
		//	if(i==n-1)
		 //	break;
		temp=pos;
		pos=fun1(a[temp],n);
		tot=tot+a[temp][pos].dist;
		printf("\nCity Travelled at no.  %d  is   %s ",i+1,name[pos]);
	}
	printf("\n\nTotal distance covered using Best First Search is %d",tot);

	getch();
	return 0;
}

int fun1(node *p,int n)
{
	int i,j,pos,temp=32766;
	for(i=0;i<n;i++)
	{
		if(p[i].status==1)
			continue;
		else
			if(temp>p[i].dist&&p[i].dist!=0)
			  {
					temp=p[i].dist;
					pos=i;
				}
	}
	return(pos);
}


select

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

void selection(int x[],int n)
{
int i,j,large,indx;
for(i=n-1;i>0;i--)
{
	large=x[0];
	indx=0;
	for(j=1;j<=i;j++)
	{
		if(x[j]>large)
		{
			large=x[j];
			indx=j;
		}
	}
	x[indx]=x[i];
	x[i]=large;

	}
}

void main()
{
	clrscr();
	int a[100];
	int num;
	cout<<endl<<"How many elements are there in array:";
	cin>>num;
	cout<<endl<<"Enter array elements:";
	for(int h=0;h<num;h++)
	cin>>a[h];
	selection(a,num);
	cout<<"The sorted array is:"<<endl;
	for(h=0;h<num;h++)
	cout<<a[h];
	getch();
}

seq_search

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

int sequentialsearch(int * a, int m, int item)
{

	int k;
	for(k=0;k<=m;k++)
	{
		if(a[k]==item)
			return k;
	}
	return -1;
}


void main()
{
	clrscr();
	int array[20],n,i,num,result;

	cout<<"Enter the no of elements in the array:";
	cin>>n;

	for(i=0;i<n;i++)
	{
		cin>>array[i];
	}

	cout<<"Enter the no you want to search:";
	cin>>num;

	result = sequentialsearch(array,n-1,num);
	if ( result== -1)
		cout<<"Number not found";
	else
		cout<<"The number has been found at position:"<<result;
	getch();
}

seq_sort

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

void main()
{
	clrscr();
	int array[20],i,j,n;

	cout<<"\nEnter number of elements you want to sort:";
	cin>>n;

	for(i=0;i<n;i++)
	{
		cin>>array[i];
	}

	for(i=0;i<n;i++)
	{
		for(j=i+1;j<n;j++)
		{
			if(array[i]>array[j])
			{
				int temp = array[i];
				array[i] = array[j];
				array[j] = temp;
			}
		}
	}

	cout<<"\nThe sorted list is:";
	for(i=0;i<n;i++)
	{
		cout<<"\n"<<array[i];
	}
	getch();
}

tictac

#include<stdio.h>
#include<iostream.h>
#include<conio.h>
void printarray(int a[3][3])
{
int k=1;
cout<<endl<<endl;
for(int i=0;i<3;i++)
{
cout<<"\t";
 for(int j=0;j<3;j++)
  {
	if(a[i][j]==1)
	cout<<"*";
	else if(a[i][j]==0)
	cout<<"o";
	else
	{
	cout<<"B"<<k;
	k++;
	}
	if(j!=2)
	cout<<" | ";
  }
	if(i!=2)
	cout<<"\n\t----------\n";
}
cout<<endl<<endl;
}
void main()
{
clrscr();
int a[3][3]={2,2,2,2,2,2,2,2,2};
int l=0,blank,k=2,count=0;
int count1,count2;
int i,j,flag,flag2;
flag=0;
while(k>=1)
{
clrscr();

printarray(a);
cout<<"For Player 1 -- ' * ' "<<endl;
cout<<"For Player 2 -- ' o ' "<<endl;
if((count%2)==0)
{
cout<<"PLAYER 1's turn\n";
l=1;
}
else
{
cout<<"PLAYER 2's turn\n";
l=0;
}
cout<<"Which Blank Would you fill(enter in numerals alone)"<<endl;
cin>>blank;
k=0;
flag2=0;
for( i=0;i<3;i++)
{
 for( j=0;j<3;j++)
  {

	if(a[i][j]==2)
	k++;

	if(blank==k)
	{
	if(l==1)
	a[i][j]=1;
	else
	a[i][j]=0;
	 flag2=1;
	 break;
	}
  }
  if(flag2==1)
  break;
}
if(blank>k && k!=0)
{
cout<<"Invalid entry for the Blank Number\n Press Enter to again enter value";
getch();
}
else
count++;

for(i=0;i<3;i++)
{
count1=0;
count2=0;
 for(j=0;j<3;j++)
 {
     if(a[i][j]==l)
     count1++;
     if(a[j][i]==l)
     count2++;
  }
 // cout<<endl<<count1<<count2;
//   getch();
if(count1==3||count2==3)
{
flag=1;
break;
}
if(a[0][0]==l&&a[1][1]==l&&a[2][2]==l)
{
//printarray(a);
//cout<<"hello";
flag=1;
break;
}
if(a[2][0]==l&&a[1][1]==l&&a[0][2]==l)
{
//printarray(a);
//cout<<"hell1";
flag=1;
break;
}

}
if(flag==1)
{
cout<<"Player" << l << " has won the game";
cout<<endl<<"Final Board"<<endl;
printarray(a);
break;
}

}
if(k==0)
{
cout<<"The Game is Drawn";
}

getch();
}