0

As the question said, my speller listed single word characters as wrong (A, a, s,...) and character that starts with letter a.

I am suspecting the check function, or the hash function that I use from the internet. But I can't see it even after 3 days straight. Can anyone point out where I am wrong? HASH is 1000, by the way.

int hash(char* hash_word)
{
    unsigned int idx = 0;
    for (int i=0, n=strlen(hash_word); i<n; i++)
        idx = (idx << 2) ^ hash_word[i];
    return idx % HASH;
}


struct node *head = NULL;
struct node *hashtable [HASH];
int count = 0;
/**
 * Returns true if word is in dictionary else false.
 */
bool check(const char *word_check)
{
    // TODO
    //char word_copy[LENGTH +1];
    // copy the content of word_check to another variable
    //memcpy(word_copy, word_check, strlen(word_check)+1);
    char* new_word = malloc((LENGTH+1) * sizeof(char));
    for (int i =0; i < strlen(word_check)+1; i++)
    {
        new_word[i] = tolower((int) word_check[i]);
    }
    int hash_check = hash(new_word);
    struct node *cursor = hashtable[hash_check];
    while(cursor->next != NULL)
    {
        if (strcmp(cursor -> word, new_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)
{
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        fprintf(stderr, "Error loading ");
        return false;
    } 
    char word[LENGTH+1];
    while(fscanf(dict, "%s", word) != EOF)
    {
        //allocate memory for a new node
        node *new_node = malloc(sizeof(node));
        int idx = hash(word);
        strcpy(new_node-> word, word);
        new_node -> next = hashtable[idx];
        //keep head as the first 
        hashtable[idx] = new_node;
        count++;

    }
    return true;
}
1
struct node *cursor = hashtable[hash_check];
while(cursor->next != NULL)

What if there is only one word in a particular bucket?

Say you are checking "a". That hashes to 97. So you've set cursor to hashtable[97]. And hashtable[97] only has one node, so hashtable[97]->word is "a" and hashtable[97]->next is NULL.

Will your loop run?

5
  • I just think that, in this speller exsercise there will not be any dictionary that only has a word in a particular character, so I didnt check for that. Still, this doesnt explain to me why all character starts with a got wrongly detected... – Ha Tran Sep 27 '17 at 9:08
  • Was it all that started with 'a'? Or all that only had one word in that hash value? When I fixed that one problem and ran your code, it worked fine for all words that I tried. – curiouskiwi Sep 27 '17 at 21:38
  • It was both actually. It detected words like "about" and "around" as misspelled same with one char words – Ha Tran Sep 28 '17 at 0:03
  • @HaTran your hash will put all one-char words into their own buckets. – curiouskiwi Sep 28 '17 at 4:07
  • I got it by using your advice. Thank you curiouskiwi – Ha Tran Sep 28 '17 at 11:32

You must log in to answer this question.

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