Наша задача :
 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/
АвтоМото
Главная страница
