fork download 
  1. /*Задача 1. Хеш-таблица (8 баллов)
  2. Реализуйте структуру данных типа “множество строк” на основе динамической хеш-таблицы с открытой адресацией. Хранимые строки непустые и состоят из строчных латинских букв. Начальный размер таблицы должен быть равным 8-ми. Перехеширование выполняйте при добавлении элементов в случае, когда коэффициент заполнения таблицы достигает 3/4.
  3. Хеш-функцию строки реализуйте с помощью вычисления значения многочлена методом Горнера.
  4. Структура данных должна поддерживать операции добавления строки в множество, удаления строки из множества и проверки принадлежности данной строки множеству.
  5. 1_1. Для разрешения коллизий используйте квадратичное пробирование. i-ая проба
  6. g(k, i)=g(k, i-1) + i (mod m). m - степень двойки.
  7. 1_2. Для разрешения коллизий используйте двойное хеширование.
  8. Формат входных данных
  9. Каждая строка входных данных задает одну операцию над множеством. Запись операции состоит из типа операции и следующей за ним через пробел строки, над которой проводится операция.
  10. Тип операции  – один из трех символов:
  11.     +  означает добавление данной строки в множество; 
  12.     -  означает удаление  строки из множества;  
  13.     ?  означает проверку принадлежности данной строки множеству. 
  14. При добавлении элемента в множество НЕ ГАРАНТИРУЕТСЯ, что он отсутствует в этом множестве. При удалении элемента из множества НЕ ГАРАНТИРУЕТСЯ, что он присутствует в этом множестве.
  15. Формат выходных данных
  16. Программа должна вывести для каждой операции одну из двух строк OK или FAIL, в зависимости от того, встречается ли данное слово в нашем множестве.
  17. */
  18.  
  19. #include <iostream>
  20. #include <string>
  21. #include <vector>
  22.  
  23. const int HashTableSize = 8;
  24.  
  25. using namespace std;
  26.  
  27. int Hash1( const string& key, int m ) {
  28.     int hash = 0;
  29.     int a = 11;
  30.     for( int i = 0; i < static_cast<int>( key.size() ); i++ ) {
  31.         hash = ( hash * a + key[i] ) % m;
  32.     }
  33.     return hash;
  34. }
  35.  
  36.  
  37. int Hash2( const string& key, int m ) {
  38.     int hash = 0;
  39.     int a = 17;
  40.     for( int i = 0; i <static_cast<int>( key.size() ); i++ ) {
  41.         hash = ( hash * a + key[i] ) % m;
  42.     }
  43.     hash =( 2 * hash + 1 ) % m;
  44.     return hash;
  45. }
  46.  
  47.  
  48. int HashFunction( int h1, int h2, int i, int m ) {
  49.     if( m != 0 ) {
  50.         return( h1 + i * h2 ) % m;
  51.     } else {
  52.         return 0;
  53.     }
  54. }
  55.  
  56. struct HashTableNode {
  57.     HashTableNode(const string &_key): key(_key), Del(false) {}
  58.     string key;
  59.     bool Del;
  60. };
  61.  
  62. class CHashTable {
  63. public:
  64.     CHashTable(): table(HashTableSize, NULL), _size(0) {}
  65.     bool Insert(const string &key);
  66.     bool Remove(const string &key);
  67.     bool Has(const string &key) const;
  68.     void ReHash();
  69.  
  70. private:
  71.     vector<HashTableNode*> table;
  72.     int _size;
  73. };
  74.  
  75.  
  76. bool CHashTable::Insert( const string &key ) {
  77.     if( static_cast<double>(_size)/static_cast<double>(static_cast<int>( table.size())) >=0.75) {
  78.         ReHash();
  79.     }
  80.  
  81.     int h1 = Hash1(key, static_cast<int>( table.size()) );
  82.     int h2 = Hash2(key, static_cast<int>( table.size()) );
  83.     int h = HashFunction(h1, h2, 0, static_cast<int>( table.size()));
  84.     for (int i=0; i<static_cast<int>( table.size()) and table[h] != NULL; i++) {
  85.         if(table[h]->key == key and table[h]->Del==false) {
  86.             return false;
  87.         }
  88. 		if(table[h]->Del==true ) {
  89.             table[h]->key=key;
  90.             table[h]->Del=false;
  91.             _size++;
  92.             return true;
  93.         }
  94.         h=HashFunction(h1, h2, i+1, static_cast<int>( table.size()));
  95.     }
  96.  
  97.     table[h] = new HashTableNode(key);
  98.     _size++;
  99.     return true;
  100. }
  101.  
  102. bool CHashTable::Remove(const string &key) {
  103.     int h1 = Hash1(key, static_cast<int>( table.size()) );
  104.     int h2 = Hash2(key, static_cast<int>( table.size()) );
  105.     int j = HashFunction( h1, h2, 0, static_cast<int>( table.size()));
  106.     for( int i = 0; i < static_cast<int>( table.size()); i++ ) {
  107.         if(table[j] != NULL) {
  108.             if( table[j]->key == key and table[j]->Del == false) {
  109.                 table[j]->Del = true;
  110.                 _size--;
  111.                 return true;
  112.             }
  113.         } else {
  114.             return false;
  115.         }
  116.         j = HashFunction( h1, h2, i+1, static_cast<int>( table.size()));
  117.     }
  118. }
  119.  
  120. bool CHashTable::Has( const string &key ) const {
  121.     int i = 0;
  122.     int h1 = Hash1(key, static_cast<int>( table.size()) );
  123.     int h2 = Hash2(key, static_cast<int>( table.size()) );
  124.     int h=h1;
  125.     while( table[h] != NULL and i < static_cast<int>( table.size()) ) {
  126.         if( table[h]->key == key and table[h]->Del==false ){
  127.             return true;
  128.         }
  129.         h = HashFunction( h1, h2, i+1, static_cast<int>( table.size()));
  130.         i++;
  131.     }
  132.     return false;
  133. }
  134.  
  135. void CHashTable::ReHash() {
  136.     int newBufferSize = static_cast<int>( table.size()) * 2;
  137.     vector<HashTableNode*> newBuffer(newBufferSize, NULL);
  138. 	for( int i = 0; i < static_cast<int>( table.size()); i++ ) {
  139.         if( table[i] != NULL and table[i]->Del==false ) {
  140.             int j = 0;
  141.             int h1 = Hash1(table[i]->key, newBufferSize );
  142.             int h2 = Hash2(table[i]->key, newBufferSize );
  143.             int h = HashFunction(h1, h2, j, newBufferSize );
  144.             while( j < newBufferSize ) {
  145.                 if (newBuffer[h] == NULL) {
  146.                     break;
  147.                 }
  148.                 j++;
  149.                 h = HashFunction(h1, h2, j, newBufferSize );
  150.             }
  151.             newBuffer[h] = table[i];
  152.         }
  153.     }
  154.     table = newBuffer;
  155. }
  156.  
  157. int main()
  158. {
  159.     CHashTable table;
  160.     while( true ) {
  161.         char command = 0;
  162.         string value;
  163.         cin >> command >> value;
  164.         if( cin.fail() )
  165.         {
  166.             break;
  167.         }
  168.         switch( command )
  169.         {
  170.         case '?':
  171.             cout << ( table.Has( value ) ? "OK" : "FAIL" ) << std::endl;
  172.             break;
  173.         case '+':
  174.             cout << ( table.Insert( value ) ? "OK" : "FAIL" ) << std::endl;
  175.             break;
  176.         case '-':
  177.             cout << ( table.Remove( value ) ? "OK" : "FAIL" ) << std::endl;
  178.             break;
  179.         }
  180.     }
  181.  
  182.  
  183.     return 0;
  184. }
Success #stdin #stdout 0s 4248KB
comments (?)
stdin 
+ hello
+ bye
? bye
+ bye
- bye
? bye
? hello
stdout 
OK
OK
OK
FAIL
OK
FAIL
OK
https://ideone.com/rY8SKi
language:
C++ (gcc 8.3)
created:
8 years ago
visibility:
public

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!