|
I have a question regarding Binary Trees. I have to read an input file, then traverse the tree, and then print out the results of the traversal. I can understand what has to be done, but when it comes to translating it into C++ language, I get stuck. 
It is a genealogy tree, with advisors and advisees assigned to them. I have to construct the tree for a sequence of name pairs, and traverse the tree to output the list of the names and the levels as I visit each node in the tree. The advisor name in the first pair of names in the text file is the given list for the root node name.
A sample input
alonzo.church hartely.rogers
alonzo.church samuel.kleene
alonzo.church manuel.blum
hartley.rogers pat.fischer
samuel.kleene rob.constable
samuel.kleene paul.axt
pat.fischer dennis.ritchie
should produce this output
alonzo.church 1
hartley.rogers 2
samuel.kleene 2
manuel.blum 2
pat.fischer 3
rob.constable 3
paul.axt 3
dennis.ritchie 4
The text file is on my computer: "TestInput.txt".
Any help is welcomed, and appreciated.
Thank you for you information.
D.
-- modified at 10:01 Sunday 30th April, 2006
|
|
|
|
|
Blah Blah Blah 29 wrote: alonzo.church 1
hartley.rogers 2
samuel.kleene 2
manuel.blum 2
pat.fischer 3
rob.constable 3
paul.axt 3
dennis.ritchie 4
Which means:
alonzo.church is the root node.
hartley.rogers , samuel.kleene , and manuel.blum are the 2nd tier.
pat.fischer , rob.constable , and paul.axt are the 3rd tier.
dennis.ritchie is the farest node.
Maxwell Chen
|
|
|
|
|
Ok, now I understand. It's just that I don't know what to do when it comes to reading an input file, and defining a binary tree based on the input file.
|
|
|
|
|
|
Blah Blah Blah 29 wrote: It's just that I don't know what to do when it comes to reading an input file
So start there. Once you can successfully read, parse, and print the contents of said file, then you can move on to manipulating a binary tree. I would suggest not mixing the two together until you have a firm grasp of the fundamentals of each.
"Let us be thankful for the fools. But for them the rest of us could not succeed." - Mark Twain
"We will be known forever by the tracks we leave." - Native American Proverb
|
|
|
|
|
I would use a std::set.
Steve
|
|
|
|
|
He was trying to do some binary tree stuffs. std::set is of red-black tree. 
Maxwell Chen
|
|
|
|
|
A red-black tree is a type of binary tree - specifically a type of self balancing binary tree.
Steve
|
|
|
|
|
OK.
Maxwell Chen
|
|
|
|
|
Hi
I am new to C++ and have come across a couple of problem I'm having difficulty to solve.
Problem 1
The code below is a function which adds data to an array and validates the input. I am having difficulty when a user hit the return key by accident, the code cycles through the options but does not allow any more input and goes into a inifite loop. I have tryed using cin.ignor() and different varients with no luck. I have bolded the code which is the problem.
#define VSIZE 3
void UserInput(char arrStudent [VSIZE][30])
{
char chTemp [200] = {' '};
system("cls");
cout<<"\n****** Student Detail Screen ******" <<endl<<endl;
for (int n = 0;n<VSIZE;n++)
{
int nValid = 0;
cout << "Details for student number "<<n<<":"<<endl<<endl;
cout << "Please input Students Name"<<endl;
cout << "(maximum of 30 characters): ";
do
{
cin.ignore();
cin.get(chTemp,200,'\n');
if(strlen(chTemp) =< 0)
{
cout << "Name contains no characters, Please try again: ";
cin.ignore();
cin.get(chTemp,200);
}
if(strlen(chTemp) > 30)
{
cout << "Name contains " << strlen(chTemp) << " characters, Please input a shorter name: ";
cin.ignore();
cin.get(chTemp,200);
}
else
{
nValid = 1;
}
}
while (nValid == 0);
strcpy(arrStudent[n],chTemp);
}
}
Problem two - this will be part of the above code, i think it reletivly simple but i cant seem to get it to work. I wanted it so if they type exit instead of a name it would exit the loop.
#define VSIZE 3
char chTemp [200] = {' '};
for (int n = 0;n<VSIZE;n++)
{
if (chTemp[200] == 'exit')
{
n = VSIZE;
cout <<"TEST";
}
}
Any help would be great. Thanks
Helen
|
|
|
|
|
Problem 1
for (int n = 0; n < VSIZE; n++)
{
int nValid = 0;
cout << "Details for student number "<<n+1<<":"<<endl<<endl;
cout << "Please input Students Name"<<endl;
cout << "(maximum of 30 characters): ";
do
{
cin.getline(chTemp,200);
if(strlen(chTemp) == 0)
{
cout << "Name contains no characters, Please try again: ";
}
else if(strlen(chTemp) > 30)
{
cout << "Name contains " << strlen(chTemp) << " characters, Please input a shorter name: ";
}
else
{
nValid = 1;
}
}
while (nValid == 0);
strcpy(arrStudent[n],chTemp);
}
It's inefficient but I guess you are just starting out so it's fine 
Did they state that you are not supposed to use STL? If not std::string is convenient.
Edit:
Another thing to note is that a C string is just an array of characters with a terminating null. If it can't find the 0, then it can go past the buffer allocated and keep going till it hits a 0. This also means that if you need a C string that can store up to 30 characters, you need to have a buffer size of 31 so you can store that terminating null character.
Problem 2
if(chTemp[200] == "exit")
All you happen to be doing here is comparing two pointer values (or their addresses) and not the actual string data. You would need to call (strcmp(chTemp, "exit") == 0) to see if the string data is actually the same.
-- modified at 13:45 Sunday 30th April, 2006
|
|
|
|
|
HI haitch79
In first problem, try to use getline instead of get(...) or simply write the following code to get input
gets(chTemp);
in problem 2, to compare your string with exit, write following line.
gets(chTemp);<br />
if (!strcmp(chTemp, "exit"))
{<br />
do something;<br />
}
i hope this will solve your problem. tell us if problem remains...
Good luck.
We Believe in Excellence
www.aqueelmirza.cjb.net
-- modified at 13:40 Sunday 30th April, 2006
|
|
|
|
|
Hi
Thanks for all your help. after reading your posts, I have rearanged the code so it is a bit more logical and used bool varible for the flaging. I replaced get with getline and it seems to work a treat.
Im not sure what STL is, but i have seen examples like what was writen around, we havnt been taught about it but i dont think that means we cant use it.
Thanks again
Helen
|
|
|
|
|
STL is Standard Template Library, which is part of the Standard Library of C++. The recent C++ compilers (released later than 1997-11-14) provide STL support.
STL[^] for your information.
Maxwell Chen
|
|
|
|
|
Thankyou, I will have a read and if i uderstand i might try and impilment it.
Thanks again for all your help.
|
|
|
|
|
You are welcome.
All those books about the C++ Language teach STL.
For example:
- "The C++ Programming Language, 3rd Ed Gold", by Bjarne Stroustrup.
- "C++ Primer, 4th Ed", by Stanley Lippman.
- "C++ From the Ground Up, 3rd Ed", by Herbert Schildt.
etc.
There also are some STL specific books talking deep into STL.
Maxwell Chen
|
|
|
|
|
mutex1 in thread 1
mutex2 in thread 2
how to lock the two mutexes simultaneously in thread 3?
Vincent
|
|
|
|
|
You can't lock two mutexes simultaneously in Windows. You can only do them one at a time. Be careful with locking two mutexes at the same time, as it can easily lead to deadlocks.
Ryan "Punctuality is only a virtue for those who aren't smart enough to think of good excuses for being late" John Nichol "Point Of Impact"
|
|
|
|
|
I agree. The only way I see is for you to create a third mutex whick must be locked before accessing any of the other 2, and unlocked when the others are locked. If you try this then you will probably be on an even faster road to deadlock.
Anyway, there may be better objects for you to use instead of mutexes if you are having such a strange necessity. Can you ellaborate a little bit?
Rilhas
|
|
|
|
|
hi ,Ryan and Rilhas
the context is producer/consumer
thread1
----------------------------------------------
p(empty)
mutexRW.lock()
produce(item)
mutexRW.unlock()
v(full)
-----------------------------------------------------
thread2
----------------------------------------------
p(full)
mutexRW.lock()
comsume(item)
mutexRW.unlock()
v(empty)
-----------------------------------------------------
I need to stop thread1 and thread2 sinultaneously in thread3 to avoid deadlock at p(empty) in thread1 for buffer is full or deadlock at p(full) in thread2 for buffer is empty.
and I can't use a third mutex to achieve that because a third mutex would be unefficient for producer/consumer. so give me some clues to solve this problem please. thanks
Vincent
-- modified at 12:48 Tuesday 2nd May, 2006
|
|
|
|
|
I think I don't understand your problem exactly... what are p(x) and v(x)? Why would they cause deadlocks??
Anyway, it seems to me that the most adequate object for you would be a critical section instead of a mutex. The critical section has the benefit of being somewhat more efficient than a mutex. A critical section executes and locks in about 10 cpu cycles (if available) while a mutex locks in about 600 cpu cycles.
The critical sections also have a very nice property that allows the same thread to lock it more than once. In fact, after a thread grabs hold of a critical section object, it can lock it as often as requested and never be blocked. This is useful in the following example:
int FuncA() {
cs.Lock();
do something A
cs.UnLock()
}
int FuncB() {
cs.Lock();
do something B
cs.UnLock()
}
int FuncC() {
cs.Lock();
FuncA();
FuncB();
do something C
cs.UnLock()
}
This property may make it easier for you to avoid deadlocks, since a critical section never locks the thread that owns it. In the example above you can export FuncA(), funcB(), and also FuncC() which uses the already protected FuncA() and FuncB(), and adds a lock of its own. As mentioned, the sequence of 3 locks and unlocks is extremelly fast.
There are also some downsides to critical sections. 1) They can only be used inside the same process space, and not across processes. 2) Some users also report that critical sections do not react very well when they are destroyed if some threads are trying to lock it under Windows 95. I never had any problems. 3) They don't allow a timeout value to be specified in the 95/98/Me fmaily, and also in NT4.
I hope this helps.
Rilhas
|
|
|
|
|
 Hi
