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); 
      } 
   }