evcamels

EBAL C++

Dec 4th, 2021
968
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string>
  4. #include <iostream>
  5. using namespace std;
  6. #define CAPACITY 50000 // Size of the Hash Table
  7.  
  8. unsigned long hash_function(char* str) {
  9.     unsigned long i = 0;
  10.     for (int j=0; str[j]; j++)
  11.         i += str[j];
  12.     return i % CAPACITY;
  13. }
  14.  
  15. typedef struct Ht_item Ht_item;
  16.  
  17. // Define the Hash Table Item here
  18. struct Ht_item {
  19.     char* key;
  20.     char* value;
  21. };
  22.  
  23. typedef struct HashTable HashTable;
  24.  
  25. // Define the Hash Table here
  26. struct HashTable {
  27.     // Contains an array of pointers
  28.     // to items
  29.     Ht_item** items;
  30.     int size;
  31.     int count;
  32. };
  33.  
  34. Ht_item* create_item(char* key, char* value) {
  35.     // Creates a pointer to a new hash table item
  36.     Ht_item* item = (Ht_item*) malloc (sizeof(Ht_item));
  37.     item->key = (char*) malloc (strlen(key) + 1);
  38.     item->value = (char*) malloc (strlen(value) + 1);
  39.      
  40.     strcpy(item->key, key);
  41.     strcpy(item->value, value);
  42.  
  43.     return item;
  44. }
  45.  
  46. HashTable* create_table(int size) {
  47.     // Creates a new HashTable
  48.     HashTable* table = (HashTable*) malloc (sizeof(HashTable));
  49.     table->size = size;
  50.     table->count = 0;
  51.     table->items = (Ht_item**) calloc (table->size, sizeof(Ht_item*));
  52.     for (int i=0; i<table->size; i++)
  53.         table->items[i] = NULL;
  54.  
  55.     return table;
  56. }
  57.  
  58. void free_item(Ht_item* item) {
  59.     // Frees an item
  60.     free(item->key);
  61.     free(item->value);
  62.     free(item);
  63. }
  64.  
  65. void free_table(HashTable* table) {
  66.     // Frees the table
  67.     for (int i=0; i<table->size; i++) {
  68.         Ht_item* item = table->items[i];
  69.         if (item != NULL)
  70.             free_item(item);
  71.     }
  72.  
  73.     free(table->items);
  74.     free(table);
  75. }
  76.  
  77. void handle_collision(HashTable* table, unsigned long index, Ht_item* item) {
  78. }
  79.  
  80. void ht_insert(HashTable* table, char* key, char* value) {
  81.     // Create the item
  82.     Ht_item* item = create_item(key, value);
  83.  
  84.     // Compute the index
  85.     unsigned long index = hash_function(key);
  86.  
  87.     Ht_item* current_item = table->items[index];
  88.      
  89.     if (current_item == NULL) {
  90.         // Key does not exist.
  91.         if (table->count == table->size) {
  92.             // Hash Table Full
  93.             printf("Insert Error: Hash Table is full\n");
  94.             // Remove the create item
  95.             free_item(item);
  96.             return;
  97.         }
  98.          
  99.         // Insert directly
  100.         table->items[index] = item;
  101.         table->count++;
  102.     }
  103.  
  104.     else {
  105.             // Scenario 1: We only need to update value
  106.             if (strcmp(current_item->key, key) == 0) {
  107.                 strcpy(table->items[index]->value, value);
  108.                 return;
  109.             }
  110.      
  111.         else {
  112.             // Scenario 2: Collision
  113.             // We will handle case this a bit later
  114.             handle_collision(table, index, item);
  115.             return;
  116.         }
  117.     }
  118. }
  119.  
  120. char* ht_search(HashTable* table, char* key) {
  121.     // Searches the key in the hashtable
  122.     // and returns NULL if it doesn't exist
  123.     unsigned long index = hash_function(key);
  124.     Ht_item* item = table->items[index];
  125.  
  126.     // Ensure that we move to a non NULL item
  127.     if (item != NULL) {
  128.         if (strcmp(item->key, key) == 0)
  129.             return item->value;
  130.     }
  131.     return NULL;
  132. }
  133.  
  134. void print_search(HashTable* table, char* key) {
  135.     char* val;
  136.     if ((val = ht_search(table, key)) == NULL) {
  137.         printf("Key:%s does not exist\n", key);
  138.         return;
  139.     }
  140.     else {
  141.         printf("Key:%s, Value:%s\n", key, val);
  142.     }
  143. }
  144.  
  145. void print_table(HashTable* table) {
  146.     printf("\nHash Table\n-------------------\n");
  147.     for (int i=0; i<table->size; i++) {
  148.         if (table->items[i]) {
  149.             printf("Index:%d, Key:%s, Value:%s\n", i, table->items[i]->key, table->items[i]->value);
  150.         }
  151.     }
  152.     printf("-------------------\n\n");
  153. }
  154.  
  155. int main() {
  156.     char key[256],value[256];
  157.     int n;
  158.     cout << "Введите количество элементов таблицы: ";
  159.     cin >> n;
  160.     cin.ignore();
  161.     HashTable* ht = create_table(CAPACITY);
  162.     for(int i=0;i<n;i++){
  163.         cout << "Введите ключ: ";
  164.         cin.getline(key,256);
  165.         cout << "Введите значение: ";
  166.         cin.getline(value,256);
  167.         ht_insert(ht, key, value);
  168.     }
  169.     print_table(ht);
  170.     free_table(ht);
  171.     return 0;
  172. }
  173.  
RAW Paste Data