如何在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結構創建迭代器包裝？

回答

相關問題