Структуры данных.
1. Постановка задачи.
При разработке программ и
алгоритмов важным этапом является этап подбора математической абстракции для
описания данных, используемых в формулировке задачи. Например, в случае поиска
оптимальной стратегии для игры чет-нечет таким объектом была игра, в случае
задачи об Ариадне и Тезее - лабиринт, в задаче о ходе коня - шахматная доска, в
примере из лекции 16 - учреждение. Будем называть предстваление этих объектов-данных
ввиде математических абстракций Абстрактными Структурами Данных (АСД). В случае
игры в качестве АСД мы использовали дерево; в случае лабиринта - граф; в случае
шахматной доски - матрицу.
Выбрав подходящую по своим
математическим свойствам структуру АСД, мы приходим к другой проблеме - как
представить выбранную АСД в терминах тех структур данных, с которыми умеет
работать исполнитель алгоритмов, которые есть в испоьзуемом языке
программирования. Назовем эти струтктуры данных Структурами Данных Хранения
(СДХ). Например, в случае задачи об Ариадне и Тезее мы представили граф,
представляющий лабиринт, в виде матрицы смежности, которую мы представили в
виде соотвествующей СДХ - массива, для шахматной доски мы применили ту же
структуру данных для хранения данных задачи, для учреждения - мы использовали
запись.
Критерием выбора для АСД
подходящей СДХ является эффективность операций над СДХ, являющихся аналогами
соотвествующих операций над АСД. Под эффективностью мы понимаем сложность
алгоритмов над СДХ.
Итак, мы приходим к
следующей проблеме: задано АСД, набор СДХ; требуется построить отображение АСД
-> СДХ так, чтобы сложность алгоритмов операций над СДХ, соотвествующих
надлежащим оперциям над АСД, была бы минимальной.
2. Основные понятия и определения
Структура G на множестве M - это пара (R,M) где R это отношение
порядка на множестве M.
Определение.
Отношение порядка на множестве M это подмножество множества M*M
обладающее следующими свойствами:
1.a