my self is ravindra kumar
this is a urgent assignment for me i need a urgent help.
steps of assignment are .
1:- draw a graphics image like circle, rectanlg,square,
triangle,
2: provide aZoom in and Zoom out functionality for that image.
3: provide a rotation functionality for that image which give a 3-d roatation
how can i solve the assignment using application wizard.
or using MFC,
thanks
ravindra
Ravindra
|
|
|
|
|
I want to handle the message that mouse click the vertical scrollbar of the listctrl,and codes as below:
CMyListCtrl::public CListCtrl
BOOL CMyListCtrl::PreTranslateMessage (MSG* pMsg)
{
CScrollBar* pScroll = GetScrollBarCtrl(SB_VERT);//pScroll is NULL!!
if(NULL != pScroll && pMsg->hwnd == pScroll->GetSafeHwnd()){
BOOL flag = FALSE;
CRect rect;
pScroll->GetWindowRect(&rect);
if (pMsg->message == WM_LBUTTONDOWN){
}
}else if(pMsg->message == WM_LBUTTONUP){
}
}
}
|
|
|
|
|
Use a different approach
check out the methods : CWnd::OnVScroll and CWnd::OnHScroll on MSDN , they will help you
Yaron
Ask not what your application can do for you,
Ask what you can do for your application
|
|
|
|
|
I just want to handle the message WM_LBUTTTONDOWN And WM_LBUTTONUP and not to handle the message of WM_VSCROLL
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
