Data Structures using C++

 #include< iostream > 
  #include< cstdlib > 
  #include< string > 
  using namespace std; 
  struct tree 
  { 
     int info; 
     tree *Left, *Right; 
  }; 
  tree *root; 
  class Binary_tree 
  { 
     string path; 
     public: 
       Binary_tree(); 
       void insert1(int); 
       tree *insert2(tree *, tree *); 
       void search(int); 
       void pretrav(tree *); 
       void intrav(tree *); 
       void posttrav(tree *); 
  }; 
  Binary_tree::Binary_tree() 
  { 
     root = NULL; 
  } 
  tree* Binary_tree::insert2(tree *temp,tree *newnode) 
  { 
     if(temp==NULL) 
     { 
       temp=newnode; 
     } 
     else if(temp->info < newnode->info) 
     { 
       insert2(temp->Right,newnode); 
       if(temp->Right==NULL) 
         temp->Right=newnode; 
     } 
     else 
     { 
       insert2(temp->Left,newnode); 
       if(temp->Left==NULL) temp->Left=newnode; 
     } 
     return temp; 
  } 
  void Binary_tree::insert1(int n) 
  { 
     tree *temp=root,*newnode; 
     newnode=new tree; 
     newnode->Left=NULL; 
     newnode->Right=NULL; 
     newnode->info=n; 
     root=insert2(temp,newnode); 
  } 
  void Binary_tree::pretrav(tree *t = root) 
  { 
     if(root == NULL) 
     { 
       cout<<"Nothing to display"; 
     } 
     else if(t != NULL) 
     { 
       cout<< t->info<<" "; 
       pretrav(t->Left); 
       pretrav(t->Right); 
     } 
  } 
  void Binary_tree::intrav(tree *t = root) 
  { 
     if(root==NULL) 
     { 
       cout<<"Nothing to display"; 
     } 
     else if(t!=NULL) 
     { 
       intrav(t->Left); 
       cout<< t->info<<" "; 
       intrav(t->Right); 
     } 
  } 
  void Binary_tree::posttrav(tree *t = root) 
  { 
     if(root==NULL) 
     { 
       cout<<"Nothing to display"; 
     } 
     else if(t!=NULL) 
     { 
       posttrav(t->Left); 
       posttrav(t->Right); 
       cout<< t->info<<" "; 
     } 
  } 
  void Binary_tree::search(int key) 
  { 
     tree *temp=root,*parent=root; 
     path = ""; 
     if(temp==NULL) 
     { 
       cout<<"The tree is empty"<< endl; 
     } 
     else 
     { 
       path = "root"; 
       while(temp!=NULL && temp->info!=key) 
       { 
         parent=temp; 
         if(temp->info< key) 
         { 
           temp=temp->Right; 
           path += "->Right"; 
         } 
         else 
         { 
           temp=temp->Left; 
           path += "->Left"; 
         } 
       } 
     } 
     if(temp==NULL) 
     { 
       cout<<"Key not found!"; 
     } 
     else 
     { 
       cout<<"Key is found\n"; 
       cout<<"Paht is: "; 
       cout<< path; 
     } 
  } 
  int main() 
  { 
     Binary_tree bt; 
     int choice, n, key; 
     while(1) 
     { 
       cout<<"\n\t1. Insert\n\t2. Search\n\t3. Preorder Traversal\n\t4. Inorder Treversal\n\t5. Postorder Traversal\n\t6. Exit"<< endl; 
       cout<<"Enter your choice: "; 
       cin>>choice; 
       switch(choice) 
       { 
         case 1: 
           cout<<"Enter item: "; 
           cin>>n; 
           bt.insert1(n); 
           break; 
         case 2: 
           cout<<"Enter element to search: "; 
           cin>>key; 
           bt.search(key); 
           break; 
         case 3: 
           cout<< endl; 
           bt.pretrav(); 
           break; 
         case 4: 
           cout<< endl; 
           bt.intrav(); 
           break; 
         case 5: 
           cout<< endl; 
           bt.posttrav(); 
           break; 
         case 6: 
           exit(0); 
       } 
     } 
     return 0; 
  }

  #include < iostream > 
  #include < cstdlib > 
  #include < string > 
  using namespace std; 
  class Dllist 
  { 
     private: 
       typedef struct Node 
       { 
         string name; 
         Node* next; 
         Node* prev; 
       }; 
       Node* head; 
       Node* last; 
     public: 
       Dllist() 
       { 
         head = NULL; 
         last = NULL; 
       } 
       bool empty() const { return head==NULL; } 
       friend ostream& operator <<(ostream& ,const Dllist& ); 
       void Insert(const string& ); 
       void Remove(const string& ); 
  }; 
  void Dllist::Insert(const string& s) 
  { 
     // Insertion into an Empty List. 
     if(empty()) 
     { 
       Node* temp = new Node; 
       head = temp; 
       last = temp; 
       temp->prev = NULL; 
       temp->next = NULL; 
       temp->name = s; 
     } 
     else 
     { 
       Node* curr; 
       curr = head; 
       while( s>curr->name && curr->next != last->next) curr = curr->next; 
     
       if(curr == head) 
       { 
         Node* temp = new Node; 
         temp->name = s; 
         temp->prev = curr; 
         temp->next = NULL; 
         head->next = temp; 
         last = temp; 
         // cout<<" Inserted "<< s <<" After "<< curr->name << endl; 
       } 
       else 
       { 
         if(curr == last && s>last->name) 
         { 
           last->next = new Node; 
           (last->next)->prev = last; 
           last = last->next; 
           last->next = NULL; 
           last->name = s; 
           // cout<<" Added "<< s <<" at the end "<< endl; 
         } 
         else 
         { 
           Node* temp = new Node; 
           temp->name = s; 
           temp->next = curr; 
           (curr->prev)->next = temp; 
           temp->prev = curr->prev; 
           curr->prev = temp; 
           // cout<<" Inserted "<< s <<" Before "<< curr->name<< endl; 
         } 
       } 
     } 
  } 
  ostream& operator<<(ostream& ostr, const Dllist& dl ) 
  { 
     if(dl.empty()) ostr << " The list is empty. "<< endl; 
     else 
     { 
       Dllist::Node* curr; 
       for(curr = dl.head; curr != dl.last->next; curr=curr->next) 
         ostr << curr->name <<" "; 
       ostr << endl; 
       ostr << endl; 
       return ostr; 
     } 
  } 
  void Dllist::Remove(const string& s) 
  { 
     bool found = false; 
     if(empty()) 
     { 
       cout<<" This is an empty list! "<< endl; 
       return; 
     } 
     else 
     { 
       Node* curr; 
       for(curr = head; curr != last->next; curr = curr->next) 
       { 
         if(curr->name == s) 
         { 
           found = true; 
           break; 
         } 
       } 
       if(found == false) 
       { 
         cout<<" The list does not contain specified Node"<         return; 
       } 
       else 
       { 
         // Curr points to the node to be removed. 
         if (curr == head && found) 
         { 
           if(curr->next != NULL) 
           { 
             head = curr->next; 
             delete curr; 
             return; 
           } 
           else 
           { 
             delete curr; 
             head = NULL; 
             last = NULL; 
             return; 
           } 
         } 
         if (curr == last && found) 
         { 
           last = curr->prev; 
           delete curr; 
           return; 
         } 
         (curr->prev)->next = curr->next; 
         (curr->next)->prev = curr->prev; 
         delete curr; 
       } 
     } 
  } 
  int main() 
  { 
     Dllist d1; 
     int ch; 
     string temp; 
     while(1) 
     { 
       cout<< endl; 
       cout<<" Doubly Linked List Operations "<< endl; 
       cout<<" ------------------------------"<< endl; 
       cout<<" 1. Insertion "<< endl; 
       cout<<" 2. Deletion "<< endl; 
       cout<<" 3. Display "<< endl; 
       cout<<" 4. Exit "<< endl; 
       cout<<" Enter your choice : "; 
       cin>>ch; 
       switch(ch) 
       { 
         case 1: cout<<" Enter Name to be inserted : "; 
           cin>>temp; 
           d1.Insert(temp); 
           break; 
         case 2: cout<<" Enter Name to be deleted : "; 
           cin>>temp; 
           d1.Remove(temp); 
           break; 
         case 3: cout<<" The List contains : "; 
           cout<< d1; 
           break; 
         case 4: system("pause"); 
           return 0; 
           break; 
       } 
     } 
  }

  #include< iostream.h > 
  #include< conio.h > 
  #include< stdlib.h > 
  class list 
  { 
     struct node 
     { 
        int data; 
        node *link; 
     }*p; 
    public: 
       void inslast(int); 
       void insbeg(int); 
       void insnext(int,int); 
       void delelement(int); 
       void delbeg(); 
       void dellast(); 
       void disp(); 
       int seek(int); 
       list(){p=NULL;} 
       ~list(); 
  }; 
  void list::inslast(int x) 
  { 
     node *q,*t; 
     if(p==NULL) 
     { 
        p=new node; 
        p->data=x; 
        p->link=NULL; 
     } 
     else 
     { 
        q=p; 
        while(q->link!=NULL) 
        q=q->link; 
        t=new node; 
        t->data=x; 
        t->link=NULL; 
        q->link=t; 
     } 
     cout<<"Inserted successfully at the end.."; 
     disp(); 
  } 
  void list:: insbeg(int x) 
  { 
     node *q; 
     q=p; 
     p=new node; 
     p->data=x; 
     p->link=q; 
     cout<<"Inserted successfully at the begining.."; 
     disp(); 
  } 
  void list::delelement(int x) 
  { 
     node *q,*r; 
     q=p; 
     if(q->data==x) 
     { 
        p=q->link; 
        delete q; 
        return; 
     } 
     r=q; 
     while(q!=NULL) 
     { 
        if(q->data==x) 
        { 
          r->link=q->link; 
          delete q; 
          return; 
        } 
        r=q; 
        q=q->link; 
     } 
     cout<<"Element u entered "<< x <<" is not found.."; 
  } 
  void list:: delbeg() 
  { 
     cout<<"The list before deletion:"; 
     disp(); 
     node *q; 
     q=p; 
     if(q==NULL) 
     { 
        cout<<"No data is present.."; 
        return; 
     } 
     p=q->link; 
     delete q; 
     return; 
  } 
  void list:: dellast() 
  { 
     cout<<"The list before deletion:"; 
     disp(); 
     node *q,*t; 
     q=p; 
     if(q==NULL) 
     { 
        cout<<"There is no data in the list.."; 
        return; 
     } 
     if(q->link==NULL) 
     { 
        p=q->link; 
        delete q; 
        return; 
     } 
     while(q->link->link!=NULL) 
        q=q->link; 
     q->link=NULL; 
     return; 
  } 
  list::~list() 
  { 
     node *q; 
     if(p==NULL) return; 
     while(p!=NULL) 
     { 
        q=p->link; 
        delete p; 
        p=q; 
     } 
  } 
  void list::disp() 
  { 
     node *q; 
     q=p; 
     if(q==NULL) 
     { 
        cout<<" No data is in the list.."; 
        return; 
     } 
     cout<<"The items present in the list are :"; 
     while(q!=NULL) 
     { 
        cout<<" "<< q->data; 
        q=q->link; 
     } 
  } 
  void list :: insnext(int value,int position) 
  { 
     node *temp,*temp1; 
     temp=p; 
     if(temp1==NULL) 
     { 
        temp1= new node; 
        temp1->data=value; 
        temp1->link=NULL; 
        p=temp1; 
        return; 
     } 
     for(int i=0;((i< position) && (temp->link!=NULL)) ;i++) 
     { 
        if(i==(position-1)) 
        { 
          temp1= new node; 
          temp1->data= value; 
          temp1->link=temp->link; 
          temp->link=temp1; 
        } 
        temp=temp->link; 
     } 
     //cout<<"Inserted successfully at the position.."<< position; 
     disp(); 
  } 
  int list::seek(int value) 
  { 
     node *temp; 
     temp=p; 
     int position=0; 
     while(temp!=NULL) 
     { 
        if(temp->data==value) 
          return position+1; 
        else 
        { 
          temp=temp->link; 
          position=position+1; 
        } 
     } 
     cout<<"Element "<< value <<" not found"; 
     return 0; 
  } 
  void main() 
  { 
    list l; 
    int ch,v,p,ps; 
    do 
    { 
       clrscr(); 
       cout<<"Operations on List.."; 
       cout<<" 
      1.Insertion 
      2.Deletion 
      3.Display 
      4.Seek 
      5.Exit"; 
       cout<<" Enter ur choice:"; 
       cin>>ch; 
       switch(ch) 
       { 
         case 1: 
            cout<<"1.Insertion at begining 
            2.Insertion at the end"; 
            cout<<"3.Insertion after the mentioned position"; 
            cout<<"Enter ur choice:"; 
            cin>>ps; 
            cout<<" Enter the value to insert:"; 
            cin>>v; 
            switch(ps) 
            { 
              case 1: 
                l.insbeg(v); 
                break; 
              case 2: 
                l.inslast(v); 
                break; 
              case 3: 
                cout << "Enter the position to insert the value:"; 
                cin>>p; 
                l.insnext(v,p); 
                break; 
   
              default: 
                cout<<"The choice is invalid"; 
                return; 
            } 
           break; 
           case 2: 
              cout<<"1.Delete the first element 
              2.Delete the last element"; 
              cout<<"3.Enter the element to delete from the list"; 
              cout<<"Enter ur choice:"; 
              cin>>ps; 
              switch(ps) 
              { 
                case 1: 
                  l.delbeg(); 
                  cout<<"The list after deletion:"; 
                  l.disp(); 
                  break; 
                case 2: 
                  l.dellast(); 
                  cout<<"The list after deletion:"; 
                  l.disp(); 
                  break; 
                case 3: 
                  l.disp(); 
                  cout<<"Enter the element to delete : "; 
                  cin>>v; 
                  l.delelement(v); 
                  cout<<"The list after deletion:"; 
                  l.disp(); 
                  break; 
                default: 
                  cout<<"The option is invalid..."; 
                  break; 
              } 
             break; 
             case 3: 
                l.disp(); 
                break; 
             case 4: 
                l.disp(); 
                cout<<"Enter the element to search:"; 
                cin>>v; 
                cout<<" The position of the element "<< v <<" is "<< l.seek(v); 
                getch(); 
                break; 
             case 5: 
                exit(1); 
             default: 
                cout<<"The option is invalid..."; 
                return; 
       } 
       getch(); 
    }while(ch!=5); 
    getch(); 
    return; 
  }

   #include< iostream.h > 
    #include< constream.h > 
    void read(int a[10],int n) 
    { 
      cout << "reading\n"; 
      for(int i=0;i < n;i++) 
        cin >> a[i]; 
    } 
    void display(int a[10],int n) 
    { 
      for(int i=0;i < n;i++) 
        cout << a[i] <<"\t"; 
    } 
    void shellsort(int a[10],int n) 
    { 
      int gap=n/2; 
      do 
      { 
        int swap; 
        do 
        { 
          swap=0; 
          for(int i=0;i < n-gap;i++) 
          if(a[i] > a[i+gap]) 
          { 
            int t=a[i]; 
            a[i]=a[i+gap]; 
            a[i+gap]=t; 
            swap=1; 
          } 
        } 
        while(swap); 
      } 
      while(gap=gap/2); 
    } 
    void main() 
    { 
      int a[10]; 
      int n; 
      clrscr(); 
      cout<<"enter n\n"; 
      cin>>n; 
      read(a,n); 
      cout<<"before sorting\n"; 
      display(a,n); 
      shellsort(a,n); 
      cout<<"\nafter sorting\n"; 
      display(a,n); 
      getch(); 
    }

  #include< iostream > 
  using namespace std; 
  int main() 
  { 
     int arr[10]; 
     int no_of_elements, key; 
     bool found = false; 
     cout<<"Enter the number of element: "; 
     cin>>no_of_elements; 
     for(int i = 0; i < no_of_elements; i++) 
     { 
       cout<<"arr["<< i <<"]: "; 
       cin>>arr[i]; 
     } 
     cout<<"Enter the value to search: "; 
     cin>>key; 
     for(int i=0;i< no_of_elements;i++) 
     { 
       if(key == arr[i]) 
       { 
         found = true; 
         cout<<"The value is found at index arr["<< i <<"]"; 
       } 
     } 
     if(!found) 
     { 
       cout<<"Key not found!"; 
     } 
     return 0; 
  }

   #include < iostream.h > 
    const int MAX = 10 ; 
    class array 
    { 
      private : 
        int arr[MAX] ; 
        int count ; 
      public : 
        array( ) ; 
        void add ( int item ) ; 
        void sort( ) ; 
        void display( ) ; 
    } ; 
    array :: array( ) 
    { 
      count = 0 ; 
      for ( int i = 0 ; i < MAX ; i++ ) 
        arr[i] = 0 ; 
    } 
    void array :: add ( int item ) 
    { 
      if ( count < MAX ) 
      { 
        arr[count] = item ; 
        count++ ; 
      } 
      else 
        cout << "\nArray is full" << endl ; 
    } 
    void array :: sort( ) 
    { 
      int temp ; 
      for ( int i = 0 ; i <= count - 2 ; i++ ) 
      { 
        for ( int j = i + 1 ; j <= count - 1 ; j++ ) 
        { 
          if ( arr[i] > arr[j] ) 
          { 
            temp = arr[i] ; 
            arr[i] = arr[j] ; 
            arr[j] = temp ; 
          } 
        } 
      } 
    } 
    void array :: display( ) 
    { 
      for ( int i = 0 ; i < count ; i++ ) 
        cout << arr[i] << " " ; 
      cout << endl ; 
    } 
    void main( ) 
    { 
      array a ; 
      a.add ( 25 ) ; 
      a.add ( 17 ) ; 
      a.add ( 31 ) ; 
      a.add ( 13 ) ; 
      a.add ( 2 ) ; 
      cout << "\nSelection sort.\n" ; 
      cout << "\nArray before sorting:" << endl ; 
      a.display( ) ; 
      a.sort( ) ; 
      cout << "\nArray after selection sorting:" << endl ; 
      a.display( ) ; 
    }

