ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
143
Полученная синтезированная двухуровневая структура представ-
ляет собой трехсвязный список с векторами прямого доступа к эле-
ментам списка
L
D
и указателям начала списков {
S
i
} (
рис. 6). Вычис-
лительная сложность выполнения основных операций доступа к эле-
ментам первого и второго уровня над этой структурой данных благо-
даря реализации в структуре дополнительных отношений составит:
1)
в множестве
<
U
,
W
,
⎢
Г
U
⎢>
:
поиск элемента
•
по номеру
q
i
=
1,
•
по значению (в том числе максимального и минимального)
q
vol
=
m /
2;
2)
в множествах Г
u
j
:
•
удаление элемента
x
k
(
через двусвязный список
S
i
)
q
del
= 1.
•
операция
∀
u
j
∈
Г
x
k
:
Г
u
j
:
= Г
u
j
\
x
k
.
В результате операция будет выполняться с функциональной вы-
числительной сложностью
ρ
,
в то время как в структуре, показанной
на рис. 1, со сложностью, равной
ρ
(
m
+
A
).
L
j
x
1
L
1
L
2
L
r
У.к 1
У.к 2
У.к
j
x
i
x
i
x
r
x
p
x
1
x
t
x
t
x
k
x
k
x
i
x
r
Г
u
1
=
X
1
Г
u
j
=
X
j
Г
u
r
=
X
r
Г
u
2
=
X
2
а
БV
S
1
S
n
Ук
u
2
w
2
Г
u
2
u
r
w
r
Г
u
r
u
j
w
j
Г
u
j
u
1
w
1
Г
u
1
V
0
0
. . .
. . .
. . .
. . .
. . .
У.н
У.к
r
L
D
а
БP
P
0
0
. .
. .
. .
S
i
. .
. . .
U,W,
Г
U
>
Рис. 6. Синтезированная двухуровневая структура – трехсвязный спи-
сок с векторами прямого доступа к элементам списка
L
D
и указателям
начала списков {
S
i
}