Pages

Friday, 8 November 2013

Data structures Lab through C++ programs

Lab Programs:

Week1: a)Write a C++ program to implement the Stack ADT using Array.
#include<iostream.h>
#include<conio.h>
#include<process.h>
#define size 5
template<class T>
class stack
{
public:
T s[size],top;
stack()
{
top=-1;
}
void push();
void pop();
void show();
};
template<class T>
void stack<T>::push()
{
T n;
                if(top==size-1)
                {
                cout<<"\nstack is overflow";
                }
                else
                {
                top++;
                cout<<"enter the value of n:";
                cin>>n;
                s[top]=n;
                cout<<"\nele is pushed";
                }
}
template<class T>
void stack<T>::pop()
{
T dx;
                if(top==-1)
                {
                cout<<"\nstack is underflow";
                }
                else
                {
                dx=s[top];
                top--;
                cout<<"\n poped ele is:"<<dx;
                }
}
template<class T>
void stack<T>::show()
{
T i;
                if(top==-1)
                {
                cout<<"\nstack is empty";
                }
                else
                {
                cout<<"\nstack  ele are:";
                                for(i=top;i>=0;i--)
                                {
                                cout<<"\n"<<s[i];
                                }
                }
}

void main()
{
int ur;
stack <int>s;
while(1)
{
clrscr();
cout<<"\n1.push";
cout<<"\n2.pop";
cout<<"\n3.show";
cout<<"\n4.exit";
cout<<"\nenter ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
                s.push();
                break;
case 2:
                s.pop();
                break;
case 3:
                s.show();
                break;
case 4:
                exit(0);
}
getch();
}
}

Week1: b)Write a C++ program to implement the Queue ADT using Array.

#include<iostream.h>
#include<conio.h>
#include<process.h>
#define size 5
template<class T>
class queue
{
public:
T q[size],rear,front;
queue()
{
rear=-1;
front=0;
}
void insert(T n);
void del();
void show();
};
template<class T>
void queue<T>::insert(T n)
{
                if(rear==size-1)
                {
                cout<<"\nqueue is over flow";
                }
                else
                {
                rear++;
                q[rear]=n;
                cout<<"\n"<<n<<"elemnet is inserted";
                }
}
template<class T>
void queue<T>::del()
{
T dx;
                if(rear==-1)
                {
                cout<<"\nqueue is under flow";
                }
                else if(front==rear)
                {
                 dx=q[front];
                front=0;
                rear=-1;
                cout<<"\n deleted elemnet is :"<<dx;
                }
                else
                {
                dx=q[front];
                front++;
                cout<<"\n deleted elemnet is :"<<dx;
                }
}
template<class T>
void queue<T>::show()
{
T i;
                if(rear==-1)
                {
                cout<<"\n queue is empty";
                }
                else
                {
                cout<<"\n queue elements are:";
                for(i=front;i<=rear;i++)
                {
                cout<<"\n"<<q[i];
                }
                }
}
void main()
{
int ur,n;
queue <int>q1;
while(1)
{
clrscr();
cout<<"\nqueue oprations:";
cout<<"\n1.insert:";
cout<<"\n2.del:";
cout<<"\n3.show:";
cout<<"\n4.exit:";
cout<<"\nenter the ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
                cout<<"enter the element for queue:";
                cin>>n;
                q1.insert(n);
                break;
case 2:
                q1.del();
                break;
case 3:
                q1.show();
                break;
case 4:
                exit(0);
}
getch();
}
}


Week 2:a)Write a C++ program to implement the Stack ADT using singly linked list.  

#include<iostream.h>
#include<conio.h>
#include<process.h>
template<class T>
class node
{
public:
T num;
node <T>*next;
};
template<class T>
class stack
{
public:
node <T>*top;
stack()
{
top=NULL;
}
void push();
void pop();
void show();
};
template<class T>
void stack<T>::push()
{
int n;
node <T>*new1;
cout<<"enter an ele for SLL:";
cin>>n;
new1=new node<T>;
new1->num=n;
new1->next=top;
top=new1;
cout<<"\nnode is pushed";
}
template<class T>
void stack<T>::pop()
{
node <T>*temp;
                if(top==NULL)
                {
                cout<<"\nstack is empty";
                }
                else
                {
                temp=top;
                top=top->next;
                temp->next=NULL;
                cout<<"\n poped ele is:"<<temp->num;
                delete temp;
                }
}
template<class T>
void stack<T>::show()
{
node <T>*temp;
                if(top==NULL)
                {
                cout<<"\nstack is empty";
                }
                else
                {
                temp=top;
                                cout<<"\nstack elements are:";
                                while(temp!=NULL)
                                {
                                cout<<"\n"<<temp->num;
                                temp=temp->next;
                                }
                }
}

