Отображение АСД на СДХ.
    Наша задача :
    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 - длина строки.
    Теперь оценим сложность операции поиска. ............