Отображение АСД на СДХ.
Наша задача :
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 - просто порядок, то граф - ориентирован, в силу свойства
антисимметричности.
Если 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/