0

//双方向リンク リストの挿入メソッドの Java コードを書きましたが、 //実行すると無限ループが発生します。バグを見つけようとしていますが、今のところ見つかりません。助言がありますか？//ヘルパー関数を呼び出しています

 public IntList insertionSort ( ) {
    DListNode soFar = null;
    for (DListNode p=myHead; p!=null; p=p.myNext) {
        soFar = insert (p, soFar);
    }
    return new IntList (soFar);
}


// values will be in decreasing order.
private DListNode insert (DListNode p, DListNode head) {
    DListNode q=new DListNode(p.myItem);
    if(head==null){
        head=q;
        return head;
    }
    if(q.myItem>=head.myItem){
        DListNode te=head;
        q.myNext=te;
        te.myPrev=q;
        q=head;
        return head;
    }
    DListNode a;
    boolean found=false;
    for(a=head; a!=null;){
        if(a.myItem<q.myItem){
            found=true;
            break;
        }
        else{
            a=a.myNext;
        }
}
    if(found==false){
        DListNode temp=myTail;
        temp.myNext=q;
        q.myPrev=temp;
        myTail=q;
        return head;
    }
    if(found==true){
    DListNode t;
    t=a.myPrev;
    a.myPrev=q;
    t.myNext=q;
    q.myPrev=t;
    q.myNext=a;
}
    return head;

}

4

1 に答える 1

1

あなたのコードは少し読みにくいですが、いくつか問題があることに気付きました

最初: リストの先頭に数字を挿入する場合の処理​​:

if(q.myItem>=head.myItem){
        DListNode te=head;
        q.myNext=te;
        te.myPrev=q;
        q=head;
        return head;
    }

特にラインq=head;とリターン。新しいヘッドなので、ヘッドではなく元q=headに戻す必要があります。あなたの意図は だったと思います。現在のコードは基本的に新しいノードを前面に追加しますが、更新されたヘッドを返すことはないため、ある意味で「エッジから落ちる」ことになります。qqhead=q; return head;

2番目myTail：元のリストのように保持しているノード参照があると想定しmyHeadています。作成しているソート済みリストのように使用したくないと思います。新しいリストに挿入する場所を探してループするときは、それを使用してテール参照を決定し、代わりにそれを使用します。

DListNode lastCompared = null;
for(a=head; a!=null; a=a.myNext) {
    lastCompared = a;
    if(a.myItem<q.myItem) {
        break;
        }
    }
if( a )
    {
    // insert node before a
    ...
    }
else
    {
    // smallest value yet, throw on the end
    lastCompared.myNext = q;
    q.myPrev = lastCompared;
    return head;
    }

最後に、DListNode のコンストラクターで myPrev と myNext が正しく null に初期化されていることを確認します。

免責事項ここに追加したコードをテストする機会はありませんでしたが、少なくとも解決策について考えるきっかけになれば幸いです。

文体に関するいくつかのメモ (単なる補足):

  1. 私の意見では、繰り返される if->return 形式は最もクリーンではありません。私は通常、関数の出口点を制限しようとします
  2. 多くの中間変数が使用されており、名前は非常にあいまいです。少なくとも、よりわかりやすい変数名を使用してみてください。
  3. コメントは常に良い考えです。コードが何をしているのかを説明するだけではなく、思考プロセスと何を達成しようとしているのかを伝えるようにしてください。
于 2013-08-08T05:25:19.823 に答える