0

Despite memory problems to be fixed, my code compiles fine and runs but returns almost every word that it checks as mispelled. I have spent so long looking at all this now that I am worried it just become messier than it needs to be and I cannot find what I think is a very aparent fault in the programme. Can anyone advise?

// Implements a dictionary's functionality

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

unsigned int hash(const char *hash_this);
// Represents a node in a hash table
typedef struct node
{
    char word[LENGTH + 1];
    struct node *next;
}
node;
int values = 0;
// Number of buckets in hash table
const unsigned int N = 1000000;

// Hash table
node *table[N];
// Returns true if word is in dictionary, else false
bool check(const char *word)
{
    int word_length = strlen(word); 
    char low_word[word_length];
    strcpy(low_word, word);
    for (int i = 0; i < word_length; i++)
    {
        low_word[i] = word[i];
    }
    
    int hash_index = hash(low_word);

    node *cursor = table[hash_index];
    if (cursor == NULL)
    {
        return false;
    }
    while (cursor != NULL)
    {
        if (strcmp(low_word, cursor -> word) == 0)
        {
            return true;
        }
        else
        {
            cursor = cursor -> next;
        }
    }
    return false;

}

// Hashes word to a number
unsigned int hash(const char *word)
{
    unsigned long hash = 5381;
    int c;
    while ((c = toupper(*word++)))
    {
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */
    }
    return hash % N;
}

// Loads dictionary into memory, returning true if successful, else false
bool load(const char *dictionary)
{
    FILE *dict = fopen(dictionary, "r");
    if (dict == NULL)
    {
        printf("Invalid Dictionary\n");
        return false;
    }
    values = 0;
    char word[LENGTH + 1];
    while (fscanf(dict, "%s", word) != EOF)
    {

        node *newNode = malloc(sizeof(node));
        if (newNode == NULL)
        {
            return false;
        }
        char low_word[strlen(word)];
        strcpy(low_word, word);
        for (int i = 0; i < strlen(word); i++)
        {
            low_word[i] = tolower(low_word[i]);
        }
        
        strcpy(newNode -> word, low_word);
        newNode -> next = NULL;

        int hash_index = hash(low_word);

        if (table[hash_index] == NULL)
        {
             table[hash_index] = newNode;
        }

        else
        {
            newNode -> next = table[hash_index];
            table[hash_index] = newNode;
        }
        values++;
    }
    return true;
}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded
unsigned int size(void)
{
    // TODO
    return values;
}

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

    if (sizeof(table) == sizeof(node[N]))
    {
        return true;
    }

    else
    {
        return false;
    }
}
2
  • Look carefully and critically at the "low word" routine in check. What's missing? – DinoCoderSaurus Apr 13 at 11:53
  • Looks like the problem is solved, based on the new question after this one. Would one of you like to post an answer (and accept) to close out the question? ;-) – Cliff B Apr 14 at 21:38
0

Here is my answer in full. Passess all checks. Had to correct some issues with the hash function and check function but annoyingly my biggest holdup was not initialising newNode -> next = NULL.

// Implements a dictionary's functionality

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

// Represents a node in a hash table typedef struct node { char word[LENGTH + 1]; struct node *next; } node; int values = 0; // Number of buckets in hash table const unsigned int N = 100000;

// Hash table node *table[N]; // Returns true if word is in dictionary, else false bool check(const char *word) { // TODO

int word_length = strlen(word);
char low_word[word_length];
strcpy(low_word, word);


for (int i = 0; i < word_length; i++)
{
    low_word[i] = tolower(low_word[i]);
}


int hash_index = hash(low_word);


node *cursor = table[hash_index];
if (cursor == NULL)
{
    return false;

}
while (cursor != NULL)
{

    if (strcasecmp(low_word, cursor -> word) == 0)
    {

        return true;
        break;
    }
    cursor = cursor -> next;

}
return false;

}

// Hashes word to a number unsigned int hash(const char *word) { unsigned long hash = 5381; int c; while ((c = toupper(word++))) { hash = ((hash << 5) + hash) + c; / hash * 33 + c */ } return hash % N; }

// Loads dictionary into memory, returning true if successful, else false bool load(const char *dictionary) { // TODO FILE *dict = fopen(dictionary, "r"); if (dict == NULL) { printf("Invalid Dictionary\n"); return false; } values = 0; char word[LENGTH + 1]; while (fscanf(dict, "%s", word) != EOF) {

    node *newNode = malloc(sizeof(node));
    if (newNode == NULL)
    {
        return false;
    }

    strcpy(newNode -> word, word);


    int hash_index = hash(word);

    if (table[hash_index] == NULL)
    {
        newNode -> next = NULL;
        table[hash_index] = newNode;
    }
    else
    {
        newNode -> next = table[hash_index];
        table[hash_index] = newNode;
    }
    values++;
}
fclose(dict);
return true;

}

// Returns number of words in dictionary if loaded, else 0 if not yet loaded unsigned int size(void) { // TODO return values; }

// Unloads dictionary from memory, returning true if successful, else false bool unload(void) { // TODO for (int i = 0; i < N; i++) {

    node *cursor = table[i];

    while (cursor != NULL)
    {
        node *tmp = cursor;
        cursor = cursor -> next;
        free(tmp);
    }
}
return true;

}

You must log in to answer this question.

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