如何在Java中为DAG结构创建迭代器包装？

我想要一个数据结构的迭代器。现在我不知道数据结构是什么，可能它是一个DAG（有向无环图），但也许它也可能是一个链表。所以我想把它包装到一个迭代器中，现在不要考虑特定的数据结构。如何在Java中为DAG结构创建迭代器包装？

我知道如何访问一个DAG使用递归般的游客，但我不能想出一个简单干净的结构实现迭代方法next()和hasNext()。

在迭代器内部，我创建了一个当前节点实例，并对所有子节点进行循环遍历，然后返回父节点。一个'已经访问'的标志是必要的。所以我DagElement具有以下多个属性：

DagElement parent 
boolean alreadyVisited

我不认为这是一个干净的解决方案。

有什么建议吗？

来源

2010-11-15 nkint

迭代器的实现自然完全取决于数据结构，也取决于您想要迭代的顺序。决定这两点并更新问题。无论如何，'alreadyVisited'不应该是数据结构的成员，而应该在迭代器中保留对被访问节点的引用的Set。 – 2010-11-15 13:32:20

嗨，感谢您的评论，已经访问过一个集合非常好\ n。直到现在我知道：我的数据结构是一棵树，我正在访问“预订”（拜访根，拜访孩子）。但事情可能会改变，我想留下一个明确的方式来改变它。所以，也许将来有人会拿我的代码，使用另一个数据结构（比如一个链表）和另一个命令（比如说，从尾到头反转），为他的ListElement implements Element编写代码，并且他的ListIterator实现迭代器，以及使用我的代码只依赖于Element和Iterator接口。我在错误的方向？ – nkint 2010-11-15 13:56:42

正如我所说，迭代器的实现取决于数据结构的实现。如果你可以创建一个可以迭代任何数据结构的通用迭代器，那么有人已经完成了它。 – 2010-11-15 14:12:05

将递归启发式转换为迭代启发式的快捷方法是使用（LIFO）堆栈或（LILO）队列来保存“未采用的道路” - 找到但尚未采用的路径。在这种情况下，迭代器将具有堆栈或队列实例变量。喜欢的东西：

class DagIterator<T> 
    extends Iterator<T> { 

     private Stack<DagNode<T>> nodes; 

     private DagIterator(Dag<T> dag) { 
      nodes.push(dag.getRootNode()); 
     } 

     public boolean hasNext() { 
      return ! nodes.isEmpty();  
     } 

     public T next() { 
      final DagNode node = nodes.pop(); 
      for (final DagNode child : node.getChildren()) { 
       nodes.push(child); 
      } 
      return node.getValue(); 
     } 

    }

你调整基于数据结构（LIFO或LILO）探望令，该命令在孩子们排队，而当他们排队。令人惊讶的是，一些访问命令可能需要按正确的顺序排队整个节点集合（在构造函数中）。

来源

2010-11-15 14:38:27

如何在Java中为DAG结构创建迭代器包装？

回答

相关问题