ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
142
Рис. 5. Модель двухуровневой структуры трехсвязный список с векто-
рами прямого доступа к вершинам модели списка
L
D
и вершинам –
указателям начала списков {
S
i
}:
yd
j
′
↔ <
u
j
,
w
j
,
⎢
Г
u
j
⎢
>,
r
= |
U
|,
yp
t
=
z
у.н
Si
•
двусвязного списка данных LD
LD
G
G
({{
<
Z
у
D
,
v
А
>
,
<
Z
э
D
,
Q
,
v
А
>
},
<
Y
D
,
v
З
,
v
А
>
},
FZ
D
);
•
вектора адресов прямого доступа V
V
G
G
({
<
z
б
V
,
v
А
>
,
<
Z
э
V
,
Q
>
},
<
Y
V
,
v
А
>
,
FZ
V
);
•
вектора адресов прямого доступа P
P
G
G
({
<
z
б
P
,
v
А
>
,
<
Z
э
P
,
Q
>
},
<
Y
P
,
v
А
>
,
FZ
P
);
•
каждого односвязного списка адресов Si
Si
G
G
({
<
z
у.н
Si
,
v
А
> <
Z
э
i
,
Q
,
v
А
>
},
FZ
i
),
i
= 1,
n
.
Емкостная сложность комбинированной структуры определяется
как сумма весов
v
вершин объединенного графа
G
с
.
С учетом объ-
единения указанных выше множеств получим
V
с
=
v
А
(3
A m
+ 5
m
+
n
+ 4) +
v
З
m
(
A
+ 3),
где
A
=
⎜
Г
u
⎜
.