SHARE
TWEET

Untitled

a guest Jan 18th, 2019 55 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /*Implementare una hash map con concatenamento*/
  2. #include<iostream>
  3. #include<string>
  4. #include<vector>
  5. #include<math.h>
  6. using namespace std;
  7.  
  8. class Nodo
  9. {
  10. private:
  11.     int ID;
  12.     string data;
  13.     Nodo *p_prev, *p_next;
  14. public:
  15.     Nodo(string x, int y) { ID = y; data = x; p_prev = nullptr; p_next = nullptr; }
  16.     ~Nodo(){}
  17.  
  18.     void setPrev(Nodo *x) { p_prev = x; }
  19.     void setNext(Nodo *x) { p_next = x; }
  20.  
  21.     int getID() { return ID; }
  22.     string getString() { return data; }
  23.     Nodo* getPrev() { return p_prev; }
  24.     Nodo* getNext() { return p_next; }
  25. };
  26.  
  27. class ListaBid
  28. {
  29. private:
  30.     Nodo *testa, *coda;
  31. public:
  32.     ListaBid() { testa = nullptr; coda = nullptr; }
  33.     ~ListaBid(){}
  34.  
  35.     bool Empity() { if (testa != nullptr)return false; else return true; }
  36.  
  37.     Nodo* Search(int val);
  38.     void Delete(int val);
  39.     void Insert(Nodo *x);
  40.  
  41.     void visualizza_ListaBid();
  42. };
  43. Nodo* ListaBid::Search(int val)
  44. {
  45.     Nodo *tmp = testa;
  46.     while (tmp != nullptr)
  47.     {
  48.         if (tmp->getID() == val)
  49.             return tmp;
  50.  
  51.         tmp = tmp->getNext();
  52.     }
  53.     return nullptr;
  54. }
  55. void ListaBid::Delete(int val)
  56. {
  57.     Nodo *tmp = Search(val);
  58.     if (tmp != nullptr)
  59.     {
  60.         if (tmp->getNext() != nullptr)
  61.             tmp->getNext()->setPrev(tmp->getPrev());
  62.         else
  63.             coda = tmp->getPrev();
  64.  
  65.         if (tmp->getPrev() != nullptr)
  66.             tmp->getPrev()->setNext(tmp->getNext());
  67.         else
  68.             testa = tmp->getNext();
  69.  
  70.         delete tmp;
  71.     }
  72. }
  73. void ListaBid::Insert(Nodo *x)
  74. {
  75.     if (Search(x->getID()) == nullptr)
  76.     {
  77.         x->setNext(testa);
  78.         x->setPrev(nullptr);
  79.         testa = x;
  80.         if (coda == nullptr)
  81.             coda = x;
  82.     }
  83. }
  84. void ListaBid::visualizza_ListaBid()
  85. {
  86.     Nodo *tmp = testa;
  87.     if (tmp != nullptr)
  88.     {
  89.         while (tmp != nullptr)
  90.         {
  91.             cout << tmp->getString() << ' ';
  92.             tmp = tmp->getNext();
  93.         }
  94.     }
  95. }
  96.  
  97. class HashTable
  98. {
  99. private:
  100.     vector<ListaBid*>Table;
  101.     int HashFunction(int val);///Metodo della moltiplicazione
  102.     int getVal(string s);///Calcola la chiave di una stringa con sistema posizionale pesato in base 27
  103. public:
  104.     HashTable(int size) { Table.resize(size, nullptr); }
  105.     ~HashTable(){}
  106.  
  107.     bool Search(string s);
  108.     void Insert(string s);
  109.     void Delete(string s);
  110.  
  111.     void visualizza_Hash();
  112. };
  113. int HashTable::getVal(string s)
  114. {
  115.     int val = 0;
  116.     for (int i = 0; i < s.size(); i++)
  117.         val += int((s[i] - 'a' + 1)*pow(27.00, double(s.size() - i - 1)));
  118.     return val;
  119. }
  120. int HashTable::HashFunction(int val)
  121. {
  122.     return fmod(double(val)*(sqrt(5.00) - 1.00) / 2.00, 1.00)*double(Table.size());
  123. }
  124. void HashTable::Insert(string s)
  125. {
  126.     int val, i;
  127.  
  128.     val = getVal(s);
  129.     i = HashFunction(val);
  130.  
  131.     if (Table[i] == nullptr)
  132.         Table[i] = new ListaBid;
  133.  
  134.     Table[i]->Insert(new Nodo(s, val));
  135. }
  136. void HashTable::Delete(string s)
  137. {
  138.     int val, i;
  139.  
  140.     val = getVal(s);
  141.     i = HashFunction(val);
  142.  
  143.     if (Table[i] != nullptr)
  144.     {
  145.         Table[i]->Delete(val);
  146.         if (Table[i]->Empity())
  147.         {
  148.             delete Table[i];
  149.             Table[i] = nullptr;
  150.         }
  151.     }
  152. }
  153. bool HashTable::Search(string s)
  154. {
  155.     int val, i;
  156.  
  157.     val = getVal(s);
  158.     i = HashFunction(val);
  159.  
  160.     if (Table[i] != nullptr)
  161.     {
  162.         if (Table[i]->Search(val) != nullptr)
  163.             return true;
  164.     }
  165.     return false;
  166. }
  167. void HashTable::visualizza_Hash()
  168. {
  169.     for (int i = 0; i < Table.size(); i++)
  170.     {
  171.         cout << Table[i] << " -> ";
  172.         if (Table[i] != nullptr)
  173.         {
  174.             Table[i]->visualizza_ListaBid();
  175.         }
  176.         cout << endl;
  177.     }
  178. }
  179.  
  180.  
  181. int main()
  182. {
  183.     HashTable tabella(4);
  184.  
  185.     vector<string>A = { "a","b","c","d","e","f","g","h","i","l","m","n","o","p","q","r","s","t" };
  186.  
  187.     for (int i = 0; i < A.size(); i++)
  188.         tabella.Insert(A[i]);
  189.  
  190.     tabella.visualizza_Hash(); cout << endl;
  191.  
  192.     tabella.Delete("a");
  193.  
  194.     tabella.visualizza_Hash(); cout << endl;
  195.  
  196.     return 0;
  197. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top