Как создать оболочку итератора для структуры DAG в Java?

Я хочу иметь итератор над структурой данных. Пока я не знаю, какая структура данных, возможно, это DAG (направленный ациклический граф), но, возможно, это может быть также связанный список. Итак, я хочу обернуть его в итератор и теперь не думаю о конкретной структуре данных.Как создать оболочку итератора для структуры DAG в Java?

Я знаю, как посетить DAG с рекурсивным, как посетителем, , но я не могу понять простую и чистую структуру для реализации методов итератора next() и hasNext().

Внутри итератора Я создал экземпляр текущего узла и перебираю цикл for для всех детей, а затем возвращаюсь к родительскому. Требуется флаг «уже посетил». Так что мой DagElement имеет следующие дополнительные атрибуты:

DagElement parent 
boolean alreadyVisited

Я не думаю, что это чистое решение.

Любые советы?

источник

2010-11-15 nkint

Реализация итератора, естественно, полностью зависит от структуры данных, а также от того, в каком порядке вы хотите итерации. Решите эти два вопроса и обновите вопрос. Во всяком случае, 'ужеVisited' не должен быть членом структуры данных, вместо этого сохраняйте' Set 'ссылок на посещенные узлы в итераторе. –

привет, спасибо за комментарий, уже выбранный в наборе действительно хорош \ n. до сих пор я знаю: моя структура данных - это дерево, и я посещаю «preorder» (посещают root, посещают дочерние элементы). Но все может измениться, и я хочу оставить ясный способ изменить его. поэтому, возможно, в будущем кто-то захочет взять мой код, использовать другую структуру данных (скажем, связанный список) и другой порядок (скажем, обратный от хвоста к голове) и написать код для его ListElement реализует элемент, а его ListIterator реализует итератор и используйте мой код, который зависит только от интерфейса Element и Iterator. я в неправильном направлении? – nkint

Как я уже сказал, реализация итератора ПОЛНОСТЬЮ зависит от реализации структуры данных. Если бы вы могли сделать общий итератор, который мог бы перебирать любую структуру данных, кто-то уже это сделал бы. –

Быстрый и грязный способ преобразования рекурсивной эвристики в итеративный - использовать стек (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

Как создать оболочку итератора для структуры DAG в Java?

ответ

Смежные вопросы