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

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

Наша задача :

 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.

               

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

   : UR

 

Граф гамма - размеченный, если задано некоторое отображение 

                     : 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

     =   -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 - сумма весов дуг этого пути.

    

  (X ... X) = (x, x)



Операции:

 - вставить вершину,

 - удалить вершину,

 - вставить дугу,

 - удалить дугу  и т.д.



С точки зрения графа строка это цепь.

Дерево

Дерево - связный ациклический граф.



Одна вершина в дереве обязательно имеет степень захода 0. Эта вершина - корень дерева. Листья дерева - вершины, имеющие степень исхода равную 0.



Для любой вершины дерева (кроме корня) степень захода равна 1.



 









Деревья могут быть ориентированные и неориентированные.



Высота дерева (H) - самый длинный путь из корня к листу.



Рекурсивное определение: Множество из одной вершины - дерево. 

Если T ... T - деревья, то 







Дерево называется k-ичным, если все вершины имеют степень исхода k.



Дерево называется линейным, степень исхода равна 1. 



ЗАДАЧА.    Подсчитать количество деревьев, имеющих n вершин.



РЕШЕНИЕ. B - число деревьев из i вершин. Следуя рекурсивному определению дерева:



  

  

  

 

      

 

 



                               



Дерево совершенное, если любой путь от корня к листу отличается не более чем на 1 от самого длинного пути.



Совершенное дерево из n вершин имеет минимальную высоту.



Свойства совершенных деревьев:

 - составляют минимальную часть всех деревьев,

 - все пути от корня к листу равноправны.