0

阅读 DS Malik 的“使用 C++ 的数据结构”一书。我对以下搜索功能有点困惑，（对于链表）

根据 Malik 的说法，“如果搜索项是列表中的第i个项，则 while 循环将执行 i 次。以下是书中的确切代码（不含注释）。

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;
}

一旦找到该项目，这个循环真的会停止吗？

while (current != NULL && !found)

我的直觉告诉我它将继续使用那些 && 运算符，但我可能错了。这只是书中的错字，还是我遗漏了什么？

另一个问题是我的编译器抱怨的以下行。

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

所以要修复它，我将其替换为

current = searchItem.first;

编译器不再抱怨，但它是否从父类访问了正确的受保护成员？（unorderedLinkList 继承自linkedListType 父类，具有受保护的nodeType<Type> *first成员）

编辑：更多代码：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
};

编辑：派生类

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

编辑：VS Express 编译我的代码，但这个站点不会。请帮忙？T_T http://ideone.com/SN2R99

4

1 回答 1

2

while (current != NULL && !found)很好。

用文字来说 - “虽然我们不在列表的末尾（这current != NULL意味着什么）并且该项目尚未找到”。因此，如果我们位于列表的末尾或已找到该项目，则条件将不再为真。

您也可以将其翻译为while (!(current == NULL || found))（使用德摩根定律），大致意思是“当我们在列表末尾或找到该项目时停止”。要理解“何时停止”的逻辑，请考虑以下琐碎案例：

  • while (!true), 即while (false), 粗略的意思是“当真时停止”（因此立即停止）
  • while (!false), 即while (true), 大致意思是“假时停止”（因此永远不会）

first没有定义，因为......好吧，我不太确定，它在某个地方的标准中（我不是专家），C++ 有时很奇怪。相关问题。解决方法：

  • 加入using linkedListType<Type>::first你的班级
  • 替换first为this->first
  • 替换first为linkedListType<Type>::first
于 2013-04-23T13:28:41.090 回答