ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
141
Рис. 4. Модель двухуровневой структуры трехсвязный список с векто-
ром прямого доступа
V
к вершинам модели списка
L
D
:
yd
j
′
↔ <
u
j
,
w
j
,
⎢
Г
u
j
⎢
,
r
= |
U
|
В результате объединения по вершинам
yp
i
и
z
у.н
Si
графов
DLVS
G
G
и
P
G
G
D P
G
−
G
(
Z
,
Y
,
FZ
)
=
DLVS
G
G
(
Z
2,
Y
1,
FZ
2)
∪
P
G
G
(
Z
P
,
Y
P
,
FZ
P
),
получим модель комбинированной структуры –
трехсвязный список
с векторами прямого доступа к элементам списка
L
D
и к спискам
S
i
.
Здесь
Z
= {
Z
2,
Z
P
},
Y
= {
Y
1,
Y
P
},
FZ
= {
FZ
2,
FZ
P
} (
рис. 5).
Теперь удаление вершины
x
i
заключается в обнулении
Y
Pi
∈
Y
P
графа
P
G
G
,
удалении вершины
Z
э
i
⊂
Z
э
L
,
т. е. графа
Si
G
G
,
и выполняет-
ся с вычислительной сложностью, равной
ρ
.
Таким образом, формальный синтез структуры производится
операцией объединения рассмотренных выше графов:
C
G
G
(
Z
,
Y
,
FZ
)
=
DL
G
G
({
Z
D
,
Z
L
}, {
Y
D
,
Y
L
},
FZ
D
,
FZ
L
)
∪
V
G
G
(
Z
V
,
Y
V
,
FZ
V
)
∪
∪
S
G
G
(
Z
S
,
Y
S
,
FZ
S
)
∪
P
G
G
(
Z
P
,
Y
P
,
FZ
P
).
Модели
рассмотренных структур, содержащие информацию, не-
обходимую для оценки емкостной и вычислительной сложности опе-
раций над ними имеют вид:
•
каждого двусвязного списка данных Lj
Lj
G
G
({
<
{
z
у.н
j
,
z
у.к
j
},
v
А
>
,
<
Z
э
Lj
,
Q
,
v
А
>
},
<
Y
Lj
,
v
З
>
,
F
{
z
у.н
j
,
z
у.к
j
},
FZ
э
Lj
)
,
j
= 1,
m
;