Quick Sort

#include<iostream.h>
#include<conio.h>
class list
 {
public:
 int n,q[20],cmp_count,mov_count;
 list()
  {
cmp_count=0;
mov_count=0;
  }
 void read()
  {
 cout<<"\nEnter the number of elements:";
 cin>>n;
      cout<<"\nEnter the elements:\n";
      for(int i=0;i<n;i++)
       {
      cin>>q[i];
       }
  }
      void swap(int x,int y)
       {
      int temp;
      temp=q[x];
      q[x]=q[y];
      q[y]=temp;
       }
      void quick_sort(int low,int high)
       {
      int pivot,i,j;
      if(low>high)
       return;
      i=low+1;
      j=high;
      pivot=q[low];
      while(i<=j)
       {
        while((q[i]<=pivot)&&(i<=high))
         {
       i++;
       cmp_count++;
         }
        cmp_count++;
        while((q[j]>pivot)&&(j>=low))
         {
       j--;
       cmp_count++;
         }
       cmp_count++;
       if(i<j)
        {
         swap(i,j);
          mov_count++;
        }
           }
          if(low<j)
      {
        swap(low,j);
        mov_count++;
           }
      quick_sort(low,j-1);
           quick_sort(j+1,high);
         }
             void display()
              {
                 cout<<"The sorted elements are:\n";
           for(int j=0;j<n;j++)
             {
          cout<<q[j]<<endl;
             }
           cout<<"\nNumber of comparisons:"<<cmp_count;
           cout<<"\nNumber of data movements:"<<mov_count;
              }
        int getsize()
               {
             return(n);
              }
    };
   void main()
    {
           clrscr();
     list l;
     l.read();
           l.quick_sort(0,l.getsize()-1);
           l.display();
           getch();
    }
Posted by No comments:
Labels: , , ,

Binary Tree Traversal

#include<iostream.h>
#include<conio.h>
class tree
 {
public:
 char info;
 tree *lchild;
 tree *rchild;
 };
class treetraversal
 {
private:
  char x;
public:
  void input(tree *p);
  void preorder(tree *p);
  void inorder(tree *p);
  void postorder(tree *p);
 };
void treetraversal::input(tree *ptr)
 {
cout<<"\n\tEnter the element:";
cin>>x;
if(x=='0')
          ptr->info='$';
else
      {
ptr->info=x;
cout<<"\n\t"<<ptr->info<<"Left is:\n"<<endl;
ptr->lchild=new tree;
input(ptr->lchild);
cout<<"\n\t"<<ptr->info<<"Right is :\n"<<endl;
ptr->rchild=new tree;
input(ptr->rchild);
}
 }
void treetraversal::preorder(tree *ptr)
 {
if(ptr->info!='$')
 {
cout<<ptr->info;
preorder(ptr->lchild);
preorder(ptr->rchild);
 }
 }
void treetraversal::inorder(tree *ptr)
 {
if(ptr->info!='$')
      {
           inorder(ptr->lchild);
 cout<<ptr->info;
 inorder(ptr->rchild);
 }
  }
 void treetraversal::postorder(tree *ptr)
  {
 if(ptr->info!='$')
  {
           postorder(ptr->lchild);
           postorder(ptr->rchild);
cout<<ptr->info;
  }
  }
 void main()
  {
 treetraversal t;
      tree *te=new tree;
      clrscr();
 t.input(te);
 cout<<"\n\tThe Pre-order traversal for the given tree is:";
 t.preorder(te);
      cout<<"\n\tThe In-order traversal for the given tree is:";
 t.inorder(te);
      cout<<"\n\tThe Post-order traversal for the given tree is:";
      t.postorder(te);
 getch();
  }
Posted by No comments:
Labels: , , ,

Singly Linked List

#include<iostream.h>
#include<string.h>
#include<conio.h>
#include<stdlib.h>
class Node
 {
public:
  int rollnumber;
  char name[20];
  Node *next;
 };
class List
 {
Node *START;
public:
  List();
  void addNode();
  int Search(int rollno, Node **current, Node **previous);
  int listEmpty();
  int delNode(int element);
  void traverse();
 };
List::List()
 {
START=NULL;
 }
void List::addNode()
 {
int rollno;
char nm[20];
cout<<"\n Enter the roll number of the student:";
cin>>rollno;
cout<<"\n Enter the name of the student:";
cin>>nm;
Node *newnode=new Node;
newnode->rollnumber=rollno;
strcpy(newnode->name,nm);
if(START==NULL||rollno<=START->rollnumber)
       {
         if((START!=NULL)&&(rollno==START->rollnumber))
          {
 cout<<"\n Duplicate roll numbers not allowed\n";
 return;
     }
         newnode->next=START;
   START=newnode;
   return;
       }
Node *previous, *current;
previous=START;
current=START;
while((current!=NULL)&&(rollno>=current->rollnumber))
       {
   if(rollno==current->rollnumber)
    {
cout<<"\n Duplicate roll numbers not allowed\n";
return;
    }
         previous=current;
   current=current->next;
       }
newnode->next=current;
previous->next=newnode;
 }
int List::listEmpty()
 {
if(START==NULL)
return 1;
else
return 0;
 }
int List::delNode(int rollno)
 {
Node *current,*previous;
if(Search(rollno,&previous,&current)==0)
return 0;
previous->next=current->next;
if(current==START)
START=START->next;
delete current;
return 1;
 }
int List:: Search(int rollno,Node **previous,Node **current)
 {
*previous=START;
*current=START;
while((*current!=NULL)&&(rollno!=(*current)->rollnumber))
 {
*previous=*current;
*current=(*current)->next;
      }
return(*current!=NULL);
 }