void main()
{
int ur;
stack <int>s;
while(1)
{
clrscr();
cout<<"\n1.push";
cout<<"\n2.pop";
cout<<"\n3.show";
cout<<"\n4.exit";
cout<<"\nenter ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
                s.push();
                break;
case 2:
                s.pop();
                break;
case 3:
                s.show();
                break;
case 4:
                exit(0);
}
getch();
}
}


Week2:b)Write a C++ program to implement the Queue ADT using  singly linked list.

#include<iostream.h>
#include<conio.h>
#include<process.h>
template<class T>
class node
{
public:
T num;
node <T>*next;
};
template<class T>
class queue
{
public:
node <T>*front;
node <T>*rear;
queue()
{
front=NULL;
rear=NULL;
}
void insert();
void del();
void show();
};
template<class T>
void queue<T>::insert()
{
T n;
node <T>*new1;
cout<<"enter an ele for SLL:";
cin>>n;
new1=new node<T>;
new1->num=n;
new1->next=NULL;
if(front==NULL)
{
front=new1;
rear=new1;
}
else
{
rear->next=new1;
rear=new1;
}
cout<<"\nnode is inserted";
}
template<class T>
void queue<T>::del()
{
node <T>*temp;
                if(front==NULL)
                {
                cout<<"\nqueue is empty";
                }
                else if(front==rear)
                {
                temp=front;
                temp->next=NULL;
                front=NULL;
                rear=NULL;
                cout<<"\n deled ele is:"<<temp->num;
                delete temp;
                }
                else
                {
                temp=front;
                front=front->next;
                temp->next=NULL;
                cout<<"\n deled ele is:"<<temp->num;
                delete temp;
                }
}
template<class T>
void queue<T>::show()
{
node <T>*temp;
                if(front==NULL)
                {
                cout<<"\nqueue is empty";
                }
                else
                {
                temp=front;
                                cout<<"\nqueue elements are:";
                                while(temp!=NULL)
                                {
                                cout<<"\t"<<temp->num;
                                temp=temp->next;
                                }
                }
}

void main()
{
int ur;
queue <int>q1;
while(1)
{
clrscr();
cout<<"\n1.insert";
cout<<"\n2.del";
cout<<"\n3.show";
cout<<"\n4.exit";
cout<<"\nenter ur's choice:";
cin>>ur;
switch(ur)
{
case 1:
                q1.insert();
                break;
case 2:
                q1.del();
                break;
case 3:
                q1.show();
                break;
case 4:
                exit(0);
}
getch();
}
}


Week 3:

Write C++ programs to implement the deque ADT using a doubly linked list and an Array


//write a program to implement he deque ADT using Array.
//write a program to implement he deque ADT using doubly linked list.
#include<iostream.h>
#include<conio.h>
#include<process.h>
#define size 5
class dqueue
{
int rear;
int front;
int dq[size];
public:
dqueue()
{
rear=-1;
front=-1;
}
void insertrear(int);
void delfront();
void delrear();
void insertfront(int);
void show();
};
void dqueue::insertrear(int n)
{
            if(rear==size-1)
            {
            cout<<"\n dqueue is over flow";
            }
            else
            {
            rear++;
            dq[rear]=n;
            if(front==-1)
            {
            front=0;
            }
            }
}
void dqueue::delfront()
{
            if(rear==-1&&front==-1)
            {
            cout<<"\ndqueue is underflow";
            }
            else
            {
            int dx;
            dx=dq[front];
            cout<<"\n deleted elemnt is:"<<dx;
                        if(front ==rear)
                        {
                        front=-1;
                        rear=-1;
                        }
                        else
                        {
                        front++;
                        }
            }
}
void dqueue::delrear()
{
            if(rear==-1)
            {
            cout<<"\n delete is not possible";
            }
            else
            {
            int dx;
            dx=dq[rear];
            cout<<"\ndeleted element is:"<<dx;
                        if(rear==front)
                        {
                        rear=-1;
                        front=-1;
                        }
                        else
                        {
                        rear--;
                        }
            }
}
void dqueue::insertfront(int n)
{
            if(front==0&&rear==size-1)
            {
            cout<<"\ninsertion is not possible";
            }
            else
            {
            front--;
            dq[front]=n;
            }
}
void dqueue::show()
{
            if(front==-1&&rear==-1)
            {
            cout<<"\ndqueue is empty";
            }
            else
            {
            for(int i=front;i<=rear;i++)
            {
            cout<<"  "<<dq[i];
            }
            }
}

