Error HERE, Little mistake when adding in Tree

Hi experts
here is my problem
my code works
i can search and evrything
the only thing is when i add into the tree, it dosent had evrything, i miss sometimes a word, or a first letter. Copy this code, creat a "dict.txt" file, add some words in it, one per line and see what it does.
let me know if u can help, any suggestion are good
thx.

code ;

#include "stdafx.h"
#include <iostream>
#include <stdlib.h>
#include <string>
#include <fstream>
#include <stdio.h>
using namespace std ;



class Dictio {
private:
 Dictio * a[26];
 bool FlagEndWord;
public:
  Dictio();
  ~Dictio();

  // This function follow from the current node
  // the letters given by word. The word is assumed
  // to be len characters.
  // On output plen will have the length of characters
  // leading to the returned entry.
  // The function searches from the given node
  // for a continuation using the first letter of
  // word and so on until it either find a complete
  // plen == len on output it means the whole word
  // has been read to reach the returned node, otherwise
  // the search stopped at some node because there is
  // no continuation present for the given leters.
  // len == plen and returned node has FlagEndWord
  // it means the input word was in the dictionary and
  // is a complete word.
  // if len == plen but the returned node do not have
  // FlagEndWord it means the 'word' contains a valid
  // prefix but is not in itself a complete word.
  // iF plen < len then not all the characters in word
  // could be followed because the word is not in the
  // dictionary, the plen indicate how many letters make
  // up a prefix that IS in the dictionary.
  // The functions VerifyWord and VerifyList can easily
  // be implemented in terms of this function.
  // also, insertion into the dictionary can be made
  // using this function as this function return the
  // leaf node that represent a prefix.
  Dictio * follow(const char * word, // the word
                  int len, // length of word
                  int & plen); // OUT: Length of prefix.

  bool IsFullWord() const { return FlagEndWord; }
 

  static void InsertDictionary(const char * word, int len);
  void print_words_r(ostream & os, char buf[], int n, char base);
};

Dictio * root = new Dictio;

bool VerifyWord(const char * word, int len)
{
  int plen;
  Dictio * n = root -> follow(word,len,plen);
  return (plen == len && n -> IsFullWord());
}



void Dictio::InsertDictionary(const char * word, int len)
{
int plen;
Dictio * n = root -> follow(word,len,plen);

/*
 Follow is a function that tries to find a node that represent the longest prefix found in the tree.
 If "pre" is stored in the tree and you do
 Dictio * n = follow("prefix",6,plen);

 n will be the node representing the 'e' of "pre". plen will have the value 3 indicating that the length of this prefix is of length 3.

The function follow never inserts new node in the tree but tries to follow the nodes as long as it find a valid continuation.

 It follows that if n != 0 (it should always be) and
 plen == len then the node represent the full word.
*/

if (plen == len) {
   /* Here we know that the node n represent the full
      word so we just set FlagEndWord to true.
      The word is complete.
    */
   n -> FlagEndWord = true;
   return;
}
/* Here we know that the prefix was incomplete, since
   we want to insert this word that means we have to
   insert nodes for the missing letters after the prefix.
 */
// need to add more nodes to the tree.
do {
   char c = word[plen++];
   /* The next char is c and so we need to add a node
      for c. */
   if (c >= 'A' && c <= 'Z')
     c = c - 'A' + 'a'; /* Uppercase letter, convert to lowercase */
   if (c < 'a' || c > 'z') {
      /* Not a letter! You should probably throw an
         error here instead of simply returning */
      return;
   }
 Dictio * & next = n -> a[c - 'a'];
   if (next != 0) {
      /* Here it says that the next node is non-zero
         but this indicates that follow didn't go as
         far as it could, so we have an internal error.
         This should definitely throw an exception */
      // follow() didn't do what it's supposed to do.
      // fatal error, throw error or something if you
      // want here.
      return;
   }
   /* Add the new node and continue */
   next = n = new Dictio;
} while (plen < len);
 /* The new word is complete, however, I see a bug here,
    FlagEndWord should be set since we have a complete
    word */
 n -> FlagEndWord = true; /* NEW FIX NEW FIX */
}






// read the file and add words to dictionary.
void AppendDictionary(const char * file)
{
 
      ifstream f(file);
  char buf[100];

  // each line is one word.
  while (f.getline(buf,sizeof(buf),'\n')) {
     
        // skip the newline at end of line if any.
     f.ignore(1024,'\n');

     Dictio::InsertDictionary(buf,strlen(buf));
  }
}

Dictio * Dictio::follow(const char * word, int len, int & plen)
{
int x = 0;

Dictio * n = this;
/* To start with we set n to this, so we start from
   current node */

while (x < len) {
   char c = word[x++];
   /* Pick up the next character to insepct */
   if (c >= 'A' && c <= 'Z')
      c = c - 'A' + 'a';
   if (c < 'a' || c > 'z') {
      // again not a legal letter....
      break;
   }
   Dictio * & next = n -> a[c - 'a'];
   if (next == 0) {
      // continuation not in dictionary.
      /* We have run out of nodes to follow so we return
         the last node we saw (n). This is the node
         which we will append new nodes to if we want to
         insert the word */
       
      break;
   }
   n = next;
}
/* plen is the prefix we have followed so far, the value
   is such that 0 <= plen <= x and if plen == x then
   the word is in the dictionary already - possibly not as
   a separate word but the word is in the dictionary.
   for example if the word "prefix" is in the dictionary
   then we have "pre" in - perhaps not as separate word
   but it is there and that is what we return, so
   follow("pre",3,plen) will return with the node for
   'pre' and a plen value of 3.
*/

plen = x;
return n;
}


