ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
140
вершины
x
i
в множестве
A
э
L
= {
A
э
j
/
j
= 1, |
U
исх
|}
адресов элементов
списков {
L
j
|}. Соответственно, для всего множества вершин
X
необхо-
димо иметь множество списков
S
= {
S
i
/
i
= 1, |
X
исх
|}, что обеспечит
прямой доступ к каждому элементу
x
i
по всем {Г
u
j
}.
Моделью каждого односвязного списка адресов
S
i
является граф
Si
G
G
(
Z
i
,
Y
i
,
FZ
i
),
в котором:
•
Z
i
=
{
z
у.н
Si
,
Z
э
i
};
•
z
у.н
Si
«
а
у.н
Si
,
а
у.н
Si
–
указатель начала каждого списка
S
i
;
•
Z
э
i
= {
zi
k
/
k
= 1,
⏐
Г
x
i
⏐
},
zi
k
=
zj
r
,
если
x
i
«
yj
r
и
yj
r
является первым
элементом кортежа
<
yj
r
,
zj
r
–1
,
zj
r
+1
>
=
Fzj
r
,
Z
э
i
⊂
Z
э
L
,
Z
э
L
= {
Z
э
Lj
/
j
= 1,
|
U
исх
|}, т. е.
Z
э
i
–
это подмножество вершин, сопоставленных адресам
тех элементов множества двусвязных списков {
L
j
},
значениями кото-
рых является вершина
x
i
;
•
Y
i
=
Z
э
i
\
zi
1
;
•
FZ
i
= {
Fz
у.н
Si
,
FZ
э
i
},
Fz
у.н
Si
= {
zi
1
};
•
FZ
э
i
= {
zi
k
/
k
= 1,
p
},
p
=
⏐
Г
x
i
⏐
,
Fzi
k
= {
zi
k+
1
}
для
k
= 1,
p –
1
и
Fz
p
=
∅
.
Обозначим множество графов
Si
G
G
как
S
G
G
(
Z
S
,
Y
S
,
FZ
S
)
= {
Si
G
G
(
Z
i
,
Y
i
,
FZ
i
)
/
i
= 1, |
X
исх
|}, где
Z
S
= {
Z
i
/
i
= 1, |
X
исх
|},
FZ
S
= {
FZ
i
/
i
= 1,
|
X
исх
|}.
Объединив по вершинам множеств
Z
э
L
и {
Z
э
i
}
графы
DLV
G
G
и
S
G
G
–
–
DLVS
G
G
(
Z
2,
Y
1,
FZ
2)
=
DLV
G
G
(
Z
1,
Y
1,
FZ
1)
∪
S
G
G
(
Z
S
,
Y
S
,
FZ
S
),
где
Z
2
=
= {
Z
1,
Z
У
S
},
Z
У
S
= {
z
у.н
Si
/
i
= 1, |
X
исх
|},
FZ
2
= {
FZ
1,
FZ
У
S
},
FZ
У
S
=
= {
Fz
у.н
Si
/
i
= 1, |
X
исх
|} и
Fzj
t
=
<
yj
t
,
zj
t
–1
,
zj
t
+1
,
zi
k+
1
>
,
получим модель
трехсвязного списка (рис. 4).
Однако для удаления вершины
x
i
необходимо найти соответству-
ющий список
S
i
.
Таким образом, поиск и удаление вершины будет вы-
полняться с вычислительной сложностью
Q = n
ρ
.
Для исключения
поиска списка
S
i
зададим отношение
D
в трактовке
«
координата эле-
мента x
i
в
векторной структуре
записи множества X
исх
соответству-
ет координате элемента
,
определяющего начало
списка
S
i
в
записи
множества S»
.
Очевидно, что в полученной структуре элементы соот-
ветствующего вектора прямого доступа, назовем его
P
,
будут иметь
значение адресов
а
у.н
i
указателей начала каждого списка
S
i
.
Моделью вектора прямого доступа P является граф
:
P
G
G
(
Z
P
,
Y
P
},
FZ
P
),
в котором:
•
Z
P
=
{
z
б
P
,
Z
э
P
},
z
б
P
«
а
б
P
,
а
б
P
–
адрес базы вектора
P
;
•
Z
э
P
= {
zp
i
/
i
= 1,
⎜
U
исх
⎜
},
Z
э
P
«
А
э
P
,
А
э
P
–
адреса элементов вектора
P
;
•
Y
P
= {
yp
i
/
i
= 1,
⎜
X
исх
⎜
},
yp
i
=
z
у.н
Si
–
если
x
i
не удален из множе-
ства
X
,
и
yp
i
= 0 в противном случае;
•
FZ
P
=
{
F
1
z
б
P
,
F
2
Z
э
P
,
F
3
Z
э
P
},
F
1
z
б
P
=
Z
э
P
,
F
2
Z
э
P
= {
F
2
zp
i
/
i
= 1,
⎜
X
исх
⎜
},
F
2
zp
i
=
Z
э
P
\
zp
i
,
F
3
Z
э
P
= {
F
3
zp
i
/
i
= 1,
⎜
X
исх
⎜
},
F
3
zp
i
=
yp
i
.