Векторная структура

Тема 2.3. Проектирование структур данных

Под проектированием структур данных понимают разработку их пред­ставлений в памяти. Основными параметрами, которые необходимо учиты­вать при проектировании структур данных, являются:

• вид хранимой информации каждого элемента данных;

• связи элементов данных и вложенных структур;

• время хранения данных структуры («время жизни»);

• совокупность операций над элементами данных, вложенными структурами и структурами в целом.

Вид хранимой информации определяет тип соответствующего поля па­мяти. В качестве элементов данных в зависимости от используемого языка программирования могут рассматриваться:

• целые и вещественные числа различных форматов;

• символы;

• булевские значения: true и false;

а также некоторые структурные типы данных, например:

• строки;

• записи;

• специально объявленные классы.

При этом для числовых полей очень важно правильно определить диа­пазон возможных значений, а для строковых данных - максимально возмож­ную длину строки.

Связи элементов и вложенных структур, а также их устойчивость и со­вокупность операций над элементами и вложенными структурами определя­ют структуры памяти, используемые для представления данных. Время жиз­ни учитывают при размещении данных в статической или динамической па­мяти, а также во внешней памяти.

Различают две базо­вые структуры организации данных в оперативной памяти: векторную и списковую.

Векторная структура представляет собой последовательность байт памяти, которые исполь­зуются для размещения полей данных (рис. 5.14). Последовательное размещение организованных структур данных позволяет осуществлять прямой доступ к элементам: по индексу (совокупности индексов) - в массивах или строках или по имени поля - в записях или объектах.

Однако выполнение операций добавления и удаления элементов при использовании векторных структур для размещения элементов массивов может потребовать осуществления многократных сдви­гов элементов.

Структуры данных в векторном представлении можно размещать как в статической, так и в динамической памяти. Расположение векторных пред­ставлений в динамической памяти иногда позволяет существенно увеличить эффективность использования оперативной памяти. Желательно размещать в динамической памяти временные структуры, хранящие промежуточные ре­зультаты, и структуры, размер которых сильно зависит от вводимых исход­ных данных.

Дата добавления: 2014-01-07