При решении задач структурного синтеза структуры данных используются для хранения не только основной (информации о графе), но и различной вспомогательной информации. Как было показано в [2, 3], способ организации элементов структуры данных существенно влияет на вычислительную и ёмкостную сложность программы решения задач структурного синтеза. Следовательно, для решения ряда задач, одной из которых является задача синтеза оптимальных структур данных, необходимо разработать такую модель структуры данных, которая отражает структурные особенности различных способов хранения данных, существенные с точки зрения оценки вычислительной сложности операций, выполняемых над структурой данных, а также ёмкостной сложности структуры данных.

Любая структура данных представляет собой описание одного из возможных способов размещения конечного множества данных D в памяти. При этом каждому элементу множества данных ставится во взаимнооднозначное соответствие P адрес из множества доступных адресов памяти.

Структура данных кроме полезной информации в виде элементов данных зачастую хранит служебную информацию о связях элементов между собой. Элемент данных вместе со служебной информацией будем далее называть компонентом структуры данных. Таким образом можно говорить о наличии множества С компонентов структуры данных и множества , определяющего взаимнооднозначное соответствие размещенных элементов данных компонентам структуры. Для учёта связей между компонентами структуры данных введём однозначное соответствие.

На данный момент при построении сложных структур данных применяется два основных способа организации данных - векторный и списковый.

Векторный способ организации предполагает последовательное размещение однотипных (одинаковых по размеру) элементов в непрерывной области памяти. Подобное размещение позволяет определить адрес любого элемента вектора по его номеру, адресу первого элемента и размеру. При этом адрес текущего элемента можно определить по адресу любого элемента, находящегося слева или справа от него. Элементом вектора может быть: элемент данных, указатель на данные или структуру данных, ключ для получения данных (в это случае данные хранятся отдельно), признак или флаг (характеристические вектора).

Компонентом вектора будет являться элемент данных, а множество связей компонентов F будет представлять собой декартово произведение множества С самого на себя, т.е..

Source: technomag.bmstu.ru