Vladislav_Bezruk

Untitled

Oct 19th, 2021
628
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 < S; i++) {
  63.  
  64.         node* hashNode = hashTable[i];
  65.         node* next;
  66.  
  67.         while (hashNode != NULL) {
  68.             next = hashNode->next;
  69.             if (hashNode->value == 0) {
  70.                 pop(hashNode->key, hashTable);
  71.             }
  72.             hashNode = next;
  73.         }
  74.     }
  75. }
  76.  
  77. void generateHashTable(node * hashTable[]) {
  78.  
  79.     for (int i = 0; i < N; i++) {
  80.         int value = rand() % MAX + 1;
  81.  
  82.         push(value, hashTable);
  83.     }
  84. }
  85.  
  86.  
  87. int hash_func(int key) {
  88.     return key % S;
  89. }
  90.  
  91. void push(int key, node* hashTable[]) {
  92.     int hashNumber = hash_func(key);
  93.  
  94.     node* newHashNode = new node;
  95.  
  96.     newHashNode->key = key;
  97.  
  98.     newHashNode->value = key %2;
  99.  
  100.     newHashNode->next = NULL;
  101.  
  102.     node* hashNode = hashTable[hashNumber];
  103.  
  104.     if (hashNode == NULL) {
  105.         hashTable[hashNumber] = newHashNode;
  106.         return;
  107.     } else {
  108.         while (hashNode->next != NULL) {
  109.             hashNode = hashNode->next;
  110.         }
  111.  
  112.         hashNode->next = newHashNode;
  113.     }
  114. }
  115.  
  116. node* search(int key, node* hashTable[]) {
  117.     int hashNumber = hash_func(key);
  118.  
  119.     node* hashNode = hashTable[hashNumber];
  120.  
  121.     while (hashNode != NULL) {
  122.         if (hashNode->key == key) {
  123.             return hashNode;
  124.         }
  125.  
  126.         hashNode = hashNode->next;
  127.     }
  128.     return NULL;
  129. }
  130.  
  131. void pop(int key, node* hashTable[]) {
  132.     int hashNumber = hash_func(key);
  133.  
  134.     node* hashNode = hashTable[hashNumber];
  135.  
  136.     while (hashNode != NULL) {
  137.         if (hashNode->key == key) {
  138.             if (hashNode->next == NULL) {
  139.                 if (hashTable[hashNumber] == hashNode) {
  140.                     hashTable[hashNumber] = NULL;
  141.                     hashNode = NULL;
  142.                 } else {
  143.                     node* tHashNode = hashTable[hashNumber];
  144.  
  145.                     while (tHashNode->next != hashNode) {
  146.                         tHashNode = tHashNode->next;
  147.                     }
  148.                     (*tHashNode).next = NULL;
  149.                 }
  150.                 return;
  151.             } else {
  152.                 *hashNode = *hashNode->next;
  153.             }
  154.             continue;
  155.         }
  156.         hashNode = hashNode->next;
  157.     }
  158. }
  159.  
  160. void print(node* hashTable[]) {
  161.     bool isEmpty = true;
  162.     bool emptyQuete = true;
  163.  
  164.     cout << endl << "##################################\n\t\tHash table" << endl;
  165.  
  166.     for (int i = 0; i < S; i++) {
  167.         emptyQuete = true;
  168.  
  169.         node* hashNode = hashTable[i];
  170.  
  171.  
  172.         cout << "in Hash table on index [" << i << "]: ";
  173.  
  174.         while (hashNode != NULL) {
  175.             emptyQuete = false;
  176.  
  177.             isEmpty = false;
  178.  
  179.             cout << hashNode->key << " ";
  180.  
  181.             hashNode = hashNode->next;
  182.         }
  183.  
  184.         if (emptyQuete) {
  185.             cout << "--";
  186.         }
  187.  
  188.         cout << endl;
  189.     }
  190.  
  191.     if (isEmpty) {
  192.         cout << "-Empty-" << endl;
  193.     }
  194.  
  195.     cout << "##################################\n\t\tEND" << endl << endl;
  196. }
  197.  
RAW Paste Data