0

I spent a huge amount of time on this pset but I still cannot make the program handle even the basic words properly. When I test the program with "austinpowers.txt", it returns 19190 words mispelled out of 19190 in the text. It returns also an enormous number of words in DICTIONARY as well - 1439228 which makes me think that the problem starts with load and then maybe gets worse somewhere in check. You tell me, here is the relevant code:

At the top:

     typedef struct node
{
   bool is_word;
   struct node* children[27];

}
node;


node* root =NULL;
node* tempPtr = NULL;


int dictionary_size=0;
FILE* dict;

The check function:

    bool check(const char* word)
    {
int cletter;
int position;

node* crawler = root;

int n;

for (int i = 0; n=strlen(word), i<=n; i++)
{
   cletter = word[i];

  if(isalpha(cletter)|| cletter=='\'')
   {

       position = tolower(cletter)-'a';

      if (crawler->children[position] == NULL)
      { 

         return false;
         break;


       }
      else if (crawler->children[position] !=NULL)
      {
        crawler= crawler->children[position];

      }
   }

   else if(cletter=='\0')
   {

      if(crawler->is_word==true)
      {

          return true;
          break;

      }
      else if(crawler->is_word != true)
      {

         return false;
         break;
      }

   }

 }

  return false;  

}

And the load function:

    bool load(const char* dictionary)
   {  
   root=(struct node*)malloc(sizeof(node));

for (int i = 0; i < 27; i++)
{

   root->children[i]=NULL;

}

tempPtr=(struct node*)malloc(sizeof(node));
tempPtr = root;
for (int j = 0; j<27; j++)
{
    tempPtr->children[j]=NULL;

}

tempPtr=root;

dict = fopen(dictionary, "r"); 

if (dict==NULL)
{
   printf("Error, unable to open file\n");
   return false;

}

//for every word from the dictionary iterate over the trie
for (int c = fgetc(dict); c != EOF; c = fgetc(dict))
{

   // allow only alphabetical characters and apostrophes
   if (letter == '\'' || isalpha(letter))

    {  
         letter = tolower(c);
         if (tempPtr->children[letter - 'a']==NULL)

        { 

            tempPtr->children[letter-'a']=(struct node*)malloc(sizeof(node));

        //then continue
        }

       tempPtr=tempPtr->children[letter-'a'];

    }

   //if at the end of the word, set is_word to true
   else if(letter=='\0') 
   {
        tempPtr->is_word=true; 
        dictionary_size++;
        tempPtr=root;

   }

}

return true;

}

Thanks in advance! I've spent a week on this problem set and once I fix one problem, another pops out. Whenever I change something on the code above, I get segmentation faults so this is the closest I got to making the code compile and run without throwing an error. However, it's still far from working the way it's supposed to.

UPDATE

Ok, so I changed the for-loop and the if-conditions to that:

    for (int c = fgetc(dict); c != EOF; c = fgetc(dict))
    {
      if(c=='\'' || isalpha(c)
       {
          letter=tolower(c);

          //then follows the rest

Not sure this is the best way to do it but it works. In addition, I made some other changes (thanks to @Irene suggestions and many, many hours tweaking with the code) and now the program passes all the requirements in check50. It has some memory leaks but this is a question for another topic :)

As I mentioned above, this problem set took me the longest time so far. I think I must have spent 10% of my time actually writing the code and 90% debugging it. I think it's also because the topic was completely novel to me. It worked well in the end. The general conclusion is that if you spend enough time and efforts on something (like debugging...), it will give the result you were looking for ;)

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 from the very first used place in root.

2) You're not considering the apostrophe correctly (both in check and load). What is its ASCII value? What happens if you subtract 'a' from it?

3) This section of code:

tempPtr=(struct node*)malloc(sizeof(node));
tempPtr = root;
for (int j = 0; j<27; j++)
{
    tempPtr->children[j]=NULL;

}

tempPtr=root;

You malloc a block of memory, you assign it to tempPtr (why?). Then you reassign the pointer to root, therefore losing the malloced block (memory leak right there). Then you NULL the children, which you had already done before when you NULLed root (both root and tempPtr point at the same block of memory malloced before). Then you assign the tempPtr to root, this has no effect. None of these should affect how the program works, but the memory leak should be avoided (the question is why mallocing a temporary pointer).

2
  • You're absolutely right! 1) I put "\n" instead of "\0" . While I was playing with the code to see where a seg fault was coming from, I changed it and then completely forgot I've left it that way. 2) I will show the updated apostrophe part above. I did something slightly different 3) very interesting point! I think I just don't understand completely how pointers and their initialization works. I thought every time I declare a new node I should malloc and initialize it to something to avoid seg faults. What should have I done in this case and why? Something like tempPtr=root and that's it?
    – GiP
    Nov 24 '15 at 11:53
  • GiP: To clarify a bit, with respect to the apostrophe, i'm still not sure how you're mapping it. The ASCII value for apostrophe is 39, so how exactly are you mapping it in your trie? With respect to tempPtr, exactly: doing tempPtr = root is enough. tempPtr is a temporary pointer you create to traverse the trie. It's meant to initially store the same address as root, and then move along the trie (you need it because if you moved "root" you would lose track of it). You don't need malloc because you don't need to allocate memory for it, since it's meant to just point at where root is :)
    – Irene
    Nov 24 '15 at 20:05

You must log in to answer this question.

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