Последовательное распределение памяти

Наиболее простым и естественным способом хранения линей­ного списка является последовательное распределение памяти. При таком распределении узлы списка размещаются в последователь-

212

 

Рис. 16.1. Адресная функция для линейного последовательного списка:

b — адрес базы, указывающий на начало вектора данных в памяти; т — размер элемента списка (длина записи); п — размер вектора данных (число записей)

ных элементах памяти, а вектор данных логически отделен от опи­сания структуры хранимых данных.

Пусть структура данных представляет собой линейный список — файл записей фиксированной длины (рис. 16.1).

Адрес каждой записи можно вычислить с помощью адресной функции, отображающей логический индекс записи в адрес фи­зической памяти:

a(i) = b + (/ - l)m.

(16.1)

Реализуем с помощью линейного списка при последователь­ном распределении памяти логическую структуру типа «регуляр­ное дерево» (рис. 16.2).

Элементы логической структуры Д1), Х(2), ..., Д15) разме­щаются последовательно в линейный список, а адресная функ­ция по-прежнему представляет собой уравнение (16.1), где / — номер узла.

Рис. 16.2. Структура типа «регулярное дерево»

По такому дереву можно двигаться в обоих направлениях: от узла Х(к) к его потомкам, удвоив индекс к или удвоив его и доба-

213

 

Рис. 16.3. Размещение двоичного дерева в виде двух поддеревьев: а — элементы от г'-го до (т - 1)-го; б — элементы от (т + 1)-го до^'-го

вив единицу; к узлу, являющемуся исходным для Х(к), разделив к пополам и взяв целую часть.

Рассмотрим еще один метод реализации адресной функции для двоичного дерева. Пусть для представления структуры использует­ся вектор памяти от элемента /до элемента,/. Корень дерева поме­щается в середину вектора с адресом

а=[(/+у)/2],

где [А] — знак операции взятия целой части А.

В элементах памяти от /-го до (т - 1)-го включительно разме­щается левое поддерево; от (т + 1)-го до j -то — правое поддерево (рис. 16.3). Таким образом можно реализовать двоичное сбалан­сированное дерево. Жирным шрифтом выделены «особые» узлы. С помощью такого варианта адресации можно ускорить считыва­ние нужных данных.

Существует еще один метод адресации данных для логических структур произвольного вида — использование так называемых левосписковых структур. Суть данного метода адресации понятна из рис. 16.4, на котором показаны логическая структура, собственно левосписковая структура для нее и последовательный список.

Можно назвать следующие достоинства линейного списка:

• по компактности размещения он наиболее экономичен;

• может размещаться на любом носителе;

• требует для создания и обработки простых программ;

• в ряде случаев обеспечивает наименьшее время выборки. Основными недостатками линейного списка являются:

 

• сложность коррекции списка (добавления или удаления эле­ментов);

• сложность адресной функции для структур общего вида, как и ее программной реализации;

214

(al(bl(cl(dld2d3)c2(d4))h2(c3(d5)c4(d6))b3(c5d7))))

 

й1

Ы

cl

d\

dl

d3

c2

dA

Ы

c3

d5

cA

d6

b3

c5

dl

Рис. 16.4. Использование для адресации левосписковой структуры:

а — логическая структура; б — собственно левосписковая структура; в —- после­довательный список

• непригодность для представления связей типа М : N;

• затрудненность перехода от записи к записи для устройств последовательного доступа.

⇐ Предыдущая31323334353637383940Следующая ⇒

Поделиться: