0

I'm having problems with pset5 speller where the words I load into my dictionary hash table are getting overwritten. So for example if I load "Ashley", "Britney" and "Charlie" into my dictionary, all three entries will show as "Charlie". Can anyone see where my code has gone wrong?

I have created three functions, 'hash', a hashing algorithm; 'insert', which places words into each linked list; and 'load', which identifies words and calls 'insert' to place them into the dictionary.

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

#define LENGTH 45
#define SIZE 33

typedef struct node
{
    char *name;
    struct node *next;
}
node;

typedef node* nodeptr; 

int hash(const char *str);
void load(const char *dictionary);
void insert(char *word);

nodeptr first[SIZE] = {NULL};

int main(void)
{
    char *dictionary = "dictionaries/small";
    for(int c = 0; c < SIZE; c++)
    {
        first[c] = malloc(sizeof(node));
    }
    load(dictionary);

    for(int i = 0; i < SIZE; i++)
    {
        printf("%s\n", first[i]->name);
    }
}

int hash(const char *str)
{
    int hash = 0;
    int n;
    for (int i = 0; str[i] != '\0'; i++) 
    {
        if (isalpha(str[i]))
            n = str[i] - 'a' + 1;
        else
            n = 27;

        hash = ((hash << 3) + n) % SIZE;
    }
    return hash;
}

void load(const char *dictionary)
{
    FILE* dict = fopen(dictionary, "r");

    char word[LENGTH + 1];
    int index = 0, c;
    while(c = fgetc(dict), c != EOF)
    {
        if (c != '\n')
        {
            word[index] = c;
            index++;
        }
        else
        {
            word[index] = '\0';
            index = 0;
            insert(word);
        }
    }
    if (c == EOF)
    {
        word[index] = '\0';
        insert(word);
    }
}

void insert(char *word)
{
    int h_word = hash(word);

    if (first[h_word]->name != NULL)
    {
        nodeptr tmpptr = malloc(sizeof(node));
        tmpptr->name = word;
        tmpptr->next = first[h_word];
        first[h_word] = tmpptr;
        printf("%i\t", h_word);
        printf("%s\t%p\n", first[h_word]->name, first[h_word]->next);
    }
    else
    {
        nodeptr newptr = malloc(sizeof(node));
        newptr->name = word;
        newptr->next = NULL;
        first[h_word] = newptr;
        printf("%i\t", h_word);
        printf("%s\n", first[h_word]->name);
    }
}
0

You've declared word in your node as char * (a pointer).

tmpptr->name = word; this simply points the name member to what is currently in word. So the next time update word, name will point to the same memory.

Your node should really hold a null-terminated char array that you can copy the chars into (using strcpy), rather than a pointer.

I'd suggest that you follow the 2019 Speller problem rather than the 2018 one. In the 2019 version, you are given a bit more distribution code so you don't run into this problem. Choose the hashtable version from that link.

(the 2018 versions of psets can no longer be submitted for grades)

You must log in to answer this question.

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