функций
Q
как
Q
=
{
q
i
(
n
) :
s
i
→
N, i
= 1
,
|
S
|}
,
где
S
=
{
s
i
}
— множество допустимых операций над структурой дан-
ных;
q
i
(
n
)
— функция оценки вычислительной сложности
i
-й опера-
ции.
Таким образом, модельвектора будет выглядетьследующим обра-
зом:
M
V
=
G
V
, Q, L
(
n
)
,
где
G
V
(
{
X
D
, X
A
, l
V
}
,
{
U
AD
,
−→
U
F
}
)
— смешанный граф, описывающий
организацию элементов;
Q
— множество функций, определяющих вы-
числительную сложность операций;
L
(
n
) = 0
— дополнительная ем-
костная сложностьструктуры данных.
Списковая организация данных
подразумевает размещение эле-
ментов списка в произвольных свободных участках памяти. При по-
строении списковых структур с каждым компонентом списка связыва-
ется набор вспомогательных полей, обеспечивающий связь отдельных
компонентов списка между собой. Так, для линейного односвязного
списка компоненты связаны между собой отношением “предыдущий–
следующий” за счет хранения в компоненте адреса следующего ком-
понента. Наличие вспомогательных полей требует рассмотрения до-
полнительных множеств — множества
D
вспомогательных элемен-
тов данных (указателей) и множества
A
— адресов вспомогательных
элементов данных. При этом связи между элементами указанных до-
полнительных множеств представим множеством
P
, каждый элемент
которого определяет соответствие адресов памяти вспомогательным
элементам данных, т.е.
A
↔
D , P
⊂
A
×
D
. Взаимно-однозначное
соответствие
P
↔
C
вспомогательных элементов компонентам дан-
ных определим как множество
Z
, такое, что
Z
⊂
P
×
C
. Неявные
связи между полями в компонентах списка представим как множе-
ство
F
.
Основными структурами со списковой организацией данных, при-
меняемыми для представления графовых моделей и вспомогательных
данных, являются линейные односвязные, линейные двусвязные,
n
-
связные и древовидные списки [3]. Рассмотрим модельпростейшего
односвязного списка, когда с каждым элементом списка связан всего
один элемент данных. Каждый компонент списка представляет собой
запись, а сам список является множеством записей, соединенных меж-
ду собой.
При переходе от объекта к модели поставим во взаимно-однознач-
ное соответствие множествам
A
,
D
,
A
,
D
соответствующие мно-
жества вершин графа
X
A
,
X
D
,
X
А
,
X
D
. Элементы множеств
P
,
P
32 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
