1

はい、これは私の宿題プロジェクトの 1 つです。単一リンク リストに基づいて循環リンク リストを実装することです。それは非常に単純で、コードは読みやすいです。ゲッターとセッター、および私的なビジネスを避けるために、私の属性はすべて公開されています。このプロジェクトの目的にはpublicで十分です。

nItemsカウンター (リスト内の項目の数) とリンク ヘッドを属性フィールドで初期化しましたが、後でコンストラクター内で初期化することで変更します。

私のstep()メソッドはまったく機能していないようです。コンパイラが一瞬フリーズした後、何も表示されません。step() メソッドを 4 回呼び出すと、次のように動作します。

List: 40 80 30 20 10 70 50 
List: 80 30 20 10 70 50 40 
List: 30 20 10 70 50 40 80 
List: 20 10 70 50 40 80 30

Find()メソッドは正常に機能します。つまり、検索している値がリンク リスト内にある場合に限ります。そうでないと永遠に続きます。これが私のリストである場合、そこにない値を検索するとfind()メソッドに何が起こるか (私はそれを段階的にデバッグしました):

70 60 50 40 30 20 10 10 10 10 10 10 10 10...and 10 forever

原因:検索しているキー値が存在しない場合、while ループから抜け出せないため、current = current.nextが永遠に繰り返されます。

while(current.dData != key) {
current = current.next;

私の削除メソッドは、私が望んでいたように値60を削除したと言いますが、これは私が得たものです:

Deleted link with key 60
70 60 40 30 20 10       // lie! it deletes 50 instead of 60

私の display() と 私の insert() メソッドも見てください。私には問題ないように見えますが、間違っている可能性があり、それが find() および delete() メソッドで発生しているすべての問題の原因である可能性があります。

よろしくお願いします!!!

class Link {
    public int dData;
    public Link next;

    public Link(int dd) {
        dData = dd;
    }

    public void displayLink() {
        System.out.print(dData + " ");
    }
}

class CircList {
    public Link head = null;
    int nItems = 0;

    public boolean isEmpty() {
        return (nItems == 0);
    }
    // INSERT
    public void insert(int key) { 

        Link current = new Link(key);
        if(isEmpty())
            head = current;

        current.next = head;
        head = current;
        nItems++;
    }
    // STEP
    public void step() {
        Link current = head;
        do {
            current = current.next;
        } while(current != head);
    }
    // FIND
    public Link find (int key) {
        Link current = head;
        while(current.dData != key) {
            current = current.next;
        }
        return current;
    }
     // DELETE
    public Link delete(int key) {
    Link current = head;
    while(current.dData != key) {
        current = current.next;
    }
    if(current == head)
        head = head.next;
    else {
        current.next = current.next.next;
        nItems--;
    }
    return current;
}
    // DISPLAY
    public void displayList() {
        Link current = head; // start at beginning
        int counter = nItems;
        while(true) {
            if(counter != 0) {
                current.displayLink();
                current = current.next; // move to next link
                counter--;
            }
            else 
                break;
        }
    }
}

class CircListApp {
    public static void main(String[] args) {
    Link f, d;
    CircList theList = new CircList();


    theList.insert(10);      // insert items
    theList.insert(20);
    theList.insert(30);
    theList.insert(40);
    theList.insert(50);
    theList.insert(60);
    theList.insert(70);

    //System.out.println(theList.nItems + " ");
    theList.displayList();              // display list

    System.out.println("");

    f = theList.find(30);               // find item
    if( f != null)
       System.out.println("Found link with key " + f.dData);
    else
       System.out.println("Can't find link with key 30");

//    theList.step();

//
//    System.out.println("Inserting link with key 80");
//    theList.insert(80);
//    theList.displayList();              // display list
//
    d = theList.delete(60);             // delete item

    if( d != null )
       System.out.println("Deleted link with key " + d.dData);
    else
       System.out.println("Can't delete link with key 60");
    theList.displayList();              // display list
//
//    f = theList.find(99);               // find item
//    if( f != null)
//       System.out.println("Found link with key " + f.dData);
//    else
//       System.out.println("Can't find link with key 99" );
//    theList.displayList();              // display list
//
//    d = theList.delete(13);             // delete item
//    if( d != null )
//       System.out.println("Deleted link with key " + d.dData);
//    else
//       System.out.println("Can't delete link with key 13");
//    theList.displayList();              // display list
//
//    System.out.println("Stepping through list");
//    for(int j=0; j<theList.getSize; j++)
//       {
//       theList.step();
//       theList.displayList();
//       }
//
//    System.out.println("Will delete and step one by one");
//    while(theList.isEmpty() == false)
//       {
//       theList.delete();
//       theList.step();
//       theList.displayList();
//       }
    }  // end main()

}
4

1 に答える 1

1

「step」メソッドへ: current というローカル参照を作成します。これは、最初は head を指します。後

current = current.next

head の後継者を参照します。そして次のステップで、それはその後継者を参照します。ただし、これはローカル参照であるため、リスト内の何も変更しません。

あなたがしなければならないことは、私があなたの望む出力から推測するように、次のように簡単です

if( head != null && head.next != null )
    head = head.next

次：あなたのfindメソッドについて：あなたのループ条件から、キーがリストにない場合、それが永遠に実行されることは明らかです.これはあなたの唯一の破壊条件だからです. リスト内のすべての項目を確認したら、停止するメカニズムを考えてください。ヒント: 自分のバージョンの step() メソッドで行ったことを見てください。

あなたの削除方法へ：最初の部分は（部分的に）大丈夫です（あなたの検索方法と同じ無限ループの問題があります）。現在のデータがキーと等しくなるまで、リストを反復処理します。それはいいです。

しかし今、 current は削除したい要素への参照です。しかし、あなたがしているのは、current.next を current.next.next に設定することです。これは、current 自体ではなく、current の後継を削除していることを意味します! キーを検索するループでは、predecessor.next を current.next に変更できるように、前任者を追跡する必要があります。これが本当にやりたいことです。

そしてもちろん、それが削除しようとしているヘッドであるかどうかを確認する必要があります。そうであれば、それを先行または後続のいずれかに設定する必要があります。

最後に、insert() メソッドに問題があることがわかりました。新しく挿入された要素がヘッドを指すようにし、それを新しいヘッドにするため、これがどのように循環リンクリストを生成できるかわかりませんが、それを指すものは何もありません。単一リンクリストのみを作成しますか? ヘッドの「前」に新しいアイテムを挿入します（ current.next = head ）が、ヘッドの前の先行者が新しいアイテム current を指すようにする必要があります。

于 2010-11-16T18:17:47.380 に答える