Advertisement
Guest User

C++ Hash Table Code

a guest
May 30th, 2016
63
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.83 KB | None | 0 0
  1. //---------
  2. //MAIN.CPP
  3. //---------
  4.  
  5. #include <iostream>
  6. #include "hashTable.h"
  7. #include "stateData.h"
  8. using namespace std;
  9.  
  10. void main()
  11. {
  12.     hashTable<stateData> myTable;
  13.    
  14.     stateData CA("California", "Sacramento", 1850, 31);
  15.     stateData OR("Oregon", "Salem", 1859, 33);
  16.     stateData WA("Washington", "Olympia", 1889, 42);
  17.  
  18.     myTable.insert(WA);
  19.     myTable.insert(OR);
  20.     myTable.insert(CA);
  21.     myTable.insert(OR);
  22.  
  23.     //cout << (WA == OR) //Should return false, and does
  24.     //cout << (WA == WA) //Should return true, and does
  25.  
  26.     myTable.display();
  27.  
  28.     system("pause");
  29. }
  30.  
  31. //------------
  32. //STATEDATA.H
  33. //------------
  34.  
  35. #include <iostream>
  36. using namespace std;
  37.  
  38. #ifndef STATEDATA
  39. #define STATEDATA
  40.  
  41. class stateData
  42. {
  43. private:
  44.     char name[15];
  45.     char capital[100];
  46.     int admissionYear; //Year admitted to the Union
  47.     int admissionOrder; //What order was it admitted? (i.e. Delaware is 1, Hawaii is 50)
  48.  
  49. public:
  50.     stateData()
  51.     {
  52.         name[0] = '\0';
  53.         capital[0] = '\0';
  54.         admissionYear = -1;
  55.         admissionOrder = -1;
  56.     }
  57.  
  58.     stateData(stateData &other)
  59.     {
  60.         memcpy(this->name, other.name, 15);
  61.         memcpy(this->capital, other.capital, 100);
  62.         this->admissionYear = other.admissionYear;
  63.         this->admissionOrder = other.admissionOrder;
  64.     }
  65.  
  66.     stateData(char* name, char* capital, int year, int order)
  67.     {
  68.         memcpy(this->name, name, 15);
  69.         memcpy(this->capital, capital, 100);
  70.         admissionYear = year;
  71.         admissionOrder = order;
  72.     }
  73.  
  74.     char* getName() { return name; }
  75.     char* getCapital() { return capital; }
  76.     int getYear() { return admissionYear; }
  77.     int getOrder() { return admissionOrder; }
  78.  
  79.     void setName(char* name) { memcpy(this->name, name, 100); }
  80.     void setCapital(char* capital) { memcpy(this->name, name, 100); }
  81.     void setYear(int year) { admissionYear = year; }
  82.     void setOrder(int order) { admissionOrder = order; }
  83.  
  84.     bool operator<(stateData &other) { return this->name < other.name; }
  85.     bool operator<=(stateData &other) { return this->name <= other.name; }
  86.     bool operator>(stateData &other) { return this->name > other.name; }
  87.     bool operator>=(stateData &other) { return this->name >= other.name; }
  88.     bool operator==(stateData &other) { return this->name == other.name; }
  89.     bool operator!=(stateData &other) { return this->name != other.name; }
  90.  
  91.     friend ostream& operator<<(ostream &out, stateData &pState)
  92.     {
  93.         out << pState.name;
  94.  
  95.         /*
  96.         out << pState.name << " was admitted to the United States in " << pState.admissionYear << " as the " << pState.admissionOrder;
  97.  
  98.         switch (pState.admissionOrder)
  99.         {
  100.         case 1:
  101.         case 21:
  102.         case 31:
  103.         case 41:
  104.             out << "st";
  105.             break;
  106.         case 2:
  107.         case 22:
  108.         case 32:
  109.         case 42:
  110.             out << "nd";
  111.             break;
  112.         case 3:
  113.         case 23:
  114.         case 33:
  115.         case 43:
  116.             out << "rd";
  117.             break;
  118.         default:
  119.             out << "th";
  120.         }
  121.  
  122.         out << " state. It's capital is " << pState.capital << "." << endl;
  123.         */
  124.         return out;
  125.     }
  126. };
  127.  
  128. #endif
  129.  
  130. //------------
  131. //HASHTABLE.H
  132. //------------
  133.  
  134. #include <iostream>
  135. #include "stateData.h"
  136. using namespace std;
  137.  
  138. #ifndef HASH_TABLE
  139. #define HASH_TABLE
  140.  
  141. template<class T>
  142. class hashTable
  143. {
  144. private:
  145.     T** list;
  146.     int length;
  147.     const int TABLE_SIZE = 101;
  148.  
  149. public:
  150.     hashTable()
  151.     {
  152.         //Creates a new array of pointers of type T
  153.         length = 0;
  154.         list = new T*[TABLE_SIZE];
  155.         for (int i = 0; i < TABLE_SIZE; i++)
  156.             list[i] = NULL;
  157.     }
  158.  
  159.     ~hashTable()
  160.     {
  161.         //Deletes the memory allocated to the hash table
  162.         for (int i = 0; i < TABLE_SIZE; i++)
  163.         {
  164.             if (list[i] != NULL)
  165.                 delete list[i];
  166.         }
  167.  
  168.         delete[] list;
  169.     }
  170.  
  171.     void display()
  172.     {
  173.         if (!isEmpty())
  174.         {
  175.             for (int i = 0; i < TABLE_SIZE; i++)
  176.             {
  177.                 if (list[i] != NULL)
  178.                     cout << "ID: " << i << "; Value: " << *list[i] << endl;
  179.             }
  180.         }
  181.         else
  182.         {
  183.             cout << "Hash table is currently empty" << endl;
  184.         }
  185.     }
  186.  
  187.     int hashFunc(stateData state)
  188.     {
  189.         string name = string(state.getName());
  190.  
  191.         int i = 0, sum = 0;
  192.         int len = name.length();
  193.  
  194.         for (int j = 0; j < (15 - len); j++)
  195.         {
  196.             name = name + ' ';
  197.         }
  198.  
  199.         for (int j = 0; j < 5; j++)
  200.         {
  201.             sum += (static_cast<int>(name[i]) * 128 * 128 + static_cast<int>(name[i + 1]) * 128 + static_cast<int>(name[i + 2]));
  202.             i += 3;
  203.         }
  204.  
  205.         return sum % TABLE_SIZE;
  206.     }
  207.  
  208.     void insert(T &what)
  209.     {
  210.         int where = hashFunc(what);
  211.         bool added = false;
  212.  
  213.         if (!isFull())
  214.         {
  215.             for (int i = 0; i <= sqrt(TABLE_SIZE); i++)
  216.             {
  217.                 where = (where + i*i) % TABLE_SIZE;
  218.  
  219.                 if (*list[where] == what)
  220.                 {
  221.                     cout << "Duplicate entries are not allowed in the hash table.";
  222.                     break;
  223.                 }
  224.  
  225.                 if (list[where] == NULL)
  226.                 {
  227.                     list[where] = new T(what);
  228.                     length++;
  229.                     added = true;
  230.                     break;
  231.                 }
  232.             }
  233.         }
  234.  
  235.         if (!added)
  236.             cerr << "Data could not be added to hash table." << endl;
  237.     }
  238.  
  239.     bool isEmpty()
  240.     {
  241.         return length == 0;
  242.     }
  243.  
  244.     bool isFull()
  245.     {
  246.         return length == (TABLE_SIZE / 2);
  247.     }
  248. };
  249.  
  250. #endif
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement