Completely stuck on LOAD in pset5 (hash-table)

Question

I do really need help on LOAD. I can not figure out what exactly is going wrong with my code and if I am on the right track or not. I would appreciate any help. Besides, I'm getting an error: "multiple definition of `hash_function'" when I try to make a shorter variable "i" which is supposed to numerate the linked lists.

Here's the code in dictionary.c:

bool load(const char* dictionary)
{

// open dictionary file
FILE *dfp = fopen(dictionary, "r");
if (dfp == NULL)
{
    printf("Could not open %s.\n", dictionary);
    unload();
    return 1;
}

while (!feof(dfp))
{
    // malloc for a new node
    node* new_node = malloc(sizeof(node));

    // read in a word to the node
    fscanf(dfp, "%s", new_node -> word);

    // hush function variables
    int i = hash_function(new_node -> word);

    // put the new node to the specified by hash-function bucket
    if (hashtable[i] == NULL)
    {
        hashtable[i] -> next = new_node;
    }
    else
    {   
        node *tmp_node = malloc(sizeof(node));
        tmp_node -> next = hashtable[i] -> next;
        hashtable[i] -> next = new_node;
    }
}

return true;
}

and here is the dictionary.h:

bool load(const char* dictionary);

// declaration of hash function
int hash_function(char *key)
{
    // hash on first letter of string
    int hash = toupper(key[0]) - 'A';
    return hash % SIZE;
}

// structure for linked lists
typedef struct node
{
    char word[LENGTH + 1];
    struct node* next;
}
node; 

// the hash table
node* hashtable[SIZE];

Answer 1

While I may or may not agree with the previous comment, none of those things will cause any issues. Your problem is here:

else
    {   
        node *tmp_node = malloc(sizeof(node));
        tmp_node -> next = hashtable[i] -> next;
        hashtable[i] -> next = new_node;
    }

So, you nave new_node-> word, which already has the word store. You now malloc a new node: tmp_node (why?). You use the "next" element of that node and you assign to that whatever is stored in hashtable[i]->next (that is, the rest of your linked list). tmp_node is local to the else block and it will go out of scope as soon as the else block exits. Nobody is pointing at it, the variable won't exist anymore, you can't access the rest of your linked list ever again.

Then you assign "new_node" to hashtable[i], which is fine, but now your hashtable will only have that one node.

What you have to do, in pseudocode would be:

1) new_node has a "next" element. Make that element point at whatever the "next" element of hashtable[i] is pointing at, so now new_node->next will point at the rest of your hashtable 2) Make hashtable[i]->next point at your new_node. Now the hashtable points at your new_node, and the new_node points at the rest.

With respect to the compilation error, it probably has something to do with the fact that you're defining your hash function inside of the .h file. Are you also defining it in the .c file? Usually, you would put only the prototype in the .h file, and the definition in the .c file.

With respect to the other comments: 1) %SIZE is fine as long as SIZE is less than the maximum possible value of word[i] - 'A'. Otherwise, it won't cause errors but it's redundant. About what you're passing to the function: you could pass the first char of the word because you only use that. Again, it won't cause errors.

2) I don't agree. Nothing wrong with assigning to next. Then in check you only ever check for "next".

3) Wrong. No reason why you would use an extra variable to store. It's ok to fscanf directly to new_node->word. I personally don't like fscanf() but the walktrhough uses it, so I guess it's fine :D

Answer 2

1. In your hash_function, why do you need to get the modulo? Also, think about what you are passing to your hash_function. Do you need a pointer argument?
2. Also, is there a need to assign a node to hashtable[i]->next if hashtable[i]==NULL? Why not just use hashtable[i]? That would be more efficient.
3. And rather than fscanf'ing a word directly into new_node->word, you'll be better off fscanf'ing it into a temporary character array buffer, and then copying it into new_node->word.