check function in speller pset5, not quite understanding the apostrophe

Question

I am working on the check() function of dictionary.c. I am using it to test cat.txt:

A cat is not a caterpillar.

It says everything is correctly spelled except "not" When I check the hashtable against this it shows me that it's trying to connect to a linked list "n's". I've seen a lot of posts about apostrophe's but I'm not quite sure why since "not" does not have an apostrophe.

If so, how might I remove the apostrophe or deal with it? Is this an ascii operation? I do recall in the large dictionary file there are many words with apostrophe's and perhaps the way the words are stored needs to account for apostrophes.... any feedback greatly appreciated.

My check() code is below:

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    // TODO
    // Determining which hashpointer should we use
    node *cursor = hashtable[hash(word)];
    // Converting uppercase to lowercase
    char *tmp = malloc((strlen(word) + 1) * sizeof(char));
    if (!tmp)
    {
        return 1;
    }


    for (int i=0; i < strlen(word); i++)
    {
        tmp[i] = tolower(word[i]);
    }

    while (cursor != NULL)
    {
        int counter = 0;
        printf("el wordios maximus is %s\n", cursor->word);
        for(int i = 0; i < strlen(cursor->word); i++)
        {
            if(cursor->word[i] == tmp[i])
            {
                counter++;
            }
            if(counter == strlen(cursor->word)){
                return true;
            }
        }
        // if (strcmp(cursor->word, tmp) == 0)
        // {

        //     return true;
        //     free(cursor);
        //     break;
        // }
        // else
        // {
            cursor = cursor -> next;
        // }
    }
    free(cursor);
    return false;
}

Otherwise I could have an issue in my load() where n's is somehow being inputted as word in my dictionary? I believe the issue is with check(), but below is my load() just in case!

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    printf("load function!\n");

    // Initialize hash table
    for (int i = 0; i < N; i++)
    {
       // printf("hash is ini dont cry! \n");
        hashtable[i] = NULL;
    }

    // Open dictionary
    file = fopen(dictionary, "r");
    if (file == NULL)
    {
        printf("file no full!");
        unload();
        return false;
    }

    // word is this long
    char word[LENGTH + 1];
     printf("pass word length!\n");

    // Insert words into hash table
    //fscanf returns words it finds and stops at last word
    while (fscanf(file, "%s", word) != EOF)
    {
        word_count++;
        // TODO
        //hash function
        //since a hashtable is an array of linked lists
        //we are telling the program where to put our new word in the array
        //basically which list it will add word to the front of
        int index = hash(word);

        //if this is the start of table
        if(hashtable[index] == NULL)
        {
          head = malloc(sizeof(node));
          if(head == NULL)
           {
             printf("null head!");
             unload();
             exit (1);
           }

        //add word into node...
        strcpy(head->word ,word);

        head->next = NULL;

        //tell head what word it represents
        hashtable[index] = head;

        }
        else
        {
        //make a new node for each word
        //malloc a node *for each new word
        node *new_node = malloc(sizeof(node));

        //check if malloc succeeded
        if (new_node == NULL)
        {
            printf("null head!");
            unload();
            return false;
        }

        strcpy(new_node->word, word);
        // printf("WORD IS %s\n", word);

        //link new_node to head
        new_node->next = head;

        //link head to new_node, preserving head position
        head = new_node;
    }
    }

    //free(new_node);

    // Close dictionary
    fclose(file);

    // Indicate success
    printf("yay! we loaded dict!\n");
    return true;
}

Answer 1

n's is the first entry starting with n in dictionaries/large. Apostrophes are significant in the trie version of this pset, since that must store every character of word separately; they are not significant in the hash version. It is a distracting coincidence.

This load will create a hashtable of at most one word in each alpha index. At the end of the if(hashtable[index] == NULL) block, hashtable[index]->next is NULL. And nothing will change that.

There needs to be code in the else block that manages/manipulates the actual head of the list hashtable[index], not just the node named head. In fact head is ostensible unnecessary. Think about hashtable[index] as the head of the list, and not an actual node containing a word.

If the hashtable is not populated correctly, how can cat.txt only report not as a misspelled word? "is", "cat" and "caterpillar" are not in the hashtable either. ("a" is because it is the first a entry). If you look into the large dictionary, you will discover "i" is the first i entry and "ca" is the first c entry.

cursor->word is always the first entry. What happens with "is"? It returns true before it even processes the s!

if(cursor->word[i] == tmp[i])
            {
                counter++;
            }
            if(counter == strlen(cursor->word)){ 
                return true;
            }

Since strlen("i") is 1, program returns true on the first iteration. Similarly, cat and caterpillar return true after the letter a (because ca is the first entry).

There are other problems in check that will not become apparent until load is corrected.

• free(cursor);. Since cursor is set the the head of the list, this will free that index in the list. Perhaps you meant free(tmp) since it is explicitly malloc'd in the function.
• speaking of tmp, it is not null-terminated, and will give inaccurate results. It is (correctly) malloc'd for strlen+1 bytes, but only populates strlen bytes. That will be a serious problem when a shorter word follows a longer one.