Поиск «максимального» символа в связанном списке Java рекурсивно - PullRequest
Новая
       30

Поиск «максимального» символа в связанном списке Java рекурсивно

0 голосов
/ 22 февраля 2020

Я пытаюсь найти «максимальное» значение в связанном списке рекурсивно, используя вспомогательную функцию. Я только начинаю узнавать об этом в своем классе и очень растерялся. У нас есть собственный класс, который определяет тип Node, и еще одна функция для расчета размера Node или связного списка. Я решил эту проблему, когда сравнивал целые числа, но с символами я потерян. Вот мой код: '' '

    static class Node {
        public Node (char item, Node next) { this.item = item; this.next = next; }
        public char item;
        public Node next;
    }

    Node first;   // this is the only instance variable,
                  // the access point to the list

    // size
    //
    // a function to compute the size of the list, using a loop
    //  an empty list has size 0
    public int size () {
        int count = 0;
        for (Node tmp = first; tmp != null; tmp = tmp.next)
            count++;
        return count; 
    }


    /*
     * maxCharacter
     * 
     * a function to compute the 'maximum' character in the list using recursion
     * You will want to create a helper function to
     * do the recursion
     * 
     * precondition: list is not empty 
     * 
     * Examples: 
     * ["ababcdefb"].maxCharacter() == 'f'
     * ["eezzg"].maxCharacter() == 'z'
     * ["a"].maxCharacter() == 'a'
     */
    public char maxCharacter () {

        return maxCharacterHelper(first, first.size());

    }

    public char maxCharacterHelper(Node first, int index) {
        char[] alpha = {'a','b','c','d','e','f','g','h','i','j','k','l','m','n','o','p','q','r','s','t','u','v','w','x','y','z'};
        int max = 0;
        while(index > 0 )
            max = alpha.indexOf(first.item) > max ? first.item : max;
            maxCharacterHelper(first, index-1);
        return max;
    }

' '' Если бы вы могли объяснить, как я рекурсивно проведу список oop, сохраняя при этом самый большой символ, я был бы очень признателен.

Ответы [ 2 ]

1 голос
/ 22 февраля 2020

Золотое правило с рекурсией: «Сначала подумай о базовом случае, а затем напиши о повторении».

В этом случае основой является пустой список. В этом случае максимальное значение - это последнее значение, которое вы видели.

Повторение - это просто вызов остальной части списка с наибольшим значением, которое вы вызвали. 

public static MaxNode(Node n, char currentMax) {
  if (n == null) // base case, we're at the end.
    return currentMax;

  // recurrence
  return MaxNode(n.next, currentMax > n.item ? currentMax : n.item);
}

Для простых значений ASCII вы можете обработать максимум с помощью оператора >.

1 голос
/ 22 февраля 2020

Ваше время l oop сбивает с толку из-за отступа и из-за того, что вы никогда не меняете индекс. Тем не менее, я не думаю, что вам это нужно, если вы собираетесь использовать рекурсию. Как правило, при рекурсии вам необходимо установить sh базовый случай, из которого вы не можете рекурсировать. Для связанного списка естественным базовым случаем является тот, где нет следующего узла, а не на основе индекса. 

if (current.next == null)
    return alpha.indexOf(current.item);

В противном случае объедините возвращаемую рекурсию с текущим значением 

int remainingMax = maxCharacterHelper(current);
int currentValue = alpha.indexOf(current.item);
return (remainingMax > currentValue) ? remainingMax : currentValue;

Здесь вот как бы я это сложил 

//I made it static because it is not a method of a specific Node
public static int maxCharacterHelper(Node currentNode){
   // remaining list includes only current node, so this one has max value
   if (current.next == null)
       return alpha.indexOf(current.item);
   //otherwise take the larger of remaining list and current node
   int remainingMax = maxCharacterHelper(current.next);
   int currentValue = alpha.indexOf(current.item);
   return (remainingMax > currentValue) ? remainingMax : currentValue;
}
...