0

请建议我解决以下无限循环。类对象包含相同类型对象的集合。在转换为 String 时，该对象调用集合中每个对象的 toString。因此它导致无限循环。请不要使用任何静态变量。

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

我将假设您有意创建了一个循环数据结构作为示例，并且您确实希望能够生成循环图的字符串渲染。

答案并不简单。

首先，您需要在不进入循环的情况下执行（可能）循环图的遍历。基本算法是这样的：

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地图允许遍历不访问它已经访问过的节点。

问题的第二部分是修改代码以进行渲染。在这一点上，您必须决定如何在图形中呈现循环......在输出是字符序列的上下文中。

显而易见的方法是给事物贴上标签。例如，我们可以写一个渲染l1为

1: [2: [1] ]

（每个列表都表示为a [ ... ]，n:表示后面的东西有一个“标签” n。当我们遇到一个我们已经看到的“节点”时，我们使用一个标签；例如1上面的第二个指的是我们标记的列表作为1。）

给定这样的表示，我们可以修改doTravers方法以获取额外的StringBuilder参数，并更改IdentityHashMap以将标签字符串保存为值。其余的非常简单。

这种方法的问题是：

  • 渲染不是很可读......尤其是对于更大和/或更复杂的图形结构。
  • 该算法需要知道如何对所涉及的特定类型进行遍历和渲染。很难以通用的、独立于数据结构的方式实现这一点。
于 2012-11-14T16:02:03.717 回答
0

是我还是递归调用 ToString() 方法总是递归调用自己，并且没有一个递归调用可以停止的情况？如果是这样，您需要一些条件来退出递归调用自身。

于 2012-11-14T15:31:12.220 回答
0

There is nothing wrong with the toString() method. By default, it prints all elements in a collection by iterating over them (look in the implementation of AbstractCollection.toString()). The problem that you are having is that by adding a list as an element to the other (and the other way around). When l1 is printed, it calls the toString() method of l2 (because that it is first element), which in turns prints the element one by one, and since l2's first element is l1 it calls the toString() method of it, and so on...

In short, don't short-circuit lists by adding them as elements to each other.

于 2012-11-14T15:46:27.147 回答