Dictio::Dictio()
{
  for (int i = 0; i < 26; ++i)
     a[i] = 0;
  FlagEndWord = false;
}

Dictio::~Dictio()
{
  for (int i = 0; i < 26; ++i)
     delete a[i];
}


void Dictio::print_words_r(ostream & os, char buf[], int n, char base)
{
 // os is ostream to print out the words to.
 // buf[0..n-1] holds the first initial characters of word.
 // n is length of initial prefix.
 // base is 'a' or 'A' depending on upper/lowercase output.
 if (FlagEndWord) {
    buf[n] = '\0'; // terminating null byte.
    os << buf << endl;
 }
 for (int i = 0; i < 26; ++i) {
    if (a[i] != 0) {
       buf[n] = base + i;
       a[i] -> print_words_r(os,buf,n+1,'a');
    }
 }

}

void print_words(ostream & os)
{
  char buf[256];
  root -> print_words_r(os,buf,0,'A');
}


int main()
{
  string prefix;
  Dictio D;
 


      AppendDictionary("dict.txt");
   

 string TypeWord ;
 int plen ;
bool fin;
fin = false;
int choix ;


      do
      {

            
            
             cout<< " Choice \n";
             cout<< " 1 : Print Words \n" ;
             cout<< " 2 : Fin a Word \n" ;
             cout<< " 3: Quit \n";
             cin >> choix;
            
             
             
             if (choix == 1)
            {
                  print_words(cout); //print the words.
                  
            }
             
            
            if (choix == 2)
            {
                  int plen ;
                  cout << " Type a Word to Find \n" ;
            cin >> TypeWord;
            plen = TypeWord.length();
                  
            
                  if(VerifyWord(TypeWord.c_str(), plen))
                  {
                  
                  cout << TypeWord << " is in tree ";
                  }
                  
                  else
                  {
                  cout << TypeWord << " is not in tree." ;
                  }
                  choix = 0 ;
            
            }
            
            if (choix == 3)
            {

                  fin = true;
                  
            }

      
      }while (fin!=true);

}
Italbro5Asked:
Who is Participating?
I wear a lot of hats...

"The solutions and answers provided on Experts Exchange have been extremely helpful to me over the last few years. I wear a lot of hats - Developer, Database Administrator, Help Desk, etc., so I know a lot of things but not a lot about one thing. Experts Exchange gives me answers from people who do know a lot about one thing, in a easy to use platform." -Todd S.

Italbro5Author Commented:
my error is probably :

void Dictio::InsertDictionary(const char * word, int len)
or
Dictio * Dictio::follow(const char * word, int len, int & plen)


an other thing is here, in InsertDictionary :

 if (next != 0) {
     /* Here it says that the next node is non-zero
        but this indicates that follow didn't go as
        far as it could, so we have an internal error.
        This should definitely throw an exception */
     // follow() didn't do what it's supposed to do.
     // fatal error, throw error or something if you
     // want here.
     return;
  }

if i take this out, it shows less and less words then i had before
0
KocilCommented:
void Dictio::InsertDictionary(const char * word, int len) {
   ....

  // need to add more nodes to the tree.
  do {

    ...
    // Only this i think
    // *** Dictio *& next = n -> a[c - 'a'];
    Dictio *next = n->a[c-'a'];
    if (next != 0) {
      return;
    }
    next = n = new Dictio;
  } while (plen < len);
  n -> FlagEndWord = true; /* NEW FIX NEW FIX */
}
0
Italbro5Author Commented:
Kocil :
now it dosent print any word at all
lol
guess it dosent work
0
KocilCommented:
Oops ... sorry :)
0
KocilCommented:
Ok mate.
I think I found it.

Ignore my prev messages. This is right.
Dictio *& next = n -> a[c - 'a'];

But at the follow, it should be

/*
Follow is a function that tries to find a node that represent the longest prefix found in the tree.
If "pre" is stored in the tree and you do
Dictio * n = follow("prefix",6,plen);

n will be the node representing the 'e' of "pre".
//** plen will have the value 3 indicating that the length
//** of this prefix is of length 3.
// I changed this spec to
plen will have the value 2 indicating that the depth of the last node (start from 0).

The function follow never inserts new node in the tree but tries to follow the nodes as long as it find a valid continuation.

It follows that if n != 0 (it should always be) and
plen == len then the node represent the full word.
*/

And you may make this simple correction

Dictio * Dictio::follow(const char * word, int len, int & plen)
{
  ...

  while (x < len) {
    //*** char c = word[x++];
    char c = word[x];

    ....
   
    // move the increment here
    x++;
    n = next;
  }
  plen = x;
  return n;
}


Second thing is, you may modify the following

void AppendDictionary(const char * file)
{
  ...
  while (f.getline(buf,sizeof(buf),'\n')) {
   
    // skip the newline at end of line if any.
    //**** f.ignore(1024,'\n');
    // just delete it
    Dictio::InsertDictionary(buf,strlen(buf));
 }
}


cheers


0

Experts Exchange Solution brought to you by

Your issues matter to us.

Facing a tech roadblock? Get the help and guidance you need from experienced professionals who care. Ask your question anytime, anywhere, with no hassle.

Start your 7-day free trial
It's more than this solution.Get answers and train to solve all your tech problems - anytime, anywhere.Try it for free Edge Out The Competitionfor your dream job with proven skills and certifications.Get started today Stand Outas the employee with proven skills.Start learning today for free Move Your Career Forwardwith certification training in the latest technologies.Start your trial today
C++

From novice to tech pro — start learning today.

Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.