使用递归在List中查找int类型-何时返回

Question

我试图递归地通过列表类中的每个节点移动，以查找列表中的一个节点中是否存在某个整数。

我的头文件:

class List
{
public:
    bool find(int d) const { return false; }
private:
    Node *head;
    bool findNode(const Node*, int) const;
};

下面是两个函数的代码:

bool List::find(int d) const
{
    return findNode(head, d);
}
bool List::findNode(const Node* n, int d) const
{
    if (n == NULL)
        return false;
    else if (n->data == d)
        return true;
    else
        findNode(n->next, d);
}

现在这是我的问题:我是否通过在findNode函数中添加if (n == NULL)语句来使它总是返回false来毁灭自己?我不认为我需要这样做，如果我已经在头文件中有return false。我应该去掉这条线吗?有没有更好的方法?

Answer 1

if (n == NULL) return false很好，因为它只会在您到达列表末尾时发生，并且您应该返回false。

我看到的第一个问题是findNode(n->next, d);应该是return findNode(n->next, d);

第二点是需要从头文件中删除find()的函数体。函数体不能定义两次。

因此，完整的代码是:

class List
{
public:
    bool find(int d) const;
private:
    Node *head;
    bool findNode(const Node*, int) const;
};
bool List::find(int d) const
{
    return findNode(head, d);
}
bool List::findNode(const Node* n, int d) const
{
    if (n == NULL)
        return false;
    else if (n->data == d)
        return true;
    else
        return findNode(n->next, d);
}

Answer 2

您需要null检查，因为这是确定列表结束的方式。我猜你是在做练习，否则显然你根本不需要递归