Thread: Confused about search function

  1. #1
    Registered User
    Join Date
    Feb 2010
    Posts
    6

    Confused about search function

    I have this search function that has a prototype of:
    Node<T>* search(const T& key, bool (*match)(const T&,const T&));

    where:
    • key is a reference to the thing that we are searching for
    • match is the address of a function that will return true if its second argument "matches" the first and false otherwise. You may assume that at most one node will "match" the key. just call it to compare key against a value in the node)
    • the function returns the address of the node that matches if it is found, NULL otherwise.
    • if item is found, the list will need to be adjusted so that the found node is at the front of the list

    The page can be found here on pastebin for the search function. It is searching for and finding 'key' in a doubly link list and it's supposed to bring it to the front of the node but this test program i have gives an error saying list was not properly adjusted after search. That's test 11 but it tests other functions before search. Please help!!
    Full assignment can be found here:
    C++ pastebin - collaborative debugging tool.

    Thank you.

  2. #2
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    this test program i have gives an error saying list was not properly adjusted after search.
    What? I dont see any printing statements where it would say this, and I dont think's the error message you'd be getting from the OS. Whats the actual/exact error message? Is it a runtime error? Compile time error? Is it even an error? Does it say what line this occurs on? If not, add simple print statements to determine where the error is. Or even better: use a debugger to step through your program until the error happens. Then let us know what line/lines the error occurs on so we have somewhere to start.

    I, for one, am not going to debug your code line by line. The alternative is to copy, paste, compile, run/debug, which is also not a likely thing to happen. So, again, narrow down where there problem is and let us know.

  3. #3
    Registered User
    Join Date
    Feb 2010
    Posts
    6

    Sorry about that

    The Main

    Up there is the main that it is supposed to iterate through. I was supposed to write the node class:

    A template class called Node, which will be used as the node in a doubly linked list. When a Node is instantiated, it is passed an instance of the unknown data type which is the data that the node will store. A Node also has the following member functions:

    And an salist.h class that

    is a friend of the Node class. This will allow SAList access to modify and change the pointers in an instance of the Node class..

    I have gotten to the debugger and it stops at line 146 because it says I have adjusted the linked list that I am sending out incorrectly after going into the search function. The problem is the logic at lines 286 and 289 of this file:

    here.

    I can't seem to figure out the proper logic after finding the 'key' in a node and reorganizing it properly so the key that had been found is now moved to the front and the other nodes that are after it are still in proper order...

  4. #4
    Registered User
    Join Date
    Feb 2010
    Posts
    6

    Clarification

    The Main link up there is the test program I was referring to.

  5. #5
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    The code at line 146 is calling "checkBooks".

  6. #6
    Registered User
    Join Date
    Feb 2010
    Posts
    6
    it's comparing one link to another in a big list of books contained within my doubly linked list

  7. #7
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    The code at line 146 is calling "checkBooks" when the given if statement is true (so that "checkBooks" returned false), so investigate that function. "checkBooks" returns false only when comparing two of the things and the if statement is true (so that "sameBook" returns false), so investigate that function. "sameBook" returns false only when the two given books do not have the same "id_" field, or do not have the same author value, or the same title value.

    In that function, add a print statement showing these 6 values: the 3 fields for both of the books. At least one of the three conditions will be true. Why it is true, is a different question that requires studying all of your code, and thus a very lengthy process.

    EDIT: The more code you have, the higher the probability that there are logic errors in it. Considering the long length of your code, there is potential for a number of logic errors, which are difficult to find after working on it for a while. If you are working on a "big list of books", then reduce the size of your dataset. Use only 2 books. Does the problem still happen? Use 5 books. Problem still happen? 10 books, 100 books. If you start with a large list of books it will only be that much more complex and tedious when debugging (and so not very productive).
    Last edited by nadroj; 02-10-2010 at 07:55 PM.

  8. #8
    Registered User
    Join Date
    Feb 2010
    Posts
    6
    Thank you.
    Can you tell me how to properly sort what is found in this algorithm:
    Code:
                 if(temp->next_ != NULL){
                    temp = temp->next_;
                    temp->prev_ = curr->prev_;
                    temp = temp->prev_;
                    temp->next_ = curr->next_;
                 }
    It is where the logical error is and I can't seem to wrap my mind around sorting it so the thing that was found (located in temp) can be found at the beginning of the linked list.
    head refers to the front of the linked list
    tail refers to the end of the linked list
    curr and temp are pointers to the linked list
    next is a pointer to the next point in the linked list and prev is a pointer to the previous node in the linked list...

  9. #9
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    Have you tried what I suggested in the edit above? Try working with only 2 books, instead of, as you said, "a big list of books". It will be very easy to debug it if you can reproduce the problem with those 2 books. If you cant, try with 5, 10. With these small numbers it is reasonable and do-able to "step through" each line of code in order to verify each step is what you intended. Debugging with "a big list of books" (which I assume is more than 10) is much more difficult, confusing, and time consuming to debug and follow all of the logic. With, say, 5 books it should be somewhat easy to remember the state of each book so that you can verify the code at each step.

    Basically, I dont want to try to debug another linked list problem. They make my head hurt.

  10. #10
    Registered User
    Join Date
    Feb 2010
    Posts
    6
    well, there's only 21 books in the list. so it's not that big. but it's basically just sorting it that i have to do...it is just the sort function that adjusts the list so that the found node is at the front of the list...

  11. #11
    Registered User
    Join Date
    Oct 2006
    Location
    Canada
    Posts
    1,243
    21 > 2, 21 > 5, 21 > 10. Again, use a small dataset. You can still sort 2 books, 5 books. Try to reproduce the problem with 2 or 5 books. I can only help with what I know and what I would do. I would try small data. If you insist on using your complete data set then I cant help.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. doubt in c parser coding
    By akshara.sinha in forum C Programming
    Replies: 4
    Last Post: 12-23-2007, 01:49 PM
  2. Logical errors with seach function
    By Taka in forum C Programming
    Replies: 4
    Last Post: 09-18-2006, 05:20 AM
  3. Including lib in a lib
    By bibiteinfo in forum C++ Programming
    Replies: 0
    Last Post: 02-07-2006, 02:28 PM
  4. Game Pointer Trouble?
    By Drahcir in forum C Programming
    Replies: 8
    Last Post: 02-04-2006, 02:53 AM
  5. c++ linking problem for x11
    By kron in forum Linux Programming
    Replies: 1
    Last Post: 11-19-2004, 10:18 AM

Tags for this Thread