- •Оглавление
- •Структуры данных и эффективность алгоритмов.
- •Построение модели задачи. Процедурная абстракция и абстракция данных.
- •Основы анализа алгоритмов. [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]
Типы данных и структуры данных.
Тип данных определяется парой:
Множество возможных значений.
Набор операций с такими значениями.
Семейство типов данных обычно задается парой:
Набор базовых типов.
Набор операций конструирования новых типов на основе базовых и ранее сконструированных.
В (процедурных) языках программирования в состав базовых типов данных обычно входят: числовые (целые и вещественные), символьный и логический типы данных, а также указательный тип данных, который имеет особый статус в наборе базовых. Базовые типы – предопределенные. В частности для них предопределены основные операции, в число которых обычно входят:
операции, возвращающие значения этого типа;
операции сравнения на равенство, возвращающие значение логического типа;
операции сравнения на меньше-больше, если на множестве значений соответствующего базового типа предопределено отношение порядка.
В состав операций конструирования новых типов данных входят конструкторы типов (описатели типов) обычно следующих видов: массивов, записей (структур), а также (последовательных) файлов, у которых в различных (процедурных) языках программирования может быть специфически различный статус. Конструкторы типов занимают фундаментальное положение в языках программирования, они являются базовой основой для создания (конструирования) сложных структур данных13.
Структурные (составные) типы данных – это типы данных, определенные с помощью набора операций конструирования, значениями которых являются наборы данных, связанных в соответствии со способом конструирования (группировки). Значения структурных типов состоят из компонентов (ранее определенных типов), поэтому для таких типов данных особый статус имеют предопределенные операции:
Селекторы компонентов, извлечение компонента по индексам – для массивов, по имени поля – для записей (структур), извлечение текущего компонента (с перемещением к следующему) – для последовательных файлов.
Модификаторы компонентов, позволяющие изменять значение компонентов. Реально в процедурных языках программирования модификаторы компонентов обычно не отличаются по синтаксису от селекторов (переменной с индексами, выборки поля), просто соответствующая языковая конструкция трактуется в правой части присваивания как селектор, а в левой – как модификатор. Но, например, для файлов – ситуация иная, операторы добавления компонентов синтаксически обычно отличаются от операторов чтения-извлечения компонентов.
Как ранее уже отмечалось, структура данных - это набор данных, связанных специальным образом. С определенной точки зрения «структуры данных» можно трактовать как значения структурных типов, хотя с близкой несколько иной точки зрения, возможно правильнее, трактовать как хранилища данных (переменные) структурного типа. Хотя понятие «структура данных» (прежде всего) означает определенный способ организации взаимосвязей между компонентами (и способ представления этих взаимосвязей), но по существу подразумевает и набор операций для работы с ее компонентами.
Новый этап в развитии понятия «тип данных» связан со становлением и утверждением в методологии и практике программирования понятий «абстрактный тип данных» и «объекты и классы». И в теории и в методологии программирования ещё много злободневных вопросов по этим понятиям, но в практике разработки программного обеспечения и собственно программирования эти понятия уже занимают значимое положение.