Guest User

Untitled

a guest
Jun 24th, 2016
51
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. /**
  2. * dictionary.c
  3. *
  4. * Computer Science 50
  5. * Problem Set 5
  6. *
  7. * Implements a dictionary's functionality.
  8. */
  9. #include <stdio.h>
  10. #include <stdlib.h>
  11. #include <stdbool.h>
  12. #include <string.h>
  13. #include <ctype.h>
  14. #include "dictionary.h"
  15.  
  16. //the array that will store the dictionary
  17. node* theArray[HASHTABLE_SIZE];
  18. node* cursor = NULL;
  19.  
  20. /**
  21. * The hash function.
  22. * I found this hash function here:https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/?
  23. * Thank you to (cs50 staff)Brenda's husband for the function */
  24.  
  25. int hash_itz(char* needs_hashing)
  26. {
  27. unsigned int hash = 0;
  28.  
  29. for (int i=0, n=strlen(needs_hashing); i<n; i++)
  30. {
  31. hash = (hash << 2) ^ needs_hashing[i];
  32. }
  33. return hash % HASHTABLE_SIZE;
  34. }
  35. /**
  36. * Returns true if word is in dictionary else false.
  37. */
  38.  
  39.  
  40. int sizer = 0;
  41.  
  42. bool check(const char* word)
  43. {
  44. // TODO
  45. int length = strlen(word);
  46.  
  47. char* word1 = malloc(length);
  48.  
  49. for(int i = 0; i < strlen(word); i++)
  50. {
  51. if(isalpha(word[i]))
  52. word1[i] = tolower(word[i]);
  53. }
  54. word1[length] = '\0';
  55.  
  56. int hashBalue = hash_itz(word1); // hashing. "Balue" for difference to load's hashValue;
  57.  
  58. if(theArray[hashBalue] != NULL)
  59. {
  60.  
  61.  
  62.  
  63. cursor = theArray[hashBalue];
  64.  
  65. while(cursor!=NULL)
  66. {
  67. int stringCompare = strcmp(word1, cursor->word);
  68.  
  69. if(stringCompare == 0)
  70. {
  71. return true;
  72. }
  73.  
  74.  
  75. cursor = cursor->next;
  76.  
  77.  
  78. }
  79. }
  80. return false;
  81. }
  82.  
  83. /**
  84. * Loads dictionary into memory. Returns true if successful else false.
  85. */
  86. bool load(const char* dictionary)
  87. {
  88. // open the dictionary and check if it opens correctly
  89. FILE* diction = fopen(dictionary, "r");
  90. char wordCopy[LENGTH + 1];
  91.  
  92. if (diction == NULL)
  93. {
  94. printf("Could not load dictionary.\n");
  95. unload();
  96. return false;
  97. }
  98.  
  99. //scanning through the dictionary word by word.
  100. while(fgetc(diction)!= EOF)
  101. {
  102. int hashValue = 0;
  103. node* node_1 = calloc(1, sizeof(node));
  104.  
  105. node_1->next = NULL;
  106.  
  107. fscanf(diction, "%s", node_1->word);
  108. strcpy(wordCopy, node_1->word);
  109. //hashing (returns value up to 65536)
  110.  
  111.  
  112. hashValue = hash_itz(node_1->word);
  113.  
  114. //if the location at the array is NULL, put the node there
  115. if(theArray[hashValue] == NULL)
  116. {
  117. theArray[hashValue] = calloc(1, sizeof(node));
  118. strcpy(theArray[hashValue]->word, wordCopy);
  119. }
  120. else //if a node exists at the location.
  121. {
  122.  
  123. node_1 -> next = theArray[hashValue] -> next;
  124. theArray[hashValue] -> next = node_1;
  125. }
  126.  
  127. //this is used later for size function
  128. sizer++;
  129. }
  130.  
  131. //That's all folks.
  132. return true;
  133.  
  134. }
  135.  
  136. /**
  137. * Returns number of words in dictionary if loaded else 0 if not yet loaded.
  138. */
  139. unsigned int size(void)
  140. {
  141. // TODO
  142.  
  143. return sizer;
  144.  
  145. }
  146.  
  147. /**
  148. * Unloads dictionary from memory. Returns true if successful else false.
  149. */
  150. bool unload(void)
  151. {
  152. // TODO
  153.  
  154. return true;
  155. }
  156.  
  157.  
  158.  
  159.  
  160. DICTIONARY.H
  161.  
  162. /**
  163. * dictionary.h
  164. *
  165. * Computer Science 50
  166. * Problem Set 5
  167. *
  168. * Declares a dictionary's functionality.
  169. */
  170.  
  171. #ifndef DICTIONARY_H
  172. #define DICTIONARY_H
  173.  
  174. #include <stdbool.h>
  175. #include <string.h>
  176. #include <stdlib.h>
  177.  
  178. // maximum length for a word
  179. // (e.g., pneumonoultramicroscopicsilicovolcanoconiosis)
  180. #define LENGTH 45
  181. #define HASHTABLE_SIZE 65536
  182. /**
  183. * Returns true if word is in dictionary else false.
  184. */
  185. bool check(const char* word);
  186.  
  187. /**
  188. * Loads dictionary into memory. Returns true if successful else false.
  189. */
  190. bool load(const char* dictionary);
  191.  
  192. /**
  193. * Returns number of words in dictionary if loaded else 0 if not yet loaded.
  194. */
  195. unsigned int size(void);
  196.  
  197. /**
  198. * Unloads dictionary from memory. Returns true if successful else false.
  199. */
  200. bool unload(void);
  201.  
  202. #endif // DICTIONARY_H
  203.  
  204.  
  205. /**
  206. * The hash function.
  207. * I found this hash function here:https://www.reddit.com/r/cs50/comments/1x6vc8/pset6_trie_vs_hashtable/?
  208. * Thank you to (cs50 staff)Brenda's husband for the function */
  209. int hash_itz(char* needs_hashing);
  210.  
  211. //linked list
  212. typedef struct node
  213. {
  214. char word[LENGTH+1];
  215. struct node *next;
  216. }
  217. node;
RAW Paste Data