Рекурсия и LinkedList в Java

Question

Хорошо, скажем, у меня есть функция, которая ищет определенное слово в пользовательском классе LinkedList:

public LinkedList find(String word) {
    if (this.word.equals(word))
        return this;
    if (next==null)
        return null;
    if (next.find(word)==next)
        return next;
    return null;
}

Этот код работает нормально, однако он возвращает ПЕРВЫЙ найденный объект, который соответствует критериям. Что если я захочу вернуть найденный последний объект, соответствующий параметру? Мне трудно понять это. Имейте в виду, я хочу использовать рекурсию.

РЕДАКТИРОВАТЬ: Что было бы не так с этим кодом:

public LinkedList findLast(String word) {
    LinkedList temp=new LinkedList(word, null);
    if (next==null && next.word.equals(word))
        return next;
    if (next==null && !next.word.equals(word))
        temp=next.findLast(word);
    return temp;
}

Answer 1

Хорошо, подумайте об этом так: вам нужно повторить вправо до конца списка, а затем позволить возвращаемому значению всплыть.

Таким образом, начало вашего метода должно быть либо рекурсивным вызовом, чтобы посмотреть вниз по списку, либо отметить, что мы находимся в конце списка - что эквивалентно тому, что «дальнейший» результат равен нулю.

Теперь, когда вы возвращаетесь, есть три варианта:

• Вы уже нашли совпадение позже текущей точки - так что верните эту ссылку
• Вы не нашли совпадение (поэтому возвращаемое значение рекурсивного вызова было нулевым) и:
  • Слово текущей точки совпадает, поэтому возвращает текущую точку
  • Текущая точка не совпадает - так что верните ноль

Надеюсь, этого будет достаточно, чтобы привести вас к реализации - если нет, пожалуйста, задавайте больше вопросов. Я бы предпочел не давать полную реализацию, когда это предположительно домашнее задание.

Answer 2

Сохраните ссылку на последнюю найденную и продолжайте вызывать себя до тех пор, пока она не вернет ноль, а затем верните последнюю ссылку.

Обратите внимание, для пояснения: вам придется перебирать свойвесь связанный список (если у вас нет двунаправленного списка), чтобы достичь этого - сохраняйте ссылку каждый раз, когда вы находите совпадение (но просто перезаписывайте одну и ту же ссылку каждый раз) - затем возвращайте то, что ссылка удерживает, как только вы достигнетеконец этого списка.

public class LinkedList {

  private static int uniqueIdCounter = 0;

  private final String word;
  private int uniqueId;
  private LinkedList next = null;

  public LinkedList( String word ) {

    this.word = word;
    this.uniqueId = uniqueIdCounter++;
  }

  @Override
  public String toString() {

    return this.word + "(" + this.uniqueId + ")";
  }



  public void setNext( LinkedList next ) {

    this.next = next;
  }

  public LinkedList find( String word ) {

    return this.find( word, null );
  }

  public LinkedList find( String word, LinkedList result ) {

    if( this.word.equals( word ) ) {
        result = this;
    }

    if( this.next != null ) {

        result = this.next.find(word, result);
    }

    return result;
  }

  public static void main(String[] args) {

    LinkedList head = new LinkedList( "A");
    System.out.println( "Head is: " + head );

    LinkedList B = new LinkedList( "B" );
    head.setNext( B );
    System.out.println( "B is: " + B );

    LinkedList A2 = new LinkedList( "A" );
    B.setNext( A2 );
    System.out.println( "A2 is: " + A2 );

    LinkedList last = head.find( "A" );
    System.out.println( "Last is: " + last );
  }

}

А вот вывод:

Голова: A (0)

B: B (1)

А2: A (2)

Последний: A (2)

Answer 3

Каждая прямая рекурсивная функция имеет два места для некоторых полезных действий: перед дальнейшим вызовом метода и после:

  function(n){
    doBefore(n);
    function(n+1)
    doAfter(n)
  }

doBefore () выполняется «на обратном пути», doAfter () выполняется «на обратном пути». Теперь ваш алгоритм проверяет равенство слов на пути вперед. Вы должны изменить свой алгоритм так, чтобы эта проверка выполнялась на обратном пути.

Answer 4

public LinkedList find(String word, LinkedList result) {
   if (this.word.equals(word))
        result = this;
   if (next != null )
        return next.find(word, result)
   return result;

Двухстрочный:

public LinkedList find(String word, LinkedList result) {
     result = this.word.equals(word) ? this : result;
     return next == null ? result : next.find(word, result);

@ fprime: Ya, объяснение: запомните результат, замените его на более поздний результат, верните в конце.* Метод с одним аргументом:

public LinkedList find(String word){
   result = this.word.equals(word) ? this : null;
   if(next != null)
      previous = next.find(word);
      return (previous != null) ? previous : result 
   else 
      return result;

Answer 5

public LinkedList find(String word) {
  if(this.word.equals(word)) return this;
  return next==null?null:next.find(word);
}

public LinkedList rfind(String word) {
  if(next != null) {
    LinkedList res = next.rfind(word);
    if(res != null) return res;
  }
  return this.word.equals(word)?this:null;
}

Answer 6

Начнем с того, что ваш начальный поиск (строковое слово) не работает правильно.

Ваше первое, если утверждение идеально. Это ваш базовый случай успеха.

Ваше второе утверждение if также идеально. Это ваш базовый случай неудачи.

Твой третий, где ты сойдешь с рельсов. Вы обработали все (в данном случае оба) базовые случаи, теперь все, что осталось, это рекурсивный случай. Вам не нужно ничего проверять здесь. next.find (word) вернет правильный ответ, успех или неудача.

Что касается findLast (Строковое слово), я не могу добавить много к тому, что сказал Джон Скит. О единственном совете, который я могу добавить, чтобы узел никогда не проверял своего соседа. Каждый узел должен только когда-либо проверять себя. Вы должны увидеть множество this.word.equals(word), но никогда next.word.equals(word).

Answer 7

Просто беги назад от хвоста.

public LinkedList find(String word) {
        if (this.word.equals(word))
            return this;
        if (prev==null)
            return null;
        if (prev.find(word)==prev)
            return prev;
        return null;
}