Probing a Tree
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++;
}
}
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++;
}
}
ASKER CERTIFIED SOLUTION
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Opps, you do have a stack size counter. I missed the private stuff. Leave the Top initialization alone and remove the _trail initialization.
continues.
continues.
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.
Note If you impliment the stack as a seperate class with push and pop operations. The code will be a lot cleaner and safer.
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?
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?
>> 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.
>> 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.
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.
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.
Gee .. this looks familiar
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.
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.
ASKER
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
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
I sent several things (without looking too close). Let me know if you need more.
ASKER
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
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
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.
ASKER
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");
....}
ASKER
Todd gave detailed explanations and answers!
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.)