1

Im having a little difficulty figuring out this, but I feel like im on the right track, but I basically want to make sure my load function at least makes sense. I've drawn it out on paper and it APPEARS to work, but im worried im messing something up array wise.

Struct Node and Array of Pointers to Nodes:

//Node Struct Definition
typedef struct node
{
    char word[LENGTH+1]; //+1 accounts for /0 (Null terminator)
    struct node *next;
}node;

node *hashtable[HASHTABLESIZE]; //Array of pointers that point to a node (struct) type

Hash Value Function:

/**
 * Hash Function: found at http://cs50.stackexchange.com/questions/19705/how-to-make-the-check-function-faster
 */
int hashValue(const char *word)
{
    unsigned int hash = 0;
    for (int i=0, n=strlen(word); i<n; i++) {
        hash = (hash << 2) ^ word[i];
    }
    return hash % HASHTABLESIZE;
}

Load Function:

/**
 * Loads dictionary into memory. Returns true if successful else false.
 */
bool load(const char *dictionary)
{
    FILE *file;
    file = fopen (dictionary, "r");
    char word[LENGTH];
    int index;

    for(int i = 0;i < HASHTABLESIZE; i++)
    {
        hashtable[i] = NULL;
    }

    while(fscanf(file, "%s", word) != EOF)
    {
      node *new_node = malloc(sizeof(node));
      if(new_node == NULL)
      {
          unload();
          return false;
      }
      strcpy(new_node->word, word);   
      index = hashValue(word);
      new_node->next = hashtable[index];
      hashtable[index] = new_node;

    }

    return false;
}

Apologies for the length, I just wanted to make sure I got everything. The portion of the video where it explains "inserting" into the linked list got me confused. Since I didn't really understand what "HEAD" was in this case, which I knew the array of pointers (of type struct node) made the most sense.

My confusion lies I think in Malloc and the array itself. From my understanding we basically have a pointer (of type struct node) that is by itself and is the only one of it's type....and it's basically switching between pointing to the "new" malloc'd memory (Which holds a node struct (containing word and node "next" pointer)), so with each new insertion it will point to whatever the root is pointing at after the insertion (until a new malloc'd memory is created).

Am I missing something here or is this correct? I need to figure out a "print" function to traverse and print all the words captured so far which would probably help me debug.

1

Have you actually tried compiling and running this? A couple of points:

  • You need to make sure the char array you use to store the word is long enough for the largest word as well as a null terminator.

  • Think about when the load() function might return true, otherwise it will always say that it can not load the dictionary, whether it has or not!

Otherwise it looks pretty good to me!

3
  • Thanks, and I have the char array set to LENGTH+1 (for the null terminator) BUT! I realize I don't have it for the WORD variable further down! Nice catch! It does compile, but I really have no way to test right now if it loaded. And Yeah im unsure of a good case for it to return true just yet....I guess if it completes reading in the file? – msmith1114 Feb 18 '17 at 23:52
  • Seems it might be a good idea to make sure the word is set to all lowercase first I would imagine before storing it (and subsequently do the same when reading in the script for spellchecking i'd imagine) – msmith1114 Feb 19 '17 at 1:19
  • 1
    Yes, if it gets to the end of the function, it will probably have loaded in the whole dictionary to memory. And I f I recall correctly, the spec says that you can assume all words in the dictionary are already lower case, so no need to check. – Steve Bunting Feb 19 '17 at 6:06

You must log in to answer this question.

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