Реферат: Отображение АСД на СДХ

АСД (абстрактные структуры данных) - математическая структура, с помощью которой мы представляем прикладные данные программы.

АЛГОРИТМ ------> ЯЗЫК ПРОГРАММИРОВАНИЯ

В каждом языке программирования существует своя концепция данных.

Назовем структуры данных конкретного ЯП структурой данных хранения (СДХ).

ПРОБЛЕМА: как отобразить АСД алгоритма на СДХ ЯП ?

Над "АСД определены некоторые операции (удалить, заменить элемент и т.д.)

Критерием выбора СДХ является сложность. Следует выбирать как можно более простые СДХ.

ЗАДАЧА. Дано: АСД и набор СДХ.

Требуется: построить АСД -----> СДХ так, чтобы сложность пераций с СДХ (аналогичных операциям с АСД) была минимальной.

Определение: Отношением порядка R на множестве M называют множество пар, обладающих следующими свойствами:

1) рефлексивность: (a,a) Î R {a £ a}

2) транзитивность: a £ b, b £ c Þ a £ c

3) антисимметричность: a £ b, b £ a Þ a = b

если отношение не обладает свойством 3), то R - предпорядок

Отношение строгого порядка, если в п. 3) (a,b) Î R Þ (b,a) Ï R

R - линейный порядок, если R определено для "a и b и R является строгим порядком.

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

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

Примеры: множество натуральных чисел - структура,

множество слов - структура

Индексация I - отображение M на отрезок [ 1..½M½].

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

Строка Граф Дерево Стек Очередь Таблица

Строка

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

Примеры строк: текст, формулы без индексов и др.

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

- переменная длина,

- обращение к элементам строки идет в соответствии с отношением линейного порядка, а не в соответствии с индексацией на этом множестве.

(L,M) I: M Þ [1..ôMô]

- часто строка имеет дополнительную структуру - синтаксис.