Списки как динамические структуры данных. Виды линейных списков. Способы формирования односвязных списков. Оценка сложности.

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

Список – линейная последовательность элементов, каждый из которых содержит указатели на аналогичные элементы(соседи).

Списки: односвязные(каждый эл-т имеет указатель на следующий), двусвязные(каждый эл-т имеет указатель на следующий и предыдущий), двусвязные циклические(первый и последний эл-ты списка ссылаются друг на друга).

Односвязный список. Включение элемента в начало списка. Удаление элемента из списка по заданному номеру.

Односвязный список. Включение элемента в конец списка. Слияние двух списков.

Слияние – формирование из 2-х списков одного.

Двусвязный список. Удаление и вставка элемента в список.

Циклические списки. Просмотр циклического списка.

Мультисписки. Нелинейные разветвленные списки.

Нелинейный разветвленный список – список, эл-ты которого тоже могут быть списками.

Характеристики разветвленного списка – порядок, глубина, длина.

Мультисписок – многосвязный список, каждый эл-т которого может входить одновременно в несколько односвязных списков.

18. Особенности программирования рекурсивных функций. Линейная рекурсия (примеры).

Рекурсия не может быть безусловной(бесконечной).

При линейной рекурсии функции содержат единственный условный вызов самой себя. Любой циклический алгоритм можно преобразовать в линейно-рекурсивный и наоборот. Пример – факториал.

19. Смешанная, ветвящаяся и бинарная рекурсия (примеры).

Смешанная рекурсия – две или более функции вызывают друг друга циклически. Пример – четное/нечетное.

Ветвящаяся – функция вызывается более одного раза.

Бинарная рекурсия – вызов других функций. Пример – ряд Фибоначчи.

Рекурсия и поисковые задачи. Результат функции рекурсивного поиска, возврат последовательности, правила разработки.

С помощью рекурсии легко решаются задачи, связанные с поиском, основанные на полном или частичном переборе возможных вариантов. В процессе поиска задача разбивается на шаги, на каждом из которых выбирается и проверяется очередной элемент из множества, а алгоритм поиска повторяется для оставшихся данных.

Результат – логический, показывает можно ли через данную точку достигнуть выхода.

Рекурсия и поисковые задачи. Ханойские башни. Генераторы перестановок, сортировки, алгоритмы с матрицами и другие.

С помощью рекурсии легко решаются задачи, связанные с поиском, основанные на полном или частичном переборе возможных вариантов. В процессе поиска задача разбивается на шаги, на каждом из которых выбирается и проверяется очередной элемент множества, а к оставшимся данным алгоритм поиска повторяется.

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

Дерево – граф, обладающий следующими св-вами:

а) существует 1 эл-т, на который не ссылается никакой другой – корень дерева.

б) начиная с корня, следуя по цепочке указателей можно получить доступ к любому эл-ту

в) на каждый эл-т, кроме корня, имеется единственная ссылка.

Ветви, нижележащие – поддеревья, вершины – потомки, листья – не ссылаются на другие узлы.

Бинарные деревья. Вставка элемента.

Дерево, каждая вершина которого имеет не более 2-х потомков. Особенность – значения вершин левого поддерева меньше, правого – больше чем значение в самой вершине.

Бинарные деревья. Удаление элемента.

3 варианта: удаляемый узел – лист, с 1 поддеревом, с 2 поддеревьями(найти следующий за ним узел, извлечь его из дерева и заменить им удаляемый узел).

Бинарные деревья. Поиск. Алгоритм представления любого дерева и леса бинарными деревьями.

Основные операции поиска для бинарного дерева – нахождение конкретного значения, макс/мин, последующего, предыдущего для данного.