ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
138
Рис. 2. Модель двухуровневой структуры двусвязный список двусвяз-
ных списков – граф
DL
G
G
({
Z
D
,
Z
L
,
Y
D
,
Y
L
},
FZ
D
,
FZ
L
):
yd
j
′
↔ <
u
j
,
w
j
,
⎢
Г
u
j
⎢
,
m
= |
U
исх
|
В выбранной структуре «двусвязный список двусвязных списков»
поиск ребра в множестве
U
требует
m
=
⎜
U
⎜
операций сравнения. С
учетом количества
⎜
Г
x
⎜
=
ρ
≤
m
ребер, инцидентных вершине
x
i
,
их
поиск будет осуществляться с вычислительной сложностью
Q = m
ρ
.
Для выполнения операции поиска в множестве U каждого ребра
u
j
∈
U
i
с вычислительной сложностью
q
i
=
1
зададим отношение
D
в трактовке
«
координата элемента
в
векторной структуре
записи
множества U
исх
соответствует координате равного ему элемента
в списковой структуре
записи множества U»
.
Очевидно, что в по-
лученной структуре элементы соответствующего вектора прямого
доступа
V
будут иметь значение адресов элементов двусвязного
списка
L
D
.
Моделью вектора прямого доступа
V является граф
:
V
G
G
(
Z
V
,
Y
V
,
FZ
V
),
в котором:
•
Z
V
=
{
z
б
V
,
Z
э
V
},
z
б
V
«
а
б
V
,
а
б
V
–
адрес базы вектора
V
;
•
Z
э
V
= {
zv
i
/
i
= 1,
⎜
U
исх
⎜
},
Z
э
V
«
А
э
V
,
А
э
V
–
адреса элементов век-
тора
V
;
•
Y
V
= {
yv
i
/
i
= 1,
⎜
U
исх
⎜
},
yv
i
=
zd
j
,
если
u
i
=
u
j
,
u
i
∈
U
исх
,
u
j
∈
U
и
yv
i
= 0 в противном случае
,
zd
j
«
а
э
Dj
,
а
э
Dj
–
адрес того элемента спис-
ка
L
D
,
в котором хранится ребро
u
j
;
•
FZ
V
=
{
F
1
z
б
V
,
F
2
Z
э
V
,
F
3
Z
э
V
},
F
1
z
б
V
=
Z
э
V
,
F
2
Z
э
V
= {
F
2
zv
i
/
i
= 1,
⎜
U
исх
⎜
},
F
2
zv
i
=
Z
э
V
\
zv
i
,
F
3
Z
э
V
= {
F
3
zv
i
/
i
= 1,
⎜
U
исх
⎜
},
F
3
zv
i
=
yv
i
.