Не итеративный эквивалент для обращения к связанному списку
Я читаю про обход списка в книге Алгоритмов Роберта Седвика. Определения функций приведены ниже. Упоминается, что можно иметь функции traverse и remove, которые могут иметь итерационные счетчики, но traverseR не может иметь. Мой вопрос, почему traverseR не может иметь итеративный счетчик? Возможно ли, что если рекурсивный вызов не является концом функции, то есть, как и в случае обхода, то у нас не может быть итеративного, верно ли мое понимание?
Спасибо за ваше время и помощь.
void traverse(link h, void visit(link))
{
if (h == 0) return;
visit(h);
traverse(h->next, visit);
}
void traverseR(link h, void visit(link))
{
if (h == 0) return;
traverseR(h->next, visit);
visit(h);
}
void remove(link& x, Item v)
{
while (x != 0 && x->item == v)
{ link t = x; x = x->next; delete t; }
if (x != 0) remove(x->next, v);
}
Решение
traverseR использует стек вызовов для хранения указателей на все узлы списка, чтобы к ним можно было обращаться в обратном порядке по мере раскрутки стека вызовов.
Чтобы сделать это без стека вызовов (то есть нерекурсивно), вам понадобится некоторая другая структура, подобная стеку, для хранения этих указателей.
Другие функции просто работают с текущим узлом и перемещаются дальше, и нет необходимости хранить что-либо для использования после возврата рекурсивного вызова функции. Это означает, что хвостовая рекурсия может быть заменен циклом (либо путем изменения кода, либо, в зависимости от компилятора, позволяя ему определить, что это возможно, и выполнить само преобразование).
Другие решения
Предполагая, что список является односвязным, невозможно просмотреть его итеративно в обратном порядке, поскольку нет указателя от узла на предыдущий узел.
Что такое рекурсивная реализация traverseR по сути, это то, что он неявно переворачивает список и посещает его в прямом порядке.
Вы могли бы написать итерационную версию traverseR используя стек: в цикле выполняйте итерацию от одного узла к другому, помещая узлы в стек. Когда вы дойдете до конца списка, в другом цикле откройте и посетите узлы, которые вы посетили.
Но это в основном то, что делает рекурсивная версия.
Можно просматривать односвязный список в обратном порядке только с дополнительным пробелом O (1), то есть без стека ранее посещенных узлов. Это, однако, немного сложнее, и нисколько не безопасно.
Хитрость в том, чтобы пройти по списку от начала до конца, перевернуть его на месте, как вы это делаете, а затем переместиться обратно к началу, снова перевернув его на обратном пути.
Поскольку это связанный список, его обратное изменение на месте довольно просто: по мере того, как вы добираетесь до узла, сохраняйте текущее значение его next указатель и замените это адресом предыдущего узла в списке (см. код для более подробной информации):
void traverseR(node *list, void (*visit)(node *)) {
node *prev = nullptr;
node *curr = list;
node *next;
if (!curr)
return;
// Traverse forwards, reversing list in-place as we go.
do {
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
} while (curr->next);
// fix up so we have a fully reversed list
curr->next = prev;
prev = nullptr;
// Traverse the reversed list, visiting each node and reversing again
do {
visit(curr);
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
} while (curr->next);
}
Как почти все, что связано со связанными списками, я чувствую себя обязанным добавить, что (по крайней мере, IMO) они почти всегда должны рассматриваться как чисто интеллектуальное упражнение. Использование их в реальном коде обычно чистый убыток. Как правило, в итоге получается код, который медленен, хрупок и труден для понимания, а также обычно тратит довольно много памяти (если данные, которые вы храните в каждом узле, не достаточно велики, указатель может часто использовать столько же места, сколько и данные сам).
Мой вопрос, почему traverseR не может иметь итеративный счетчик? Возможно ли, что если рекурсивный вызов не является концом функции, то есть, как и в случае обхода, то у нас не может быть итеративного, верно ли мое понимание?
Правильный. Функции traverse а также remove покончить с призывом к себе. Они являются хвостовыми рекурсивными функциями. Звонок в traverseR сам по себе не в конце функции; traverseR не хвостовой рекурсив
В целом рекурсия требует затрат на создание и последующее уничтожение стековых фреймов. Этого можно полностью избежать с помощью хвостовых рекурсивных функций, превратив рекурсию в итерацию. Большинство компиляторов распознают хвостовые рекурсивные функции и преобразуют рекурсию в итерацию.
Можно написать итерационную версию traverseR в зависимости от того, что вы подразумеваете под итеративным. Если вы ограничены одним проходом по списку, это невозможно. Но если вы можете пожертвовать много времени обработки, это может быть сделано. Он использует меньше памяти в классическом соотношении скорости и памяти.
void traverseRI(link h, void visit(link))
{
if (h == 0) return;
link last = 0;
while (last != h)
{
link test = h;
while (test->next != last)
{
test = test->next;
}
visit(test);
last = test;
}
}