0

Could somebody please offer up some advice on my pset5 speller program? The code compiles and it seems like both the load and check functions are working to some extent. However, when I run speller on a text it throws up too many misspelled words which aren't actually misspelled. As an example, I used the large dictionary to check the Alice text and got the following output:

WORDS MISSPELLED: 4073

WORDS IN DICTIONARY: 143091

WORDS IN TEXT: 29758

TIME IN load: 0.04

TIME IN check: 0.11

TIME IN size: 0.00

TIME IN unload: 0.02

TIME IN TOTAL: 0.17

As a comparison, here is the staff solution:

WORDS MISSPELLED: 295 WORDS IN DICTIONARY: 143091 WORDS IN TEXT: 29758 TIME IN load: 0.02 TIME IN check: 0.02 TIME IN size: 0.00 TIME IN unload: 0.01 TIME IN TOTAL: 0.04

I've also added a print function to my code to show which words are being compared. The example below shows that misspelled words are being printed which aren't actually mispelled:

Word=subscribe, copy_word=subscribe

Word=to, copy_word=to

Word=our, copy_word=our

Word=email, copy_word=email

Word=newsletter, copy_word=newsletter

I've pasted my code below. Any help would be much appreciated.

    #include <stdbool.h>
    #include <stdio.h>
    #include <string.h>
    #include <strings.h>
    #include <stdlib.h>
    #include <ctype.h>

    #include "dictionary.h"

    #define SIZE 500000

    bool loaded;

    unsigned int counter = 0;

    //create node structure
    typedef struct node
    {
    char word[LENGTH + 1];
    struct node *next;
    }
    node;
    //create hashtable
    node* hashtable[SIZE];

    //hash function
    unsigned long

    //Hash the word using hash function djb2
    hash(char *word)
    {
    unsigned long hash = 5381;
    int c;

    while ((c = *word++))
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash % SIZE;
    }

   /**
   * Returns true if word is in dictionary else false.
   */
   bool check(const char *word)
   {
    int l = strlen(word);
    char copy_word[l + 1];



    for(int j = 0; j <= l; j++)
    {
        copy_word[j] = (tolower(word[j]));
    }



    int h = hash(copy_word);

    node *cursor = hashtable[h];

    printf("Word=%s, copy_word=%s\n", word, copy_word );

    while(cursor != NULL)
    {
    if(strcasecmp(copy_word, cursor->word) == 0)
    {
        return true;
    }
    else
    {
        cursor = cursor->next;
    }
    }

    return false;
    }

    /**
   * Loads dictionary into memory. Returns true if successful else false.
   */
   bool load(const char *dictionary)
   {
   //open dictionary    
   FILE *fp = fopen(dictionary, "r");

   //creates buffer for word to be stored in
   char dict_word[LENGTH + 1];

    //Scan through each word in the dictionary until end of file
    while(fscanf(fp, "%s", dict_word) != EOF)
    {

    //create new node and check that space has been allocated for it
    node *new_node = malloc(sizeof(node));
    new_node->next = NULL;

    if(new_node == NULL)
    {
        unload();
        return false;
    }

    strcpy(new_node->word, dict_word);

    //has the word using the hash function
    int h = hash(new_node->word);
    node *head = hashtable[h];

    //if there is a blank space in the hashtable, place new node in that  space
    if (hashtable[h] == NULL)
    {
        hashtable[h] = new_node;

    }
    else //if not, insert new node
    {
        new_node->next = head;
        head = new_node;
    }

    counter++;


    }
    loaded = true;
    fclose(fp);
    return true;
    }

   /**
   * Returns number of words in dictionary if loaded else 0 if not yet loaded.
   */
    unsigned int size(void)
    {
    if(loaded == true)
    {
       return counter; 
    }
    else
    {
        return false;
    }
    }



    /**
    * Unloads dictionary from memory. Returns true if successful else false.
    */
    bool unload(void)
    {
    if(loaded == true)
    {
        for(int i = 0; i < SIZE; i++)
        {
            node *cursor = hashtable[i];

            while(cursor != NULL)
            {
                node *temp = cursor;
                cursor = cursor->next;
                free(temp);
            }
        }
    loaded = false;
    return true;
    }
    else
    {
    return false;
    }
    }
1

check will only return true for the first word stored in hashtable for any h.

Problem in the load function:

else //if not, insert new node
    {
        new_node->next = head;
        head = new_node;
    }

After this block executes who is hashtable[h] pointing to? The first word.
Who is pointing to new_node? Nobody. Well, technically, the node(s) called head, which are local to this function, and thus destroyed when function returns.

Hint1: node *head = hashtable[h]; is unnecessary

Hint2: If head is the head of the list, then nothing should point to it.

  • Brilliant, code works now! I was completely forgetting that hashtable[h] was indeed a pointer in itself so the head pointer wasn't needed. Thanks vert much!! – Mike B May 13 '17 at 10:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .