代码之家  ›  专栏  ›  技术社区  ›  nkint

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

  •  2
  • nkint  · 技术社区  · 14 年前

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

    我知道如何和一个递归的访客一起访问DAG, 但是我无法找到一个简单而干净的结构来实现迭代器方法 next() hasNext() .

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

    DagElement parent
    boolean alreadyVisited
    

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

    有什么建议吗?

    1 回复  |  直到 14 年前
        1
  •  1
  •   Bert F    14 年前

    将递归启发式转换为迭代启发式的快速方法是使用(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)、子项排队的顺序以及子项排队的时间调整访问顺序。有些访问命令可能需要在bat(构造函数)中以正确的顺序对整个节点集进行排队,这并不让我吃惊。

    推荐文章