#include 
   #include 
   #include 
   #include 
   int Partition(int low,int high,int arr[]); 
   void Quick_sort(int low,int high,int arr[]); 
   void main() 
   { 
     int *a,n,low,high,i; 
     clrscr(); 
     cout<<"Quick Sort Algorithm";<< endl 
     cout<<"Enter number of elements:"; 
     cin>>n; 
     a=new int[n]; 
     /* cout<<"enter the elements:"; 
     for(i=0;i< n;i++) 
     cin>>a;*/ 
     for(i=0;i < n;i++) 
     a[i]=rand()%100; 
     clrscr(); 
     cout<<"Initial Order of elements"; 
      for(i=0;i< n;i++) 
      cout<< a[i] <<" "; 
        cout <<""; 
     high=n-1; 
     low=0; 
     Quick_sort(low,high,a); 
     cout <<"Final Array After Sorting:"; 
        for(i=0;i < n;i++) 
        cout << a[i] <<" "; 
     getch(); 
   } 
   /*Function for partitioning the array*/ 
   int Partition(int low,int high,int arr[]) 
   
   { 
      int i,high_vac,low_vac,pivot/*,itr*/; 
      pivot=arr[low]; 
      while(high>low) 
      { 
        high_vac=arr[high]; 
        while(pivot< high_vac) 
        { 
          if(high < =low) break; 
          high--; 
          high_vac=arr[high]; 
        } 
        arr[low]=high_vac; 
        low_vac=arr[low]; 
        while(pivot > low_vac) 
        { 
          if(high < =low) break; 
          low++; 
          low_vac=arr[low]; 
        } 
        arr[high]=low_vac; 
      } 
      arr[low]=pivot; 
      return low; 
   } 
   void Quick_sort(int low,int high,int arr[]) 
   { 
      int Piv_index,i; 
      if(low < high) 
      { 
        Piv_index=Partition(low,high,arr); 
        Quick_sort(low,Piv_index-1,arr); 
        Quick_sort(Piv_index+1,high,arr); 
      } 
   }

  #include < iostream.h > 
  #include < conio.h > 
  #include < stdlib.h > 
  struct node 
   { 
     char name[20]; 
     int age; 
     float height; 
     node *nxt; 
   }; 
  node *start_ptr=NULL; 
  int main() 
  { 
     void push (); 
     void pop(); 
     char ch; 
     clrscr(); 
     cout<<"Queue"; 
     cout<<"-----"; 
     do 
     { 
       cout<<"Select an operation"; 
       cout<<"u->push"; 
       cout<<"o->pop"; 
       cout<<"e->exit"; 
       cin>>ch; 
       switch(ch) 
       { 
         case 'u': 
           push(); 
           break; 
         case 'o': 
           pop(); 
           break; 
         case 'e': 
           exit(0); 
       } 
     }while(ch!='e'); 
     return 0; 
  } 
  void pop() 
  { 
     node *temp1,*temp2; 
     if(start_ptr==NULL) 
       cout<<"The list is empty"; 
     else 
     { 
       temp1=start_ptr; 
       temp2=temp1; 
       while(temp1->nxt!=NULL) 
       { 
         temp2=temp1; 
         temp1=temp1->nxt; 
       } 
       if(temp1==temp2) 
       { 
         cout<< temp1->name<<","; 
         cout<< temp1->age<<", "; 
         cout<< temp1->height; 
         start_ptr=NULL; 
       } 
       else 
       { 
         cout<< temp1->name<<", "; 
         cout<< temp1->age<<", "; 
         cout<< temp1->height; 
         temp2->nxt=NULL; 
         delete temp1; 
       } 
     } 
  } 
  void push () 
   { 
     node *temp; 
     temp = new node; 
     cout << "Please enter the name of the person: "; 
     cin >> temp->name; 
     cout << "Please enter the age of the person: "; 
     cin >> temp->age; 
     cout << "Please enter the height of the person: "; 
     cin >> temp->height; 
     if (start_ptr == NULL) 
     { 
       temp->nxt=NULL; 
       start_ptr = temp; 
     } 
     else 
     { 
       temp->nxt=start_ptr; 
       start_ptr=temp; 
     } 
   }

 #include< iostream.h > 
  #include< conio.h > 
  const int MAX=5; 
  class pqueue 
  { 
      int front,rear; 
     public: 
        struct data 
        { 
          int val,p,o; 
        }d[MAX]; 
        pqueue() 
        { 
          front=rear=-1; 
        } 
        void insert(data d1); 
        data deletion(); 
        void display(); 
  }; 
  void pqueue :: insert(data d1) 
  { 
     if(rear==MAX-1) 
        cout<<"Priority Queue is Full"; 
     else 
     { 
        rear++; 
        d[rear]=d1; 
        if(front==-1) 
          front=0; 
        data temp; 
        for(int i=front;i<=rear;i++) 
          for(int j=i+1;j<=rear;j++) 
          { 
            if(d[i].p > d[j].p) 
            { 
              temp=d[i]; 
              d[i]=d[j]; 
              d[j]=temp; 
            } 
            else 
            { 
              if(d[i].p==d[j].p) 
              { 
                if(d[i].o > d[j].o) 
                { 
                  temp=d[i]; 
                  d[i]=d[j]; 
                  d[j]=temp; 
                } 
              } 
            } 
          } 
     } 
  } 
  data pqueue :: deletion() 
  { 
     data d1; 
     if(front==-1) 
        cout<<"Priority Queue is Empty"; 
     else 
     { 
        d1=d[front]; 
        if(front==rear) 
          front=rear=-1; 
        else 
          front++; 
     } 
     return d1; 
  } 
  void pqueue :: display() 
  { 
      if(front==-1) 
        cout<<"Priority Queue is Empty"; 
      else 
      { 
        for(int i=front;i<=rear;i++) 
        { 
          cout<<"Object :"<< i+1<< endl; 
          cout<<"Value ="<< d[i].val<< endl; 
          cout<<"Priority="<< d[i].p<< endl; 
          cout<<"Order = "<< d[i].o<< endl; 
        } 
      } 
  } 
  void main() 
  { 
     pqueue p1; 
     data d1; 
     char op; 
     do 
     { 
       int ch; 
       clrscr(); 
       cout<<"----------Menu-------------"; 
       cout<<" 1.Insertion 
        2.Deletion 
        3.Display 
        4.Exit"; 
       cout<<"Enter your Choice<1..4> ?"; 
       cin>>ch; 
       switch(ch) 
       { 
        case 1 : cout<<"Enter Value ?"; 
          cin>>d1.val; 
          cout<<"Enter Priority?"; 
          cin>>d1.p; 
          cout<<"Enter Order ?"; 
          cin>>d1.o; 
          p1.insert(d1); 
          break; 
        case 2 : d1=p1.deletion(); 
          cout<<"Value = "<< d1.val<< endl; 
          cout<<"Priority = "<< d1.p<< endl; 
          cout<<"Order ="<< d1.o<< endl; 
          break; 
        case 3 : p1.display(); 
          break; 
        } 
        cout<<"Do You Want to Continue < Y/N > ?"; 
        cin>>op; 
     }while(op=='Y' || op=='y'); 
     getch(); 
  }

  #include< iostream.h > 
  #include< conio.h > 
  const int MAX = 5; 
  class cqueue 
  { 
      int a[MAX],front,rear; 
     public : 
        cqueue() 
        { 
          front=rear=-1; 
       } 
       void insert(int ); 
       int deletion(); 
       void display(); 
  }; 
  void cqueue :: insert(int val) 
  { 
      if((front==0 && rear==MAX-1) || (rear+1==front)) 
        cout<<" Circular Queue is Full"; 
     else 
     { 
       if(rear==MAX-1) 
          rear=0; 
       else 
          rear++; 
       a[rear]=val; 
     } 
     if(front==-1) 
       front=0; 
  } 
  int cqueue :: deletion() 
  { 
     int k; 
     if(front==-1) 
       cout<<"Circular Queue is Empty"; 
     else 
     { 
       k=a[front]; 
       if(front==rear) 
          front=rear=-1; 
       else 
       { 
          if(front==MAX-1) 
            front=0; 
          else 
            front++; 
       } 
     } 
     return k; 
  } 
  void cqueue :: display() 
  { 
     int i; 
     if(front==-1) 
        cout<<"Circular Queue is Empty"; 
     else 
     { 
        if(rear < front) 
        { 
          for(i=front;i<=MAX-1;i++) 
            cout<< a[i] <<" "; 
          for(i=0;i<=rear;i++) 
            cout<< a[i] <<" "; 
        } 
        else 
        { 
          for(i=front;i<=rear;i++) 
            cout<< a[i]<<" "; 
          cout<< endl; 
        } 
     } 
  } 
  void main() 
  { 
     cqueue c1; 
     int ch,val; 
     char op; 
     do 
     { 
       clrscr(); 
       cout<<"-----------Menu-------------"; 
       cout<<"1.Insertion 
       2.Deletion 
       3.Display 
       4.Exit"; 
       cout<<"Enter Your Choice <1..4> ?"; 
       cin>>ch; 
       switch(ch) 
       { 
          case 1 : cout<<"Enter Element to Insert ?"; 
            cin>>val; 
            c1.insert(val); 
            break; 
          case 2 : val=c1.deletion(); 
            cout<<"Deleted Element :"<< val<< endl; 
            break; 
          case 3 : c1.display(); 
            break; 
       } 
       cout<<"Do you want to continue < Y/N > ?"; 
       cin>>op; 
     }while(op=='Y' || op=='y'); 
       getch(); 
  }

  #include< iostream.h > 
  #include< conio.h > 
  #include< process.h > 
  // Creating a NODE Structure 
  struct node 
  { 
     int data; // data 
     struct node *next; // link to next node and previous node 
  }; 
  // Creating a class LIST 
  class list 
  { 
     struct node *start; 
     public: 
       void create(); // to create a list 
       void show(); // show 
       void merge(list,list); // Merge two list's 
  }; 
  // Main function 
  int main() 
  { 
     clrscr(); 
     list l1,l2,l3; 
     cout<<"Enter the First List in ascending order."; 
     l1.create(); // to create a first list 
     cout<<"Enter the Second List in ascending order."; 
     l2.create(); // to create a second list 
     cout<<"The first list is"; 
     l1.show(); 
     cout<<"The second list is"; 
     l2.show(); 
     l3.merge(l1,l2); 
     l3.show(); 
     getch(); 
     return (0); 
  } 
  // Functions 
  // Creating a new node 
  void list::create() 
  { 
     struct node *nxt_node,*pre_node; 
     int value,no,i; 
     start=nxt_node=pre_node=NULL; 
     cout<<"How many nodes : "; 
     cin>>no; 
     cout<<"Enter "<< no <<" Elements: "; 
     for(i=1;i<=no;i++) 
     { 
       cin>>value; 
       nxt_node=new node; 
       nxt_node->data=value; 
       nxt_node->next=NULL; 
       if(start==NULL) 
          start=nxt_node; 
       else 
          pre_node->next=nxt_node; 
         pre_node=nxt_node; 
     } 
     cout<<"The list is created!"; 
  } 
  // Displaying LIST 
  void list::show() 
  { 
     struct node *ptr=start; 
     cout<<"The List is "; 
     while(ptr!=NULL) 
     { 
       cout<< ptr->data<<" -> "; 
       ptr=ptr->next; 
     } 
     cout<<" "; 
  } 
  void list::merge(list l1,list l2) 
  { 
     struct node *nxt_node,*pre_node,*pptr,*qptr; 
     int dat; 
     pptr=l1.start; 
     qptr=l2.start; 
     start=nxt_node=pre_node=NULL; 
     while(pptr!=NULL && qptr!=NULL) 
     { 
       if(pptr->data<=qptr->data) 
       { 
          dat=pptr->data; 
          pptr=pptr->next; 
       } 
       else 
       { 
          dat=qptr->data; 
          qptr=qptr->next; 
       } 
       nxt_node=new node; 
       nxt_node->data=dat; 
       nxt_node->next=NULL; 
       if(start==NULL) 
          start=nxt_node; 
       else 
          pre_node->next=nxt_node; 
         pre_node=nxt_node; 
     } 
     if(pptr==NULL) 
     { 
       while(qptr!=NULL) 
       { 
          nxt_node=new node; 
          nxt_node->data=qptr->data; 
          nxt_node->next=NULL; 
          if(start==NULL) 
            start=nxt_node; 
          else 
            pre_node->next=nxt_node; 
          pre_node=nxt_node; 
          qptr=qptr->next; 
       } 
     } 
     else if(qptr==NULL) 
     { 
       while(pptr!=NULL) 
       { 
          nxt_node=new node; 
          nxt_node->data=pptr->data; 
          nxt_node->next=NULL; 
          if(start==NULL) 
            start=nxt_node; 
          else 
            pre_node->next=nxt_node; 
          pre_node=nxt_node; 
          pptr=pptr->next; 
       } 
     } 
     cout<<"The lists are merged."; 
     return; 
  }

   #include <iostream.h> 
    int a[50]; 
    void merge(int,int,int); 
    void merge_sort(int low,int high) 
    { 
      int mid; 
      if(low<high) 
      { 
        mid=(low+high)/2; 
        merge_sort(low,mid); 
        merge_sort(mid+1,high); 
        merge(low,mid,high); 
      } 
    } 
    void merge(int low,int mid,int high) 
    { 
      int h,i,j,b[50],k; 
      h=low; 
      i=low; 
      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(k=j;k<=high;k++) 
        { 
          b[i]=a[k]; 
          i++; 
        } 
      } 
      else 
      { 
        for(k=h;k<=mid;k++) 
        { 
          b[i]=a[k]; 
          i++; 
        } 
      } 
      for(k=low;k<=high;k++) 
      a[k]=b[k]; 
    } 
    void main() 
    { 
      int num,i; 
      cout<<"MERGE SORT PROGRAM"<<endl; 
      cout<<"Please Enter THE NUMBER OF ELEMENTS you want to sort [THEN 
      PRESS ENTER]:"<<endl; 
      cin>>num; 
      cout<<endl; 
      cout<<"Now, Please Enter the ( "<< num <<" ) numbers (ELEMENTS) [THEN 
      PRESS ENTER]:"<<endl; 
      for(i=1;i<=num;i++) 
      { 
        cin>>a[i] ; 
      } 
      merge_sort(1,num); 
      cout<<endl; 
      cout<<"So, the sorted list (using MERGE SORT) will be :"<<endl; 
      cout<<endl<<endl; 
      for(i=1;i<<=num;i++) 
      cout<<a[i]<<" "; 
      cout<<endl<<endl<<endl<<endl; 
    }

  #include < iostream.h > 
    const int MAX = 10 ; 
    class array 
    { 
      private : 
        int arr[MAX] ; 
        int count ; 
      public : 
        array( ) ; 
        void add ( int item ) ; 
        void sort( ) ; 
        void display( ) ; 
    } ; 
    array :: array( ) 
    { 
      count = 0 ; 
      for ( int i = 0 ; i < MAX ; i++ ) 
        arr[i] = 0 ; 
    } 
    void array :: add ( int item ) 
    { 
      if ( count < MAX ) 
      { 
        arr[count] = item ; 
        count++ ; 
      } 
      else 
        cout << "\nArray is full" << endl ; 
    } 
    void array :: sort( ) 
    { 
      int temp ; 
      for ( int i = 1 ; i <= count - 1 ; i++ ) 
      { 
        for ( int j = 0 ; j < i ; j++ ) 
        { 
          if ( arr[j] > arr[i] ) 
          { 
            temp = arr[j] ; 
            arr[j] = arr[i] ; 
            for ( int k = i ; k > j ; k-- ) 
              arr[k] = arr[k - 1] ; 
            arr[k + 1] = temp ; 
          } 
        } 
      } 
    } 
    void array :: display( ) 
    { 
      for ( int i = 0 ; i < count ; i++ ) 
        cout << arr[i] << "\t" ; 
      cout << endl ; 
    } 
    void main( ) 
    { 
      array a ; 
      a.add ( 25 ) ; 
      a.add ( 17 ) ; 
      a.add ( 31 ) ; 
      a.add ( 13 ) ; 
      a.add ( 2 ) ; 
      cout << "\nInsertion sort.\n" ; 
      cout << "\nArray before sorting:" << endl ; 
      a.display( ) ; 
      a.sort( ) ; 
      cout << "\nArray after insertion sorting:" << endl ; 
      a.display( ) ; 
    }

 #include< iostream.h > 
  #include< conio.h > 
  class cirdlink 
  { 
     struct node 
     { 
        int data; 
        node *rnext; 
        node *lnext; 
     }*new1,*head,*tail,*ptr,*temp; 
     public: 
     cirdlink() 
     { 
        head=tail=NULL; 
     } 
     void creation(); 
     void insertion(); 
     void deletion(); 
     void display(); 
   }; 
   void cirdlink :: creation() 
   { 
     if(head==NULL) 
     { 
        new1=new node[sizeof(node)]; 
        new1->rnext=NULL; 
        new1->lnext=NULL; 
        cout<<"enter student number :"; 
        cin>>new1->data; 
        head=new1; 
        tail=new1; 
        head->rnext=tail; 
        head->lnext=tail; 
        tail->rnext=head; 
        tail->lnext=head; 
      } 
      else 
        cout<<" creation done only once !"; 
   } 
   void cirdlink :: insertion() 
   { 
      int i,pos; 
      new1=new node[sizeof(node)]; 
      new1->rnext=NULL; 
      new1->lnext=NULL; 
      cout<<"enter student number :"; 
      cin>>new1->data; 
      cout<<"enter position you want to insert :"; 
      cin>>pos; 
      if(pos==1) 
      { 
        new1->rnext=head; 
        head=new1; 
        tail->lnext=head; 
        tail->rnext=head; 
        head->lnext=tail; 
      } 
      else 
      { 
        i=1; 
        temp=head; 
        while(i < pos-1 && temp->rnext!=tail) 
        { 
          i++; 
          temp=temp->rnext; 
        } 
        if(temp->rnext==tail) 
        { 
          new1->rnext=tail->rnext; 
          tail->rnext=new1; 
          new1->lnext=tail; 
          tail=new1; 
          head->lnext=tail; 
        } 
        else 
        { 
          new1->rnext=temp->rnext; 
          new1->lnext=temp; 
          temp->rnext=new1; 
          new1->rnext->lnext=new1; 
        } 
      } 
   } 
   void cirdlink :: deletion() 
   { 
      int pos,i; 
      cout<<"Enter Position you want to Delete ?"; 
      cin>>pos; 
      if(pos==1 && head!=tail) 
      { 
        ptr=head; 
        head=head->rnext; 
        head->lnext=tail; 
        tail->rnext=head; 
        delete ptr; 
      } 
      else 
      { 
        i=1; 
        temp=head; 
        while(i < pos-1 && temp->rnext!=tail) 
        { 
          i++; 
          temp=temp->rnext; 
        } 
        if(temp->rnext!=tail) 
        { 
          ptr=temp->rnext; 
          temp->rnext=ptr->rnext; 
          ptr->rnext->lnext=ptr->lnext; 
          delete ptr; 
        } 
        else 
        { 
          if(temp->rnext==tail && head!=tail) 
          { 
            ptr=tail; 
            tail=temp; 
            tail->rnext=head; 
            head->lnext=tail; 
            delete ptr; 
          } 
          else 
          { 
            head=NULL; 
            tail=NULL; 
            delete head; 
            delete tail; 
          } 
        } 
      } 
    } 
    void cirdlink::display() 
    { 
      int ch; 
      cout<<"1.forward 
      2.backward:"; 
      cout<<"Enter your choice<1/2>?"; 
      cin>>ch; 
      switch(ch) 
      { 
        case 1: if(head!=NULL) 
        { 
          temp=head; 
          while(temp!=tail) 
          { 
            cout<< temp->data<<" "; 
            temp=temp->rnext; 
          } 
          if(temp==tail) 
            cout<< temp->data; 
        } 
        break; 
        case 2 : if(tail!=NULL) 
        { 
          temp=tail; 
          while(temp!=head) 
          { 
            cout<< temp->data<<" "; 
            temp=temp->lnext; 
          } 
          if(temp==head) 
            cout<< temp->data; 
        } 
        break; 
      } 
    } 
    void main() 
    { 
      cirdlink c1; 
      int ch; 
      char op; 
      do 
      { 
        clrscr(); 
        cout<<"----------Menu------------"; 
        cout<<" 1.Creation 
        2.Insertion 
        3.Deletion 
        4.Display "; 
        cout<<"Enter Your choice <1..4> ?"; 
        cin>>ch; 
        switch(ch) 
        { 
          case 1 : c1.creation(); 
            break; 
          case 2 : c1.insertion(); 
            break; 
          case 3 : c1.deletion(); 
            break; 
          case 4 : c1.display(); 
            break; 
        } 
        cout<<"Do you want to continue < Y/N > ?"; 
        cin>>op; 
      }while(op=='y' || op=='Y'); 
      getch(); 
    }

  #include< iostream.h> 
  #include< conio.h> 
  #define SIZE 20 
  class stack 
  { 
    int a[SIZE]; 
    int tos; // Top of Stack 
    public: 
       stack(); 
       void push(int); 
       int pop(); 
       int isempty(); 
       int isfull(); 
  }; 
  stack::stack() 
  { 
    tos=0; //Initialize Top of Stack 
  } 
  int stack::isempty() 
  { 
    return (tos==0?1:0); 
  } 
  int stack::isfull() 
  { 
    return (tos==SIZE?1:0); 
  } 
  void stack::push(int i) 
  { 
    if(!isfull()) 
    { 
      cout<<"Pushing "<< i<< endl; 
      a[tos]=i; 
      tos++; 
    } 
    else 
    { 
      cerr<<"Stack overflow error ! 
      Possible Data Loss !"; 
    } 
  } 
  int stack::pop() 
  { 
    if(!isempty()) 
    { 
      cout<<"Popping "<< a[tos-1]<< endl; 
      return(a[--tos]); 
    } 
    else 
    { 
      cerr<<"Stack is empty! What to pop...!"; 
    } 
    return 0; 
  } 
  void reverse(stack s) 
  { 
    stack s2; 
    while(!s.isempty()) 
    { 
       s2.push(s.pop()); 
    } 
    cout<<"Reversed contents of the stack..."<< endl; 
    while(!s2.isempty()) 
    { 
       cout<< s2.pop()<< endl; 
    } 
  }//end of fn. 
  void main() 
  { 
    clrscr(); 
    stack s; 
    s.push(1); 
    s.push(2); 
    s.push(3); 
    reverse(s); 
    getch(); 
  }

  # include < iostream.h > 
  # include < conio.h > 
  # define SIZE 20 
  class queue 
  { 
     int a[SIZE]; 
     int front; 
     int rear; 
    public: 
       queue(); 
       ~queue(); 
       void insert(int i); 
       int remove(); 
       int isempty(); 
       int isfull(); 
  }; 
  queue::queue() 
  { 
    front=0; 
    rear=0; 
  } 
  queue::~queue() 
  { 
    delete []a; 
  } 
  void queue::insert(int i) 
  { 
    if(isfull()) 
    { 
       cout<<"*Queue is FULL !!!No insertion allowed further.*"; 
       return; 
    } 
    a[rear] = i; 
    rear++; 
  } 
  int queue::remove() 
  { 
    if(isempty()) 
    { 
       cout<<"*Queue Empty !!!Value returned will be garbage.*"; 
       return (-9999); 
    } 
    return(a[front++]); 
  } 
  int queue::isempty() 
  { 
    if(front == rear) 
       return 1; 
    else 
       return 0; 
  } 
  int queue::isfull() 
  { 
    if(rear == SIZE) 
       return 1; 
    else 
       return 0; 
  } 
  void main() 
  { 
    clrscr(); 
    queue q; 
    q.insert(1); 
    q.insert(2); 
    cout<<""<< q.remove(); 
    cout<<""<< q.remove(); 
    cout<<"" << q.remove(); 
    getch(); 
  }

  #include<iostream.h> 
    #include<conio.h> 
    #include<stdio.h> 
    #include<stdlib.h> 
    class path 
    { 
      int n; 
        int p[10][10]; 
        int a[10][10]; 
        int c[10][10]; 
      public: 
        void get(); 
        void pm(); 
        void ap(); 
        void disp(); 
    }; 
    void path::get() 
    { 
      int i,j,k; 
      clrscr(); 
      cout<<"Enter the no. of nodes in the graph :"; 
      cin>>n; 
      cout<<"Enter the adjacency matrix :"; 
      for(i=1;i<=n;i++) 
      { 
        for(j=1;j<=n;j++) 
        { 
          cin>>a[i][j]; 
          p[i][j]=0; 
        } 
      } 
      cout<<"Enter The cost matrix is :"; 
      for(i=1;i<=n;i++) 
      { 
        for(j=1;j<=n;j++) 
        { 
          cin>>c[i][j]; 
        } 
      } 
      for(i=1;i<=n;i++) 
      { 
        for(j=1;j<=n;j++) 
        { 
          p[i][j]=a[i][j]; 
        } 
      } 
    } 
    void path::disp() 
    { 
      // cout<<"The output matrix for the given graph is :"; 
      for(int i=1;i<=n;i++) 
      { 
        for(int j=1;j<=n;j++) 
        { 
          cout<<p[i][j]<< " "; 
        } 
        cout<<endl; 
      } 
    } 
    void path::pm() 
    { 
      int i,j,k; 
      for(k=1;k<=n;k++) 
      { 
        for(i=1;i<=n;i++) 
        { 
          for(j=1;j<=n;j++) 
          { 
            p[i][j]=p[i][j] || p[i][k] && p[k][j]; 
          } 
        } 
      } 
    } 
    void path::ap() 
    { 
      int i,j,k; 
      for(i=1;i<=n;i++) 
      { 
        for(j=1;j<=n;j++) 
        { 
          p[i][j]=c[i][j]; 
        } 
      } 
      for(k=1;k<=n;k++) 
      { 
        for(i=1;i<=n;i++) 
        { 
          for(j=1;j<=n;j++) 
          { 
            if(p[i][j]<p[i][k]+p[k][j]) 
            { 
              p[i][j]=p[i][j]; 
            } 
            else 
            { 
              p[i][j]=p[i][k]+p[k][j]; 
            } 
          } 
        } 
      } 
    } 
    void main() 
    { 
      path p; 
      p.get(); 
      p.pm(); 
      cout<<"path matrix is :"; 
      p.disp(); 
      getch(); 
      p.ap(); 
      cout<<"all pair shortest path matrix is :"; 
      p.disp(); 
      getch(); 
    }

 #include < iostream > 
  #include < cstdlib > 
  #include < string > 
  using namespace std; 
  class Dllist 
  { 
     private: 
       typedef struct Node 
       { 
         string name; 
         Node* next; 
         Node* prev; 
       }; 
       Node* head; 
       Node* last; 
     public: 
       Dllist() 
       { 
         head = NULL; 
         last = NULL; 
       } 
       bool empty() const { return head==NULL; } 
       friend ostream& operator<<(ostream& ,const Dllist& ); 
       void Insert(const string& ); 
       void Remove(const string& ); 
  }; 
  void Dllist::Insert(const string& s) 
  { 
     // Insertion into an Empty List. 
     if(empty()) 
     { 
       Node* temp = new Node; 
       head = temp; 
       last = temp; 
       temp->prev = NULL; 
       temp->next = NULL; 
       temp->name = s; 
     } 
     else 
     { 
       Node* curr; 
       curr = head; 
       while( s>curr->name && curr->next != last->next) 
          curr = curr->next; 
       if(curr == head) 
       { 
         Node* temp = new Node; 
         temp->name = s; 
         temp->prev = curr; 
         temp->next = NULL; 
         head->next = temp; 
         last = temp; 
         // cout<<" Inserted "<< s <<" After " << curr->name << endl; 
       } 
       else 
       { 
         if(curr == last && s>last->name) 
         { 
           last->next = new Node; 
           (last->next)->prev = last; 
           last = last->next; 
           last->next = NULL; 
           last->name = s; 
           // cout<<" Added "<< s <<" at the end "<< endl; 
         } 
         else 
         { 
           Node* temp = new Node; 
           temp->name = s; 
           temp->next = curr; 
           (curr->prev)->next = temp; 
           temp->prev = curr->prev; 
           curr->prev = temp; 
           // cout<<" Inserted "<< s <<" Before "<< curr->name << endl; 
         } 
       } 
     } 
  } 
  ostream& operator<<(ostream& ostr, const Dllist& dl ) 
  { 
     if(dl.empty()) ostr<<" The list is empty. "<< endl; 
     else 
     { 
       Dllist::Node* curr; 
       for(curr = dl.head; curr != dl.last->next; curr=curr->next) 
       ostr<< curr->name<<" "; 
       ostr<< endl; 
       ostr<< endl; 
       return ostr; 
     } 
  } 
  void Dllist::Remove(const string& s) 
  { 
     bool found = false; 
     if(empty()) 
     { 
       cout<<" This is an empty list! "<< endl; 
       return; 
     } 
     else 
     { 
       Node* curr; 
       for(curr = head; curr != last->next; curr = curr->next) 
       { 
         if(curr->name == s) 
         { 
           found = true; 
           break; 
         } 
       } 
       if(found == false) 
       { 
         cout<<" The list does not contain specified Node"<< endl; 
         return; 
       } 
       else 
       { 
         // Curr points to the node to be removed. 
         if (curr == head && found) 
         { 
           if(curr->next != NULL) 
           { 
             head = curr->next; 
             delete curr; 
             return; 
           } 
           else 
           { 
             delete curr; 
             head = NULL; 
             last = NULL; 
             return; 
           } 
         } 
         if (curr == last && found) 
         { 
           last = curr->prev; 
           delete curr; 
           return; 
         } 
         (curr->prev)->next = curr->next; 
         (curr->next)->prev = curr->prev; 
         delete curr; 
       } 
     } 
  } 
  int main() 
  { 
     Dllist d1; 
     int ch; 
     string temp; 
     while(1) 
     { 
       cout<< endl; 
       cout<<" Doubly Linked List Operations "<< endl; 
       cout<<" ------------------------------"<< endl; 
       cout<<" 1. Insertion "<< endl; 
       cout<<" 2. Deletion "<< endl; 
       cout<<" 3. Display "<< endl; 
       cout<<" 4. Exit "<< endl; 
       cout<<" Enter your choice : "; 
       cin>>ch; 
       switch(ch) 
       { 
         case 1: cout<<" Enter Name to be inserted : "; 
           cin>>temp; 
           d1.Insert(temp); 
           break; 
         case 2: cout<<" Enter Name to be deleted : "; 
           cin>>temp; 
           d1.Remove(temp); 
           break; 
         case 3: cout<<" The List contains : "; 
           cout<< d1; 
           break; 
         case 4: system("pause"); 
           return 0; 
           break; 
       } 
     } 
  }

  #include< iostream > 
  #define INFINITY 999 
  using namespace std; 
  class Dijkstra 
  { 
     private: 
       int adjMatrix[15][15]; 
       int predecessor[15],distance[15]; 
       bool mark[15]; //keep track of visited node 
       int source; 
       int numOfVertices; 
     public: 
       /* 
       * Function read() reads No of vertices, Adjacency Matrix and source 
       * Matrix from the user. The number of vertices must be greather than 
       * zero, all members of Adjacency Matrix must be postive as distances 
       * are always positive. The source vertex must also be positive from 0 
       * to noOfVertices - 1 
       */ 
       void read(); 
       
       /* 
       * Function initialize initializes all the data members at the begining of 
       * the execution. The distance between source to source is zero and all other 
       * distances between source and vertices are infinity. The mark is initialized 
       * to false and predecessor is initialized to -1 
       */ 
       void initialize(); 
       
       /* 
       * Function getClosestUnmarkedNode returns the node which is nearest from the 
       * Predecessor marked node. If the node is already marked as visited, then it search 
       * for another node. 
       */ 
        int getClosestUnmarkedNode(); 
       
       /* 
       * Function calculateDistance calculates the minimum distances from the source node to 
       * Other node. 
       */ 
        void calculateDistance(); 
       /* 
       * Function output prints the results 
       */ 
        void output(); 
       void printPath(int); 
  }; 
  void Dijkstra::read() 
  { 
     cout<<"Enter the number of vertices of the graph(should be > 0)\n"; 
     cin>>numOfVertices; 
     while(numOfVertices <= 0) 
     { 
        cout<<"Enter the number of vertices of the graph(should be > 0)\n"; 
        cin>>numOfVertices; 
     } 
     cout<<"Enter the adjacency matrix for the graph\n"; 
     cout<<"To enter infinity enter "<< INFINITY<< endl; 
     for(int i=0;i< numOfVertices;i++) 
     { 
        cout<<"Enter the (+ve)weights for the row "<< i << endl; 
     
       for(int j=0;j< numOfVertices;j++) 
       { 
          cin>>adjMatrix[i][j]; 
         while(adjMatrix[i][j]<0) 
         { 
            cout<<"Weights should be +ve. Enter the weight again\n"; 
            cin>>adjMatrix[i][j]; 
         } 
       } 
     } 
     cout<<"Enter the source vertex\n"; 
     cin>>source; 
     while((source<0) && (source>numOfVertices-1)) 
     { 
        cout<<"Source vertex should be between 0 and"<< numOfVertices-1<< endl; 
        cout<<"Enter the source vertex again\n"; 
        cin>>source; 
     } 
  } 
  voidpre Dijkstra::initialize() 
  { 
     for(int i=0;i< numOfVertices;i++) 
     { 
        mark[i] = false; 
       predecessor[i] = -1; 
       distance[i] = INFINITY; 
     } 
     distance[source]= 0; 
  } 
  int Dijkstra::getClosestUnmarkedNode() 
  { 
     int minDistance = INFINITY; 
     int closestUnmarkedNode; 
     for(int i=0;i< numOfVertices;i++) 
     { 
        if((!mark[i]) && ( minDistance >= distance[i])) 
       { 
          minDistance = distance[i]; 
         closestUnmarkedNode = i; 
       } 
     } 
     return closestUnmarkedNode; 
  } 
  void Dijkstra::calculateDistance() 
  { 
     initialize(); 
     int minDistance = INFINITY; 
     int closestUnmarkedNode; 
     int count = 0; 
     while(count < numOfVertices) 
     { 
        closestUnmarkedNode = getClosestUnmarkedNode(); 
       mark[closestUnmarkedNode] = true; 
       for(int i=0;i< numOfVertices;i++) 
       { 
          if((!mark[i]) && (adjMatrix[closestUnmarkedNode][i]>0) ) 
         { 
           if(distance[i] > distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]) 
           { 
             distance[i] = distance[closestUnmarkedNode]+adjMatrix[closestUnmarkedNode][i]; 
             predecessor[i] = closestUnmarkedNode; 
           } 
         } 
       } 
       count++; 
     } 
  } 
  void Dijkstra::printPath(int node) 
  { 
     if(node == source) 
       cout<<(char)(node + 97)<<".."; 
     else if(predecessor[node] == -1) 
       cout<<"No path from “<< source<<”to "<<(char)(node + 97)<< endl; 
     else 
     { 
        printPath(predecessor[node]); 
       cout<<(char) (node + 97)<<".."; 
     } 
  } 
  void Dijkstra::output() 
  { 
     for(int i=0;i< numOfVertices;i++) 
     { 
        if(i == source) 
         cout<<(char)(source + 97)<<".."<< source; 
       else 
         printPath(i); 
       cout<<"->"<< distance[i]<< endl; 
     } 
  } 
  int main() 
  { 
     Dijkstra G; 
     G.read(); 
     G.calculateDistance(); 
     G.output(); 
     return 0; 
  }

  #include<iostream> 
  #include<stdlib.h> 
  using namespace std;
  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<<" 
      1: DFS 
      2: BSF 
      3: Exit 
      Enter 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 dat,flag=0; 
     start=NULL; 
     cout<<" 
    Enter the nodes in the graph(0 to end): "; 
     while(1) 
     { 
       cin>>dat; 
       if(dat==0) 
          break; 
       p=new node; 
       p->data=dat; 
       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<<"Enter the links to "<< p->data<<" (0 to end) : "; 
       flag=0; 
       while(1) 
       { 
          cin>>dat; 
          if(dat==0) 
            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==dat) 
              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; 
  }