Рекурсия при слиянии связанных списков
Я начинаю понимать рекурсию,
Я прикрепил рекурсивный код для объединения двух отсортированных связанных списков,
Моя проблема в том, что я понимаю, что temp возвращает значение temp -> (first (or) second), как только первое или второе становится нулевым, но я не могу понять тот факт, что,
Скажем, например, если у меня 5 -> 10 -> 15 -> 20.
Последняя функция возвращает 15 -> 20, которые затем объединяются как root.next-> temp, но после этого шага, когда я возвращаю temp, почему возвращается корневое значение. т.е. 10 -> 15 -> 20, когда я ожидаю, что будет возвращена только температура.
Пожалуйста, найдите код,
/**
*
*/
*
*
*/
public class MergeLinkedLists {
static class Node {
int data;
Node next;
public Node(int value) {
this.data = value;
}
}
Node root;
/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
MergeLinkedLists s1 = new MergeLinkedLists();
s1.root = new Node(0);
Node n1 = new Node(10);
//n1.next = new Node(20);
//n1.next.next = new Node(30);
Node n2 = new Node(5);
n2.next = new Node(15);
//n2.next.next = new Node(50);
Node result = sortedLists(n1, n2, s1.root);
while (result != null) {
System.out.print(result.data + "--->");
result = result.next;
}
}
/**
* @param n1
* @param n2
* @param root2
*/
private static Node sortedLists(Node n1, Node n2, Node root) {
// TODO Auto-generated method stub
Node temp = root;
Node first = n1; // 10 20 30
Node second = n2; // 5 15 50
if (first == null) {
temp.next = second;
return temp;
} else if (second == null) {
temp.next = first;
return temp;
}
else if (first.data < second.data) {
temp = new Node(first.data);
first = first.next;
} else {
temp = new Node(second.data);
second = second.next;
}
sortedLists(first, second, temp);
root.next = temp;
System.out.println("The Temp Data is ::::"+temp.data);
return temp;
}
}
Ответы 1
Потому что tempявляется в данном случае корневое значение. Не волнуйтесь, это единственное, что вам нужно понять, чтобы понять саму рекурсию.
Отличная возможность понять функциональность вашего кода - использовать отладчик. Установите точку останова для вызова функции, и вы можете пошагово выполнять программу, одновременно наблюдая за изменением переменных.
Помимо этого, давайте посмотрим на ваш код.
Важно отметить, что всякий раз, когда вы вызываете свой sortedLists(first, second, temp);, указатель будет попадать в него, пока функция не завершится (то есть, когда он вернет temp). Вы вызовете эту функцию несколько раз по мере продолжения работы программы, чтобы она глубже погрузилась в свою собственную функцию.
Затем он передает информацию шаг за шагом на уровне до тех пор, пока первый вызов sortedLists(first, second, temp); не завершится, и это будет в вашем основном методе Node result = sortedLists(n1, n2, s1.root);.
Я постараюсь обойтись вашим примером:
Node result = sortedLists(n1, n2, s1.root);вызывается в методеmain(). Итак, корень равен 0, и у вас есть узлы 10 и 5,15.При первом вызове
sortedLists()temp становится 5, аsecondтеперь несет 15, потому чтоfirst.data > second.data.В НАСТОЯЩЕЕ ВРЕМЯ Вы снова вызываете метод
sortedLists(), но с новыми значениями: теперь корень равен 5, первое остается 10, а второе - 15. Мы выполняем шаг внутри функции и начинаем с новых значений:- из-за
first.data < second.dataзначение temp становится равным 10, теперь значение first равно нулю. - и снова: мы получили еще один звонок на
sortedLists(). Мы передаем значения:first = null second = 15 root = 10функции и идем на один шаг глубже.- поскольку
firstтеперь равен нулю,temp.nextбудетsecond(15) - temp теперь выглядит так: 10-> 15 и мы возвращаемся. (это первый раз, когда
sortedLists()отключается!)
- поскольку
- Теперь мы вернулись сюда и можем продолжить работу с
root.next = temp;. Помните, какая временная температура была в этом контексте? темп был 10, но он был обновлен функцией выше. Новыйtemp- это 10-> 15, поэтому нашrootвыглядит так: 5-> 10-> 15. - Затем вы печатаете заголовок temp, равный 10. Эта функция также завершается.
- из-за
теперь мы вернулись к нашему первому вызову и посмотрим, что произойдет: в 3.3 мы обновили его корень. Корнем 3.3 был temp из 3, потому что мы вызвали
sortedLists(first, second, temp)(temp действует как корень, потому что последний аргумент этой функции -Node root).Подводя итог: наш корень по-прежнему равен 0, а наша темп - 5-> 10-> 15.
root.nextнаходится после этого присвоения 0-> 5-> 10-> 15. Теперь корень, который вы объявили в своем классе над основным методом, имеет значение.мы возвращаем темп, равный 5-> 10-> 15, и все готово.
Теперь мы можем перейти к основному методу и распечатать результаты.
Чтобы избавиться от ---> при отсутствии result.next, вы можете обработать нулевое значение следующим образом:
while (result != null) {
if (result.next != null)
System.out.print(result.data + "--->");
else System.out.println(result.data);
result = result.next;
}
Надеюсь, это поможет немного разобраться в рекурсии.
Привет, e.Fro! Большое спасибо за ваше предложение, у меня есть небольшое сомнение в шаге 4, где вы говорите, что корень 3.3 равен temp из 3 ... Я понимаю ... но когда вызов функции 3.3 завершается, почему возвращается корневое значение .... где я возвращаю только temp. (10-> 15) .... все значения возвращаются в предыдущую вызывающую функцию .... Заранее спасибо.
Я предполагаю, что вся концепция основана на передаче по значению, поскольку корневое значение вызываемой функции обновляется, оно отражается обратно в временном значении вызывающей функции. Пожалуйста, поправьте меня, если я ошибаюсь!
Об объектах в Java следует помнить, что они уникальны, если вы их не воссоздаете (новый объект ()). Итак, ваша функция передает временный объект, а вызываемая функция назначает объект такой же корневым. Но сам объект остается прежним. Таким образом, если вы измените его, вы не просто измените его значение, ваша операция повлияет на весь объект. Это огромное преимущество, так как вы можете сэкономить много места. Таким образом, нет необходимости возвращать, поэтому вы не обрабатываете возвраты в рекурсии. Вы просто манипулируете самим объектом
Этот подход называется на месте и также используется для быстрой сортировки. В контексте списков понравившихся это очень полезно использовать, потому что вы не хотите создавать новые элементы для манипуляций. Я надеюсь, что смогу вам немного помочь с этим. en.m.wikipedia.org/wiki/In-place_algorithm
Я рекомендую использовать отладчик в вашем методе, чтобы увидеть, когда меняются временные объекты на верхних уровнях. Думаю, это очень поможет.
Большое спасибо ! e.Fro
Добро пожаловать в SO! Эта функция написана довольно запутанно, но, насколько я могу судить, работает отлично. Можете прояснить, в чем ваша проблема? Ваши возвращаемые значения здесь не имеют значения, за исключением первого вызова функции, который возвращает правильный результат (следующее значение фиктивного корня, то есть
root.next) в основную область видимости.