Найти мин в связанном списке - PullRequest
0 голосов
/ 02 мая 2018

Я пытаюсь найти мин в связанном списке вершин. Это то, что я написал, но это ошибочно. Я не получаю ошибку, но моя программа не работает, и я думаю, что это источник ошибки. Что я делаю неправильно?

      Iterator itr = vertices.iterator();
      Vertex smallest= getVertex(s);
      Vertex temp;
      while (itr.hasNext()){
          smallest=(Vertex)itr.next();
           if(itr.hasNext() && vertices.size()> 1 ){//there are at least 2 vertices left
                temp = (Vertex)itr.next();
                if (temp.distance< smallest.distance){
                    smallest = temp;
                }
          }
     }

1 Ответ

0 голосов
/ 02 мая 2018

Проблема в том, что вы потребляете два элемента из итератора на каждой итерации (через itr.next()), так что это означает, что вы сравниваете только некоторые элементы:

1----2----3-----4-----5-----6
\----/    \-----/     \-----/

Вы сравниваете 1 и 2; 3 и 4; 5 и 6; но не 2 и 3; 4 и 5.

Самый простой способ решить эту проблему - сохранить предыдущую вершину:

Vertex prev = itr.next();
while (itr.hasNext()) {
  Vertex current = itr.next();

  // Compare prev and current

  prev = current;
}

Обратите внимание, что вы можете избежать приведений (Vertex), если объявите итератор с параметром типа:

Iterator<Vertex> itr = vertices.iterator();
...