Anachronos

Hash Alphabetically. Link Alphabetically

Jan 29th, 2021 (edited)
863
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C 2.75 KB | None | 0 0
  1. // Implements a dictionary's functionality
  2. // This is just an inefficient way to hash a table
  3. // I want to try hashing myself before using popular hash algorithms
  4. #include <stdbool.h>
  5. #include <ctype.h>
  6. #include "dictionary.h"
  7. #include <stdio.h>
  8. #include <stdlib.h>
  9. #include <string.h>
  10.  
  11. // Represents a node in a hash table
  12. typedef struct node
  13. {
  14.     char word[LENGTH + 1];
  15.     struct node *next;
  16. }
  17. node;
  18.  
  19. // Number of buckets in hash table
  20. const unsigned int N = 26;
  21. unsigned int total;
  22. node *table[N];
  23.  
  24. // Returns true if word is in dictionary, else false
  25. bool check(const char *word)
  26. {
  27.     int l = strlen(word)+1;
  28.     char p[l];
  29.     strcpy(p,word);
  30.     //One liner for-loop to lowercasing p
  31.     //tolower cause p to point to new address
  32.     for (int i = 0; i < l; i++) p[i] = tolower(p[i]);
  33.  
  34.     node *temp;
  35.     int i = hash(p);
  36.     temp = table[i];
  37.  
  38.     //scanning index node and check if input word is correct
  39.     while(temp)
  40.     {
  41.         if(!strcmp(temp->word,p))
  42.         {
  43.             return true;
  44.         }
  45.         temp = temp->next;
  46.     }
  47.     return false;
  48. }
  49.  
  50. // Hashes word to a number
  51. unsigned int hash(const char *word)
  52. {
  53.     //Hash alphabetically.
  54.     return ((unsigned int)word[0] % 97);
  55. }
  56.  
  57. // Loads dictionary into memory, returning true if successful
  58. bool load(const char *dictionary)
  59. {
  60.     FILE *fp = fopen(dictionary,"r");
  61.     //LENGTH = 45 defined in dictionary.h
  62.     //sizeof(char) equal to 1, so there's no need to put it in malloc
  63.     char *word = malloc(LENGTH + 1);
  64.      //[\n] regex use to read 1 word at a time.
  65.     while(fscanf(fp,"%s[\n]",word) != EOF)
  66.     {
  67.         node *n = malloc(sizeof(node));
  68.         if(n == NULL)
  69.         {
  70.             printf("error: Out of memory");
  71.             return false;
  72.         }
  73.         else if(word[0] == '\0')
  74.         {
  75.             free(n);
  76.             return false;
  77.         }
  78.         size();
  79.         int index = hash(word);
  80.         strcpy(n->word,word);
  81.         //If there's an existing node in current index, link it. Else initialize it.
  82.         n->next = NULL;
  83.         node *temp = table[index];
  84.         if(!temp)
  85.         {
  86.             table[index] = n;
  87.             continue;
  88.         }
  89.         for(;temp->next;) temp = temp->next;
  90.             temp->next = n;
  91.     }
  92.    
  93.     --total;
  94.     free(word);
  95.     fclose(fp);
  96.     return true;
  97. }
  98.  
  99. // Returns number of words in dictionary if loaded, else return 0.
  100. unsigned int size(void)
  101. {
  102.     total++;
  103.     return total;
  104. }
  105.  
  106. // Unloads dictionary from memory
  107. bool unload(void)
  108. {
  109.     // TODO
  110.     for(int i = 0; i < N; i++)
  111.     {
  112.         while(table[i])
  113.         {
  114.             node *temp = table[i]->next;
  115.             free(table[i]);
  116.             table[i] = temp;
  117.         }
  118.     }
  119.     return true;
  120. }
  121.  
Add Comment
Please, Sign In to add comment