1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
// Implements a dictionary's functionality
#include "dictionary.h"
#include <ctype.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.h>
// Represents a node in a hash table
typedef struct node
{
char word[LENGTH + 1];
struct node *next;
} node;
// TODO: Choose number of buckets in hash table
const unsigned int N = 26;
// Hash table
node *table[N];
// Size integer
int siz = 0;
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
// hash word to find bucket
int val = hash(word);
node *current = table[val];
// check all nodes in the bucket
while (current != NULL)
{
// check if this is the word
if (strcasecmp(current->word, word) == 0)
{
return true;
}
current = current->next;
}
return false;
}
// Hashes word to a number
unsigned int hash(const char *word)
{
return (tolower(word[0]) % 26);
}
// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
// initialize the table
for (int i = 0; i < N; i++)
{
// malloc size of next
table[i] = NULL;
}
// Open dictionary file
FILE *source = fopen(dictionary, "r");
if (source == NULL)
{
return false;
}
// read each word in dictionary
char word[LENGTH + 1];
// use fscanf(file, "%s", word) to grab words
// check for ended file
while (fscanf(source, "%s", word) == 1)
{
// update size int
siz++;
// create new node
// use malloc
node *ptr = malloc(sizeof(node));
// check if return is NULL
if (ptr == NULL)
{
fclose(source);
return false;
}
// copy word from fscanf into node using strcpy
strcpy(ptr->word, word);
// set the new ptr
ptr->next = NULL;
// hash the word to find the bucket it goes in
int val = hash(ptr->word);
// put new node at begining of bucket
if (table[val] == NULL)
{
// if empty put it there
table[val] = ptr;
}
else
{
// if not empty move the current first one down,
// then put the new one there
ptr->next = table[val];
table[val] = ptr;
}
}
// Close the dictionary file
fclose(source);
return true;
}
// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
return siz;
}
// Unloads dictionary from memory, returning true if successful, else false
bool unload(void)
{
// for every bucket
for (int i = 0; i < N; i++)
{
// while there's more in the bucket
node *current = table[i];
while (current != NULL)
{
// record position of this node
node *this = current;
// record position of next node
current = current->next;
// free this node
free(this);
}
}
return true;
}
|
