Для решения задачи автоматического синтеза оптимальных струк-
тур данных необходимо разработатьтакую модельструктуры данных,
которая отражает структурные особенности различных способов орга-
низации данных, существенные с точки зрения вычислительной слож-
ности выполняемых над структурой данных операций, а также ее ем-
костной сложности.
Любая структура данных представляет собой описание одного из
возможных способов размещения конечного множества данных
D
в
памяти. При этом каждому элементу множества данных ставится во
взаимно-однозначное соответствие
P
адрес из множества доступных
адресов памяти
A
↔
D, P
⊂
A
×
D
.
Структура данных кроме полезной информации в виде элементов
данных обычно хранит служебную информацию о связях элементов
между собой. Элемент данных вместе со служебной информацией бу-
дем называть
компонентом
структуры данных. Таким образом, мож-
но говоритьо наличии множества
С
компонентов структуры данных
и множества
Z
, определяющего взаимно-однозначное соответствие
размещенных элементов данных компонентам структуры
P
↔
C
,
Z
⊂
P
×
C
. Связи
F
между компонентами структуры данных ото-
бразим, определив однозначное соответствие
C
→
C
,
F
⊂
C
×
C
.
Для построения моделей конкретных структур данных рассмотрим
основные способы организации данных, лежащие в основе сложных
структур данных — векторный и списковый, и определим основные
компоненты этих структур, отношения компонентов, их характери-
стики и свойства.
Векторный способ организации
предполагает последовательное
размещение однотипных (одинаковых по размеру) элементов в непре-
рывной области памяти. Подобное размещение позволяет определить
адрес любого элемента вектора по его номеру, адресу первого элемен-
та и размеру. При этом адрес текущего элемента можно определить
по адресу любого элемента, находящегося слева или справа от него.
Элементом вектора может бытьэлемент данных, указательна данные
или структуру данных, ключ для получения данных (в этом случае
они хранятся отдельно), признак или флаг (характеристические век-
торы). Компонентом вектора будет являться непосредственно элемент
данных, а множество связей компонентов
F
будет представлятьсобой
декартово произведение множества
С
самого на себя, т.е.
F
=
C
×
C
.
При переходе от объекта к модели поставим во взаимно-однознач-
ное соответствие множеству
D
множество вершин графа
X
D
, а множе-
ству адресов
A
— множество вершин графа
X
А
. Поскольку множество
P
описывает взаимно-однозначное соответствие между множества-
ми
A
и
D
, каждой паре элементов множества
P
сопоставляем ребро
30 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 4
