0

Currently I am working on the load function using a hash table with singly-linked list. I have tested the create(), insert(), and find() function in a separate file and they work as expected.

Whenever I add a word to nodeBucket[index] and print out the last node added the value is correct. However, after iterating through every line in the dictionary file, all the nodes of nodeBucket[index] holds the last word "Zymurgy".

Global Variable and Typedef:

typedef struct sllist {
        char *word;
        struct sllist* next;
    }
    sllnode;

sllnode* nodeBucket[26];

Main function:

char line[128];
// iterates over each line to obtain each word
while (fgets(line, 128, dictionaryFile))
{

    // get index the word belongs to through hash function (a is 0, b is 1, c is 2 etc...)
    int index = getHashIndex(line);

    if (nodeBucket[index] == NULL)
    {
        nodeBucket[index] = create(line);
    } else
    {
        insert(&nodeBucket[index], line);
        // prints the last word added to nodeBucket[index]
        // this happens to print the correct words
        printf("%s\n", nodeBucket[index] -> word);
    }
}

// both print statements end up printing out "zymurgy"

// prints out all elements of nodeBucket[1]
find(nodeBucket[1], "aaaaaaaaa");

// prints out last word inserted into nodeBucket[1]
printf("%s\n", nodeBucket[1] -> word);

create function (tested to be working)

sllnode* create(char *word)
{
    sllnode *list = malloc(sizeof(char) * (strlen(word) + 1) + sizeof(struct sllist*));
    list -> word = word;
    list-> next = NULL;
    return list;
}

insert function (also tested to be working)

void insert(sllnode **head, char *word)
{
    sllnode *item = create(word);
    item -> next = *head;
    *head = item;
}
0

Let's take a look at the create function. The address of the word being processed is passed to create(), and the function is processed, including the following two lines:

sllnode *list = malloc(sizeof(char) * (strlen(word) + 1) + sizeof(struct sllist*));

list -> word = word;

The first line allocates space for the word plus space for the structure. Next, the address that was passed is assigned to list->word. The problem is that the address points to line[], not to the space that was just allocated.

For each word processed, every tree node points to the line char array. The line array is overwritten with every processed word from the dictionary. The space allocated for each new word in the node is simply left unused.

Remember, the malloc will allocate that space, but it can only be accessed using the structure of the struct declaration. That means that the first chunk of space goes to a pointer called word, followed by a pointer to next. Any remaining space that was allocated will sit unused, unless you get creative with code. If you do get creative though, it will be ugly, and definitely not any kind of best practice. I could explain how you could do it, but I wouldn't want to teach how to do something that shouldn't be done.

If you want to use that logic in the create function, there would need to be two malloc calls. First, one call to create a node, and then a second call to assign the address of the space for word to list->word.

Having said that, wouldn't it be simpler to use a char array in the struct of sufficient length instead of a pointer followed by an extra malloc call?

Finally, a strcpy() call would still be needed for either method to add the actual word to the new node.

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

| improve this answer | |

You must log in to answer this question.

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