ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2012
137
кой операции
Q
=
A
ρ
,
которую можно выполнять с вычислительной
сложностью
Q
=
ρ
,
если каждому ребру
u
j
∈
U
поставить в однознач-
ное соответствие мощность его образа
⎢
Г
u
j
⎢
и уменьшать эту мощ-
ность на 1, если удаляемая вершина
x
i
∈
Г
u
j
.
Таким образом, каждое
ребро гиперграфа будет задаваться тройкой
<
u
j
,
w
j
,
⎢
Г
u
j
⎢>
.
Моделью исходной двухуровневой структуры двусвязный список
двусвязных списков является граф
DL
G
G
({
Z
у
,
Z
Э
D
,
ZУ
,
Z
Э
L
,
Y
D
,
Y
L
},
FZ
D
,
FZ
L
).
Шаблон этого графа должен находиться в библиотеке мо-
делей базовых и производных структур данных (модели базовых и
некоторых комбинированных и двухуровневых структур данных рас-
смотрены в работах [2, 3]).
Для синтезируемой структуры необходимо задать:
•
вид структуры и имя ее модели;
•
множество кортежей {
<
u
j
,
w
j
,
⎢
Г
u
j
⎢>
/
j
= 1, |
U
исх
|}, которые явля-
ются значениями элементов двусвязного списка
L
D
,
и мощность
m
=
= |
U
исх
| этого множества (
U
исх
–
исходное множество ребер гиперграфа);
•
имена множеств {
X
j
/
j
= 1,
⎢
U
исх
⎢
},
значение элементов которых
принимает первое поле записи элементов двусвязных списков {L
j
/
j
= 1,
⎢
U
исх
⎢
},
и мощности {
⎢
X
j
⎢
/
j
= 1,
⎢
U
исх
⎢
}
этих множеств.
В результате настройки шаблона получим граф
DL
G
G
({
Z
D
,
Z
L
},
{
Y
D
,
Y
L
},
FZ
D
,
FZ
L
),
в котором (рис. 2)
•
Z
D
= {
Z
у
D
,
Z
э
D
};
•
Z
у
D
= {
z
у.н
,
z
у.к
},
z
у.н
↔
а
у.н
,
z
у.к
↔
а
у.к
–
вершины, сопоставлен-
ные адресам указателей начала и конца списка
L
D
соответственно;
•
Z
э
D
= {
zd
j
/
j
= 1, |
U
исх
|},
Z
э
D
↔
A
э
D
,
где
A
э
D
–
адреса элементов
двусвязного списка
L
D
,
zd
j
↔
а
э
Dj
;
•
Z
L
=
{
Z
У
L
,
Z
Э
L
};
•
Z
У
L
= {
Z
j
/
j
= 1, |
U
исх
|},
Z
j
= {
z
у.н
j
,
z
у.к
j
},
z
у.н
j
,
↔
а
у.н
j
,
z
у.к
j
↔
а
у.к
j
–
вершины, сопоставленные адресам указателей начала и конца спис-
ков {
L
j
};
•
Z
э
L
= {
Z
э
Lj
/
j
= 1, |
U
исх
|},
Z
э
Lj
↔
A
э
Lj
,
где
A
э
Lj
= {
аj
i
/
i
= 1, |
X
j
|} –
адреса элементов списка
L
j
,
Z
э
Lj
= {
zj
t
/
t
= 1, |
X
j
|},
zj
t
↔
аj
t
,
|
X
j
| = Г
u
j
;
•
Y
D
= {
yd
j
/
j
= 1,
⎢
U
исх
⎢
},
yd
j
=
<
yd
j
′
,
z
у.н
j
>
,
yd
j
′
↔ <
u
j
,
w
j
,
⎢
Г
u
j
⎢>
;
•
Y
L
= {
Y
Lj
/
j
= 1,
⎢
U
исх
⎢
},
Y
Lj
↔
X
j
,
X
j
= Г
u
j
,
Y
Lj
= {
yj
t
/
t
= 1, |
X
j
|},
yj
t
↔
x
l
;
•
FZ
D
= {
FZ
у
D
,
FZ
Э
D
},
Fz
у.н
={
zd
1
},
Fz
у.к
= {
zd
m
};
•
FZ
э
D
= {
Fzd
j
/
j
= 1,
⎢
U
исх
⎢
},
Fzd
j
=
<
yd
j
,
zd
j
–1
,
zd
j
+1
>
;
•
FZ
L
= {
FZ
У
L
,
FZ
Э
L
},
FZ
У
L
= {
Fz
у.н
j
,
Fz
у.к
j
},
Fz
у.н
j
={
zj
1
},
Fz
у.к
j
=
= {
zj
m
};
•
FZ
э
L
=
{
FZ
э
Lj
/
j
= 1, |
U
исх
|},
FZ
э
Lj
= {
Fzj
t
/
t
= 1, |
X
j
|},
Fzj
t
=
<
yj
t
,
zj
t
–1
,
zj
t
+1
>
.