Vladislav_Bezruk

Untitled

Oct 19th, 2021
618
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <stdlib.h>
  3. #include <time.h>
  4.  
  5. #define N 50
  6. #define S 30
  7. #define MAX 100
  8.  
  9. using namespace std;
  10.  
  11. struct node {
  12.     int key;
  13.     int value;
  14.     struct node* next = NULL;
  15. };
  16.  
  17. void generateHashTable(node * hashTable[]);
  18.  
  19. void removingHashTable(node * hashTable[] );
  20.  
  21. int getRandom();
  22.  
  23. int hash(int key);
  24.  
  25. void push(int key, node* hashTable[]);
  26.  
  27. node* search(int key, node* hashTable[]);
  28.  
  29. void pop(int key, node* hashTable[]);
  30.  
  31. void print(node* hashTable[]);
  32.  
  33. int main() {
  34.     srand(time(NULL));
  35.    
  36.     node* hashTable[S] = { NULL };
  37.    
  38.     generateHashTable(hashTable);
  39.    
  40.     cout << "Before removing even elements:" << endl;
  41.    
  42.     print(hashTable);
  43.    
  44.     removingHashTable(hashTable);
  45.    
  46.     cout << "After removing even elements:" << endl;
  47.    
  48.     print(hashTable);
  49.    
  50.     return 0;
  51. }
  52.  
  53. void removingHashTable(node * hashTable[] ){
  54.    
  55. //     for (int i = 1; i <= MAX; i++) {
  56. //      node* p = search(i, hashTable);
  57. //      if (p != NULL && p->value == 0) {
  58. //          pop(i, hashTable);
  59. //      }
  60. //  }
  61.  
  62.     for (int i = 0; i <= MAX; i++) {
  63.        
  64.         node* hashNode = search(i, hashTable);
  65.        
  66.         if (hashNode != NULL) {
  67.             if (hashNode->value == 0) {
  68.            
  69.                 //cout<< " Key = " << hashNode->key << endl;
  70.                 //cout<< " Value =  "<< hashNode->value << endl << endl;
  71.                
  72.                 pop(hashNode->key, hashTable);
  73.                
  74.             }
  75.         }
  76.     }
  77. }
  78.  
  79. void generateHashTable(node * hashTable[]){
  80.    
  81.     for (int i = 0; i < N; i++) {
  82.         int value = rand() % MAX + 1;
  83.        
  84.         push(value, hashTable);
  85.     }
  86. }
  87.  
  88.  
  89. int hash_func(int key) {
  90.     return key % S;
  91. }
  92.  
  93. void push(int key, node* hashTable[]) {
  94.     int hashNumber = hash_func(key);
  95.    
  96.     node* newHashNode = new node;
  97.    
  98.     newHashNode->key = key;
  99.    
  100.     newHashNode->value = key %2;
  101.    
  102.     newHashNode->next = NULL;
  103.    
  104.     node* hashNode = hashTable[hashNumber];
  105.    
  106.     if (hashNode == NULL) {
  107.         hashTable[hashNumber] = newHashNode;
  108.         return;
  109.     } else {
  110.         while (hashNode->next != NULL) {
  111.             hashNode = hashNode->next;  
  112.         }
  113.                
  114.         hashNode->next = newHashNode;
  115.     }
  116. }
  117.  
  118. node* search(int key, node* hashTable[]) {
  119.     int hashNumber = hash_func(key);
  120.    
  121.     node* hashNode = hashTable[hashNumber];
  122.    
  123.     while (hashNode != NULL) {
  124.         if (hashNode->key == key) {
  125.             return hashNode;
  126.         }
  127.        
  128.         hashNode = hashNode->next;  
  129.     }  
  130.     return NULL;
  131. }
  132.  
  133. void pop(int key, node* hashTable[]) {
  134.   int hashNumber = hash_func(key);
  135.  
  136.   node* hashNode = hashTable[hashNumber];
  137.  
  138.   while (hashNode != NULL) {
  139.     if (hashNode->key == key) {
  140.       if (hashNode->next == NULL) {
  141.         if (hashTable[hashNumber] == hashNode) {  
  142.             hashTable[hashNumber] = NULL;
  143.             hashNode = NULL;
  144.         } else {        
  145.           node* tHashNode = hashTable[hashNumber];
  146.          
  147.           while (tHashNode->next != hashNode) {
  148.             tHashNode = tHashNode->next;
  149.           }
  150.           (*tHashNode).next = NULL;
  151.         }
  152.         return;
  153.       } else {
  154.         *hashNode = *hashNode->next;
  155.       }
  156.       continue;
  157.     }
  158.     hashNode = hashNode->next;    
  159.   }
  160. }
  161.  
  162. void print(node* hashTable[]) {
  163.     bool isEmpty = true;
  164.     bool emptyQuete = true;
  165.    
  166.     cout << endl << "##################################\n\t\tHash table" << endl;
  167.    
  168.     for (int i = 0; i < S; i++) {
  169.         emptyQuete = true;
  170.        
  171.         node* hashNode = hashTable[i];
  172.        
  173.    
  174.         cout << "in Hash table on index [" << i << "]: ";
  175.        
  176.         while (hashNode != NULL) {
  177.             emptyQuete = false;
  178.                    
  179.             isEmpty = false;
  180.                    
  181.             cout << hashNode->key << " ";
  182.                
  183.             hashNode = hashNode->next;  
  184.         }
  185.            
  186.         if (emptyQuete) {
  187.             cout << "--";
  188.         }
  189.            
  190.         cout << endl;
  191.     }
  192.        
  193.     if (isEmpty) {
  194.         cout << "-Empty-" << endl;
  195.     }
  196.        
  197.     cout << "##################################\n\t\tEND" << endl << endl;
  198. }
RAW Paste Data