Рекурсивные алгоритмы с односвязными списками
Односвязные списки и рекурсия
Для односвязного списка можно дать просто рекурсивное определение. Односвязный список либо пуст, либо состоит из головы и списка.
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();
}
Другим решением будет создание структуроразрушающих функций - таких функций, которые вместо создания нового списка будут изменять текущий. Таким образом, они будут работать с одним и тем же списком, изменяя его.
