Если логическую структуру данных удается свести к последовательности элементов данных (записей), то такую логическую структуру называют линейной, в противном случае – нелинейной (деревья, сети).
Древовидные структуры часто представляются линейным списком с последовательным распределением памяти. Здесь возможны следующие два метода.
1. Метод использования адресной арифметики.Хорошо применим к сбалансированным (регулярным) деревьям. В сбалансированном дереве количество исходящих узлов из любого произвольного узла может быть больше двух (например, r ), однако обязательно из каждого произвольного узла (кроме концевого) исходит одинаковое количество порожденных узлов. В этом случае узлы представляются записями фиксированной длины.
Пусть для размещения одного узла дерева требуется квант памяти размером m единиц. В имеющемся векторе памяти А в первом кванте А[1] c адресом a [1] = b помещают корень дерева. Кванты А[2] с адресом a [2] = b + m ; А[3] с адресом a [3] = b + 2m ; ...; А[r+1] с адресом a [r+1] = b + rm заполняют непосредственными потомками корня дерева. Последующие r квантов заполняются непосредственными потомками узла, размещенного в кванте А[2]. Далее r квантов заполняются непосредственными потомками узла кванта А[3] и т.д. Адрес k-го кванта А[k] вычисляют по формуле a [k] = b +(k-1)m . В зависимости от r определяется функциональная зависимость между адресами квантов, в которых размещаются узел и его непосредственные потомки. Для r = 3 непосредственные потомки кванта А[k] – это кванты А[3k-1], А[3k], А[3k+1] с адресами a [3k-1] = b +(3k-2)m , a [3k] = b +(3k-1)m , a [3k+1] = b +3km . Чтобы получить адрес узла, являющегося исходным для узла кванта А[k], надо k разделить на 3 и округлить до целого значения по общим правилам округления. Адрес определяют по формуле a [l] = b +(l-1)m .
Для двоичных сбалансированных деревьев применяют и другой способ адресной арифметики (рис. 9.1 лек.9).
2. Метод использования левосписковых структур.Этот метод примени для любой древовидной структуры и строит последовательность узлов при обходе структуры сверху вниз и слева направо по следующему алгоритму. Выбираются узлы, начиная от корня дерева и до концевого узла включительно по крайней левой ветке дерева. Затем осуществляется подъем вверх до первой следующей ветки, и процесс повторяется. Узлы, выбранные ранее, в последовательность не включаются. Схема обхода дерева поясняется на рис. 11.1.
а
б1
в1
г1
г2
г3
в2
г4
б2
в3
г5
г6
в4
г7
б3
в5
г8
Рис. 11.1. Пример построения левосписковой структуры
В результате обхода дерева получим такую последовательность узлов (а, б1, в1, г1, в1, г2, в1, г3, в1, б1, в2, г4, в2, б1, а, б2, в3, г5, в3, г6, в3, б2, в4, г7, в4, б2, а, б3, в5, г8 ) . Затем удалим ранее выбранные узлы и получим левосписковую структуру (список внизу рис.10.1). При размещении полученной последовательности в памяти можно использовать либо специальные разделители (а (б1 (в1 (г1, г2, г3) в2 (г4)) б2 )( в3 (г5, г6) в4 (г7)) б3 (в5 (г8)))), либо в каждой записи резервировать поле, в котором указывается номер уровня. Доступ к узлам дерева реализуется в прямом и обратном направлениях.
Часто древовидные структуры представляются связанными линейными списками. В этом случае можно использовать следующие методы.
1. Метод указателей на порожденные записи. Он реализует движения по дереву в прямом направлении. Здесь любая запись, кроме записей самого нижнего уровня, должна иметь столько указателей, сколько имеется порожденных записей (рис. 11. 2).
Рис.11.2. Реализация древовидной структуры с использованием указателей на порожденные узлы
2. Метод указателей на исходные записи. В этом методе указатели используются для организации прохода по дереву в обратном направлении – от концевых узлов к корню. (Рис. 11.3)
Рис.11.3. Представление древовидной структуры с помощью указателей на исходные записи
3. Метод указателей на порожденные и исходные записи. Он обеспечивает прохождение дерева как в прямом, так и в обратном направлениях, так как используется двунаправленный список.
4. Метод указателей на порожденные и подобные записи. Он обеспечивает прохождение дерева в прямом направлении. Здесь используется по одному указателю в концевых узлах и по два в остальных (рис. 11.4).
Рис. 11.4. Использование указателей на порожденные и подобные узлы
5. Метод указателей на порожденные, подобные и исходные записи. Он реализует прохождение дерева и в прямом, и в обратном направлениях.
6. Метод кольцевых структур. Если в каждом узле по два указателя ( порожденных и подобных записей), то получим однонаправленные циклические списки (рис. 11.5)
Рис.11.5. Организация дерева с использованием циклических списков
Часто используются двунаправленные циклические списки с четырьмя указателями в каждом узле для обхода в прямом и обратном направлениях как по кольцам порожденных записей, так и по кольцам подобных записей.
7. Метод справочников. Здесь указатели удаляются из записей и организуются в специальные файлы-справочники (рис.10.6). Справочники занимают мало места, обычно полностью размещаются в оперативной памяти, что повышает скорость поиска данных.
Точка входа Файл-справочник Файл записей
К(а)
b1
b1
a1
^
a2 a 3 a4
a1
а
К(б)
b2
b2
a2
a1
a5 a6 a7
a2
б
К(в)
b3
b3
a3
a1
a8
a3
в
К(г)
b4
b4
a4
a1
a9 a10
a4
г
.....
.....
a5
д
a6
ж
a7
з
Указатели на основные Указатели на исходные Указатели на порож-
a8
и
записи
записи
записи
a9
к
a10
л
a11
м
Рис.11.6. Реализация древовидной структуры методом справочника
Для представления сетевых структур часто используют рассмотренные выше методы в определенной комбинации, позволяющей реализовывать сетевую структуру. Например, используют комбинацию методов с указателями на порожденные, подобные и исходные записи. Часто используют кольцевые структуры. Однако для сложных сетевых структур необходимо вводить для каждой записи переменный список указателей. При этом одни связи между записями в сети могут добавляться, другие устраняться. Это создает серьезные проблемы при создании соответствующих обслуживающих программ.
Сложность и трудоемкость организации и использования записей со встроенными указателями переменной длины приводит к целесообразности использования метода справочника (как и для древовидных структур). Чем сложнее структура данных, тем более целесообразно применять справочник.
Точка входа Файл-справочник Файл записей
