0

ノードからのデータをスワップしてソートする二重リンクリストのJavaでの挿入ソートについて、次のルーチンを作成しました。これは正常に機能します。しかし、私は挿入ソートを実現するために実際にノードリンクを交換する方法を理解しようとしています。多くのオプションを試しましたが、ノードが参照しているオブジェクト参照であるため、それらを変更するとリストが台無しになり、すべてが失敗します。任意のポインタをいただければ幸いです。

ノードクラス（内部クラス）：

   private class Node {
    T data;
    Node next;
    Node prev;
}

ソートルーチン

   public void sort() {
    if(isEmpty()) {
        throw new RuntimeException("List is empty");
    }
    Node current = head;
    while(current != null) {
        for(Node prev=current; prev.prev != null; prev = prev.prev) {
            if(prev.data.compareTo(prev.prev.data) <= 0) {
                T tmp = prev.data;
                prev.data = prev.prev.data;
                prev.prev.data = tmp;
            }
        }
        current = current.next;
    }
}

編集1：

ノードを交換する方法を提供してくれたlhuangに感謝します。できます。実際の答えは、Javaがオブジェクトではなく値で参照をコピーして渡すという事実にあります（http://www.javaworld.com/javaqa/2000-05/03-qa-0526-pass.htmlを参照）。したがって、同じ場所で試行するのではなく、ノードスワッピングを他の方法に渡す必要があります。したがって、スワッピングされる2つのノード以外の残りのノードには影響しません。

ルーチンを次のように変更しました

public void sort() {
    if(isEmpty()) {
        throw new RuntimeException("List is empty");
    }
    Node current = top;
    while(current != null) {
        for(Node prev=current; prev != null && prev.prev != null; prev = prev.prev) {
            if(prev.data.compareTo(prev.prev.data) <= 0) {
                swap(prev,prev.prev);
            }
        }
        current = current.next;
    }
}

このロジックを使用する際の最後の問題は、スワップされたときに電流が常に遅れており、同じ2つのノードがこのロジックで2回処理されることです。それを軽減する方法、つまりスワップ後に元の場所に電流を戻す方法はありますか？

4

2 に答える 2

2

それに応じて、node1とnode2の前のノードと次のノードを更新する必要があります。

1、1つのノードがヘッドの場合、ヘッドを更新します。

2、node1がnode2の直前にある場合、node1.prev=node2.prevを更新することはできません。リストに回覧を導入します。

public void swap(Node node1, Node node2) {
    if (node1 == null || node2 == null) {
        throw new IllegalArgumentException(
                "The nodes couldn't be null");
    }

    if (node1 == node2) {
        return;
    }

    // make sure node1 is before node2
    if (node1.getPrev() == node2) {
        Node temp = node2;
        node2 = node1;
        node1 = temp;
    }

    Node node1Prev = node1.getPrev();
    Node node1Next = node1.getNext();
    Node node2Prev = node2.getPrev();
    Node node2Next = node2.getNext();

    node1.setNext(node2Next);
    if (node2Next != null) {
        node2Next.setPrev(node1);
    }

    node2.setPrev(node1Prev);
    if (node1Prev != null) {
        node1Prev.setNext(node2);
    }

    if (node1 == node2Prev) {
        node1.setPrev(node2);
        node2.setNext(node1);
    } else {
        node1.setPrev(node2Prev);
        if (node2Prev != null) {
            node2Prev.setNext(node1);
        }

        node2.setNext(node1Next);
        if (node1Next != null) {
            node1Next.setPrev(node2);
        }
    }

    if (node1 == head) {
        head = node2;
    } else if (node2 == head) {
        head = node1;
    }
}

質問2については、スワップの前にprevを確認できます。currentの場合は、currentをprev.prevに設定します。

while(current != null) {
    for(Node prev=current; prev != null && prev.prev != null; prev = prev.prev) {
        if(prev.data.compareTo(prev.prev.data) <= 0) {
            if (prev==current) {
                current=prev.prev;
            }
            swap(prev,prev.prev);
        }
    }
    current = current.next;
}

ちなみに、スワップ操作を減らすこともできます。リンクリストを並べ替えているので、要素の削除と挿入は非常に簡単です。だから、現在の適切な場所を見つけてください。元の場所から削除して、そこに挿入します。もちろん、いくつかの詳細に注意する必要があります。

于 2013-03-11T04:49:29.607 に答える
0

データだけでなく、ノード参照を割り当てます。スワップされたノード自体だけでなく、両方のスワップされたノードの左右のノードの「次」と「前」を必ず更新してください。そして最後に、スワップした後、反復が正しいノードで続行されることを確認してください。

于 2013-03-11T03:47:45.910 に答える