- •Оглавление
- •Структуры данных и эффективность алгоритмов.
- •Построение модели задачи. Процедурная абстракция и абстракция данных.
- •Основы анализа алгоритмов. [4 ч.1, гл.17, гл.34.]
- •Наихудшее и среднее время работы.
- •Пример 4. Рассмотрим вычисление полинома
- •Асимптотические обозначения.
- •Сложность задач и нижние оценки.
- •Труднорешаемые задачи и np-полнота. [8, 4 гл.34.]
- •Типы данных и структуры данных.
- •Абстрактные типы данных.
- •Последовательность (Sequence). [13 гл.4,5,11.1; 7 п.2.1-4; 3 гл.3-4; 4 п.10.1-3.]
- •Множество (Set). [7 гл.4.1-4; 13 п.10.2; 2 гл.4.]
- •Словарь (Dictionary, Map), другое название – ассоциативный массив [7 п.4.5-8; 3 гл.12; 2 п.4.10; 13 гл.8.].
- •Очередь с приоритетом (Priority queue). [7 п.4.10-11, п.5.6; 3 гл.9; 4 п.6.5; 2 п.4.10-13; 13 гл.7.]
- •Непересекающиеся множества (Disjoint Sets, Partitions, Разбиения) [7 п.5.5; 4 гл.21; 2 п.4.6-8.].
- •Деревья, графы и отношения общего вида. [13 гл.6,12; 7 гл.3, п.4.12, гл.6-7; 3 гл.17.]
- •Структуры данных как способы представления атд.
- •Линейные структуры данных.
- •Деревья.
- •Поисковые деревья (search tree). [13 гл.9]
- •Splay-дерево [19 п.4.3; 3 п.13.2]
- •Деревья цифрового (позиционного) поиска (DigitalSearchTrees,TrieTrees).[7 п.5.3; 3 гл.15.; 13 п.11.3]
- •Пирамиды (heap), другое название – сортирующее (или частично упорядоченное) дерево. [4 гл.6,19-20]
- •Структуры данных для непересекающихся множеств (отношения эквивалентности). [4 гл.21]
- •Рандомизированные структуры данных.
- •Случайная балансировка бинарных поисковых деревьев. [3 п.13.1]
- •Списки пропусков (Skip Lists). [13 п.8.6; 3 п.13.5]
- •Декартово дерево (Treap). [4 гл.13 Задачи 13-4; 20]
Структуры данных как способы представления атд.
На сегодняшний день разработано и исследовано достаточно обширное количество разнообразных структур данных, позволяющих представлять АТД, широко используемые в практике программирования, и эффективно реализовать соответствующие операции.
Структурные типы данных и структуры данных принято классифицировать на статические и динамические. В случае статических типов конструктор (описатель) этого типа данных фиксирует количество компонентов и взаимосвязи между ними, все значения такого типа одинаковы по количеству компонентов и взаимосвязям между ними. В случае динамических типов конструктор не фиксирует количество компонентов, операции со значениями такого типа могут допускать добавление или удаление компонентов и изменение взаимосвязей между ними.
Среди вышеприведенных базовых структурных типов данных - записи (структуры) являются статическими типами, а файлы динамическими (но ограниченно - допустимо только добавление компонентов в конец файла). Массивы имеют промежуточный статус. В классическом Pascal допускаются только статические массивы, а в Java и С# массив объявляется как динамический, но в периоде выполнения должен быть инициализирован (создан), после чего фактически становится статическим.
АТД «Граф» может быть определен как статический тип данных, не допускающий операции добавления и удаления вершин и ребер, и представлен, например, статической матрицей смежности16. Но для каких-то приложений АТД «Граф» необходим как динамический тип данных с операциями, позволяющими изменять количество компонентов (вершин) и связи между ними (ребра). В этом случае для представления графа потребуется связная динамическая структура данных (реализуемая на основе указателей).
Рекурсивный тип данных - это структурный тип, у которого хотя бы один из компонентов имеет такой же тип, т.е. имеем ситуацию - тип части совпадает с типом целого (или в более общем случае - опосредованно зависит от него через другие совместно определяемые типы данных). Аналогичное определение для рекурсивных структур данных - значений рекурсивного типа данных.
Последовательность можно определить как рекурсивный тип данных - как пару (заголовок, хвост), где заголовок – первый элемент последовательности, а хвост – последовательность остальных её элементов. Но это скорее итерация, чем полноценная рекурсия, однако, если:
«Последовательность» – это либо пустая последовательность (), либо (s1, s2,… sk).
Где si – либо «атом» (элемент базового типа), либо «Последовательность».
то мы получаем рекурсивный (по существу) тип данных (и соответствующую рекурсивную структуру данных – значений этого типа), известный как LISP-список.
Отметим, что LISP-список:
Это (фактически) дерево, поскольку - это последовательность элементов (братьев в дереве), которые могут быть LISP-списками (быть корнями поддеревьев).
Причем доступ к вершинам этого дерева аналогичен стековому – только к заголовку (к первому элементу списка – к первому сыну текущей вершины дерева), а доступ к следующему (к брату текущего сына) получим только выделив хвост. Добавление элемента в такой список тоже допустимо только в начало. Доступ к внукам (сыновьям текущего сына) можно получить, выделив текущий элемент списка.
В состав операций LISP-списка входят – операция «Получить заголовок» (CAR, HEAD), «Получить хвост» (CDR, TAIL) и «Добавить в список новый элемент в качестве первого» (CONS).
Для рекурсивных типов данных естественным является набор операций, согласованный с рекурсивной структурой значений этого типа, и рекурсивные методы обработки таких данных.