0

这更多是因为我缺乏理解 SortedList 类的能力。我理解的 ListNode：它是一个由两件事组成的节点：一个可比较的对象和一个 ListNode 对象，它本身具有相同的两件事。

我不明白下面的 SortedList 类中的插入和删除方法是如何工作的。理解起来非常复杂。在 SortedList 类中，如果 head 为 null，则指向 curr。curr 不应该为空吗？那么while循环不应该执行，但实际上当我使用println测试执行时它确实执行了。

ListNode 类的代码：

public class ListNode {

    private Comparable data;
    private ListNode next;

    public ListNode() {
        data = null;
        next = null;
    }

    public ListNode(Comparable x) {
        data = x;
        next = null;
    }

    public ListNode(Comparable x, ListNode nextListNode) {
        data = x;
        next = nextListNode;
    }

    public Comparable getData() {
        return data;
    }

    public ListNode getNext() {
        return next;
    }

    public void setData(Comparable x) {
        data = x;
    }

    public void setNext(ListNode nextListNode) {
        next = nextListNode;
    }

}

排序列表的代码：

public class SortedList {

    private ListNode head;

    public SortedList() {
        head = null;
    }

    public void insert(Comparable x) {
        ListNode curr = head, prev = null;
        while (curr != null && x.compareTo(curr.getData()) > 0) {
            prev = curr;
            curr = curr.getNext();
        }
        if (prev == null) {
            head = new ListNode(x, curr);
        } else {
            prev.setNext(new ListNode(x, curr));
        }
    }

    public boolean delete(Comparable x) {
        if (head == null) {
            return false;
        }
        ListNode curr = head, prev = null;
        while (curr != null && x.compareTo(curr.getData()) > 0) {
            prev = curr;
            curr = curr.getNext();
        }
        if (curr == null || x.compareTo(curr.getData()) != 0) {
            return false;
        }
        if (prev == null) {
            head = curr.getNext();
        } else {
            prev.setNext(curr.getNext());
        }
        return true;
    }

    public void output() {
        for (ListNode curr = head; curr != null; curr = curr.getNext()) {
            System.out.println(curr.getData());
        }
    }

}

TestSortedList 的代码：

public class TestSortedList {

    public static void main(String[] args) {
        SortedList list = new SortedList();
        list.insert(5);
        list.insert(1);
        list.insert(10);
        list.insert(3);
        list.insert(7);
        list.output();
        System.out.println(list.delete(5));
        System.out.println(list.delete(5));
        System.out.println(list.delete(1));
        System.out.println(list.delete(10));
        System.out.println(list.delete(11));
    }

}
4

3 回答 3

2

curr是null第一次调用的时间insert。所以while这次被忽略了。

但是当prev == null评估为真时，如果块被执行，本质上是执行这一行：

head = new ListNode(x, curr);

这样，head没有更多的剩余null，任何进一步的调用都insert可能导致while循环被执行。循环是否while会被执行取决于这个表达式：

x.compareTo(curr.getData()) > 0

If true,while被执行，否则不执行。

于 2013-03-17T00:35:41.917 回答
1

在第一条语句中，您的 while 循环具有： 

while(curr != null && x.compareTo(curr.getData()) >0 )

当您调用 x.compareTo(curr.getData()) 时，您将 5 与 null 进行比较，返回 1。大于 0，因此一半的要求为真，但它仍然跳过 while 循环并继续执行

 if (prev == null) {
        head = new ListNode(x, curr);

这个动作给 head 一个值，它不再是 null。所以当你做第二次插入时，你做

ListNode curr = head;

这次 curr 不为空，允许它进入循环

于 2013-03-17T00:20:49.940 回答
1

您需要分解（例如）该insert方法的功能。

  • 新节点将（通常）插入两个节点之间......除非您最终插入列表的开头和结尾。

  • 局部变量初始化设置了一些东西，以便我们开始查看循环的开头。该prev变量将指向插入点之前的节点。该curr变量将指向插入点之后的节点。

  • while循环找到插入点。它遍历列表节点，直到找到一个大于或等于的节点x。插入点在该节点之前。如果列表为空（即为head）null，则插入点是列表的开头。当它完成时（包括它从不运行的情况），prev并且curr将具有最终部分所需的值......

  • prevwhile 循环之后的代码进行插入，在节点和节点之间插入新curr节点。如果prev是null，它必须以不同的方式处理事情。

所以回答你的问题：

但是哪个代码使 curr 不为空呢？

没有代码可以做到这一点。它不需要不为空。

在您实际进行插入的那一点，curr是插入点之后的节点。如果您在列表末尾插入（或插入空列表），则插入点之后没有节点，并且curr将（并且应该）是null.

插入单链表有点棘手，但要记住的关键是任何算法都需要在要插入新节点的位置之前找到并更新节点。删除也是如此。

于 2013-03-17T00:38:53.760 回答