void main()
{
dqueue d;
int ur,iur,our,n;
while(1)
{
clrscr();
cout<<"\ndqueueue opration are:";
cout<<"\n1.input restricted queue:";
cout<<"\n2.ouput restricted queue:";
cout<<"\n3.exit";
cout<<"\nenter user choice:";
cin>>ur;
switch(ur)
{
      case 1:       while(1)
                        {

                        cout<<"\ninput restricted queue operations are:";
                        cout<<"\n1.insertrear";
                        cout<<"\n2.delfront";
                        cout<<"\n3.delrear";
                        cout<<"\n4.show";
                        cout<<"\n5.exit";
                        cout<<"\nenter user choice:";
                        cin>>iur;
                        switch(iur)
                        {
                        case 1:
                                    cout<<"enter the element for deque:";
                                    cin>>n;
                                    d.insertrear(n);
                                    break;
                        case 2:
                                    d.delfront();
                                    break;
                        case 3:
                                    d.delrear();
                                    break;

                        case 4:
                                    d.show();
                                    break;
                        case 5:
                                    exit(0);
                        default:cout<<"invalid entry";
                                    break;
                        }

                }
   case 2: while(1)
                        {

                        cout<<"\noutput restricted queue operations are:";
                        cout<<"\n1.insertfront";
                        cout<<"\n2.insertrear";
                        cout<<"\n3.delfront";
                        cout<<"\n4.show";
                        cout<<"\n5.exit";
                        cout<<"\nenter user choice:";
                        cin>>our;
                        switch(our)
                        {
                        case 1:
                                    cout<<"enter the element for deque:";
                                    cin>>n;
                                    d.insertfront(n);
                                    break;
                        case 2:
                                    cout<<"enter the element for deque:";
                                    cin>>n;
                                    d.insertrear(n);
                                    break;
                        case 3:
                                    d.delfront();
                                    break;
                        case 4:
                                    d.show();
                                    break;
                        case 5:
                                    exit(0);
                        default:cout<<"invalid entry";
                                    break;
            }

            }
      case 3:exit(0);
            default:cout<<"invalid entry";
                                    break;
}
getch();
}
}
#include<iostream.h>
#include<conio.h>
#include<process.h>
class node
{
public:
node *prev;
int num;
node *next;
};
class dequeedll
{
node *root;
node *last;
public:
dequeedll()
{
root=NULL;
last=NULL;
}
void create();
void show();
void f_insert();
void l_insert();
void f_del();
void l_del();
};
void dequeedll::create()
{
int n;
cout<<"\nEnter -1 to stop reading values.";
while(1)
{
cout<<"\nEnter element for dequeedll:";
cin>>n;
if(n==-1)
break;
node *new1;
new1=new node;
new1->num=n;
new1->prev=NULL;
new1->next=NULL;
if(root==NULL)
{
root=new1;
last=new1;
}
else
{
new1->prev=last;
last->next=new1;
last=new1;
}
}
}
void dequeedll::show()
{
node *temp;
if(root==NULL)
{
cout<<"\nList is empty.";
}
else
{
temp=root;
            while(temp!=NULL)
            {
            cout<<"  "<<temp->num;
            temp=temp->next;
            }
delete temp;
}
}
void dequeedll::f_insert()
{
int n;
node *new1;
cout<<"\nEnter element for new node:";
cin>>n;
new1=new node;
new1->num=n;
new1->next=NULL;
new1->prev=NULL;
root->prev=new1;
new1->next=root;
root=new1;
}
void dequeedll::l_insert()
{
int n;
node *new1;
cout<<"\nEnter element for new node:";
cin>>n;
new1=new node;
new1->num=n;
new1->next=NULL;
new1->prev=NULL;
last->next=new1;
new1->prev=last;
last=new1;
}
void dequeedll::f_del()
{
node *temp;
if(root==last)
{
temp=root;
root=NULL;
last=NULL;
cout<<"\nDeleted element is "<<temp->num;
delete temp;
}
else
{
temp=root;
root=root->next;
temp->next=NULL;
root->prev=NULL;
cout<<"\nDeleted element is "<<temp->num;
delete temp;
}
}
void dequeedll::l_del()
{
node *temp;
if(root==last)
{
temp=last;
root=NULL;
last=NULL;
cout<<"\nDeleted element is "<<temp->num;
delete temp;
}
else
{
temp=last;
last=last->prev;
temp->prev=NULL;
last->next=NULL;
cout<<"\nDeleted element is "<<temp->num;
delete temp;
}
}
void main()
{
int ur;
dequeedll d;
while(1)
{
clrscr();
cout<<"\ndequeedll operations\n";
cout<<"1.Create\n2.F_insert\n3.L_insert\n4.F_delete\n5.L_delete";
cout<<"\n6.Show\n7.Exit";
cout<<"\nEnter user's choice:";
cin>>ur;
switch(ur)
{
case 1:d.create();
break;
case 2:d.f_insert();
break;
case 3:d.l_insert();
break;
case 4:d.f_del();
break;
case 5:d.l_del();
break;
case 6:d.show();
            break;
case 7:exit(0);
default: cout<<"\nInvalid choice....Try again...!!";
break;
}
getch();
}
}
Week: 4   Write  a C++ programs to perform the following operations 
a) insert an element into a binary search tree

