0 
public class LinkedList {

 Object contents;
 LinkedList next = null;

public boolean equals(Object item) {
   return (this == item) || ((item instanceof LinkedList) &&  this.equals((LinkedList)item)); 
  }

 public boolean equals(LinkedList item) { 
   return myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next); 
 }

} 

public class myUtil{
  public static boolean equals(Object x, Object y) {
    return (x == y) || (x != null && x.equals(y));
 }
}

main(){
 LinkedList myList = new LinkedList();
 myList.next = new LinkedList();
 LinkedList head = myList.next;
 myList.next = head;
}

ここで循環リンクリストを作成したと思います。だから私がしたことは、equals メソッドを上書きして、循環参照が確実に処理されるようにすることです。

何らかの理由で LinkedList.equals が返されないようです...それは私の循環リンクリストのためですか、それともいくつかの条件がありませんか?

4

5 に答える 5

2

このコードの主な問題は、比較が循環参照で終了せず、すべてのコンテンツ フィールドが等しい場合に永久にループすることです。それは常に次の比較に続き、次のアイテムは常にそこにあるため (円であるため)、これは永遠に続きます。

myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next);

この問題を解決するための最も簡単な方法は、ブール値の非公開の「visited」フィールドを各リスト アイテムに追加することです。比較する場合は、比較後の各項目に訪問済みを設定します。両方が訪問されておらず、同じである場合は、続行します。1 つしかアクセスされていない場合、リストは同一ではありません。両方が訪問された場合、到達可能なリスト全体を比較したことになります。一般に、リストにループを含めることは悪い考えであり、ループを検出するための特別なアルゴリズムが存在します。これは紛らわしいトピックになる可能性があります。これは、問題をさらに理解するのに役立つ可能性のあるループ検出のカバレッジです。訪問済みフィールドを使用する場合は、equals() の別のループですべての設定を解除して、再度実行できるようにする必要があることに注意してください。

別の注意として、テスト用にリスト ノードのコンテンツ フィールドを初期化しません。null に初期化されるため、ここでは問題ありませんが、通常はすべてのフィールドを明示的に初期化することをお勧めします。

equals(Object item)一般的に言えば、オーバーライドも必要ありません。試す

public boolean equals(LinkedList item){
  if (this == item){
     return true; // It's the same object
  }

  // Add some null checks here, I'm lazy

  if (this.visited && item.visited && this.contents.equals(item.contents){
     this.visited = false; //Unset
     item.visited = false;
     return true;
  }
  if (this.visited && !item.visited){
      this.visited = false;
      return false;
  }
  if (!this.visited && item.visited){
      item.visited = false;
      return false;
  }
  if (!this.visited && !item.visited && this.visited.contents.equals(item.contents){
      this.visited = true;
      item.visited = true;
      boolean ret = this.next.equals(item.next);
      this.visited = false;
      item.visited = false;
      return ret;
  }

  // Contents not equal
  return false;
}

これは、いくつかの基本的な再帰でバックトラックして設定を解除します。私は明らかにこれをコンパイルしていませんが、それが要点だと思います（エラーが多すぎないことを願っています）

于 2012-06-20T14:18:39.833 に答える
1

2 つの問題があります。まず、循環リンク リストがありません。次のコードは、list1.next = list2、list2.next = null の 2 つのリストを作成します。サークルが作成されていません。

LinkedList myList = new LinkedList();
myList.next = new LinkedList();
LinkedList head = myList.next;
myList.next = head;

第二に、循環リンクリストを DID した場合、終了条件に到達しないため、以下は無限ループを生成します。これは、循環リンクリンクでnextは決してnull.

public boolean equals(Object item) {
  return (this == item) || ((item instanceof LinkedList) &&       
    this.equals((LinkedList)item)); 
}

public boolean equals(LinkedList item) { 
   return myUtil.equals(this.contents, item.contents) && myUtil.equals(this.next, item.next); 
}

これを効果的に行うには、このメカニズムが非公開であり、他のユーザーに公開されていない場合でも、非循環的な方法でリストを反復するいくつかのメカニズムを提供する必要があります。これを行う 1 つの方法は、単一のノードを「ルート」としてマークすることです。

于 2012-06-20T14:16:50.087 に答える
0 
return myUtil.equals(this.contents, item.contents) 
&& myUtil.equals(this.next, item.next);

&& の 2 番目の式を実行すると、つまり、次のmyUtil.equals(this.next, item.next);行を実行する myUtil.equals メソッドに入ります。

return (x == y) || (x != null && x.equals(y));

次に、の .equals() メソッドを使用します。このメソッドは、循環的にリンクされたリストがあるため、xその のプロセスを繰り返します。item.next

于 2012-06-20T14:10:18.703 に答える
0

これにより、無限ループが発生します。これは、コードに次の理由があるためです。

public static boolean equals(Object x, Object y) {
        return (x == y) || (x != null && x.equals(y));
    }

はx.equals(y)再び呼び出します：

public boolean equals(LinkedList item) {
        return myUtil.equals(this.contents, item.contents)
                && myUtil.equals(this.next, item.next);
    }

ただし、 を実行している場合myList1.equals(myList1)は(x==y)inmyUtils.equals()が返さtrueれるため無限ループにはなりません。同じオブジェクトを比較しても無限ループにはなりません。

ただし、異なるオブジェクトを比較すると、無限ループに陥ります。

これは循環リストの問題ではなく、選択したコード設計が原因です。

于 2012-06-20T14:26:40.890 に答える