5

コードに問題があります。追加、削除、変更、マージなどを行う単一リンク リスト クラスを作成しましたが、単純なバブル ソートを試みているところ、リストが正しくソートされていません。以下に注意事項を示します。

  • リンクリストのカスタム実装です
  • シングル リンク リストのノードには、顧客のすべてのデータを含む CustomerFile オブジェクトと、リスト内の次の項目への「次の」ノード ポインタの 2 つが含まれます。
  • リストは、各ノードの顧客ファイルに保存されている姓の昇順 (AZ) でソートされます。
  • レコード追加機能は、リストの正しい位置にノードを挿入するため、最初にリストをソートする必要はありません。ただし、プログラムの一部として姓が変更された場合は、リストを再度ソートする必要があります。
  • 新しいリストを作成せず、そのリストでこの挿入レコードを再利用して新しいリストを作成します。これはメモリを集中的に使用するため、私のタスクはできるだけ効率的にする必要があるためです。
  • リンクされたリストの構造そのものを変更することはできません-決定されており、配列などに変更するには遠すぎます
  • リストにはヘッド ノードがあり、次の項目がありますがテール ノードはありません。リストの終わりを示すために指定された NULL ネクスト ポインターがあります。

コード

public static void sortList()
{
    if (isEmpty() == true)
    {
        System.out.println("Cannot sort - the list is empty");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("List sorted");
    }
    else
    {
        Node current = getHead().getNext();
        CustomerFile tempDat;
        boolean swapDone = true;
        while (swapDone)
        {
            current = getHead().getNext();
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null &&
                    current.getData().getSurname().compareTo(
                        current.getNext().getData().getSurname()) >0)
                {
                    tempDat = current.getData();
                    current.setData(current.getNext().getData());
                    current.getNext().setData(tempDat);
                    swapDone = true;
                }
                current = current.getNext();
            }
        }
        if (getHead().getData().getSurname().compareTo(
            getHead().getNext().getData().getSurname()) >0)
        {
            current = getHead().getNext();
            getHead().setNext(current.getNext());
            setHead(current);
        }
    }
}

フィードバックをいただければ幸いです

4

3 に答える 3

4

あなたのコードは奇妙な混合物であり、ほとんどの場合データを交換しますが、リンクを切り替えることによってヘッドを特別に次のデータと交換しようとします。

別の回答で述べたように、この最後のスワップは正しく実装されていませんが、データをスワップすることによって何かをしている場合、実際には頭を特別に扱う理由はありません。

あなたがしなければならないのは、外側のループの先頭でリストの各トラバーサルを開始することです。

これにより、実用的なソリューションが得られます。

public void sortList()
{
    if (isEmpty())
    {
        System.out.println("An empty list is already sorted");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("A one-element list is already sorted");
    }
    else
    {
        Node current = getHead();
        boolean swapDone = true;
        while (swapDone)
        {
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null && current.getData().getSurname().compareTo(current.getNext().getData().getSurname()) >0)
                {
                    CustomerFile tempDat = current.getData();
                    current.setData(current.getNext().getData());
                    current.getNext().setData(tempDat);
                    swapDone = true;
                }
                current = current.getNext();
            }
            current = getHead();
        }
    }
}

コメントに記載されているように、静的としてどのように機能するかが明確ではなかったため、これを非静的にしました。あなたはそれをあなたの文脈で静的にすることができるかもしれません。

他にもいくつかマイナーな変更を加えました。次のようなコードで条件を確認する必要はありません。

if (isEmpty() == true)

Javaでは、これは完全に同等です

if (isEmpty())

またtempDat、使用場所の外で宣言する必要はありません。

于 2012-12-22T15:33:56.453 に答える
1

ソートに頭を含めていません。

public static void sortList()
{
    if (isEmpty() == true)
    {
        System.out.println("Cannot sort - the list is empty");
    }
    else if (getHead().getNext() == null)
    {
        System.out.println("List sorted");
    }
    else
    {
        Node current = getHead();
        // Node current = getHead().getNext();
        CustomerFile tempDat;
        boolean swapDone = true;
        while (swapDone)
        {
            current = getHead().getNext();
            swapDone = false;
            while (current != null)
            {
                if (current.getNext() != null && current.getData().getSurname().compareTo(current.getNext().getData().getSurname()) >0)
                {
                    tempDat = current.getData(); // td -> objectA, cd -> objectA
                    current.setData(current.getNext().getData()); // cd -> objectB
                    current.getNext().setData(tempDat); // nd -> td -> objectA
                    swapDone = true;
                }
                current = current.getNext();
            }
        }
        //if (getHead().getData().getSurname().compareTo(getHead().getNext().getData().getSurname()) >0)
        //{
        //  current = getHead().getNext(); // current -> head+1
        //  getHead().setNext(current.getNext()); //head+1 -> head+2
        //  setHead(current); // head -> head+1
        //}
    }
}

上記のコメントアウトされたコードにもエラーがあります。そのコードを適用すると、ノードがドロップされます。

// list: a -> b -> c -> d
current = getHead().getNext(); // current = b
getHead().setNext(current.getNext()); // a -> c 
setHead(current); // head = b
// list: b -> c -> d
// and nothing points to 'a' anymore

データを交換するのではなく、ノードを交換してみてください。そのアプローチを行えば、より良い解決策が見つかるはずです。

于 2012-12-21T22:48:11.523 に答える
1

ここでの主な問題は、あなたがから始めることだと思います

current = getHead().getNext()

このコードでは、head をソート プロセスから完全に除外し、ここにあるデータをリストの反対側に移動する必要がある場合がありますが、この場合は常に head 内のデータのいずれかになります。要素、またはヘッド ノードの直後のデータになります (後者は最後の if ステートメントによるものです)。

代わりに、リストの先頭から始めてみて、何が表示されるかを確認してください。

于 2012-12-21T23:30:23.363 に答える