0

对于作业，我被告知要编写自定义链表的插入方法（按顺序）。我写了基本案例，但我仍然不明白递归案例。我知道我刚刚问过如何编写 contains 方法并且有人帮了我，但在那种情况下，我不必像在此方法中那样对列表进行任何修改。请帮助我了解导致我的链接列表覆盖的原因以及是否有更简单的方法来简化我的代码。

这是我的代码：

public class OrderedList {

private Node first;

//Constructor
public OrderedList() {
    this.first = null;
}

//Return the number of items in the list
public int size() {
    int counter = 0;
    Node pointer = this.first;
    while (pointer != null) {
        counter++;
        pointer = pointer.next;
    }
    return counter;
}

//Return an array of copies of the stored elements
public Comparable[] getStore() {

    Comparable[] elements = new Comparable[size()];
    Node pointer = this.first;
    if (this.first == null) {
        return elements;
    } else {
        int i = 0;
        while (pointer != null) {
            elements[i] = pointer.data;
            pointer = pointer.next;
            i++;
        }
        return elements;
    }

}
//true iff item matches a stored element
//Recursive

public boolean contains(Comparable item) {

    return containsHelper(this.first, item);

}

private boolean containsHelper(Node node, Comparable item) {
    //base case
    if (node == null) {
        return false;
    } else {
        if (node.data.compareTo(item) == 0) {
            return true;
        }

        return containsHelper(node.next, item);
    }

}
//Add item preserving the order of the elements
//Recursive

public void insert(Comparable item) {

    insertHelper(this.first, item);

}

public void insertHelper(Node pointer, Comparable item) {
    //Base case
    Node store = new Node(item);

    if (pointer == null) {
        store.next = this.first;
        this.first = store;

        return;
    }
    if (pointer.data.compareTo(item) > 0 ) {
        store.next = pointer;


        return;
    }
    if (pointer.data.compareTo(item) < 0 && pointer.next == null) {
        store.next = pointer.next;
        pointer.next = store;

        return;

    } else {

        Node save = this.first;
        this.first = this.first.next;

        insertHelper(this.first, item);

        if (pointer.data.compareTo(item) > 0) {
            save.next = store;
            this.first = save;
        } else {
            save.next = pointer;
            this.first = save;
        }

    }

}
4

1 回答 1

1

一开始我只给你部分答案。认为这是一个线索。然后还有更多的线索。在找到完整答案之前，看看你是否能弄清楚。

线索 1

这部分代码不能在递归方法中，因为它引用了链表的头部。您的递归正在向下移动列表，将其分解为头部和其余部分，决定是否在头部插入，如果插入必须在其余部分中，则递归。

if (pointer == null) {
    store.next = this.first;
    this.first = store;

    return;
}

这应该稍作修改，以便它可以进入insert()处理整个列表的方法。

为什么？

因为这段代码处理整个列表并提出问题，“这个列表是空的吗？”

线索 2

现在，对于这部分代码：

if (pointer.data.compareTo(item) > 0 ) {
    store.next = pointer;
    return;
}

注意它是如何引用整个列表的。这是一件坏事。

它提出了一个问题，“新项目（要插入的）是否应该放在当前头项目的前面？”

如果答案是肯定的，它需要将它插入到当前头部的前面，让当前头部像以前一样附加链表的当前剩余部分，并返回一些让调用代码附加新排列的链表剩余部分的东西。

if (pointer.data.compareTo(item) > 0 ) {
    store.next = pointer; // new item goes in front of this part of list
    return store;
}

线索 3

现在，让我们跳到这部分代码：

Node save = this.first;
this.first = this.first.next;

insertHelper(this.first, item);

if (pointer.data.compareTo(item) > 0) {
    save.next = store;
    this.first = save;
} else {
    save.next = pointer;
    this.first = save;
}

这段代码不问任何问题。它只是递归，因为我们知道不需要对当前链表的头部进行任何更改。当我们递归时，我们将链表的其余部分传递给它，并告诉它修复它。我们不在乎如何，因为我们相信它会通过在正确的位置插入新项目来修复列表的其余部分。

所以这就是我们要做的：

Node rest = insertHelper(pointer.next, item);
pointer.next = rest;
return pointer;

线索 4

这部分代码是最后要考虑的部分：

if (pointer.data.compareTo(item) < 0 && pointer.next == null) {
    store.next = pointer.next;
    pointer.next = store;

    return;

}

现在，想想你为什么要再次比较它。前面的代码测试了该项目是否需要排在链表其余部分的前面。答案是否定的。

这意味着只剩下两种可能的情况。

要么列表中没有任何内容......我们必须将新项目放在最后。

或者列表中有一些东西......并且线索3通过递归处理。

所以这部分变得更简单了：

if (pointer.next == null) {
    return store;
}

我们所要做的就是返回新节点，它将成为新的“列表的其余部分”，而不是列表的其余部分中没有任何内容。

再注

请记住，方法签名必须更改为如下所示：

/**
 * Insert the 'item' into the linked list beginning with the supplied node, 'pointer'
 * @returns the new, modified linked list, with the new item in it.
 */
public Node insertHelper(Node pointer, Comparable item) {

整个东西

这包括对“插入”方法的更改：

public void insert(Comparable item) {
   // if there isn't anything in the list, the new item becomes the whole list
   if (first == null) {
        Node store = new Node(item);
        store.next = null;
        this.first = store;
        return;
    }

    // Otherwise let the helper fix up the list for us to store away
    this.first = insertHelper(this.first, item);
}

public Node insertHelper(Node pointer, Comparable item) {
    Node store = new Node(item);

    if (pointer.data.compareTo(item) > 0 ) {
        store.next = pointer; // new item goes in front of this part of list
        return store;
    }

    if (pointer.next == null) {
        return store; // new item becomes this part of the list
    }

    // The head of this part of the list is ok, fix the rest of the list

    pointer.next = insertHelper(pointer.next, item);
    return pointer;
}

进一步的评论

还有另一种方法可以做到这一点，您将第一个节点存储在某个其他类中，每个节点Node只存储一个指向列表其余部分的指针（as next）。

然后你有一个方法insert知道它什么时候被调用它不能为空，因为如果它为空你就不能调用它。

因此，没有测试第一个在内部为空insert。但这意味着调用者必须执行以下操作：

Node item = new Node(data);
if (list != null) {
    list.insert(item);
} else {
    list = item;
}

插入方法如下所示：

if (this.next == null || this.data > item.data) { // pseudo code for greater than
    item.next = this.next;
    this.next = item;
    return;
}
this.next.insert(item);

就是这样。

于 2013-07-22T21:26:09.273 回答