void List::traverse()
 {
if(listEmpty())
cout<<"\n List is enpty\n";
else
 {
  cout<<endl<<"The record in the list are:"<<endl;
  Node *currentNode;
 
for(currentNode=START;currentNode!=NULL;currentNode=currentNode->next)
 {
cout<<currentNode->rollnumber<<" "<<currentNode->name<<"\n";
 }
cout<<endl;
}
 }
void main()
 {
clrscr();
List obj;
int rollno;
char ch;
do
  {
   cout<<"Main Menu";
   cout<<endl<<"1.Add a record to the list"<<endl;
   cout<<"2.Delete a record from the list"<<endl;
   cout<<"3.View all the records in the list"<<endl;
   cout<<"4.Search for a record in the list"<<endl;
   cout<<"5.Exit"<<endl;
   cout<<"Enter the choice:";
   cin>>ch;
   switch(ch)
{
 case '1':
                     obj.addNode();
                     break;
 case '2':
                     if(obj.listEmpty())
                      {
                       cout<<endl<<"List is empty"<<endl;
                       break;
                      }
                     cout<<endl<<"\n Enter the roll number of the student  
                                           whose record is to be delete:";
                     cin>>rollno;
                     if(obj.delNode(rollno)==0)
                          cout<<endl<<"Record not found"<<endl;
                     else
                      {
                          cout<<endl<<"Record with roll
                                           number"<<rollno<<"delete"<<endl;
                      }
                     break;
 case '3':
                     obj.traverse();
                     break;




 case'4':
                     if(obj.listEmpty()==1)
                      {
                        cout<<"\n List is empty\n";
                        break;
                      }
                     Node *previous,*current;
                     cout<<endl<<"Enter the roll number of the student whose
                                                  record is to be searched:";
                     cin>>rollno;
                     if(obj.Search(rollno, &previous, &current)==0)
                          cout<<endl<<"Record not found"<<endl;
                     else
                      {
                        cout<<endl<<"Record found"<<endl;
                        cout<<"\nRoll number:"<<current->rollnumber;
                        cout<<"\n\nName:"<<current->name;
                        cout<<"\n";
                      }
                     break;
     case '5':
                      exit(0);
                      break;
   }
       }while(ch!=5);
getch();
 }
Posted by No comments:
Labels: , , ,

Queue Using Array

#include<iostream.h>

#include<conio.h>
class queue
 {
private:
  int q[10],front,rear,n,x,i;
public:
  queue()
   {
cout<<"Enter the no.of elements:";
cin>>n;
front=0;
rear=0;
   }
  void add()
   {
cout<<"Enter the element:";
cin>>x;
if(rear==n)
      {
   cout<<"Queue is full";
   return;
      }
else
 {
   rear=rear+1;
   q[rear]=x;
 }
  }
 int delet()
  {
    if(front==rear)
{
   cout<<"Queue is empty";
   return(0);
}
    else
{
        int y;
   front=front+1;
   y=q[front];
        return(y);
}
  }






 void display()
  {
for(i=front+1;i<=rear;i++)
 {
cout<<q[i]<<”\t”;
 }
  }
 };
void main()
 {
clrscr();
int choice;
queue q;
do
        {
cout<<"\n1.Add"<<endl;
cout<<"2.Delete"<<endl;
cout<<"3.Display"<<endl;
cout<<"4.Exit"<<endl;
cout<<"Enter the choice:";
cin>>choice;
if(choice==1)
 {
    q.add();
    cout<<"The elements after addition are "<<endl;
    q.display();
            }
if(choice==2)
            {
    int p;
    p=q.delet();
    cout<<"The deleted element is:"<<p;
    cout<<"\nThe element after deletion are "<<endl;
    q.display();
            }
if(choice==3)
 {
    cout<<"The queue elements are"<<endl;
               q.display();
 }
  }while(choice!=4);
getch();
 }
Posted by No comments:
Labels: , , ,

Stack Using Array

#include<iostream.h>
#include<conio.h>
class stack
 {
private:
  int s[10],top,n,x,i;
public:
 stack()
  { 
cout<<"Enter the No.of elements:";
cin>>n;
top=0;
  }
 void push()
       {
cout<<"Enter the element:";
cin>>x;
if(top>=n)
            {
    cout<<"Stack is full";
 }
     else
                 {
         top=top+1;
               s[top]=x;
            }
      }
int pop()
      {
          if(top==0)
           {
              cout<<"Stack is empty";
                   return(0);
                }
         else
     {
                   int y;
                   y=s[top];
                   top=top-1;
                  return(y);
                }
           }
void display()
           {
     for(i=top;i>0;i--)
     cout<<s[i]<<endl;
      }
  };


 void main()
  {
     clrscr();
     stack s;
int choice;
     do
        {
           cout<<"1.Push"<<endl;
cout<<"2.Pop"<<endl;
           cout<<"3.Display"<<endl;
           cout<<"4.Exit"<<endl;
           cout<<"Enter the choice:";
           cin>>choice;
           if(choice==1)
            {
               s.push();
               cout<<"\nThe element after push operation are:"<<endl;
               s.display();
            }
           if(choice==2)
            {
               int p;
               p=s.pop();
               cout<<"\nThe poped element is:"<<p;
               cout<<"\nThe element after pop operation are:"<<endl;
               s.display();
            }
           if(choice==3)
            {
               cout<<"The stack elements are"<<endl;
               s.display();
            }
        }while(choice!=4);
     getch();
 }
Posted by No comments:
Labels: , , ,
Subscribe to: Posts (Atom)
Related Posts with Thumbnails