· 6 years ago · Mar 17, 2019, 07:48 AM
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#include "dictionary.h"
11
12// Represents "number of buckets" in a hash table
13#define N 26
14
15// Represents a node in a HASH TABLE
16typedef struct node
17{
18 char word[LENGTH + 1];
19 struct node *next;
20}
21node;
22
23// Represents a hash table as a linked list not an array
24node *hashtable[N];
25
26// Hashes word to a number between 0 and 25, in equivalent to between 'a' and 'z' inclusive,
27// based on its first letter
28unsigned int hash(const char *word)
29{
30 return tolower(word[0]) - 'a';
31}
32
33int counter = 0;
34
35// Loads dictionary into memory, returning true if successful else false
36bool load(const char *dictionary) // load a dictionary of words into the hash table
37{
38 // Initialize hash table
39 for (int i = 0; i < N; i++)
40 {
41 hashtable[i] = NULL;
42 }
43
44 // Open dictionary
45 FILE *file = fopen(dictionary, "r");
46 if (file == NULL)
47 {
48 unload();
49 return false;
50 }
51
52 // Buffer for a word
53 char word[LENGTH + 1];
54
55 // Insert words into hash table
56 while (fscanf(file, "%s", word) != EOF) //irritating through file, assign 1 word at a time to word
57 {
58 // TODO
59 counter++;
60
61 node *new_node = malloc(sizeof(node)); //create new node
62 if(new_node == NULL) //make sure malloc succeeded
63 {
64 unload();
65 return false;
66 }
67
68 strcpy(new_node->word,word); // copy that word into new node
69
70
71 int index = hash(new_node->word); // hash function splits out a hashed-code
72
73 if(hashtable[index] != NULL) //if the bucket has had a word or more
74 {
75 new_node->next = hashtable[index]; // point the new node to the very first node (pointer that head's pointing to) of this linklist
76 hashtable[index] = new_node; // pin new_node to the hash table.
77 }
78 else
79 {
80 hashtable[index] = new_node; // Insert into the linked list (hashtable)
81 }
82
83 }
84
85 // Close dictionary
86 fclose(file);
87
88 // Indicate success
89 return true;
90}
91
92// Returns number of words in dictionary if loaded else 0 if not yet loaded
93unsigned int size(void)
94{
95 // TODO
96 if(counter>0)
97 {
98 return counter;
99 }
100 else
101 {
102 return 0;
103 }
104}
105
106// Returns true if word is in dictionary else false
107bool check(const char *word)
108{
109 // TODO
110 bool result = false;
111
112 int keyAccess = hash(word); //get the key by hashing the word
113
114 node *cursor = hashtable[keyAccess]; // access the right bucket
115
116 while(cursor) // irritating through a linklist of a bucket.
117 {
118 if(strcasecmp(cursor->word,word) == 0) // if the two strings are equal
119 {
120 return result = true; // return true if that word exists
121 break;
122 }
123 cursor = cursor->next; //increment
124 }
125 //indicate result
126 return result;
127}
128
129// Unloads dictionary from memory, returning true if successful else false
130bool unload(void)
131{
132 // TODO
133
134 for (int i = 0; i < N; i++) //irritating through the hash table's buckets
135 {
136 node *finger = NULL;
137 finger = hashtable[i]; //point finger to the indexed a bucket
138
139 while(finger)
140 {
141 node *temp = finger; //create a temporary varible to keep moving finger
142 finger = finger->next; //increment (moving along the chain(the linked-list)) finger will point to NULL at somepoint.
143 free(temp); // free temporary varible (it means freeing up the node finger has pointed to)
144 }
145 }
146
147 //indicate success
148 return true;
149}