Отображение АСД на СДХ
Отображение
АСД на СДХ.
Наша задача :
1.Найти отображение АСД -> СДХ;
2.Оценить сложность алгоритмов операций
вставки, замены, поиска и удаления при различных способах отображениях.
1.
Отображения на вектор.
Будем предполагать что мы имеем дело с
неотсортированными структурами. Подробно что означает условие сортированности
мы рассмотрим в разделе IV "Сортировка."
1.1.
Строка
Отображение строки на вектор строится
так:
1. Возьмем антитранзитиное отношение R'
такое что его транзитивное замыкание дает R (для этого достаточно рассмотреть
отношение линейного порядка R без условия 2 - условия транзитивности :
если (a, b) и (b, c) принадлежат R, то
(a, c) тоже принадлежит R;
Ясно что R' задает отношение соседства,
т.е. (a,b) принадл. R' если и только если
Не существ. c: c принадл. M ,
(a,c)принадл.R' и (c,b)принадл.R'
2.Возьмем минимальный элемент в строке
(он существует в силу свойства отношения линейного порядка R); пусть это a;
3.Элементу a сопоставим первый компонент
вектора: I(a)=1;
4.Паре (b,c)принадл.R' сопоставим
I(c)=I(b)+1.
В одном векторе можно хранить несколько
строк. Для этого существует два принципиально разных способа: строки
разделяются специальным признаком - признаком конца, которого нет среди
символов строк; второй способ - в начале каждой строки указывается ее длина.
Последний способ предпочтительней когда
мы имеем дело со строками переменной длины, а первый хорош когда строки
фиксированной длины.
Рассмотрим сложность операций поиска,
вставки, удаления и замены. Операции вставки, удаления и замены содержат
операцию поиска как составную часть.
Предполагаем что частота встречаемости
всех элементов в строке одна и та же. Тогда в среднем (когда мы имеем дело с
множеством строк,а не с одной, двумя) нам придется просомтреть половину строки,
чтобы найти нужный символ: (1/N)+(1/N)2+(1/N)3+...+(1/N)N= (N+1)/2 = ~N/2
Отсюда следует сложность поиска
(количество операций сравнения) пропорциональна половине длины строки.
Для операции вставки сложность
проворциональна длине строки. Действительно, нам надо N/2 сравнений, чтобы
найти место для вставки, а затем N/2 сдвигов вправо, чтобы освободить место для
нового элемента.
Сложность операции удаления равна
сложности операции вставки. Рассуждения здесь аналогично предыдущим.
Нетрудно подсчитать сложность операции
замены - N/2+1.
Основной вывод состоит в том, что при
отображении строки на вектор все операции со строкой имеют линейную сложность,
пропорциональную длине строки.
1.2.
Граф (дерево)
Отображение графа на вектор строится
через метрицу смежности или матрицу инцидентностей. В Pascal, где есть
двумерные массивы такое представление графа очевидно. (См. представление
лабиринта в задаче об Ариадне и Тезее.) При отображении на вектор возможно два
подхода: отображение по строкам или по столбцам.
Здесь мы рассмотрим случай отображения
по строкам. Случай отображения по столбцам полностью аналогичный. При
отображении по строкам элементу матрицы A[i,j] сопоставляется элемент вектора
V[k], где
k=(i-1)n + j, где n - длина строки.
Теперь оценим сложность операции поиска.
Нам придется просмотреть в среднем половину строк - N/2, и половину элементов в
каждой строке - N/2 при условии что часто встречаемости всех элементов
одинакова. Таким образом сложность операции поиска пропорциональна N^2 /4 или
N^2 при больших N.
Однако при оперции удаления нам не надо
сдвигать все элементы как в случае со строкой. Однако, операция вставки трубет
изменения размерности матрицы смежности по каждому измерению с N на N+1. Для
этого нам придется выполнить (N+1) операций присваивания, чтобы заполнить новую
строку в векторе, плюс N+1 сдвигов строк, чтобы добавить к каждой старой строке
по новому элементу, соответствующему N+1 столбцу. Количество операций сдвига
определяется следующим соотношением:
Таким образом сложность операции вставки
будет равна
N^2/4
+ N^3/2 = N^2(N+2)/2.
Следует обратить внимание что
по-прежнему значительный вклад в сложность операций с графами составляет
операция поиска.
Для k-ичного дерева можно предложить
специальный способ отображения на вектор. Компоненту V[0] сопоставляем корню
дерева; компоненты V[1]...V[k] сопоставляем потомкам корня, затем с V[k+1] по
V[2k] размещаем потомков V[1], с V[2k+1] - V[3k] - потомков V[2] и т.д. В общем
случае потомки i-ой вершины, расположенной на j ярусе, будет размещаться в
компонентах вектора
с V[k(k^j -1)/(k-1)+ (i-1)k] компонента
по V[k(k^j -1)/(k-1)+ ik] компонент.
Оценим сложность операции поиска при
таком отображении дерева на вектор. Учитывая, что высота k-ичного дерева из N
вершин равна
H =
log (N(k-1)+1) - 1 ~log(k) N
получаем что число листьев в таком
дереве ~ N^2. Отсюда, при условии равновстречаемости элементов в дереве, нам
надо просмотреть в среднем половину путей (их число равно чмслу листьев в
дереве) длины H каждый. Эти рассуждения дают нам величину
~
Nlog(k) N.
Сравнивая эту оценку с предыдущей для
векторного представления графа N , можно увидеть что данное представление много
эффективнее.
1.3.
Стек
Поскольку стек есть мо существу
единичное дерево все операции с которым осуществляются через корень, то
отображение на стека на вектор достаточно очевидно. С вектором свзываем
указатель p, который указывает на тот компонент вектора, где в данный момент
размещается корень дерева. Изначально p=0. Операция вставки суть
p:=p+1;V[p]:=<новый элемент>. Операция удаления: p:=p-1.
Самый важный вывод состоит в том, что
операции над стеком при векторном представлении не зависят от длины стека.
1.4.
Очередь
Для векторного представления очереди
нам потребуются два указателя t и h для хвоста и головы очереди соотвественно.
Напомним, что удаление элемента из очереди возможно только из головы очереди, а
вставка - только из хвоста.
Одно из возможных отображений очереди
на вектор состоит в том, что полагаем изначально h:=N; t:=N. Тогда изъятие
элемента - h:=h-1; а вставка - t:=t-1. Такое отображение обладает тем
недостатком, что если общее число элементов, прошедших через очередь -
M>>N, при условии что длина очереди не более N, то после вставки N
элементов мы исчерпаем длину вектора в указателе t.
Можно модифицировать этот метод -
зафиксировать положение указателя h:=N. Тогда при изъятии элемента из очереди
нам надо будет сдвигать все элементы на единицу вправо и корректировать
значение указателя t. Чем больше средняя длина очереди, тем менее выгодно такое
представление ( длина сдвига увеличивается).
Третий способ представления очереди
через вектор состоит в том, что мы "загибаем" вектор в кольцо. Для
этого достаточно выполнять все операции в указателями по модулю N. При таком
представлении очереди сложность операций вставки и изъятия становятся
совершенно не зависимыми от размера очереди.
1.5.
Таблицы
Отображение таблиц на векторную память
будет рассмотрено позднее в разделе "Таблицы".
Основным недостатком векторного
представления АСД - ограниченность длины вектора. Ее мы должны знать заранее.
Кроме этого, как мы видели достаточно часто нам приходится двигать компоненты
вектора при вставке и удалении элементов в векторе.
2.
Представление АСД в списковой памяти
2.1.
Понятие списка
Списком называется множество звеньев
вида
|------------------------------------|
| тело ... | указатель на звено |
|------------------------------------|
увязанных в цепочку с помощью указателей
друг на друга.
Поле тело предназнаяено для хранения
собственно данных, поле указатель на звено - для ссылки на соседнее звено. В
одном звене может быть несколько полей указатель на звено. Значением этого поля
- ссылка на звено.
Каждая ссылка соотвествует
ориентированной, упорядоченной паре в отношении некоторой структуры данных.
Вдоль указателя можно двигаться только в одном направлении.
Звенья можно использовать как для представления
элементов множества структуры, так и для представления элементов отношения.
Звенья можно использовать для наращивания длины поля тело, для связи звеньев
между собой.
Основной недостаток списка - затраты
памяти на хранение указателей. Чем сложнее структура - тем больше указателей
надо для ее представления, тем больше памяти расходуется под указатели.
Основное достоинство - неограниченности
по размеру, динамичность в управлении и организации.
2.2.
Представление строк
Для представления строк можно
использовать звенья со следующими видами поля тело:
- односимвольные звенья;
- многосимвольные звенья;
- звенья переменной длины (в Pascal где
динамические структуры переменной длины не поддерживаются этого вида звенья не
эффективны);
-однонаправленные;
-двунаправленные;
-мультиссылочные (когда один элемент
структуры связан с несколькими другими элементами).
Заметим, что в случае мультиссылочного
звена по некоторым направлениям мы можем иметь двунаправленную связь между
звеньями, а по некоторым - однонапрвленную.
2.3.
Представление графов
При представлении графов можно
использовать несколько подходов:
- использовать звенья только для
представления вершин, а дуги отображать через указатели; недостатком здесь
является то, что негде отобразить информацию, например, о весе дуги, а так же -
в случае неориентированного графа одной дуге будет соотвествовать два
указателя.
- использовать звенья для дуг, а
вершины отображать как ссылки между дугами инцидентными одной и той же вершине;
в этом подходе затруднено представление оринетированных дуг, а так же инфомации
о вершиных;
- наконец можно ввести два вида звеньев
один для представления дуг, другой для представления вершин; звенья-дуги
увязываются в список, звенья-вершины также увязываются в список с перекрестными
ссылками между списками.
Особый случай представляют нерегулярные
графы, т.е. графы в которых степень вершин - величина переменная. В этом случае
используются специальные служебные звенья из двух полей-указателей. Одно поле
служит для ссылки на двругое аналогичное звено, а второе поле - для ссылки на
соотвествующий элемент структуры.
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 - предпорядок, то граф
неориентированный.
Пару (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 вершин имеет
минимальную высоту.
Свойства совершенных деревьев:
- составляют минимальную часть всех
деревьев,
- все пути от корня к листу равноправны.
Список
литературы
Для подготовки данной работы были
использованы материалы с сайта http://www.ergeal.ru/