Facebook
From ozioo, 3 Years ago, written in C++.
Embed
Download Paste or View Raw
Hits: 167
  1. // Implements a dictionary's functionality
  2.  
  3. #include <ctype.h>
  4. #include <stdbool.h>
  5. #include <stdio.h>
  6. #include <stdlib.h>
  7. #include <string.h>
  8. #include <strings.h>
  9.  
  10.  
  11. #include "dictionary.h"
  12.  
  13. // Represents a node in a hash table
  14. typedef struct node
  15. {
  16.     char word[LENGTH + 1];
  17.     struct node *next;
  18. }
  19. node;
  20.  
  21. // Number of buckets in hash table
  22. const unsigned int N = 50000;
  23.  
  24.  
  25.  
  26.  
  27. // Hash table
  28. node *table[N];
  29.  
  30. // Returns true if word is in dictionary else false
  31. bool check(const char *word)
  32. {
  33.     int index = hash(word);
  34.    
  35.    
  36.     for (node *cursor = table[index]; cursor != NULL; cursor = cursor->next)
  37.     {
  38.      int check = strcasecmp(cursor -> word, word);
  39.      if(check == 0)
  40.      {
  41.          return true;
  42.      }
  43.        
  44.     }
  45.    
  46.     return false;
  47. }
  48.  
  49. // Hashes word to a number
  50. // this hash function is based on a hash function called djb2 and it is from http://www.cse.yorku.ca/~oz/hash.html
  51. unsigned int hash(const char *word)
  52. {
  53.    
  54.     unsigned long hash = 5381;
  55.     int c;
  56.  
  57.     while ((c = *word++))
  58.     {
  59.        
  60.         hash = ((hash << 5) + hash) + tolower(c);
  61.      
  62.     }
  63.     return hash % N;
  64. }
  65.  
  66.    
  67.  
  68.  
  69. // Loads dictionary into memory, returning true if successful else false
  70. bool load(const char *dictionary)
  71. {
  72.     char word[LENGTH + 1];
  73.    FILE *file = fopen(dictionary, "r");
  74.     if (!file)
  75.     {
  76.         return false;
  77.     }
  78.    
  79.     while (fscanf(file, "%s", word) != EOF)
  80.     {
  81.       int index = hash(word);
  82.      
  83.       node *new_ = malloc(sizeof(node));
  84.      
  85.       if (new_ == NULL)
  86.       {
  87.         return 1;  
  88.       }
  89.       strcpy(new_->word, word);
  90.      
  91.       new_->next= table[index];
  92.      
  93.       new_ = table[index]  ;
  94.        
  95.     }
  96.     fclose(file);
  97.     return true;
  98. }
  99.    
  100.    
  101.  
  102.  
  103. // Returns number of words in dictionary if loaded else 0 if not yet loaded
  104. unsigned int size(void)
  105. {
  106.     int count = 0;
  107.     for (int o = 0; o< N;o++)
  108.     {
  109.         for (node *temp = table[o]; temp != NULL; temp = temp->next)
  110.     {
  111.         count ++;
  112.         temp = temp -> next;
  113.        
  114.     }
  115.    
  116.     }
  117.  
  118.     return count;
  119. }
  120.  
  121. // Unloads dictionary from memory, returning true if successful else false
  122. bool unload(void)
  123. {
  124.     for (int o = 0; o< N;o++)
  125.     {
  126.         node *cursor2 = table[o];
  127.        
  128.      while(cursor2 != NULL)
  129.      {
  130.          node *temp = cursor2;
  131.          
  132.          cursor2 = cursor2->next;
  133.          
  134.          free(temp);
  135.      }
  136.     }
  137.     return true;
  138.  }
  139.  
  140.