SHARE
TWEET

Untitled

a guest Apr 25th, 2019 62 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.h>
  4. #include <ctype.h>
  5.  
  6. // Uncomment line with "#define DEBUG" if you want to see your hashtable.
  7. // But rememeber to send only solutions with debug turned off!
  8. // #define DEBUG 1
  9.  
  10. #define MAX_CHARS 31
  11. typedef unsigned int uint;
  12.  
  13. typedef enum states {
  14.     EMPTY = 0,
  15.     OCCUPIED = 1,
  16.     STH_WAS_HERE = 2
  17. } states;
  18.  
  19. typedef struct Slot {
  20.     char name[MAX_CHARS];
  21.     char phone[MAX_CHARS];
  22.     states state;
  23. } Slot;
  24.  
  25. uint hashfunc(const char* name) {
  26.     /*char* result = (char*)malloc(sizeof(char*)*4);
  27.     int i = 0;
  28.     int hash = 0;
  29.     for(i = 0; i < 4; i++) result[i] = '0';
  30.     for(i = 0; i < 4 && name[i] != '\0'; i++) result[i%4] = result[i%4] ^ name[i];
  31.     for(i = 0; i < 4; i++)
  32.     {
  33.         hash += result[i];
  34.         if(i != 3) hash = hash << 8;
  35.     }
  36.     free(result);
  37.     return hash; */
  38.     int p = 2137;
  39.     uint h = 0;
  40.     int i = 0;
  41.     for(i = 0; i < strlen(name); i++){
  42.         if(name[i] == '\0') break;
  43.         h = h*p +name[i];
  44.     }
  45.     return h;
  46.     /**********************
  47.     * PLACE FOR YOUR CODE *
  48.     **********************/
  49. }
  50.  
  51. void add_to_hashtable(Slot** hashtable, int n, const char* name, const char* phone) {
  52.     if(n == 0) return;
  53.     uint hash = hashfunc(name) % n;
  54.     /**********************
  55.     * PLACE FOR YOUR CODE *
  56.     **********************/
  57.     // find a good spot for placing this entry!
  58.     // You may use this:
  59.     //uint hash = ???;
  60.     while (hashtable[hash]->state == OCCUPIED) {
  61.          hash = (hash+1)%n;
  62.     }
  63.     hashtable[hash]->state = OCCUPIED;
  64.     strcpy(hashtable[hash]->name, name);
  65.     strcpy(hashtable[hash]->phone, phone);
  66. }
  67.  
  68. char* get_number(Slot** hashtable, int n, const char* name) {
  69.     if (n == 0) return NULL;
  70.     uint hash = hashfunc(name) % n;
  71.     while(hashtable[hash]->state == STH_WAS_HERE || (hashtable[hash]->state == OCCUPIED && strcmp(hashtable[hash] -> name, name) != 0)) hash = (hash+1)%n;
  72.     if(hashtable[hash] -> state == EMPTY) return NULL;
  73.     return hashtable[hash] -> phone;
  74.     /**********************
  75.     * PLACE FOR YOUR CODE *
  76.     **********************/
  77. }
  78.  
  79. void remove_from_hashtable(Slot** hashtable, int n, const char* name) {
  80.     if(n == 0) return;
  81.     uint hash = hashfunc(name) % n;
  82.     while((hashtable[hash]->state == OCCUPIED && strcmp(hashtable[hash] -> name, name) != 0) || hashtable[hash]->state == STH_WAS_HERE) hash = (hash+1)%n;
  83.     if(hashtable[hash] -> state == EMPTY) return;
  84.     /**********************
  85.     * PLACE FOR YOUR CODE *
  86.     **********************/
  87.     //hashtable[hash]->name[0] = "\0";
  88.     hashtable[hash]->state = STH_WAS_HERE;
  89. }
  90.  
  91.  
  92. void free_memory(Slot** hashtable, int n) {
  93.     for (int i = 0; i < n; i++) {
  94.         free(hashtable[i]);
  95.     }
  96.     free(hashtable);
  97. }
  98.  
  99. void debug_print_hashtable(Slot** hashtable, int n) {
  100.     #ifdef DEBUG
  101.         for (int i = 0; i < n; i++) {
  102.             printf("%d: [%d] %s\n", hashtable[i]->state, hashtable[i]->name);
  103.         }
  104.         printf("\n");
  105.     #endif
  106. }
  107.  
  108. int main() {
  109.     int Z;
  110.     scanf("%d", &Z);
  111.     while (Z--) {
  112.         int n, k;
  113.         char op;
  114.         char tmp_name[MAX_CHARS], tmp_phone[MAX_CHARS];
  115.  
  116.         scanf("%d", &n);
  117.         scanf("%d", &k);
  118.         int size = n * 10;
  119.  
  120.         Slot** hashtable = (Slot**)calloc(size, sizeof(Slot*));
  121.  
  122.         for (int i = 0; i < size; i++) {
  123.             hashtable[i] = (Slot*) malloc(sizeof(Slot));
  124.             hashtable[i]->state = EMPTY;
  125.         }
  126.  
  127.         for (int i = 0; i < k; i++) {
  128.             do { scanf("%c", &op); } while(isspace(op));
  129.             switch(op) {
  130.                 case 'a':
  131.                     scanf("%s", tmp_name);
  132.                     scanf("%s", tmp_phone);
  133.                     add_to_hashtable(hashtable, size, tmp_name, tmp_phone);
  134.                     break;
  135.                 case 'r':
  136.                     scanf("%s", tmp_name);
  137.                     remove_from_hashtable(hashtable, size, tmp_name);
  138.                     break;
  139.                 case 'g':
  140.                     scanf("%s", tmp_name);
  141.                     char* num = get_number(hashtable, size, tmp_name);
  142.                     printf("%s\n", num ? num : "");
  143.                     break;
  144.             }
  145.             debug_print_hashtable(hashtable, size);
  146.         }
  147.         free_memory(hashtable, size);
  148.     }
  149.     return 0;
  150. }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top