#include<iostream.h>
#include<conio.h>
class node
{
public:
    node *left;
   int data;
   node *right;
};
node *root=NULL;
class bst
{
public:
node * create(int data,node *p)
{
  if(!p)
  {
    p=new node;
    p->data=data;
    p->left=NULL;
    p->right=NULL;
    return(p);
  }
  if(data<p->data)
     p->left=create(data,p->left);
  else
  if(data>p->data)
     p->right=create(data,p->right);
  return (p);

}
node * del(node *p,node *q)
{
     node *temp;
    if(p->right !=NULL)
      p->right = del(p->right, q);
    else
    {
       dnode = p;
       q->data = p->data;
       p=p->left;
       delete temp;
   }
  return p;
}
node *deleteNode( node *p,int data)
{
    node *t;
   if(!p)
   {
      cout<<"\ndeleted element is not found ";
      return (p);
   }
   else
   {
      if(data <p->data)
p->left = deleteNode(p->left, data);
      else
if(data > p->data)
  p->right=deleteNode(p->right,data);
else
{
   t=p;
   if(t->right==NULL)
   {
      p=t->left;
      delete t;
   }
   else
    if(t->left==NULL)
    {
p=t->right;
delete t;
    }
    else
     t->left=del(t->left, t);
}
    }
    return (p);
}
node * search(node *p,node *q)
{
     node *dnode;
    if(p->right !=NULL)
      p->right = del(p->right, q);
    else
    {
       dnode = p;
       q->data = p->data;
       p=p->left;
       cout<<"\nsearch element is:"<<dnode->data;
   }
  return p;
}
node *searchNode( node *p,int data)
{
    node *t;
   if(!p)
   {
      cout<<"\n search element is not found ";
      return (p);
   }
   else
   {
      if(data <p->data)
p->left = searchNode(p->left, data);
      else
if(data > p->data)
  p->right=searchNode(p->right,data);
else
{
   t=p;
   if(t->right==NULL)
   {
      p=t->left;
      cout<<"\nsearch element is found:"<<t->data;
   }
   else
    if(t->left==NULL)
    {
p=t->right;
cout<<"\nsearch element is found:"<<t->data;
}
    else
     t->left=search(t->left, t);
}
    }
    return (p);
}


void preorder(node *p)
{
    if(p!=NULL)
    {
       cout<<"  "<<p->data;
       preorder(p->left);
       preorder(p->right);
    }
}
void inorder(node *p)
{
    if(p!=NULL)
    {
       inorder(p->left);
       cout<<"  "<<p->data;
       inorder(p->right);
    }
}
void postorder(node *p)
{
    if(p!=NULL)
    {
       postorder(p->left);
       cout<<"  "<<p->data;
       postorder(p->right);
    }
}
};
void main()
{
  int data;
  bst d;
   node *root =NULL;
  clrscr();
  while(1)
  {
     cout<<"\nenter the data for binary search tree:<-1 to exit>?";
     cin>>data;
     if(data==-1)
       break;
     root=d.create(data,root);
  }
    cout<<"\nelements in binary search tree:\n";
    cout<<"\npre order:";
    d.preorder(root);
    cout<<"\nin order:";
    d.inorder(root);
    cout<<"\npost order:";
    d.postorder(root);
    getch();
  while(1)
  {
     cout<<"\nenter to be  deleted element: <-1 to exit>:";
     cin>>data;
     if(data==-1)
       break;
     root=d.deleteNode(root,data);
     cout<<"\nTree after deletion: \n";
     d.preorder(root);
  }
  getch();
    while(1)
  {
     cout<<"\nenter to the search element: <-1 to exit>:";
     cin>>data;
     if(data==-1)
       break;
     root=d.searchNode(root,data);
  }
  getch();
}



 Week 5:
