我想要一个数据结构的迭代器。 现在我不知道什么是数据结构,也许它是一个DAG(有向无环图),但也许它也可能是一个链表。 所以我想把它包装成一个迭代器,现在不考虑特定的数据结构。
我知道如何使用类似递归的访问者访问 DAG,
但我想不出一个简单干净的结构来实现迭代器方法 next()
和 hasNext()
。
在迭代器中,我创建了一个当前节点实例,并使用 for 循环遍历所有子节点,然后返回到父节点。需要一个“已经访问过”的标志。
所以我的 DagElement
有更多的属性:
DagElement parent
boolean alreadyVisited
我认为这不是一个干净的解决方案。
有什么建议吗?
最佳答案
将递归启发式转换为迭代启发式的快速而肮脏的方法是使用 (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)、 child 排队的顺序以及他们排队的时间调整访问顺序。我不会感到惊讶,某些访问顺序可能需要立即(在构造函数中)以正确的顺序对整个节点集进行排队。
关于java - 如何在 Java 中为 DAG 结构创建迭代器包装器?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/4184797/