?
Solved

Error HERE, Little mistake when adding in Tree

Posted on 2003-03-11
5
Medium Priority
?
208 Views
Last Modified: 2010-04-01
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);

}
0
Comment
Question by:Italbro5
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
  • 3
  • 2
5 Comments
 

Author Comment

by:Italbro5
ID: 8116657
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
 
LVL 5

Expert Comment

by:Kocil
ID: 8116874
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
 

Author Comment

by:Italbro5
ID: 8118800
Kocil :
now it dosent print any word at all
lol
guess it dosent work
0
 
LVL 5

Expert Comment

by:Kocil
ID: 8123340
Oops ... sorry :)
0
 
LVL 5

Accepted Solution

by:
Kocil earned 140 total points
ID: 8124176
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

Featured Post

Independent Software Vendors: We Want Your Opinion

We value your feedback.

Take our survey and automatically be enter to win anyone of the following:
Yeti Cooler, Amazon eGift Card, and Movie eGift Card!

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Article by: SunnyDark
This article's goal is to present you with an easy to use XML wrapper for C++ and also present some interesting techniques that you might use with MS C++. The reason I built this class is to ease the pain of using XML files with C++, since there is…
Basic understanding on "OO- Object Orientation" is needed for designing a logical solution to solve a problem. Basic OOAD is a prerequisite for a coder to ensure that they follow the basic design of OO. This would help developers to understand the b…
The goal of the tutorial is to teach the user how to use functions in C++. The video will cover how to define functions, how to call functions and how to create functions prototypes. Microsoft Visual C++ 2010 Express will be used as a text editor an…
The viewer will be introduced to the member functions push_back and pop_back of the vector class. The video will teach the difference between the two as well as how to use each one along with its functionality.
Suggested Courses

770 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question