Write  a C++ programs that use recursive functions to traverse the given binary tree 
a) Preorder   b) Inorder   c) Postorder 
#include<iostream.h>
#include<conio.h>
template<class T>
struct node
{
node *left;
T data;
node *right;
};
template<class T>
class tree
{
node<T> *root;
public:
void create();
void insert(node<T> *p);
void traverse();
void preorder(node<T> *p);
void inorder(node<T> *p);
void postorder(node<T> *p);
};
template<class T>
void tree<T>::create()
{
T n;
root=NULL;
node<T> *new1;
while(1)
{
cout<<"'enter the data:";
cin>>n;
if(n==-1)
break;
new1 =new node<T>;
new1->data=n;
new1->left=NULL;
new1->right=NULL;
insert(new1);
}
}
template<class T>
void tree<T>::insert(node<T> *p)
{
if(root==NULL)
{
root=p;
}
else
{
node<T> *temp=root;
while(1)
{
if(p->data<temp->data)
{
if(temp->left!=NULL)
{
temp=temp->left;
}
else
{
temp->left=p;
return;
}
}
else
{
if(temp->right!=NULL)
{
temp=temp->right;
}
else
{
temp->right=p;
return;
}
}
}
}
}
template<class T>
void tree<T>::preorder(node<T> *p)
{
if(p!=NULL)
{
cout<<"  "<<p->data;
preorder(p->left);
preorder(p->right);
}
}
template<class T>
void tree<T>::inorder(node<T> *p)
{
if(p!=NULL)
{
inorder(p->left);
cout<<"  "<<p->data;
inorder(p->right);
}
}
template<class T>
void tree<T>::postorder(node<T> *p)
{
if(p!=NULL)
{
postorder(p->left);
postorder(p->right);
cout<<"  "<<p->data;
}
}
template<class T>
void tree<T>::traverse()
{
cout<<"\npreorder:";
preorder(root);
getch();
cout<<"\ninorder:";
inorder(root);
getch();
cout<<"\npostorder:";
postorder(root);
}
void main()
{
clrscr();
tree <int>t;
t.create();
t.traverse();
getch();
}

 Week 6:
Write  a C++ programs that use non-recursive functions to traverse the given binary tree 
a) Preorder   b) Inorder   c) Postorder 

#include<iostream.h>
#include<conio.h>
class node
{
public:
    node *left;
   int data,flag;
   node *right;
};
node *root=NULL;
class Bst
{
public:
node * create(int data,node *p)
{
  if(!p)
  {
    p=new node;
    p->data=data;
    p->left=NULL;
    p->right=NULL;
    return(p);
  }
  if(data<p->data)
     p->left=create(data,p->left);
  else
  if(data>p->data)
     p->right=create(data,p->right);
  return (p);
}
void non_preorder(node *p);
void non_inorder(node *p);
void non_postorder(node *p);
};
void Bst::non_preorder(node *p)
 {
 int top=0;
 node *s[20],*pt=p;
 s[0]=NULL;
 while(pt != NULL)
  {
  cout<<"\t"<<pt->data;
  if(pt->right != NULL)
   s[++top] = pt->right;
  if(pt->left != NULL)
   pt = pt->left;
  else
   pt = s[top--];
  }
 }

void Bst::non_inorder(node *p)
 {
 int top=0;
 node *s[20],*pt=p;
 s[0]=NULL;
 while(pt != NULL)
  {
  s[++top] = pt;
  pt = pt->left;
  }
 pt = s[top--];
 while(pt != NULL)
  {
  cout<<"\t"<<pt->data;
  if(pt->right != NULL)
   {
   pt = pt->right;
   while(pt != NULL)
    {
    s[++top] = pt;
    pt = pt->left;
    }
   }
   pt = s[top--];
  }
 }
