1

我在编写一种在跳过列表中查找元素的方法时遇到了一些困难。

我正在尝试实现它，如果我们正在搜索一个元素并且该元素在列表中不存在，则返回下一个最大值；这将使其成为插入的理想选择。但是，如果找到该元素，则返回该元素。

我将其用于我的remove(T key)方法；如果我们找到该元素，则将其删除。如果它不在列表中，throw new java.util.NoSuchElementException().

虽然我当前的实现可以很好地插入，但我发现它在查找现有元素时不起作用——相反，它将获得下一个值。（从技术上讲，它不应该适用于插入，但确实如此）。

********************** SkipList (size = 3) Level: 2 (null), , , (5) Level: 1 (null), (3), (4), (5) **********************

以上是跳过列表当前的样子。

下面是我正在制作的跳过列表的结构。左手标记是数据为空的节点；我们还有一个幻像节点作为头部；幻像头帮助我们跟踪跳过列表中的当前级别数。结构图

private Node<T> search(T key) {
    Node<T> node = head;
    boolean found = false;

    while (!found) {
        while (compare(node.getNext().getData(), key) <= 0) {
            node = node.getNext();
        }
        if (node.getDown() != null) {
            node = node.getDown();
        } else {
            node = node.getNext();
            found = true;
        }
    }
    return node;
}

在其当前状态下，如果我们尝试search(4)，返回的节点将是5，即使4它在列表中。

4

1 回答 1

0

我在这里看到了许多问题。

  1. 您实际上在哪里返回值？return node;我看不到 return 声明，尽管我认为您只是在底部遗漏了 a 。

  2. 您永远不会验证最终值是否确实是您正在寻找的。你需要一些方法来表明没有找到一个值，我假设？

  3. 如果您无法关闭，您目前只是决定您找到了该节点。

我认为您需要重新考虑一下算法。试试这个代码：

private Node<T> search(T key) {
    Node<T> node = head;
    boolean found = false;

    while (!found) {
        //special case to return a node containing null - indicates value not in list
        if (node == null) return new Node(null);
        //We found it!
        else if (node.getData().equals(key)) found = true;
        //Go to the next one over if it's not too high.
        else if (node.getNext() != null && compare(node.getNext().getData(), key) <= 0) node = node.getNext();
        //It was too high, so go down instead.
        else node = node.getDown();
    }
    return node;
}

请注意在内部 while 循环中检查空条件 - 这可以防止您调用getData()不存在的下一个节点，这将导致空指针异常。另请注意您如何不检查空值是否下降。这是因为只有在它不在列表中时才会遇到它，因此开始时的特殊情况将在下次循环执行时捕获该空值。

您还可以调整它检查值是否相等的方式。我使用过.equals，但您可以将其更改为使用该compare方法，具体取决于您检查相等性的方式。

于 2015-03-03T18:19:26.387 回答