smatskevich

StringHashTable

Nov 26th, 2016
193
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <string>
  3. #include <vector>
  4. using std::string;
  5. using std::vector;
  6.  
  7. // Начальный размер хеш-таблицы.
  8. const int InitialTableSize = 1001;
  9.  
  10. // Простая хеш-функция строки. Использует только первый символ.
  11. int StringHash( const string& source, int m )
  12. {
  13.     if( source.empty() ) {
  14.         return 0;
  15.     }
  16.     return source[0] % m;
  17. }
  18.  
  19. class CHashTable {
  20. public:
  21.     CHashTable();
  22.     ~CHashTable();
  23.  
  24.     // Проверка наличия ключа в таблице.
  25.     bool Has( const string& key ) const;
  26.     // Добавление ключа в таблицу. Если ключ уже есть, возвращает false.
  27.     bool Add( const string& key );
  28.     // Удаление ключа из таблицы. Если ключа не было, возвращает false.
  29.     bool Remove( const string& key );
  30.  
  31. private:
  32.     struct CHashTableNode {
  33.         string Data;
  34.         CHashTableNode* Next;
  35.  
  36.         explicit CHashTableNode( const string& data ) : Data( data ), Next( 0 ) {}
  37.     };
  38.     vector<CHashTableNode*> table;
  39. };
  40.  
  41. CHashTable::CHashTable()
  42. {
  43.     table.resize( InitialTableSize, 0 );
  44. }
  45.  
  46. CHashTable::~CHashTable()
  47. {
  48.     // Чистка всех цепочек.
  49.     for( int i = 0; i < static_cast<int>( table.size() ); ++i ) {
  50.         for( CHashTableNode* node = table[i]; node != 0; ) {
  51.             CHashTableNode* nextNode = node->Next;
  52.             delete node;
  53.             node = nextNode;
  54.         }
  55.     }
  56. }
  57.  
  58. bool CHashTable::Has( const string& key ) const
  59. {
  60.     int hash = StringHash( key, table.size() );
  61.     for( CHashTableNode* node = table[hash]; node != 0; node = node->Next ) {
  62.         if( node->Data == key ) {
  63.             return true;
  64.         }
  65.     }
  66.     return false;
  67. }
  68.  
  69. bool CHashTable::Add( const string& key )
  70. {
  71.     int hash = StringHash( key, table.size() );
  72.     for( CHashTableNode* node = table[hash]; node != 0; node = node->Next ) {
  73.         if( node->Data == key ) {
  74.             return false;
  75.         }
  76.     }
  77.     // Добавим новый ключ в начало цепочки.
  78.     CHashTableNode* newNode = new CHashTableNode( key );
  79.     newNode->Next = table[hash];
  80.     table[hash] = newNode;
  81.     return true;
  82. }
  83.  
  84. bool CHashTable::Remove( const string& key )
  85. {
  86.     int hash = StringHash( key, table.size() );
  87.     if( table[hash] == 0 ) {
  88.         // Ключей в цепочке нет.
  89.         return false;
  90.     }
  91.     CHashTableNode* node = table[hash];
  92.     if( node->Data == key ) {
  93.         // Если искомый ключ - первый в списке.
  94.         table[hash] = node->Next;
  95.         delete node;
  96.         return true;
  97.     }
  98.  
  99.     for( CHashTableNode* nextNode = node->Next; nextNode != 0; node = nextNode, nextNode = nextNode->Next ) {
  100.         if( nextNode->Data == key ) {
  101.             node->Next = nextNode->Next;
  102.             delete nextNode;
  103.             return true;
  104.         }
  105.     }
  106.     return false;
  107. }
  108.  
  109. int main()
  110. {
  111.     CHashTable stringsTable;
  112.  
  113.     while( true ) {
  114.         char command = 0;
  115.         string value;
  116.         std::cin >> command >> value;
  117.         if( std::cin.fail() ) {
  118.             break;
  119.         }
  120.         switch( command ) {
  121.         case '?':
  122.             std::cout << ( stringsTable.Has( value ) ? "OK" : "FAIL" ) << std::endl;
  123.             break;
  124.         case '+':
  125.             std::cout << ( stringsTable.Add( value ) ? "OK" : "FAIL" ) << std::endl;
  126.             break;
  127.         case '-':
  128.             std::cout << ( stringsTable.Remove( value ) ? "OK" : "FAIL" ) << std::endl;
  129.             break;
  130.         }
  131.     }
  132.     return 0;
  133. }
RAW Paste Data

Adblocker detected! Please consider disabling it...

We've detected AdBlock Plus or some other adblocking software preventing Pastebin.com from fully loading.

We don't have any obnoxious sound, or popup ads, we actively block these annoying types of ads!

Please add Pastebin.com to your ad blocker whitelist or disable your adblocking software.

×