void Bst::non_postorder(node *p)
 {
 node *s[20];
 int top=-1;
 node *temp=p;
 while(temp!=NULL)
  {
  while(temp!= NULL)
   {
   top++;
   s[top] = temp;
   temp = temp->left;
   }
  label:temp =s[top];
  top--;
  if(temp->flag==1)
   {
   cout<<"\t"<<temp->data;
   break;
   }
  else
   {
   temp->flag=1;
   top++;
   s[top] = temp;
   temp=temp->right;
   }
  }
  if(top>=0)
   goto label;
 }
void main()
{
  int data;
  Bst d;
   node *root =NULL;
  clrscr();
  while(1)
  {
     cout<<"\nenter the data for binary search tree:<-1 to exit>?";
     cin>>data;
     if(data==-1)
       break;
     root=d.create(data,root);
  }
    cout<<"\nelements in binary search tree:\n";
    cout<<"\npre order:";
    d.non_preorder(root);
    cout<<"\nin order:";
    d.non_inorder(root);
    cout<<"\npost order:";
    d.non_postorder(root);

  getch();
}

Week: 7 Write  a C++ programs for implementation of bfs and dfs for a given graph.

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

void create();  // For creating a graph
void dfs();  // For Deapth First Search(DFS) Traversal.
void bfs();  // For Breadth First Search(BFS) Traversal.

struct node  // Structure for elements in the graph
{
   int data,status;
   struct node *next;
   struct link *adj;
};

struct link  // Structure for adjacency list
{
   struct node *next;
   struct link *adj;
};

struct node *start,*p,*q;
struct link *l,*k;

int main()
{
   int choice;
   clrscr();
   create();
   while(1)
   {
      cout<<"-----------------------";
      cout<<"\n1:DFS \n2:BSF \n3:Exit \nEnter your choice: ";
      cin>>choice;
      switch(choice)
      {
case 1:
   dfs();
   break;
case 2:
   bfs();
   break;
case 3:
   exit(0);
   break;
default:
  cout<<"Incorrect choice!Re-enter your choice.";
   getch();
      }
   }
   return 0;
}

void create()    // Creating a graph
{
   int n,flag=0;
   start=NULL;
   cout<<"\nEnter the nodes in the graph(-1 to exit): ";
   while(1)
   {
   cout<<"\nEnter the data \n";
      cin>>n;
      if(n==-1)
break;
      p=new node;
      p->data=n;
      p->status=0;
      p->next=NULL;
      p->adj=NULL;
      if(flag==0)
      {
start=p;
q=p;
flag++;
      }
      else
      {
q->next=p;
q=p;
      }
   }
   p=start;
   while(p!=NULL)
   {
      cout<<"\nEnter the links to "<<p->data<<" (-1 to exit) : ";
      flag=0;
      while(1)
      {
cin>>n;
if(n==-1)
   break;
k=new link;
k->adj=NULL;
if(flag==0)
{
   p->adj=k;
   l=k;
   flag++;
}
else
{
   l->adj=k;
   l=k;
}
q=start;
while(q!=NULL)
{
   if(q->data==n)
      k->next=q;
   q=q->next;
}
      }
      p=p->next;
   }
   cout<<"-------------------------";
   return;
}


// Deapth First Search(DFS) Traversal.
void bfs()
{
   int qu[20],i=1,j=0;
   p=start;
   while(p!=NULL)
   {
      p->status=0;
      p=p->next;
   }
   p=start;
   qu[0]=p->data;
   p->status=1;
   while(1)
   {
      if(qu[j]==0)
break;
      p=start;
      while(p!=NULL)
      {
if(p->data==qu[j])
    break;
p=p->next;
      }
      k=p->adj;
      while(k!=NULL)
      {
q=k->next;
if(q->status==0)
{
   qu[i]=q->data;
   q->status=1;
   qu[i+1]=0;
   i++;
}
k=k->adj;
      }
      j++;
   }
   j=0;
   cout<<"Breadth First Search Results";
   cout<<"---------------------------";
   while(qu[j]!=0)
   {
      cout<<qu[j]<<"  ";
      j++;
   }
   getch();
   return;
}


// Breadth First Search(BFS) Traversal.
void dfs()
{
   int stack[25],top=1;
   cout<<"Deapth First Search Results";
   cout<<"---------------------------";
   p=start;
   while(p!=NULL)
   {
      p->status=0;
      p=p->next;
   }
   p=start;
   stack[0]=0;
   stack[top]=p->data;
   p->status=1;
   while(1)
   {
      if(stack[top]==0)
break;
      p=start;
      while(p!=NULL)
      {
if(p->data==stack[top])
   break;
p=p->next;
      }
      cout<<stack[top]<<"  ";
      top--;
      k=p->adj;
      while(k!=NULL)
      {
q=k->next;
if(q->status==0)
{
   top++;
   stack[top]=q->data;
   q->status=1;
}
k=k->adj;
      }
   }
   getch();
   return;
}
  

