Solved

Probing a Tree

Posted on 1998-06-01
15
268 Views
Last Modified: 2010-04-02
I am currently working on a program which reads a file and extracts only words, putting them into a tree in dictionary order.  If the same word occurrs twice or more, its counter is incremented.

One option for the user is to p)robe the tree.  After choosing to probe from the main menu, the user is given another menu option of to go up, left, or right.  After choosing to go a certain direction a two line graphical display of the tree is given.  I need help on the statements which will print these branches of the tree each time a move is made by the user.

Here is what I have so far.

class Probe{
  public:
      Probe(){_top = 0; _trail [0] = ??;};
      ~Probe(){_top = 0; _trail [0] = ??;};
      void goUp(){if(top > 0) top--;}
      void goLeft();
      void goRight();
      void goTop(){top = 0;}
      void print();
      void Delete();   // delete current node yet

      private:

            int _top;  // index to top of trail stack
            enum {_size = 30};
            Node *_trail[_size];
};

For the constructor and destructor above, I think I need to initialize the stack with a pointer.  Any suggestions?

The function definitions for goLeft and goRight are:

void Probe::goRight()
{
      if(_trail[_top]->_right && _top < _size -1)
      {
      _trail[_top + 1] = _trail[_top] -> _right;
      top++;
      }
}

void Probe::goLeft()
{
      if(_trail[_top]->_left && _top < _size -1)
            {
            _trail[_top + 1] = _trail[_top] -> _right;
            top++;
      }
}
0
Comment
Question by:John500
  • 9
  • 4
  • 2
15 Comments
 
LVL 22

Accepted Solution

by:
nietod earned 100 total points
ID: 1165037
answer coming.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1165038
A bunch of things.

First of all, you've got space for a strack called _trail.  but you don't have anything to indicate how many items are on the stack.  You need an integer counter to record how many entries on the stack are in use.

The constructor does not need to initialize the stack, that is _trail.  It needs to initialize the counter that indicates how much is on the stack.  (You couldn't figure out how to initialize the stack.  (Often when you can't figure out how to do something that is an indication that you are trying to do the wrong thing.  Mybe not often for you yet, but as you advance, look fo this clue.)

0
 
LVL 22

Expert Comment

by:nietod
ID: 1165039
Opps, you do have a stack size counter.  I missed the private stuff.  Leave the Top initialization alone and remove the _trail initialization.

continues.


0
 
LVL 22

Expert Comment

by:nietod
ID: 1165040
Other than indenting (just kidding), your go left and right code is very good.  One potential problem would be if there is no entries in the _trail array.  That is, if the probe doesn't yet have a pointer to the head node in the first entry, calling one of these procedures will cause a crash.  I don't know if that will be a problem in your program.  That depends on how this is used.  but you might want to put in a check.

Note If you impliment the stack as a seperate class with push and pop operations.  The code will be a lot cleaner and safer.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1165041
Question:  What is the mean when _top is 0.  Usually that means that there are not items on the stack.  Your code sometimes is written that way.  but sometimes is written as if it means there is one item on the stack, a pointer to the head node.  You need to make that consistent.  (Either way would work,  but 0 being empty seems better.)

Just as an example, GoTop() sets the _top to 0.  Does that mean there are no items on the stack or 1 item on the stack?
0
 
LVL 22

Expert Comment

by:nietod
ID: 1165042
>> I need help on the statements which will print these
>> branches of the tree each time a move is made by the user

Do you mean the help with the movement (the stuff so far), or help actually printing?  I can't help you with the printing yet, because I don't know what you need to print.
0
 
LVL 22

Expert Comment

by:nietod
ID: 1165043
You've come a long way.  What you've got is 99% correct and well on its way to being done.

The changes you HAVE to make are small.  Remove the _trail initialization.  Make the meanning of _top = 0 consistent, possibly look for errros when there stack is empty.  One change I would recomend, but that is not necessary, is that you use a stack class rather than a hardcoded stack.  It makes the code shorter and simpler and less potential for errors.
0
Top 6 Sources for Identifying Threat Actor TTPs

