0

私は、LinkedList を使用して並べ替えるクイック 並べ替えの演習に取り組んでいます (効率的ではなく、本当に無意味であることはわかっています。これはクラス用です)。Quick Sort メソッドの仕組みと、3 つの戦略の中央値が理解できました。ただし、たとえば、私のコードは特定の長さでのみ正しく機能しています。

これはうまくいきます：

7 6 5 4 3 2 1、ピボット = 4

7 6 5、ピボット = 6 | 3 2 1、ピボット = 2

さて、そうではないものについては、つまり。

5 4 3 2 1、ピボット = 3

5 4、エラーをスローします | 2 1エラーをスローします。

これが私が持っているコードです:

LinkedList の中間ノードを検索します。

public Node findMiddleNode() {
    Node node1 = first;
    Node node2 = first;
    while(node2.getNext() != null && node2.getNext().getNext()!= null) {
        node1 = node1.getNext();
        node2 = node2.getNext().getNext();
    }
    return node1;
}

最初、中間、および最後のノードの中央値を見つけます。

public Node medianOfThree() {
    Node firstNode = first;
    Node lastNode = last;
    Node middleNode = findMiddleNode();

    if((firstNode.getData() - middleNode.getData()) * (lastNode.getData() - firstNode.getData()) >= 0) {
        return firstNode;
    } else if((middleNode.getData() - firstNode.getData()) * (lastNode.getData() - middleNode.getData()) >= 0) {
        return middleNode;
    } else {
        return lastNode;
    }
}

リストからピボットを削除します。これは壊れるメソッドです。

private Node chooseAndRemovePivot() {
    Node pivot = medianOfThree();
    Node previous = first;

    // If the pivot is the first Node.
    if(previous == pivot) {
        first = previous.getNext();
    }

    // Gets the last Node before the pivot
    while(previous.getNext() != pivot) {
        previous = previous.getNext();
    }

    previous.setNext(pivot.getNext());
    pivot.setNext(null);
    size--;
    if (size == 0)
        last = null;
    return pivot;
}

ここで何がうまくいかないのか誰でも指摘できますか、それは私が犯している単純な間違いだと確信しています。

編集:解決策;

メソッド chooseAndRemovePivot(); で

// If the pivot is the first Node.
if(previous == pivot) {
    first = previous.getNext();
} else {
    // Gets the last Node before the pivot
    while(previous.getNext() != pivot) {
        previous = previous.getNext();
    }
}

これにより、すべての長さで機能します。

4

2 に答える 2

2

このmedianOfThree関数はpivot == first、長さ 2 のリストを返します。したがって、このコードは次のようになります。

// Gets the last Node before the pivot
while(previous.getNext() != pivot) {
    previous = previous.getNext();
}

...終了条件を見つけることは決してなく、代わりにprevious = nullリストの最後に到達したときに割り当てます。次に、次の反復でNullPointerException.

于 2013-06-11T21:16:16.750 に答える
0

エラーは findMiddleNode() 関数にあると思います。具体的には、node2.getNext.getNext() は、node2.getNext() が null でないことを確認しません。

アイテムの数が偶数のリストでは、 node2.getNext().getNext() が最後まで実行されます。エラーである Null.getNext() にステートメントを効果的に減らします。

たとえば、リストを使用して

first -> a -> b -> null
  1. 最初の node1 と node2 は「first.
  2. 次に、node1 が a になり、node2 が b になります。
  3. 次に、node1 が b になり、node2 が b.getNext().getNext()、つまり Null.getNext になります。

node2.getNext().getNext() は常に null に到達するため、このアルゴリズムは奇数長のリストに対して機能します。

于 2013-06-11T21:23:52.210 に答える