Рис. 2. Модель односвязного списка:
— вершина данных;
— вспомогательная вершина;
— вершина адреса;
— дуга, связывающая вершины адреса; —— — ребро, связывающее вершину
адреса и вершину данных;
— дуга, связывающая компоненты списка между
собой
взаимно-однозначно сопоставим с ребрами из множеств
U
AD
,
U
AD
.
Связи между полями записей, задаваемые множеством
F
, отобразим
на множество дуг
−→
U
A
. Связи компонентов между собой, задаваемые
множеством
F
, отобразим на множество дуг
−→
U
F
. Таким образом, мно-
жеству компонентов односвязного списка
С
взаимно-однозначно соот-
ветствует множество подграфов
{
g
(
x
A
, x
D
, x
A
, x
D
,
−→
u
A
, u
AD
, u
AD
)
∈
∈
G
}
(рис. 2).
Выполним оценку емкостной сложности связного списка по мо-
дели. Количество данных, хранимых списком, определяется числом
элементов множества
X
А
, поэтому сопоставим каждому элементу из
этого множества значение веса, равное
l
V
, т.е. (
∀
x
∈
X
A
)
l
V
(
x
) =
l
V
.
Число дополнительных указателей, которые содержит список, опре-
деляется числом элементов множества
X
А
, поэтому сопоставим ка-
ждому элементу из этого множества значение веса, равное
l
A
, т.е.
(
∀
x
∈
X
А
)
l
V
(
x
) =
l
A
. Каждому элементу множеств
X
D
, X
D
со-
поставим значение веса, равное нулю, т.е. (
∀
x
∈
X
D
)
l
V
(
x
) = 0
,
(
∀
x
∈
X
D
)
l
V
(
x
) = 0
. Тогда объем памяти (в байтах), требуемый для
хранения списка, составит
E
(
n
) =
∀
x
∈
X
l
V
(
x
) =
l
V
|
X
A
|
+
l
А
|
X
A
|
=
nl
V
+
nl
A
.
По аналогии с вектором модельсписка будет выглядетьследую-
щим образом:
M
S
=
G
S
, Q, L
(
n
)
,
где
G
S
(
{
X
D
, X
D
, X
A
, l
V
, X
A
, l
А
}
,
{
U
AD
, U
AD
,
−→
U
A
,
−→
U
F
}
)
— смешан-
ный граф, описывающий организацию элементов в структуре данных;
Q
— множество функций, определяющих вычислительную сложность
операций;
L
(
n
) =
nl
A
— дополнительная емкостная сложность списка.
Полученные модели базовых структур данных являются более про-
стыми, чем модели, предложенные в работе [2], так как они не содер-
жат избыточной с точки зрения поставленной задачи информации.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4 33
