0

could you please teach me how to make sure if i load the dictionary successfully. when i run check, no word misspelled.. Thank you.

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

node* root=NULL;
// Returns true if word is in dictionary else false
bool check(const char *word)
{

// TODO
int j=0;
int k;
 for (k=0;k <= strlen(word) +2;k++)
   {
     for (node *travs=root;travs!=NULL;travs=travs->children[j])
              {

            if(isalpha(word[k]) || word[k]=='\'')
                     {
                      j=tolower(word[k])-'a';
                         if(j==-58)
                                {
                                 j=26;
                                 }

  if (travs->children[j]==NULL)
     {
        return false;

     }



    else if (travs->children[j]!=NULL)
    {

        travs=travs->children[j];
    }

   } //end of if(isalpha(letter) || letter=='\'' )

   }//end of (node *travs=root;travs!=NULL;travs=travs->children[j])

   if(word[k]=='\0')
    {
      for (node *travs=root;travs!=NULL;travs=travs->children[j])
          if (travs->is_word==true)
             {
                 return true;
                 k=0;
            }
     }

   }// end of for (k=0;k<strlen(word),k++)

  return false;

}


bool load(const char *dictionary)
{
// TODO
root = calloc(1, sizeof(node));

  FILE *inptr=fopen(dictionary,"r");
   int i=0; //for children[i]
  if(inptr==NULL)
  {
  printf("Error opening file");
  return 0;
  }
   char letter='\0';
   while (true)
  {
  letter=fgetc(inptr);

  if (letter==EOF)
  {
      break;
  }

   for (node *ptr=root; ptr != NULL; ptr=ptr->children[i])
{

if(isalpha(letter) || letter=='\'' )
  {
   i = tolower(letter) - 'a';
    if (i==-58) //ASCII code of '\'' - 'a'
    {
     i=26;
     }

        //check children[i]’s value, if the value in children[i] is NULL, 
calloc a new node, then let children[i] point to it
   if(ptr->children[i]==NULL)
   {
     ptr->children[i] = calloc(1, sizeof(node));
     ptr=ptr->children[i];
    }

     else if (ptr->children[i]!=NULL)
    {
       ptr=ptr->children[i];

      }

     }// end of if(isalpha(letter) || letter=='\'' )
   else if(letter=='\n')
    {
        ptr-> is_word=true;
    }




   } // end of for(node *ptr=root; ptr != NULL; ptr=ptr->children[index])


} //end of while




  fclose(inptr);
   return true;

} // end of bool load(const char *dictionary)
1

Hmmm... partial analysis. To be honest, my impression is that there are multiple issues as a result of overly complex code.

There are issues in both load and check. In load, the code executes ptr-> is_word=true; twice for every word. (Hint: implement word count function to keep an eye on this.) This happens because of the way the for loop is structured. It doesn't terminate until it executes a second time to set the null condition.

Next, both load and check have a similar problem. The setup of the for loop is a serious issue. It is terminated based on a node pointer being set to NULL. That presents problems. It makes it possible for the loop to execute more times than there are letters in a word (or word plus \n). It also presents a problem when words are contained in other words, like a dictionary of "caterpillar, cater, cat, cate", etc.

Because of this, I decided to stop chasing it after a while. My recommendation is to redesign both load and check. Make the code dependent on word lengths, the \n char, and other known factors instead of finding a null pointer, with one exception. In check, while walking the trie for a word, if a null pointer is found where a node should exist, that's not a word, so return false immediately in this case.

Remember if the code seems overly complex, then it's worth looking for a simpler way. In this case, the for loops can be simplified. Also, the EOF check in load can be integrated into a loop design (is a for loop or a while loop better here?) and the code can be simplified even more.

If this answers your question, please click on the check mark to accept. Let's keep up on forum maintenance. ;-)

1
  • i redesign both load and check per this answer (make the code dependent on word lengths and \n char). It works on small dictionary but not works in large dictionary. i will try to see if i can find a way to fix it. Thank you for your analysis very much.
    – user21342
    Apr 8 '18 at 12:59

You must log in to answer this question.

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