Рекурсивные алгоритмы с односвязными списками

Теги: Односвязный список, си, рекурсия



Односвязные списки и рекурсия

Для односвязного списка можно дать просто рекурсивное определение. Односвязный список либо пуст, либо состоит из головы и списка.


L: [],
L: H|L.

В данном случае, [] обозначает пустой список. Под пустым списком будем понимать NULL, то есть указатель типа Node, ссылающийся на NULL это тоже список. Под головой будем понимать первый узел списка.
Из этого определения списка следует примерный алгоритм обработки односвязного списка

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();
}

Другим решением будет создание структуроразрушающих функций - таких функций, которые вместо создания нового списка будут изменять текущий. Таким образом, они будут работать с одним и тем же списком, изменяя его.

Q&A

Всё ещё не понятно? – пиши вопросы на ящик email
Базовые операции. Сортировка слиянием