0

尝试递归搜索时，我没有返回正确的数字。我正在使用它来遍历使用单链表实现的队列并返回该项目所在的索引，以便我可以确定需要多少次 dequeue() 才能到达该项目。

public int search(E item) {
    return recSearch(item, head);
}

public int recSearch(E item, Node node){
    if (head == null){
        return -1;
    }else if (node.data.equals(item)){
        return searchCnt;
    }else{
        searchCnt++;
        return recSearch(item, node.next);
    }
}

我觉得它应该正确计数，因为每次它无法满足 if 和 else if 条件时都必须计数，但我不是在正确的地方递增吗？还是我完全离开了？谢谢您的帮助！

4

2 回答 2

2

您需要searchCnt在search()调用recSearch(). 此外，您需要测试是否node == null，不是head == null。

或者，你可以试试这个：

public int search(E item) {
    return recSearch(item, head, 0);
}

public int recSearch(E item, Node node, int index){
    if (node == null){
        return -1;
    }else if (node.data.equals(item)){
        return index;
    }else{
        return recSearch(item, node.next, index + 1);
    }
}

它消除了对类/实例变量的需要。

请注意，这不允许null节点上的数据。为了支持null值，您需要if/else在检查后立即创建另一个分支node == null：

}else if (item == null && node.data == null) {
    return index;
}
于 2013-10-29T23:44:33.460 回答
1

您需要searchCnt在递归时传递您的 var 以便正确更新它。

public int search(E item) {
    return recSearch(item, head, 1);
}

public int recSearch(E item, Node node, int searchCnt){
    if (head == null){
        return -1;
    }else if (node.data.equals(item)){
        return searchCnt;
    }else{
        return recSearch(item, node.next, ++searchCnt);
    }
}

初始1调用中的 假设，如果您在 的第一次迭代中找到您的项目，则recSearch算作一次搜索（在这种情况下search将返回1）。

于 2013-10-29T23:45:10.257 回答