Vfrdtyky

I am new to C programming. I am trying to do the pset5 in CS50 while trying to understand the concepts of memory, linked list and hashtable. I wrote the code and it compiled but there seems to be something wrong because every time I tried to execute the code it returns some garbage value. Could anyone please help me with that? Many thanks.

#include<stdio.h>

#include<stdlib.h>

#include<ctype.h>

#include<string.h>



#include "dictionary.h"



#define DICTIONARY "dictionaries/small"



typedef struct node

{

char WORD[LENGTH + 1];

struct node *next;

}

node;



int hash(char *word);



int main(void)

{

node **HASHTABLE = malloc(sizeof(node) * 26);



//open the dictionary

FILE *dic = fopen(DICTIONARY, "r");

if (dic == NULL)

{

    fprintf(stderr, "Could not open the libraryn");

    return 1;

}



int index = 0;

char word[LENGTH + 1];



for (int c = fgetc(dic); c != EOF; c = fgetc(dic))

{

    word[index] = c;

    index++;



    if (c == 'n')

    {

        int table = hash(word);

        printf("%dn", table);

        //create a newnode

        node *newnode = malloc(sizeof(node));

        strcpy(newnode->WORD, word);

        newnode->next = NULL;



        printf("Node: %sn", newnode->WORD);

        index = 0;



        //add new node to hash table

        if (HASHTABLE[table] == NULL)

        {

            HASHTABLE[table] = newnode;

        }

        else

        {

            HASHTABLE[table]->next = newnode;

        }

    }

}

for(int i = 0; i < 26; i++)

{

    node *p = HASHTABLE[i];

    while (p != NULL)

    {

        printf("%s", p->WORD);

        p = p->next;

    }

}



//free memory

for(int i = 0; i < 26; i++)

{

    node *p = HASHTABLE[i];

    while (p != NULL)

    {

        node *temp = p->next;

        free(p);

        p = temp;

    }

}

free(HASHTABLE);

}





int hash(char *word)

{

int i = 0;

if (islower(word[0]))

    return i = word[0] - 'a';

if (isupper(word[0]))

    return i = word[0] - 'A';

return 0;

}

Your code has serious problems that result in undefined behavior.

Two of them are the result of this line:

node **HASHTABLE = malloc(sizeof(node) * 26);

That allocates 26 node structures, but the HASHTABLE variable expects the address of a pointer to an array of node * pointers (that's the ** in the node **HASHTABLE declaration).

So, you should replace it with something like:

node **HASHTABLE = malloc( 26 * sizeof( *HASHTABLE ) );

Note that I used the dereferenced value of the variable being assigned to - HASHTABLE. This means in this case a node (one less * than in the declaration). So if the type of HASHTABLE changes, you don't need to make any other changes to the malloc() statement.

That problem, while technically undefined behavior, likely wouldn't cause any problems.

However, there's still a problem with

node **HASHTABLE = malloc( 26 * sizeof( *HASHTABLE ) );

that will cause problems - and serious ones.

That array of 26 pointers isn't initialized - you don't know what's in them. They can point anywhere. So this won't work well, if at all:

    if (HASHTABLE[table] == NULL)

Meaning this points off to somewhere unknown:

    HASHTABLE[table]->next = newnode;

And that will cause all kinds of problems.

The simplest fix? Initialize the values all to zero by using calloc() instead of malloc():

node **HASHTABLE = calloc( 26, sizeof( *HASHTABLE ) );

Until that's fixed, any results from your entire program are questionable, at best.

The reason for the garbage is that you didn't null-terminate the string:

strcpy(newnode->WORD, word);

strcpy expects the src to point to a null-terminated string. Simply adding 0 at the end. Simply terminate it with

word[index] = 0;

before the strcpy.

Other than that, the ones in Andrew Henle's answer should be addressed too, but I am not going to repeat them here.

BTW, next you will notice that

HASHTABLE[table]->next = newnode;

wouldn't work properly - that code always inserts the node as the 2nd one. But you want to always insert the new node unconditionally as the head, with

newnode->next = HASHTABLE[table];

HASHTABLE[table] = newnode;

There need not be any special condition for inserting the first node to a bucket.