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

1. Постановка задачи.

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

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

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

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

2. Основные понятия и определения

Структура G на множестве M - это пара (R,M) где R это отношение порядка на множестве M.

Определение.

Отношение порядка на множестве M это подмножество множества M*M обладающее следующими свойствами:

 1.a<=a - рефлективность;

 2.если a<=b и b<=c, то a<=c - транзитивность;

 3.если a<=b и b<=a, то a=b - антисимметричность.

Если отношение не обладает свойством антисимметричности, то оно называется предпорядком.

Определение.

Отношение порядка назывется линейным, если оно определено для любых a и b из M.

Определение.

Множество называется частично упорядоченным если на нем зафиксирован некоторый порядок.

Примеры.

 1. Множество натуральных чисел с отношением <=.

 2. Множество слов в алфавите с отношением лексико-графического упорядочения.

 3. Множество людей с отношением родства.

 4. Множество людей с отношением начальник-подчиненный.

Для выбора и обозачения элементов на M используют индексацию I: I - это отображение M -> [ 1.. |M| ].

3. Абстрактные структуры данных.

 Наиболее часто встречающимися абстрактыми структурами данных являются строка, граф, дерево, стек, очередь, таблица.

3.1. Строка

 Строка - конечное множество символов с отношением линейного прядка, определяющем следование символов в строке.

 Примеры: текст, программа, формула.

Свойства строк:

Рекомендуем скачать другие рефераты по теме: банк курсовых работ бесплатно, отчет по практике.



1  2  3  4  5 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки