C++ Program to Implement Hash Tables Chaining with Doubly Linked Lists

«
»
This C++ Program demonstrates operations on Hash Tables Chaining with Doubly Linked Lists.

Here is source code of the C++ Program to demonstrate Hash Tables Chaining with Doubly Linked Lists. 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 
  3.  * Doubly Linked Lists
  4.  */
  5. #include <iostream>
  6. #include <string>
  7. #include <vector>
  8. #include <cstdlib>
  9. const int TABLE_SIZE = 25;
  10. using namespace std;
  11. /*
  12.  * Node Declaration
  13.  */
  14. struct HashNode
  15. {
  16.     int data, key;
  17.     HashNode *next;
  18.     HashNode *prev;
  19. };
  20. /*
  21.  * Class Declaration
  22.  */
  23. class HashMap
  24. {
  25.     public:
  26.         HashNode **htable, **top;
  27.         HashMap()
  28.         {
  29.             htable = new HashNode*[TABLE_SIZE];
  30.             top = new HashNode*[TABLE_SIZE];
  31.             for (int i = 0; i < TABLE_SIZE; i++)
  32.             {
  33.                 htable[i] = NULL;
  34.                 top[i] = NULL;
  35.             }
  36.         }
  37.         ~HashMap()
  38.         {
  39.             delete [] htable;
  40.         }
  41.  
  42.         /* 
  43.          * Hash Function 
  44.          */
  45.         int HashFunc(int key)
  46.         {
  47.             return key % TABLE_SIZE;
  48.         }
  49.  
  50.         /* 
  51.          * Insert Element at a key 
  52.          */
  53.         void insert(int key, int value)
  54.         {
  55.             int hash_val = HashFunc(key);
  56.             HashNode *entry = htable[hash_val];
  57.             if (entry == NULL)
  58.             {
  59.                 entry = new HashNode;
  60.                 entry->data = value;
  61.                 entry->key = key;
  62.                 entry->next = NULL;
  63.                 entry->prev = NULL;
  64.                 htable[hash_val] = entry;
  65.                 top[hash_val] = entry;
  66.             }
  67.             else
  68.             {
  69.                 while (entry != NULL)
  70.                     entry = entry->next;
  71.                 entry = new HashNode;
  72.                 entry->data = value;
  73.                 entry->key = key;
  74.                 entry->next = NULL;
  75.                 entry->prev = top[hash_val];
  76.                 top[hash_val]->next = entry;
  77.                 top[hash_val] = entry;
  78.             }
  79.         }
  80.  
  81.         /*
  82.          * Remove Element at a key
  83.          */
  84.         void remove(int key)
  85.         {
  86.             int hash_val = HashFunc(key);
  87.             HashNode *entry = htable[hash_val];
  88.             if (entry->key != key || entry == NULL)
  89.             {
  90.                 cout<<"No Element found at key: "<<key<<endl;
  91.                 return;
  92.             }
  93.             while (entry != NULL)
  94.             {
  95.                 if (entry->next == NULL)
  96.                 {
  97.                     if (entry->prev == NULL)
  98.                     {
  99.                         htable[hash_val] = NULL;
  100.                         top[hash_val] = NULL;
  101.                         delete entry;
  102.                         break;
  103.                     }
  104.                     else
  105.                     {
  106.                         top[hash_val] = entry->prev;
  107.                         top[hash_val]->next = NULL;
  108.                         delete entry;
  109.                         entry = top[hash_val];
  110.                     }
  111.                 }
  112.                 entry = entry->next;
  113.             }
  114.         }
  115.         /*
  116.          * Search Element at a key
  117.          */
  118.         void get(int key)
  119.         {
  120.             int hash_val = HashFunc(key);
  121.             bool flag = false;
  122.             HashNode* entry = htable[hash_val];
  123.             if (entry != NULL)
  124.             {
  125.                 while (entry != NULL)
  126.                 {
  127.                     if (entry->key == key)
  128.                     {
  129.                         flag = true;
  130.                     }
  131.                     if (flag)
  132.                     {
  133.                         cout<<"Element found at key "<<key<<": ";
  134.                         cout<<entry->data<<endl;
  135.                     }
  136.                     entry = entry->next;
  137.                 }
  138.             }
  139.             if (!flag)
  140.                 cout<<"No Element found at key "<<key<<endl;
  141.         }
  142. };
  143.  
  144. /*
  145.  * Main Contains Menu
  146. */
  147. int main()
  148. {
  149.     HashMap hash;
  150.     int key, value;
  151.     int choice;
  152.     while (1)
  153.     {
  154.         cout<<"\n----------------------"<<endl;
  155.         cout<<"Operations on Hash Table"<<endl;
  156.         cout<<"\n----------------------"<<endl;
  157.         cout<<"1.Insert element into the table"<<endl;
  158.         cout<<"2.Search element from the key"<<endl;
  159.         cout<<"3.Delete element at a key"<<endl;
  160.         cout<<"4.Exit"<<endl;
  161.         cout<<"Enter your choice: ";
  162.         cin>>choice;
  163.         switch(choice)
  164.         {
  165.         case 1:
  166.             cout<<"Enter element to be inserted: ";
  167.             cin>>value;
  168.             cout<<"Enter key at which element to be inserted: ";
  169.             cin>>key;
  170.             hash.insert(key, value);
  171.             break;
  172.         case 2:
  173.             cout<<"Enter key of the element to be searched: ";
  174.             cin>>key;
  175.             hash.get(key);
  176.             break;
  177.         case 3:
  178.             cout<<"Enter key of the element to be deleted: ";
  179.             cin>>key;
  180.             hash.remove(key);
  181.             break;
  182.         case 4:
  183.             exit(1);
  184.         default:
  185.            cout<<"\nEnter correct option\n";
  186.         }
  187.     }
  188.     return 0;
  189. }

advertisement
$ g++ hash_doubly.cpp
$ a.out
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 12
Enter key at which element to be inserted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 24
Enter key at which element to be inserted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 36
Enter key at which element to be inserted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 48
Enter key at which element to be inserted: 2
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 60
Enter key at which element to be inserted: 2
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 72
Enter key at which element to be inserted: 2
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 3
No Element found at key 3
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 2
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 2
Element found at key 2: 48
Element found at key 2: 60
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 1
Element found at key 1: 12
Element found at key 1: 24
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 1
Element found at key 1: 12
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 1
Enter element to be inserted: 100
Enter key at which element to be inserted: 1
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 2
Enter key of the element to be searched: 1
Element found at key 1: 12
Element found at key 1: 100
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 3
Enter key of the element to be deleted: 4
No Element found at key: 4
 
----------------------
Operations on Hash Table
 
----------------------
1.Insert element into the table
2.Search element from the key
3.Delete element at a key
4.Exit
Enter your choice: 4
 
 
------------------
(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
advertisement
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