dictionaryChecker.c 4.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include "boggle.h"
  5. #include <ctype.h>
  6. #define MAX_LINE 100
  7. #define BIG_HASH_SIZE 20000
  8. #define SMALL_HASH_SIZE 100
  9. typedef struct d_node {
  10. char* key;
  11. struct d_node *next;
  12. }DNode;
  13. char *copystr(const char *s) { /* make a duplicate of s */
  14. char *p;
  15. int len = strlen(s);
  16. p = (char *) malloc(len+1); /* +1 for í\0í */
  17. if (p != NULL)
  18. strncpy(p, s, len);
  19. p[len] = '\0';
  20. return p;
  21. }
  22. //form hash value for string s
  23. ////this produces a starting value in the dictionary array
  24. unsigned hash(const char *s) {
  25. unsigned hashval;
  26. for (hashval = 0; *s != '\0'; s++)
  27. hashval = *s + 31 * hashval;
  28. return hashval ;
  29. }
  30. //Performs search for a key in the hashtable.
  31. ////if the string s is in the dictionary, it is in the list of blocks
  32. ////beginning in array entry hash(s).
  33. ////if lookup finds entry for s, it returns a pointer to the node
  34. ////if not - it returns NULL
  35. DNode * lookup (DNode ** dictionary, int hash_size, const char *key) {
  36. DNode * np;
  37. unsigned int hashval = hash(key);
  38. for (np = dictionary [hashval % hash_size]; np !=NULL; np = np->next)
  39. if (strcmp (key, np->key) == 0)
  40. return np; //found
  41. return NULL; //not found
  42. }
  43. //insert uses lookup to detemine whether key is already in the dictionary
  44. ////if not, a new entry is created
  45. DNode * insert (DNode ** dictionary, int hash_size, const char * key) {
  46. unsigned int hashval;
  47. DNode *np;
  48. if ((np = lookup (dictionary, hash_size, key)) == NULL ) { //
  49. np = (DNode *) malloc (sizeof (*np));
  50. if (np == NULL || (np->key = copystr (key)) == NULL)
  51. return NULL;
  52. hashval = hash (key) % hash_size;
  53. //now links itself on top of array entry
  54. np->next = dictionary [hashval];
  55. dictionary [hashval] = np;
  56. }
  57. return np;
  58. }
  59. void free_dictionary (DNode ** dictionary, int hash_size) {
  60. int i;
  61. for (i=0; i<hash_size; i++) { //iterate over hash array
  62. if (dictionary [i]!=NULL) { //if there is an entry at position i
  63. DNode *head = dictionary[i]; //find the head of the linked list
  64. DNode *current = head;
  65. while (current != NULL) {
  66. DNode * temp = current;
  67. current = current->next;
  68. if (temp->key !=NULL)
  69. free (temp->key);
  70. free (temp);
  71. }
  72. dictionary[i] = NULL; //BUG fix
  73. }
  74. }
  75. }
  76. int isInDictionary(char * word) {
  77. //int i;
  78. FILE *input_FP;
  79. char line [MAX_LINE];
  80. char * file_name;
  81. DNode* result;
  82. static DNode* big_dictionary [BIG_HASH_SIZE];
  83. // static DNode* small_dictionary[SMALL_HASH_SIZE];
  84. //
  85. // if (argc < 2) {
  86. // fprintf (stderr, "test_dictionary <dictionary file name>\n");
  87. // return 1;
  88. // }
  89. file_name = "wordlist.txt";
  90. if(!(input_FP = fopen ( file_name , "r" ))) {
  91. fprintf(stderr,"Could not open file \"%s\" for reading dictionary words\n", file_name);
  92. return 1;
  93. }
  94. while( fgets (line, MAX_LINE, input_FP)!=NULL ) {
  95. line[strcspn(line, "\r\n")] = '\0'; //trim new line characters
  96. insert (big_dictionary, BIG_HASH_SIZE, line);
  97. }
  98. fclose (input_FP);
  99. result = lookup (big_dictionary, BIG_HASH_SIZE, word);
  100. if (result != NULL)
  101. return 1;
  102. else
  103. return 0;
  104. /*result = lookup (big_dictionary, BIG_HASH_SIZE, "MACAC");
  105. if (result != NULL)
  106. printf ("<MACAC> is in the dictionary\n");
  107. else
  108. printf ("<MACAC> not found\n");
  109. */
  110. free_dictionary(big_dictionary, BIG_HASH_SIZE);
  111. /* printf ("\n new game session: 1\n");
  112. //now testing small dictionary - twice - with cleanup
  113. char key[] = "arc";
  114. capitalize(key);
  115. for (i =0; i< 5; i++) {
  116. result = lookup (small_dictionary, SMALL_HASH_SIZE, key);
  117. if (result == NULL) {
  118. insert (small_dictionary, SMALL_HASH_SIZE, key);
  119. printf ("Successfully inserted %s in session 1\n", key);
  120. }
  121. else
  122. printf ("%s has been already used in session 1\n", key);
  123. }
  124. free_dictionary(small_dictionary, SMALL_HASH_SIZE);
  125. printf ("\n new game session: 2\n");
  126. for (i =0; i< 5; i++) {
  127. result = lookup (small_dictionary, SMALL_HASH_SIZE, key);
  128. if (result == NULL){
  129. insert (small_dictionary, SMALL_HASH_SIZE, key);
  130. printf ("Successfully inserted %s in session 2\n", key);
  131. }
  132. else
  133. printf ("%s has been already used in session 2\n", key);
  134. }
  135. free_dictionary(small_dictionary, SMALL_HASH_SIZE);
  136. */
  137. return -10000;
  138. }