Search function in derived class, loop condition

Question

Working through the book "Data structures using C++" of D.S. Malik. I'm a bit puzzled about the following search function, (for linked lists)

According to Malik, "if the search item is the i th item in the list, the while loop executes i times. The following is the exact code from the book(without comments).

template <class Type>
bool unorderedLinkList<Type>::search(const Type& searchItem) const
{
    nodeType<Type> *current; 
    bool found = false; 
    current = first; 

    while (current != NULL && !found)
        if (current->info == searchItem) 
            found = true;
        else
            current = current->link; 
    return found;
}

Will this loop really stop once the item is found?

while (current != NULL && !found)

My instinct tells me it will keep going with those && operators, but I might be wrong. Was it just a typo in the book, or am I missing something?

Another problem is the following line that my compiler complains about.

current = first; //error 'first' was not declared in this scope

So to fix it, I replaced it with

current = searchItem.first;

Compiler doesn't complain anymore, but is it accessing the right protected member from the parent class? (unorderedLinkList inherits from linkedListType parent class, which has protected nodeType<Type> *first member)

Edit: More code :D

template <class Type>
struct nodeType
{
    Type info;
    nodeType<Type> *link;
};



template <class Type>
class linkedListType
{ 
public: //some removed for space
        virtual bool search(const Type& searchItem) const = 0;

protected: 
    int count; 
    nodeType<Type> *first; 
    nodeType<Type> *last; 

private:
    void copyList(const linkedListType<Type>& otherList);
    //function to make a copy of otherlist and assign to this list
};

Edit: The derived class

template <class Type>
class unorderedLinkedList: public linkedListType<Type>
{
public:
    bool search(const Type& searchItem) const;
}

Edit: VS Express compiles my code, but this site wont. Help please? T_T http://ideone.com/SN2R99

score 2 · Accepted Answer · edited May 23 '17 at 12:18

2

while (current != NULL && !found) is fine.

In words - "while we're not at the end of the list (which is what current != NULL means) and the item has not been found". So if we're either at the end of the list or the item has been found, the condition will no longer be true.

You can also translate it to while (!(current == NULL || found)) (using De Morgan's laws), which loosely means "stop when we're at the end of the list or the item has been found". To understand the "stop when" logic, think about the trivial cases:

while (!true), which is while (false), which loosely means "stop when true" (thus instantly)
while (!false), which is while (true), which loosely means "stop when false" (thus never)

first isn't defined because ... well, I'm not exactly sure, it's there in the standard somewhere (which I am no expert on), C++ is weird sometimes. Related question. Workarounds:

Put using linkedListType<Type>::first in your class
Replace first by this->first
Replace first by linkedListType<Type>::first

edited May 23 '17 at 12:18

Community

1
1

answered Apr 23 '13 at 13:28

Bernhard Barker

54,589
14
104
138

Thanks, I had a bit of a derp moment there and misunderstood it. So the moment found is true, !found is no longer not true, which ends the loop. I'll add some more code to help clarify my second problem. – user2280041 Apr 23 '13 at 13:37
-____- You're right, it works fine in VS Express. I was trying to run it in codeblocks with gcc and it kept giving me troubles. I've been hesitant to move over to VS for my coding, because I started on codeblocks, but I guess this is the last straw. Thanks for the help, much appreciated! – user2280041 Apr 23 '13 at 13:57
1

VS accepts it, but that site you linked me doesn't. It also gives compiler error. Here, take a look. :/ http://ideone.com/SN2R99 – user2280041 Apr 23 '13 at 14:10

Search function in derived class, loop condition

1 Answers1