Рекурсивные алгоритмы с односвязными списками
Односвязные списки и рекурсия
Для односвязного списка можно дать просто рекурсивное определение. Односвязный список либо пуст, либо состоит из головы и списка.
L: [],
В данном случае, [] обозначает пустой список. Под пустым списком будем понимать NULL, то есть указатель типа Node, ссылающийся на NULL это тоже список. Под головой будем понимать первый узел списка.
L: H|L.
Из этого определения списка следует примерный алгоритм обработки односвязного списка
f([]) -> <выход из рекурсии>> f(H|L) -> <обработка головы> + <вызов f(L)>.
Конечно, всё зависит от ситуации, и условие выхода из рекурсии может быть совсем другое. Посмотрим теперь несколько простых рекурсивных алгоритмов.
Я далее буду использовать немного странный псевдокод. В нём функция заканчивается точкой, а аргумент проверяется на соответствие шаблону, то есть
f(0) -> 1; f(n) -> n*f(n)-1.
означает, что если аргумент функции равен 0, то произойдёт возврат значения 0, а если аргумент - какое-то число n, то произойдёт возврат произведения функции f с аргументом n-1 и n. Стрелка означает, что происходит возврат значения. Выражение f([]) значит, что функция получила в качестве аргумента пустой список, а f([H|L]) - что функция получила непустой список, в котором к первому узлу мы будем обращаться как к H, а к остальным элементам как к списку с именем L (даже если он пуст).
1. Суммирование значений списка.
Сначала напишем итеративный алгоритм
int sum(const Node *head) { int sum = 0; while (head) { sum += head->value; head = head->next; } return sum; }
Теперь реализуем рекурсивный алгоритм. В псевдокоде
f([]) -> 0; f([H|L]) -> H.value + f(L).
код на си
int sum(Node* head) { if (head == NULL) { return 0; } else { return head->value + sum(head->next); } }
Эту же функцию можно написать и по-другому. Будем передавать ещё один аргумент - ранее вычисленную сумму.
f([], s) -> s; f([H|L], s) -> f(L, s + H.value).
int sum(Node* head, int s) { if (head == NULL) { return s; } else { sum(head->next, s + head->value); } }
Мы свели рекурсивную функцию к хвостовой рекурсии. Теперь можно свести эту функцию обратно к итеративной.
Сведём к циклу
int sum(Node* head, int s) { s = 0; while (1) { if (head == NULL) { return s; } else { s += head->value; head = head->next; } } }
2. Подсчитать количество элементов в списке. Итеративный алгоритм
int count(const Node *head, int key) { int counter = 0; while (head) { if (head->value == key) { counter++; } head = head->next; } return counter; }
Запишем теперь рекурсивный алгоритм в псевдокоде.
f([], key) -> 0; f([H|L], key) -> if (H == key) 1 + f(L, key); else f(L, key).
Реализация на языке си
int count(Node *head, int key) { if (!head) { return 0; } else { if (head->value == key) { return 1 + count(head->next, key); } else { return count(head->next, key); } } }
или так
int count(Node *head, int key) { if (!head) { return 0; } else { return (head->value == key ? 1: 0) + count(head->next, key); } }
Теперь сведём к хвостовой рекурсии
f([], key, count) -> count; f([H|L], key, count) -> if (H == key) f(L, key, count + 1); else f(L, key, count).
Код на си
int count(Node *head, int key, int count) { if (!head) { return count; } else { if (head->value == key) { count(head->next, key, count + 1); } else { count(head->next, key, count); } } }
Теперь сведём обратно к циклу
int count(Node *head, int key, int count) { count = 0; while (1) { if (!head) { return count; } else { if (head->value == key) { count++; } head = head->next; } } }
3. Нахождение максимального элемента списка
f(H)-> H.value; f([H|L]) if (H.value > f(L)) -> H.value.
Код на си
int maxn(Node* head) { if (head->next == NULL) { return head->value; } if (head->value > maxn(head->next)) { return head->value; } }
4. map - отображение. Для начала нам понадобится функция повторения списка. Это достаточно простая функция
Node* repeat(Node* head) { Node* tmp = NULL; if (head == NULL) { return NULL; } tmp = (Node*) malloc(sizeof(Node)); tmp->value = head->value; tmp->next = repeat(head->next); return tmp; }
Функция map применяет к каждому элементу списка функцию и возвращает новый список. Например, если у нас был список
[1, 3, 5, 7, 9]
и мы применили к нему функцию
int dbl(int val) { return val * 2; }
то мы получим новый список
[2, 6, 10, 14, 18]
На основе функции repeat
Node* map(Node *head, int (*fun)(int)) { Node* tmp = NULL; if (head == NULL) { return NULL; } tmp = (Node*) malloc(sizeof(Node)); tmp->value = fun(head->value); tmp->next = map(head->next, fun); return tmp; }
5. Рекурсивный оборот списка. Функция достаточно простая. Нам понадобится новый указатель – новая "голова" списка. Мы должны сначала пройти до конца списка, и только с конца до начала проталкивать новые элементы. Таким образом, push должны быть завершающей командой.
void reverse(Node* head, Node **out) { if (head->next == NULL) { push(out, head->value); return; } push(out, head->value); reverse(head->next, out); }
6. Правоассоциативная свёртка. Пусть у нас имеется список значений вида
[x1, x2, ..., xN]
и мы хотим получить из списка единственное атомарное значение, применяя заданную функцию к списку следующим образом
f(X1, f(x2, f(..., f(XN-1, XN)))),
например, мы хотим применить к списку
[1,2,3,4,5]
операцию суммирования
1+(2+(3+(4+5)))
f(H, g) -> H.value; f([H|L], g)-> g(H.value, f(L, g)).
Код на си
int foldr(Node* head, int (*fun)(int, int)) { if (head->next == NULL) { return head->value; } return fun(head->value, foldr(head->next, fun)); }
Например, можно найти факториал из списка, используя функцию
int mult(int a, int b) { return a * b; }
Или максимальный элемент списка, используя функцию
int maxe(int a, int b) { return a > b ? a : b; }
7. Левоассоциативная свёртка. Работает в обратном порядке, то есть для
[x1, x2, ..., xN]
и мы хотим получить из списка единственное атомарное значение, применяя заданную функцию к списку следующим образом
f(f(f(...f(X1, X2))), xN)
f(H, g) -> H.value; f([H|L], g)-> g(f(L, g), H.value).
Код на си
int foldl(Node* head, int (*fun)(int, int)) { if (head->next == NULL) { return head->value; } return fun(foldl(head->next, fun), head->value); }
Очевидно, что если операция g коммутирует, то левая свёртка равна правой свёртке, но в общем случае они могут давать разный результат.
8. Фильтр. Из названия понятно, что функция получает список и выбрасывает из него все элементы, которые не удовлетворяют условию. По сути - это повторение списка, только с пропуском "плохих" узлов.
Node* filter(Node* head, int (*pred)(int)) { Node* tmp = NULL; if (head == NULL) { return NULL; } if (pred(head->value)) { tmp = (Node*) malloc(sizeof(Node)); tmp->value = head->value; tmp->next = filter(head->next, pred); } else { return filter(head->next, pred); } return tmp; }
Функцию, которая возвращает логическое значение, принято называть предикат.
Последовательное выполнение и утечка памяти
Функции map, reduce (foldl и в большей степени foldr) и filter нашли очень широкое применение в программировании. Особенно привлекательным выглядит объединение этих функций и передача параметров от одной функции к другой. Такое связывание ряда функций в цепочку, когда следующая получает результаты предыдущей, обычно называют chaining; в нашем случае, к сожалению, простое последовательное применение не возможно, так как будет происходить утечка памяти.
int dbl(int i) { return i * 2; } int plus(int a, int b) { return a + b; } int even(int a) { return (a % 2) == 0; } void main() { Node* head = NULL; int arr[] = {1,2,3,4,5,6,7,8,9,10}; fromArray(&head, arr, 10); printLinkedList(head); printf("%d", foldr(map(filter(head, even), dbl), plus)); deleteList(&head); getch(); }
При вызове функции filter будет создан новый список L1, который будет передан в функцию map. Функция map в свою очередь создаст новый список L2, а переданный ей L1 не уничтожит. L2 также не будет уничтожен и продолжит храниться в памяти. Самым простым решением будет явное сохранение значений в переменных, а затем явное освобождение памяти
void main() { Node *head = NULL; Node *tmp1, *tmp2 = NULL; int arr[] = {1,2,3,4,5,6,7,8,9,10}; fromArray(&head, arr, 10); printLinkedList(head); tmp1 = filter(head, even); tmp2 = map(tmp1, dbl); deleteList(&tmp1); printf("%d", foldr(tmp2, plus)); deleteList(&tmp2); deleteList(&head); getch(); }
Другим решением будет создание структуроразрушающих функций - таких функций, которые вместо создания нового списка будут изменять текущий. Таким образом, они будут работать с одним и тем же списком, изменяя его.
