C++ Program to Implement Hash Tables Chaining with Binary Trees

«
»
This C++ Program demonstrates operations on Hash Tables Chaining with Binary Trees.

Here is source code of the C++ Program to demonstrate Hash Tables Chaining with Binary Trees. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Hash Tables Chaining with Binary Trees
  3.  */
  4. #include <iostream>
  5. #include <string>
  6. #include <vector>
  7. #include <cstdlib>
  8. using namespace std;
  9.  
  10. /*
  11.  * Node Class Declaration
  12.  */
  13. template <class T>
  14. class BSTNode
  15. {
  16.     private:
  17.         T value;
  18.         BSTNode *left, *right;
  19.     public:
  20.         BSTNode(T value)
  21.         {
  22.             this->value = value;
  23.             left = NULL;
  24.             right = NULL;
  25.         }
  26.         /*
  27.          * Adding element to a node
  28.          */
  29.         void add(T& value)
  30.         {
  31.             if (value < this->value)
  32.             {
  33.                 if (left)
  34.                     left->add(value);
  35.                 else
  36.                     left = new BSTNode(value);
  37.             }
  38.             else if (this->value < value)
  39.             {
  40.                 if (right)
  41.                     right->add(value);
  42.                 else
  43.                     right = new BSTNode(value);
  44.             }
  45.         }
  46.         /*
  47.          * Check if node contains element
  48.          */
  49.         bool contains(T& value)
  50.         {
  51.             if (value < this->value)
  52.     	    {
  53.                 if (left)
  54.             	    return left->contains(value);
  55.         	else
  56.            	    return false;
  57.     	    }
  58.     	    else if (this->value < value)
  59.     	    {
  60.                 if (right)
  61.             	    return right->contains(value);
  62.         	else
  63.             	    return false;
  64.     	    }
  65.     	    else
  66.     	    {
  67.                 return true;
  68.     	    }
  69.         }
  70.         friend class BSTHashtable;
  71. };
  72.  
  73. /*
  74.  * Table Class Declaration
  75.  */
  76. class BSTHashtable
  77. {
  78.     private:
  79.         int size;
  80.         vector<BSTNode<string>*>* bucket;
  81.         int hash(string& s)
  82.         {
  83.             unsigned int hashVal = 0;
  84.             for (unsigned int i = 0; i < s.length(); i++)
  85.                 hashVal ^= (hashVal << 5) + (hashVal >> 2) + s[i];
  86.             return hashVal % size;
  87.         }
  88.     public:
  89.         BSTHashtable(int vectorSize)
  90.         {
  91.             size = vectorSize;
  92.             bucket = new vector<BSTNode<string>*>(size);
  93.         }
  94.         /*
  95.          * Adding string in the table
  96.          */
  97.         void add(string& s)
  98.         {
  99.             int index = hash(s);
  100.             if (bucket->at(index) == NULL)
  101.                 bucket->at(index) = new BSTNode<string>(s);
  102.             else
  103.                 bucket->at(index)->add(s);
  104.         }
  105.         /*
  106.          * Check if table contains string
  107.          */
  108.         bool contains(string& s)
  109.         {
  110.             int index = hash(s);
  111.             if (bucket->at(index) == NULL)
  112.                 return false;
  113. 	    cout<<"String \""<<s<<"\" found at index: "<<index<<endl;
  114.             return bucket->at(index)->contains(s);
  115.         }
  116.         /*
  117.          * Display Table
  118.          */
  119.         void display()
  120.         {
  121.             for (unsigned int i = 0; i < bucket->size(); i++)
  122.             {
  123.                 cout <<"[" << i << "] ";
  124. 	        if (bucket->at(i) != NULL)
  125.                 {
  126.                     BSTNode<string> *node = bucket->at(i);
  127.                     display_bst(node);
  128.                 }
  129.                 cout << endl;
  130.             }
  131.         }
  132.         /*
  133.          * Display BST
  134.          */
  135.         void display_bst(BSTNode<string> *node)
  136.         {
  137. 	    if (node!=NULL)
  138.             {
  139.             	display_bst(node->left);
  140.             	cout << node->value << " ";
  141.             	display_bst(node->right);
  142.             }
  143.         }
  144. };
  145.  
  146. /*
  147.  * Main Contains Menu
  148.  */
  149. int main()
  150. {
  151.     BSTHashtable table(10);
  152.     string str;
  153.     int choice;
  154.     while (1)
  155.     {
  156.         cout<<"\n----------------------"<<endl;
  157. 	cout<<"Operations on BST Hash Table"<<endl;
  158. 	cout<<"\n----------------------"<<endl;
  159. 	cout<<"1.Insert element into the table"<<endl;
  160. 	cout<<"2.Find element in the table"<<endl;
  161. 	cout<<"3.Display Table Chained with Binary Tree"<<endl;
  162. 	cout<<"4.Exit"<<endl;
  163.         cout<<"Enter your choice: ";
  164.         cin>>choice;
  165.         switch(choice)
  166.         {
  167.         case 1:
  168.             cout<<"Enter String to be inserted: ";
  169.             cin>>str;
  170.             table.add(str);
  171.             break;
  172.         case 2:
  173.             cout<<"Enter String to search: ";
  174.             cin>>str;
  175.             if (table.contains(str) == 0)
  176.             {
  177. 	        cout<<"String \""<<str<<"\" not found in the table"<<endl;
  178. 		continue;
  179. 	    }
  180.             break;
  181.         case 3:
  182.             cout<<"Displaying Table Chained with Binary Tree: "<<endl;
  183.             table.display();
  184.             break;
  185.         case 4:
  186.             exit(1);
  187.         default:
  188.             cout<<"\nEnter correct option\n";
  189.         }
  190.     }
  191.     return 0;
  192. }

advertisement
$ g++ xor_list.cpp
$ a.out
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 100
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 200
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 300
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
300 200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 400
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
400 300 200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 1
Enter value to be inserted: 500
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 2
Elements of XOR Linked List: 
500 400 300 200 100 
 
-------------
Operations on XOR Linked List
 
-------------
1.Insert Element at First
2.Display List
3.Quit
Enter your Choice: 3
 
 
------------------
(program exited with code: 1)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He is Linux Kernel Developer & SAN Architect and is passionate about competency developments in these areas. He lives in Bangalore and delivers focused training sessions to IT professionals in Linux Kernel, Linux Debugging, Linux Device Drivers, Linux Networking, Linux Storage, Advanced C Programming, SAN Storage Technologies, SCSI Internals & Storage Protocols such as iSCSI & Fiber Channel. Stay connected with him @ LinkedIn