Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- // Implements a dictionary's functionality
- #include <stdbool.h>
- #include "dictionary.h"
- #include <stdio.h>
- #include <string.h>
- #include <strings.h>
- #include <stdlib.h>
- #include <stdbool.h>
- #include <cs50.h>
- #include <ctype.h>
- // Represents a node in a hash table
- typedef struct node
- {
- char word[LENGTH + 1];
- struct node *next;
- }
- node;
- // Number of buckets in hash table
- const unsigned int N = 1;
- // Hash table
- node *table[N];
- // Global Variable for word count incremented in load() called and returned in size()
- int nWordCount = 0;
- // Returns true if word is in dictionary else false
- bool check(const char *word)
- {
- // TODO
- bool bFound = false;
- int key = hash(word);
- node *cursor = malloc(sizeof(node));
- if (cursor == NULL)
- {
- printf("\n \t Unable to malloc check()");
- return 1;
- }
- //checks if the list is outright empty : meaning the hash did not map correctly
- if (table[key]->next == NULL)
- {
- printf("\n \t Dictionary is empty");
- return 1;
- }
- //if list is not empty
- else
- {
- for(cursor = table[key]; cursor->next != NULL; cursor=cursor->next)
- {
- if (strcasecmp(word, cursor->word))
- bFound = true;
- }
- }
- free(cursor);
- return bFound;
- }
- // Hashes word to a number
- unsigned int hash(const char *word)
- {
- // TODO
- return 0;
- }
- // Loads dictionary into memory, returning true if successful else false
- bool load(const char *dictionary)
- {
- // TODO
- int key = 0;
- char word[LENGTH];
- bool bState = true;
- //initialize values for hash table. word = "" and next = NULL. no dangling pointers
- for(int i = 0; i < N; i++)
- {
- table[i] = NULL;
- //strcpy(table[i]->word, "\0");
- //table[i]->next = NULL;
- }
- //node cursor to mark head node of linked list
- node *cursor = malloc(sizeof(node));
- //check if able to malloc cursor
- if(cursor == NULL)
- {
- printf("\n \t Unable to malloc cursor in load()");
- bState = false;
- return 1;
- }
- //initialize values in node cursor
- strcpy(cursor->word, "");
- cursor->next = NULL;
- //open file
- FILE *fp1 = fopen(dictionary, "r");
- //check that the file was opened
- if (fp1 == NULL)
- {
- printf("\n \t Error opening file");
- bState = false;
- return 1;
- }
- //reading each word in the file, while not EOF
- while (fscanf(fp1, "%s", word) != EOF)
- {
- //creating the node n which will hold the word form the dictionary file
- node *n = malloc(sizeof(node));
- //check if node was created
- if (n == NULL)
- {
- printf("\n \t Unable to malloc node n in load()");
- bState = false;
- return 1;
- }
- //initialize values in node n
- strcpy(n->word, word);
- n->next = NULL;
- //counter for total words loaded
- nWordCount++;
- //call hash function to get value of word
- key = hash(word);
- //insert first node / head if array is empty
- if (table[key] == NULL)
- {
- table[key] = n;
- }
- //else array is not empty, insert new node at the end
- else if (table[key] != NULL)
- {
- cursor = table[key];
- n->next = table[key]->next;
- cursor->next = n;
- }
- }
- free(cursor);
- fclose(fp1);
- return bState;
- }
- // Returns number of words in dictionary if loaded else 0 if not yet loaded
- unsigned int size(void)
- {
- // TODO
- //return 0;
- return nWordCount;
- }
- // Unloads dictionary from memory, returning true if successful else false
- bool unload(void)
- {
- // TODO
- int i;
- int j;
- bool bState = false;
- //node runner + trailer to traverse link lists
- node *runner = malloc(sizeof(node));
- node *trailer = malloc(sizeof(node));
- //check if able to malloc cursor
- if(runner == NULL)
- {
- printf("\n \t Unable to malloc runner in load()");
- bState = false;
- return 1;
- }
- //check if able to malloc cursor
- if(trailer == NULL)
- {
- printf("\n \t Unable to malloc trailer in load()");
- bState = false;
- return 1;
- }
- //initialize values in runner
- strcpy(runner->word, "");
- runner->next = NULL;
- //initialize values in trailer
- strcpy(trailer->word, "");
- trailer->next = NULL;
- //to traverse each linked list in each array
- for (i = 0; i < N; i++)
- {
- //if index is outright NULL, increment and go to the next slot
- if(table[i]->next == NULL)
- i++;
- //set runner + trailer to index
- runner = table[i];
- trailer = table[i];
- do
- {
- //move trailer = to runner
- trailer = runner;
- //means only 1 node on the list
- if(runner->next == NULL)
- free(runner);
- //move runner 1 node forward (now 1 node ahead of trailer)
- else
- {
- runner = runner->next;
- free(trailer);
- }
- }while(runner->next != NULL);
- //assumption is that all linked lists have been free()'d after the for loop
- //all that is left is the array table[i] itself
- for(j = 0; j < N; j++)
- {
- strcpy(trailer->word, "");
- trailer->next = NULL;
- }
- free(trailer);
- free(runner);
- }
- //quick check to see it was done for all array slots
- if((i == N) && (j == N))
- bState = true;
- return bState;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement