1

私は Java でいくつかの演習を行ってきましたが、今はそのような問題で立ち往生しています - 私のリストは正しく動作しません。私はそれが正しく機能しないと確信しており、循環単一リンクリストを正しい方法でremove実装するために（アドバイスまたはコードで）私を助けることができるかもしれません。他の機能が正常に動作するかどうかはわかりませんが、最善を尽くしました。

これが私のコードです：

import java.util.*;


public class Node {
    private Object value;
    private Object nextValue;

    private Node next;


    public Node(int data) {
        this.value = data;
        this.next = null;
    }

    public Object getValue() {
        return this.value;
    }

    public Node nextItem() {
        return this.next;   
    }

    public void setNextItem(Node nextItem) {
        this.next = (Node) nextItem;
        this.next.setValue(nextItem.getValue());
    }


    public void setValue(Object arg0) {
        this.value = arg0;
    }

}

    -------------------------------------------------------------------

   import java.util.*;



public class CircularList  {
    private Object[] array;
    private int arrSize;
    private int index;
    private Node head;
    private Node tail;
    public CircularList() {
        head = null;
        tail = null;
    }



    public boolean add(Node item) {

        if (item == null) {
            throw new NullPointerException("the item is null!!!");
        }


        if (head == null) {
            head = item;
            head.setNextItem(head);
            arrSize++;

            return true;
        } 

        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == item.getValue()) {
                throw new IllegalArgumentException("the element already " +
                        "exists!");
            }
            cur = cur.nextItem();
        }

            head.setNextItem(item);
            item.setNextItem(head);
            arrSize++;

            return true;

    }


    public Node getFirst() {
        return head;
    }


    public void insertAfter(Node item, Node nextItem) {

        if ((item == null) || (nextItem == null)) {
            throw new NullPointerException("the item is nul!!!");
        } else if (this.contains(nextItem) == true) {
            throw new IllegalArgumentException("the item already exists!");
        } 

        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == item.getValue()) {
                nextItem.setNextItem(item.nextItem());
                item.setNextItem(nextItem);
            } else {
                cur = cur.nextItem();
            }
        }

    }


    public boolean remove(Node item) {

        if(item == head) {
            Node cur = head;
            for(int i = 0; i < arrSize-1; i++) {
                cur = cur.nextItem();
            }

            head = head.nextItem();

            for(int i = 0; i < arrSize; i++) {
                cur = cur.nextItem();
            }
            arrSize--;
            return true;
        }

        Node cur = head;
        int counter = 0;
        while(cur.nextItem() != head) {
            if(cur == item) {
                item = null;
                cur = cur.nextItem();
                while(cur.nextItem() != head) {
                    cur.setNextItem(cur.nextItem().nextItem());
                }
            return true;    
            }
            cur = cur.nextItem();
        }



        return false;
    }

    public int size() {

        return arrSize;
    }

    public boolean contains(Object o) {
        if ((o == null) && (arrSize == 0)) {
            return false;
        }
        Node cur = head;
        while(cur.nextItem() != head) {
            if(cur.getValue() == o) {
                return true;
            }
            cur = cur.nextItem();
    }


        return false;
    }



}
4

3 に答える 3

0

あなたのコードにはたくさんのことが起こっています、ここにそれのいくつかのためのいくつかのアドバイスがあります：

  1. Nodeクラス：Javaの命名規則：セッターの前に「set」を付けるのと同じように、ゲッターの前に「get：​​」nextItem()を付ける必要がありますgetNextItem()。

  2. また、Nodeクラスでも：私が知る限り、リンクリストのノードの「次の値」フィールドは通常、リスト内の次のノードへの参照であるため、Nodeオブジェクトだけでなく、タイプである必要があります。それはあなたが持っているように動作するはずですが、明示的な入力を使用する方がはるかに安全です。（「オブジェクト」を使用することがリンクリストの次のノードを構築する一般的な方法である場合は、訂正してください。）

  3. の最初のケースではremove()、ヘッドを削除するときに、リストをループして最後の値に到達します。おそらく、その「次の値」を新しいヘッドにリセットしますが、実際には実行していません。あなたはこのようなものが欲しいです：

    if (item == head) {
head = head.nextItem();
for(int i = 0; i < arrSize-1; i++){
cur = cur.nextItem();            
}
}
cur.setNextItem(head);

    2番目のループで何を達成したいのかわかりません。

  4. 2番目のケースremove()：2番目のループで何をしようとしているのかわかりませんwhile-リスト全体のすべてのリンクをリセットしますか？リンクリストの要点は、それを不要にすることです。リンクリスト内のノードを削除しても、実際にはオブジェクトが削除されるわけではありません（したがって、に設定itemする必要はありませんnull）。むしろ、次のように、不要なオブジェクトを「移動」して「無視」し、リストから効果的に削除します。

元のリスト：

[ Value: A; Next: B ] --> [ Value: B; Next: C ] --> [ Value C; Next: D ] ...

ノードBを削除した後：

  [ Value: A; Next: C ] --> [Value C; Next: D ] ...

[ Value: B; Next: C ]まだメモリに存在しますが、それを指しているものはないため、次のガベージコレクションサイクルで削除されます。

実装するには：リストを歩きながら、前にアクセスしたノードへの参照を保持します。次に、探しているアイテムが見つかったら（Thomasが指摘したように、正しい比較を使用して）、次のように設定できますprev.setNextItem(cur.nextItem());（注意：テストされていないコード）。

    Node prev = head;
    Node cur;
    while ((cur = prev.nextItem()) != head) {
    if (cur.equals(item)) {
    prev.setNextItem(cur.getNextItem());
    return true;
    }
    }

これらのヒントが正しい道に沿って役立つことを願っています。

于 2012-03-05T21:10:15.770 に答える
0

ここには、リストを超えたさまざまな問題があります。ノードを == と比較しているようです。このコードは「一致なし」を出力します。

Node n1 = new Node(5);
Node n2 = new Node(5);
if (n1 == n2)
  System.out.println("objects match");
else
  System.out.println("no match");

add() では、リストに 2 つの項目しか持てないように見えるので、

head.setNextItem(item);
item.setNextItem(head);

これである必要があります：

cur.setNextItem(item);
item.setNextItem(head);
于 2012-03-05T20:44:53.117 に答える
0

これらのアルゴリズムの多くは、より単純になる可能性があります。

例：

  public boolean remove(Node item) {
     Node current = head;
     for(int i = 0; i < size; i++) {
       if (current.getNext() == item) {
          current.next = current.getNext().getNext();
          size --;
          return true;
       }
       current = current.getNext()
     }
     return false;
  }
于 2012-03-05T20:02:37.577 に答える