0

我目前是一名 Comp sci 大一学生，致力于通过课堂和在线学习数据结构。

我也是新手，但过去对我有很大帮助。

我当前的问题是搜索 LinkedList 以返回其编号出现在列表中的最后一个索引。

我觉得这与递归和不断搜索有关，直到您可以以某种方式检查确定这是该项目的最后一次出现，然后返回其索引。

然而，我的第一学期 Java 课程根本没有涉及递归，我有点不知所措。

在这些课程中，我并不要求明确的答案，我只需要一些指导。或者向我保证我在研究递归方面走在正确的道路上？

另外，这是我到目前为止所尝试的。谢谢您的帮助！

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable 
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
            //check rest of the list for if that number exists beyond
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
    return -1;
}
4

3 回答 3

1

当您有这样的匹配时，您可以保存并覆盖索引：

public int getLastIndexOf(int lastItem) { //goal is to return the lastindex at which that number appears last
    Node current;
    current = head;
    int count = 0; //count variable
    int lastIndex = 0;
    while (current.next != null) { //go through list
        if (current.dataItem == lastItem) { 
                lastIndex = count;
        }
        count++; //increment count for every time loop executes
        current = current.next; //moves onto next node to check
    }
return lastIndex;

因此，您将在 lastIndex 中保存匹配的位置，如果有多个匹配，您将使用“最新”值覆盖它。

于 2017-02-25T18:21:30.387 回答
0

将列表视为一个节点，然后是另一个列表，称为尾部。这是伪代码，注意你需要两个方法，private一个接受一个节点，这是子列表。

public int getLastIndexOf(value) {
    return getLastIndexOf(head, value);
}

private int getLastIndexOf(sublist, value) {
    //check the tail first (because we want last index)
    if (sublist.tail != null) {//list has a tail
        int lastIndexInTail = getLastIndexOf(sublist.tail, value); //recursion
        if(lastIndexInTail != -1)
          return lastIndexInTail + 1; //it's in the sub list, the sub list starts at idx 1
    }

    // it's not in the tail, check this head
    if (sublist.data == value){
      return 0; //it's at the front of this list
    }

    return -1; //it's not in the head or in the tail of sublist
}
于 2017-02-25T18:21:39.017 回答
0

如果你想通过递归来做到这一点

Topcoder的这个教程在这里可能很有用。

我的 2 美分如下：

递归和迭代（循环，如 for、while 等）可用于解决您当前的问题。

您当前的代码不是递归的，而是迭代的。当您一次又一次地调用相同的函数直到某个结束条件时，就会发生递归。

递归函数有两个部分：

  1. 基本条件 - 告诉您何时停止递归
  2. 递归条件 - 告诉你何时进行递归

让我们看一个例子。假设您要打印 10 次“Hello World”。这是您如何迭代地执行此操作的方法

for(int i = 0; i < 10; i++){
   System.out.println("Hello World");
}

这就是你如何递归地做到这一点

void helloWorldPrinter(int index){
   //This is the base condition, tells us to stop when we've reached 10
   if(index == 10){
      return;
   }
   else{
      //Print for the n th hello world
      System.out.println("Hello World");
      //call the same function for printing the next (n+1 th) hello world
      helloWorldPrinter(index+1); //Looks similar to the i++ in the loop right?
   }
}

递归在二叉树中非常有用，二叉树是一种看起来像倒挂树的数据结构。在编写迭代与递归代码时，您可以牢记的一个概念是，迭代就像将数据结构视为观察者并对其执行操作。递归就像您是数据结构中的一个元素一样进行 - 您完成您的工作并将责任传递给下一个元素（下一个递归调用）

现在我相信您可以将此逻辑扩展到查找链接列表中的最后一项。尽管对此的迭代解决方案比递归解决方案要容易得多。

逻辑是：

Loop over list (iterative or recursive)
  If element is found, note down the index
End Loop if list has been traversed completely
return the element index
于 2017-02-25T18:22:08.137 回答