I'm having a really hard time with pset5.. I think I 'vaguely' understand the flow from the walkthrough, but it's really difficult for me to implement it in code..

I tried to 'collage' every element that could get / think of here. Could anybody please let me know if this makes sense? I know it's a very vague question, but it would be great to know if at least the order/flow is going okay.

It's not even syntactically correct yet, as it prompts 'function definition is not allowed here' error message for my hash function. I tried to declare that function in dictionary.h but still doesn't work..

Any advice would be appreciated.

bool load(const char *dictionary)
FILE* dic = fopen(dictionary, "r");
int index = 0;
int word_count = 0;
char word[LENGTH + 1];

// declare a node structure
typedef struct node
    char word[LENGTH + 1];
    struct node *next;

node *hash_table[26];

if (dic == NULL){
    printf("cannot open dictionary file\n");
    return false;
// define a hash function

// scan dictionary word by word
while (fscanf(dic, "%s", word) != EOF)
        node *new_node = malloc(sizeof(node));
        if (new_node == NULL)
            printf("cannot allocate memory for a new node when loading dictionary\n");
            return false;


        // copy word into node
        strcpy(new_node->word, word);

        // hash your words: Inserting word into hash array, and linked lists
    int hash_function(char* word)
        // hash on first letter of string
        new_node->word = toupper(word[0] - 'A');
        char* index;
        index = new_node->word % 26;

        // inserting.. taking that word to a linked list]
        new_node->next = hash_table[index];
        hash_table[index] = new_node;
    return true;
return false;

1 Answer 1


I'll try and offer a couple of comments, but know that I'm probably on a similar level with you, so take my suggestions with a healthy dose of skepticism. I also chose to implement the tries data structure, which means i haven't had a chance to test out any of the ideas you're using myself or watch any of the walkthroughs with zamyla for those parts. Anyway, I hope this is useful:

1) Declaration/Definition of the hash function needs to occur outside of load(). Put a function prototype at the top of the code (perhaps somewhere after you're typedef lines) - i.e.

int hashfunction(char* word); 

and then define what the code does somewhere after load(). When you call hashfunction in load(), the call might look something like this:

int hashval = hashfunction(char* word);

That way, you're storing the integer returned by hashfunction in a variable that you can then use later on. Currently, i'm pretty sure you're just causing the compiler to complain about an implicit function declaration.

2) I am worried about the way you're trying to access/store the first character of of your word. Specifically, the line of code that bugs me is:

new_node->word = toupper(word[0] - 'A');

Here, you're saying "in the object 'new_node', there is a field/property called word, where i want you to save the result of this calculation: subtract 'A' from the first letter and then capitalize the result". I think the first and obvious negative result is that you're not saving the word you wanted to save in the first place. Presumably, you want to save the word in the field/property 'word' so that later, in check, you can see if that word is in your dictionary. Instead, at best you're saving just one letter (the first), and probably miscalculating it as you try. The left half of this equation should probably just be a temporary variable that can be overwritten in the next loop. e.g.

char c = toupper(yadayada);

The second problem here is in the character arithmetic inside toupper: consider the case that the first letter of word is 'a'. In the ascii table, the decimal representation of 'a' is 97. Now subtract 'A' from 'a' --> result = 'a' - 'A' = 97 - 65 = 32. 32 in the ascii table is a space. You can compile and run the following code to confirm this for yourself:

#include <stdio.h>
int main(void)
    char a = 'a';
    char b = 'A';
    printf("%c  %i\n", a-b, a-b);  //print the result of a-b as a character
                                   //and then as an integer

So in this case, you're calling toupper() on a space, which will just return the space itself since its not part of the regular alphabet. If you want to keep doing you're uppercase system, then you're toupper() call should look more like this

char c = toupper(word[0]) - 'A';

the third problem here is about efficiency: If you look at the 'large' and 'small' dictionaries, you'll see that all the words are lowercase. Why are you trying to force them to be uppercase? It just results in more work for your program. Now consider the inputs (daffodils.txt or austinpowers.txt), they'll have some words that are uppercase, but the vast majority will be lowercase, right? Then why don't you leave the words lowercase, and as a result hope to have to call a the function less frequently?

3) I think you're making a mistake when you're trying to compute you're index. We know we have 26 letters in the alphabet (a-z), and have to allow for the '\'' (apostrophe character). So why not this?

int index = (word[0] - 'a') % 27;

now (assuming the words in the dictionary are uniformly distributed across the alphabet) I should get an evenly spread hash table.

4) I'm super uncertain about everything that has to do with malloc and its accompanying functions, but I'm pretty sure you shouldn't be calling free yet. Free will be called for every node, but not in the load function. If you call free(new_node) now, you'll have done all this work to store a word in new_node, and place new node in your hash table, and then say to yourself 'fuck it, i don't need to know where new_node is' and forget it. Don't call free() until you're certain you'll never need the attached data again (and you still need it for when you implement 'check')

5) Just realized here at the end, that you made the same mistake when creating the hash table in the first place. I think (and like i said, i didn't see the walkthroughs on this stuff) there should be 27 pointers altogether. Also, after declaring the hashtable for the first time, you should iterate over it and set all the pointers to NULL in order to prevent things from going sideways later (and help yourself when implementing 'check' and 'unload').

It seems i've written more than I intended. I hope you find this helpful and good luck!


You must log in to answer this question.

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