I made my dictionary.c for my speller program, however...

  1. it lists the whole text as mispelled

  2. check50 gives a sad face for substrings, showing that in its testing, "cat" is listed as mispelled, although it is in the dictionary.

My code : https://pastebin.com/7DDbQ1yU (note: I will clean it up once I get it to properly work)



        hashtable[i] = malloc(sizeof(node));
        hashtable[i]-> next = NULL;

makes no sense to me. Why create a node if you don't have content for it yet?

The hashtable[i] = NULL; also doesn't add much, as global variables are guaranteed to start initialised to zero (unlike function-scope variables).

Within the loop, you then replace the word stored in one of those 26 nodes, but you have at most 26 nodes with valid words (the rest of them might contain arbitrary data, as malloc doesn't specify the content of the allocated memory).

You should however malloc (or equivalent) for each new word, within the while (fscanf... loop. Something like

        node *newnode = (node*)malloc(sizeof(node));
        newnode->next = hashtable[key];
        hashtable[key] = newnode;

would install a new node at the beginning of linked list hashtable[key].

For the "clean up", notice that char is a (signed or unsigned, with the default being implementation-specific) 8-bit integer. So you can do things like

int key = tolower(word[0]) - 'a';

(gives a value of 0 to 25 if the word starts with a regular "latin" letter). In production code, you'd have to ensure this won't access array elements outside the array (if input does not start with a letter), but it's still so much shorter and more readable than your if-elseif chain.

Also, a hash table works great with a more complex hash function that not just relies on the first element, but distributes words about evenly (but reproducible!) among the lists within the hash table. With this setup, you could determine a reasonable trade-off between memory (table size) and run-time (individual linked list length). With only 26 lists, some of which are much longer than others, your code's performance on large dictionaries has room for improvement.

  • Wow! Thanks! But could you suggest me a hash function then? I couldn't find a faster one online. (On reddit, delipity's hashfunction was quite slow for me) – Ubuntu NutCracker Nov 4 '17 at 1:43
  • Any hash function hashing a variable length string is slower (I don't know the particular one you chose), but if it evenly distributes the words over a large table, you still win for larger dicts. – Blauelf Nov 4 '17 at 10:41

You must log in to answer this question.

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