1

I'm trying to use tries with pset5. Based on some error checking, it seems the newNodes I'm creating and the links between them are not carrying over from one word to the next. In other words, if the dictionary loads the word "cat", and then "caterpillar", it seems to be creating new nodes for the "a" and the "t" all over again. I can't figure out why.

Here is my code. Thanks in advance for any advice you can offer. Also, I know I haven't accounted for apostrophes yet. I want to get the code working and then I'll integrate apostrophes.

/**
* dictionary.c
*
* Computer Science 50
* Problem Set 5
*
* Implements a dictionary's functionality.
*/

#include <cs50.h>
#include <ctype.h>
#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
#include <string.h>

#include "dictionary.h"

/* in dictionary.h
*
*
typedef struct node
{
   bool is_word;
   struct node* next[26];
}
node;
*/


// hashed number
int h_num;

node* root = NULL;


/**
* Loads dictionary into memory.  Returns true if successful else false.
*/
bool load(const char* dictionary)
{
// open dictionary "d" for reading
FILE* d = fopen(dictionary, "r");

// Error checking
if (d == NULL)
{
    printf("Could not load dictionary.\n");
    return false;
}

root = malloc(sizeof(node));

for (int j = 0; j < 26; j++)
{
    node* child = calloc(1, sizeof(node));
    root->next[j] = child;
}

while (!feof(d))
{
    // array to hold the words of the text file
    char str[LENGTH + 1];

    // read the word
    fscanf(d, "%s", str);

    // keep track of strlen so you know when to change is_word to true
    int wordlen = strlen(str);

    // this int will iterate through the chars in the str
    int i = 0;

    // number to determine alphabetic index of pointer
    h_num = str[i] - 'a';

    // for moving from node to node
    node* trav = root;

    // if node has already been created, jump to furthest down node already created
    while (trav->next[h_num] != NULL)
    {
        // using this formula again so it can reset each time the node jumps
        int h_num = str[i] - 'a';

        // trav node jumps to next node
        trav = trav->next[h_num];

        if (i + 1 == wordlen)
        {
            trav->is_word = true;
        }

        i++;
        printf("preexisting node\n"); // error checking
    }

    // create new nodes for remainder of word
    while (i < wordlen)
    {
        int h_num = str[i] - 'a';
        node* newNode = malloc(sizeof(node));
        trav->next[h_num] = newNode;
        trav = newNode;
        printf("created node\n"); // error checking

        if (i + 1 == wordlen)
        {
            trav->is_word = true;
            printf("word\n"); // error checking
        }

        i++;
    }
    total++;
}

fclose(d);    
return true;
}
Improve this question
0

1 Answer 1

Reset to default
1

Look at your condition in your second while loop. Why would it not create a node? 

while (i < wordlen)

After iterating through the first word 'cat', it start iterating over 'caterpillar'. The condition in the first while loop checks if trav->next[h_num] is not null. Then you set trav to trav->next[h_num] and increment to the letter 'a' in caterpillar. Look at what your second while loop does after i++.

Improve this answer
5
  • Thank you for your response, however I still don't see it. The way I'm reading it, trav should move through the nodes so long as the pointer points to a node (rather than to NULL). It checks whether a pointer points to a node, then if it does, trav becomes that pointed-to node and repeats. When it eventually detects a pointer to a node is NULL (hasn't yet been created), the program jumps to the "while (i < wordlen)" condition and begins creating new nodes char by char until the word is complete. Why would it not be doing that?
    – Scott
    Sep 5, 2016 at 20:33
  • 1
    Correct. But your loop, however, checks for Not null. In other words, where in your code are you saying that if the pointer is Null then create a new node? Your second loop just says if I is less than wordlen create a node.
    – Darc Nawg
    Sep 5, 2016 at 20:53
  • Still not getting it but thank you for trying. I guess I'm having trouble because, as I see it, my second loop is contingent on the program exiting the first loop, whose condition is != null; thus the second loop shouldn't need to specify "if pointer ==null create a new node" since it's exited the previous condition and the pointers would by default then ==null, no? I just need to keep creating new, linked nodes until the end of the word, no?.. What should my second while condition be? Can I work off this code or do I need to rework my while conditions more or less from scratch? Any advice?
    – Scott
    Sep 5, 2016 at 22:23
  • You certainly can work with what you've written. If you look at it say after the nodes for 'cat' have been added. The first loop does correctly on the character 'c' in 'caterpillar'. It sees that the pointer for that node trav->next[h_num] is not null. Then it sets trav to trav->next[h_num] effectively making trav->next[h_num] null. Then the first loop is done, which is probably not what you expected. The first while loop only runs on 'c' of caterpillar. So then in the second while loop, it starts making the nodes that had already been created when the first word 'cat' was added.
    – Darc Nawg
    Sep 5, 2016 at 22:56
  • Finally figured out the bug. Thank you!
    – Scott
    Sep 7, 2016 at 1:39

You must log in to answer this question.

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