I can't assign a node to a bucket in a hash table with with right assignment of pointer and word values

Question

When I assign table[index3] = n; what happens is that the value of the word receives a memory address and I can't follow table[index]->next to achieve the old n->word; This shouldn't happen.

// Implements a dictionary's functionality

#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <strings.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 = 6359;

// Hash table
node *table[N];


// Declaration of variable that counts words loaded from dictionary
int howmany = 0;

// Declararation of tmp pointer
node *tmp = NULL;

// Declaration of index used to address a bucket from a hash
unsigned int index2 = 0;
unsigned int index3 = 0;

// Declare variable key
unsigned int key = 0;

// Returns true if word is in dictionary else false
bool check(const char *word)
{
    bool checked = false;
    index2 = hash(word);
    tmp = table[index2]->next;
    while (tmp->next != NULL)
    {
        if (strcasecmp(tmp->word, word) == 0)
        {
            checked = true;
        }
        // Updates tmp to next word in list
        tmp = tmp->next;
    }
    return checked;
}


// Hashes word to a number
unsigned int hash(const char *word)
{
    // Assigns variables
    char *position = "00zyxwvutsrqponmlkjihgfedcba'";


    // Calculate a key for the word
    for (int i = 0; word[i] !='\0'; i++)
    {
        for (int j = 0; j < 29; j++)
        {
            if((int)word[i] == (int)position[j])
            {
                key = key + (int)word[i] * i * j * 31 * 7;
            }
        }
    }

    printf("key is : %i\n", key);  /////test

    // Recalculates values bigger than N
    if (key > N)
    {
        key = key % N;
    }
///  Test-----------------------------------------
    printf("Key is:  %i\n", key);

    return key;
}




// Loads dictionary into memory, returning true if successful else false
bool load(const char *dictionary)
{
    FILE *file = fopen(dictionary, "r");
    if (file == NULL)
    {
        return false;
    }


    char *word[46];


    // Load words in hash table
    while (fgets(*word, 46, file) != NULL)
    {

printf("word is: %s", *word); // test------------

        // Hash the key of a certain word and translates to an array's index
        index3 = hash(*word);

printf("index3 é : %u\n", index3); // test----------------

        // Allocate memory for a node
        node *n = malloc(sizeof(node));
        if (n == NULL)
        {
            return 1;
        }

        strcpy(n->word, *word);
        n->next = NULL;



        if (table[index3] == NULL)
        {
            table[index3] = n;

     printf("table[index3]after: %p\n", table[index3]->next);   // test
     printf("table[index3]word: %p\n", table[index3]->word);     //test

        }
        else
        {
            // Scan end of list and update with 'n'
            tmp = malloc(sizeof(node));
            tmp = table[index3]->next;

            while (tmp->next != NULL)
            {
                tmp = tmp->next;
            }
            tmp->next = n->next;
            strcpy(tmp->word, n->word);
        }



        // Updates number of words as loads each one
        howmany++;
    }



    if (howmany > 0)
    {
        return true;
    }
    else
    {

        return false;
    }

    fclose(file);
}

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

// Unloads dictionary from memory, returning true if successful else false
bool unload(void)
{
    // Declaration of temporary pointer and variable
    node *cursor = NULL;
    int is_not_null = 0;


    // Free memory for list in each bucket
    for (int i = 0; i < N; i++)
    {
        if(table[i] != NULL)
        {
        *tmp = *table[i];
        *cursor = *table[i];
        while(cursor->next != NULL)
        {
            cursor = cursor->next;
            free(tmp);
            tmp = cursor;
        }
        free(tmp);
        free(cursor);
        }
        if (table[i] != NULL)
        {
            is_not_null++;
        }
    }

printf("is_not_null: %i\n",is_not_null); //-----------teste--------------------

    // Verify if memory was freed and return a boolean value
    if(is_not_null == 0)
    {
        return true;
    }
    else
    {
        return false;
    }
}

Answer 1

Let's go through several issues.

First, probably foremost, there's this:

    char *word[46];

This creates an array of 46 pointers to chars, not a char array. C is treating everything stored in each array elemment as an 8 byte memory address, not a 1 byte char. This is messing up just about everything in the program. To fix it, remove the asterisk. Note: don't remove the asterisk from the hash signature const char *word or where making calls to hash. This is actually passing the address of the array that contains the word.

Next, the hash function is indeterminate, meaning that it doesn't generate the same key for the same word every time. The reason for this is that key is declared as a global variable. Because it's a global, it retains whatever value it is assigned throughout the execution of the program. Every time hash is called, it uses whatever key the previous usage had, not 0. Key should be declared as a local inside of hash, and inside every function that uses it. It has no need to be a global.

This is a perfect demonstration of why vars should never be declared as globals unless there's a really, really good reason for it. Globals invite subtle bugs into code and should be avoided wherever possible!!!! There's one var in this program that makes sense as a global. I'll leave it to you to figure out which one.

Next, what happens if a word has a capital letter in it? The hash for "Cat" would be different than the hash for "cat". I don't see any code to handle uppercase letters anywhere. This will be a big problem.

There's also code that works, but could be simplified. I'll leave it to you to think about where this code is and how to simplify it. ;-)

Finally, these are just some of the big things. There may be more problems, but this will get you going. If you get stumped again, please post a new question.

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