2

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

我知道如何使用类似递归的访问者来访问 DAG，但我无法找出一个简单而干净的结构来实现迭代器方法next()和hasNext().

在迭代器内部，我创建了一个当前节点实例，并使用 for 循环遍历所有子节点，然后返回父节点。需要一个“已访问”标志。所以我DagElement有这些更多的属性：

DagElement parent
boolean alreadyVisited

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

有什么建议吗？

4

1 回答 1

1

将递归启发式转换为迭代启发式的快速而简单的方法是使用（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-15T14:38:27.983 回答