Реферат: Отображение АСД на СДХ
Для 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. Представление строк
Для представления строк можно использовать звенья со следующими видами поля тело:
- односимвольные звенья;
- многосимвольные звенья;