Операция объединения моделей структур данных.
В резуль та-
те объединения двух и более базовых структур данных получается
новая комбинированная структура. Очевидно, что результирующая и
исходные структуры должны описыватьразмещение одних и тех же
элементов данных в памяти, т.е. набор данных и для исходных струк-
тур, и для структуры-результата должен быть один и тот же.
В качестве примера рассмотрим объединение древовидного списка
M
1
и вектора
M
2
, которые описываются следующим образом:
M
1
=
G
1
, Q
1
, L
1
(
n
)
,
G
1
=
G
(
X
1
, U
1
) =
=
G
(
{
X
D
, X
D
1
, X
A
, l
V
, X
A
1
, l
A
}
,
{
U
AD
, U
AD
1
,
−→
U
F
1
, U
1
}
)
,
M
2
=
G
2
, Q
2
, L
2
(
n
)
,
G
2
=
G
(
X
2
, U
2
) =
G
(
{
X
D
, X
A
, l
V
}
,
{
U
AD
,
−→
U
F
2
}
)
,
где
G
1
, G
2
— графы организации элементов древовидного списка и
вектора;
Q
1
, Q
2
— множества функций, определяющих вычислитель-
ную сложностьопераций над структурой данных;
L
1
(
n
)
, L
2
(
n
)
— до-
полнительные объемы памяти для организации древовидного списка
и вектора;
X
D
,
X
A
— множество вершин, соответствующих элементам
данных и их адресам;
U
AD
— множество дуг, отражающих взаимно-
однозначное соответствие между элементами данных и их адресами;
X
D
1
,
X
A
1
,
U
AD
1
— множества вершин и дуг, описывающие дополни-
тельные поля в компонентах древовидного списка;
−→
U
F
1
,
−→
U
F
2
— мно-
жества дуг, отражающих связи компонентов структуры данных между
собой;
U
1
— множество дуг, отражающие связи между полями внутри
компонента.
Графы
G
1
и
G
2
имеют общие вершины
X
A
,
X
D
и ребра
U
AD
, что
позволяет выполнитьоперацию их объединения. Результат объедине-
ния представлен на рис. 3.
Подсчитаем вычислительную и емкостную сложности комбиниро-
ванной структуры данных. В ходе объединения моделей не было вве-
дено никаких вспомогательных конструкций, следовательно, допол-
нительная емкостная сложность комбинированной структуры данных
составит
L
(
n
) =
L
1
(
n
) +
L
2
(
n
)
.
При подсчете вычислительной сложности необходимо учитывать,
что операции доступа можно выполнятьнад любой структурой дан-
ных, входящих в комбинированную структуру (так как все они описы-
вают расположение одних и тех же данных в памяти). Однако опера-
34 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
