0

我正在尝试以递归方式在指定索引处添加列表节点。我的意思是 List 类 addAtRec() 调用 ListNode 类中的 addAtRec() ，该方法应该是递归的。

这就是我所做的：

列表：

public class List implements Cloneable {

private ListNode firstNode;
private ListNode lastNode;
private String name;
private int counter;

public List(){
    this("list");
}
public void addAtRec(Object obj, int k)
{
    if(firstNode != null)
        firstNode.addAtRec(obj, k, firstNode);
}
}

那当然只是相关的部分......

列表节点：

public class ListNode implements Cloneable {

Object data;
ListNode nextNode;
public ListNode(Object o){
    this(o,null);
}
public ListNode(Object o,ListNode node){
    data=o;
    nextNode=node;
}
public void addAtRec(Object obj, int k, ListNode current) throws ListIndexOutOfBoundsException {
    if(current.nextNode == null && k != 0)
        throw new ListIndexOutOfBoundsException(); //line 47
    if(k == 0)
    {
        ListNode l = new ListNode(obj);
        l.nextNode = current.nextNode;
        current.nextNode = l;
    }
    current = current.nextNode;
    addAtRec(obj, k, current); //line 55
    k--;
}

ListIndexOutOfBoundsException：

public class ListIndexOutOfBoundsException extends RuntimeException {

}

我的 main() 方法：

String s1 = "Objects";
    String s2 = "to";
    String s3 = "check";
    String s4 = "are";
    String s5 = "strings";
    List list = new List("My list");
    list.insertAtBack(s1);
    list.insertAtBack(s2);
    list.insertAtBack(s3);
    list.insertAtBack(s4);
    list.insertAtBack(s5);

    list.addAtRec(s3, 2);

和错误：

Exception in thread "main" ListIndexOutOfBoundsException
at ListNode.addAtRec(ListNode.java:47)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at ListNode.addAtRec(ListNode.java:55)
at List.addAtRec(List.java:158)

我做错了什么？感谢您的时间和答案。

4

1 回答 1

0

您的递归方法中有两个错误：

  1. 在调用之前addAtRec(obj, k, current);你应该减k1，所以最好k--在这条线之前调用。

  2. 一旦你达到了基本情况（when k == 0）并执行了添加新节点的逻辑，你的递归方法必须停止，可能只需要一个简单的return;语句。在这种情况下，您不会停止它，因此您每次都会调用它，直到到达列表的末尾。

根据这 2 条建议，您的代码应如下所示：

public void addAtRec(Object obj, int k, ListNode current)
    throws ListIndexOutOfBoundsException {
    //always use braces even for single line block of code
    if(current.nextNode == null && k != 0) {
        throw new ListIndexOutOfBoundsException();
    }
    if(k == 0) {
        ListNode l = new ListNode(obj);
        l.nextNode = current.nextNode;
        current.nextNode = l;
        //stopping the recursion
        return;
    }
    current = current.nextNode;
    //decrease k by 1 before calling your method recursively
    k--;
    addAtRec(obj, k, current);
}

这不是主要问题的一部分，但是 IMO 您在列表中添加节点的方法应该属于List该类而不是ListNode. 请记住，保存节点并决定如何绑定它们的数据结构将是List，而不是节点本身。

于 2013-06-23T14:37:54.380 回答