0

Please suggest me to solve the below infinite loop . Class object contains the collection of same type objects. While converting to String , The object calls the toString of each object in the collection. Hence it leads to infinite loop. Please dont use any static variables.

import java.util.LinkedList;

/**
 *
 * @author ranga
 */
public class MyList  {
    LinkedList<Object> l1,l2;

    MyList() {
        l1 = new LinkedList<Object>();
        l2 = new LinkedList<Object>();
        l2.add(l1);
        l1.add(l2);
    }

    @Override
    public String toString() {
        return l1.toString();
    }

    public static void main(String ...args) {
        MyList m = new MyList();
        System.out.println(m);
    }
}
4

4 に答える 4

2

リンクされたリストをそれ自体に追加しないでください。

于 2012-11-14T15:26:06.380 に答える
1

例として循環データ構造を意図的に作成し、循環グラフの String レンダリングを生成できるようにしたいと仮定します。

答えは簡単ではありません。

まず、ループに入らずに (潜在的に) 巡回グラフの走査を実行する必要があります。基本的なアルゴリズムは次のようになります。

public void traverse(List<?> graph) {
    doTraverse(graph, new IdentityHashMap<?, ?>());
}

private void doTraverse(List<?> graph, IdentityHashMap<?, ?> visited) {
    if (visited.get(graph) == null) {
        visited.put(graph, graph);
        for (Object element : graph) {
            if (element instanceof List<?>) {
                doTraverse((List<?>) element, visited);
            }
        }
    }
}

マップはvisited、トラバーサルが既に訪れたノードを訪れないようにします。

問題の 2 番目の部分は、レンダリングを行うようにコードを変更することです。この時点で、グラフ内のサイクルをどのようにレンダリングするかを決定する必要があります...出力が一連の文字であるというコンテキストで。

明白な方法は、物事にラベルを付けることです。たとえば、のレンダリングを次のように書くことができますl1。

1: [2: [1] ]

(各リストは として表され、次のものに「ラベル」があること[ ... ]を意味します。既に見た「ノード」に遭遇すると、ラベルを使用します。たとえば、上記の 2 番目は、ラベルを付けたリストを参照します。として。）n:n11

そのような表現が与えられた場合、追加の引数doTraversを取るようにメソッドを変更し、ラベル文字列を値として保持するように変更できます。残りは非常に簡単です。StringBuilderIdentityHashMap

このアプローチの問題点は次のとおりです。

  • レンダリングはあまり読みやすくありません...特に大規模および/またはより複雑なグラフ構造の場合。
  • アルゴリズムは、関連する特定のタイプのトラバーサルとレンダリングを行う方法を知る必要があります。これを一般的なデータ構造に依存しない方法で実装することは困難です。
于 2012-11-14T16:02:03.717 に答える
0

それは私ですか、それとも ToString() メソッドを再帰的に呼び出すことは常にそれ自体を再帰的に呼び出しており、その再帰的な呼び出しが停止できる単一のケースはありませんか? もしそうなら、再帰的に自分自身を呼び出すのをやめるための条件が必要です。

于 2012-11-14T15:31:12.220 に答える
0

メソッドに問題はありませんtoString()。デフォルトでは、コレクション内のすべての要素を反復して出力します ( AbstractCollection.toString()の実装を見てください)。あなたが抱えている問題は、リストを要素として他のリストに追加することです（そしてその逆）。が出力されると、(最初の要素であるため)のメソッドがl1呼び出され、要素が 1 つずつ出力されます。toString()l2l2l1toString()

要するに、リストを互いに要素として追加することによってリストを短絡させないでください。

于 2012-11-14T15:46:27.147 に答える