Understanding your enemy is essential. These six sources will help you identify the most popular threat actor tactics, techniques, and procedures (TTPs).

 
LVL 10

Expert Comment

by:RONSLOW
ID: 1165044
Gee .. this looks familiar
0
 
LVL 10

Expert Comment

by:RONSLOW
ID: 1165045
Also, as a matter of style and good habits, I'd initialize member variables in your constructor like this
  Probe() : _top(0) { .. }
instead of like this
  Probe() { _top = 0; .. }
this is a good habit to get into as it can save you from inefficient code, when initializing classes instead of just simple integer variable.

The difference is, if _top were a class object, the first (preferred) method would construct it in one step using the appropriate constructor; the second method would use the default constructor to initialize it, and then use an assignment operator to change the value.

Another thing is in this bit of code
  if(_trail[_top]->_left && _top < _size -1)
you access the [_top] element BEFORE checking that the subscript is valid.  This is not good!! instead write it as
  if(_top < _size -1 && _trail[_top]->_left)
just to be safe.

0
 

Author Comment

by:John500
ID: 1165046
Todd,

Sorry, but I lost use of my computer since 9:30 this morning.  My employer was upgrading my hard drive when one problem after another kept creeping up.  I won't have my PC back until tomorrow and I'm currently using a co-workers computer.

Can you send me your response to the two letters I sent you this morning?  Thanks

John
0
 
LVL 22

Expert Comment

by:nietod
ID: 1165047
I sent several things (without looking too close).  Let me know if you need more.
0
 

Author Comment

by:John500
ID: 1165048
Todd,

I need some feedback.  Is the mail I sent still acting up?  If so I will have to continue via this screen, but I must continue.

John
0
 
LVL 22

Expert Comment

by:nietod
ID: 1165049
I sent back a response.  Both e-mails were acting up.  The word search is fine, but I suggested a little clean-up.  The count is in need of help.  I tried a different approach to explaining it, hopefully it will click.
0
 

Author Comment

by:John500
ID: 1165050

Todd,


>If the options that are currently available are "U"p, "L"eft, "R"ight,
>and "Q"uit  you will use
>
>char Option = GetMenuLetter("ULRQ");

Still a little confused about where these options will be displayed and where char Option is defined.  Is char Option defined each time a particular move is available?

If so, the first time the user sees the menu he/she will be able to move in any direction assuming there is a _root/tree.  So, the first char Option is:

char Option = GetMenuLetter ("LRTUQ")
This is what I was able to come up with so far.  Let me know where I'm lacking.

char GetMenuLetter(const char *string)
{
    while (1) // Do until a return.
    {
     char string[15];
     char *ptr;
     char ch = getc(stdin);
     ch = toupper(ch);
    ptr = strchr(string, ch);
    if (ptr)
     return ch;
   }
}
void Probe::probeTree()
{
    cout << "Indicate direction to probe with first letter of word:\n\n";
    cout<<"l)eft,   r)ight,   t)op,   u)p,   q)uit\n";
    cout<<"\nSelection:\n\n";
    cin>> string;
    char Option = GetMenuLetterr("LRTUQ");

....}



0
 

Author Comment

by:John500
ID: 1165051
Todd gave detailed explanations and answers!
0

Featured Post

How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

Join & Write a Comment

Unlike C#, C++ doesn't have native support for sealing classes (so they cannot be sub-classed). At the cost of a virtual base class pointer it is possible to implement a pseudo sealing mechanism The trick is to virtually inherit from a base class…
Go is an acronym of golang, is a programming language developed Google in 2007. Go is a new language that is mostly in the C family, with significant input from Pascal/Modula/Oberon family. Hence Go arisen as low-level language with fast compilation…
The goal of the video will be to teach the user the concept of local variables and scope. An example of a locally defined variable will be given as well as an explanation of what scope is in C++. The local variable and concept of scope will be relat…
The viewer will learn how to use the return statement in functions in C++. The video will also teach the user how to pass data to a function and have the function return data back for further processing.

746 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

Need Help in Real-Time?

Connect with top rated Experts

13 Experts available now in Live!

Get 1:1 Help Now