Tuesday, January 19, 2010

TREE TRAVERSAL

#include
#include
#include
#include
#include

struct node
{
int data;
node *lftchild,*rtchild;
}*root,*temp,*t,*save;

void preorder(node *);
void inorder(node *);
void postorder(node *);

void main()
{
clrscr();
root=0;
int ch=0;
char c;
while(ch==0)
{
cout< cout< cout< cout< cout< cout< cin>>ch;
switch(ch)
{
case 1:
{
int item;
int found;
do
{
temp=(node *)malloc(sizeof (node));
cout< cin>>item;
temp->data=item;
found=0; //found is false
save=0;
t=root;
while(t!=0 && found==0)
{
save=t;
if(item==t->data)
found=1;
else
{
if(itemdata)
t=t->lftchild;
else
t=t->rtchild;
}
}
if(found==1) //found is true
cout<<"item is already in the tree"< else
{
if(save==0)
{
root=temp;
root->lftchild=0;
root->rtchild=0;
}
else
{
if(itemdata)
save->lftchild=temp;
else
save->rtchild=temp;
}
}
cout<<"do you want to insert again(y/n)::";
cin>>c;
}while(c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}

case 2:
{
t=root;
preorder(t);
ch=0;
break;
}

case 3:
{
t=root;
inorder(t);
ch=0;
break;
}

case 4:
{
t=root;
postorder(t);
ch=0;
break;
}

case 5:
{
ch=6;
exit(0);
}
}
}
getch();
}


void inorder(node *t)
{
if(t!=0)
{
inorder(t->lftchild);
cout<data;
inorder(t->rtchild);
}
}

void preorder(node *t)
{
if(t!=0)
{
cout<data;
preorder(t->lftchild);
preorder(t->rtchild);
}
}

void postorder(node *t)
{
if(t!=0)
{
postorder(t->lftchild);
postorder(t->rtchild);
cout<data;
}
}

SUM OF ARRAY ELEMENTS

#include
#include
void main()
{
clrscr();
int asum(int a[],int l);
int a[50],i,sum,n,count=0,l,c=0;
cout<<"Enter the maximum limit of array";
cin>>l;
cout<<"\nEnter the elements";
for(i=0;i<=l-1;i++)
{
cin>>a[i];
}
do
{
cout<<"\n1:sum with simple method\n2:sum using recursion\n3:exit\n";
cin>>n;
switch(n)
{
case 1:
{
sum=0,count=0;
for(i=0;i<=l-1;i++)
{
sum=sum+a[i];
count++;
}
cout<<"sum of all the elements of array using simple addition="< cout<<"\nloop was executed "< c=0;
break;
}
case 2:
{
sum=asum(a,l);
cout<<"sum of all elements of array using resursive method="< cout<<"\nrecursion was performed "< c=0;
break;
}
case 3:
{
c++;
}
}
}while(c==0);
}
int asum(int a[],int l)
{
int sum=0,count=0;
int m=l-1;
if(m<0)
{
count++;
}
else
{
sum=a[m]+asum(a,m);
count++;
}
return(sum);
}

STACK

#include
#include
#include
#include
#include
struct node
{
char info;
int data;
node *link;
}*top,*temp;
void main()
{
clrscr();
top=0;
int ch;
ch=0;
char c;
while(ch==0)
{
cout< cout<<"2:pop the elements of the stack"< cout<<"3:reverse the elements of the string"< cout<<"4:exit"< cout<<"enter your choice::";
cin>>ch;
switch(ch)
{
case 1:
{
do
{
temp=(node *)malloc(sizeof(node));
cout<<"enter the data/element::";
cin>>temp->data;
temp->link=top;
top=temp;
cout<<"do you still want to insert(y/n): ";
cin>>c;
}while (c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}

case 2:
{
int item;
if(top==0)
{
cout< ch=0;
break;
}
else
{
do
{
item=top->data;
top=top->link;
cout<<"deleted element is::"< cout< cin>>c;
}while((c=='y'|| c=='Y')&& top->data!=0);
if(c=='n' || c=='N')
{
ch=0;
break;
}
if(top==0)
{
cout< ch=0;
break;
}
}
}

case 3:
{
char item;
char a[20];
top=0;
cout< cin>>a;
for(int i=0;a[i]!='\0';i++)
{
temp=(node *)malloc(sizeof(node));
temp->info=a[i];
temp->link=top;
top=temp;
}
while(top!=0)
{
item=top->info;
top=top->link;
cout< }
cout< ch=0;
break;
}

case 4:
{
ch=5;
exit(0);
}

}
}
getch();
}

LINEAR SEARCH AND BINARY SEARCH

#include
#include
void main()
{
int a[100],n,i,item,l=-1,j,c=0,beg,end,mid,flag=0;
clrscr();
cout<<"\nEnter the number of element:";
cin>>n;
cout<<"Enter the number:\n";
for(i=0;i<=n-1;i++)
{
cin>>a[i];
}
do
{
cout<<"\n1:Linear search\n2:Binary search\n3:exit\n";
cin>>j;
switch(j)
{
case 1:
{
cout<<"Enter the no. to be search\n";
cin>>item;
for(i=0;i<=n-1;i++)
{
if(item==a[i])
{
l=i+1;
break;
}
}
if(l>=0)
cout<<"\n"< else
cout<<"\nItem does not exits";
break;
}
case 2:
{
cout<<"Enter the element to be searched";
cin>>item;
beg=0;
end=n-1;
while((beg<=end)&&(item!=a[mid]))
{
mid=((beg+end)/2);
if(item==a[mid])
{
cout<<"search is successfull\n";
cout<<"position of the item"< flag=flag+1;
}
if(item end=mid-1;
else
beg=mid+1;
}
if(flag==0)
cout<<"search is not successfull\n";
break;
}
case 3:
{
c++;
}
}
}while(c==0);
}

PRIORITY QUEUE

#include
#include
#include
#include

void insert(int [],int);
void remove(int[]);
void print(int[]);
void heapify(int[],int);
void adjust(int[],int,int);

int n=0; //size of array initialized to 0

void main()
{
clrscr();
char c;
int a[50];
int ch=0;
// for(i=1;i<=50;i++)
// a[i]=0;
while(ch==0)
{
cout< cout< cout< cout< cout< cin>>ch;
switch(ch)
{
case 1:
{
int x;
do
{
cout< cin>>x;
insert(a,x);
cout<<"Do you want to insert again(y/n)::";
cin>>c;
}while(c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}
case 2:
{
do
{
remove(a);
cout< cin>>c;
}while(c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}
case 3:
{
print(a);
ch=0;
break;
}
case 4:
{
ch=5;
exit(0);
}
}
}
getch();
}

void insert(int a[],int x)
{
if(n==0)
{
a[1]=x;
n++;
}
else
{
a[n+1]=x;
heapify(a,n+1);
n++;
}
}

void remove(int a[])
{
if(n==0)
cout<<"The queue is empty";
else
{
int item=a[1];
cout< a[1]=a[n];
a[n]=item;
n=n-1;
heapify(a,n);
}
}

void print(int a[])
{
if(n==0)
cout< else
{
cout< for(int i=1;i<=n;i++)
cout< }
}

void heapify(int a[],int n)
{
for(int i=n/2;i>=1;i--)
adjust(a,i,n);
}

void adjust(int a[],int i,int n)
{
int j=2*i;
int item=a[i];
while(j<=n)
{
if((j j=j+1;
if(item>=a[j])
break;
a[j/2]=a[j];
j=2*j;
}
a[j/2]=item;
}

QUICK SORT

#include
#include

void quicksort(int[],int,int);
int partition(int[],int,int);

void main()
{
clrscr();
int a[50],x,i;
cout<<"Enter the size of the array::";
cin>>x;
cout< for(i=1;i<=x;i++)
cin>>a[i];
quicksort(a,1,x);
cout< for(i=1;i<=x;i++)
cout< getch();
}

void quicksort(int a[],int p,int q)
{
if(p {
int j=partition(a,p,q+1);
quicksort(a,p,j-1);
quicksort(a,j+1,q);
}
}

int partition(int a[],int m,int p)
{
int v=a[m];
int i=m;
int j=p;
do
{
do
{
i++;
} while(a[i]>=v);
do
{
j--;
} while(a[j]<=v);
if(i {
int temp;
temp=a[i];
a[i]=a[j];
a[j]=temp;
}
}while(i>=j);
a[m]=a[j];
a[j]=v;
return(j);
}

MERGE SORT

#include
#include
#include

void mergesort(int[],int,int);
void merge(int[],int,int,int);

void main()
{
clrscr();
int a[50],b[50],x,i;
cout<<"Enter the size of the array::";
cin>>x;
cout< for(i=1;i<=x;i++)
cin>>a[i];
mergesort(a,1,x);
cout< for(i=1;i<=x;i++)
cout< getch();
}

void mergesort(int a[],int low,int high)
{
int mid;
if(low {
mid=floor((low+high)/2);
mergesort(a,low,mid);
mergesort(a,mid+1,high);
merge(a,low,mid,high);
}
}

void merge(int a[],int low,int mid,int high)
{
int b[50];
int h=low;
int i=low;
int 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(int k=j;k<=high;k++)
{
b[i]=a[k];
i++;
}
}
else
{
for(int k=h;k<=mid;k++)
{
b[i]=a[k];
i++;
}
}
for(int k=low;k<=high;k++)
a[k]=b[k];
}

MAXMIN

#include
#include
#include

int max;
int min;

void maxmin(int[],int,int);

void main()
{
clrscr();
int a[50],x,i;
cout<<"Enter the size of the array::";
cin>>x;
cout< for(i=1;i<=x;i++)
cin>>a[i];
maxmin(a,1,x);
cout< cout< getch();
}

void maxmin(int a[],int i,int j)
{
if(i==j)
{
max=a[i];
min=a[i];
}
else
{
if(i==(j-1))
{
if(a[i]>a[j])
{
max=a[i];
min=a[j];
}
else
{
max=a[j];
min=a[i];
}
}
else
{
int mid=floor((i+j)/2);
maxmin(a,i,mid);
int max1=max;
int min1=min;
maxmin(a,mid+1,j);
if(max1>max)
max=max1;
if(min1 min=min1;
}
}
}

KNAPSACK

#include
#include

void Gknapsack(int [],int,int);

void main()
{
clrscr();
int i,w[30],p[30],m,n;
/* w array for weights.
p array for profits.
m stands for maximum capacity.
n stands for number od items.
i is counter.*/
cout<<"enter the number of items::";
cin>>n;
cout< cin>>m;
cout< for(i=1;i<=n;i++)
cin>>w[i];
cout< for(i=1;i<=n;i++)
cin>>p[i];
Gknapsack(w,m,n);
getch();
}

void Gknapsack(int w[],int m,int n)
{
float x[30];
int U=m;
for(int i=1;i<=n;i++)
x[i]=0;
for(i=1;i<=n;i++)
{
if(w[i]>U)
break;
x[i]=1;
U=U-w[i];
}
if(i<=n)
x[i]=(float)U/w[i];
cout< for(i=1;i<=n;i++)
cout<}

HEAPSORT

#include
#include
#include

void heapsort(int [],int);
void heapify(int [],int);
void adjust(int[],int,int);

void main()
{
clrscr();
int a[50],x,i;
cout<<"Enter the size of the array::";
cin>>x;
cout< for(i=1;i<=x;i++)
cin>>a[i];
heapsort(a,x);
cout< for(i=1;i<=x;i++)
cout< getch();
}

void heapsort(int a[],int n)
{
heapify(a,n);
for(int i=n;i>=2;i--)
{
int temp;
temp=a[i];
a[i]=a[1];
a[1]=temp;
adjust(a,1,i-1);
}
}

void heapify(int a[],int n)
{
for(int i=floor(n/2);i>=1;i--)
adjust(a,i,n);
}

void adjust(int a[],int i,int n)
{
int j=2*i;
int item=a[i];
while(j<=n)
{
if((j j=j+1;
if(item>=a[j])
break;
a[j/2]=a[j];
j=2*j;
}
a[j/2]=item;
}

DEPTH FIRST SEARCH

#include
#include
#include
#include
#include

struct node
{
int data,status;
node *lftchild,*rtchild;
}*root,*temp,*t,*save,*xyz,*item;

struct stack
{
node *info;
stack *link;
}*top,*temp1;

void push(node *);
node *pop();

void main()
{
clrscr();
root=0;
int ch=0;
char c;
while(ch==0)
{
cout< cout< cout< cout< cin>>ch;
switch(ch)
{
case 1:
{
int item;
int found;
do
{
temp=(node *)malloc(sizeof (node));
cout< cin>>item;
temp->status=0;
temp->data=item;
found=0; //found is false
save=0;
t=root;
while(t!=0 && found==0)
{
save=t;
if(item==t->data)
found=1;
else
{
if(itemdata)
t=t->lftchild;
else
t=t->rtchild;
}
}
if(found==1) //found is true
cout<<"item is already in the tree"< else
{
if(save==0)
{
root=temp;
root->lftchild=0;
root->rtchild=0;
}
else
{
if(itemdata)
save->lftchild=temp;
else
save->rtchild=temp;
}
}
cout<<"do you want to insert again(y/n)::";
cin>>c;
}while(c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}

case 2:
{
top=0;
if(root==0)
{
cout< ch=0;
break;
}
push(root);
while(top!=0)
{
xyz=pop();
xyz->status=2;
cout<data<<"\t";
if(xyz->rtchild->status==0)
push(xyz->rtchild);
if(xyz->lftchild->status==0)
push(xyz->lftchild);
}
ch=0;
break;
}

case 3:
{
ch=5;
exit(0);
}
}
}
getch();
}

void push(node *p)
{
temp1=(stack *)malloc(sizeof(stack));
p->status=1;
temp1->info=p;
temp1->link=top;
top=temp1;
}

node *pop()
{
item=top->info;
top=top->link;
return(item);
}

BINARY TREE

#include
#include
#include
#include
#include

struct node
{
int data;
node *lftchild,*rtchild;
}*root,*temp,*t,*save;

void search(node *,int);
void print(node *);

void main()
{
clrscr();
root=0;
int ch=0;
char c;
while(ch==0)
{
cout< cout< cout< cout< cout< cin>>ch;
switch(ch)
{
case 1:
{
int item;
int found;
do
{
temp=(node *)malloc(sizeof (node));
cout< cin>>item;
temp->data=item;
found=0; //found is false
save=0;
t=root;
while(t!=0 && found==0)
{
save=t;
if(item==t->data)
found=1;
else
{
if(itemdata)
t=t->lftchild;
else
t=t->rtchild;
}
}
if(found==1) //found is true
cout<<"item is already in the tree"< else
{
if(save==0)
{
root=temp;
root->lftchild=0;
root->rtchild=0;
}
else
{
if(itemdata)
save->lftchild=temp;
else
save->rtchild=temp;
}
}
cout<<"do you want to insert again(y/n)::";
cin>>c;
}while(c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}

case 2:
{
int element;
cout< cin>>element;
do
{
search(root,element);
cout< cin>>c;
}while(c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}

case 3:
{
if(root==0)
{
cout<<"there is no element in the tree"< ch=0;
break;
}
else
{
t=root;
print(t);
}
ch=0;
break;
}

case 4:
{
ch=4;
exit(0);
}
}
}
getch();
}

void print(node *t)
{
if(t!=0)
{
print(t->lftchild);
cout<data;
print(t->rtchild);
}
}

void search(node *t,int element)
{
if(t==0)
cout<<"there is no element in the tree"< else
{
if(t->data==element)
cout<<"item found"< else
{
if(elementdata)
search(t->lftchild,element);
else
search(t->rtchild,element);
}
}
}

Thursday, January 14, 2010

BREADTH FIRST SEARCH

#include
#include
#include
#include
#include

struct node
{
int data,status;
node *lftchild,*rtchild;
}*root,*temp,*t,*save,*xyz,*item;

struct queue
{
node *info;
queue *linkback,*linkforward;
}*front,*rear,*temp1;

void insert(node *);
node* remove();

void main()
{
clrscr();
front=0;
rear=0;
root=0;
int ch=0;
char c;
while(ch==0)
{
cout<<<"1:insert into binary search tree"; cout<<<"2:print the elements of the tree"; cout<<<"3:exit"; cout<<<"enter your choice"; cin>>ch;
switch(ch)
{
case 1:
{
int item;
int found;
do
{
temp=(node *)malloc(sizeof (node));
cout<<<"enter the element to be inserted::"; cin>>item;
temp->status=0;
temp->data=item;
found=0; //found is false
save=0;
t=root;
while(t!=0 && found==0)
{
save=t;
if(item==t->data)
found=1;
else
{
if(itemdata)
t=t->lftchild;
else
t=t->rtchild;
}
}
if(found==1) //found is true
cout<<"item is already in the tree"<lftchild=0;
root->rtchild=0;
}
else
{
if(itemdata)
save->lftchild=temp;
else
save->rtchild=temp;
}
}
cout<<"do you want to insert again(y/n)::"; cin>>c;
}while(c=='y' || c=='Y');
if(c=='n' || c=='N')
{
ch=0;
break;
}
}

case 2:
{
// front=0;
if(root==0)
{
cout<<<"tree is empty"<status=2;
cout<data<<"\t"; if(xyz->lftchild->status==0)
insert(xyz->lftchild);
if(xyz->rtchild->status==0)
insert(xyz->rtchild);
}
ch=0;
break;
}

case 3:
{
ch=5;
exit(0);
}
}
}
getch();
}

void insert(node *p)
{
if(front==0 && rear==0)
{
temp1=(queue *)malloc(sizeof(queue));
p->status=1;
temp1->info=p;
temp1->linkback=0;
temp1->linkforward=0;
front=temp1;
rear=temp1;
}
else
{
temp1=(queue *)malloc(sizeof(queue));
p->status=1;
temp1->info=p;
rear->linkforward=temp1;
temp1->linkback=rear;
rear=temp1;
temp1->linkforward=0;
}
}

node *remove()
{
item=front->info;
front=front->linkforward;
return(item);
}