Week: 8 a)Write  a C++ program for implementing the Merge Sort

#include<iostream.h>
#include<conio.h>
template<class T>
class mergesort
{
public:
void msort(T *,T,T,T);
void mpass(T *,T ,T);
};
template<class T>
void mergesort<T>::msort(T a[],T first,T size,T last)
{
T temp[20];
T low=first;
T high=size+1;
T k=first;
while((low<=size)&&(high<=last))
{
if(a[low]<=a[high])
{
temp[k]=a[low];
low++;
}
else
{
temp[k]=a[high];
high++;
}
k++;
}
if(low<=size)
{
for(T i=low;i<=size;i++)
{
temp[k]=a[i];
k++;
}
}
else
{
for(T j=high;j<=last;j++)
{
temp[k]=a[j];
k++;
}
}
for(T i=first;i<=last;i++)
{
a[i]=temp[i];
}
}
template<class T>
void mergesort<T>::mpass(T a[],T first,T last)
{
if(first!=last)
{
T mid=(first+last)/2;
mpass(a,first,mid);
mpass(a,mid+1,last);
msort(a,first,mid,last);
}
}
void main()
{
mergesort <int>m1;
clrscr();
int a[20];
int n;
cout<<"enter the value of n:";
cin>>n;
for(int i=0;i<n;i++)
{
cout<<"\n enter the"<<i+1<<"element:";
cin>>a[i];
}
cout<<"\n original order:";
for(i=0;i<n;i++)
{
cout<<a[i]<<"   ";
}
m1.mpass(a,0,n-1);
cout<<"\n after sorting :";
for(i=0;i<n;i++)
{
coudt<<a[i]<<"   ";
}
getch();
}

Week: 8 b)Write  a C++ program for implementing the Heap Sort
#include<iostream.h>
#include<conio.h>
template<class T>
class heap
{
T i,j,k,temp;
public:
void heaps(T *,T);
void create(T *,T);
void display(T *,T);
};
template<class T>
void heap<T>::create(T a[],T n)
{
for(k=2;k<=n;k++)
{
i=k;
temp=a[k];
j=i/2;
while((i>1)&&(temp>a[j]))
{
a[i]=a[j];
i=j;
j=i/2;
if(j<1)
j=1;
}
a[i]=temp;
}
}
template<class T>
void heap<T>::heaps(T a[],T n)
{
for(int k=n;k>=2;k--)
{
temp=a[1];
a[1]=a[k];
a[k]=temp;
i=1;
int value=a[1];
j=2;
if((j+1)<k)
if(a[j+1]>a[j])
j++;
while((j<=(k-1))&&(a[j]>value))
{
a[i]=a[j];
i=j;
j=2*i;
if((j+1)<k)
if(a[j+1]>a[j])
j++;
else
if(j>n)
j=n;
a[i]=value;
}
cout<<"\n";
for(i=1;i<=n;i++)
cout<<" "<<a[i];
}
}
template<class T>
void heap<T>::display(T a[],T n)
{
for(i=1;i<=n;i++)
{
cout<<" "<<a[i];
}
}
 void main()
{
heap <int>h;
clrscr();
int a[20],n;
cout<<"\nEnter Value of n:";
cin>>n;
for(int i=1;i<=n;i++)
{
cout<<"\nEnter "<<i<<" Element:";
cin>>a[i];
}
cout<<"\n Original order:\n";;
h.display(a,n);
h.create(a,n);
cout<<"\n heap\n";
h.display(a,n);
h.heaps(a,n);
cout<<"\n after sorting:\n";
h.display(a,n);
getch();
}

Week 10:
write a C++ program to per form the following operation 
#include<iostream.h>
#include<conio.h>
#include<alloc.h>
# include<stdlib.h>
class node
{
public:
int data;
struct node *left,*right;
int ht;
};

class AVL
{
node *root;
int height(node *);
node *rotateright(node *);
node *rotateleft(node *);
node *RRrotation(node *);
node *LLrotation(node *);
node *LRrotation(node *);
node *RLrotation(node *);
int BF(node *);
public:
AVL()
{
root=NULL;
}
node *insert(node *,int);
node *delet(node *,int);
void preorder (node *);
void inorder(node *);
};

