Возвращает количество элементов в связанном списке рекурсивно

У меня есть следующий рекурсивный метод в классе ImageNode, который передается голосом ( - начало связанного списка) из класса Image. Я думал, что мой код будет рекурсивно проходить через каждый узел, увеличивая счет, тогда когда его в конце вернет счет, к сожалению, нет. Где я иду не так?Возвращает количество элементов в связанном списке рекурсивно

private int countRec() { 
    int count = 1; 
    ImageNode node = this; 

    if (node.next != null){ 
     node = node.next; 
     count++; 
     countRec(); 
    } 

    return count; 
}

источник

2014-09-19 Dan_ENZ

'int count = 1;' вы всегда устанавливаете счетчик в 1, увеличивая его и возвращая. – TheLostMind

count не должен быть локальной переменной для вашего метода. – zerocool

. Вы сбрасываете счет с помощью вызова метода, и каждый метод countRec() устанавливает значение «1», чтобы узел «это» содержал один и тот же результат каждый раз, когда –

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

Если следующий узел равен NULL, размер списка равен 1
В противном случае размер равен 1 + от следующего узла.

Итак:

private int countRec() { 
    return next == null ? 1 : 1 + next.countRec(); 
}

Теперь, не позволяет получить список длины 0 конечно ... Вы, вероятно, хотите, чтобы отделить идею списка от узла, в этом случае список классов будет иметь что-то вроде:

public int count() { 
    return head == null ? 0 : head.countRec(); 
}

где значение head является ссылкой на головной узел, если есть один или null иначе.

Конечно, это будет O (n) во времени и. Вы можете получить пространство O (1), используя итерацию вместо рекурсии, и время O (1), просто сохранив размер списка в качестве переменной экземпляра в списке, обновив его, когда вам нужно. Я надеюсь, что этот вопрос был основан на требованиях к образованию, а не в реальном коде, хотя в производственном коде вы просто использовали уже предоставленные коллекции.

источник

2014-09-19 06:19:03

Спасибо! что прекрасно работает, никогда не использовал? раньше, немного запутался относительно того, что? и: делают –

@Dan_ENZ: Это условный оператор - он проверяет условие перед '?', затем оценивает либо второй аргумент, либо третий. Связывался бы с некоторыми документами, но теперь должен сойти с поезда ... –

Никаких забот не рассмотрит. Спасибо за помощь. –

Определение рекурсивной функции определено в терминах самого себя: то есть подсчет элементов в списке равен 0, если пустой список; в противном случае он равен 1 + счет остальным элементам списка.

Целочисленная часть вышеуказанного определения - это то, где производится вызов функции.

источник

2014-09-19 06:24:27

Рекурсивная функция полезна, когда она использует результат дальнейших вызовов для решения своей проблемы (например, индуктивный шаг по математике). Ваша функция не использует возврат для вызова countRec(), и вы все еще пытаетесь решить проблему без помощи рекурсии. Вы можете решить, используя его, как:

if(node.next != null) 
{ 
    node = node.next; 
    count = countRec()+1; 
} 
return count;

Конечно, так как мы говорим о том, чтобы ваш код лучше, вы даже не нужно будет использовать этот node вар, просто делает:

private int countRec() { 

    if (this.next != null) 
     return (this.next.countRec())+1; 
    return 1; 
}

Надеюсь, что это поможет.

источник

2014-09-19 06:32:11

Возвращает количество элементов в связанном списке рекурсивно

ответ

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