Отображение АСД на СДХ (стр. 2 из 2)
Особый случай представляют нерегулярные графы, т.е. графы в которых степень вершин - величина переменная. В этом случае используются специальные служебные звенья из двух полей-указателей. Одно поле служит для ссылки на двругое аналогичное звено, а второе поле - для ссылки на соотвествующий элемент структуры.
2.4. Представление стека и очереди
Стек представляется однонапрвленным списком из звеньев, состоящих из двух полей: тела и ссылки. Ниже приводятся процедуры, реализующие операции загрузки в и выгрузки из стека.
type
звено = record тело: char; следующий:связь end;
связь = Iзвено;
var тело:char;
стек:связь;
procedure загрузить (тело:char;var стек:связь);
var элемент:связь;
begin new(элемент); элементI.тело:=тело;элементI.следующий:=стек;
стек:=элемент
end{загрузить}
procedure выгрузить (var тело:char;var стек:связь);
var использованный:связь;
begin ifnot(стек = nil) then
begin тело := стекI.тело; использованный:= стек;
стек:=стекI.следующий; dispose(использованный) end
else write ('стекпуст')
end{загрузить}
Обратите внимание на значение оператора dispose.
Все соображения о представлении очереди в списковой памяти аналогичны тем, что были приведены в разделе векторного представления очереди. Заметим что кольцевую очередь легче организовать через список. очереди.
Структуры данных
АСД (абстрактные структуры данных) - математическая структура, с помощью которой мы представляем прикладные данные программы.
АЛГОРИТМ ------> ЯЗЫК ПРОГРАММИРОВАНИЯ
В каждом языке программирования существует своя концепция данных.
Назовем структуры данных конкретного ЯП структурой данных хранения (СДХ).
ПРОБЛЕМА: как отобразить АСД алгоритма на СДХ ЯП ?
Над "АСД определены некоторые операции (удалить, заменить элемент и т.д.)
Критерием выбора СДХ является сложность. Следует выбирать как можно более простые СДХ.
ЗАДАЧА. Дано: АСД и набор СДХ.
Требуется: построить АСД -----> СДХ так, чтобы сложность пераций с СДХ (аналогичных операциям с АСД) была минимальной.
Определение: Отношением порядка 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ô]
- часто строка имеет дополнительную структуру - синтаксис.
Операции:
- поиск символа,
- вставка символа,
- удаление символа,
- замена символа.
Граф
Графом гамма называются пары (X,U), где X - множество, U- отношение порядка на X (X - частично упорядоченное множество).
Если U - просто порядок, то граф - ориентирован, в силу свойства антисимметричности.
Если U - предпорядок, то граф неориентированный.
Пару (a,b) соединяют дугой, если пара (a,b) Î множеству U.
Граф гамма называется взвешанным, если каждой дуге мы сопоставляем некоторое вещественное число, называемое весом данной дуги.
m: UÞR
Граф гамма - размеченный, если задано некоторое отображение
h: X Þ A, где A - множество меток.
ПРИМЕРЫ: 1) сеть дорог (вес - расстояние, метка - название населенного пункта). Найти кратчайший путь из п.A в п.B.
2) Найти электрические характеристики в различных участках электрической цепи.
Способы задания графа:
- графический,
- применение матрицы смежности
½x½ = n; X...X
.
X
ì 1, (X, X) Î U
S = í
î 0, (X, X) Ï U
- применение матрицы инцедентности
U...U (дуги)
X
.
X
(Вершины)
ì 1, если X инцендентно U и Xявляется концом дуги U
s = í -1, если X инцендентно U и Xявляется началом дуги U
î 0, в противном случае.
Степень вершины - число дуг входящих (в) и выходящих (из) данной вершины (инцендентных данной вершине).
Степень захода (исхода) - число дуг входящих (выходящих) в (из) данную вершину.
Граф называется регулярным, если степень его вершин постоянна.
Последовательность вершин графа X...Xназывается цепью, если для
" (X, X) Î U, т.е. существуют дуги по которым можно перейти от X к X, от X к X и т.д.
Последовательность вершин графа называется путем, если для
" (X, X) Î U или (X, X) Î U.
Всякая цепь - путь, но не всякий путь - цепь.
Если в цепи X=X, то такая цепь называется цикл.
Граф называется слабосвязанным, если для " его двух вершин существует путь их соединяющий, без относительно их ориентации.
Граф называется сильносвязанным, если для " его двух вершин существует путь их соединяющий, с учетом их ориентации.
Вес пути X ... X - сумма весов дуг этого пути.
m (X ... X) =m (x, x)
Операции:
- вставить вершину,
- удалить вершину,
- вставить дугу,
- удалить дугу и т.д.
С точки зрения графа строка это цепь.
Дерево
Дерево - связный ациклический граф.
Одна вершина в дереве обязательно имеет степень захода 0. Эта вершина - корень дерева. Листья дерева - вершины, имеющие степень исхода равную 0.
Для любой вершины дерева (кроме корня) степень захода равна 1.
Деревья могут быть ориентированные и неориентированные.
Высота дерева (H) - самый длинный путь из корня к листу.
Рекурсивное определение: Множество из одной вершины - дерево.
Если T ... T - деревья, то
Дерево называется k-ичным, если все вершины имеют степень исхода k.
Дерево называется линейным, степень исхода равна 1.
ЗАДАЧА. Подсчитать количество деревьев, имеющих n вершин.
РЕШЕНИЕ. B - число деревьев из i вершин. Следуя рекурсивному определению дерева:
Þ
Дерево совершенное, если любой путь от корня к листу отличается не более чем на 1 от самого длинного пути.
Совершенное дерево из n вершин имеет минимальную высоту.
Свойства совершенных деревьев:
- составляют минимальную часть всех деревьев,
- все пути от корня к листу равноправны.