0

CYCLIC LINKED LIST をソートするためのクイックソートを実装しようとしています!

DoublyLinkedListを含む がありますListElements。

にはListElementElement First があり、その前身と後継者への参照があります。

たとえばDoubleLinkyedList、 in にはListElement最初のものが含まれます。First は、first.prev または first.next で参照できます。

リンク リストの最後の要素には、最初の要素への参照がありlast = first.prevます。

私の問題は、エラーが発生し続けることですが、どれが正確かわかりません。これは、終わりのないループのようなものであり、端末が正確な例外を出力していないためです。

ソート操作を実装するクラス Sorter.java のコード:

package ads1ss13.pa;


public class Sorter {

public DoublyLinkedList quicksort(DoublyLinkedList in, int numOfElements) {


    System.out.println("STARTE sort() in quicksorT()");

    in = Sort(in, in.first.getId(), in.first.prev.getId());

    return in;
}

public DoublyLinkedList Sort(DoublyLinkedList in, int l, int r)
{
    System.out.println("Sort()");

    l = in.first.getId();
    r = in.first.prev.getId();
    ListElement pivot = null;

    System.out.println("l: "+l+"; r: "+r);

    if(l < r)
    {
        pivot = in.first.prev;
    }

    System.out.println("pivot: "+pivot);

    System.out.println("Ausfuehren der Partition mit l, r, pivot");

    int p = Partition(in, l, r, pivot);

    System.out.println("Ausgabe aus Partition p: "+p);

    System.out.println("Ausführen der Sort() mit l und p-1 für r");


    Sort(in, l, p-1);

    System.out.println("Ausführen der Sort() mit p+1 für l, und r");
    Sort(in, p+1, r);

    return in;
}

public int Partition(DoublyLinkedList in, int l, int r, ListElement pivot)
{
    System.out.println("Partition()");

    int i = l;
    int j = r;
    ListElement r_ListElement = in.first.prev;
    ListElement i_element = in.first.next;
    ListElement j_element = pivot;

    System.out.println("i: "+i+"; j: "+j+", pivot: "+j_element);

    do {

        do {
            i = i + 1;
            i_element = i_element.next;
        } while (i_element.getKey() < pivot.getKey());

        do {
            j = j - 1;
            j_element = j_element.prev; 
        } while (j > i || j_element.getKey() > pivot.getKey());

        if(i_element.getKey() < j_element.getKey())
        {
            swap(in, i_element, j_element);
        }

    } while (i < j);

    swap(in, i_element, r_ListElement);

    return i;
}

public void swap(DoublyLinkedList in, ListElement links, ListElement rechts)
{
    if(links.next.getId()==rechts.getId()){

        ListElement Lprev = links.prev;
        ListElement Rnext = rechts.next;
        Lprev.next=rechts;
        rechts.prev=Lprev;
        links.next=Rnext;
        Rnext.prev=links;
        links.prev=rechts;
        rechts.next=links;

        }

        else if(rechts.next.getId()==links.getId())
        {
            swap(in, rechts, links);
        }
        else
        {
            ListElement Lprev=links.prev;
            ListElement Lnext = links.next; 
            links.next=rechts.next;
            links.prev=rechts.prev;
            rechts.next=Lnext;
            rechts.prev=Lprev; 
            links.prev.next=links;
            links.next.prev=links;
            rechts.prev.next=rechts;
            rechts.next.prev=rechts;
        }


        if(in.first.getId()==links.getId())
        {
            in.first = rechts;
        }
        else if(in.first.getId()==rechts.getId())
        {
            in.first = links;

        }
}
}

私のコードが2回目の再帰呼び出しに切り替わらない理由sort()と、どのエラーが返されるのか分かりますか?

4

1 に答える 1

0

コードをデバッガーに投入できないため、これを分析するのは困難です。ただし、正しい軌道に乗るためのいくつかのこと：

問題1。

int landを引数として取りますがint r、すぐに上書きします。

l = in.first.getId();
r = in.first.prev.getId();

何度も何度も再起動するため、これはほぼ間違いなくやりたいことではありません。これがおそらく無限ループの原因です。

問題2。

if(l < r)
{
    pivot = in.first.prev;
}

の場合l >= r、ピボットはnullであり、これによりNullPointerException

問題 3。

パーティション ロジックが間違っています。ネストされたループを持つ必要はありません。要素をピボットと比較するとすぐに、スワップをすぐに行うことができます (ピボットのどちら側にあると想定されているかは常にわかります)。

于 2013-05-08T14:18:37.057 に答える