void main()
{
AVL A;
int x,n,i,ur;
node *root=NULL;
clrscr();
cout<<"\n\t CREATION OF AVL TREE ";

while(1)
{
cout<<"\n\t1.Create\n\t2.Insert\n\t3.Delete\n\t4.Display\n\t5.Exit ";
cout<<"\nEnter ur choice: ";
cin>>ur;
if(ur==-99)
break;
switch(ur)
{
case 1:
cout<<"\nEnter the number of elements: ";
cin>>n;
cout<<"\nEnter tree data: ";
for(i=0;i<n;i++)
{
cin>>x;
root=A.insert(root,x);
}
break;
case 2:
cout<<"\n\nEnter the data to be insert: ";
cin>>x;
A.insert(root,x);
break;
case 3:
cout<<"\n\nEnter a data which u have to delete: ";
cin>>x;
A.delet(root,x);
break;
case 4:
cout<<"\n\nPreorder Display:\n\n";
A.preorder(root);
cout<<"\n\nInorder Display:\n\n";
A.inorder(root);
break;
case 5:
exit(0);
}
}
getch();
}

node *AVL::insert(node *root,int x)

{
if(root==NULL)
{
root=new node;
root->data=x;
root->left=NULL;
root->right=NULL;
}
else
{
if(x>root->data)
{
root->right=insert(root->right,x);
if(BF(root)<=-2)
{
if(x>root->right->data)
root=RRrotation(root);
else
root=RLrotation(root);
}
}
else if(x<root->data)
{
root->left=insert(root->left,x);
if(BF(root)>=2)
{
if(x<root->left->data)
root=LLrotation(root);
else
root=LRrotation(root);
}
}
}
root->ht=height(root);
return(root);
}

node *AVL::delet(node *root,int x)

{
node *p;
if(root==NULL)
return(0);
else
if(x>root->data)
{
root->right=delet(root->right,x);
if(BF(root)>=2)
if(BF(root->left)>=0)
root=LLrotation(root);
else
root=LRrotation(root);
}
else if(x<root->data)
{
root->left=delet(root->left,x);
if(BF(root)<=-2)
if(BF(root->right)<=0)
root=RRrotation(root);
else
root=RLrotation(root);
}
else
{
if(root->right!=NULL)
{
p=root->right;
while(p->left!=NULL)
p=p->left;
root->data=p->data;
root->right=delet(root->right,p->data);
if(BF(root)>=2)
if(BF(root->left)>=0)
root=LLrotation(root);
else
root=LRrotation(root);
}
else
return(root->left);
}
root->ht=height(root);
return(root);
}

int AVL::height(node *root)

{
int LH,RH;
if(root==NULL)
return(0);
if(root->left==NULL)
LH=0;
else
LH=1+root->left->ht;
if(root->right==NULL)
RH=0;
else
RH=1+root->right->ht;
if(LH>RH)
return (LH);
else
return (RH);
}

int AVL::BF(node *root)

{
int LH,RH;
if(root==NULL)
return(0);
if(root->left==NULL)
LH=0;
else
LH=1+root->left->ht;
if(root->right==NULL)
RH=0;
else
RH=1+root->right->ht;
return(LH-RH);
}

node *AVL::rotateleft(node *x)

{
node *y;
y=x->right;
x->right=y->left;
y->left=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}

node *AVL::rotateright(node *x)

{
node *y;
y=x->left;
x->left=y->right;
y->right=x;
x->ht=height(x);
y->ht=height(y);
return(y);
}

node *AVL::LLrotation(node *root)

{
root=rotateright(root);
return(root);
}

node *AVL::RRrotation(node *root)

{
root=rotateleft(root);
return(root);
}

node *AVL::LRrotation(node *root)

{
root->left=rotateleft(root->left);
root=rotateright(root);
return(root);
}

node *AVL::RLrotation(node *root)

{
root->right=rotateright(root->right);
root=rotateleft(root);
return(root);
}

void AVL::preorder(node *root)

{
if(root!=NULL)
{

cout<<" \n"<<root->data<<" [BF= "<<BF(root)<<"]";
preorder(root->left);
preorder(root->right);
}
}

void AVL::inorder(node *root)

{
if(root!=NULL)
{
inorder(root->left);
cout<<" \n"<<root->data<<" [BF= "<<BF(root)<<"]";
inorder(root->right);
}

}

No comments:

Post a Comment