0

I've been doing the speller exercise for a while and I'm stuck in the "handle substrings properly". Here's my code:

    // Implements a dictionary's functionality

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

#include "dictionary.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 = 26;

// Hash table
node *table[N];
    
int counter = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    //check in which location of the table the word is
    int bucket = hash(word);
    
    node *cursor = NULL;
    
    //cursor points at the beginning of the list in the location bucket
    cursor = table[bucket];
    
    //if the cursor is not empthy it should compare the word from the text and the dictionary, if it's not in that location the cursor moves to next and the comparison is done again
    while (cursor != NULL)
    {
        if (strcasecmp(word, table[bucket]->word) == 0)
        {
            return true;
        }
        else
        {
            cursor = cursor->next;
        }
    }
    
    //the word doesn't exist in the dictionary
    return false;
}

// Hashes word to a number
unsigned int hash(const char *word)
{
    
    int bucket;
    
    if (word[0] == 96)
    {
        if (word[1] >= 'a' && word[1] <= 'z')
        {
        bucket = word[1] - 97;
        }
        else if (word[1] >= 'A' && word[1] <= 'Z')
        {
        bucket = word[1] - 65;
        }
        else
        {
        return false;
        }
    }
    else
    {
        if (word[0] >= 'a' && word[0] <= 'z')
        {
        bucket = word[0] - 97;
        }   
        else if (word[0] >= 'A' && word[0] <= 'Z')
        {   
        bucket = word[0] - 65;
        }
        else
        {   
        return false;
        }
    }
    
    return bucket;
}

// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *fp;
    
    //open dictionary file
    fp = fopen(dictionary, "r");
   
    
    //check if file open successfully
    if (fp == NULL)
    {
        return false;
    }
    
    char line[LENGTH + 1];
    
    //read file one line at a time
    while (fscanf(fp,"%s", line) != EOF)
    {
        //allocates memory to node
        node *n = malloc(sizeof(node));
        
        if (n == NULL)
        {
            printf("Not enough memory!");
            return 1;
        }
        
        //copies the line in the dictionary to the hash table
        strcpy(n->word, line);
        n->next = NULL;
        
        int location = hash(line);
        
        if (table[location] == NULL)
        {
            table[location] = n;
        }
        else
        {
            table[location]->next = n;
        }
        
        counter++;
    }
    
    fclose(fp);
    
    return true;
}

// Returns number of words in dictionary if loaded else 0 if not yet loaded
unsigned int size()
{
    
    //load("dictionaries/small.txt");
    
    return counter;
}

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    for (int i = 0; i < N; i++)
    {
         node *cursor = table[i];
        
        while (cursor != NULL)
        {
            node *tmp = cursor;
            
            cursor = cursor->next;
            
            free(tmp);
            
        }
    
    free(cursor);
    
    }
    
    return true;
}

I tried to understand the check50 result but I can't understand how caterpillar is there if the strcasecmp should be 0 in that situation. I tried recreating dictionary file and text file with the same words to check with debug50 but it stops suddenly after a few words, not printing the whole result.

check50 result

Can someone please help me understand? I feel I'm stuck!

Thanks in advance, Ana

1

It looks like there's a major problem in load. As I read the code above, there will never be more than two nodes in any bucket. The code puts one pointer in table[x] and a second in table[x]->next. Any subsequent nodes added will only replace the address in table[x]->next. This code is not preserving the previously added nodes after the first node. It isn't properly creating a linked list.

Suggest reviewing the lectures and shorts on how to insert a node into a linked list.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • Thank you! That really helped and I learned a bit more! Just submited the exercise :) – Ana Cláudia Faria Aug 1 '20 at 14:26

You must log in to answer this question.

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