Структуры данных. Линейные списки. Стек и очередь. Двоичные деревья



Скачать 118.46 Kb.
страница1/6
Дата06.11.2018
Размер118.46 Kb.
Название файла-
  1   2   3   4   5   6

МИНИСТЕРСТВО НАУКИ И ОБРОЗОВАНИЯ РЕСПУБЛИКИ КАЗАХСТАН

ТАРАЗСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМЕНИ М.Х.ДАЛУТИ



СРМ

На тему: Структуры данных. Линейные списки. Стек и очередь. Двоичные деревья.

Выполнила: Балгынбаева К.А.

Проверила: Беглерова С.Т.

Тараз 2018

Структуры данных.

При разработке программ и алгоритмов важным этапом является этап подбора математической абстракции для описания данных, используемых в формулировке задачи. Например, в случае поиска оптимальной стратегии для игры чет-нечет таким объектом была игра, в случае задачи об Ариадне и Тезее - лабиринт, в задаче о ходе коня - шахматная доска, в примере из лекции 16 - учреждение. Будем называть предстваление этих объектов-данных ввиде математических абстракций Абстрактными Структурами Данных (АСД). В случае игры в качестве АСД мы использовали дерево; в случае лабиринта - граф; в случае шахматной доски - матрицу.

Выбрав подходящую по своим математическим свойствам структуру АСД, мы приходим к другой проблеме - как представить выбранную АСД в терминах тех структур данных, с которыми умеет работать исполнитель алгоритмов, которые есть в испоьзуемом языке программирования. Назовем эти струтктуры данных Структурами Данных Хранения (СДХ). Например, в случае задачи об Ариадне и Тезее мы представили граф, представляющий лабиринт, в виде матрицы смежности, которую мы представили в виде соотвествующей СДХ - массива, для шахматной доски мы применили ту же структуру данных для хранения данных задачи, для учреждения - мы использовали запись.

Критерием выбора для АСД подходящей СДХ является эффективность операций над СДХ, являющихся аналогами соотвествующих операций над АСД. Под эффективностью мы понимаем сложность алгоритмов над СДХ.

Итак, мы приходим к следующей проблеме: задано АСД, набор СДХ; требуется построить отображение АСД -> СДХ так, чтобы сложность алгоритмов операций над СДХ, соотвествующих надлежащим оперциям над АСД, была бы минимальной.



Поделитесь с Вашими друзьями:
  1   2   3   4   5   6


База данных защищена авторским правом ©rppna.ru 2017
обратиться к администрации

    Главная страница