Hot answers tagged

9

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 inside of main or another function. It's the = malloc(...) part that's killing you here. You can't do that outside of main or another function. If this answers ...


6

Should I declare freenodes in the header file? It is not necessary to declare freenodes in the header file. However because freenodes is written after the function which calls it, it should be declared at the top of the .c file, like so: void freenodes(node* path); This is the same as the function signature used to define the function itself, with the ...


6

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 pointer that actually points to, well, the literal root of the trie. It's critical that you never reassign this pointer. If you do, you'll lose the root of the ...


3

for (int i = 0; i < 26; i++) You have 27 elements (a-z and '), so <=26 or <27 would be appropriate.


3

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 calculating a. Instead of if(tmp->is_word==true) return true; else return false; just do return tmp->is_word; load: Be ...


3

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. Whenever you malloc, don't forget to initialise the structure.


3

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 potentially point at up to 26 nodes, but let's keep it simple. Say that you have to build a trie with 3 words, "am", "at", and "ad". When the trie is finished, ...


2

@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 clean up and be tidy, but it should not affect how your function works. If you get a double free error by commenting out the line that sets the freed pointer to ...


2

You've got the basic concept started, but the logic has some problems. First and foremost, look at int k = word[i] - '\''; This statement subtracts decimal 39 from the letter. Yes, you can do math on chars like this, but there's a problem. It will sorta work for "A", but will blow up for any other letter, upper or lower case. Let's take "B" as an example. ...


2

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 wanted to be more technical, you would say each node's link member, points to the next node, not the node itself, because a node has two members. A value and a ...


2

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 the number of words in the given dictionary per the specs, but our program should allow loading custom dictionaries). as a result, we would have to ...


2

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 your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)


2

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 each node in turn. In your case, you are going down to the final children[i] then freeing spider, you're not going back up the tree.


2

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 level into the tree, as in root->children[0] before setting that node's is_word to true. (a two letter word, like ad, would traverse the path of root->...


2

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 function, or as a global variable. Then a second variable is created with the same name, but will have local scope because it's within a set of curly braces ...


2

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 file after you've failed to read something. So it has to be placed after a read operation, not before. check should not open any files. It should use the ...


2

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: for(int i = 0; i < 27; i++) { if(x->children[i] != NULL) { x = x->children[i]; NULL_search_and_free(x); } } Now, say that ...


2

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 node is not null, it will go on to process it's children, doing the same thing. BUT, on return, the node isn't freed. In other words, nothing is ever freed. ...


2

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, failing for larger ones. Bloom filter is interesting, I'm just not convinced it will help, as you still would have to verify your "positives". And for the large ...


1

What Zamyla meant, is that you need to inspect the value stored in children[i], and perform some action depending on whether the value is NULL. Basically this equates to an if statement: if (children[i] == NULL) { // children[i] does not point to anything } else { // children[i] points to something } Also the example implies that the children ...


1

Here's a big red flag. The following line is near the bottom of the check() function. next_node -> is_word = true; In every dictionary word that it checks, it will set is_word to true for every letter that it moves across in the trie. The check function should not make any changes in the trie, it should only read the trie data. It looks like that ...


1

1) fgetc will return each character as it appears in the file. Are you sure that the words in the text file are null terminated? (i don't think they are, not unless something changed a lot in the text file from last year's). If they aren't, your tempPtr never goes back to root, and what you'll end up having is a very, very long series of pointers that start ...


1

It seems you forgot to initialize your children array to NULL, which is why GDB shows you a segfault occurring there. While you're at it, you might want to initialize is_word to false as well. Finally, and this is just a matter of good coding practice, you might also want to have error handling each time you malloc, just to make sure malloc!=null. Also, it's ...


1

I see several problems. First, look at this: if (c == '\'' && c !='\n') The only time this will ever be true is when you see an apostrophe. No letter will ever get past this. Perhaps you meant to type c != '\''? Now, tempPtr->children[c-'a'] = NULL; What happens if c is a capital letter? You end up with a negative number for the index of ...


1

Yes, the dictionary file is expected to be a file that contains a sorted list of words, one per line. Your mission is, indeed, to create in the LOAD function, code that will take those words and insert them into a tree or trie in memory so that you can check words from a test file against them later. LOAD will either take a command line parameter that ...


1

Figured it out! The problem was on dictionary.c:179. I replaced return freeMem(pntr->next[i]) with freeMem(pntr->next[i]) and now valgrind is happy!


1

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. Unfortunately, by adding the asterisk in the sizeof() call, you are allocating just enough memory to store a pointer to a node, not an actual node, which is much larger. ...


1

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 possible that check50 is using inputs that will reveal an error that your testing doesn't. Having said that, since every test is showing the seg fault, I'm ...


1

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 question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)


1

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 cat and caterpillar. Because it doesn't make the check, it would accept caterp as a word. The code doesn't handle apostrophes. It gets by because, ...


Only top voted, non community-wiki answers of a minimum length are eligible