fork download
copy 
  1. #include <iostream>
  2. #include <cstring>
  3.  
  4. using namespace std;
  5.  
  6. struct elt {
  7.     int key; // to hold a unique key for each element
  8.     int data;  // the data for each element
  9.     elt * next; // next element in the bucket list
  10. };
  11.  
  12. typedef elt * Eltp; // elt pointer
  13.  
  14.  
  15. class HashTableOne {
  16.     int size= 0;
  17.     Eltp * table; // array of buckets
  18.  
  19.     int hash(int k){ // hash function, k= key value
  20.         int i;
  21.         for (i= 0; k; i += k++);
  22.         return i % size;
  23.     }
  24.  
  25. public:
  26.     HashTableOne(int n); // constructor, n= size of hash table array    
  27.     void add(int k, int d); // function adds element to hash table, k= key value, d= data to be added (an int)
  28.     int find(int k); // function that returns data (an int) for "k" key value input (returns -1 if no key exists)
  29.     void print(); // function that prints the contents of the hash table
  30. };
  31.  
  32.  
  33.  
  34. // HashTable3 class declaration:
  35. class HashTable3 {
  36.     HashTableOne_p * table; // array of pointers to buckets
  37. public:
  38.     HashTable3(int n1, int n2); // constructor, n1= size of main hash table, n2= size for bucket hash tables
  39.     void add(int k, int d); // adds element, k= key, d= data (an int)
  40.     int find(int key); // returns d (data) associated with key (returns -1 if key does not exist)
  41.     void print(); // prints contents of hash table, printing bucket hash tables
  42. };
  43.  
  44.  
  45. // HashTableOne constructor:
  46. HashTableOne::HashTableOne(int n) {
  47.         size = n;
  48.         table = new Eltp [size];
  49.         for(int i=0; i < size; i++){
  50.             table[i] = NULL;
  51.         }
  52.     }
  53.  
  54.  
  55. // HashTableOne add function:
  56. void HashTableOne::add(int k, int d) {
  57.         int index = hash(k);
  58.         if(table[index] == NULL){
  59.             table[index] = new elt;
  60.             table[index]->data = d;
  61.             table[index]->key = k;
  62.             table[index]->next = NULL;
  63.         } else{
  64.             // search for the key, if found update the data
  65.             elt * p = table[index];
  66.             while(p != NULL) {
  67.                 if(p->key == k){ // found one
  68.                     p->data = d;
  69.                     return;
  70.                 }
  71.                 p = p->next;
  72.             }// end while
  73.  
  74.             // did not find it in the bucket
  75.             p = table[index];
  76.             table[index] = new elt;
  77.             table[index]->data = d;
  78.             table[index]->key = k;
  79.             table[index]->next = p;
  80.         }
  81.     }
  82.  
  83. // HashTableOne find function:
  84. int HashTableOne::find(int k) {
  85.         int index = hash(k);
  86.         elt * p = table[index];
  87.         while(p != NULL) {
  88.             if(p->key == k){ // found one
  89.                 return p;
  90.             }
  91.             p = p->next;
  92.         }// end while
  93.  
  94.         // did not find it 
  95.         return -1;
  96.     }
  97.  
  98.  
  99.  
  100. // HashTable3 constructor:
  101. HashTable3::HashTable3(int n1, int n2) {
  102.     typedef HashTableOne * HashTableOne_p; // a pointer to HashTableOne class
  103.  
  104.     table= new HashTableOne_p[n1];
  105.     for (int i= 0; i < n1; i++){
  106.         table[i]= new HashTableOne(n2);
  107.     }
  108.  
  109. }
  110.  
  111. // HashTable3 add function:
  112. void HashTable3::add(int k, int d) {
  113.         int index = hash(k);
  114.         if(table[index] == NULL){
  115.             table[index] = new elt;
  116.             table[index]->data = d;
  117.             table[index]->key = k;
  118.             table[index]->next = NULL;
  119.         } else{
  120.             // search for the key, if found update the data
  121.             elt * p = table[index];
  122.             while(p != NULL) {
  123.                 if(p->key == k){ // found one
  124.                     p->data = d;
  125.                     return;
  126.                 }
  127.                 p = p->next;
  128.             }// end while
  129.  
  130.             // did not find it in the bucket
  131.             p = table[index];
  132.             table[index] = new elt;
  133.             table[index]->data = d;
  134.             table[index]->key = k;
  135.             table[index]->next = p;
  136.         }
  137.     }
  138.  
  139. // HashTable3 find function:
  140. int HashTable3::find(int k) {
  141.         int index = hash(k);
  142.         elt * p = table[index];
  143.         while(p != NULL) {
  144.             if(p->key == k){ // found one
  145.                 return p;
  146.             }
  147.             p = p->next;
  148.         }// end while
  149.  
  150.         // did not find it 
  151.         return -1;
  152.     }
  153.  
  154.  
  155.  
  156. int main() {
  157.  
  158.     // test cases go here
  159.  
  160.     HashTable3 H1(3, 2); // New hash table with 3 elements in main hash table and 2 bucket hash tables, populate with add() method randomly
  161.                          // Print the contents of the table after each operation using print()
  162.  
  163.     H1.find("key"); // finds an element with "key" value and returns data value (or -1 if key does not exist)
  164.  
  165.  
  166.     return 0;
  167. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
prog.cpp:36:5: error: ‘HashTableOne_p’ does not name a type
     HashTableOne_p * table; // array of pointers to buckets
     ^~~~~~~~~~~~~~
prog.cpp: In member function ‘int HashTableOne::find(int)’:
prog.cpp:89:24: error: invalid conversion from ‘elt*’ to ‘int’ [-fpermissive]
                 return p;
                        ^
prog.cpp: In constructor ‘HashTable3::HashTable3(int, int)’:
prog.cpp:104:5: error: ‘table’ was not declared in this scope
     table= new HashTableOne_p[n1];
     ^~~~~
prog.cpp: In member function ‘void HashTable3::add(int, int)’:
prog.cpp:113:25: error: missing template arguments before ‘(’ token
         int index = hash(k);
                         ^
prog.cpp:114:12: error: ‘table’ was not declared in this scope
         if(table[index] == NULL){
            ^~~~~
prog.cpp: In member function ‘int HashTable3::find(int)’:
prog.cpp:141:25: error: missing template arguments before ‘(’ token
         int index = hash(k);
                         ^
prog.cpp:142:19: error: ‘table’ was not declared in this scope
         elt * p = table[index];
                   ^~~~~
prog.cpp:145:24: error: invalid conversion from ‘elt*’ to ‘int’ [-fpermissive]
                 return p;
                        ^
prog.cpp: In function ‘int main()’:
prog.cpp:163:18: error: invalid conversion from ‘const char*’ to ‘int’ [-fpermissive]
     H1.find("key"); // finds an element with "key" value and returns data value (or -1 if key does not exist)
                  ^
prog.cpp:140:5: note:   initializing argument 1 of ‘int HashTable3::find(int)’
 int HashTable3::find(int k) {
     ^~~~~~~~~~
stdout
copy 
Standard output is empty
https://ideone.com/TDoa7D
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!