CheckDictionary.c 2.7 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118
  1. //ready
  2. //this was created by combining and modifying the hash_table sample code
  3. //not much to explain, it also includes code from test_dictionary.c
  4. #include <stdio.h>
  5. #include <stdlib.h>
  6. //#include "boggle.h"
  7. #include <string.h>
  8. #include <ctype.h>
  9. #include "game_server.h"
  10. #define MAX_LINE 200
  11. #define BIG_HASH_SIZE 30000
  12. #define SMALL_HASH_SIZE 200
  13. typedef struct d_node {
  14. char * key;
  15. struct d_node *next;
  16. }DNode;
  17. unsigned hash(const char *s) {
  18. unsigned hashval;
  19. for (hashval = 0; *s != '\0'; s++)
  20. hashval = *s + 31 * hashval;
  21. return hashval ;
  22. }
  23. DNode * lookup (DNode ** dictionary, int hash_size, const char *key) {
  24. DNode * np;
  25. unsigned int hashval = hash(key);
  26. for (np = dictionary [hashval % hash_size]; np !=NULL; np = np->next)
  27. if (strcmp (key, np->key) == 0)
  28. return np; //found
  29. return NULL; //not found
  30. }
  31. char *copystr(const char *s) { /* make a duplicate of s */
  32. char *p;
  33. int len = strlen(s);
  34. p = (char *) malloc(len+1); /* +1 for ’\0’ */
  35. if (p != NULL)
  36. strncpy(p, s, len);
  37. p[len] = '\0';
  38. return p;
  39. }
  40. DNode * insert (DNode ** dictionary, int hash_size, const char * key) {
  41. unsigned int hashval;
  42. DNode *np;
  43. if ((np = lookup (dictionary, hash_size, key)) == NULL ) { //
  44. np = (DNode *) malloc (sizeof (*np));
  45. if (np == NULL || (np->key = copystr (key)) == NULL)
  46. return NULL;
  47. hashval = hash (key) % hash_size;
  48. //now links itself on top of array entry
  49. np->next = dictionary [hashval];
  50. dictionary [hashval] = np;
  51. }
  52. return np;
  53. }
  54. void free_dictionary (DNode ** dictionary, int hash_size) {
  55. int i;
  56. for (i=0; i<hash_size; i++) { //iterate over hash array
  57. if (dictionary [i]!=NULL) { //if there is an entry at position i
  58. DNode *head = dictionary[i]; //find the head of the linked list
  59. DNode *current = head;
  60. while (current != NULL) {
  61. DNode * temp = current;
  62. current = current->next;
  63. if (temp->key !=NULL)
  64. free (temp->key);
  65. free (temp);
  66. }
  67. dictionary[i] = NULL;
  68. }
  69. }
  70. }
  71. int WordInDictionary(char * word){
  72. FILE * input_FP;
  73. char line [MAX_LINE];
  74. char * name_of_file;
  75. DNode* result;
  76. static DNode* big_dictionary [BIG_HASH_SIZE];
  77. name_of_file = "WordsList.txt";
  78. if(!(input_FP = fopen (name_of_file, "r"))) {
  79. fprintf(stderr, "Unable To Open File \"%s\" \n", name_of_file);
  80. return 1;
  81. }
  82. while(fgets (line, MAX_LINE, input_FP) != NULL){
  83. line[strcspn(line, "\r\n")] = '\0';
  84. insert (big_dictionary, BIG_HASH_SIZE, line);
  85. }
  86. fclose(input_FP);
  87. result = lookup(big_dictionary, BIG_HASH_SIZE, word);
  88. if(result != NULL)
  89. return 1;
  90. else
  91. return 0;
  92. free_dictionary(big_dictionary, BIG_HASH_SIZE);
  93. return 0;
  94. }