13628-1 (Отображение АСД на СДХ)

Отображение АСД на СДХ.

Наша задача :

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