9
votes
Accepted
pset5 root node defitnion (trie)
It's actually a simple fix. Since it's something that you would either know or not know, here it is. You declare the pointer variable as a global outside of a function, but you malloc space for it ...
- 68.1k
6
votes
Accepted
Pset5: Misunderstanding tries and method to assign letter to an array inside a struct
Your understanding is correct, but your example has a dangerous flaw if you were to implement it. Look back at your question as a whole. You have two important variables, root and newptr. root is the ...
- 68.1k
3
votes
Accepted
CS50 pset5 Memory Leak (trie structure)
for (int i = 0; i < 26; i++)
You have 27 elements (a-z and '), so <=26 or <27 would be appropriate.
- 20.9k
3
votes
Accepted
pset5:(speller) Check function does not correctly identify misspelled words
check:
tolower(word[i]) returns the lowercased ith character in word. You never use the value, you might want to assign it. Or remove this loop and later use tolower(word[i]) instead of word[i] when ...
- 20.9k
3
votes
Accepted
Speller(trie) / my code can't handle most basic words and substrings properly
current_node = root;
should be within your while loop, so you start at the root for every new word. Otherwise a dictionary of cat caterpillar would end up with two words, cat and catcaterpillar.
...
- 20.9k
3
votes
PSET5 speller - I cannot understand tries at all
Don't feel bad, it took me a little while to wrap my head around the concept originally. ;-)
A trie is essentially a tree representation of a bunch of words. The root of a tree and every node can ...
- 68.1k
2
votes
Accepted
how effective would it have been to use an array for the dictionary?
suppose we are to implement speller using an array instead of a hash-table or a trie.
a main problem that we have is that we don't know the number of words in the dictionary in advance (yes, we know ...
- 17.6k
2
votes
Accepted
pset5 trie: What is the boolean-data value in the root node if the dictionary has one-letter words?
The trie starts at one root node. This node will always have the is_word bool as false because the root node doesn't actually represent a letter. For a one letter word, say a, you would first move one ...
- 68.1k
2
votes
Pset5 unload trie 244 bytes lost
Your code isn't freeing recursively. It should keep on going down the tree while children[i]!=NULL, only freeing the node when that condition isn't met anymore. It then returns up the tree, freeing ...
- 1,415
2
votes
Accepted
Pset5: trie check outputs 18000 out of 19000 words in austin powers
You have a very narrow but very deep trie. Each word is supposed to start at the base of the trie. Where does the second word start loading in the trie? The third? After that? ;-)
If this answers ...
- 68.1k
2
votes
Accepted
adding data to singly linked list
When we have a SLI with five values {1, 3, 4, 6, 7}, every node points to the next one (given that it is not a double linked list) an the node containing 7 points to NULL.
Correct, even though if you ...
- 7,366
2
votes
pset 05 trie large dictionary unload issue
@SFri: I agree that it's hard to tell without seeing some code, but I'll tell you what i think can happen from the errors and the pseudocode.
The reason to set a recently freed pointer to null is to ...
- 1,677
2
votes
Accepted
PSET5 - Trie Check Segmentation Fault
It's a common problem. The problem lies in load(), where you have created a "shadow variable."
A shadow variable happens this way: First, the original variable is created, either earlier in main or a ...
- 68.1k
2
votes
Pset5 - Check not returning expected output
Please state in which way your output differs. Number of loaded words? Number of mismatches?
feof does not tell you whether you are at the end of the file. It tells you that you are at the end of the ...
- 20.9k
2
votes
Accepted
pset5 2017 unload() trie segmentation fault and undefined behavior
Couldn't do a full, in-depth analysis because I would need to see the node struct declaration and all of the involved functions. However, here's a somewhat common issue. Look at the following code:
...
- 68.1k
2
votes
Accepted
Pset5 trie unload -recursive function does not free memory
Think carefully about what the code is doing. It checks if a pointer is null, and if so, it will free that node. In other words, it will free a nonexistent node - a do nothing operation. OR, if the ...
- 68.1k
2
votes
Accepted
PSET 5 - how to use the least memory - the magic trie sauce
The people at the top of speller bigboard, to get incredibly low values in reported memory usage, use other kinds of memory than stack or heap. It requires picking a maximum dictionary size, though, ...
- 20.9k
1
vote
Accepted
pset5 load with tries, not permanently creating connections between nodes
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 ...
- 151
1
vote
Accepted
Implementing a trie. Updated load function in dictionary.c causes more problems with valgrind
I'm trying to figure out the best way to tell you this so that you can find it on your own, without just telling you where the problems lie. The good news is that the total memory leak code fix is ...
- 68.1k
1
vote
Accepted
Pset5 600 out 644 words misspelled. What am I missing?
There are two major problems with the code. First, neither load nor check are coded to handle apostrophes. Because of that, the value of index will be set at the ascii value of an apostrophe every ...
- 68.1k
1
vote
Accepted
Segmentation fault in pset 5
There are two major problems in the code. First, look at this:
node* root = (node*) malloc(sizeof(node*));
The parameter for malloc is the size of the object that needs to be allocated. ...
- 68.1k
1
vote
seg fault in pset5 check50 speller.c
check50 runs in a slightly different environment that can produce seg faults that won't show up in the IDE. However, the seg fault is showing that there's an error somewhere in the code. Also, it's ...
- 68.1k
1
vote
Accepted
Load giving segmentation fault
Your code doesn't handle apostrophes. If the dictionary file has a word with an apostrophe, the index value generated is -58, so trav->children[index] generates a seg fault.
If this answers your ...
- 68.1k
1
vote
Trie is failing in Check function
Your problem lies in what's not in the code - two oversights.
The code doesn't actually check is_word when it actually gets to the end of a word in the trie. Say that your dictionary had the words ...
- 68.1k
1
vote
Pset5: speller.c listing all checked words as misspelled
Didn't really look into the code because there's a major problem right at the beginning of check(). Look at the following:
bool check(const char* word)
{
root = malloc(sizeof(node));
As soon as ...
- 68.1k
1
vote
pset5 Dictionary issues after run check50
Also, for navigating the trie, instead of defining a new node next_node:
struct node* next_node = arrow->child[index];
you can just move the arrow pointer like so:
arrow=arrow->child[index];
...
- 1,415
1
vote
PSET5 Load (total confusion)
First, I would recommend using calloc for root node, because this one sets it to 0.
Then, in your first if statement, checking for '\n' does not necessarily mean that we are not pointing at an empty ...
- 33
1
vote
Accepted
Pset5 - Apostrophe and check problems with Tries
There are several problems. The most significant is this:
for (char* i = buffer; *i != '\n'; i++)
{
// creating a variable to store letters in
int templetter = i[j];
This code is supposed to ...
- 68.1k
1
vote
Accepted
pset5 memory leak while using a Trie
I figured out what caused the memory leak. In the helper function of unload, I would free a node if it had no children, but I forgot to set the pointer that points to that node equal to NULL. I have ...
- 11
1
vote
Pset5 - Dinamic name allocation for nodes? - Tries
Okay. It seems my knowledge on linked-lists was far from flawless. I have reviewed some of the videos and read up some more on the topic.
I'll begin with trying to put together a linked-list then ...
- 88
Only top scored, non community-wiki answers of a minimum length are eligible